Page
1
(This page has no text content)
Page
2
Discrete Mathematics AN INTRODUCTION TO PROOFS AND COMBINATORICS KEVIN FERLAND Bloomsburg University HOUGHTON MIFFLIN COMPANY Boston New York
Page
3
To Sarah and Ethan Publisher: Richard Stratton Senior Sponsoring Editor: Molly Taylor Senior Marketing Manager: Jennifer Jones Senior Development Editor: Maria Morelli Senior Project Editor: Tamela Ambush Art and Design Manager: Jill Haber Cover Design Manager: Anne S. Katzeff Senior Composition Buyer: Chuck Dutton New Title Project Manager: Susan Peltier Editorial Associate: Andrew Lipsett Editorial Assistant: Joanna Carter-O’Connell Cover image: © Peter Samuels Copyright © 2009 by Houghton Mifflin Company. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying and recording, or by any information storage or retrieval system without the prior written permission of Houghton Mifflin Company unless such copying is expressly permitted by federal copyright law. Address inquiries to College Permissions, Houghton Mifflin Company, 222 Berkeley Street, Boston, MA 02116-3764. Printed in the U.S.A. Library of Congress Control Number: 2007941451 ISBN-10: 0-618-41538-6 ISBN-13: 978-0-618-41538-0 123456789-CRW-12 11 10 09 08
Page
4
Contents Preface v Acknowledgments viii 0 Representing Numbers 1 Part I Proofs 7 1 Logic and Sets 9 1.1 Statement Forms and Logical Equivalences 9 1.2 Set Notation 23 1.3 Quantifiers 32 1.4 Set Operations and Identities 42 1.5 Valid Arguments 54 Chapter 1 Review Problems 65 2 Basic Proof Writing 69 2.1 Direct Demonstration 69 2.2 General Demonstration (Part 1) 75 2.3 General Demonstration (Part 2) 82 2.4 Indirect Arguments 88 2.5 Splitting into Cases 94 Chapter 2 Review Problems 100 3 Elementary Number Theory 103 3.1 Divisors 103 3.2 Consequences of Well-Ordering 113 3.3 Euclid’s Algorithm and Lemma 130 3.4 Rational Numbers 136 3.5 Irrational Numbers 142 3.6 Modular Arithmetic 150 Chapter 3 Review Problems 162 4 Indexed by Integers 167 4.1 Sequences, Indexing, and Recursion 167 4.2 Sigma Notation 177 4.3 Mathematical Induction, an Introduction 185 4.4 Induction and Summations 195 4.5 Strong Induction 201 4.6 The Binomial Theorem 211 Chapter 4 Review Problems 218 5 Relations 222 5.1 General Relations 222 5.2 Special Relations on Sets 235 5.3 Basics of Functions 250 5.4 Special Functions 261 5.5 General Set Constructions 275 5.6 Cardinality 286 Chapter 5 Review Problems 295 iii
Page
5
iv Contents Part II Combinatorics 301 6 Basic Counting 303 6.1 The Multiplication Principle 303 6.2 Permutations and Combinations 311 6.3 Addition and Subtraction 320 6.4 Probability 328 6.5 Applications of Combinations 341 6.6 Correcting for Overcounting 351 Chapter 6 Review Problems 358 7 More Counting 364 7.1 Inclusion-Exclusion 364 7.2 Multinomial Coefficients 373 7.3 Generating Functions 381 7.4 Counting Orbits 390 7.5 Combinatorial Arguments 403 Chapter 7 Review Problems 411 8 Basic Graph Theory 415 8.1 Motivation and Introduction 415 8.2 Matrices and Special Graphs 429 8.3 Isomorphisms 446 8.4 Invariants 458 8.5 Directed Graphs and Markov Chains 471 Chapter 8 Review Problems 490 9 Graph Properties 497 9.1 Connectivity 497 9.2 Euler Circuits 507 9.3 Hamiltonian Cycles 516 9.4 Planar Graphs 527 9.5 Chromatic Number 538 Chapter 9 Review Problems 552 10 Trees and Algorithms 559 10.1 Trees 559 10.2 Search Trees 574 10.3 Weighted Trees 587 10.4 Analysis of Algorithms (Part 1) 600 10.5 Analysis of Algorithms (Part 2) 611 Chapter 10 Review Problems 621 Appendix A Assumed Properties of Z and R 627 Appendix B Pseudocode 630 Answers to Selected Exercises A1 Bibliography B1 Index I1
Page
6
Preface This book is intended for a one- or two-semester course in discrete mathemat- ics. Such a course is typically taken by mathematics, mathematics education, and computer science majors, usually in their sophomore year. Calculus is not a prerequisite for using this book. Consequently, even freshmen with sufficient maturity could use it. Additionally, the second half of the book can be used for an introductory course in combinatorics and graph theory. The basic organiza- tion of the book can be seen in the Contents. For those designing a one-semester course that covers the core material, the following sections accommodate this approach and make up half of the sections of this book. Sections Topic 1.1–1.5 Logic and Sets 2.1–2.5 Basic Proof Writing 3.1, 3.2 Divisibility, Primes, and Integer Division 4.1–4.4 Sequences, Summations, and Induction 5.1, 5.3, 5.4 Basic Relations and Functions 6.1–6.3 Fundamentals of Counting 8.1–8.4 Fundamentals of Graph Theory 10.1 Trees A two-semester course may most naturally be set to follow Part I and then Part II, each in order. However, there is sufficient flexibility that other organi- zational choices may be made as well. The dependence among the chapters of this book is roughly reflected in the following figure.1 1Note that portions of Chapter 5 are needed in the later chapters. For example, the discussion of bijections in Section 5.4 is needed in Section 8.3 when graph isomorphisms are introduced, and the discussion of logarithms is needed in Section 10.4 when growth rates of functions are compared. v
Page
7
vi Preface 1 3 109 4 6 8 7 5 2 The central topic of Part I of the book is learning how to write proofs. We be- lieve that basic set theory is the best area in which to learn how to write proofs. The connection between properties of sets and the rules of logic (e.g., between De Morgan’s laws for sets and De Morgan’s laws for logic) is so strong that many of the proofs seem to write themselves. This should help students as they learn how to write proofs. After this introduction, we move to number theory, which serves both as a source of interesting applications and as the second set- ting in which to write proofs. This move also sets up the introduction to proofs by induction, presented in Chapter 4. That introduction is spread over three sections to mitigate the difficulties with induction proofs that many students experience. In Part II, the emphasis shifts to computations and problem solving. How- ever, we still call on our ability to prove things and to think logically. For exam- ple, to conclude that a graph has connectivity 3, it is necessary to do two things. First, a disconnecting set of size 3 must be presented. Second, an argument must be given showing that the removal of fewer than three vertices will not discon- nect the graph. The focus of Part II is on combinatorics and graph theory. Chapter 0 is a single section that should take approximately one class to cover. Some users might even skip it or assign it as reading. However, it is in- cluded to emphasize the link between Parts I and II. A conscious effort has been made to give suggestive names to the theorems in this book whenever reasonable, with the common names used whenever possi- ble (e.g., the Rational Roots Theorem and the Binomial Theorem). Consequently, theorems may be referred to by name rather than by an unenlightening number. The names should remind the reader of the content of the theorem and hence re- duce the amount of page flipping. The index gives page references for use when desired. The approximately 3500 exercises throughout this book have been purpose- fully structured. Students are provided a rich supply of straightforward exer- cises before they encounter those that stretch their thinking. Several exercises that are very much like the examples in the text are included. These provide the students with ample opportunity to sharpen their teeth before moving on to bigger prey. Beyond the exercises that reinforce the central concepts, there are many that explore further both the theory and the applications of these concepts. Exercises that may be particularly challenging are marked with a star, .
Page
8
Preface vii Solutions are provided in the back of the book for the odd-numbered exer- cises from each section and all of the exercises from the review sections. Consequently, a balance is sought between the odd and even exercises. That is, each odd-numbered exercise is generally followed by a similar even-numbered exercise. Instructors wanting to assign homework without solution references can assign the even problems. Students can use the odd exercises to help them with the even ones. Note that an answer listed in the back may be more brief than that required by the exercise. In particular, exercises demanding proofs are often answered in the back with sketches. Students are expected to flesh out the answer given to obtain the answer requested. Two appendices containing background material are also provided. In Ap- pendix A, we list the fundamental properties of real numbers and integers that are assumed throughout the book. Appendix B describes the pseudocode in which algorithms are presented throughout the book. Strengths of Discrete Mathematics ■ Range, depth, and quantity of exercises and applications, including additional problems that provide extra challenge, give instructors flexible assignment options. ■ Mathematics is written with rigor and precision. Definitions and theorems are consistently and clearly highlighted. ■ Solid foundation in learning how to write proofs. ■ Engaging writing style makes the presentation especially appealing to students. ■ Hundreds of worked-out examples feature a wide variety of applications to illustrate concepts and enhance understanding. Supplements Online Instructor Resource Guide Available on the Instructor Website through HM MathSPACE®, complete solu- tions are provided to all exercises in the text. The guide also includes a test bank with over 400 test items. Digital Figures and Definitions Available on the Instructor Website through HM MathSPACE, selected figures, definitions, and theorems from the text are provided in convenient PowerPoint® slides. Print Student Solutions Manual Solutions to odd-numbered section exercises and all the review exercises in a printed format. The manual also includes a valuable chapter review and sum- mary of key definitions. Available through your college bookstore.
Page
9
viii Preface Acknowledgments I gratefully acknowledge the following reviewers for their helpful suggestions and comments: Scott Annin, California State University—Fullerton Richard Chang, University of Maryland Baltimore County Ronald Dotzel, University of Missouri—St.Louis William Gasarch, University of Maryland at College Park Premalatha Junius, Mansfield University, Pennsylvania Mark Kannowski, DePauw University, Indiana Matthew Harper Langston, New York University Derek W. Hein, Southern Utah University Roger Lipsett, Newton, Massachusetts Teresa Magnus, Rivier College, New Hampshire Robert Messer, Albion College, Michigan Edward W. Packel, Lake Forest College, Illinois Holly Patterson-McNeil, Lewis-Clark State College Doyt Perry, Muskingum College, Ohio Filip Saidak, Wake Forest University, North Carolina Shirley W. Thompson, Morehouse College, Georgia I have many thanks to give for help that I have received at various stages in the development of this book. I am grateful to Rachel Hykel, the textbook repre- sentative for Houghton Mifflin who enabled me to present my idea for a new discrete mathematics book. Lauren Schultz was my original editor for this book and provided valuable support through the early stages of this project. I would like to thank Bloomsburg University for giving me the opportu- nity to write and use early versions of this book. I am also grateful to my many students who endured early versions of this book and contributed immensely to reducing the number of errors in the current edition. Thanks to copyeditor Connie Day for her excellent and careful work, and to production editor Sara Planck at Matrix Productions. In addition to the many reviewers who provided valuable feedback as this book was being developed, I am grateful to several of my colleagues. Those who made a particular effort to help me with this project include Bill Calhoun, Frank Dangello, Keith Ferland, Jaiwant Mulik, Reza Noubary, Jim Pomfret, and Dan Younger. Additionally, I am forever grateful to my late Ph.D. advisor, L. Gaunce Lewis, for teaching me how to write mathematics. Finally, I would like to thank my family for all of their love and support. They empower me throughout all of my pursuits. Kevin Ferland January 2008
Page
10
C H A P T E R 0 Representing Numbers THROUGHOUT THIS BOOK, we encounter binary sequences, whose terms have only two possible values. In Part I, we consider sequences of Boolean variables; the terms of such sequences can take on either the value True or the value False (briefly T or F). For example, in Part II, sequences of coin flips are considered. There, each coin flip results in either Heads or Tails (briefly H or T). Both of these types of sequences have the same structure as a sequence whose terms are either 1 or 0. Such sequences are used to store data in computers, since a 1 can be represented by the presence of an electrical signal, and a 0 by its absence. In that setting, each term is called a bit, which is short for binary digit. The primary aim of this chapter is to study sequences of 1’s and 0’s and learn how each nonnegative integer can be represented by such a sequence. The key to understanding how integers can be so represented is to recall how numbers are ordinarily written in the decimal system. Decimal (Base Ten) When we see numbers written as 3527 and 60,409, we know their values because we understand them to be represented in a familiar form. The decimal system, or base ten place system, for numbers is taught in elementary school. For exam- ple, in the number 3527, we learn that 7 is the units digit, 2 is the tens digit, 5 is the hundreds digit, and 3 is the thousands digit. That is, 3527 = (3)1000+ (5)100+ (2)10+ (7)1 = (3)103 + (5)102 + (2)101 + (7)100. Similarly, 60409 = (6)104 + (0)103 + (4)102 + (0)101 + (9)100. In the sums above, the exponent on the base ten starts at 0 for the rightmost term and increases by 1 as we move from right to left. In base ten, only the digits 0, 1, . . . , 9 are used. The place system then allows any nonnegative integer value to be specified. The reason why base ten is used is simply that we have ten fingers. However, the method of this numbering system can be used for any base s ≥ 2, where s is an integer. Base s As we will be able to prove in Section 4.5, the system used to represent num- bers in base ten can be generalized to represent numbers in any integer base s ≥ 2. To write integers in base s, digits representing 0, 1, . . . , s − 1 are needed. 1
Page
11
2 C H A P T E R 0 ■ Representing Numbers If s ≤ 10, then the familiar symbols are used (and s, s + 1, . . . , 9 are discarded). If s > 10, then symbols for the values 10, 11, . . . , s− 1 need to be chosen. For example, for s = 16 (the hexadecimal system), the convention is to use the digits 0, 1, . . . , 9, a , b, c, d , e , f . That is, ten is represented by a , eleven is represented by b, and so on. In base s, a nonnegative integer n is represented in the form n = akak−1 · · · a1a0, (in base s) where the digits ak , ak−1, . . . , a1, a0 represent elements from the set {0, 1, . . . , s − 1}. The corresponding value of n is determined by the equation n = aksk + ak−1sk−1 + · · · + a1s1 + a0s0. Our primary focus here is on the base s= 2. That is, we focus on binary numbers. However, some other related and important bases are also explored. Binary (Base Two) For binary numbers, 0 and 1 are the only digits used to represent nonnegative integers. We start by practicing the skill of reading binary numbers. EXAMPLE 0.1 Determine the decimal value of the following binary numbers. (a) 110101. (1)25 + (1)24 + (0)23 + (1)22 + (0)21 + (1)20 = 32+ 16+ 0+ 4+ 0+ 1 = 53 (in base ten) (b) 01101110. (0)27 + (1)26 + (1)25 + (0)24 + (1)23 + (1)22 + (1)21 + (0)20 = 0+ 64+ 32+ 0+ 8+ 4+ 2+ 0 = 110 (in base ten) ■ Note in Example 0.1(b) that the base ten result is 110. When working with multiple bases, it is important to specify the base in which a number is repre- sented. Otherwise, a number like 110 could be mistakenly interpreted as binary. Note also in Example 0.1(b) that the first digit 0 does not contribute to the value of the integer. Only the digits starting from the leftmost nonzero digit contribute to the result. However, sometimes padding a number with zeros to the left to obtain some fixed length is convenient. Table 1 lists the values of all the 3-digit Binary Numbers Base Ten Values 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 Table 1 All 3-Digit Binary Numbers
Page
12
C H A P T E R 0 ■ Representing Numbers 3 binary numbers. There are 8 = 23 binary numbers with 3 digits. In general, there are 2n binary numbers with n digits. Connecting Parts I and II The numerical values of binary sequences provide a natural way to order them. For Boolean sequences, identifying T with 1 and F with 0 gives each sequence a numerical value. Similarly, a sequence of coin flips can be given a numerical value by identifying H with 1 and T with 0. Consequently, this provides a sys- tematic way to list all Boolean sequences and all sequences of coin flips of some fixed length n. Under our identifications, Table 2 lists the possible sequences of length 3 (in increasing order). In Part I of this book, we study problems related to the second column of Table 2. In Part II, we study problems related to the third column of Table 2. The basic notion of binary numbers provides a link between these two considerations. Binary Numbers Boolean Values Coin Flips 000 FFF TTT 001 FFT TTH 010 FTF THT 011 FTT THH 100 TFF HTT 101 TFT HTH 110 TTF HHT 111 TTT HHH Table 2 Binary Sequences of Length 3 Expressing Numbers in Alternative Bases So far we have learned how to convert from binary to decimal, but we should also be aware of how to go in the other direction. For this, there is a simple algo- rithm that involves integer division and the computation of remainders. After we develop sufficient proof-writing skills, in the exercises in Section 4.5, we will be asked to prove the validity of the method we now introduce in Example 0.2. EXAMPLE 0.2 Determine the binary representations of the following numbers given in decimal. (a) 49. To start, we perform a sequence of divisions by 2, in which each resulting quotient is the number divided by 2 in the subsequent step. 49/2= 24 remainder 1 24/2= 12 remainder 0 12/2= 6 remainder 0 6/2= 3 remainder 0 3/2= 1 remainder 1 1/2= 0 remainder 1 The sequence of divisions is terminated when the quotient 0 is obtained. The binary representation is then given by listing the remainders in
Page
13
4 C H A P T E R 0 ■ Representing Numbers reverse order. In this case, the binary representation of 49 is 110001. Note that (1)25 + (1)24 + (0)23 + (0)22 + (0)21 + (1)20 = 25 + 24 + 20 = 49. (b) 72. 72/2= 36 remainder 0 36/2= 18 remainder 0 18/2= 9 remainder 0 9/2= 4 remainder 1 4/2= 2 remainder 0 2/2= 1 remainder 0 1/2= 0 remainder 1 The binary representation of 72 is 1001000. Note that (1)26 + (0)25 + (0)24 + (1)23 + (0)22 + (0)21 + (0)20 = 26 + 23 = 72. ■ Any nonnegative integer can be written in binary by following the procedure from Example 0.2. As we shall further prove in Section 4.5, for any integer s ≥ 2, the base s representation of a number is obtained by a sequence of divisions by s. In the general case, the remainders are values from 0, 1, . . . , s − 1, which are appropriate for base s digits. After the quotient 0 is obtained, the base s representation is given by listing the sequence of remainders in reverse order. Octal (Base Eight) and Hexadecimal (Base Sixteen) Two number systems related to binary are of particular importance in computer science. The octal system represents numbers in base eight, and the hexadecimal system uses base sixteen. By using the appropriate value of the base s, we can determine the values of numbers expressed using these systems just as in any other. EXAMPLE 0.3 The decimal value of the hexadecimal number 3ce0 is found to be 15584. (3)163 + (12)162 + (14)161 + (0)160 = 12288+ 3072+ 224+ 0 = 15584 (in base ten) Recall that c represents twelve and e represents fourteen in hexadecimal. ■ To convert from decimal to these number systems, we use the general pro- cedure described after Example 0.2. EXAMPLE 0.4 Writing the decimal number 93 in octal is accomplished by a sequence of divisions by 8. 93/8= 11 remainder 5 11/8= 1 remainder 3 1/8= 0 remainder 1 Thus 135 is the octal representation of the decimal number 93. ■
Page
14
CHAPTER 0 ■ Representing Numbers 5 The utility of the octal and hexadecimal systems and their connection to the binary system derives from the fact that their bases are powers of two. This makes it particularly easy to convert between binary and either of these systems. For example, since 16 = 24, the hexadecimal digits of a number are obtained by grouping the binary digits into blocks of size 4, starting from the right. EXAMPLE 0.5 The binary number 1110110101 is written in hexadecimal as 3b5. 0011︸︷︷︸ 3 1011︸︷︷︸ b 0101︸︷︷︸ 5 The left-most block is padded to its left with zeros to give it size 4. Since 1011 is the binary representation of eleven, the hexadecimal digit for the middle block is b. ■ The hexadecimal system represents number using fewer digits than the bi- nary system. Since a human can more easily parse 3b5 than 1110110101, when binary data in a computer is printed out for human interpretation, it is often converted to a more readable system such as hexadecimal. Exercises In Exercises 1 through 10, convert the given binary numbers to decimal. 1. 1010 2. 1001 3. 10111 4. 11010 5. 101110 6. 110010 7. 1001011 8. 1011011 9. 10101011 10. 11110000 In Exercises 11 through 20, write in binary the numbers given in decimal. 11. 59 12. 73 13. 84 14. 95 15. 117 16. 230 17. 304 18. 500 19. 1024 20. 4096 21. List all of the possible outcomes from a sequence of 4 coin flips. 22. List all of the possible assignments to a sequence of 4 Boolean variables. Other Bases In Exercises 23 through 28, convert the numbers given in octal to decimal. 23. 163 24. 274 25. 3217 26. 2164 27. 40510 28. 50072 In Exercises 29 through 32, convert the numbers given in hexadecimal to decimal. 29. dc9 30. 2ab 31. 5a7e 32. b63d
Page
15
6 C H A P T E R 0 ■ Representing Numbers In Exercises 33 through 36, write in octal the numbers given in decimal. 33. 59 34. 84 35. 117 36. 230 In Exercises 37 through 42, write in hexadecimal the numbers given in decimal. 37. 59 38. 84 39. 117 40. 230 41. 44252 42. 43962 In Exercises 43 through 46, write the given binary number in (a) octal and (b) hexadecimal. 43. 1100110011. 44. 11100011001. 45. 101100110001011. 46. 11011000001100111. 47. Write the octal number 47 in binary. 48. Write the octal number 162 in binary. 49. Write the hexadecimal number acc in binary. 50. Write the hexadecimal number fda in binary. Questions for Thought 51. What number is expressed in binary by a one followed by m zeros? 52. What number is expressed in binary by m consecutive ones? 53. Describe the binary expression of 4n. 54. How is multiplication by 8 accomplished with a binary number? 55. How can a binary number be tested for divisibility by 4? 56. How can an alternating sum of the digits of a binary number be used to test for divisibility by 3? For example, 1011 has alternating sum −1+ 0− 1+ 1 = −1, and 10101 has alternating sum 1− 0+ 1− 0+ 1 = 3. 57. What number is expressed in octal by m consecutive sevens? 58. What number is expressed in octal by m consecutive ones? 59. How can the sum of the digits of an octal number be used to test for divisibility by 7? 60. How can an alternating sum of the digits of an octal number be used to test for divisibility by 9? 61. How would you convert from octal to hexadecimal without using decimal? 62. If a number written in binary reads the same frontwards and backwards, will this symmetry remain when it is written in hexadecimal? Explain. ∗Exercises that may be particularly challenging are marked with a star.
Page
16
P A R T I Proofs 7
Page
17
This page intentionally left blank
Page
18
C H A P T E R 1 Logic and Sets IN THIS CHAPTER, we lay the conceptual and notational foundation for much of the book, especially Part I. Mathematical reasoning and arguments are based on the rules of logic. Time must be spent learning those rules and eliminating misconceptions that do not follow them. For example, we need to be familiar with the mathematical meaning of the word or, in contrast with the phrase exclusive or, which is sometimes intended in common uses. The notation that needs to be introduced is primarily set notation. This is first presented somewhat informally. It is considered in a more precise way after logic and quantifiers are formally established. However, we do not venture beyond a somewhat naı··ve approach to set theory. Throughout the chapter, we consider some applications. Digital circuit design is our featured application of logic. A discussion of software implementation of sets is also highlighted. 1.1 Statement Forms and Logical Equivalences Our goal in Part I is to learn how to prove statements. However, before we can undertake this, we must study statements and their structure. Consequently, much of our work here involves truth tables and logic identities. As a closely related application, we further consider digital circuits, since their underlying structure is the same as that of statements. DEFINITION 1.1 A statement is a sentence that is either true or false, but not both. It is easy to construct examples of statements. Of course, our primary focus will be on those of a mathematical nature. EXAMPLE 1.1 The following sentences are statements. (a) 2+ 2 = 4. (b) 2+ 2 = 4. (c) √ 4 = 2 and √ 5 > 2. (d) The sine function is periodic and 2π is an integer. (e) 102 > 210 or 210 > 102. 9
Page
19
10 P A R T I ■ Proofs (f) If e > 2, then e2 > 4. (g) √−1 is a real number. ■ In Example 1.1, it turns out that sentences (a), (c), (e), and (f) are true state- ments, while (b), (d), and (g) are false. In some cases, such as (a), the truth or falsehood might be obvious. However, in other cases, such as (f), we see the need to understand various forms that statements might have, such as if-then statements. A study of these forms is taken up immediately after the following example showing that not every sentence is a statement. EXAMPLE 1.2 The following sentences are not statements. (a) What is the sum 2+ 2? (b) Evaluate the sum 2+ 2. (c) This sentence is false. Sentence (a) is a question, and (b) can either be performed or not, but neither can be true or false. The point is that, in particular, a statement must be a declarative sentence. Sentence (c) warrants a bit more thought, since it is a declarative sentence, so the problem must be in assigning it a value of true or false. If (c) were true, then what it says would be false. If (c) were false, then what it says would be true. Hence, (c) can be neither true nor false. ■ Statement Forms We are interested in studying statements. However, insight is gained by step- ping back and examining their forms. In Example 1.1, both (c) and (d) are state- ments of the form “p and q ,” where p and q represent statements. In (c), p = “ √ 4 = 2.” q = “ √ 5 > 2.” In (d), p = “The sine function is periodic.” q = “2π is an integer.” Although statements (c) and (d) are different, their forms are the same. Formally, we say that (c) and (d) both have the statement form p ∧ q . Here, the word and is denoted by the symbol ∧, and p and q are statement vari- ables. The most basic statement forms are listed in Table 1.1. General statement forms, or logical expressions, can be built from these, as we shall see. The def- initions of the basic logical operations ¬, ∧, ∨, and → can be expressed by pre- senting truth tables for the statement forms listed in Table 1.1. A truth table Form Translation ¬p not p (negation of p) p ∧ q p and q p ∨ q p or q p → q if p then q (p implies q ) Table 1.1 Basic Statement Forms
Page
20
C H A P T E R 1 ■ Logic and Sets 11 for a logical expression is a table that displays how the truth or falsehood of the statement variables involved in the expression affect the truth or falsehood of the expression. The truth table defining the operator ¬ is given in Table 1.2. The truth tables for ∧, ∨, and→ are combined in Table 1.3. Notice in Tables 1.2 and 1.3 that if F and T are replaced by 0 and 1, respectively, then the portion of the tables corresponding to the input variables represents binary numbers listed in increasing order. This ordering is not required in truth tables but is used throughout this book for consistency. Variables, such as statement variables, that can only take on one of two possible values (e.g., T or F) are called Boolean variables and are named after the English mathematician George Boole (1815– 1864), who pioneered their use. p ¬ p F T T F Table 1.2 Truth Table Defining ¬ p q p ∧ q p ∨ q p → q F F F F T F T F T T T F F T F T T T T T Table 1.3 Truth Table Defining ∧, ∨, and → We see in Table 1.3 that p ∧ q is true precisely when both p and q are true. Notice that p ∨ q is true if p is true or if q is true, and that it is also true if both p and q are true. In fact, it suffices to say that p ∨ q is false precisely when both p and q are false. The if-then, or conditional, statement form p → q is meant to reflect whether the truth of p implies (or forces) the truth of q . Consequently, p → q is false if and only if p is true and q is false. Notice that p → q is true whenever p is false. In that case, we say that p → q is vacuously true. Only in the other case, when p is true, does the truth of q matter. In logical expressions involving more than one operation, the order of op- erations must be understood. The order of precedence of the basic operations listed from highest to lowest is The operations ∧ and ∨ are listed on the same line because they are considered to be equal in precedence. Of course, any desired order of operations can be forced by using parentheses. For example,¬p∧ q should be understood to mean (¬p) ∧ q and not ¬( p ∧ q ). Remark 1.1 In programming languages such as C++, it is commonly specified that ∧, which is denoted && in C++, has higher precedence than ∨, which is denoted || in C++. Consequently, p && q || r would be interpreted as ( p ∧ q ) ∨ r . However, in applications such as Microsoft Excel, it is impossible to enter an expression of the form p ∧ q ∨ r without explicitly entering it either as ( p ∧ q ) ∨ r or p ∧ (q ∨ r ). The syntax used in Excel is discussed in Example 1.4. That the order of operations matters is illustrated in Example 1.8.