NAND and NOR connectives

Discrete Mathematical Structures
Fundamentals of Logic
NAND, NOR COnnectives
Representing the given compound proposition in terms of only NAND and/or NOR connectives

1. CONNECTIVES –NAND AND NOR
By,
Lakshmi R
Asst. professor,
Dept. of ISE

2. NAND, NOR -CONNECTIVES
Lakshmi R, Asst. Professor, Dept. Of ISE
The compound proposition ¬ ( p ∧q)
: Not p and q
or
p NAND q
The compound proposition ¬ ( p ∨q)
: Not p or q
or
p NOR q
p ↑q
p ↓q

3. NAND, NOR –CONNECTIVES
TRUTH TABLE
Lakshmi R, Asst. Professor, Dept. Of ISE
p q p ∧qp ∨qp ↑qp ↓q
0 0 0 0 1 1
0 1 0 1 1 0
1 0 0 1 1 0
1 1 1 1 0 0
p ↑q ⇔¬ ( p ∧q) ⇔¬p ∨¬q
p ↓q⇔¬ ( p ∨q) ⇔¬p ∧¬q

4. NAND, NOR –CONNECTIVES
Lakshmi R, Asst. Professor, Dept. Of ISE
DeMorgan’sLaw
holds good for ↑
and ↓as well!!
Prove the following:
i.¬ (p ↑q) ⇔¬p ↓¬q
ii.¬ (p ↓q) ⇔¬p ↑¬q
Proof:
i.¬ (p ↑q) ⇔¬(¬ (p ∧q))
⇔¬(¬p ∨¬q)
⇔¬p ↓¬q
ii. ¬ (p ↓q) ⇔¬(¬ (p ∨q))
⇔¬(¬p ∧¬q)
⇔¬p ↑¬q

5. 1. Express the following
propositions in terms of only
NAND and NOR connectives.
i.¬ p
ii.p ∧q
iii.p ∨q
iv.p →q
v.p ↔q
Lakshmi R, Asst. Professor, Dept. Of ISE
i. ¬ p ⇔¬ (p ∧p ) ----By idempotent law, p ∧p ⇔p
¬ p ⇔p ↑p -------eq(1)
<or>
¬ p ⇔¬ (p ∨p ) ----By idempotent law, p ∨p ⇔p
¬ p ⇔p ↓p -------eq(2)
ii. p ∧q ⇔¬ ¬(p ∧q ) -----Law of double negation
⇔¬ (¬p ∨¬q ) -----DeMorgan’sLaw
⇔(¬p ↓¬q ) ----Definition of NOR
⇔((p ↑p)↓(q ↑q)) ----By eq(1) [Can use eq(2)]
iii. p ∨q ⇔¬ ¬(p ∨q ) -----Law of double negation
⇔¬ (¬p ∧¬q ) -----DeMorgan’sLaw
⇔(¬p ↑¬q ) ----Definition of NAND
⇔((p ↑p)↑(q ↑q)) ----By eq(1)
[Can use eq(2)]

6. Lakshmi R, Asst. Professor, Dept. Of ISE
iv.p →q ⇔¬p ∨q
⇔¬ ¬(¬p ∨q) ---Law of double negation
⇔¬ (p ∧¬q ) ---DeMorgan’sLaw
⇔(p ↑¬q ) ----By definition of NAND
⇔(p ↑q ↑q) ---By eq(1)
iv.p ↔q ⇔(p →q ) ∧(q →p ) ----Known fact
⇔(p ↑q ↑q) ∧(q ↑p ↑p) -From solution (iv)
Let A = (p ↑q ↑q) and B = (q ↑p ↑p) and
substitute in the above equivalence
⇔A ∧B
Using solution (ii),
⇔A ∧B ⇔((A ↑A)↓(B ↑B))
Substitute back A and B in the above equivalence
((A ↑A)↓(B ↑B))
⇔(((p ↑q ↑q) ↑(p ↑q ↑q)↓((q ↑p ↑p)↑
(q ↑p ↑p)))
Express the following
propositions in terms of only
NAND and NOR connectives.
i.¬ p
ii.p ∧q
iii.p ∨q
iv.p →q
v.p ↔q

7. Lakshmi R, Asst. Professor, Dept. Of ISE
2. For propositions,p, q, and r, prove the following
i.p ↑(q ↑r) ⇔¬p ∨( q ∧r)
ii.(p ↑q )↑r⇔(p ∧q) ∨¬r
iii.p ↓(q ↓r ) ⇔¬p ∧( q ∨r)
iv.(p ↓q) ↓r ⇔(p ∨q) ∧¬r

8. Lakshmi R, Asst. Professor, Dept. Of ISE
i.p ↑(q ↑r) ⇔¬p ∨( q ∧r)
LHS, p ↑(q ↑r)
⇔¬( p ∧(¬(q ∧r)) ---By the definition of NAND
⇔(¬ p ∨(¬¬(q ∧r)) ---DeMorgan’sLaw
⇔¬ p ∨(q ∧r) ------Law of double negation
ii.(p ↑q )↑r⇔(p ∧q) ∨¬r
LHS, (p ↑q )↑r
⇔¬ (¬( p ∧q) ∧r) ---By the definition of NAND
⇔(¬ ¬(p ∧q) ∨¬ r)---DeMorgan’sLaw
⇔(p ∧q) ∨¬ r---Law of double negation

9. Lakshmi R, Asst. Professor, Dept. Of ISE
iii.p ↓(q ↓r ) ⇔¬p ∧( q ∨r)
iv.(p ↓q) ↓r ⇔(p ∨q) ∧¬r
Solve it!!!