Tautology
Armahedi Mahzar (c) 2011
What is a tautology?
Tautology is a logical formula which is true for every possible values of its variables. For example, x OR y = y OR x is true for x=TRUE and y=TRUE and other possible values of x and y. Formulated in Boolean algebra this formula is written as x + y = y + x which is so obvious in numerical algebra. It is the law of commutativity. So, many numerical algebra identities has their logical tatutologies counterpart. But some logical tautology do not have numerical algebra identities.
For example is the laws of idempotency
x+x=x and x.x=x.
Other simple tautologies are
Law of Double Negation:
x” = x
Laws of Absorption:
x+1=1 and x.0=0
Laws of Identity:
x+0=x and x.1 =x
Law of Complementation:
x+x’ =1
Law of Contradiction:
x.x’=0
De Morgan Laws:
(x+y)’=x’.y’ and (x.y)’=x’+y’
Laws of Distribution
x.(y+z)=x.y + x.z and x+(y.z)=(x+y).(x+z)
It is George Spencer-Brown who derived all logical tautologies, in his planar Cross formulation, from just two tautologies as the axioms:
Law of contradiction
x.x’ = 0
written as
(x(x)) =
Law of Distribution
x+(y.z)=(x+y).(x+z)
written as
x((y)(z))=((xy)(xz))
Later on, Louis Kauffman derived both Spencer-Brown axioms, consequently all tautologies, in his Box Algebra formulation, from a single axiom from Huntington Axiom
Reductio ad Absurdum:
(x’+y’)’+(x’+y)’= x
written as
+------+ +------+ |+-++-+| |+-+ | ||x||y|| ||x| y | = x |+-++-+| |+-+ | +------+ +------+
The beautiful thing about Spencer-Brown and Kauffman derivation is that they only use algebraic substitution and replacement rules rather than the logical rule of modus tollens or modus ponens. In the following blogs I’ll try to derive all valid classical syllogism using the concept of tautology.