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!

Discrete: Applications of Propositional Logic, Part 2

We are re-visiting Applications of Propositional Logic today for Part 2, which includes Boolean searches and logic circuits. Make sure you have already read through Part 1, as information there will come in handy for this section.

Problem 3 is about Boolean searches on the internet. When searching on the internet (on Yahoo! or Bing, for example), you can use Boolean search terms to narrow your sea of results. The connectives used are AND, OR, and NOT. If you wanted to search for information about universities in Mexico, you could type “university AND Mexico,” but this would return results for universities in New Mexico also (because “Mexico” is in the name). To further narrow your search, you could instead search for “(university AND Mexico) NOT New,” which would exclude results that contain the word “new.”

Note that Google, the word “NOT” is not used. Instead, a minus sign (“-“) is placed before an excluded term.

To include a search term, use the conjunction AND; to exclude, use NOT. To include either of two search terms, use the connective OR.

Lastly, we will look at logic circuits, which are sometimes used in the design of computer hardware. Instead of words, we use symbols to create logic circuits. The symbol set consists of gates: the “inverter” (NOT gate), the OR gate, and the AND gate. Notice the difference in the shape of the AND and OR gates (shown below).

Here is problem 4.

Begin by reading the statement from left to right. Here, we first need p and r to go through NOT gates, then through an OR gate (green). Beginning at the top left, we construct the two NOT gates that then feed into a single OR gate (green). Next, we need a q that feeds first through a NOT gate, then into an AND gate (red) along with the result of the previous OR gate.

Below that q, we need another p that again feeds through a NOT gate. Then we need another q and r, that go to an OR gate (blue). The product of this OR gate (blue) joins up with the p that has gone through the NOT gate and together, they go through an AND gate (purple). The products of the two AND gates (red and purple) come together and go through an OR gate (orange).

You can check the work by following through the circuit and writing out the products. You should end up with the same statement as given in the problem.

I hope this series has helped you learn more about propositional logic and has allowed you to practice what you have already learned by applying your knowledge to various types of problems. The best way to improve your skills with this topic is to practice (as with any math, right?).

Don’t forget to leave comments about what you are working on, what you would like me to cover in the future, or how you are doing in your studies! I love to read them, and will try to respond to each of you. I am always excited to receive topic suggestions. Thanks for reading!

Discrete: Applications of Propositional Logic, Part 1

I would first like to offer my apologies to my readers for my absence as of late. Life has gotten in the way, as I moved to a new house, acquired a new pet, planted a late garden, and have been without internet for nearly a month. I am hoping the internet situation will soon be remedied, but until then, I hope you will not abandon this blog for inactivity.

Growing weary of Algebra, Calculus, and Number Theory, I decided to jump into a new subject today: Discrete Math. We begin with propositional logic; more specifically, the applications of such. I assume you have already learned the base definitions (proposition, implication, etc.) of propositional logic and turn my attention to the applications in my textbook

Part 1 of this topic includes translating English sentences and testing the consistency of system specifications.

Problem 1 is an example of how to translate English sentences into propositional logic.

In this case, the propositions are defined for us. After reading the sentence a couple of times, a key phrase should instinctively pop out at you: “only if.” You should recall that this phrase is one of many ways that a conditional statement (or implication) is expressed. When you see this phrase, or any other equivalent, underline or add parentheses to define the first and second propositions, generic  p and q. Here is a list of English phrases that are used to express the conditional statement p -> q:

It is very important that you pay attention to the order that p and q appear in these phrases. Many times q appears first, but comes last in the propositional statement!

Back to our problem, you can see below that I’ve underlined the first proposition, “p,” in green and the second, “q,” in blue. The first proposition is simple, but the second is a compound proposition we will have to digest.

Let’s take a closer look at that compound proposition “q.” When breaking down a compound proposition, look for key words such as “and” and “or.”These words highlight conjunctions (and’s) and disjunctions (or’s). “And” appears twice in this proposition (I’ve boxed them in blue). Once again, we can separate everything between the conjunctions into individual propositions (here, underlined in orange, purple, and red).

The orange proposition is exactly proposition “r” given in the problem. The purple proposition is similar to the proposition “m” given in the problem, but there is one key difference: the word “not.” In fact, the portion underlined in purple is the negation of proposition “m,” and it is written as shown or with a bar over the “m.” Lastly, the red proposition is, again, the negation of the listed proposition “b.”

Putting all of these together, as shown above, with conjunctions between each (if “or” had been present, we would use a disjunction instead), we get the second part of the sentence, generic proposition “q.” Since this is a compound proposition, we enclose it in parentheses.

We now return to the original statement. Notice that the first proposition, generic “p,” is exactly the given proposition “g,” and the second is what the compound proposition we just put together. Since this is a conditional statement, we connect the two with an arrow pointing right, as shown below in the final answer.

Translating English sentences into propositional logic requires that you find key phrases, such as the conditional statement phrases we considered earlier and words like “and,” “or,” and “not.”

Problem 2 (below) is an example of how to determine the consistency of a set of system specifications.

A set of system specifications are consistent if they do not contain conflicting requirements. To determine if system specs are consistent, perform the following steps:

You can walk through step (2) by reasoning through truth values or by the use of a truth table. We will do both in this example.

Now back to our problem. Step (1) is to translate these system specifications into propositional logic. This works exactly as Problem 1 did, except this time, we need to define our own propositions.  Define propositions by finding individual statements in the list and assigning them a letter. You can use generic letters (p, q, r), but it is easier if you choose a letter with some connection to the statement.

Each statement is underlined in a different color (above). When a statement is repeated (that is, it has already been assigned a color), I have underlined it in the same color. In this way, we see there are really only three propositions at work here (three colors). They are defined explicitly below.

Use the information from Problem 1 to write each statement using propositional logic. The statements are as follows:

Step (2), then, is where we determine if the specs are consistent. Let’s use reasoning first. In order for all four specs to be true, the final spec must be true. In order for (4) to be T, s must be F (because spec (4) is the negation of s). Now, assuming s is F, the only way for spec (1) to be T is for r to also be F (check the truth table for conditional statements). Now assume that both r and s are false. Since r is F, the only way for spec (3) to be true is if i is also F (again, using the truth table for conditional statements). Since s and i are both false, spec (2) is T. When all three propositions are false, all of the system specifications are true. Therefore, the system is consistent.

Alternately, you could look for a set of truth values that makes all specs true by using a truth table. Begin by creating a column for each proposition (towards the left, below) and listing every combination of truth values for those statements. Since there are 3 statements, there will be 2^3 = 8 possibilities or rows.

Next, create a column for each system specification and fill in its truth values according to the truth tables for that operator (here, only conditional statements and a negation are used). Pay careful attention to the order of the propositions. A conditional statement is only false if p is T and q is F (generic p, q). Look at the first spec. It deals with propositions r and s, the first two columns. Look for the cases where r is true, but s is false (I’ve placed a red arrow on those rows.). First, fill in those entries as F, then the rest as T. Fill in the remaining conditional statements similarly (blue and green arrows and circles). The last spec is a simple negation of s. Fill this column in by writing F every time a T appears under s, and writing T every time an F appears.

The system is consistent if there exists a set of propositional truth values that makes ALL specifications true. Look, therefore, for a row in the set of specs in which every spec is true. Here, that occurs at the bottom, when all three propositions are F (in purple, above). If there didn’t exist a row of all true specs, then the system would be inconsistent.

Thus we conclude Part 1 of Applications of Propositional Logic. Part 2, coming next week, will include information on Boolean searches and logic circuits!