Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Derive all four propositional logic operators from nand

  1. May 5, 2013 #1
    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. jcsd
  3. May 6, 2013 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
  4. May 6, 2013 #3
    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?
  5. May 6, 2013 #4


    User Avatar
    Gold Member

    You have also NOR.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook