Next: Statements involving variables Up: NOTES ON SYMBOLIC LOGIC Previous: Statementstruth values and

Logical equivalence and implication

We cannot construct any more than 16 truth tables involving two statements. This is because such a truth table has 4 rows and the truth value of each row is T or F.   Click on the microscope for a list of 16 inequivalent truth tables. However, we can certainly construct more than 16 statements involving two statements. What happens is that many (in fact infinitely many) statements have identical truth tables. We say that the statements r and s are logically equivalent if their truth tables are identical. For example the truth table of

shows that is equivalent to . It is easily shown that the statements r and s are equivalent if and only if is a tautology.

If statements r and s are equivalent we write . For statements involving three statements, r, s and t, there are 64 different truth tables that can be constructed. In general, there are truth tables that can be constructed from n statements.

One common error is think that the statements and its converse are equivalent, but they are not. The conditional statement is equivalent to its contrapositive statement .

We say that r implies s if s is true whenever r is true. If r implies s then we write . Alternatively, r implies s if and only if the statement is a tautology. We say that s is logically deducible from r. For example, in a mathematical theorem the hypothesis implies the conclusion or the conclusion is deducible from the hypothesis.   Click on the microscope for a list of common equivalences and implications.   It is also important to spot equivalent statements when written in English and not just symbollically.

Peter Williams
Mon Sep 2 15:51:33 PDT 1996