Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
If this is homework, then please add the homework tag to your question. –  Alexander Thumm Jan 10 '12 at 7:45
1  
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

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer

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$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.