Natural Deduction

[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 im not mistaken those logical operators are defined if they werent 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*}
!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.

[StarThrower]

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


"NOR" suffices as well.