Natural Deduction

1. Dec 20, 2003

StarThrower

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. Jan 9, 2004

MathematicalPhysicist

if im not mistaken those logical operators are defined if they werent then how could we use them?

3. Jan 9, 2004

Hurkyl

Staff Emeritus
For the record, you can build any binary operator out of just nand.

4. Jan 9, 2004

MathematicalPhysicist

what does nand mean?

5. Jan 9, 2004

Staff Emeritus
"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?

6. Jan 9, 2004

master_coda

\begin{align*} !A&=A\barwedge A \\ A\wedge B&=(A\barwedge B)\barwedge(A\barwedge B) \\ A\vee B&=(A\barwedge A)\barwedge(A\barwedge B) \end{align*}

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

So you can clearly express NOT, AND and OR using just NAND.

7. Apr 6, 2004

StarThrower

"NOR" suffices as well.