2.2: Introduction to Logic

In the previous section, we jumped in head first and attempted to prove several theorems in the context of number theory without a formal understanding of what it was we were doing. Likely, many issues bubbled to the surface. What is a proof? What sorts of statements require proof? What should a proof entail? How should a proof be structured? Let’s take a step back and do a more careful examination of what it is we are actually doing. In the the next two sections, we will introduce the basics of propositional logic—also referred to as propositional calculus or sometimes zeroth-order logic.

Definition 2.16. A proposition is a sentence that is either true or false but never both. The truth value (or logical value) of a proposition refers to its attribute of being true or false.

For example, the sentence “All dogs have four legs” is a false proposition. However, the perfectly good sentence “x = 1” is not a proposition all by itself since we do not actually know what x is.

Problem 2.17. Determine whether each of the following is a proposition. Explain your reasoning.

(a) All cars are red.

(b) Every person whose name begins with J has the name Joe.

(c) x² = 4.

(d) There exists a real number x such that x² = 4.

(e) For all real numbers x, x² = 4.

(f) √2 is an irrational number.

(g) p is prime.

(h) Is it raining?

(i) It will rain tomorrow

(j) Led Zeppelin is the best band of all time.

The last two sentences in the previous problem may stir debate. It is not so important that we come to consensus as to whether either of these two sentences is actually a proposition or not. The good news is that in mathematics we do not encounter statements whose truth value is dependent on either the future or opinion.

Given two propositions, we can form more complicated propositions using logical connectives.

Definition 2.18. Let A and B be propositions.

(a) The proposition “not A” is true if A is false; expressed symbolically as \(¬A\) and called the negation of A.

(b) The proposition “A and B” is true if both A and B are true; expressed symbolically as \(A∧B\) and called the conjunction of A and B.

(c) The proposition “A or B” is true if at least one of A or B is true; expressed symbolically as \(A∨B\) and called the disjunction of A and B.

(d) The proposition “If A, then B” is true if both A and B are true, or A is false; expressed symbolically as \(A =⇒ B\) and called a conditional proposition (or implication). In this case, A is called the hypothesis and B is called the conclusion. Note that A = whenever A”. ⇒ B may also be read as “A implies B”, “A only if B”, “B if A”, or “B

(e) The proposition “A if and only if B” (alternatively, “A is necessary and sufficient for B”) is true if both A and B have the same truth value; expressed symbolically as \(A ⇐⇒ B\) and called a biconditional proposition. If A ⇐⇒ B is true, we say that A and B are logically equivalent.

Each of the boxed propositions is called a compound proposition, where A and B are referred to as the components of the compound proposition.

It is worth pointing out that definitions in mathematics are typically written in the form “B if A” (or “B provided that A” or “B whenever A”), where B contains the term or phrase we are defining and A provides the meaning of the concept we are defining. In the case of definitions, we should always interpret “B if A” as describing precisely the collection of “objects” (e.g., numbers, sets, functions, etc.) that should be identified with the term or phrase we defining. That is, if an object does not meet the condition specified in A, then it is never referred to by the term or phrase we are defining. Some authors will write definitions in the form “B if and only if A”. However, a definition is not at all the same kind of statement as a usual biconditional since one of the two sides is undefined until the definition is made. A definition is really a statement that the newly defined term or phrase is synonymous with a previously defined concept.

We can form complicated compound propositions with several components by utilizing logical connectives.

Problem 2.19. Let A represent “6 is an even integer” and B represent “4 divides 6.” Express each of the following compound propositions in an ordinary English sentence and then determine its truth value.

(a) A ∧B

(b) A ∨B

(c) ¬A

(d) ¬B

(e) ¬(A∧B)

(f) ¬(A∨B)

(g) A =⇒ B

Definition 2.20. A truth table for a compound proposition is a table that illustrates all possible combinations of truth values for the components of the compound proposition together with the resulting truth value for each combination.

Example 2.21. If A and B are propositions, then the truth table for the compound proposition A ∧B is given by the following.

A	B	A∧B
T	T	T
T	F	F
F	T	F
F	F	F

Notice that we have columns for each of A and B. The rows for these two columns correspond to all possible combinations of truth values for A and B. The third column yields the truth value of A ∧B given the possible truth values for A and B.

Each component of a compound proposition has two possible truth values, namely true or false. Thus, if a compound proposition is built from n component propositions, then the truth table will require 2n rows.

Problem 2.22. Create a truth table for each of the following compound propositions. You should add additional columns to your tables as needed to assist you with intermediate steps. For example, you might need four columns for the third and fourth compound propositions below.

(a) ¬A

(b) A∨B

(c) ¬(A∧B)

(d) ¬A∧¬B

Problem 2.23. A coach promises her players, “If we win tonight, then I will buy you pizza tomorrow.” Determine the cases in which the players can rightly claim to have been lied to. If the team lost the game and the coach decided to buy them pizza anyway, was she lying?

Problem 2.24. Use Definition 2.18(d) to construct a truth table for A =⇒ B. Compare your truth table with Problem 2.23. The combination you should pay particular attention to is when the hypothesis is false while the conclusion is true.

In accordance with Definition 2.18(d), a conditional proposition A =⇒ B is only false when the hypothesis is true and the conclusion is false. Perhaps you are bothered by the fact that A =⇒ B is true when A is false no matter what the truth value of B is. The thing to keep in mind is that the truth value of A =⇒ B relies on a very specific definition and may not always agree with the colloquial use of “If. . . , then. . . ” statements that we encounter in everyday language. For example, if someone says, “If you break the rules, then you will be punished”, the speaker likely intends the statement to be interpreted as “You will be punished if and only if you break the rules.” In logic and mathematics, we aim to remove such ambiguity by explicitly saying exactly what we mean. For our purposes, we should view a conditional proposition as a contract or obligation. If the hypothesis is false and the conclusion is true, the contract is not violated. On the other hand, if the hypothesis is true and the conclusion is false, then the contract is broken.

We can often prove facts concerning logical statements using truth tables. Recall that two propositions P and Q (both of which might be complicated compound propositions) are logically equivalent if P ⇐⇒ Q is true (see Definition 2.18(e)). This happens when P and Q have the same truth value. We can verify whether P and Q have the same truth value by constructing a truth table that includes columns for each of the components of P and Q, listing all possible combinations of their truth values, together with columns for P and Q that lists their resulting truth values. If the truth values in the columns for P and Q agree, then P and Q are logically equivalent, and otherwise they are not logically equivalent. When constructing truth tables to verify whether P and Q are logically equivalent, you should add any necessary intermediate columns to aid in your “calculations”. Use truth tables when attempting to justify the next few problems.

Theorem 2.25. If A is a proposition, then ¬(¬A) is logically equivalent to A.

The next theorem, referred to as De Morgan’s Law, provides a method for negating a compound proposition involving a conjunction.

Theorem 2.26 (De Morgan’s Law). If A and B are propositions, then ¬(A ∧ B) is logically equivalent to ¬A ∨ ¬B.

Problem 2.27 (De Morgan’s Law). Let A and B be propositions. Conjecture a statement similar to Theorem 2.26 for the proposition ¬(A∨B) and then prove it. This is also called De Morgan’s Law.

We will make use of both versions De Morgan’s Law on on a regular basis. Sometimes conjunctions and disjunctions are “buried” in a mathematical statement, which makes negating statements tricky business. Keep this in mind when approaching the next problem.

Problem 2.28. Let x be your favorite real number. Negate each of the following statements. Note that the statement in Part (b) involves a conjunction.

(a) x < −1 or x ≥ 3.

(b) 0 ≤ x < 1.

Theorem 2.29. If A and B are propositions, then A ⇐⇒ B is logically equivalent to (A =⇒ B)∧(B =⇒ A).

Theorem 2.30. If A, B, and C are propositions, then (A ∨ B) =⇒ C is logically equivalent to (A =⇒ C)∧(B =⇒ C).

We already introduced the following notion in the discussion following Theorem 2.11

Definition 2.31. If A and B are propositions, then the converse of A =⇒ B is B =⇒ A.

Problem 2.32. Provide an example of a true conditional proposition whose converse is false.

Definition 2.33. If A and B are propositions, then the inverse of A =⇒ B is ¬A =⇒ ¬B.

Problem 2.34. Provide an example of a true conditional proposition whose inverse is false.

Based on Problems 2.32 and 2.34, we can conclude that the converse and inverse of a conditional proposition do not necessarily have the same truth value as the original statement. Moreover, the converse and inverse of a conditional proposition do not necessarily have the same truth value as each other.

Problem 2.35. If possible, provide an example of a conditional proposition whose converse is true but whose inverse is false. If this is not possible, explain why.

What if we swap the roles of the hypothesis and conclusion of a conditional proposition and negate each?

Definition 2.36. If A and B are propositions, then the contrapositive of A =⇒ B is ¬B =⇒ ¬A.

Problem 2.37. Let A and B represent the statements from Problem 2.19. Express each of the following in an ordinary English sentence.

(a) The converse of A =⇒ B.

(b) The contrapositive of A =⇒ B.

Problem 2.38. Find the converse and the contrapositive of the following statement: “If Dana lives in Flagstaff, then Dana lives in Arizona.”

Use a truth table to prove the following theorem.

Theorem 2.39. If A and B are propositions, then A =⇒ B is logically equivalent to its contrapositive.

So far we have discussed how to negate propositions of the form A, A ∧ B, and A ∨ B for propositions A and B. However, we have yet to discuss how to negate propositions of the form A =⇒ B. Prove the following result with a truth table.

Theorem 2.40. If A and B are propositions, then the implication A =⇒ B is logically equivalent to the disjunction ¬A ∨B.

The next result follows quickly from Theorem 2.40 together with De Morgan’s Law. You can also verify this result using a truth table.

Corollary 2.41. If A and B are propositions, then ¬(A =⇒ B) is logically equivalent to A ∧ ¬B.

Problem 2.42. Let A and B be the propositions “√ 2 is an irrational number” and “Every rectangle is a trapezoid,” respectively.

(a) Express A =⇒ B as an English sentence involving the disjunction “or.”

(b) Express ¬(A =⇒ B) as an English sentence involving the conjunction “and.”

Problem 2.43. It turns out that the proposition “If .99··· = \(dfrac{9}{10} + dfrac{9}{100} + dfrac{9}{1000} +···\), then .99 ≠ 1” is false. Write its negation as a conjunction.

Recall that a proposition is exclusively either true or false—it can never be both.

Definition 2.44. A compound proposition that is always false is called a contradiction. A compound proposition that is always true is called a tautology.

Theorem 2.45. If A is a proposition, then the proposition ¬A ∧ A is a contradiction.

Problem 2.46. Provide an example of a tautology using arbitrary propositions and any of the logical connectives ¬, ∧, and ∨. Prove that your example is in fact a tautology.