# 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.