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!