Discrete Mathematics: An Open Introduction, 4th edition (preview)

Propositional logic studies the ways statements can interact with each other (the term “proposition” is simply a synonym for “statement”). More precisely, we consider the way the logical form of propositions interact. Thus, propositional logic does not really care about the content of the atomic statements that make up the propositions. For example, in terms of propositional logic, the claims, “if the moon is made of cheese, then cheddar is a type of cheese,” and “if spiders have six legs, then Sam walks with a limp” are exactly the same. That the first statement has two atomic parts that reference cheese is irrelevant. What we care about is that the two molecular statements have the same logical form: they are implications, \(P \imp Q\text{.}\)

Of course, in mathematics we often do know some relationship between various atomic statements (for the record, I do not know any such relationship between the moon’s composition and cheddar). For example, we know a relationship between being even and being a multiple of 10. That relationship allows us to make claims such as, “if the number I’m thinking of is a multiple of 10, then it is even.” What can you conclude from the fact that I am now thinking of an odd number (i.e., not even)? If we accept both statements as true, we can deduce that that I am not thinking of a multiple of 10, and importantly, we can make this deduction without thinking about the nature of numbers. Being able to separate the content from the form of arguments can feel very liberating and provide much needed clarity when trying to understand complicated reasoning.

Our goal in this section is to establish some procedures for analyzing how the truth or falsity of statements interact, based on their logical form. We will see that some molecular statements must be true regardless of whether their atomic parts are true or false, while some statements must always be false. For other statements, it can be that two statements are always true or false together, or that whenever one statements is true, another statement must also be true.

The main method for establishing these relationships will be truth tables. There is a very clear procedure for constructing and analyzing truth tables, but for complicated arguments that contain many atomic statements, the truth tables become very large and unwieldy. We will therefore use truth tables to understand some basic equivalences and deductions, that can be applied in a sequence of reasoning to construct larger arguments.

Here’s a question about playing Monopoly:

True or false? We will answer this question, and won’t need to know anything about Monopoly. Instead we will look at the logical form of the statement.

We need to decide when the statement \((P \imp Q) \vee (Q \imp R)\) is true. Using the definitions of the connectives in Section 1.1, we see that for this to be true, either \(P \imp Q\) must be true or \(Q \imp R\) must be true (or both). Those are true if either \(P\) is false or \(Q\) is true (in the first case) and \(Q\) is false or \(R\) is true (in the second case). So—yeah, it gets kind of messy. Luckily, we can make a chart to keep track of all the possibilities. Enter truth tables. The idea is this: on each row, we list a possible combination of T’s and F’s (True and False) for each of the propositional variables, and then mark down whether the (molecular) statement in question is true or false in that case. We do this for every possible combination of T’s and F’s. Then we can clearly see in which cases the statement is true or false. For complicated statements, we will first fill in values for each part of the statement, as a way of breaking up our task into smaller, more manageable pieces.

Since the truth value of a statement is completely determined by the truth values of its parts and how they are connected, all you really need to know is the truth tables for each of the logical connectives. Here they are:

The truth table for negation looks like this:

None of these truth tables should come as a surprise; they are all just restating the definitions of the connectives. Let’s try another one.

Now let’s answer our question about monopoly:

The statement about monopoly is an example of a tautology, a statement which is true on the basis of its logical form alone. Tautologies are always true but they don’t tell us much about the world. No knowledge about monopoly was required to determine that the statement was true. In fact, it is equally true that “If the moon is made of cheese, then Elvis is still alive, or if Elvis is still alive, then unicorns have 5 legs.”

You might have noticed in Example 1.2.2 that the final column in the truth table for \(\neg P \vee Q\) is identical to the final column in the truth table for \(P \imp Q\text{:}\)

This says that no matter what \(P\) and \(Q\) are, the statements \(\neg P \vee Q\) and \(P \imp Q\) either both true or both false. We therefore say these statements are logically equivalent.

To verify that two statements are logically equivalent, you can make a truth table for each and check whether the columns for the two statements are identical.

Recognizing two statements as logically equivalent can be very helpful. Rephrasing a mathematical statement can often lend insight into what it is saying, or how to prove or refute it. By using truth tables we can systematically verify that two statements are indeed logically equivalent.

Notice that this example gives us a way to “distribute” a negation over a disjunction (an “or”). We have a similar rule for distributing over conjunctions (“and”s):

This suggests there might be a sort of “algebra” you could apply to statements (okay, there is: it is called Boolean algebra) to transform one statement into another. We can start collecting useful examples of logical equivalence, and apply them in succession to a statement, instead of writing out a complicated truth table.

De Morgan’s laws do not do not directly help us with implications, but as we saw above, every implication can be written as a disjunction:

With this and De Morgan’s laws, you can take any statement and simplify it to the point where negations are only being applied to atomic propositions. Well, actually not, because you could get multiple negations stacked up. But this can be easily dealt with:

Let’s see how we can apply the equivalences we have encountered so far.

Notice that the above example illustrates that the negation of an implication is NOT an implication: it is a conjunction! We saw this before, in Section 1.1, but it is so important and useful, it warrants a second blue box here:

To verify that two statements are logically equivalent, you can use truth tables or a sequence of logically equivalent replacements. The truth table method, although cumbersome, has the advantage that it can verify that two statements are NOT logically equivalent.

Earlier we claimed that the following was a valid argument:

How do we know this is valid? Let’s look at the form of the statements. Let \(P\) denote “Edith eats her vegetables” and \(Q\) denote “Edith can have a cookie.” The logical form of the argument is then:

This is an example of a deduction rule, an argument form which is always valid. This one is a particularly famous rule called modus ponens. Are you convinced that it is a valid deduction rule? If not, consider the following truth table:

This is just the truth table for \(P \imp Q\text{,}\) but what matters here is that all the lines in the deduction rule have their own column in the truth table. Remember that an argument is valid provided the conclusion must be true given that the premises are true. The premises in this case are \(P \imp Q\) and \(P\text{.}\) Which rows of the truth table correspond to both of these being true? \(P\) is true in the first two rows, and of those, only the first row has \(P \imp Q\) true as well. And lo-and-behold, in this one case, \(Q\) is also true. So if \(P\imp Q\) and \(P\) are both true, we see that \(Q\) must be true as well.

Here are a few more examples.