1.1.4: Logical equivalence
- Page ID
Suppose we want to verify that, in fact, (p∧q)∧r and p∧(q∧r) do always have the same value. To do so, we have to consider all possible combinations of values of p, q, and r, and check that for all such combinations, the two compound expressions do indeed have the same value. It is convenient to organize this computation into a truth table. At ruth table is a table that shows the value of one or more compound propositions for each possible combination of values of the propositional variables that they contain. We call each such combination a situation. Figure 2.1 is a truth table that compares the value of (p ∧ q) ∧ r to the value of p ∧ (q ∧ r) for all possible values of p, q, and r. There are eight rows in the table because there are exactly eight different ways in which truth
Figure 2.1: A truth table that demonstrates the logical equivalence of (p ∧ q) ∧ r and p ∧ (q ∧ r). The fact that the last two columns of this table are identical shows that these two expressions have the same value for all eight possible combinations of values of p, q, and r.
values can be assigned to p, q, and r. In this table, we see that the last two columns, representing the values of (p ∧ q) ∧ r and p ∧ (q ∧ r), are identical.
We discuss the creation of truth tables for statements written in propositional logic in more detail in one of the pencasts of this course: youtu.be/ SOZqDm0bDuc. We also discuss using truth tables to test for equivalence in another pencast youtu.be/sWu0fUu7s5c.
You can write the rows in a truth table in any order you like. I suggest you write them in a sorted order, as in Table 2.1. This helps you to be systematic in writing out the table.
More generally, we say that two compound propositions are logically equivalent if they always have the same value, no matter what truth values are assigned to the pro- positional variables that they contain. If the number of propositional variables is small, it is easy to use a truth table to check whether or not two propositions are logically equivalent.
When writing a piece of code you will often have your code make decisions. For instance in a bit of Java code—such as in your Object-Oriented Program- ming course—you might encounter an if-statement to check if the user has inputted the right type of data. Since the input you expect can be rather difficult, the if-statement is a complex combination of many simple checked chained together by &&’s and ||’s. After taking a look at the code, you be- lieve it can be simplified to a much smaller expression. Using a truth table you can prove that your simplified version is equivalent to the original.