Logic
Logic is a systematic way of thinking that allows us to deduce new information from old information and to parse the meanings of sentences. You use logic informally in everyday life and certainly also in doing mathematics. For example, suppose you are working with a certain circle, call it “Circle X,” and you have available the following two pieces of information.- Circle X has radius equal to 3.
- If any circle has radius r, then its area is πr2 square units.
- Circle X has area 9π square units.
- Circle X has radius equal to 3.
- If any circle has radius r, then its area is πr2 square units.
- Circle X has area 9π square units.
Statements
The study of logic begins with statements. A statement is a sentence or a mathematical expression that is either definitely true or definitely false. You can think of statements as pieces of information that are either correct or incorrect. Thus statements are pieces of information that we might apply logic to in order to produce other pieces of information (which are also statements).Example 1
Here are some examples of statements. They are all true.If a circle has radius r, then its area is πr2 square units.
Every even number is divisible by 2.
[latex]2\text{ }{\in}\text{ }\mathbb{Z}[/latex] (2 is an element of the set of integers (or more simply, 2 is an integer).)
[latex]\sqrt{2}\text{ }{\notin}\text{ }\mathbb{Z}[/latex] (The square root of 2 is not an integer.)
[latex]\mathbb{N}\text{ }{\subseteq}\text{ }\mathbb{Z}[/latex] (The set of natural numbers is a subset of the set of integers.)
The set {0,1,2} has three elements.
Some right triangles are isosceles.
Example 2
Here are some additional statements. They are all false.All right triangles are isosceles.
5 = 2
[latex]\sqrt{2}\text{ }{\notin}\text{ }\mathbb{R}[/latex] (The square root of 2 is not a real number.)
[latex]\mathbb{Z}\subseteq\mathbb{N}[/latex] (The set of integers is a subset of the set of natural numbers.)
[latex]{0,1,2}\cap\mathbb{N}=\varnothing[/latex] (The intersection of the set {0,1,2} and the natural numbers is the empty set.)
Example 3
Here we pair sentences or expressions that are not statements with similar expressions that are statements.NOT Statements | Statements |
---|---|
Add 5 to both sides. | Adding 5 to both sides of x − 5 = 37 gives x = 42. |
[latex]\mathbb{Z}[/latex] (The set of integers) | [latex]42\text{ }{\in}\text{ }\mathbb{Z}[/latex] (42 is an element of the set of integers.) |
42 | 42 is not a number. |
What is the solution of 2x = 84? | The solution of 2x = 84 is 42. |
Example 4
We will often use the letters P, Q, R, and S to stand for specific statements. When more letters are needed we can use subscripts. Here are more statements, designated with letters. You decide which of them are true and which are false.P : For every integer n > 1, the number 2n − 1 is prime. Q : Every polynomial of degree n has at most n roots. R : The function f(x) = x2 is continuous. S1 : [latex]\mathbb{N}\subseteq\varnothing[/latex] S2 : [latex]{0,-1,-2}\cap\mathbb{N}=\varnothing[/latex]
P : If an integer x is a multiple of 6, then x is even.
This is a sentence that is true. (All multiples of 6 are even, so no matter which multiple of 6 the integer x happens to be, it is even.) Since the sentence P is definitely true, it is a statement. When a sentence or statement P contains a variable such as x, we sometimes denote it as P(x) to indicate that it is saying something about x. Thus the above statement can be denoted asP(x) : If an integer x is a multiple of 6, then x is even.
A statement or sentence involving two variables might be denoted P(x, y), and so on. It is quite possible for a sentence containing variables to not be a statement. Consider the following example.Q(x) : The integer x is even.
Is this a statement? Whether it is true or false depends on just which integer x is. It is true if x = 4 and false if x = 7, etc. But without any stipulations on the value of x it is impossible to say whether Q(x) is true or false. Since it is neither definitely true nor definitely false, Q(x) cannot be a statement. A sentence such as this, whose truth depends on the value of one or more variables, is called an open sentence. The variables in an open sentence (or statement) can represent any type of entity, not just numbers. Here is an open sentence where the variables are functions:R(f, g) : The function f is the derivative of the function g.
This open sentence is true if f(x) = 2x and g(x) = x2. It is false if f(x) = x3 and g(x) = x2, etc. We point out that a sentence such as R(f, g) (that involves variables) can be denoted either as R(f, g) or just R. We use the expression R(f, g) when we want to emphasize that the sentence involves variables. We will have more to say about open sentences later, but for now let’s return to statements. Statements are everywhere in mathematics. Any result or theorem that has been proved true is a statement. The quadratic formula and the Pythagorean theorem are both statements:P : The solutions of the equation [latex]\displaystyle{a}x^2+bx+c=0\text{ are }x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}[/latex]. Q : If a right triangle has legs of lengths a and b and hypotenuse of length [latex]a^2+b^2={c}^2[/latex]..
Here is a very famous statement, so famous, in fact, that it has a name. It is called Fermat’s last theorem after Pierre Fermat, a seventeenth-century French mathematician who scribbled it in the margin of a notebook.R : For all numbers a, b, c, n ∈ [latex]\mathbb{N}[/latex] with n > 2, it is the case that [latex]a^n+b^n\neq{c}^n[/latex].
Fermat believed this statement was true. He noted that he could prove it was true, except his notebook’s margin was too narrow to contain his proof. It is doubtful that he really had a correct proof in mind, for after his death generations of brilliant mathematicians tried unsuccessfully to prove that his statement was true (or false). Finally, in 1993, Andrew Wiles of Princeton University announced that he had devised a proof. Wiles had worked on the problem for over seven years, and his proof runs through hundreds of pages. The moral of this story is that some true statements are not obviously true. Here is another statement famous enough to be named. It was first posed in the eighteenth century by the German mathematician Christian Goldbach, and thus is called the Goldbach conjecture:S : Every even integer greater than 2 is a sum of two prime numbers.
You must agree that S is either true or false. It appears to be true, because when you examine even numbers that are bigger than 2, they seem to be sums of two primes: 4 = 2+2, 6 = 3+3, 8 = 3+5, 10 = 5+5, 12 = 5+7, 100 = 17+83 and so on. But that’s not to say there isn’t some large even number that’s not the sum of two primes. If such a number exists, then S is false. The thing is, in the over 260 years since Goldbach first posed this problem, no one has been able to determine whether it’s true or false. But since it is clearly either true or false, S is a statement. This book is about the methods that can be used to prove that S (or any other statement) is true or false. To prove that a statement is true, we start with obvious statements (or other statements that have been proven true) and use logic to deduce more and more complex statements until finally we obtain a statement such as S. Of course some statements are more difficult to prove than others, and S appears to be notoriously difficult; we will concentrate on statements that are easier to prove. But the point is this: In proving that statements are true, we use logic to help us understand statements and to combine pieces of information to produce new pieces of information. In the next several sections we explore some standard ways that statements can be combined to form new statements, or broken down into simpler statements.And, Or, Not
The word “and” can be used to combine two statements to form a new statement. Consider for example the following sentence.R1 : The number 2 is even and the number 3 is odd.
We recognize this as a true statement, based on our common-sense understanding of the meaning of the word “and.” Notice that R1 is made up of two simpler statements:P : The number 2 is even. Q : The number 3 is odd.
These are joined together by the word “and” to form the more complex statement R1. The statement R1 asserts that P and Q are both true. Since both P and Q are in fact true, the statement R1 is also true. Had one or both of P and Q been false, then R1 would be false. For instance, each of the following statements is false.R2 : The number 1 is even and the number 3 is odd. R3 : The number 2 is even and the number 4 is odd. R4 : The number 3 is even and the number 2 is odd.
From these examples we see that any two statements P and Q can be combined to form a new statement “P and Q.” In the spirit of using letters to denote statements, we now introduce the special symbol ∧ to stand for the word “and.” Thus if P and Q are statements, P ∧ Q stands for the statement “P and Q.” The statement P ∧ Q is true if both P and Q are true; otherwise it is false. This is summarized in the following table, called a truth table.P | Q | P ∧ Q |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | F |
S1 : The number 2 is even or the number 3 is odd. S2 : The number 1 is even or the number 3 is odd. S3 : The number 2 is even or the number 4 is odd. S4 : The number 3 is even or the number 2 is odd.
In mathematics, the assertion “P or Q” is always understood to mean that one or both of P and Q is true. Thus statements S1, S2, S3 are all true, while S4 is false. The symbol ∨ is used to stand for the word “or.” So if P and Q are statements, P ∨ Q represents the statement “P or Q.” Here is the truth table.P | Q | P ∨ Q |
---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
P or Q, but not both.
Either P or Q.
If the university official were a mathematician, he might have qualified his statement in one of the following ways.Pay your tuition or you will be withdrawn from school, but not both. Either you pay your tuition or you will be withdrawn from school.
To conclude this section, we mention another way of obtaining new statements from old ones. Given any statement P, we can form the new statement “It is not true that P.” For example, consider the following statement.The number 2 is even.
This statement is true. Now change it by inserting the words “It is not true that” at the beginning:It is not true that the number 2 is even.
This new statement is false.For another example, starting with the false statement “[latex]2\in\varnothing[/latex]” we get the true statement “It is not true that [latex]2\in\varnothing[/latex].”
We use the symbol ∼ to stand for the words “It’s not true that,” so ∼ P means “It’s not true that P.” We often read ∼ P simply as “not P.” Unlike ∧ and ∨, which combine two statements, the symbol ∼ just alters a single statement. Thus its truth table has just two lines, one for each possible truth value of P.P | ∼ P |
---|---|
T | F |
F | T |
P : The number 2 is even.
Here are several ways of expressing its negation.∼ P : It’s not true that the number 2 is even. ∼ P : It is false that the number 2 is even. ∼ P : The number 2 is not even.
In this section we’ve learned how to combine or modify statements with the operations ∧, ∨ and ∼. Of course we can also apply these operations to open sentences or a mixture of open sentences and statements. For example, (x is an even integer)∧(3 is an odd integer) is an open sentence that is a combination of an open sentence and a statement.Conditional Statements
There is yet another way to combine two statements. Suppose we have in mind a specific integer a. Consider the following statement about a.R : If the integer a is a multiple of 6, then a is divisible by 2.
We immediately spot this as a true statement based on our knowledge of integers and the meanings of the words “if” and “then.” If integer a is a multiple of 6, then a is even, so therefore a is divisible by 2. Notice that R is built up from two simpler statements:P : The integer a is a multiple of 6. Q : The integer a is divisible by 2. R : If P, then Q.
In general, given any two statements P and Q whatsoever, we can form the new statement “If P, then Q.” This is written symbolically as P ⇒ Q which we read as “If P, then Q,” or “P implies Q.” Like ∧ and ∨, the symbol ⇒ has a very specific meaning. When we assert that the statement P ⇒ Q is true, we mean that if P is true then Q must also be true. (In other words we mean that the condition P being true forces Q to be true.) A statement of form P ⇒ Q is called a conditional statement because it means Q will be true under the condition that P is true. You can think of P ⇒ Q as being a promise that whenever P is true, Q will be true also. There is only one way this promise can be broken (i.e. be false) and that is if P is true but Q is false. Thus the truth table for the promise P ⇒ Q is as follows:P | Q | P ⇒ Q |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
If you pass the final exam, then you will pass the course.
Your professor is making the promise(You pass the exam) ⇒ (You pass the course).
Under what circumstances did she lie? There are four possible scenarios, depending on whether or not you passed the exam and whether or not you passed the course. These scenarios are tallied in the following table.You pass exam | You pass course | (You pass exam) ⇒ (You pass course) |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
(You pass the exam) ⇒ (You pass the course)
This means that your passing the exam is a sufficient (though perhaps not necessary) condition for your passing the course. Thus your professor might just as well have phrased her promise in one of the following ways.Passing the exam is a sufficient condition for passing the course. For you to pass the course, it is sufficient that you pass the exam.
However, when we want to say “If P, then Q” in everyday conversation, we do not normally express this as “Q is a necessary condition for P” or “P only if Q.” But such constructions are not uncommon in mathematics. To understand why they make sense, notice that P ⇒ Q being true means that it’s impossible that P is true but Q is false, so in order for P to be true it is necessary that Q is true; hence “Q is a necessary condition for P.” And this means that P can only be true if Q is true, i.e., “P only if Q.”Biconditional Statements
It is important to understand that P ⇒ Q is not the same as Q ⇒ P. To see why, suppose that a is some integer and consider the statements(a is a multiple of 6) ⇒ (a is divisible by 2), (a is divisible by 2) ⇒ (a is a multiple of 6).
The first statement asserts that if a is a multiple of 6 then a is divisible by 2. This is clearly true, for any multiple of 6 is even and therefore divisible by 2. The second statement asserts that if a is divisible by 2 then it is a multiple of 6. This is not necessarily true, for a = 4 (for instance) is divisible by 2, yet not a multiple of 6. Therefore the meanings of P ⇒ Q and Q ⇒ P are in general quite different. The conditional statement Q ⇒ P is called the converse of P ⇒ Q, so a conditional statement and its converse express entirely different things.(a is even) ⇒ (a is divisible by 2), (a is divisible by 2) ⇒ (a is even).
No matter what value a has, both of these statements are true. Since both P ⇒ Q and Q ⇒ P are true, it follows that (P ⇒ Q)∧(Q ⇒ P) is true. We now introduce a new symbol ⇔ to express the meaning of the statement (P ⇒ Q)∧(Q ⇒ P). The expression P ⇔ Q is understood to have exactly the same meaning as (P ⇒ Q)∧(Q ⇒ P). According to the previous section, Q ⇒ P is read as “P if Q,” and P ⇒ Q can be read as “P only if Q.” Therefore we pronounce P ⇔ Q as “P if and only if Q.” For example, given an integer a, we have the true statement(a is even) ⇔ (a is divisible by 2),
which we can read as “Integer a is even if and only if a is divisible by 2.” The truth table for ⇔ is shown below. Notice that in the first and last rows, both P ⇒ Q and Q ⇒ P are true (according to the truth table for ⇒), so (P ⇒ Q) ∧ (Q ⇒ P) is true, and hence P ⇔ Q is true. However, in the middle two rows one of P ⇒ Q or Q ⇒ P is false, so (P ⇒ Q)∧(Q ⇒ P) is false, making P ⇔ Q false.P | Q | P ⇔ Q |
---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | T |
Truth Tables for Statements
You should now know the truth tables for ∧, ∨, ∼, ⇒ and ⇔. They should be internalized as well as memorized. You must understand the symbols thoroughly, for we now combine them to form more complex statements. For example, suppose we want to convey that one or the other of P and Q is true but they are not both true. No single symbol expresses this, but we could combine them as(P ∨ Q)∧ ∼ (P ∧ Q),
which literally means:P or Q is true, and it is not the case that both P and Q are true.
This statement will be true or false depending on the truth values of P and Q. In fact we can make a truth table for the entire statement. Begin as usual by listing the possible true/false combinations of P and Q on four lines. The statement (P ∨ Q)∧ ∼ (P ∧ Q) contains the individual statements (P ∨ Q) and (P ∧ Q), so we next tally their truth values in the third and fourth columns. The fifth column lists values for ∼ (P ∧ Q), and these are just the opposites of the corresponding entries in the fourth column. Finally, combining the third and fifth columns with ∧, we get the values for (P ∨ Q)∧ ∼(P ∧ Q) in the sixth column.P | Q | (P ∨ Q) | (P ∧ Q) | ∼(P ∧ Q) | (P ∨ Q)∧ ∼(P ∧ Q) |
---|---|---|---|---|---|
T | T | T | T | F | F |
T | F | T | F | T | T |
F | T | T | F | T | T |
F | F | F | F | T | F |
The product xy equals zero if and only if x = 0 or y = 0.
This can be modeled as (xy = 0) ⇔ (x = 0 ∨ y = 0). If we introduce letters P, Q, and R for the statements xy = 0, x = 0 and y = 0, it becomes P ⇔ (Q ∨ R). Notice that the parentheses are necessary here, for without them we wouldn’t know whether to read the statement as P ⇔ (Q ∨ R) or (P ⇔ Q) ∨ R. Making a truth table for P ⇔ (Q ∨ R) entails a line for each T/F combination for the three statements P, Q, and R. The eight possible combinations are tallied in the first three columns of the following table.P | Q | R | Q ∨ R | P ⇔ (Q ∨ R) |
---|---|---|---|---|
T | T | T | T | T |
T | T | F | T | T |
T | F | T | T | T |
T | F | F | F | F |
F | T | T | T | F |
F | T | F | T | F |
F | F | T | T | F |
F | F | F | F | T |
You pass the class if and only if you get an “A” on the final or you get a “B” on the final.
This promise has the form P ⇔ (Q ∨ R), so its truth values are tabulated in the above table. Imagine it turned out that you got an “A” on the exam but failed the course. Then surely your professor lied to you. In fact, P is false, Q is true and R is false. This scenario is reflected in the sixth line of the table, and indeed P ⇔ (Q ∨ R) is false (i.e., it is a lie). The moral of this example is that people can lie, but true mathematical statements never lie. We close this section with a word about the use of parentheses. The symbol ∼ is analogous to the minus sign in algebra. It negates the expression it precedes. Thus ∼P ∨ Q means (∼P) ∨ Q, not ∼(P ∨ Q). In ∼(P ∨ Q), the value of the entire expression P ∨ Q is negated.Logical Equivalence
In contemplating the truth table for P ⇔ Q, you probably noticed that P ⇔ Q is true exactly when P and Q are both true or both false. In other words, P ⇔ Q is true precisely when at least one of the statements P ∧ Q or ∼P ∧ ∼Q is true. This may tempt us to say that P ⇔ Q means the same thing as (P ∧ Q)∨(∼P ∧ ∼Q). To see if this is really so, we can write truth tables for P ⇔ Q and (P ∧ Q) ∨ (∼P ∧ ∼Q). In doing this, it is more efficient to put these two statements into the same table, as follows. (This table has helper columns for the intermediate expressions ∼P, ∼Q, (P ∧ Q), and (~P ∧ ∼Q).)P | Q | ∼P | ∼Q | (P ∧ Q) | (∼P ∧ ∼Q) | (P ∧ Q)∨(∼P ∧ ∼Q) | P ⇔ Q |
---|---|---|---|---|---|---|---|
T | T | F | F | T | F | T | T |
T | F | F | T | F | F | F | F |
F | T | T | F | F | F | F | F |
F | F | T | T | F | T | T | T |
P ⇔ Q = (P ∧ Q)∨(∼P ∧ ∼Q)
and saying that P ⇔ Q and (P ∧ Q)∨(∼P ∧ ∼Q) are logically equivalent. In general, two statements are logically equivalent if their truth values match up line-for-line in a truth table. Logical equivalence is important because it can give us different (and potentially useful) ways of looking at the same thing. As an example, the following table shows that P ⇒ Q is logically equivalent to (∼Q) ⇒ (∼P).P | Q | ∼P | ∼Q | (∼Q) ⇒ (∼P) | P ⇒ Q |
---|---|---|---|---|---|
T | T | F | F | T | T |
T | F | F | T | F | F |
F | T | T | F | T | T |
F | F | T | T | T | T |
Fact: DeMorgan’s Laws
- ∼(P ∧ Q) = (∼P)∨(∼Q)
- ∼(P ∨ Q) = (∼P)∧(∼Q)
P | Q | ~P | ~Q | P ∧ Q | ∼(P ∧ Q) | (∼P)∨(∼Q) |
---|---|---|---|---|---|---|
T | T | F | F | T | F | F |
T | F | F | T | F | T | T |
F | T | T | F | F | T | T |
F | F | T | T | F | T | T |
Negating Statements
Given a statement R, the statement ∼R is called the negation of R. If R is a complex statement, then it is often the case that its negation ∼R can be written in a simpler or more useful form. The process of finding this form is called negating R. In proving theorems it is often necessary to negate certain statements. We now investigate how to do this. We have already examined part of this topic. DeMorgan’s laws∼ (P ∧Q) = (∼ P)∨(∼ Q) ∼ (P ∨Q) = (∼ P)∧(∼ Q)
(from "Logical Equivalence") can be viewed as rules that tell us how to negate the statements P ∧Q and P ∨Q. Here are some examples that illustrate how DeMorgan’s laws are used to negate statements involving “and” or “or.”Example 5
Consider negating the following statement.R : You can solve it by factoring or with the quadratic formula.
Now, R means (You can solve it by factoring) ∨ (You can solve it with Q.F.), which we will denote as P ∨ Q. The negation of this is∼(P ∨ Q) = (∼P)∧(∼Q).
Therefore, in words, the negation of R is∼R : You can’t solve it by factoring and you can’t solve it with the quadratic formula.
Maybe you can find ∼R without invoking DeMorgan’s laws. That is good; you have internalized DeMorgan’s laws and are using them unconsciously.Example 6
We will negate the following sentence.R : The numbers x and y are both odd.
This statement means (x is odd) ∧ (y is odd), so its negation is~[(x is odd) ∧ (y is odd)] = ∼(x is odd) ∨ ∼(y is odd) (x is odd) ∧ (y is odd) = (x is even) ∨ (y is even).
Therefore the negation of R can be expressed in the following ways:∼ R : The number x is even or the number y is even. ∼ R : At least one of x and y is even.
It is not the case that P(x) is true for all natural numbers x.
This means P(x) is false for at least one x. In symbols, this is ∃ x ∈ [latex]\mathbb{N}[/latex], ∼P(x). Thus ∼ (∀x ∈ [latex]\mathbb{N}[/latex], P(x)) = ∃ x ∈ [latex]\mathbb{N}[/latex], ∼P(x). Similarly, you can reason out that ∼ (∃ x ∈ [latex]\mathbb{N}[/latex], P(x)) = ∀x ∈ [latex]\mathbb{N}[/latex], ∼P(x). In general:∼ (∀x ∈ S, P(x)) = ∃ x ∈ S, ∼P(x) ∼ (∃ x ∈ S, P(x)) = ∀x ∈ S, ∼P(x)
Logical Inference
Suppose we know that a statement of form P ⇒ Q is true. This tells us that whenever P is true, Q will also be true. By itself, P ⇒ Q being true does not tell us that either P or Q is true (they could both be false, or P could be false and Q true). However if in addition we happen to know that P is true then it must be that Q is true. This is called a logical inference: Given two true statements we can infer that a third statement is true. In this instance true statements P ⇒ Q and P are “added together” to get Q. This is described below with P ⇒ Q and P stacked one atop the other with a line separating them from Q. The intended meaning is that P ⇒ Q combined with P produces Q. Two other logical inferences are listed above. In each case you should convince yourself (based on your knowledge of the relevant truth tables) that the truth of the statements above the line forces the statement below the line to be true. Following are some additional useful logical inferences. The first expresses the obvious fact that if P and Q are both true then the statement P ∧ Q will be true. On the other hand, P ∧ Q being true forces P (also Q) to be true. Finally, if P is true, then P ∨ Q must be true, no matter what statement Q is. These inferences are so intuitively obvious that they scarcely need to be mentioned. However, they represent certain patterns of reasoning that we will frequently apply to sentences in proofs, so we should be cognizant of the fact that we are using them.An Important Note
It is important to be aware of the reasons that we study logic. There are three very significant reasons. First, the truth tables we studied tell us the exact meanings of the words such as “and,” “or,” “not,” and so on. For instance, whenever we use or read the “If..., then” construction in a mathematical context, logic tells us exactly what is meant. Second, the rules of inference provide a system in which we can produce new information (statements) from known information. Finally, logical rules such as DeMorgan’s laws help us correctly change certain statements into (potentially more useful) statements with the same meaning. Thus logic helps us understand the meanings of statements and it also produces new meaningful statements. Logic is the glue that holds strings of statements together and pins down the exact meaning of certain key phrases such as the “If..., then” or “For all” constructions. Logic is the common language that all mathematicians use, so we must have a firm grip on it in order to write and understand mathematics. But despite its fundamental role, logic’s place is in the background of what we do, not the forefront. From here on, the beautiful symbols ∧, ∨, ⇒, ⇔, ∼, ∀ and ∃ are rarely written. But we are aware of their meanings constantly. When reading or writing a sentence involving mathematics we parse it with these symbols, either mentally or on scratch paper, so as to understand the true and unambiguous meaning.Licenses & Attributions
CC licensed content, Shared previously
- Logic. Authored by: Richard Hammack. Located at: http://www.people.vcu.edu/~rhammack/BookOfProof/. License: CC BY-ND: Attribution-NoDerivatives.