xx To the Student TABLE 1 Hand-Icon Exercises and where They are Used Section Exercise Section Where Used Pages Where Used 41 31 .6 71 13 10 16 70,71 71 717 122 20 86 2.3 144 23 25 170 174 25 3 11 761 4.2 270 41 239 46 301 466 7.4 480 7.2 466 94 508 104 11.1 747 1. 11.2 762 12.1 12 12.3 825 A2 83 531 THE VALUE OF THIS BOOK My intention is to make your substantial investment in this text an excellent value.The book,the associated ancillaries,and companion website have taken many years of effort to develop and refine.I am confident that most of you will find that hem ner likcly that vou wille mathematics.just so many previous students hav not cover some ill rotur useful tool throughout your future studies.especiall for those of you who continue in computer science,mathematics,and engineering I have designed this book to be a gateway for future studies and explorations,and to be comprehensive reference,and I wish you luck as you begin your journey. Kenneth H.Rosen
xx To the Student TABLE 1 Hand-Icon Exercises and Where They Are Used Section Exercise Section Where Used Pages Where Used 1.1 40 1.3 31 1.1 41 1.3 31 1.3 9 1.6 71 1.3 10 1.6 70, 71 1.3 15 1.6 71 1.3 30 1.6 71, 74 1.3 42 12.2 820 1.7 16 1.7 86 2.3 72 2.3 144 2.3 79 2.5 170 2.5 15 2.5 174 2.5 16 2.5 173 3.1 43 3.1 197 3.2 72 11.2 761 4.2 36 4.2 270 4.3 37 4.1 239 4.4 2 4.6 301 4.4 44 7.2 464 6.4 17 7.2 466 6.4 21 7.4 480 7.2 15 7.2 466 9.1 26 9.4 598 10.4 59 11.1 747 11.1 15 11.1 750 11.1 30 11.1 755 11.1 48 11.2 762 12.1 12 12.3 825 A.2 4 8.3 531 THE VALUE OF THIS BOOK My intention is to make your substantial investment in this text an excellent value. The book, the associated ancillaries, and companion website have taken many years of effort to develop and refine. I am confident that most of you will find that the text and associated materials will help you master discrete mathematics, just as so many previous students have. Even though it is likely that you will not cover some chapters in your current course, you should find it helpful—as many other students have—to read the relevant sections of the book as you take additional courses. Most of you will return to this book as a useful tool throughout your future studies, especially for those of you who continue in computer science, mathematics, and engineering. I have designed this book to be a gateway for future studies and explorations, and to be comprehensive reference, and I wish you luck as you begin your journey. Kenneth H. Rosen
CHAPTER The Foundations: Logic and Proofs 1.1 Propositional he rules of logic r specify the meaning of mathematical statements for instance these rule Logic help us understand and reason with statements such as"There exists an integer that is “ sum of squaresandFor every positive integer n.the sumohosie not exceeding n isn+1)/2.Logic is the basis of all mathematical reasoning.and of d reasoning.It has practic ications to the design of computing machines,to the 1.3 Propositional ems.to a mput eauivalences atics,we must understand at make 1.4 Predica To n that is. ce we prove ama s up a corre 1.5 Nested topic.a person needs to actively construct mathematical arguments on this topic.and not just read exposition.Moreover.,knowing the proof of a theorem often makes it possible to modify the result to fit new situations. 1.6 Rules of Everyone knows that proofs are important throughout mathematics,but many people find Inference it surprising how important proofs are in computer science.In fact,proofs are used to verify hat c mputer programs pro r all possible e input values.to show tha ays pro the correct result. the or a system,and ntel 0e omated reasoning systems have been creal that will enable us to y different lopfter introduci differen 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 Introduction The rules of logic give precise meaning to mathematical statements.These rules are used to distinguish betwee en valid and invalid mathematical arguments.Because a major goal of this book Besides the importance of logic in understanding mathematical reasoning.logic has numer computer sclence e use in the design o omputer circu uer programs,the v s h ed for of programs, es of proofs automatically.We will discuss these applications of logic in this and
1 CHAPTER The Foundations: Logic and Proofs 1.1 Propositional Logic 1.2 Applications of Propositional Logic 1.3 Propositional Equivalences 1.4 Predicates and Quantifiers 1.5 Nested Quantifiers 1.6 Rules of Inference 1.7 Introduction to Proofs 1.8 Proof Methods and Strategy The 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 positive integers not exceeding n is n(n + 1)/2.” Logic is the basis of all mathematical reasoning, and of all automated reasoning. It has practical applications to the design of computing machines, to the specification of systems, to artificial intelligence, to computer programming, to programming languages, and to other areas of computer science, as well as to many other fields of study. To understand mathematics, we must understand what makes up a correct mathematical 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 mathematical topic, a person needs to actively construct mathematical arguments on this topic, and not just read exposition. Moreover, knowing the proof of a theorem often makes it possible to modify the result to fit new situations. 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 that computer programs produce the correct output for all possible input values, to show that algorithms always produce the correct result, to establish the security of a system, and to create artificial intelligence. Furthermore, automated reasoning systems have been created to allow computers to construct their own proofs. In this chapter, we will explain what makes up a correct mathematical argument and introduce 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 introduce the notion of a conjecture and explain the process of developing mathematics by studying conjectures. 1.1 Propositional Logic Introduction The rules of logic give precise meaning to mathematical statements. These rules are used to distinguish 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 numerous 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 Propositions Our discussion begins with an introduction to the basic building blocks of logic- positions 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 Doantptes 1.Washington,D.C.,is the capital of the United States of America. 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= and 4 can be tumed into a pro values to th variables.We will also di other ways to turn sentences such as these into positions in Section 1.4. We use letters to denote propositional variables(or sta ables that represent propositions,just as letters are used RISTOTLE (384 BCE-322 B.CE)Aristotle was bom in St s(Stagira)in norther m Greece.His fathe an young.A oric.and reek.At the ttended Plato's lectures.la enting s own le es on rhetor When Plato d in 347 Bc ed th King Hermeas v ne rem for three ece Aristotle's foll of King th ed to A led t eoften walked around as he ed to Aristotle wrote three types of works:th en about 200 years later.They were o Rome,whe hey were st n neweditions.preserving them for posterity
2 1 / The Foundations: Logic and Proofs 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. 1. Washington, D.C., is the capital of the United States of America. 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 statement variables), that is, variables that represent propositions, just as letters are used to denote numerical variables. The 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 of the King. When the Persians defeated Hermeas, Aristotle moved to Mytilene and, at the invitation of King 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 ntional letters tional variables The truth value of a is false,denoted by F.if it isa false proposition. 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 2300 years ago. sfrom those tha in 1854 in his book The Laus of Though.Many mathematical statements are const combining one or more propositions.New propositions,called compound propositions,are formed from existing propositions using logical operators. DEFINITION L 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 EXAMPLE3 Find the negation of the proposition "Michael's PC runs Linux" a编西 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." EXAMPLE4 Find the negation of the proposition "Vandana's smartphone has at least 32GB of memory" and express this in simple English. Solution:The negation is "It is not the case that Vandana's smartphone has at least 32GB of memory." This negation can also be expressed as "Vandana's smartphone does not have at least 32GB of memory or even more simply as "Vandana's smartphone has less than 32GB of memory
1.1 Propositional Logic 3 conventional letters used for propositional variables are p, q, r, s, . . . . The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition. The area of logic that deals with propositions is called the propositional calculus or propositional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago. 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 combining 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. EXAMPLE 3 Find the negation of the proposition “Michael’s PC runs Linux” 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 32GB of memory” and express this in simple English. Solution: The negation is “It is not the case that Vandana’s smartphone has at least 32GB of memory.” This negation can also be expressed as “Vandana’s smartphone does not have at least 32GB of memory” or even more simply as “Vandana’s smartphone has less than 32GB of memory.” ▲
4 1/The Foundations:Logic and Proofs TABLE1 The Table 1 displays the truth table for the negation of a proposition p.This table has a row for each of the two possible truth values of a proposition p.Each row shows the truth value of his row. roposition. also be con sidered the result of the operation of the -P or on a propoNe rators are also called connectives. s of This table has a f th fo a row f nd to the airs of t TF.F.and FF.where the rst truh value i the value pair is the truth value of p and the second truth value is the truth value of g. Note that in logic the word"but"sometimes is used instead of"and"in a conjunction.For example,the statement"The sun is sh re is a su here. EXAMPLE 5 Find the conjunction of the where p is the p osition "Rebecca's pc has more than GB free hard dis spaceand the proposition The processor in Rebeccas PC runs faster than 1 GHz." ese proposit ns.pAq,is ca's PC ha free hard o n 16 GB runs fase s 1GHz”For this c n to be both conditions given must be true.It is false.when one or both of these conditions are false. DEFINITION 3 p or q. Table 3 displays the truth table for p. TABLE 2 The Truth Table for TABLE 3 The Truth Table for Propo P V q
4 1 / The Foundations: Logic and Proofs TABLE 1 The Truth Table for the Negation of a Proposition. p ¬p T F F T Table 1 displays the truth table for the negation of a proposition p. This table has a row for each of the two possible truth values of a proposition p. Each row shows the truth value of ¬p corresponding to the truth value of p for this row. 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 a single existing proposition. We will now introduce the logical operators that are used to form new propositions from two or more existing propositions. These logical operators are also called 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 the Conjunction of Two Propositions. p q p ∧ q T T T T F F F T F F F F TABLE 3 The Truth Table for the Disjunction of Two Propositions. p q p ∨ q T T T T F T F T T F F F