1
Elements of logic
Logic is the systematic study of the form of valid arguments. Valid arguments are important not just in mathematics, but also in computer science, artificial intelligence or in everyday life.
In this chapter we introduce mathematical statements and logical operations between them like negation, disjunction and conjunction. We construct truth tables and determine when two statements are equivalent, in preparation for making meaningful judgments and writing correct proofs. We introduce new symbols, like the universal quantifier ∀ and the existential quantifier ∃, and learn how to negate statements involving quantifiers. Quantifiers will be used throughout the book.
1.1 True and false statements
We can use words and symbols to make meaningful sentences, also called statements. For example:
a) Mary snores.
b) A healthy warthog has four legs.
c) 2 + 3 = 5.
d) x + 5 = 7.
e)
f) ∀x ∈ ℝ ∃ y ∈ ℝ such that y2 = x.
g) x/x = 1.
h) 3 ∈ [1, 2).
i) Dr. Pfaff is the president of the United States.
Some of these statements have eccentric formats, using symbols that you may not have seen before. By the way, ∀ means for all, ∈ means belongs to (or is an element of) and ∃ means there exists. The symbol ∀ is also called the universal quantifier, and the symbol ∃ is called the existential quantifier.
The statements could be true, like statements b, c, e; could be false, like statements f, h, i; or could be neither true nor false, like statements a, d, g. The last possibility occurs because we don’t have enough information. For statement a, we could ask: which Mary are we talking about? Is she snoring now or in general? For statement d, do we know that x = 2? For statement g, do we know x to be a nonzero number? We don’t, and these kind of ambiguous statements (neither true nor false) also appear in real life.
To make things easier, let’s agree that a proposition is a statement which is either true or false. Each proposition has a truth value denoted T for true or F for false. All statements b, c, e, f, h, i are propositions, but a, d, g are not. We can modify statements d and g as
d’) ∀x : x + 5 = 7 and
g’) ∃x : x/x = 1,
which become propositions. Of course, the proposition d’ is false since, for example, 1 + 5 ≠ 7 and the proposition g’ is true because we can take x = 2 and 2/2 = 1.
1.2 Logical connectives and truth tables
It is important to understand the meaning of key words that will be used throughout mathematics. Primary words which must be clarified are the logical terms “not”, “and”, “or”, “if...then”, and “if and only if”. The word “and” is used to combine two sentences to form a new sentence which is always different from the original ones. For example, combining sentences c and h above we get
2 + 3 = 5 and 3 ∈ [1, 2),
which is false, since 3 does not belong to the interval [1, 2). The meaning of this compound sentence can be determined in a straightforward way from the meanings of its component parts. Similar remarks hold for the other basic logical terms, also called connectives. We will think of the above basic logical terms as operations on sentences. Though there are linguistic conventions which dictate the proper form of a correctly constructed sentence, we will find it convenient to write all our compound sentences in a manner reminiscent of algebra and arithmetic. Thus, irrespective of where the word “not” should appear in a sentence, in order to placate the grammarians, we will write it sometimes at the beginning. For example, though a grammar book would tell us that “not Dr. Pfaff is the president of the United States” is improper usage, and that the correct way is to write “Dr. Pfaff is not the president of the United States”, it will prove easier for us to work with the first form. We regard the two as the same for our purposes.
We will use the following symbolic notation.
Definition 1.1. The negation of a statement P is denoted by ¬P, verbalized as “it is not the case that P” or just “not P”.
The operation of negation always reverses the truth value of a sentence. We summarize this in this truth table:
Recall that T stands for true and F for false.
Definition 1.2. We write P ∧ Q for “P and Q”, the conjunction of two sentences. This is true precisely when both of the constituent parts are correct, but false otherwise.
This is in line with normal everyday usage of the word “and”. Nobody would deny that I am telling the truth if I say
(2 + 2 = 4) ∧ (3 + 3 = 6),
nor would anyone hesitate to call me a liar if I boldly announced that
(2 + 2 = 4) ∧ (3 + 3 = 5).
Her...