Following is a slightly more formal version of the proof.
On Dec 19, 2007, at 8:57 AM, Stephen A. Lawrence wrote (in the
WAY_OT: "The Mindless crap shoot of evolution" thread):
Something I encountered with surprise when I first studied logic is
that the primary rule of inference:
(A => B) & A => B
is an assumption, not a theorem.
This depends on the definition of A => B. As used in the above
assertion, (A=>B) has a truth value, otherwise the operation "&" is
not closed. Thus the proposition A=>B can be defined as a function:
(A=>B) == f(A,B)
where f(A,B) can be defined by:
A, B, f(A,B)
F, F, T
F, T, T
T, F, F
T, T, T
or more formally, we can define that
(A=>B) == f(A,B) == (A' + B) == ((not A) or B),
which we can be more comfortable about by looking at an expanded table:
A, B, f(A,B), A', (A' + B)
F, F, T, T, T
F, T, T, T, T
T, F, F, F, F
T, T, T, F, T
where we see the f(A,B) and (A'+B) columns are identical. Now to
apply the definitions and some readily formally proved common
theorems in order to provide a more formal proof, i.e. one that does
not require inspecting a table.
Now, if (A => B) & A => B is true for every choice of (A,B) then,
by definition, the proposition
(A => B) & A => B == f([(A=>B) & A ], B)
must be true for every for every possible choice of A,B.
Substituting (A'+B) for (A=>B) we have:
f([(A=>B) & A ], B) = f ([(A'+B) & A)],B)
Distributing A:
f ([(A'+B) & A)],B) = f([(A' & A) + (A & B)], B)
But (A' & A) = F, by law of the excluded middle, so
f([(A' & A) + (A & B)], B) = f([F + (A & B)], B)
but F+ X = X for all X, so
f([F + (A & B)], B) = f((A & B) , B)
Again applying the definition of f(X,Y) == (X' + Y) we substitute to
obtain:
f((A & B) , B) = (A & B)' + B
By De Morgan's law (A & B)' = A' + B', so, substituting:
(A & B)' + B = (A' + B') + B
Reassociating:
(A' + B') + B = A' + (B' + B)
But (B' + B) = T by the law of non-contradiction, so
A' + (B' + B) = A' + T
but X + T = T for any X, so
A' + T = T
We have thus proven (by the transitive property of equivalence
relations) the proposition:
f([(A=>B) & A ], B) = T
is true for every choice of (A,B), so back substituting (A => B) &
A => B == f([(A=>B) & A ], B) (which can be substituted in either
direction because equivalence relations are symmetric) we have the
proposition
(A => B) & A => B = T
i.e. the proposition (A => B) & A => B is true for every possible
choice of A,B.
Q.E.D.
Horace Heffner
http://www.mtaonline.net/~hheffner/
