Tautologies are extremely useful when it comes to crafting conditional statements in your programs. They can simplify and condense your logical statements by large amounts when implemented successfully.
Biconditional Statements
Tautologies are defined as logically equivalent statements, or more formally, biconditional statements. So a biconditional statement actually consists of two statements.
The notation p↔q states that p and q are logically equivalent. Two statements are logically equivalent if for every possible combination of True and False, the ending logical value is the same. Using a truth table, we can identify if two statements are logically equivalent. For example, let's take a tautology that is obvious.
p↔~(~p)
The negation of the negation of p is obviously equivalent to p, but let's use the truth table to show this.
Remember, the beautiful thing about the truth table is that you can refer to columns you've already filled in. So for the ~(~p) column, all we have to do is negate the ~p column.
Since the values of p and ~(~p) are equal for every combination, we can say p↔~(~p), or p and ~(~p) are logical equivalent.
Let's take a less obvious example. ~(p || q)↔(~p) && (~q).
| p | q | p||q | ~(p||q) | ~p | ~q | (~p) && (~q) |
|---|
| T | T | T | F | F | F | F |
|---|
| T | F | T | F | F | T | F |
|---|
| F | T | T | F | T | F | F |
|---|
| F | F | F | T | T | T | T |
|---|
We see that for every combination of True and False for p and q, the columns for ~(p||q) and (~p) && (~q) are the same. Thus, these statements are logically equivalent.
To put tautologies into context, consider the compound statement "My iPhone is not wet or broken". An equivalent statement would be "My iPhone is not wet and my iPhone is not broken". This is a pretty intuitive statement, and it applies the tautology we just proved.
Useful Tautologies
Now that we've discussed what makes a tautology and how to prove one, here's a reference for useful tautologies you can implement throughout your program. Remember tautologies go "either direction". So you can convert a logical statement in the form of the left side of the arrows to the right side, and vice versa.
| ~(p || q) | ↔ | (~p) && (~q) |
| ~(~p) | ↔ | p |
| (p || q) || r | ↔ | p || (q || r) |
| (p && q) || (p && r) | ↔ | p && (q || r) |
| p || (q && r) | ↔ | (p || q) && (p || r) |
| (p && q) && r | ↔ | p && (q && r) |
| ~(p && q) | ↔ | (~p) || (~q) |
January 13, 2011
Joseph is the lead developer of Vert Studios
Follow Joseph on Twitter: