Discrete Mathematics: An Open Introduction, 4th Edition

Logic studies the ways statements can interact with each other. More precisely, we consider the way the logical form statements can interact. The study of logic does not care about the content of the atomic statements or the meaning of predicates. For example, the claims, “If spiders have six legs, then Sam walks with a limp,” and, “If the moon is made of cheese, then cheddar is a type of cheese,” are identical from a logical perspective. Logic doesn’t care about whether Sam is a spider or the culinary makeup of the moon. Both statements have the same form: They are implications, \(P \imp Q\text{.}\)

Of course, in mathematics we often do know some relationship between various atomic statements. 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.” Suppose I also told you that I am now thinking of a number that is not even. We can deduce that I am not thinking of a multiple of 10! Crucially, if we accept the truth of the statements here, we can make this deduction without thinking about the nature of numbers. It can feel very liberating and provide much-needed clarity when trying to understand complicated reasoning if we can separate the content from the logical form of arguments.

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 statement 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 Definition 1.1.8, 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 a bit messy. Luckily, we can make a chart to keep track of all the possibilities with a truth table.

The idea is this: On each row, we list a possible combination of T’s and F’s (Trues and Falses) 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 the cases in which 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 need to know is the truth tables for each of the logical connectives, which we have already seen in Figure 1.1.9

The truth tables we consider here all build off the basic ones, applying the basic rules multiple times.

Now let’s answer our question about Monopoly.

The statement about monopoly is an example of a tautology, a statement that is necessarily true based on 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, and thus knowing that the statement is true tells us nothing about monopoly. 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.3.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\) are 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.

In Section 1.2 we claimed that whenever an implication is true, so is its contrapositive. We can now make this claim as the following theorem.

Recognizing two statements as logically equivalent can be quite 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 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, except that 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.

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 stating as a theorem.

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.

All the examples we have looked at so far have only involved propositional logic, where the basic units of logic are statements that are either true or false. It is also possible to say that two statements involving quantifiers and predicates are logically equivalent.

Other times, the more interesting times, it is exactly the logic of the quantifiers that makes the statements logically equivalent. What is especially interesting here is that we cannot use truth tables to verify these equivalences!

Instead, we need to reason about the domain of discourse as a set. For example, let’s consider how negation interacts with quantifiers.

Consider the claim that “all odd numbers are prime.” We might represent this symbolically as \(\forall x (O(x) \imp P(x))\text{.}\) The statement clearly is not true, so what is true is that “not all odd numbers are prime” (i.e., \(\neg\forall x(O(x) \imp P(x))\)). How do we know? Easy: 9. Yes, 9 is odd but not prime. But is it enough that just one odd number isn’t prime?

Negating an existential quantifier results in a universal quantifier. This makes sense. If there does not exist something with a property, then everything does not have that property.

Symbolically, we can pass the negation symbol over a quantifier, but that causes the quantifier to switch type.

Another way to see why this makes sense: Universal quantifiers are like (possibly infinite) conjunctions since they claim that the property is true of this thing, and that thing, and the other thing,... all things. Existential quantifiers are like (possibly infinite) disjunctions: The property is true of at least one thing, maybe this, or that, or the other, or.... De Morgan’s laws tell us that when we negate a conjunction, we get a disjunction, and when we negate a disjunction, we get a conjunction. Isn’t it great when everything works out as it should?

It is important to stress that predicate logic extends propositional logic (much like how quantum mechanics extends classical mechanics). Everything that we learned about logical equivalence and deductions still applies. However, predicate logic allows us to analyze statements at a higher resolution, digging down into the individual propositions \(P\text{,}\) \(Q\text{,}\) etc.

To do this, we need to understand how quantifiers and connectives interact. We have already seen something about negations and quantifiers. What about the other connectives? Let’s look at an example exploring how the universal quantifier and disjunctions can (or cannot) work together.

We can also consider how quantifiers interact with each other.

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 that 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.

Think of deduction rules as a sort of one-way form of logical equivalence. Two statements are logically equivalent provided that in every row of the truth table in which the first statement is true, so is the second, and in every row in which the second statement is true, so is the first. A deduction only requires the first of these two parts.

Here are a few more examples.