Discrete: Propositional Equivalences

Today in Discrete Math, we are looking at problems dealing with propositional equivalences. We will cover logical equivalences and propositional satisfiability.

The most fool-proof, though time-consuming, way to verify logical equivalences is by construction of truth tables. This method is sufficient for small compound propositions, but quickly grows out of hand for longer propositions. Also, it requires little thought (which is a large part of its appeal), but reasoning through equivalences will make you more familiar with the laws than truth tables will. Your professor may even disallow the use of truth tables as “proof” of your assertions.

In problem 1 only, we will use a truth table. The process requires little instruction, as it is so simple.

Begin the table with a column for each proposition and enough rows for every combination of truth values for those propositions. In general, 2^n rows are needed to write a truth table for a compound proposition with n base propositions (plus 1 heading row). In this example, there are 3 base propositions, so we will start with 3 columns and 2^3 + 1 = 9 rows. Fill in the heading row and the 8 rows below with every possible combination of truth values for the three propositions (below).

Begin with the left side of the equivalence (part a). Add a column to the table for every operator, including every negation, conjunction, and disjunction. Here, we have two operators (two disjunctions), so we need to add two columns to our table (below). Determine the truth values along each column. Recall that a disjunction is only truth if both propositions are false (red arrows). It is easier to first fill in all the false values (red circles), then add in the truths afterward. Blue arrows and circles refer to the last column, where the only false value appears at the bottom.

Next, create a second truth table using the right side of the equivalence (below).

The final step is to compare the far right columns of each truth table. If the truth values are exactly the same, 

then the two compound propositions are equivalent. These are, as shown below.

Part (b) of this problem is worked the same way. Try it on your own. :)

Another use of truth tables is for determining whether a compound proposition is a tautology. A tautology is a compound proposition that is always true. Therefore, the truth table of a tautology will have only T entries in the far right column.

Reasoning through logical equivalences will better help you learn the laws and basic equivalences. Let’s try an example.

Problem 2 is actually asking that you verify that the contrapositive of a conditional statement is equivalent to the original statement. To show that two compound propositions are logically equivalent (without the use of truth tables), we need to show that both sides are true for exactly the same combinations of truth values of the propositional values. Alternately, we can show that both sides are false for the same combinations.

I will call the conditional statement side A (or the left) and the contrapositive side B (or the right). First, we must determine which route we will take, either when side A is true or when it is false. You should recall that a conditional statement is true in every case except the one in which (T -> F), that is, when p is T but q is F. 

We have two choices: (1) go through each of the three cases in which A is T and determine if B is also T OR (2) consider the only case in which A is F and see if B is F as well. Obviously, the second option is less work, so let’s do that!

Considering the case when side A is F, we will assume that p is T and q is F. Then notq is T (the opposite of q) and notp is F (the opposite of p). Then side B is the situation where (T -> F), which, as noted earlier, is F. Therefore, side B is F when side A is F. Furthermore, this is the only case where side B is F (as we know from the truth table of a conditional statement). Therefore, side A and B are false for exactly the same set of truth values of p and q, and thus, the two sides are logically equivalent.

There, that wasn’t so hard, was it?

Our final example deals with propositional satisfiability. A compound proposition is satisfiable if there is at least one set of truth values for the propositions that makes it true. This (or these) set(s) of truth values are called the solution to the compound proposition. If the compound proposition is always false (the opposite of a tautology), then it is unsatisfiable.

To determine if the compound proposition is satisfiable, we need to find one set of truth values that make the entire proposition true. If we cannot find such a set, we know the proposition is unsatisfiable. Of course, this can be done with truth tables, but we will use our reasoning this time.

Look across the entire compound proposition. Notice that this long string is made up of three conjunctions (red) of four “pieces” (each section in parentheses can be considered a piece; in green below). A conjunction (or set of conjunctions) is only true if every piece is true.

The first piece is a basic conditional statement. It is true in three cases as noted below. Keeping these three cases in mind, we will look at each individually. First, we will assume the truth values of that case. Then, we will systematically go through each of the pieces to determine if they are also true in that case. Once we get to a false “piece,” we can discard that case and move to the next, beginning again with the piece on the left.

We begin by assuming the case truth values. In case (1), that is the case where both p and q are true. The second “piece” contains notq, which would be false (the opposite of q). That makes the second piece entirely false. At this point, we do not need to check the other two “pieces.” With conjunctions, one false “piece” makes the entire thing false.

Now we move on to case (2), below, where p is F and q is T. We must again check the second “piece,” in green, which we find to be true this time. So now we go on to the next “piece,” in blue. Since p is assumed F, notp is T, and thus the third “piece” is true as well. Now the final “piece,” in orange below: we have determined that notp is T and notq is F. This makes the final piece false. That spoils the entire case, and we can mark it off.

We follow the same procedure for the third case. We again return to the “beginning” of the compound proposition and work our way across, piece by piece. This time, the third “piece” fails us. And since every case that makes the first “piece” true does not make every other “piece” true, we have determined there is no set of truth values that will make this entire compound proposition true. Therefore, it is unsatisfiable. To check your work, you can use a truth table.

That’s all for this installment of Math Rescue. I hope you learned something and will continue to return for more helpful posts! Leave a comment below with any topic suggestions, questions, or feedback. Thanks for reading!