The Foundations: Logic and Proofs Chapter 1 PDF

C H A P T E R The Foundations: 1 Logic and Proofs 1.1 Propositional Logic 1.2 Applications of T he rules of logic specify the meaning of mathematical statements. For instance, these rules help us...

C H A P T E R The Foundations: 1 Logic and Proofs 1.1 Propositional Logic 1.2 Applications of T he rules of logic specify the meaning of mathematical statements. For instance, these rules help us understand and reason with statements such as “There exists an integer that is not the sum of two squares” and “For every positive integer n, the sum of the posi- Propositional tive integers not exceeding n is n(n + 1)∕2.” Logic is the basis of all mathematical reasoning, Logic and of all automated reasoning. It has practical applications to the design of computing ma- chines, to the specification of systems, to artificial intelligence, to computer programming, to 1.3 Propositional programming languages, and to other areas of computer science, as well as to many other fields Equivalences of study. 1.4 Predicates and To understand mathematics, we must understand what makes up a correct mathematical Quantifiers argument, that is, a proof. Once we prove a mathematical statement is true, we call it a theorem. A collection of theorems on a topic organize what we know about this topic. To learn a math- 1.5 Nested ematical topic, a person needs to actively construct mathematical arguments on this topic, and Quantifiers not just read exposition. Moreover, knowing the proof of a theorem often makes it possible to 1.6 Rules of modify the result to fit new situations. Inference Everyone knows that proofs are important throughout mathematics, but many people find it surprising how important proofs are in computer science. In fact, proofs are used to verify 1.7 Introduction to that computer programs produce the correct output for all possible input values, to show that Proofs algorithms always produce the correct result, to establish the security of a system, and to create 1.8 Proof Methods artificial intelligence. Furthermore, automated reasoning systems have been created to allow and Strategy computers to construct their own proofs. In this chapter, we will explain what makes up a correct mathematical argument and intro- duce tools to construct these arguments. We will develop an arsenal of different proof methods that will enable us to prove many different types of results. After introducing many different methods of proof, we will introduce several strategies for constructing proofs. We will intro- duce the notion of a conjecture and explain the process of developing mathematics by studying conjectures. 1.1 Propositional Logic 1.1.1 Introduction The rules of logic give precise meaning to mathematical statements. These rules are used to dis- tinguish between valid and invalid mathematical arguments. Because a major goal of this book is to teach the reader how to understand and how to construct correct mathematical arguments, we begin our study of discrete mathematics with an introduction to logic. Besides the importance of logic in understanding mathematical reasoning, logic has numer- ous applications to computer science. These rules are used in the design of computer circuits, the construction of computer programs, the verification of the correctness of programs, and in many other ways. Furthermore, software systems have been developed for constructing some, but not all, types of proofs automatically. We will discuss these applications of logic in this and later chapters. 1 2 1 / The Foundations: Logic and Proofs 1.1.2 Propositions Our discussion begins with an introduction to the basic building blocks of logic—propositions. A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. EXAMPLE 1 All the following declarative sentences are propositions. Extra 1. Washington, D.C., is the capital of the United States of America. Examples 2. Toronto is the capital of Canada. 3. 1 + 1 = 2. 4. 2 + 2 = 3. Propositions 1 and 3 are true, whereas 2 and 4 are false. ◂ Some sentences that are not propositions are given in Example 2. EXAMPLE 2 Consider the following sentences. 1. What time is it? 2. Read this carefully. 3. x + 1 = 2. 4. x + y = z. Sentences 1 and 2 are not propositions because they are not declarative sentences. Sentences 3 and 4 are not propositions because they are neither true nor false. Note that each of sentences 3 and 4 can be turned into a proposition if we assign values to the variables. We will also discuss other ways to turn sentences such as these into propositions in Section 1.4. ◂ We use letters to denote propositional variables (or sentential variables), that is, variables that represent propositions, just as letters are used to denote numerical variables. The conven- tional letters used for propositional variables are p, q, r, s, …. The truth value of a proposition Links ARISTOTLE (384 B.C.E.–322 B.C.E.) Aristotle was born in Stagirus (Stagira) in northern Greece. His father was the personal physician of the King of Macedonia. Because his father died when Aristotle was young, Aristotle could not follow the custom of following his father’s profession. Aristotle became an orphan at a young age when his mother also died. His guardian who raised him taught him poetry, rhetoric, and Greek. At the age of 17, his guardian sent him to Athens to further his education. Aristotle joined Plato’s Academy, where for 20 years he attended Plato’s lectures, later presenting his own lectures on rhetoric. When Plato died in 347 B.C.E., Aristotle was not chosen to succeed him because his views differed too much from those of Plato. Instead, Aristotle joined the court of King Hermeas where he remained for three years, and married the niece Source: National Library of of the King. When the Persians defeated Hermeas, Aristotle moved to Mytilene and, at the invitation of King Medicine Philip of Macedonia, he tutored Alexander, Philip’s son, who later became Alexander the Great. Aristotle tutored Alexander for five years and after the death of King Philip, he returned to Athens and set up his own school, called the Lyceum. Aristotle’s followers were called the peripatetics, which means “to walk about,” because Aristotle often walked around as he discussed philosophical questions. Aristotle taught at the Lyceum for 13 years where he lectured to his advanced students in the morning and gave popular lectures to a broad audience in the evening. When Alexander the Great died in 323 B.C.E., a backlash against anything related to Alexander led to trumped-up charges of impiety against Aristotle. Aristotle fled to Chalcis to avoid prosecution. He only lived one year in Chalcis, dying of a stomach ailment in 322 B.C.E. Aristotle wrote three types of works: those written for a popular audience, compilations of scientific facts, and systematic treatises. The systematic treatises included works on logic, philosophy, psychology, physics, and natural history. Aristotle’s writings were preserved by a student and were hidden in a vault where a wealthy book collector discovered them about 200 years later. They were taken to Rome, where they were studied by scholars and issued in new editions, preserving them for posterity.  1.1 Propositional Logic 3 is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, de- noted by F, if it is a false proposition. Propositions that cannot be expressed in terms of simpler propositions are called atomic propositions. The area of logic that deals with propositions is called the propositional calculus or propo- sitional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago. Links We now turn our attention to methods for producing new propositions from those that we already have. These methods were discussed by the English mathematician George Boole in 1854 in his book The Laws of Thought. Many mathematical statements are constructed by com- bining one or more propositions. New propositions, called compound propositions, are formed from existing propositions using logical operators. Definition 1 Let p be a proposition. The negation of p, denoted by ¬p (also denoted by p), is the statement “It is not the case that p.” The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p, is the opposite of the truth value of p. Remark: The notation for the negation operator is not standardized. Although ¬p and p are the most common notations used in mathematics to express the negation of p, other notations you might see are ∼p, −p, p′ , Np, and !p. EXAMPLE 3 Find the negation of the proposition “Michael’s PC runs Linux” Extra Examples and express this in simple English. Solution: The negation is “It is not the case that Michael’s PC runs Linux.” This negation can be more simply expressed as “Michael’s PC does not run Linux.” ◂ EXAMPLE 4 Find the negation of the proposition “Vandana’s smartphone has at least 32 GB of memory” and express this in simple English. Solution: The negation is “It is not the case that Vandana’s smartphone has at least 32 GB of memory.” This negation can also be expressed as “Vandana’s smartphone does not have at least 32 GB of memory” or even more simply as “Vandana’s smartphone has less than 32 GB of memory.” ◂ 4 1 / The Foundations: Logic and Proofs Table 1 displays the truth table for the negation of a proposition p. This table has a row for TABLE 1 The Truth Table for each of the two possible truth values of p. Each row shows the truth value of ¬p corresponding the Negation of a to the truth value of p for this row. Proposition. The negation of a proposition can also be considered the result of the operation of the negation operator on a proposition. The negation operator constructs a new proposition from p ¬p a single existing proposition. We will now introduce the logical operators that are used to form T F new propositions from two or more existing propositions. These logical operators are also called F T connectives. Definition 2 Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise. Table 2 displays the truth table of p ∧ q. This table has a row for each of the four possible combinations of truth values of p and q. The four rows correspond to the pairs of truth values TT, TF, FT, and FF, where the first truth value in the pair is the truth value of p and the second truth value is the truth value of q. Note that in logic the word “but” sometimes is used instead of “and” in a conjunction. For example, the statement “The sun is shining, but it is raining” is another way of saying “The sun is shining and it is raining.” (In natural language, there is a subtle difference in meaning between “and” and “but”; we will not be concerned with this nuance here.) EXAMPLE 5 Find the conjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.” Solution: The conjunction of these propositions, p ∧ q, is the proposition “Rebecca’s PC has more than 16 GB free hard disk space, and the processor in Rebecca’s PC runs faster than 1 GHz.” This conjunction can be expressed more simply as “Rebecca’s PC has more than 16 GB free hard disk space, and its processor runs faster than 1 GHz.” For this conjunction to be true, both conditions given must be true. It is false when one or both of these conditions are false. ◂ Definition 3 Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise. Table 3 displays the truth table for p ∨ q. TABLE 2 The Truth Table for TABLE 3 The Truth Table for the Conjunction of Two the Disjunction of Two Propositions. Propositions. p q p∧q p q p∨q T T T T T T T F F T F T F T F F T T F F F F F F  1.1 Propositional Logic 5 The use of the connective or in a disjunction corresponds to one of the two ways the word or is used in English, namely, as an inclusive or. A disjunction is true when at least one of the two propositions is true. That is, p ∨ q is true when both p and q are true or when exactly one of p and q is true. EXAMPLE 6 Translate the statement “Students who have taken calculus or introductory computer science can take this class” in a statement in propositional logic using the propositions p: “A student who has taken calculus can take this class” and q: “A student who has taken introductory computer science can take this class.” Solution: We assume that this statement means that students who have taken both calculus and introductory computer science can take the class, as well as the students who have taken only one of the two subjects. Hence, this statement can be expressed as p ∨ q, the inclusive or, or disjunction, of p and q. ◂ EXAMPLE 7 What is the disjunction of the propositions p and q, where p and q are the same propositions as Extra in Example 5? Examples Solution: The disjunction of p and q, p ∨ q, is the proposition “Rebecca’s PC has at least 16 GB free hard disk space, or the processor in Rebecca’s PC runs faster than 1 GHz.” This proposition is true when Rebecca’s PC has at least 16 GB free hard disk space, when the PC’s processor runs faster than 1 GHz, and when both conditions are true. It is false when both of these conditions are false, that is, when Rebecca’s PC has less than 16 GB free hard disk space and the processor in her PC runs at 1 GHz or slower. ◂ Besides its use in disjunctions, the connective or is also used to express an exclusive or. Unlike the disjunction of two propositions p and q, the exclusive or of these two propositions is true when exactly one of p and q is true; it is false when both p and q are true (and when both are false). Definition 4 Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q (or p XOR q), is the proposition that is true when exactly one of p and q is true and is false otherwise. Links GEORGE BOOLE (1815–1864) George Boole, the son of a cobbler, was born in Lincoln, England, in November 1815. Because of his family’s difficult financial situation, Boole struggled to educate himself while supporting his family. Nevertheless, he became one of the most important mathematicians of the 1800s. Al- though he considered a career as a clergyman, he decided instead to go into teaching, and soon afterward opened a school of his own. In his preparation for teaching mathematics, Boole—unsatisfied with textbooks of his day—decided to read the works of the great mathematicians. While reading papers of the great French mathematician Lagrange, Boole made discoveries in the calculus of variations, the branch of analysis dealing with finding curves and surfaces by optimizing certain parameters. Source: Library of Congress In 1848 Boole published The Mathematical Analysis of Logic, the first of his contributions to Washington, D.C. 20540 symbolic logic. In 1849 he was appointed professor of mathematics at Queen’s College in Cork, USA [LC-USZ62-61664] Ireland. In 1854 he published The Laws of Thought, his most famous work. In this book, Boole introduced what is now called Boolean algebra in his honor. Boole wrote textbooks on differential equations and on difference equations that were used in Great Britain until the end of the nineteenth century. Boole married in 1855; his wife was the niece of the professor of Greek at Queen’s College. In 1864 Boole died from pneumonia, which he contracted as a result of keeping a lecture engagement even though he was soaking wet from a rainstorm. 6 1 / The Foundations: Logic and Proofs The truth table for the exclusive or of two propositions is displayed in Table 4. EXAMPLE 8 Let p and q be the propositions that state “A student can have a salad with dinner” and “A student can have soup with dinner,” respectively. What is p ⊕ q, the exclusive or of p and q? Solution: The exclusive or of p and q is the statement that is true when exactly one of p and q is true. That is, p ⊕ q is the statement “A student can have soup or salad, but not both, with dinner.” Note that this is often stated as “A student can have soup or a salad with dinner,” without explicitly stating that taking both is not permitted. ◂ EXAMPLE 9 Express the statement “I will use all my savings to travel to Europe or to buy an electric car” in propositional logic using the statement p: “I will use all my savings to travel to Europe” and the statement q: “I will use all my savings to buy an electric car.” Solution: To translate this statement, we first note that the or in this statement must be an ex- clusive or because this student can either use all his or her savings to travel to Europe or use all these savings to buy an electric car, but cannot both go to Europe and buy an electric car. (This is clear because either option requires all his savings.) Hence, this statement can be expressed as p ⊕ q. ◂ 1.1.3 Conditional Statements We will discuss several other important ways in which propositions can be combined. Definition 5 Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q.” The conditional statement p → q is false when p is true and q is false, and true otherwise. In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence). Assessment The statement p → q is called a conditional statement because p → q asserts that q is true on the condition that p holds. A conditional statement is also called an implication. The truth table for the conditional statement p → q is shown in Table 5. Note that the state- ment p → q is true when both p and q are true and when p is false (no matter what truth value q has). TABLE 4 The Truth Table for TABLE 5 The Truth Table for the Exclusive Or of Two the Conditional Statement Propositions. p → q. p q p⊕q p q p→q T T F T T T T F T T F F F T T F T T F F F F F T  1.1 Propositional Logic 7 Because conditional statements play such an essential role in mathematical reasoning, a va- riety of terminology is used to express p → q. You will encounter most if not all of the following ways to express this conditional statement: “if p, then q” “p implies q” “if p, q” “p only if q” “p is sufficient for q” “a sufficient condition for q is p” “q if p” “q whenever p” “q when p” “q is necessary for p” “a necessary condition for p is q” “q follows from p” “q unless ¬p” “q provided that p” A useful way to understand the truth value of a conditional statement is to think of an obli- gation or a contract. For example, the pledge many politicians make when running for office is “If I am elected, then I will lower taxes.” If the politician is elected, voters would expect this politician to lower taxes. Furthermore, if the politician is not elected, then voters will not have any expectation that this person will lower taxes, although the person may have sufficient influence to cause those in power to lower taxes. It is only when the politician is elected but does not lower taxes that voters can say that the politician has broken the campaign pledge. This last scenario corresponds to the case when p is true but q is false in p → q. Similarly, consider a statement that a professor might make: “If you get 100% on the final, then you will get an A.” If you manage to get 100% on the final, then you would expect to receive an A. If you do not get 100%, you may or may not receive an A depending on other factors. However, if you do get 100%, but the professor does not give you an A, you will feel cheated. Remark: Because some of the different ways to express the implication p implies q can be confusing, we will provide some extra guidance. To remember that “p only if q” expresses the same thing as “if p, then q,” note that “p only if q” says that p cannot be true when q is not true. That is, the statement is false if p is true, but q is false. When p is false, q may be either true or false, because the statement says nothing about the truth value of q. For example, suppose your professor tells you “You can receive an A in the course only if your score on the final is at least 90%.” Then, if you receive an A in the course, then you know that your score on the final is at least 90%. If you do not receive an A, you may or may not have scored at least 90% on the final. Be careful not to use “q only if p” to express p → q because this is incorrect. The word “only” plays an essential role here. To see this, note that the truth values of “q only if p” and p → q are different when p and q have different truth values. To see why “q is necessary for p” is equivalent to “if p, then q,” observe that “q is necessary for p” means that p cannot be true unless q is true, or that if q is false, then p is false. This is the same as saying that if p is true, then q is true. To see why “p is sufficient for q” is equivalent to “if p, then q,” note that “p is sufficient for q” means if p is true, it must be the case that q is also true. This is the same as You might have trouble saying that if p is true, then q is also true. understanding how To remember that “q unless ¬p” expresses the same conditional statement as “if p, then “unless” is used in conditional statements q,” note that “q unless ¬p” means that if ¬p is false, then q must be true. That is, the state- unless you read this ment “q unless ¬p” is false when p is true but q is false, but it is true otherwise. Consequently, paragraph carefully. “q unless ¬p” and p → q always have the same truth value. 8 1 / The Foundations: Logic and Proofs We illustrate the translation between conditional statements and English statements in Example 10. EXAMPLE 10 Let p be the statement “Maria learns discrete mathematics” and q the statement “Maria will find Extra a good job.” Express the statement p → q as a statement in English. Examples Solution: From the definition of conditional statements, we see that when p is the statement “Maria learns discrete mathematics” and q is the statement “Maria will find a good job,” p → q represents the statement “If Maria learns discrete mathematics, then she will find a good job.” There are many other ways to express this conditional statement in English. Among the most natural of these are “Maria will find a good job when she learns discrete mathematics.” “For Maria to get a good job, it is sufficient for her to learn discrete mathematics.” and “Maria will find a good job unless she does not learn discrete mathematics.” ◂ Note that the way we have defined conditional statements is more general than the meaning attached to such statements in the English language. For instance, the conditional statement in Example 10 and the statement “If it is sunny, then we will go to the beach” are statements used in normal language where there is a relationship between the hypothesis and the conclusion. Further, the first of these statements is true unless Maria learns discrete mathematics, but she does not get a good job, and the second is true unless it is indeed sunny, but we do not go to the beach. On the other hand, the statement “If Juan has a smartphone, then 2 + 3 = 5” is true from the definition of a conditional statement, because its conclusion is true. (The truth value of the hypothesis does not matter then.) The conditional statement “If Juan has a smartphone, then 2 + 3 = 6” is true if Juan does not have a smartphone, even though 2 + 3 = 6 is false. We would not use these last two conditional statements in natural language (except perhaps in sarcasm), because there is no relationship between the hypothesis and the conclusion in either statement. In math- ematical reasoning, we consider conditional statements of a more general sort than we use in English. The mathematical concept of a conditional statement is independent of a cause-and- effect relationship between hypothesis and conclusion. Our definition of a conditional statement specifies its truth values; it is not based on English usage. Propositional language is an artificial language; we only parallel English usage to make it easy to use and remember. The if-then construction used in many programming languages is different from that used in logic. Most programming languages contain statements such as if p then S, where p is a proposition and S is a program segment (one or more statements to be executed). (Although this looks as if it might be a conditional statement, S is not a proposition, but rather is a set of executable instructions.) When execution of a program encounters such a statement, S is executed if p is true, but S is not executed if p is false, as illustrated in Example 11.  1.1 Propositional Logic 9 EXAMPLE 11 What is the value of the variable x after the statement if 2 + 2 = 4 then x := x + 1 if x = 0 before this statement is encountered? (The symbol := stands for assignment. The state- ment x := x + 1 means the assignment of the value of x + 1 to x.) Solution: Because 2 + 2 = 4 is true, the assignment statement x := x + 1 is executed. Hence, x has the value 0 + 1 = 1 after this statement is encountered. ◂ CONVERSE, CONTRAPOSITIVE, AND INVERSE We can form some new conditional statements starting with a conditional statement p → q. In particular, there are three related conditional statements that occur so often that they have special names. The proposition q → p is called the converse of p → q. The contrapositive of p → q is the proposition ¬q → ¬p. The proposition ¬p → ¬q is called the inverse of p → q. We will see that of these three condi- tional statements formed from p → q, only the contrapositive always has the same truth value as p → q. We first show that the contrapositive, ¬q → ¬p, of a conditional statement p → q always has the same truth value as p → q. To see this, note that the contrapositive is false only when ¬p is false and ¬q is true, that is, only when p is true and q is false. We now show that neither the converse, q → p, nor the inverse, ¬p → ¬q, has the same truth value as p → q for all possible truth values of p and q. Note that when p is true and q is false, the original conditional statement is false, but the converse and the inverse are both true. Remember that the contrapositive, but When two compound propositions always have the same truth values, regardless of the truth neither the converse or values of its propositional variables, we call them equivalent. Hence, a conditional statement inverse, of a conditional and its contrapositive are equivalent. The converse and the inverse of a conditional statement statement is equivalent are also equivalent, as the reader can verify, but neither is equivalent to the original conditional to it. statement. (We will study equivalent propositions in Section 1.3.) Take note that one of the most common logical errors is to assume that the converse or the inverse of a conditional statement is equivalent to this conditional statement. We illustrate the use of conditional statements in Example 12. EXAMPLE 12 Find the contrapositive, the converse, and the inverse of the conditional statement Extra “The home team wins whenever it is raining.” Examples Solution: Because “q whenever p” is one of the ways to express the conditional statement p → q, the original statement can be rewritten as “If it is raining, then the home team wins.” Consequently, the contrapositive of this conditional statement is “If the home team does not win, then it is not raining.” The converse is “If the home team wins, then it is raining.” The inverse is “If it is not raining, then the home team does not win.” Only the contrapositive is equivalent to the original statement. ◂ 10 1 / The Foundations: Logic and Proofs TABLE 6 The Truth Table for the Biconditional p ↔ q. p q p↔q T T T T F F F T F F F T BICONDITIONALS We now introduce another way to combine propositions that expresses that two propositions have the same truth value. Definition 6 Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if and only if q.” The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications. The truth table for p ↔ q is shown in Table 6. Note that the statement p ↔ q is true when both the conditional statements p → q and q → p are true and is false otherwise. That is why we use the words “if and only if” to express this logical connective and why it is symbolically written by combining the symbols → and ←. There are some other common ways to express p ↔ q: “p is necessary and sufficient for q” “if p then q, and conversely” “p iff q.” “p exactly when q.” The last way of expressing the biconditional statement p ↔ q uses the abbreviation “iff” for “if and only if.” Note that p ↔ q has exactly the same truth value as (p → q) ∧ (q → p). EXAMPLE 13 Let p be the statement “You can take the flight,” and let q be the statement “You buy a ticket.” Then p ↔ q is the statement Extra Examples “You can take the flight if and only if you buy a ticket.” This statement is true if p and q are either both true or both false, that is, if you buy a ticket and can take the flight or if you do not buy a ticket and you cannot take the flight. It is false when p and q have opposite truth values, that is, when you do not buy a ticket, but you can take the flight (such as when you get a free trip) and when you buy a ticket but you cannot take the flight (such as when the airline bumps you). ◂ IMPLICIT USE OF BICONDITIONALS You should be aware that biconditionals are not always explicit in natural language. In particular, the “if and only if” construction used in biconditionals is rarely used in common language. Instead, biconditionals are often expressed using an “if, then” or an “only if” construction. The other part of the “if and only if” is implicit. That is, the converse is implied, but not stated. For example, consider the statement in English “If you finish your meal, then you can have dessert.” What is really meant is “You can have dessert if and only if you finish your meal.” This last statement is logically equivalent to the two statements “If you finish your meal, then you can have dessert” and “You can have dessert only if you finish your meal.” Because of this imprecision in natural language, we need to make an assumption whether a conditional statement in natural language implicitly includes its converse. Because precision is essential in mathematics and in logic, we will always distinguish between the conditional statement p → q and the biconditional statement p ↔ q.  1.1 Propositional Logic 11 1.1.4 Truth Tables of Compound Propositions We have now introduced five important logical connectives—conjunction, disjunction, exclu- Demo sive or, implication, and the biconditional operator—as well as negation. We can use these con- nectives to build up complicated compound propositions involving any number of propositional variables. We can use truth tables to determine the truth values of these compound propositions, as Example 14 illustrates. We use a separate column to find the truth value of each compound expression that occurs in the compound proposition as it is built up. The truth values of the compound proposition for each combination of truth values of the propositional variables in it is found in the final column of the table. EXAMPLE 14 Construct the truth table of the compound proposition (p ∨ ¬q) → (p ∧ q). Solution: Because this truth table involves two propositional variables p and q, there are four rows in this truth table, one for each of the pairs of truth values TT, TF, FT, and FF. The first two columns are used for the truth values of p and q, respectively. In the third column we find the truth value of ¬q, needed to find the truth value of p ∨ ¬q, found in the fourth column. The fifth column gives the truth value of p ∧ q. Finally, the truth value of (p ∨ ¬q) → (p ∧ q) is found in the last column. The resulting truth table is shown in Table 7. ◂ TABLE 7 The Truth Table of (p ∨ ¬ q) → (p ∧ q). p q ¬q p ∨ ¬q p∧q (p ∨ ¬q) → (p ∧ q) T T F T T T T F T T F F F T F F F T F F T T F F 1.1.5 Precedence of Logical Operators We can construct compound propositions using the negation operator and the logical operators defined so far. We will generally use parentheses to specify the order in which logical operators in a compound proposition are to be applied. For instance, (p ∨ q) ∧ (¬r) is the conjunction of p ∨ q and ¬r. However, to reduce the number of parentheses, we specify that the negation operator is applied before all other logical operators. This means that ¬p ∧ q is the conjunction of ¬p and q, namely, (¬p) ∧ q, not the negation of the conjunction of p and q, namely ¬(p ∧ q). (It is generally the case that unary operators that involve only one object precede binary operators.) TABLE 8 Another general rule of precedence is that the conjunction operator takes precedence over Precedence of Logical Operators. the disjunction operator, so that p ∨ q ∧ r means p ∨ (q ∧ r) rather than (p ∨ q) ∧ r and p ∧ q ∨ r means (p ∧ q) ∨ r rather than p ∧ (q ∨ r). Because this rule may be difficult to remember, we will Operator Precedence continue to use parentheses so that the order of the disjunction and conjunction operators is clear. Finally, it is an accepted rule that the conditional and biconditional operators, → and ↔, ¬ 1 have lower precedence than the conjunction and disjunction operators, ∧ and ∨. Consequently, ∧ 2 p → q ∨ r means p → (q ∨ r) rather than (p → q) ∨ r and p ∨ q → r means (p ∨ q) → r rather ∨ 3 than p ∨ (q → r). We will use parentheses when the order of the conditional operator and bi- → 4 conditional operator is at issue, although the conditional operator has precedence over the ↔ 5 biconditional operator. Table 8 displays the precedence levels of the logical operators, ¬, ∧, ∨, →, and ↔. 12 1 / The Foundations: Logic and Proofs 1.1.6 Logic and Bit Operations Computers represent information using bits. A bit is a symbol with two possible values, namely, Truth Value Bit 0 (zero) and 1 (one). This meaning of the word bit comes from binary digit, because zeros and ones are the digits used in binary representations of numbers. The well-known statistician John T 1 Tukey introduced this terminology in 1946. A bit can be used to represent a truth value, because F 0 there are two truth values, namely, true and false. As is customarily done, we will use a 1 bit to represent true and a 0 bit to represent false. That is, 1 represents T (true), 0 represents F (false). A variable is called a Boolean variable if its value is either true or false. Consequently, Links a Boolean variable can be represented using a bit. Computer bit operations correspond to the logical connectives. By replacing true by a one and false by a zero in the truth tables for the operators ∧, ∨, and ⊕, the columns in Table 9 for the corresponding bit operations are obtained. We will also use the notation OR, AND, and XOR for the operators ∨, ∧, and ⊕, as is done in various programming languages. TABLE 9 Table for the Bit Operators OR, AND, and XOR. x y x∨y x∧y x⊕y 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 Information is often represented using bit strings, which are lists of zeros and ones. When this is done, operations on the bit strings can be used to manipulate this information. Definition 7 A bit string is a sequence of zero or more bits. The length of this string is the number of bits in the string. EXAMPLE 15 101010011 is a bit string of length nine. ◂ Links JOHN WILDER TUKEY (1915–2000) Tukey, born in New Bedford, Massachusetts, was an only child. His parents, both teachers, decided home schooling would best develop his potential. His formal education began at Brown University, where he studied mathematics and chemistry. He received a master’s degree in chemistry from Brown and continued his studies at Princeton University, changing his field of study from chemistry to mathematics. He received his Ph.D. from Princeton in 1939 for work in topology, when he was appointed an instructor in mathematics at Princeton. With the start of World War II, he joined the Fire Control Research Office, where he began working in statistics. Tukey found statistical research to his liking and impressed several leading statisticians with his skills. In 1945, at the conclusion of the war, Tukey re- Alfred c Eisenstaedt/ turned to the mathematics department at Princeton as a professor of statistics, and he also took a position The LIFE Picture at AT&T Bell Laboratories. Tukey founded the Statistics Department at Princeton in 1966 and was its first Collection/Getty Images chairman. Tukey made significant contributions to many areas of statistics, including the analysis of variance, the estimation of spectra of time series, inferences about the values of a set of parameters from a single experiment, and the philos- ophy of statistics. However, he is best known for his invention, with J. W. Cooley, of the fast Fourier transform. In addition to his contributions to statistics, Tukey was noted as a skilled wordsmith; he is credited with coining the terms bit and software. Tukey contributed his insight and expertise by serving on the President’s Science Advisory Committee. He chaired several important committees dealing with the environment, education, and chemicals and health. He also served on committees working on nuclear disarmament. Tukey received many awards, including the National Medal of Science. HISTORICAL NOTE There were several other suggested words for a binary digit, including binit and bigit, that never were widely accepted. The adoption of the word bit may be due to its meaning as a common English word. For an account of Tukey’s coining of the word bit, see the April 1984 issue of Annals of the History of Computing.  1.1 Propositional Logic 13 We can extend bit operations to bit strings. We define the bitwise OR, bitwise AND, and bitwise XOR of two strings of the same length to be the strings that have as their bits the OR, AND, and XOR of the corresponding bits in the two strings, respectively. We use the symbols ∨, ∧, and ⊕ to represent the bitwise OR, bitwise AND, and bitwise XOR operations, respectively. We illustrate bitwise operations on bit strings with Example 16. EXAMPLE 16 Find the bitwise OR, bitwise AND, and bitwise XOR of the bit strings 01 1011 0110 and 11 0001 1101. (Here, and throughout this book, bit strings will be split into blocks of four bits to make them easier to read.) Solution: The bitwise OR, bitwise AND, and bitwise XOR of these strings are obtained by taking the OR, AND, and XOR of the corresponding bits, respectively. This gives us 01 1011 0110 11 0001 1101 11 1011 1111 bitwise OR 01 0001 0100 bitwise AND 10 1010 1011 bitwise XOR ◂ Exercises 1. Which of these sentences are propositions? What are the c) Abby sent more than 100 text messages yesterday. truth values of those that are propositions? d) 121 is a perfect square. a) Boston is the capital of Massachusetts. 7. What is the negation of each of these propositions? b) Miami is the capital of Florida. a) Steve has more than 100 GB free disk space on his c) 2 + 3 = 5. laptop. d) 5 + 7 = 10. b) Zach blocks e-mails and texts from Jennifer. e) x + 2 = 11. c) 7 ⋅ 11 ⋅ 13 = 999. f ) Answer this question. d) Diane rode her bicycle 100 miles on Sunday. 2. Which of these are propositions? What are the truth 8. Suppose that Smartphone A has 256 MB RAM and values of those that are propositions? 32 GB ROM, and the resolution of its camera is 8 MP; a) Do not pass go. Smartphone B has 288 MB RAM and 64 GB ROM, and b) What time is it? the resolution of its camera is 4 MP; and Smartphone C c) There are no black flies in Maine. has 128 MB RAM and 32 GB ROM, and the resolution d) 4 + x = 5. of its camera is 5 MP. Determine the truth value of each e) The moon is made of green cheese. of these propositions. f ) 2n ≥ 100. a) Smartphone B has the most RAM of these three 3. What is the negation of each of these propositions? smartphones. a) Linda is younger than Sanjay. b) Smartphone C has more ROM or a higher resolution b) Mei makes more money than Isabella. camera than Smartphone B. c) Moshe is taller than Monica. c) Smartphone B has more RAM, more ROM, and a d) Abby is richer than Ricardo. higher resolution camera than Smartphone A. 4. What is the negation of each of these propositions? d) If Smartphone B has more RAM and more ROM than Smartphone C, then it also has a higher resolution a) Janice has more Facebook friends than Juan. camera. b) Quincy is smarter than Venkat. e) Smartphone A has more RAM than Smartphone B if c) Zelda drives more miles to school than Paola. and only if Smartphone B has more RAM than Smart- d) Briana sleeps longer than Gloria. phone A. 5. What is the negation of each of these propositions? 9. Suppose that during the most recent fiscal year, the an- a) Mei has an MP3 player. nual revenue of Acme Computer was 138 billion dollars b) There is no pollution in New Jersey. and its net profit was 8 billion dollars, the annual revenue c) 2 + 1 = 3. of Nadir Software was 87 billion dollars and its net profit d) The summer in Maine is hot and sunny. was 5 billion dollars, and the annual revenue of Quixote 6. What is the negation of each of these propositions? Media was 111 billion dollars and its net profit was a) Jennifer and Teja are friends. 13 billion dollars. Determine the truth value of each of b) There are 13 items in a baker’s dozen. these propositions for the most recent fiscal year.  1.2 Applications of Propositional Logic 17 48. Evaluate each of these expressions. “Fred and John are happy” and “Neither Fred nor John is a) 1 1000 ∧ (0 1011 ∨ 1 1011) happy”? b) (0 1111 ∧ 1 0101) ∨ 0 1000 51. The truth value of the disjunction of two propositions in c) (0 1010 ⊕ 1 1011) ⊕ 0 1000 fuzzy logic is the maximum of the truth values of the two d) (1 1011 ∨ 0 1010) ∧ (1 0001 ∨ 1 1011) propositions. What are the truth values of the statements Fuzzy logic is used in artificial intelligence. In fuzzy logic, a “Fred is happy, or John is happy” and “Fred is not happy, proposition has a truth value that is a number between 0 and or John is not happy”? 1, inclusive. A proposition with a truth value of 0 is false and ∗ 52. Is the assertion “This statement is false” a proposition? one with a truth value of 1 is true. Truth values that are be- ∗ 53. The nth statement in a list of 100 statements is “Exactly tween 0 and 1 indicate varying degrees of truth. For instance, the truth value 0.8 can be assigned to the statement “Fred is n of the statements in this list are false.” happy,” because Fred is happy most of the time, and the truth a) What conclusions can you draw from these state- value 0.4 can be assigned to the statement “John is happy,” ments? because John is happy slightly less than half the time. Use b) Answer part (a) if the nth statement is “At least n of these truth values to solve Exercises 49–51. the statements in this list are false.” 49. The truth value of the negation of a proposition in fuzzy c) Answer part (b) assuming that the list contains 99 logic is 1 minus the truth value of the proposition. What statements. are the truth values of the statements “Fred is not happy” 54. An ancient Sicilian legend says that the barber in a remote and “John is not happy”? town who can be reached only by traveling a dangerous 50. The truth value of the conjunction of two propositions in mountain road shaves those people, and only those peo- fuzzy logic is the minimum of the truth values of the two ple, who do not shave themselves. Can there be such a propositions. What are the truth values of the statements barber? 1.2 Applications of Propositional Logic 1.2.1 Introduction Logic has many important applications to mathematics, computer science, and numerous other disciplines. Statements in mathematics and the sciences and in natural language often are im- precise or ambiguous. To make such statements precise, they can be translated into the language of logic. For example, logic is used in the specification of software and hardware, because these specifications need to be precise before development begins. Furthermore, propositional logic and its rules can be used to design computer circuits, to construct computer programs, to ver- ify the correctness of programs, and to build expert systems. Logic can be used to analyze and solve many familiar puzzles. Software systems based on the rules of logic have been developed for constructing some, but not all, types of proofs automatically. We will discuss some of these applications of propositional logic in this section and in later chapters. 1.2.2 Translating English Sentences There are many reasons to translate English sentences into expressions involving propositional variables and logical connectives. In particular, English (and every other human language) is often ambiguous. Translating sentences into compound statements (and other types of logical expressions, which we will introduce later in this chapter) removes the ambiguity. Note that this may involve making a set of reasonable assumptions based on the intended meaning of the sentence. Moreover, once we have translated sentences from English into logical expres- sions, we can analyze these logical expressions to determine their truth values, we can manip- ulate them, and we can use rules of inference (which are discussed in Section 1.6) to reason about them. To illustrate the process of translating an English sentence into a logical expression, con- sider Examples 1 and 2. 18 1 / The Foundations: Logic and Proofs EXAMPLE 1 How can this English sentence be translated into a logical expression? Extra “You can access the Internet from campus only if you are a computer science major or you Examples are not a freshman.” Solution: There are many ways to translate this sentence into a logical expression. Although it is possible to represent the sentence by a single propositional variable, such as p, this would not be useful when analyzing its meaning or reasoning with it. Instead, we will use propositional vari- ables to represent each sentence part and determine the appropriate logical connectives between them. In particular, we let a, c, and f represent “You can access the Internet from campus,” “You are a computer science major,” and “You are a freshman,” respectively. Noting that “only if” is one way a conditional statement can be expressed, this sentence can be represented as a → (c ∨ ¬f ). ◂ EXAMPLE 2 How can this English sentence be translated into a logical expression? “You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.” Solution: Let q, r, and s represent “You can ride the roller coaster,” “You are under 4 feet tall,” and “You are older than 16 years old,” respectively. Then the sentence can be translated to (r ∧ ¬s) → ¬q. There are other ways to represent the original sentence as a logical expression, but the one we have used should meet our needs. ◂ 1.2.3 System Specifications Translating sentences in natural language (such as English) into logical expressions is an essen- tial part of specifying both hardware and software systems. System and software engineers take requirements in natural language and produce precise and unambiguous specifications that can be used as the basis for system development. Example 3 shows how compound propositions can be used in this process. EXAMPLE 3 Express the specification “The automated reply cannot be sent when the file system is full” using logical connectives. Extra Examples Solution: One way to translate this is to let p denote “The automated reply can be sent” and q de- note “The file system is full.” Then ¬p represents “It is not the case that the automated reply can be sent,” which can also be expressed as “The automated reply cannot be sent.” Consequently, our specification can be represented by the conditional statement q → ¬p. ◂ System specifications should be consistent, that is, they should not contain conflicting re- quirements that could be used to derive a contradiction. When specifications are not consistent, there would be no way to develop a system that satisfies all specifications. EXAMPLE 4 Determine whether these system specifications are consistent: “The diagnostic message is stored in the buffer or it is retransmitted.” “The diagnostic message is not stored in the buffer.” “If the diagnostic message is stored in the buffer, then it is retransmitted.”  1.2 Applications of Propositional Logic 19 Solution: To determine whether these specifications are consistent, we first express them using logical expressions. Let p denote “The diagnostic message is stored in the buffer” and let q denote “The diagnostic message is retransmitted.” The specifications can then be written as p ∨ q, ¬p, and p → q. An assignment of truth values that makes all three specifications true must have p false to make ¬p true. Because we want p ∨ q to be true but p must be false, q must be true. Because p → q is true when p is false and q is true, we conclude that these specifications are consistent, because they are all true when p is false and q is true. We could come to the same conclusion by use of a truth table to examine the four possible assignments of truth values to p and q. ◂ EXAMPLE 5 Do the system specifications in Example 4 remain consistent if the specification “The diagnostic message is not retransmitted” is added? Solution: By the reasoning in Example 4, the three specifications from that example are true only in the case when p is false and q is true. However, this new specification is ¬q, which is false when q is true. Consequently, these four specifications are inconsistent. ◂ 1.2.4 Boolean Searches Logical connectives are used extensively in searches of large collections of information, such Links as indexes of Web pages. Because these searches employ techniques from propositional logic, they are called Boolean searches. In Boolean searches, the connective AND is used to match records that contain both of two search terms, the connective OR is used to match one or both of two search terms, and the connective NOT (sometimes written as AND NOT ) is used to exclude a particular search term. Careful planning of how logical connectives are used is often required when Boolean searches are used to locate information of potential interest. Example 6 illustrates how Boolean searches are carried out. EXAMPLE 6 Web Page Searching Most Web search engines support Boolean searching techniques, which is useful for finding Web pages about particular subjects. For instance, using Boolean searching to find Web pages about universities in New Mexico, we can look for pages matching NEW AND MEXICO AND UNIVERSITIES. The results of this search will include those pages that contain the three words NEW, MEXICO, and UNIVERSITIES. This will include all of the pages of interest, together with others such as a page about new universities in Mexico. (Note Extra that Google, and many other search engines, do require the use of “AND” because such search Examples engines use all search terms by default.) Most search engines support the use of quotation marks to search for specific phrases. So, it may be more effective to search for pages matching “NEW MEXICO” AND UNIVERSITIES. Next, to find pages that deal with universities in New Mexico or Arizona, we can search for pages matching (NEW AND MEXICO OR ARIZONA) AND UNIVERSITIES. (Note: Here the AND operator takes precedence over the OR operator. Also, in Google, the terms used for this search would be NEW MEXICO OR ARIZONA.) The results of this search will include all pages that contain the word UNIVERSITIES and either both the words NEW and MEXICO or the word ARIZONA. Again, pages besides those of interest will be listed. Finally, to find Web pages that deal with universities in Mexico (and not New Mexico), we might first look for pages matching MEXICO AND UNIVERSITIES, but because the results of this search will include pages about universities in New Mexico, as well as universities in Mexico, it might be better to search for pages matching (MEXICO AND UNIVERSITIES) NOT NEW. The results of this search include pages that contain both the words MEXICO and UNIVERSITIES but do not contain the word NEW. (In Google, and many other search engines, the word “NOT” is 20 1 / The Foundations: Logic and Proofs replaced by the symbol “-”. In Google, the terms used for this last search would be MEXICO UNIVERSITIES -NEW.) ◂ 1.2.5 Logic Puzzles Links Puzzles that can be solved using logical reasoning are known as logic puzzles. Solving logic puzzles is an excellent way to practice working with the rules of logic. Also, computer programs designed to carry out logical reasoning often use well-known logic puzzles to illustrate their capabilities. Many people enjoy solving logic puzzles, published in periodicals, books, and on the Web, as a recreational activity. The next three examples present logic puzzles, in increasing level of difficulty. Many others can be found in the exercises. In Section 1.3 we will discuss the n-queens puzzle and the game of Sudoku. EXAMPLE 7 As a reward for saving his daughter from pirates, the King has given you the opportunity to win a treasure hidden inside one of three trunks. The two trunks that do not hold the treasure are empty. To win, you must select the correct trunk. Trunks 1 and 2 are each inscribed with the message “This trunk is empty,” and Trunk 3 is inscribed with the message “The treasure is in Trunk 2.” The Queen, who never lies, tells you that only one of these inscriptions is true, while the other two are wrong. Which trunk should you select to win? Solution: Let pi be the proposition that the treasure is in Trunk i, for i = 1, 2, 3. To translate into propositional logic the Queen’s statement that exactly one of the inscriptions is true, we observe that the inscriptions on Trunk 1, Trunk 2, and Trunk 3, are ¬p1 , ¬p2 , and p2 , respectively. So, her statement can be translated to (¬p1 ∧ ¬(¬p2 ) ∧ ¬p2 ) ∨ (¬(¬p1 ) ∧ ¬p2 ∧ ¬p2 ) ∨ (¬(¬p1 ) ∧ ¬(¬p2 ) ∧ p2 )). Using the rules for propositional logic, we see that this is equivalent to (p1 ∧ ¬p2 ) ∨ (p1 ∧ p2 ). By the distributive law, (p1 ∧ ¬p2 ) ∨ (p1 ∧ p2 ) is equivalent to p1 ∧ (¬p2 ∨ p2 ). But because ¬p2 ∨ p2 must be true, this is then equivalent to p1 ∧ T, which is in turn equivalent to p1. So the treasure is in Trunk 1 (that is, p1 is true), and p2 and p3 are false; and the inscription on Trunk 2 is the only true one. (Here, we have used the concept of propositional equivalence, which is discussed in Section 1.3.) ◂ Next, we introduce a puzzle originally posed by Raymond Smullyan, a master of logic puzzles, who has published more than a dozen books containing challenging puzzles that involve logical reasoning. EXAMPLE 8 In [Sm78] Smullyan posed many puzzles about an island that has two kinds of inhabitants, knights, who always tell the truth, and their opposites, knaves, who always lie. You encounter Extra two people A and B. What are A and B if A says “B is a knight” and B says “The two of us are Examples opposite types”? Solution: Let p and q be the statements that A is a knight and B is a knight, respectively, so that ¬p and ¬q are the statements that A is a knave and B is a knave, respectively. We first consider the possibility that A is a knight; this is the statement that p is true. If A is a knight, then he is telling the truth when he says that B is a knight, so that q is true, and A and B are the same type. However, if B is a knight, then B’s statement that A and B are of opposite  1.2 Applications of Propositional Logic 21 types, the statement (p ∧ ¬q) ∨ (¬p ∧ q), would have to be true, which it is not, because A and B are both knights. Consequently, we can conclude that A is not a knight, that is, that p is false. If A is a knave, then because everything a knave says is false, A’s statement that B is a knight, that is, that q is true, is a lie. This means that q is false and B is also a knave. Furthermore, if B is a knave, then B’s statement that A and B are opposite types is a lie, which is consistent with both A and B being knaves. We can conclude that both A and B are knaves. ◂ We pose more of Smullyan’s puzzles about knights and knaves in Exercises 23–27. In Ex- ercises 28–35 we introduce related puzzles where we have three types of people, knights and knaves as in this puzzle together with spies who can lie. Next, we pose a puzzle known as the muddy children puzzle for the case of two children. EXAMPLE 9 A father tells his two children, a boy and a girl, to play in their backyard without getting dirty. However, while playing, both children get mud on their foreheads. When the children stop play- ing, the father says “At least one of you has a muddy forehead,” and then asks the children to answer “Yes” or “No” to the question: “Do you know whether you have a muddy forehead?” The father asks this question twice. What will the children answer each time this question is asked, assuming that a child can see whether his or her sibling has a muddy forehead, but cannot see his or her own forehead? Assume that both children are honest and that the children answer each question simultaneously. Solution: Let s be the statement that the son has a muddy forehead and let d be the statement that the daughter has a muddy forehead. When the father says that at least one of the two children has a muddy forehead, he is stating that the disjunction s ∨ d is true. Both children will answer “No” the first time the question is asked because each sees mud on the other child’s forehead. That is, the son knows that d is true, but does not know whether s is true, and the daughter knows that s is true, but does not know whether d is true. After the son has answered “No” to the first question, the daughter can determine that d must be true. This follows because when the first question is asked, the son knows that s ∨ d is true, but cannot determine whether s is true. Using this information, the daughter can conclude that d must be true, for if d were false, the son could have reasoned that because s ∨ d is true, Links RAYMOND SMULLYAN (1919–2017) Raymond Smullyan, the son of a businessman and a homemaker, was born in Far Rockaway, Queens, New York. He dropped out of high school because he wanted to study what he was really interested in and not standard high school material. After attending Pacific College and Reed College in Oregon, he earned an undergraduate degree in mathematics at the University of Chicago in 1955. He paid his college expenses by performing magic tricks at parties and clubs, using the stage name Five-Ace Merrill. He obtained a Ph.D. in logic in 1959 at Princeton, studying under Alonzo Church. After graduating from Princeton, he taught mathematics and logic at Dartmouth College, Princeton University, Yeshiva University, and the City University of New York. He joined the philosophy department at Indiana University in 1981, where be became Courtesy of Indiana an emeritus professor. University Archives Smullyan wrote many books on recreational logic and mathematics, including Satan, Cantor, and Infin- ity; What Is the Name of This Book?; The Lady or the Tiger?; Alice in Puzzleland; To Mock a Mockingbird; Forever Undecided; and The Riddle of Scheherazade: Amazing Logic Puzzles, Ancient and Modern. Because his logic puzzles are challenging, entertaining, and thought-provoking, he was considered to be a modern-day Lewis Carroll. Smullyan also wrote several books about the application of deductive logic to chess, three collections of philosophical essays and aphorisms, and several advanced books on mathematical logic and set theory. He was particularly interested in self-reference and worked on extending some of Gödel’s results that show that it is impossible to write a computer program that can solve all mathematical problems. He was also particularly interested in explaining ideas from mathematical logic to the public. Smullyan was a talented musician and often played piano with his second wife, who was a concert-level pianist. Making telescopes was one of his hobbies and he was interested in optics and stereo photography. He said, “I’ve never had a conflict between teaching and research as some people do because when I’m teaching, I’m doing research.” Smullyan is the subject of a documentary short film entitled This Film Needs No Title. 22 1 / The Foundations: Logic and Proofs then s must be true, and he would have answered “Yes” to the first question. The son can reason in a similar way to determine that s must be true. It follows that both children answer “Yes” the second time the question is asked. ◂ 1.2.6 Logic Circuits Propositional logic can be applied to the design of computer hardware. This was first observed in 1938 by Claude Shannon in his MIT master’s thesis. In Chapter 12 we will study this topic in depth. (See that chapter for a biography of Shannon.) We give a brief introduction to this application here. A logic circuit (or digital circuit) receives input signals p1 , p2 , … , pn , each a bit [either 0 (off) or 1 (on)], and produces output signals s1 , s2 , … , sn , each a bit. In this section we will In Chapter 12 we will restrict our attention to logic circuits with a single output signal; in general, digital circuits may design some useful have multiple outputs. circuits. Complicated digital circuits can be constructed from three basic circuits, called gates, shown in Figure 1. The inverter, or NOT gate, takes an input bit p, and produces as output ¬p. The OR gate takes two input signals p and q, each a bit, and produces as output the signal p ∨ q. Finally, the AND gate takes two input signals p and q, each a bit, and produces as out- put the signal p ∧ q. We use combinations of these three basic gates to build more complicated circuits, such as that shown in Figure 2. ¬p p p∨q p p∧q p q q Inverter OR gate AND gate FIGURE 1 Basic logic gates. Given a circuit built from the basic logic gates and the inputs to the circuit, we determine the output by tracing through the circuit, as Example 10 shows. EXAMPLE 10 Determine the output for the combinatorial circuit in Figure 2. Solution: In Figure 2 we display the output of each logic gate in the circuit. We see that the AND gate takes input of p and ¬q, the output of the inverter with input q, and produces p ∧ ¬q. Next, we note that the OR gate takes input p ∧ ¬q and ¬r, the output of the inverter with input r, and produces the final output (p ∧ ¬q) ∨ ¬r. ◂ Suppose that we have a formula for the output of a digital circuit in terms of negations, dis- junctions, and conjunctions. Then, we can systematically build a digital circuit with the desired output, as illustrated in Example 11. p p ∧ ¬q q (p ∧ ¬q) ∨ ¬r ¬q r ¬r FIGURE 2 A combinatorial circuit.  1.2 Applications of Propositional Logic 23 p p ∨ ¬r r ¬r (p ∨ ¬r) ∧ (¬p ∨ (q ∨ ¬r)) ¬p p q ¬p ∨ (q ∨ ¬r) r q ∨ ¬r ¬r FIGURE 3 The circuit for (p ∨ ¬r) ∧ (¬p ∨ (q ∨ ¬r)). EXAMPLE 11 Build a digital circuit that produces the output (p ∨ ¬r) ∧ (¬p ∨ (q ∨ ¬r)) when given input bits p, q, and r. Solution: To construct the desired circuit, we build separate circuits for p ∨ ¬r and for ¬p ∨ (q ∨ ¬r) and combine them using an AND gate. To construct a circuit for p ∨ ¬r, we use an inverter to produce ¬r from the input r. Then, we use an OR gate to combine p and ¬r. To build a circuit for ¬p ∨ (q ∨ ¬r), we first use an inverter to obtain ¬r. Then we use an OR gate with inputs q and ¬r to obtain q ∨ ¬r. Finally, we use another inverter and an OR gate to get ¬p ∨ (q ∨ ¬r) from the inputs p and q ∨ ¬r. To complete the construction, we employ a final AND gate, with inputs p ∨ ¬r and ¬p ∨ (q ∨ ¬r). The resulting circuit is displayed in Figure 3. ◂ We will study logic circuits in great detail in Chapter 12 in the context of Boolean algebra, and with different notation. Exercises In Exercises 1–6, translate the given statement into proposi- time of your birth both of your parents were citizens, and tional logic using the propositions provided. you have lived at least 14 years in the country. Express 1. You cannot edit a protected Wikipedia entry unless you your answer in terms of e: “You are eligible to be Pres- are an administrator. Express your answer in terms of e: ident of the U.S.A.,” a: “You are at least 35 years old,” “You can edit a protected Wikipedia entry” and a: “You b: “You were born in the U.S.A.,” p: “At the time of your are an administrator.” birth, both of your parents were citizens,” and r: “You have lived at least 14 years in the U.S.A.” 2. You can see the movie only if you are over 18 years old 6. You can upgrade your operating system only if you have a or you have the permission of a parent. Express your an- 32-bit processor running at 1 GHz or faster, at least 1 GB swer in terms of m: “You can see the movie,” e: “You are RAM, and 16 GB free hard disk space, or a 64-bit pro- over 18 years old,” and p: “You have the permission of a cessor running at 2 GHz or faster, at least 2 GB RAM, parent.” and at least 32 GB free hard disk space. Express your an- 3. You can graduate only if you have completed the require- swer in terms of u: “You can upgrade your operating sys- ments of your major and you do not owe money to the tem,” b32 : “You have a 32-bit processor,” b64 : “You have university and you do not have an overdue library book. a 64-bit processor,” g1 : “Your processor runs at 1 GHz or Express your answer in terms of g: “You can graduate,” faster,” g2 : “Your processor runs at 2 GHz or faster,” r1 : m: “You owe money to the university,” r: “You have com- “Your processor has at least 1 GB RAM,” r2 : “Your pro- pleted the requirements of your major,” and b: “You have cessor has at least 2 GB RAM,” h16 : “You have at least an overdue library book.” 16 GB free hard disk space,” and h32 : “You have at least 4. To use the wireless network in the airport you must pay 32 GB free hard disk space.” the daily fee unless you are a subscriber to the service. 7. Express these system specifications using the proposi- Express your answer in terms of w: “You can use the tions p: “The message is scanned for viruses” and q: “The wireless network in the airport,” d: “You pay the daily message was sent from an unknown system” together fee,” and s: “You are a subscriber to the service.” with logical connectives (including negations). 5. You are eligible to be President of the U.S.A. only if you a) “The message is scanned for viruses whenever the are at least 35 years old, were born in the U.S.A., or at the message was sent from an unknown system.” 24 1 / The Foundations: Logic and Proofs b) “The message was sent from an unknown system but 16. What Google search would you use to look for men’s it was not scanned for viruses.” shoes or boots not designed for work? c) “It is necessary to scan the message for viruses when- 17. Suppose that in Example 7, the inscriptions on Trunks 1, ever it was sent from an unknown system.” 2, and 3 are “The treasure is in Trunk 3,” “The treasure is d) “When a message is not sent from an unknown sys- in Trunk 1,” and “This trunk is empty.” For each of these tem it is not scanned for viruses.” statements, determine whether the Queen who never 8. Express these system specifications using the proposi- lies could state this, and if so, which trunk the treasure tions p: “The user enters a valid password,” q: “Access is in. is granted,” and r: “The user has paid the subscription a) “All the inscriptions are false.” fee” and logical connectives (including negations). b) “Exactly one of the inscriptions is true.” a) “The user has paid the subscription fee, but does not c) “Exactly two of the inscriptions are true.” enter a valid password.” d) “All three inscriptions are true.” b) “Access is granted whenever the user has paid the 18. Suppose that in Example 7 there are treasures in two of subscription fee and enters a valid password.” the three trunks. The inscriptions on Trunks 1, 2, and 3 c) “Access is denied if the user has not paid the subscrip- are “This trunk is empty,” “There is a treasure in Trunk tion fee.” 1,” and “There is a treasure in Trunk 2.” For each of these d) “If the user has not entered a valid password but has statements, determine whether the Queen who never lies paid the subscription fee, then access is granted.” could state this, and if so, which two trunks the treasures are in. 9. Are these system specifications consistent? “The system is in multiuser state if and only if it is operating normally. a) “All the inscriptions are false.” If the system is operating normally, the kernel is func- b) “Exactly one of the inscriptions is true.” tioning. The kernel is not functioning or the system is in c) “Exactly two of the inscriptions are true.” interrupt mode. If the system is not in multiuser state, d) “All three inscriptions are true.” then it is in interrupt mode. The system is not in interrupt ∗ 19. Each inhabitant of a remote village always tells the truth mode.” or always lies. A villager will give only a “Yes” or a “No” 10. Are these system specifications consistent? “Whenever response to a question a tourist asks. Suppose you are a the system software is being upgraded, users cannot ac- tourist visiting this area and come to a fork in the road. cess the file system. If users can access the file system, One branch leads to the ruins you want to visit; the other then they can save new files. If users cannot save new branch leads deep into the jungle. A villager is standing files, then the system software is not being upgraded.” at the fork in the road. What one question can you ask the villager to determine which branch to take? 11. Are these system specifications consistent? “The router 20. An explorer is captured by a group of cannibals. There are can send packets to the edge system only if it supports the two types of cannibals—those who always tell the truth new address space. For the router to support the new ad- and those who always lie. The cannibals will barbecue dress space it is necessary that the latest software release the explorer unless he can determine whether a particu- be installed. The router can send packets to the edge sys- lar cannibal always lies or always tells the truth. He is tem if the latest software release is installed. The router allowed to ask the cannibal exactly one question. does not support the new address space.” a) Explain why the question “Are you a liar?” does not 12. Are these system specifications consistent? “If the file work. system is not locked, then new messages will be queued. b) Find a question that the explorer can use to determine If the file system is not locked, then the system is func- whether the cannibal always lies or always tells the tioning normally, and conversely. If new messages are not truth. queued, then they will be sent to the message buffer. If the file system is not locked, then new messages will be sent 21. When three professors are seated in a restaurant, the host- to the message buffer. New messages will not be sent to ess asks them: “Does everyone want coffee?” The first the message buffer.” professor says “I do not know.” The second professor then says “I do not know.” Finally, the third professor says 13. What Boolean search would you use to look for Web “No, not everyone wants coffee.” The hostess comes back pages about beaches in New Jersey? What if you wanted and gives coffee to the professors who want it. How did to find Web pages about beaches on the isle of Jersey (in she figure out who wanted coffee? the English Channel)?