Recall that the NAND operator(denoted by "|") is equivalent to AND followed by negation; that is, for any two propositions a and b, the propositional form (a|b) is logically equivalent to ￢(a∧b). Express the propositional form c∧(a→b) using only the NAND operator.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
You can rewrite c∧(a→b) as c∧((￢a)∨b). Use de Morgan's law to find that
(1) c∧((￢a)∨b) = c∧(￢(a∧(￢b))) = c∧(a|(￢b)).
Now, observe that since
(2) ￢d = d|d,
￢ can be expressed in terms of the NAND operator. Therefore, ∧ can also be expressed in terms of the NAND operator since
(3) e∧f = ￢(e|f).
Substituting the identities (2) and (3) into (1) as required will give an expression for c∧(a→b) which uses only NAND.
Solution that involves operators NAND and NOT :
$c \land (a \Rightarrow b) \Leftrightarrow c \land (\lnot a \lor b) \Leftrightarrow c \land (\lnot(a\land \lnot b)) \Leftrightarrow c \land (a | \lnot b) \Leftrightarrow \lnot(c | (a| \lnot b))$
Now , as David rightly observed use fact that : $\lnot p \Leftrightarrow p | p$
Note that if (a|b) comes as a propositional form, then c∧(a→b) isn't a propositional form, but (c∧(a→b)) does come as a propositional form. In Polish notation the complete answer goes DDcDaDbbDcDaDbb, which becomes an even bigger mess in infix notation with 14 parenthetical symbols floating around.