What Set of Axioms Leads to All Tautologies in Propositional Calculus?

[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}.

 

[MathematicalPhysicist]

Originally posted by StarThrower


I want the number of undefined logical operators to be limited to two, either {not,and} or {not,or}.

if I am not mistaken those logical operators are defined if they weren't then how could we use them?

 

[Hurkyl]

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

 

[MathematicalPhysicist]

what does nand mean?

 

[selfAdjoint]

Originally posted by loop quantum gravity
what does nand mean?

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

 

[master_coda]

$$\begin{align*}<br /> !A&=A\barwedge A \\<br /> A\wedge B&=(A\barwedge B)\barwedge(A\barwedge B) \\<br /> A\vee B&=(A\barwedge A)\barwedge(A\barwedge B)<br /> \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.

 

[StarThrower]

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

"NOR" suffices as well.