-1
$\begingroup$

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.

  • 1
    Did you try and figure out the equivalents of "^" or "->" or "¬" using only the NAND operator before posing this problem?2012-01-10

3 Answers 3

3

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.

1

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$

0

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.