# Express the propositional form ie. using only the NAND operator.

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.

-
Did you try and figure out the equivalents of "^" or "->" or "￢" using only the NAND operator before posing this problem? – Doug Spoonwood Jan 10 '12 at 20:44

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))$

EDIT:

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.

-