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*not**q*is T (the opposite of*q*) and*not**p*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*not**q*, 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,*not**p*is T, and thus the third “piece” is true as well. Now the final “piece,” in orange below: we have determined that*not**p*is T and*not**q*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!