1
Mathematical Logic

CHAPTER CONTENTS

1. 1.1 Propositions
2. 1.2 Logical Operators
3. 1.3 Propositional Formulas
4. 1.4 Logical Normal Forms
5. 1.5 The Boolean Satisfiability Problem
6. 1.6 Predicates and Quantifiers
7. 1.7 Symbolizing Statements of the Form “All P Are Q”
   1. Exercises
   2. Notes and Sources
   3. References

The term “logic” has a broad definition, and countless logics have been explored by philosophers, mathematicians, and computer scientists. For most individuals, “logic” typically refers to either propositional logic or predicate logic. Propositional logic, a classical form, involves two truth values (true and false). Predicate logic, on the other hand, expands upon propositional logic by allowing explicit discussion of objects and their properties.

In this chapter, we first study the propositional logic which is the simplest, and most abstract logic we can study. After that, we study the predicate logic. We start by introducing the notion of a proposition.

Throughout this chapter (and the entire book), denotes the set of all natural numbers, denotes the set of all integers, and denotes the set of all rational numbers. For example, 2 and are rational numbers, but and are irrational numbers. We also let denote the set of all real (rational and irrational) numbers.

1.1 Propositions

In this section, we define a proposition and introduce two different types of propositions with examples. To begin with, we have the following definition.

Definition 1.1 A proposition is a statement that can be either true or false.

It is essential to emphasize that the proposition must hold either a true or false value, and it cannot simultaneously possess both. We give the following example.

Example 1.1

Identify each of the following statements as a proposition or not and provide any required clarifications.

1. .
2. .
3. Hillary Clinton is a former president of the United States.
4. Bill Clinton is a former president of the United States.
5. Be careful.
6. Is Abraham Lincoln the greatest president that the United States has ever had?
7. .

Solution

1. “” is a proposition (a true proposition).
2. “” is a proposition (a false proposition).
3. “Hillary Clinton is a former president of the United States” is a proposition (a false proposition).
4. “Bill Clinton is a former president of the United States” is a proposition (a true proposition).
5. “Be careful” is not a proposition.
6. “Is Abraham Lincoln the greatest president that the United States has ever had?” is not a proposition.
7. “” is not a proposition. In fact, the values of the variables have not been assigned. So, we do not know the values of and , and hence it is neither true or false.

▄

Sometimes a sentence does not provide enough information to determine whether it is true or false, so it is not a proposition. An example is, “Your answer to Question 13 is incorrect.” The sentence does not tell us who we are talking about. If we identify the person, say “Adam’s answer to Question 13 is incorrect,” then the sentence becomes a proposition.

Note that, for a given statement, being not able to decide whether it is true or false (due to the lack of information) is different from being not able to know how to verify whether it is true or false. Consider Goldbach’s conjecture1: “Every even integer greater than 2 can be written as the sum of two primes.”2 Despite its origin dating back to 1742 and computational data suggesting its validity, this conjecture remains an open problem in number theory. It is impossible for this sentence to be true sometimes, and false at other times. As of now, no one has proved or disproved this claim, classifying it as a proposition with an undetermined truth value because it cannot simultaneously be both true and false, and its resolution may await future mathematical breakthroughs.

There are some sentences that cannot be determined to be either true or false. For example, the sentence: “This statement is false.” This is not a proposition because we cannot decide whether it is true or false. In fact, if the sentence: “This statement is false” is true, then by its meaning it is false. On the other hand, if the sentence: “This statement is false” is false, then by its meaning it is true. Therefore, the sentence: “This statement is false” can have neither true nor false for its truth value. This type of sentence is referred to as paradoxes.3 The study of a paradox has played a fundamental role in the development of modern mathematical logic.

Note that the sentence “This statement is false,” which is self-contradicting, is different from the sentence “This statement is true,” which is self-consistent on either choice. Nevertheless, neither is a proposition. The latter type of sentence is referred to as an anti-paradox.4 The question that arises now is: Why the sentence “This statement is true” is not a proposition? This question is left as an exercise for the reader.

We now define atomic (or primitive) propositions. Intuitively, these are the set of smallest propositions.

Definition 1.2 An atomic proposition is one whose truth or falsity does not depend on the truth or falsity of any other proposition.

According to Definition 1.2, we find that all the propositions in items – of Example 1.1 are atomic.

Definition 1.3 A compound proposition is a proposition that involves the assembly of multiple atomic propositions.

The following connectives allow us to build up compound propositions:

Example 1.2 The following proposition is compound.

Note that

• compound proposition 1 = (atomic proposition 1) (atomic proposition 2),
• compound proposition 2 = (compound proposition 1) (atomic proposition 3).

▄

In the realm of natural language, such as English, ambiguity is a recurring challenge that writers and readers encounter. The following remark says that slight variations in context could drastically alter the intended message.

Remark 1.1 Sentences in natural languages can often be ambiguous and words can have different meanings in the context in which they are used.

To illustrate Remark 1.1, we consider the following sentences:

• The sentence “You can download WhatsApp or Skype to ring friends” could mean that you can only download one of the applications or it could mean that you can download just one or download both.
• The sentence “I smelled a chlorine-like odor and felt ill” implies that the odor of chlorine made you sick, but the sentence “I am majoring in CS and minoring in Math” does not imply that majoring in CS caused you to minor in Math.
• The sentence “I went to Chicago and took a plane” could mean that you took a plane to travel to Chicago or it could mean that you went to Chicago and then took a plane from Chicago to another destination, such as Las Vegas.

In mathematics and computer science, it is important to avoid ambiguity and for sentences to have a precise meaning. This is why people have invented artificial languages such as Java.

1.1.1 Notations

Rather than writing out propositions in full, we will abbreviate them by using propositional variables: , etc.

Example 1.3 (Example 1.2 revisited)

In Example 1.2, let be the proposition “It is raining,” be the proposition “You are outside,” and be the proposition “You get wet.” Then we can abbreviate the compound proposition

▄

In Section 1.2, we will learn more about the connectives AND, OR, NOT, IF-THEN, and IFF. This will enable us to gain a comprehensive understanding of how these connectives function within the context of formal logic and the role they play in constructing logical statements and arguments.

1.2 Logical Operators

In this section, we study the following logical operators or connectives: Negation, conjunction, disjunction, exclusive disjunction, implication, and double implication.

Before starting with the logical operators, we introduce the truth tables which help us understand how such operators work by calculating all of the possible return values of atomic propositions.

Definition 1.4 A truth table is a mathematical table used to show the truth or falsity of a compound proposition depending on the truth or falsity of the atomic propositions from which it is constructed.

Examples of truth tables will be seen very frequently throughout this chapter.

1.2.1 Negation, Conjunction, and Disjunction

This part is devoted to introducing the logical operators:...