Truth Tables and Logical Equivalence
In the last topic, we indicated that statements can be represented by statement variables (such as \(p\) and \(q\)). We also discussed that the truth of formally represented compound statements, such as \(p\wedge q\), often depend on the truth values of simpler statements; in this case \(p\) and \(q\).
Similarly, for a more complicated compound statement, such as \((p\vee \neg q)\wedge r\), the truth values of this statement depends on the truth values of both \((p\vee \neg q)\) and \(r\). But, the value of \((p\vee \neg q)\) depends on the truth values of \(p\) and \(\neg q\). Lastly, \(\neg q\) depends on the truth value of \(q\). So, based on this breakdown, the truth values of a compound statement can be determined from the truth values of the statement variables.
To easily determine the truth value of such a compound statement, we can construct a truth table, which will indicate how the truth values of the compound statement change based on the truth values of the statement variables that compose it.
How to Generate a Truth Table for a Compound Statement
Suppose we want to determine the truth values of the compound statement \((p\vee \neg q)\wedge r\) based on the values of \(p,q\) and \(r\). The number of logical connectives (i.e. \(\vee\), \(\wedge\), and \(\not\)) in this statement is \(3\), and the number of different statement variables we have is also \(3\), so we have six columns total in our table.
| – | – | – | – | – | – |
Start with the full compound statement in the header of the last column of the first row and your statement variables at the left side.
| \(p\) | \(q\) | \(r\) | \((p\vee \neg q)\wedge r\) | ||
Then, work from the outermost connective inward, breaking each compound statement down into its constituent parts, adding them to the first row of your table, working from right to left. Don’t write in duplicate statements.
For instance, we can break down \((p\vee \neg q)\wedge r\) into \((p\vee \neg q\)\) and \(r\) (if we knew whether or not each of these were true, we could determine whether \((p\vee \neg q)\wedge r\) is true). See table below for how this step of the breakdown unfolds.
| \(p\) | \(q\) | \(r\) | \(p\vee \neg q\) | \((p\vee \neg q)\wedge r\) | |
Rinse and repeat, breaking down each newly added statement, adding new entries to the first row of the table, until you either fill in your table, or you can’t break down your statements anymore.
Similar to the last step, we now break down \(p\vee\neg q\) into \(p\) and \(\neg q\). \(p\) is already in the table, so don’t add it. Definitely add the \(\neg q\) though. The completed first row is below.
| \(p\) | \(q\) | \(r\) | \(\neg q\) | \(p\vee \neg q\) | \((p\vee \neg q)\wedge r\) |
NOTE: You may end up with extra columns not filled after break down all your compound statements. This is because the method used to calculate the number of columns you need doesn’t take into consideration duplicate (sub)statements. Just remove the extra columns ifn the rare case where this happens.
Let \(n\) be the number of distinct statement variables you have in your compound statement. The number of rows your truth table will have is \(2^n\).
In our case with \((p\vee \neg q)\wedge r\), we have three statement variables, \(p,q,\) and \(r\). So, we need \(2^3=8\) rows for our table.
| \(p\) | \(q\) | \(r\) | \(\neg q\) | \(p\vee \neg q\) | \((p\vee \neg q)\wedge r\) |
The mini lesson video illustrates how to do this quickly so you don’t miss any. The “True” values below are bolded to help you see the pattern. Double check to make sure you don’t have any duplicate rows!
| \(p\) | \(q\) | \(r\) | \(\neg q\) | \(p\vee \neg q\) | \((p\vee \neg q)\wedge r\) |
| F | F | F | |||
| F | F | T | |||
| F | T | F | |||
| F | T | T | |||
| T | F | F | |||
| T | F | T | |||
| T | T | F | |||
| T | T | T |
For each column in your table, compute the truth value of the statement in the header of that column based on the truth values of statements to the left in the same row.
| \(p\) | \(\underline{q}\) | \(r\) | \(\neg q\) | \(p\vee \neg q\) | \((p\vee \neg q)\wedge r\) |
| F | F | F | T | ||
| F | F | T | T | ||
| F | T | F | F | ||
| F | T | T | F | ||
| T | F | F | T | ||
| T | F | T | T | ||
| T | T | F | F | ||
| T | T | T | F |
For instance, each row of the column \(\neg q\) was computed by looking at the truth values found in the same row in the \(q\) column, because we need to know what \(q\) is to compute \(\neg q\).
Rinse and repeat for all columns until the table is filled out. See result of column 5 below.
| \(\underline{p}\) | \(q\) | \(r\) | \(\underline{\neg q}\) | \(p\vee \neg q\) | \((p\vee \neg q)\wedge r\) |
| F | F | F | T | T | |
| F | F | T | T | T | |
| F | T | F | F | F | |
| F | T | T | F | F | |
| T | F | F | T | T | |
| T | F | T | T | T | |
| T | T | F | F | T | |
| T | T | T | F | T |
Each row of the 5th column was computed by looking at the truth values of \(p\) and a\(\neg q\) in the same row. \(p\vee \neg q\) is true when you see a “T” in either the column for \(p\) or the column for \(\neg q\).
Lastly (for this example) we compute the truth values of the full compound statement that we started with.
| \(p\) | \(q\) | \(\underline{r}\) | \(\neg q\) | \(\underline{p\vee \neg q}\) | \((p\vee \neg q)\wedge r\) |
| F | F | F | T | T | F |
| F | F | T | T | T | T |
| F | T | F | F | F | F |
| F | T | T | F | F | F |
| T | F | F | T | T | F |
| T | F | T | T | T | T |
| T | T | F | F | T | F |
| T | T | T | F | T | T |
Logical Equivalence
Take a look at the following two statements:
- “Bob likes fishing and Bob likes hiking.”
- “Bob likes hiking and Bob likes fishing.”
You would probably agree that these statements say essentially the same thing. All that was changed was the order of the statements “Bob likes fishing” and “Bob likes hiking.” In fact, one could change out these two phrases for any phrases they saw fit, and reach the same conclusion, essentially comparing statements of the form \(p\wedge q\) and \(q\wedge p\). These two statements would end up saying the same thing regardless of what statements are chosen for \(p\) and \(q\). Furthermore, the truth values of \(p \wedge q\) and \(q\wedge p\) would be the same, no matter if \(p\) and \(q\) were true or false.
The equivalence of these statements therefore has nothing to do with the meaning of the phrases chosen, but rather on the truth values of each statement. This leads us into the next key idea, which allows us to determine whether two statements say the same thing logically, based only on the form of the sentences.
So, if we want to determine/prove whether or not statements such as \(P=(\neg p \vee \neg q)\) and \(Q=\neg (p \wedge q)\) are logically equivalent, all we need to do is build a truth table that breaks down both \(P\) and \(Q\) and see if the columns for \(\neg p \vee \neg q\) and \(\neg (p \wedge q)\) are the same in all their truth values. If they are, then \(P\) and \(Q\) are logically equivalent. Otherwise, if there is a row where \(P\) and \(Q\) differ, the two statements are not logically equivalent. See table below for this verification.
| \(p\) | \(q\) | \(\neg p\) | \(\neg q\) | \((p\wedge q)\) | \(\neg (p \wedge q)\) | \(\neg p\vee \neg q\) |
| F | F | T | T | F | T | T |
| F | T | T | F | F | T | T |
| T | F | F | T | F | T | T |
| T | T | F | F | T | F | F |
De Morgan’s Laws
The last truth table example proved one half of a useful logical identity.
Essentially, De Morgan’s Laws give us a handy way of negating conjunction or disjunction.
Examples Making Use of De Morgan’s Laws
Our two statements are \(p=\)”I have cats” and \(q=\)”I have dogs” which comprise the compound statement \(p\wedge q=\)”I have cats and I have dogs.”
To negate this, i.e. to find the opposite of what the original statement says, i.e. to find the value of \(\neg (p\wedge q)\) we use De Morgan’s 1st law, which states \(\neg (p\wedge q)=\neg p \vee \neg q=\)”I don’t have cats or I don’t have dogs.”
Our two statements are \(p=\)”I am fast” and \(q=\)”You are slow” which comprise the compound statement \(p\wedge q=\)”I am fast or you are slow”
To negate this, i.e. to find the opposite of what the original statement says, i.e. to find the value of \(\neg (p\wedge q)\) we use De Morgan’s 2nd law, which states \(\neg (p\vee q)=\neg p \wedge \neg q=\)”I am not fast and you are not slow.”
| \(p\) | \(q\) | \(\neg q\) | \(p\vee \neg q\) | \((p\vee \neg q)\wedge q\) |
| F | F | T | T | F |
| F | T | F | F | F |
| T | F | T | T | F |
| T | T | F | T | T |
| \(p\) | \(q\) | \(\neg p\) | \(\neg p \vee q\) | \((p\wedge (\neg p \vee q))\) | \(\neg (p\wedge (\neg p \vee q))\) |
| F | F | T | T | F | T |
| F | T | T | T | F | T |
| T | F | F | F | F | T |
| T | T | F | T | T | F |
| \(p\) | \(q\) | \(r\) | \((q\wedge r)\) | \(p\vee (q\wedge r)\) |
| F | F | F | F | F |
| F | F | T | F | F |
| F | T | F | F | F |
| F | T | T | T | T |
| T | F | F | F | T |
| T | F | T | F | T |
| T | T | F | F | T |
| T | T | T | T | T |
To prove or disprove the logical equivalence of two statements, simply generate a truth table containing both statements and compare the truth values in the columns of the given two statements. If the columns are identical, the statements are logically equivalent. If the columns differ AT ALL, they are not logically equivalent. The truth table containing \(p\wedge (q\vee p)\) and \((p\wedge \neg q)\) is below.
| \(p\) | \(q\) | \(q\vee p\) | \(p\wedge (q\vee p)\) | \(\neg q\) | \(p\wedge \neg q\) |
| F | F | F | F | T | F |
| F | T | T | F | F | F |
| T | F | T | T | T | T |
| T | T | T | T | F | F |
The fourth and last columns differ in the last row, so the statements given are not logically equivalent.
Create a single truth table breaking down the statements you wish to show are equal. See below.
| \(p\) | \(\neg p\) | \(\neg(\neg p)\) |
| F | T | F |
| T | F | T |
Since the columns of \(p\) and \(\neg(\neg p)\) are identical in their truth values, it follows that \(p\equiv \neg (\neg p)\).
Create a single truth table breaking down the statements you wish to show are equal. See below.
| \(p\) | \(q\) | \(r\) | \(q\vee r\) | \(p\wedge (q\vee r)\) | \(p\wedge q\) | \(p\wedge r\) | \((p\wedge q)\vee (p\wedge r)\) |
| F | F | F | F | F | F | F | F |
| F | F | T | T | F | F | F | F |
| F | T | F | T | F | F | F | F |
| F | T | T | T | F | F | F | F |
| T | F | F | F | F | F | F | F |
| T | F | T | T | T | F | T | T |
| T | T | F | T | T | T | F | T |
| T | T | T | T | T | T | T | T |
Since the columns of \(p\wedge (q\vee r)\) and \((p\wedge q)\vee (p\wedge r)\) are identical in their truth values, it follows that they are logically equivalent.
NOTE: There is an analogous “distribution of OR” property: \(p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)\)