Chapter 1
Basic Logic
When I staggered out from sleep before dawn, I often found her studying calculus at the kitchen table, held in a cloud of Kool smoke like some radiant, unlikely Buddha.
“It’s a language,” she said of the math one morning, tapping her legal pad with the tip of a mechanical pencil. “I’ve never understood that. It’s a language that describes certain stuff very precisely.”
Mary Carr, Cherry
“I know what you’re thinking about,” said Tweedledum; “but it isn’t so, nohow.”
“Contrariwise,” continued Tweedledee, “if it was so, it might be; and if it were so, it would be; but as it isn’t, it ain’t. That’s logic.”
Lewis Carroll, Through the Looking Glass
Introduction. Logic, or logical reasoning, is a system for drawing conclusions from premises. Premises are the input of a logical argument; the conclusion is the output. Whether the conclusion of an argument is true depends on the truth or falsity of the premises, and on whether or not the conclusion truly follows from the premises.
Since we propose to reason about mathematical objects, we will make use of a formal system of logical operators, called connectives. These connectives give us ways to combine statements to obtain other statements. They also give us rules for determining the truth or falsity of the new statements, based on that of the old statements.
Propositional logic concerns true and false statements and logical connectives. The connectives are as follows: not (¬), and (∧), or (∨), implies (⟶), and if and only if (⟷). Suppose that p is a statement. If p is true, then ¬p (not p) is false. If p is false, then ¬p is true. This tells us all we need to know about the logical connective not. Similarly, the connective and (∧) may be described as follows. Let p and q be statements. If p is true and q is true, then p ∧ q (p and q) is true. If p is false and q is false, then p ∧ q is false. If p is true and q is false, then p ∧ q is false. If p is false and q is true, then p ∧ q is false.
Since logical connectives are determined by what they do to propositions, we define the connectives by means of truth tables. A truth table tells us what value a connective produces for each possible set of input values. Actually, as we will see in Chapter 4, logical connectives are functions from sets of truth values to sets of truth values. (There are two truth values in our system: true and false.) But we cannot describe functions between sets without already knowing how to use logical connectives, quantifiers, sets, and so on. Hence, we begin with propositions and connectives defined by means of truth tables. In this first chapter, we will learn the use of logical quantifiers with sets and elements of sets, and the technique of negating quantified statements. By the end of Chapter 1, we will have learned enough formal mathematical language to write and understand mathematical sentences. In the next chapter, we will introduce definitions constructed out of words, and will use the definitions and logical reasoning to write paragraphs and prove theorems. We will prove theorems about more and more interesting and complicated mathematical objects as we move through the book and become proficient in the language and lore of mathematics.
But here, at the beginning of Chapter 1, we have not yet even learned to write and interpret formal sentences. So we begin rather inarticulately, with propositions and logical connectives defined by truth tables. By the end of the chapter, we’ll be able to start using words to say what we mean in formal mathematical language. Without more ado, let’s begin.
Propositions. A proposition, or statement, is a declarative sentence which is either true or false.
Examples of propositions:
1. 3 + 7 = 10.
2. 3 + 7 = 42.
3. –3 < –4.
4. 5 ≥ 7.
Non-statements:
1. 42.
2. 15 – 27.
3.
4. x2.
Connectives. Connectives, or logical operators, or truth functions, are defined by means of truth tables. The symbols p denote propositions; T stands for “true” and F for “false.”
(a) not (¬)
(b) and (∧)
Exercises (1.1) Construct truth tables for the following propositions.
1. p ∧ ¬q
2. ¬(¬(¬p))
3. (p ∧ q) ∧ r
(c) or (∨)
This is “the inclusive or.” Thus p ∨ q means: p is true or q is true or both p and q are true.
Examples (1.1) The following statements are true.
1. 4 > 5 or 4 < 5.
2. 4 ≥ 5 or 4 ≤ 5.
3. 4 > 0 or 4 < 8.
(d) if . . . then (⟶)
p ⟶ q means each of the following:
if p then q.
p implies q.
p only if q.
q is a necessary condition for p.
p is a sufficient condition for q.
Remark. In ordinary English, the phrase “if . . . then” is used in many different ways. In mathematical English, “if . . . then” is used in only one way. Hence the convention that p ⟶ q is true whenever p is false often strikes people as peculiar.
The mathematical convention concerning “if . . . then” corresponds most closely to the use of the phrase when making a promise. Suppose that I say to you, “If it rains tomorrow, I’ll invite you to dinner.” The only way this statement can be false is that it rains tomorrow and I don’t invite you to dinner. In case it doesn’t rain tomorrow, my statement to you is true, whether I invite you to dinner or not.
Two