# Find a representation of $\neg p$, $p \wedge q$, $p \vee q$, $p \rightarrow q$, and $p \leftrightarrow q$ using only the logical connective nand.

a) Find a representation of each of the following statements using only the logical connective nand.
i. $\neg p$
ii. $p \wedge q$
iii. $p \vee q$
iv. $p \rightarrow q$
v. $p \leftrightarrow q$

b) Explain why every statement has a representation using only the logical connective nand.

My work so far:

i. $\neg p \Leftrightarrow p \barwedge p$
iii. $p \vee q \Leftrightarrow (p \barwedge p) \barwedge (q \barwedge q)$

• Yes. So far, so good. What problem do you have with the otters? Commented Sep 21, 2017 at 6:45
• My problem is I can't figure out what they are
– Shea
Commented Sep 21, 2017 at 6:45
• Why not? You managed those two just fine. What have you tried with the others? Commented Sep 21, 2017 at 6:48
• I don't know where to start with the others, that's the problem.
– Shea
Commented Sep 21, 2017 at 6:56

$\def\nand{\barwedge}$

i. $\neg p$

Since $p=p\wedge p$ , then indeed $\neg p = p\nand p$ $\checkmark$

ii. $p \wedge q$

Well, $p\wedge q = \neg(p\nand q)$ so...

iii. $p \vee q$

Yes, $p\vee q = \neg(\neg p\wedge \neg q) = \neg p\nand \neg q=(p\nand p)\nand(q\nand q)$ $\checkmark$

iv. $p \rightarrow q$

Well $p\to q = \neg p\vee q$ so...

v. $p \leftrightarrow q$

Likewise $p\leftrightarrow q = (p\to q)\wedge (q\to p)$ so...

• We are only allowed to use $\barwedge$, no other operators can be used. I know how to solve all five of them if I am allowed to use $\neg$, but I can't.
– Shea
Commented Sep 21, 2017 at 6:58
• But you know that $\neg f(p,q)=f(p,q)\nand f(p,q)$... It's the first one you did, and you used that very fact to express $p\vee q$ as $(p\nand p)\nand (q\nand q)$ Commented Sep 21, 2017 at 7:00
• @Shea But You've already showed haw to replace negation with nand. Commented Sep 21, 2017 at 7:04
• ...just substitute... $\neg x=x\nand x$ when $x$ is $(p\land q)$ Commented Sep 21, 2017 at 7:05
• @Shea and if we take another statement $a\equiv p\wedge q$, then how do you write $\neg a$ using only nand? Commented Sep 21, 2017 at 7:06