Truth table proofs

Truth tables are used to show all possible values that a given logical expression might take.

Examples

Definition of AND

The following gives the definition of the logical AND operation.

A	B	A ∧ B
false	false	false
false	true	false
true	false	false
true	true	true

Proof of one of De Morgan's laws

A truth table can also be used to prove a logical identity. The following proves De Morgan's law that ¬ (A ∧ B) is equivalent to (¬ A) ∨ (¬ B). Notice that the truth values for these (the last two columns in the table) are always the same.

A	B	A ∧ B	¬ (A ∧ B)	(¬ A) ∨ (¬ B)
false	false	false	true	true
false	true	false	true	true
true	false	false	true	true
true	true	true	false	false

Disproof of a logical fallacy

Truth tables can also be used to disprove a logical fallacy. For example, one fallacy is to assume the converse of an implication holds. If you know that (A → B) is true, and you know that B is true, the fallacy would be to then conclude that A must also be true. Note that the statement - "if an animal is a mammal then it is also a vertebrate" - is true. If we have an animal that is a vertebrate (for example, a dog), it would be a fallacy to now conclude that the animal must also be a mammal.

We will show that this is a logical fallacy - regardless of the statements A and B, just because we know A → B is true, we should not in general assume the converse is also true. First we remind you that (A → B) is equivalent to ¬ A ∨ B. What we want to look at is the claim: ((A → B) ∧ B) → A. If this expression is always true, then we could rely on the converse to always be used. Let us first simplify the expression. It is equivalent to ((¬ A ∨ B) ∧ B) → A. This is equivalent to ¬ ((¬ A ∨ B) ∧ B) ∨ A. We can keep this formula in mind as we evaluate it's truth value for each possible value of A and B.

Consider this truth table.

A	B	A → B	((A → B) ∧ B) → A
false	false	true	true
false	true	true	false
true	false	false	true
true	true	true	true

In the second row, we see that the last column is false. This is where we should expect to see a problem - the place where B is true, but we should not be able to conclude that A must also be true. We have shown that we cannot always apply the converse.