# Derive all four propositional logic operators from nand

1. May 5, 2013

### Uvohtufo

So I recently learned that you can derive all four of the propositional logic operators (~, V, &, →) from Nand alone.

As I have understood it, so long as you have negation, and one of the other operators, you can derive the rest. Like P → Q can be defined as ~P V Q.

However, I learned that if you start with the Nand (Not and) operator, you can derive all four. I'll use ' N ' to designate Nand.

The truth table for Nand being
P Q | P N Q
T T | F
F T | T
T F | T
F F | T

~P := P N P
P & Q := (P N Q) N (P N Q)
P V Q := (P N P) N (Q N Q)
P -> Q := (P N Q) N (Q N Q)

Isn't that cool?

2. May 6, 2013

### Stephen Tashi

Yes, it's cool.

I wonder if that explains why NAND gates are common electronic components. But perhaps NAND gates are common only because the circuit is simple to construct.

3. May 6, 2013

### Uvohtufo

Yeah I am not sure.

I think its interesting how when symbolic logic was being invented, implication and negation were viewed as the basic components of logic. Today it seems like programmers view and or or and negation as basic parts.

Unlike philosophers or programmers, electronics people have a cost constraint. Nand is simpler, but is it cheapest?

4. May 6, 2013

### MathematicalPhysicist

You have also NOR.