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

Natural Deduction

  1. Dec 20, 2003 #1
    Does anyone know a set of axioms for natural deductions? One which leads to the rest of the tautologies of the propositional calculus (and,or,not,if,iff) as theorems?

    I want the number of undefined logical operators to be limited to two, either {not,and} or {not,or}.
  2. jcsd
  3. Jan 9, 2004 #2


    User Avatar
    Gold Member

    if im not mistaken those logical operators are defined if they werent then how could we use them?
  4. Jan 9, 2004 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For the record, you can build any binary operator out of just nand.
  5. Jan 9, 2004 #4


    User Avatar
    Gold Member

    what does nand mean?
  6. Jan 9, 2004 #5


    User Avatar
    Staff Emeritus
    Gold Member
    Dearly Missed

    "Not And". It's the negation of the AND relation. The point being that, I believe it has been proven that any digital circuit you can make with the normal boolean operators you can make with NAND gates. Is that right?
  7. Jan 9, 2004 #6
    !A&=A\barwedge A \\
    A\wedge B&=(A\barwedge B)\barwedge(A\barwedge B) \\
    A\vee B&=(A\barwedge A)\barwedge(A\barwedge B)

    For those less familiar with such notation, [itex]!,\wedge,\vee,\barwedge[/itex] mean NOT, AND, OR and NAND, respectively.

    So you can clearly express NOT, AND and OR using just NAND.
  8. Apr 6, 2004 #7

    "NOR" suffices as well.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook