I know that the ↓ operator means "nor" but how do I prove/disprove that every Boolean function can be expressed using only this operator ? Induction ? Contradiction ? I have to idea where to begin. Help would be much appreciated.
Asked
Active
Viewed 942 times
1
-
1Express and, or and not in terms of nor. – copper.hat Dec 18 '13 at 00:15
-
1@copper.hat. Of course you realize that you only have to establish it for {and, not} or {or, not}. – Rick Decker Dec 18 '13 at 00:33
-
@RickDecker: I realise that, I thought it would be more straightforward for the OP to use these and the Shannon expansion theorem. – copper.hat Dec 18 '13 at 00:38
-
@copper.hat. ... which is why I said "Of course you realize that...". Just being pedantic. – Rick Decker Dec 18 '13 at 00:58
2 Answers
1
Hint 1. Have you seen the algorithm that will express every Boolean function in disjunctive normal form? If you have, then you know that every Boolean function can be expressed using only $\land, \lor, \neg$ (and, or, not).
Hint 2. Since DeMorgan tells us that $p\land q\equiv \neg(\neg p \lor \neg q)$, we can express every Boolean function using only $\lor$ and $\neg$.
Hint 3. Show that $\neg p\equiv p\downarrow p$.
Hint 4. Using the above and the fact that $p\lor q\equiv \neg(\neg (p\lor q))$, find a way to express $p\lor q$ in terms of some expression in $p$ and $q$ and $\downarrow$.
Using these hints will give you what you want. Need some more help? Just ask.
Rick Decker
- 8,718
0
Hint: There are 16 binary Boolean functions to represent. You need to represent all of them.
vadim123
- 82,796