Essentials Of Discrete Mathematics 3rd Ed Pdf

9,304,601冊の本本
84,837,646本の記事記事
ZLibrary ホーム
ホーム

メインページ Essentials of Discrete Mathematics, Third Edition

表紙 Essentials of Discrete Mathematics, Third Edition

Essentials of Discrete Mathematics, Third Edition

David James Hunter

この本はいかがでしたか？

ファイルの質はいかがですか？

質を評価するには、本をダウンロードしてください。

Written for the one-term course, Essentials of Discrete Mathematics, Third Edition is designed to serve computer science and mathematics majors, as well as students from a wide range of other disciplines. The mathematical material is organized around five types of thinking: logical, relational, recursive, quantitative, and analytical. This presentation results in a coherent outline that steadily builds upon mathematical sophistication. Graphs are introduced early and referred to throughout the text, providing a richer context for examples and applications. Algorithms are presented near the end of the text, after students have acquired the skills and experience needed to analyze them. The final chapter emphasizes the multidisciplinary approach and contains case studies that integrate the fields of biology, sociology, linguistics, economics, and music.

New & Key Features: NEW – Student Inquiry Problems, found at the beginning of each section, are designed to introduce and motivate the material in the section that follows NEW – Incorporates new content on Graph Theory - Coverage of algorithms appropriate for computer science majors, as well as students with no previous programming experience - Careful attention to mathematical logic and proof techniques - Instructor resources include an Instructor's Solutions Manual, slides in PowerPoint format, and additional Inquiry Problems

出版社:

Jones & Bartlett Learning

シリーズ:

Jones and Bartlett Publishers Series in Mathematics

1～5分以内にこのファイルをあなたの電子メールにお届けします。

1～5分以内にこのファイルをあなたのKindleにお届けします。

注意！Kindleへ送信するすべての本は、メールによる確認が求められています。Amazon Kindle Supportからメールが送信されますので、メールをご確認ください。

こちらはいかがでしょうか？ Powered by Rec2Me

主要なフレーズ

ESSENTIALS of DISCRETE MATHEMATICS — Third Edition — DAVID J. HUNTER Westmont College World Headquarters Jones & Bartlett Learning 5 Wall Street Burlington, MA 01803 978-443-5000 info@jblearning.com www.jblearning.com Jones & Bartlett Learning books and products are available through most bookstores and online booksellers. To contact Jones & Bartlett Learning directly, call 800-832-0034, fax 978-443-8000, or visit our website, www.jblearning.com. Substantial discounts on bulk quantities of Jones & Bartlett Learning publications are available to corporations, professional associations, and other qualified organizations. For details and specific discount information, contact the special sales department at Jones & Bartlett Learning via the above contact information or send an email to specialsales@jblearning.com. Copyright © 2017 by Jones & Bartlett Learning, LLC, an Ascend Learning Company All rights reserved. No part of the material protected by this copyright may be reproduced or utilized in any form, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without written permission from the copyright owner. The content, statements, views, and opinions herein are the sole expression of the respective authors and not that of Jones & Bartlett Learning, LLC. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not constitute or imply its endorsement or recommendation by Jones & Bartlett Learning, LLC, and such reference shall not be used for advertising or product endorsement purposes. All trademarks displayed are the trademarks of the parties noted herein. Essentials of Discrete Mathematics, Third Edition is an independent publication and has not been authorized, sponsored, or otherwise approved by the owners of the trademarks or service marks referenced in this product. There may be images in this book that feature models; these models do; not necessarily endorse, represent, or participate in the activities represented in the images. Any screenshots in this product are for educational and instructive purposes only. Any individuals and scenarios featured in the case studies throughout this product may be real or fictitious, but are used for instructional purposes only. Production Credits VP, Executive Publisher: David D. Cella Publisher: Cathy L. Esperti Acquisitions Editor: Laura Pagluica Editorial Assistant: Taylor Ferracane Director of Production: Amy Rose Senior Marketing Manager: Andrea DeFronzo VP, Manufacturing and Inventory Control: Therese Connell Composition: Cenveo Publisher Services Cover Design: Kristin E. Parker Rights and Media Research Coordinator: Abigail Reip Cover Image: © David J. Hunter Printing and Binding: Edwards Brothers Malloy Cover Printing: Edwards Brothers Malloy Library of Congress Cataloging-in-Publication Data Hunter, David James, 1968– Essentials of discrete mathematics / David J. Hunter, PhD., Westmont College, Santa Barbara, California. —Third edition. pages ; cm Includes bibliographical references and index. ISBN 978-1-284-05624-2 (casebound) 1. Computer science—Mathematics. I. Title. QA76.9.M35H867 2016 004.01'5113--dc23 2015015506 6048 Printed in the United States of America 19 18 17 16 15 10 9 8 7 6 5 4 3 2 1 Contents Preface How to Use This Book Chapter 1 Logical Thinking 1.1 Formal Logic 1.1.1 Inquiry Problems 1.1.2 Connectives and Propositions 1.1.3 Truth Tables 1.1.4 Logical Equivalences Exercises 1.1 1.2 Propositional Logic 1.2.1 Tautologies and Contradictions 1.2.2 Derivation Rules 1.2.3 Proof Sequences 1.2.4 Forward–Backward Exercises 1.2 1.3 Predicate Logic 1.3.1 Predicates 1.3.2 Quantifiers 1.3.3 Translation 1.3.4 Negation 1.3.5 Two Common Constructions Exercises 1.3 1.4 Logic in Mathematics 1.4.1 The Role of Definitions in Mathematics 1.4.2 Other Types of Mathematical Statements 1.4.3 Counterexamples 1.4.4 Axiomatic Systems Exercises 1.4 1.5 Methods of Proof 1.5.1 Direct Proofs 1.5.2 Proof by Contraposition 1.5.3 Proof by Contradiction Exercises 1.5 Chapter 2 Relational Thinking 2.1 Graphs 2.1.1 Edges and Vertices 2.1.2 Terminology 2.1.3 Modeling Relationships with Graphs Exercises 2.1 2.2 Sets 2.2.1 Membership and Containment 2.2.2 New Sets from Old 2.2.3 Identities Exercises 2.2 2.3 Functions 2.3.1 Definition and Examples 2.3.2 One-to-One and Onto Functions 2.3.3 New Functions from Old Exercises 2.3 2.4 Relations and Equivalences 2.4.1 Definition and Examples 2.4.2 Graphs of Relations 2.4.3 Relations vs. Functions 2.4.4 Equivalence Relations 2.4.5 Modular Arithmetic Exercises 2.4 2.5 Partial Orderings 2.5.1 Definition and Examples 2.5.2 Hasse Diagrams 2.5.3 Topological Sorting 2.5.4 Isomorphisms 2.5.5 Boolean Algebras‡ Exercises 2.5 2.6 Graph Theory 2.6.1 Graphs: Formal Definitions 2.6.2 Isomorphisms of Graphs 2.6.3 Degree Counting 2.6.4 Euler Paths and Circuits 2.6.5 Hamilton Paths and Circuits 2.6.6 Trees Exercises 2.6 Chapter 3 Recursive Thinking 3.1 Recurrence Relations 3.1.1 Definition and Examples 3.1.2 The Fibonacci Sequence 3.1.3 Modeling with Recurrence Relations Exercises 3.1 3.2 Closed-Form Solutions and Induction 3.2.1 Guessing a Closed-Form Solution 3.2.2 Polynomial Sequences: Using Differences‡ 3.2.3 Inductively Verifying a Solution Exercises 3.2 3.3 Recursive Definitions 3.3.1 Definition and Examples 3.3.2 Writing Recursive Definitions 3.3.3 Recursive Geometry 3.3.4 Recursive Jokes Exercises 3.3 3.4 Proof by Induction 3.4.1 The Principle of Induction 3.4.2 Examples 3.4.3 Strong Induction 3.4.4 Structural Induction Exercises 3.4 3.5 Recursive Data Structures 3.5.1 Lists 3.5.2 Efficiency 3.5.3 Binary Search Trees Revisited Exercises 3.5 Chapter 4 Quantitative Thinking 4.1 Basic Counting Techniques 4.1.1 Addition 4.1.2 Multiplication 4.1.3 Mixing Addition and Multiplication Exercises 4.1 4.2 Selections and Arrangements 4.2.1 Permutations: The Arrangement Principle 4.2.2 Combinations: The Selection Principle 4.2.3 The Binomial Theorem‡ Exercises 4.2 4.3 Counting with Functions 4.3.1 One-to-One Correspondences 4.3.2 The Pigeonhole Principle 4.3.3 The Generalized Pigeonhole Principle 4.3.4 Ramsey Theory‡ Exercises 4.3 4.4 Discrete Probability 4.4.1 Definitions and Examples 4.4.2 Applications 4.4.3 Expected Value Exercises 4.4 4.5 Counting Operations in Algorithms 4.5.1 Algorithms 4.5.2 Pseudocode 4.5.3 Sequences of Operations 4.5.4 Loops 4.5.5 Arrays 4.5.6 Sorting Exercises 4.5 4.6 Estimation 4.6.1 Growth of Functions 4.6.2 Estimation Targets 4.6.3 Properties of Big-Θ Exercises 4.6 Chapter 5 Analytical Thinking 5.1 Algorithms 5.1.1 More Pseudocode 5.1.2 Preconditions and Postconditions 5.1.3 Iterative Algorithms 5.1.4 Functions and Recursive Algorithms Exercises 5.1 5.2 Three Common Types of Algorithms 5.2.1 Traversal Algorithms 5.2.2 Greedy Algorithms 5.2.3 Divide-and-Conquer Algorithms Exercises 5.2 5.3 Algorithm Complexity 5.3.1 The Good, the Bad, and the Average 5.3.2 Approximate Complexity Calculations Exercises 5.3 5.4 Bounds on Complexity 5.4.1 Algorithms as Decisions 5.4.2 A Lower Bound 5.4.3 Searching an Array 5.4.4 Sorting 5.4.5 P vs. NP Exercises 5.4 5.5 Program Verification 5.5.1 Verification vs. Testing 5.5.2 Verifying Recursive Algorithms 5.5.3 Searching and Sorting 5.5.4 Towers of Hanoi Exercises 5.5 5.6 Loop Invariants 5.6.1 Verifying Iterative Algorithms 5.6.2 Searching and Sorting 5.6.3 Using Invariants to Design Algorithms Exercises 5.6 Chapter 6 Thinking Through Applications 6.1 Patterns in DNA 6.1.1 Mutations and Phylogenetic Distance 6.1.2 Phylogenetic Trees 6.1.3 UPGMA Exercises 6.1 6.2 Social Networks 6.2.1 Definitions and Terminology 6.2.2 Notions of Equivalence 6.2.3 Hierarchical Clustering 6.2.4 Signed Graphs and Balance Exercises 6.2 6.3 Structure of Languages 6.3.1 Terminology 6.3.2 Finite-State Machines 6.3.3 Recursion 6.3.4 Further Issues in Linguistics Exercises 6.3 6.4 Discrete-Time Population Models 6.4.1 Recursive Models for Population Growth 6.4.2 Fixed Points, Equilibrium, and Chaos 6.4.3 Predator–Prey Systems 6.4.4 The SIR Model Exercises 6.4 6.5 Twelve-Tone Music 6.5.1 Twelve-Tone Composition 6.5.2 Listing All Permutations 6.5.3 Transformations of Tone Rows 6.5.4 Equivalence Classes and Symmetry Exercises 6.5 Hints, Answers, and Solutions to Selected Exercises 1.1 Formal Logic 1.2 Propositional Logic 1.3 1.4 1.5 2.1 Predicate Logic Logic in Mathematics Methods of Proof Graphs 2.2 2.3 2.4 2.5 2.6 3.1 3.2 3.3 3.4 3.5 4.1 4.2 4.3 4.4 4.5 4.6 5.1 5.2 5.3 5.4 5.5 5.6 Sets Functions Relations and Equivalences Partial Orderings Graph Theory Recurrence Relations Closed-Form Solutions and Induction Recursive Definitions Proof by Induction Recursive Data Structures Basic Counting Techniques Selections and Arrangements Counting with Functions Discrete Probability Counting Operations in Algorithms Estimation Algorithms Three Common Types of Algorithms Algorithm Complexity Bounds on Complexity Program Verification Loop Invariants Selected References Index Index of Symbols Preface Introduction Essentials of Discrete Mathematics is designed for first- or second-year computer science and math majors in discrete mathematics courses. This text is also an excellent resource for students in other disciplines. Unlike most other textbooks on the market, Essentials presents the material in a manner that is suitable for a comprehensive and cohesive one-semester course. The text is organized around five types of mathematical thinking: logical, relational, recursive, quantitative, and analytical. To reinforce this approach, graphs are introduced early and referred to throughout the text, providing a richer context for examples and applications. Applications appear throughout the text, and the final chapter explores several uses of discrete mathematical thinking in a variety of disciplines. Case studies from biology, sociology, linguistics, economics, and music can be used as the basis for independent study or undergraduate research projects. Every section has its own set of exercises, which are designed to develop the skills of reading and writing proofs. Synopsis of the Chapters Chapter 1 introduces the reader to Logical Thinking. The chapter explores logic formally (symbolically) and then teaches the student to consider how logic is used in mathematical statements and arguments. The chapter begins with an introduction to formal logic, focusing on the importance of notation and symbols in mathematics, and then explains how formal logic can be applied. The chapter closes with a look at the different ways that proofs are constructed in mathematics. As most mathematical problems contain different objects that are related to each other, Chapter 2 considers Relational Thinking. Finding the relationships among objects often is the first step in solving a mathematical problem. The mathematical structures of sets, relations, functions, and graphs describe these relationships, and thus this chapter focuses on exploring ways to use these structures to model mathematical relationships. Graph theory is introduced early and used throughout the chapter. Chapter 3 describes Recursive Thinking. Many objects in nature have recursive structures: a branch of a tree looks like a smaller tree; an ocean swell has the same shape as the ripples formed by its splashes; an onion holds a smaller onion under its outer layer. Finding similar traits in mathematical objects unleashes a powerful tool. Chapter 3 begins by studying simple recurrence relations and then considers other recursive structures in a variety of contexts. Students also will cover recursive definitions, including how to write their own, and will extend the technique of induction to prove facts about recursively defined objects. Chapter 4 engages the reader in Quantitative Thinking, as many problems in mathematics, computer science, and other disciplines involve counting the elements of a set of objects. The chapter examines the different tools used to count certain types of sets and teaches students to think about problems from a quantitative point of view. After exploring the different enumeration techniques, students will consider applications, including a first look at how to count operations in an algorithm. Chapter 4 also will practice the art of estimation, a valuable skill when precise enumeration is difficult. Chapter 5 explores Analytical Thinking. Many applications of discrete mathematics use algorithms, and thus it is essential to be able to understand and analyze them. This chapter builds on the four foundations of thinking covered in the first four chapters, applying quantitative and relational thinking to the study of algorithm complexity, and then applying logical and recursive thinking to the study of program correctness. Finally, students will study mathematical ways to determine the accuracy and efficiency of algorithms. The final chapter, Thinking Through Applications, examines different ways that discrete mathematical thinking can be applied: patterns in DNA, social networks, the structure of language, population models, and twelve-tone music. What's New in the Third Edition The third edition incorporates several improvements and additions designed to make teaching a course from this text more rewarding and effective. Thanks to helpful feedback from faculty and students, incremental changes in clarity and accuracy have been made, resulting in a more polished product. The early introduction to graph theory has been expanded, allowing deeper integration with later topics such as functions and relations. Perhaps most significantly, each section now opens with a set of inquiry problems designed to motivate the upcoming material. These open-ended problems can be assigned as independent work prior to a class meeting or as group work to engage students in class discussion. Unlike the end-of-section exercises, these inquiry problems often have a variety of plausible answers, prompting students to construct their own notation and conjectures. The instructor's version of the Inquiry Problems supplement contains pedagogical notes on each set of section-opener problems, as well as over 150 additional problems that can be used in a variety of ways. About the Cover The Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … is a famous example of recursion; each number in this sequence is the sum of the two numbers that precede it. The Asteraceae specimen pictured on the front cover of this book exhibits 21:34 Fibonacci phyllotaxis: there are 21 yellow spirals in one direction and 34 in the other. This flower continues the theme of the cover illustrations for the first and second editions of this text: an 8:13 pine cone and a 13:21 Santolina flower, respectively. You can read more about Fibonacci numbers in Section 3.1.2. Supplements • Instructor's Solutions Manual • Lecture slides in PowerPoint format • WebAssign™, developed by instructors for instructors, is a premier independent online teaching and learning environment, guiding several million students through their academic careers since 1997. With WebAssign, instructors can create and distribute algorithmic assignments using questions specific to this textbook. Instructors can also grade, record, and analyze student responses and performance instantly; offer more practice exercises, quizzes, and homework; and upload additional resources to share and communicate with their students seamlessly, such as the lecture slides in PowerPoint format supplied by Jones & Bartlett Learning. • eBook format. As an added convenience, this complete textbook is now available in eBook format for purchase by the student through WebAssign. • Inquiry Problems. Available in both student and instructor versions, this sequence of problems is designed to lead students through the main topics of the book using inquirybased learning. Acknowledgments I would like to thank the following colleagues for their valuable input and suggestions: Dana Dahlstrom; University of California, San Diego Arturo Gonzalez Gutierrez; Universidad Autónoma de Querétaro, Mexico Peter B. Henderson; Butler University Uwe Kaiser; Boise State University Miklos Bona; University of Florida Brian Hopkins; St. Peter's College Frank Ritter; The Pennsylvania State University Bill Marion; Valparaiso University Richard L. Stankewitz; Ball State University C. Ray Rosentrater; Westmont College Susanne Doree; Augsburg College Zachary Kudlak; Mount Saint Mary College Vladimir Akis; California State University, Los Angeles Howard Francis; University of Pikeville Kyle Calderhead; Malone University Caroline Shapcott; Indiana University at South Bend Bonita M. McVey; St. Norbert College Wasim A. Al-Hamdani; Kentucky State University Relja Vulanovic; Kentucky State University Darren A. Narayan; Rochester Institute of Technology Daniel Birmajer; Nazareth College of Rochester Lazaros D. Kikas; University of Detroit Mercy Fereja Mohammed Tahir; Illinois Central College Sven Anderson; Bard College Hemant Pendharkar; Worcester State University Richard Freda; Farmingdale State College David Tannor; Cornerstone University Also, I would like to express my appreciation to the team at Jones & Bartlett Learning. In particular I would like to thank my Acquisitions Editor, Laura Pagluica; Amy Rose, Director of Production; and Taylor Ferracane, Editorial Assistant. Finally, I am deeply thankful to my wife Patti, whose support, patience, and encouragement sustained me throughout this project. David Hunter Westmont College How to Use This Book This book is designed to present a coherent one-semester course in the essentials of discrete mathematics for several different audiences. Figure 1 shows a diagram describing the dependencies among the sections of this book. Regardless of audi- ence, a course should cover the sections labeled "Core" in the diagram: 1.1–1.5, 2.1–2.4, 3.1–3.4, 4.1–4.3, 4.5, and 5.1. Beyond these 18 core sections, instructors have many options for additional sections to include, depending on the audience. A one-semester course should be able to cover approximately 5–8 additional sections. Table 1 shows three possible course outlines, each with a different focus. Figure 1 Dependencies among sections of this book. Computer Science Emphasis Mathematics Emphasis 1.1–1.5 1.1–1.5 Interdisciplinary 1.1–1.5 2.1–2.4 3.1–3.5 4.1–4.6 5.1–5.2 5.3–5.4 and/or 5.5–5.6 2.1–2.6 3.1–3.4 4.1–4.5 5.1 6.3, 6.4, 6.5 2.1–2.4 3.1–3.4 4.1–4.3, 4.5 5.1 6.1–6.5 Table 1 Three possible course outlines. Some subsections in the core (3.2.2, 4.2.3, and 4.3.4) have been marked with a doubledagger symbol (‡) to indicate that these subsections may safely be omitted without disrupting the continuity of the material. Answers and hints to selected problems can be found at the end of the book. Exercises requiring extra effort or insight have been marked with an asterisk (*). At the beginning of each section, you will find some questions labeled "Inquiry." These problems introduce and motivate the material in the section that follows. As such, they can be attempted before the corresponding material is presented in class. Instructors may elect to use these problems in a variety of ways: as group exercises, as independent student investigations, or as the basis for student presentations in class. Often these problems are open ended and can inspire class discussions. The Inquiry Problems supplement to this text contains all of these inquiry problems and many more, and the instructor's version of this supplement includes several notes with additional pedagogical suggestions. Chapter 1 Logical Thinking Mathematicians are in the business of stating things precisely. When you read a mathematical statement, you are meant to take every word seriously; good mathematical language conveys a clear, unambiguous message. In order to read and write mathematics, you must practice the art of logical thinking. The goal of this chapter is to help you communicate mathematically by understanding the basics of logic. Figure 1.1 Symbols are an important part of the language of mathematics. A word of warning: mathematical logic can be difficult—especially the first time you see it. This chapter begins with the study of formal, or symbolic, logic, and then applies this study to the language of mathematics. Expect things to be a bit foggy at first, but eventually (we hope) the fog will clear. When it does, mathematical statements will start making more sense to you. 1.1 Formal Logic Notation is an important part of mathematical language. Mathematicians' chalkboards are often filled with an assortment of strange characters and symbols; such a display can be intimidating to the novice, but there's a good reason for communicating this way. Often the act of reducing a problem to symbolic language helps us see what is really going on. Instead of operating in the fuzzy world of prose, we translate a problem to notation and then perform well-defined symbolic manipulations on that notation. This is the essence of the powerful tool called formalism. In this section, we explore how a formal approach to logic can help us avoid errors in reasoning. A note on terminology: we'll use the word formal to describe a process that relies on manipulating notation. Often people use this word to mean "rigorous," but that's not our intention. A formal argument can be rigorous, but so can an argument that does not rely on symbols. One nice feature of formalism is that it allows you to work without having to think about what all the symbols mean. In this sense, formal logic is really "logical not-thinking." Why is this an advantage? Formal calculations are less prone to error. You are already familiar with this phenomenon: much of the arithmetic you learned in school was formal. You have a welldefined symbolic algorithm for multiplying numbers using pencil and paper, and you can quite effectively multiply three-digit numbers without thinking much about what you are really doing. Of course, formalism is pointless if you don't know what you are doing; at the end of any formal calculation, it is important to be able to interpret the results. 1.1.1 Inquiry Problems The following three inquiry problems are designed to help you begin thinking about the ideas in this section. You should attempt these problems before reading further. Ideally, you should also discuss your answers with your classmates. You will find inquiry problems scattered throughout the text. When you encounter them, keep in mind that they are open-ended problems that will often introduce unfamiliar concepts. To get the most out of these inquiry problems, spend some time thinking about them on your own, write down preliminary solutions, and then share your thoughts, conclusions, and questions with others. Inquiry 1.1 Westley, standing with his hands behind his back, claims that he is holding a quarter in his left hand and a $20 bill in his right hand. You believe he is lying. What would you have to show to demonstrate that he is lying? Invent a diagram, chart, or symbols to illustrate all the possible scenarios. Inquiry 1.2 Buttercup knows whether or not Westley is lying. She promises that if Westley is lying, she will give you a cookie. Buttercup always keeps her promises. Suppose she does not give you a cookie; what can you conclude? Suppose she gives you a cookie; what can you conclude? Illustrate your thinking in some organized way. Inquiry 1.3 Camp Halcyon and Camp Placid are two summer camps with the following daily policies on pool use and cleanup duties. Camp Halcyon's Policy: If you used the pool in the afternoon and you didn't clean up after lunch, then you must clean up after dinner. Camp Placid's Policy: You must do at least one of the following: (a) Stay out of the pool in the afternoon, (b) clean up after lunch, or (c) clean up after dinner. How do these policies differ? Explain your reasoning. 1.1.2 Connectives and Propositions In order to formalize logic, we need a system for translating statements into symbols. We'll start with a precise definition of statement. Definition 1.1 A statement (also known as a proposition) is a declarative sentence that is either true or false, but not both. The following are examples of statements: • 7 is odd. • 1+1=4 • If it is raining, then the ground is wet. • Our professor is from Mars. Note that we don't need to be able to decide whether a statement is true or false in order for it to be a statement. Either our professor is from Mars or our professor is not from Mars, though we may not be sure which is the case. How can a declarative sentence fail to be a statement? There are two main ways. A declarative sentence may contain an unspecified term: x is even. In this case, x is called a free variable. The truth of the sentence depends on the value of x, so if that value is not specified, we can't regard this sentence as a statement. A second type of declarative non-statement can happen when a sentence is self-referential: This sentence is false. We can't decide whether or not the above sentence is true. If we say it is true, then it claims to be false; if we say it is false, then it appears to be true. Often, a complicated statement consists of several simple statements joined together by words such as "and," "or," "if … then," etc. These connecting words are represented by the five logical connectives shown in Table 1.1. Logical connectives are useful for decomposing compound statements into simpler ones, because they highlight important logical properties of a statement. In order to use a formal system for logic, we must be able to translate between a statement in English and its formal counterpart. We do this by assigning letters for simple statements, and then building expressions with connectives. Example 1.1 If p is the statement "you are wearing shoes" and q is the statement "you can't cut your toenails," then represents the statement, "If you are wearing shoes, then you can't cut your toenails." We may choose to express this statement differently in English: "You can't cut your toenails if you are wearing shoes," or "Wearing shoes makes it impossible to cut your toenails." The statement ¬q translates literally as "It is not the case that you can't cut your toenails." Of course, in English, we would prefer to say simply, "You can cut your toenails," but this involves using logic, as we will see in the next section. Name and or not implies (if … then) if and only if Symbol ∧ ∨ ¬ → ↔ Table 1.1 The Five Logical Connectives 1.1.3 Truth Tables We haven't finished setting up our formal system for logic because we haven't been specific about the meaning of the logical connectives. Of course, the names of each connective suggest how they should be used, but in order to make statements with mathematical precision, we need to know exactly what each connective means. Defining the meaning of a mathematical symbol is harder than it might seem. Even the + symbol from ordinary arithmetic is problematic. Although we all have an intuitive understanding of addition—it describes how to combine two quantities—it is hard to express this concept in words without appealing to our intuition. What does "combine" mean, exactly? What are "quantities," really? One simple, but obviously impractical, way to define the + sign would be to list all possible addition problems, as in Table 1.2. Of course, such a table could never end, but it would, in theory, give us a precise definition of the + sign. The situation in logic is easier to handle. Any statement has two possible values: true (T) or false (F). So when we use variables such as p or q for statements in logic, we can think of them as unknowns that can take one of only two values: T or F. This makes it possible to define the meaning of each connective using tables; instead of infinitely many values for numbers x and y, we have only two choices for each variable p and q. We will now stipulate the meaning of each logical connective by listing the T/F values for every possible case. The simplest example is the "not" connective, ¬. If p is true, then ¬p should be false, and vice versa. p ¬p T F F T This table of values is called a truth table; it defines the T/F values for the connective. x y 0 0 x+ y 0 0 1 1 2 1 ⋮ 1 0 1 1 2 ⋮ 1 1 2 3 3 ⋮ Table 1.2 Defining the + sign by listing all possible addition problems would require an infinite table. The "and" and "or" connectives are defined by the following truth tables. Since we have two variables, and each can be either T or F, we need four cases. The definition of the "and" connective ∧ is what you would expect: in order for p ∧ q to be true, p must be true and q must be true. The "or" connective ∨ is a little less obvious. Notice that our definition stipulates that p ∨ q is true whenever p is true, or q is true, or both are true. This can be different from the way "or" is used in everyday speech. When you are offered "soup or salad" in a restaurant, your server isn't expecting you to say "both." The "if and only if" connective says that two statements have exactly the same truth values. Thus, its truth table is as follows. p q T T F F T F T F p↔ q T F F T Sometimes authors will write "iff" as an abbreviation for "if and only if." The "if … then" connective has the least intuitive definition. p q T T F T F T p→q T F T F F T To understand the motivation for this definition, let p → q be the statement of Example 1.1: "If you are wearing shoes, then you can't cut your toenails." In order to demonstrate that this statement is false, you would have to be able to cut your toenails while wearing shoes. In any other situation, you would have to concede that the statement is not false (and if a statement is not false, it must be true). If you are not wearing shoes, then maybe you can cut your toenails or maybe you can't, for some other reason. This doesn't contradict the statement p → q. Put another way, if you live in a world without shoes, then the statement is vacuously true; since you can never actually wear shoes, it isn't false to say that "If you are wearing shoes," then anything is possible. This explains the last two lines of the truth table; if p is false, then p → q is true, no matter what q is. Often, mathematicians use the word "implies" as a synonym for the → connective. "If p then q" means the same thing as "p implies q," namely that q is a necessary consequence of p. Like many words in the English language, "imply" has multiple meanings. Sometimes it means "to indicate or suggest," as in, "She didn't say she wanted to leave, but she implied it." The mathematical usage is stronger, expressing a forced relationship: "x > 3 implies x2 > 3." It is important to recognize when common words have special meanings in mathematical writing; Exercise 32 at the end of this section explores another example, the word "only." 1.1.4 Logical Equivalences Definition 1.2 Two statements are logically equivalent if they have the same T/F values for all cases, that is, if they have the same truth tables. There are some logical equivalences that come up often in mathematics, and also in life in general. Example 1.2 Consider the following theorem from high school geometry. If a quadrilateral has a pair of parallel sides, then it has a pair of supplementary angles.1 This theorem is of the form p → q, where p is the statement that the quadrilateral has a pair of parallel sides, and q is the statement that the quadrilateral has a pair of supplementary angles. We can state a different theorem, represented by ¬q → ¬p. If a quadrilateral does not have a pair of supplementary angles, then it does not have a pair of parallel sides. We know that this second theorem is logically equivalent to the first because the formal statement p → q is logically equivalent to the formal statement ¬q → ¬p, as the following truth table shows. Notice that the column for p → q matches the column for ¬q → ¬p. Since the first theorem is a true theorem from geometry, so is the second. Now consider a different variation on this theorem. If a quadrilateral has a pair of supplementary angles, then it has a pair of parallel sides. This statement is of the form q → p. But the following truth table shows that q → p is not logically equivalent to p → q, because the T/F values are different in the second and third rows. p q T T F F T F T F q→p T T F T In fact, this last statement is not true, in general, in geometry. (Can you draw an example of a quadrilateral for which it fails to be true?) The statement ¬q → ¬p is called the contrapositive of p → q, and the statement q → p is called the converse. The truth tables above prove that, for any statement s, the contrapositive of s is logically equivalent to s, while the converse of s may not be. There are lots of situations where assuming the converse can cause trouble. For example, suppose that the following statement is true. If a company is not participating in illegal accounting practices, then an audit will turn up no evidence of wrongdoing. It is certainly reasonable to assume this, since there couldn't be evidence of wrongdoing if no such wrongdoing exists. However, the converse is probably not true: If an audit turns up no evidence of wrongdoing, then the company is not participating in illegal accounting practices. After all, it is possible that the auditors missed something. At this point you might object that formal logic seems like a lot of trouble to go through just to verify deductions like this last example. This sort of thing is just common sense, right? Well, maybe. But something that appears obvious to you may not be obvious to someone else. Furthermore, our system of formal logic can deal with more complicated situations, where our common sense might fail us. The solution to the next example uses formal logic. Before you look at this solution, try to solve the problem using "common sense." Although the formal approach takes a little time, it resolves any doubt you might have about your own reasoning process. Example 1.3 If Aaron is late, then Bill is late, and, if both Aaron and Bill are late, then class is boring. Suppose that class is not boring. What can you conclude about Aaron? Solution: Let's begin by translating the first sentence into the symbols of logic, using the following statements. Let S be the statement "If Aaron is late, then Bill is late, and, if both Aaron and Bill are late, then class is boring." In symbols, S translates to the following. Now let's construct a truth table for S. We do this by constructing truth tables for the different parts of S, starting inside the parentheses and working our way out. You should check that the last column is the result of "and-ing" the column for p → q with the column for (p ∧ q) → r. We are interested in the possible values of p. It is given that S is true, so we can eliminate rows 2, 3, and 4, the rows where S is false. If we further assume that class is not boring, we can also eliminate the rows where r is true, namely the oddnumbered rows. The rows that remain are the only possible T/F values for p, q, and r: rows 6 and 8. In both of these rows, p is false. In other words, Aaron is not late. ◊ Exercises 1.1 1. Let the following statements be given. (a) Translate the following statement into symbols of formal logic. If the head gasket is blown and there's water in the cylinders, then the car won't start. (b) Translate the following formal statement into everyday English. 2. Let the following statements be given. (a) Translate the following statement into symbols of formal logic. If you are not in South Korea, then you are not in Seoul or Kwangju. (b) Translate the following formal statement into everyday English. 3. Let the following statements be given. (a) Translate the following statement into symbols of formal logic. You can't vote if you are under 18 years old or you are from Mars. (b) Give the contrapositive of this statement in the symbols of formal logic. (c) Give the contrapositive in English. 4. Let s be the following statement. If you are studying hard, then you are staying up late at night. (a) Give the converse of s. (b) Give the contrapositive of s. 5. Let s be the following statement. If it is raining, then the ground is wet. (a) Give the converse of s. (b) Give the contrapositive of s. 6. Give an example of a quadrilateral that shows that the converse of the following statement is false. If a quadrilateral has a pair of parallel sides, then it has a pair of supplementary angles. 7. We say that two ordered pairs (a, b) and (c, d) are equal when a = c and b = d. Let s be the following statement. If (a, b) = (c, d), then a = c. (a) Is this statement true? (b) Write down the converse of s. (c) Is the converse of s true? Explain. 8. Give an example of a true if–then statement whose converse is also true. 9. Show that p ↔ q is logically equivalent to (p → q) ∧ (q → p) using truth tables. 10. Use truth tables to establish the following equivalences. (a) Show that ¬(p ∨ q) is logically equivalent to ¬p ∧ ¬q. (b) Show that ¬(p ∧ q) is logically equivalent to ¬p ∨ ¬q. These equivalences are known as De Morgan's laws, after the nineteenth-century logician Augustus De Morgan. 11. Are the statements ¬(p → q) and ¬p → ¬q logically equivalent? Justify your answer using truth tables. 12. Use truth tables to show that (a ∨ b) ∧ (¬(a ∧ b)) is logically equivalent to a ↔ ¬b. (This arrangement of T/F values is sometimes called the exclusive or of a and b.) 13. Use a truth table to prove that the statement is always true, no matter what p and q are. 14. Let the following statements be given. (a) Use connectives to translate the following statement into formal logic. If Andy is hungry and the refrigerator is empty, then Andy is mad. (b) Construct a truth table for the statement in part (a). (c) Suppose that the statement given in part (a) is true, and suppose also that Andy is not mad and the refrigerator is empty. Is Andy hungry? Explain how to justify your answer using the truth table. 15. Let A be the statement p → (q ∧ ¬r). Let B be the statement q ↔ r. (a) Construct truth tables for A and B. (b) Suppose statements A and B are both true. What can you conclude about statement p? Explain your answer using the truth table. 16. Use truth tables to prove the following distributive properties for propositional logic. (a) p ∧ (q ∨ r) is logically equivalent to (p ∧ q) ∨ (p ∧ r). (b) p ∨ (q ∧ r) is logically equivalent to (p ∨ q) ∧ (p ∨ r). 17. Use truth tables to prove the associative properties for propositional logic. (a) p ∨ (q ∨ r) is logically equivalent to (p ∨ q) ∨ r. (b) p ∧ (q ∧ r) is logically equivalent to (p ∧ q) ∧ r. 18. Mathematicians say that "statement P is stronger than statement Q" if Q is true whenever P is true, but not conversely. (In other words, "P is stronger than Q" means that P → Q is always true, but Q → P is not true, in general.) Use truth tables to show the following. (a) a ∧ b is stronger than a. (b) a is stronger than a ∨ b. (c) a ∧ b is stronger than a ∨ b. (d) b is stronger than a → b. 19. Suppose Q is a quadrilateral. Which statement is stronger? • Q is a square. • Q is a rectangle. Explain. 20. Which statement is stronger? • Manchester United is the best football team in England. • Manchester United is the best football team in Europe. Explain. 21. Which statement is stronger? • n is divisible by 3. • n is divisible by 12. Explain. 22. Mathematicians say that "Statement P is a sufficient condition for statement Q" if P → Q is true. In other words, in order to know that Q is true, it is sufficient to know that P is true. Let x be an integer. Give a sufficient condition on x for x/2 to be an even integer. 23. Mathematicians say that "Statement P is a necessary condition for statement Q" if Q → P is true. In other words, in order for Q to be true, P must be true. Let n ≥ 1 be a natural number. Give a necessary but not sufficient condition on n for n + 2 to be prime. 24. Let Q be a quadrilateral. Give a sufficient but not necessary condition for Q to be a parallelogram. 25. Write the statement "P is necessary and sufficient for Q" in the symbols of formal logic, using as few connectives as possible. 26. Often a complicated expression in formal logic can be simplified. For example, consider the statement S = (p ∧ q) ∨ (p ∧ ¬q). (a) Construct a truth table for S. (b) Find a simpler expression that is logically equivalent to S. 27. Consider the statement S = [¬(p → q)] ∨ [¬(p ∨ q)]. (a) Construct a truth table for S. (b) Find a simpler expression that is logically equivalent to S. 28. The NAND connective ↑ is defined by the following truth table. p q T T F F T F T F p↑q F T T T Use truth tables to show that p ↑ q is logically equivalent to ¬(p ∧ q). (This explains the name NAND: Not AND.) 29. The NAND connective is important because it is easy to build an electronic circuit that computes the NAND of two signals (see Figure 1.2). Such a circuit is called a logic gate. Moreover, it is possible to build logic gates for the other logical connectives entirely out of NAND gates. Prove this fact by proving the following equivalences, using truth tables. (a) (p ↑ q) ↑ (p ↑ q) is logically equivalent to p ∧ q. (b) (p ↑ p) ↑ (q ↑ q) is logically equivalent to p ∨ q. (c) p ↑ (q ↑ q) is logically equivalent to p → q. Figure 1.2 A NAND gate can be built with just two transistors. 30. Write ¬p in terms of p and ↑. 31. A technician suspects that one or more of the processors in a distributed system is not working properly. The processors, A, B, and C, are all capable of reporting information about the status (working or not working) of the processors in the system. The technician is unsure whether a processor is really not working, or whether the problem is in the status reporting routines in one or more of the processors. After polling each processor, the technician receives the following status reports. • Processor A reports that processor B is not working and processor C is working. • Processor B reports that A is working if and only if B is working. • Processor C reports that at least one of the other two processors is not working. Help the technician by answering the following questions. (a) Let a = "A is working," b = "B is working," and c = "C is working." Write the three status reports in terms of a, b, and c, using the symbols of formal logic. (b) Complete the following truth table. (c) Assuming that all of the status reports are true, which processor(s) is/are working? (d) Assuming that all of the processors are working, which status report(s) is/are false? (e) Assuming that a processor's status report is true if and only if the processor is working, what is the status of each processor? 32. Use the symbols of propositional logic to explain the difference between the following two statements. My team will win if I yell at the TV. My team will win only if I yell at the TV. Look up the word "only" in a dictionary. This word has several different meanings. Which meaning applies when we use the phrase "if and only if" in logic? 1.2 Propositional Logic After working through the exercises of the previous section, you may have noticed a serious limitation of the truth table approach. Each time you add a new statement to a truth table, you must double the number of rows. This makes truth table analysis unwieldy for all but the simplest examples. In this section we will develop a system of rules for manipulating formulas in symbolic logic. This system, called the propositional calculus, will allow us to make logical deductions formally. There are at least three reasons for doing this. 1. These formal methods are useful for analyzing complex logical problems, especially where truth tables are impractical. 2. The derivation rules we will study are commonly used in mathematical discourse. 3. The system of derivation rules and proof sequences is a simple example of mathematical proof. Of these three, the last is the most important. The mechanical process of writing proof sequences in propositional calculus will prepare us for writing more complicated proofs in other areas of mathematics. 1.2.1 Tautologies and Contradictions Inquiry 1.4 Explain how the answers to the following two questions are related. If you pass all the exams, will you pass the course? Is it possible to pass all the exams and fail the course? Inquiry 1.5 Consider the following statement. If you have a ticket, then, as long as you are wearing a shirt, you may enter the theater, unless you aren't wearing shoes. Write a simpler statement that expresses the same policy. Explain how you know that your statement is equivalent. Inquiry 1.6 Suppose that a natural number n is gaunt if it satisfies the following condition. If n is even, then 10 divides n, and, if n is odd, then 5 divides n. List the first 6 gaunt numbers. Is there a simpler way to define the condition of "gauntness"? There are some statements in formal logic that are always true, no matter what the T/F values of the component statements are. For example, the truth table for (p ∧ q) → p is as follows. Such a statement is called a tautology, and we write to indicate this fact. The notation A ⇒ B means that the statement A → B is true in all cases; in other words, the truth table for A → B is all T's. Similarly, the ⇔ symbol denotes a tautology containing the ↔ connective. Example 1.4 In Exercise 1.1.10 you proved the following tautologies. (a) ¬(p ∨ q) ⇔ ¬p ∧ ¬q (b) ¬(p ∧ q) ⇔ ¬p ∨ ¬q When a tautology is of the form (C ∧ D) ⇒ E, we often prefer to write instead. This notation highlights the fact that if you know both C and D, then you can conclude E. The use of the ∧ connective is implicit. Example 1.5 Use a truth table to prove the following. Solution: Let S be the statement [p ∧ (p → q)] → q. We construct our truth table by building up the parts of S, working from inside the parentheses outward. Since the column for S is all T's, this proves that S is a tautology. ◊ The tautology in Example 1.5 is known as modus ponens, which is Latin for "affirmative mode." This concept goes back at least as far as the Stoic philosophers of ancient Greece, who stated it as follows. If the first, then the second; but the first; therefore the second. In the exercises, you will have the opportunity to prove a related result called modus tollens ("denial mode"). In the symbols of logic, this tautology is as follows. There are also statements in formal logic that are never true. A statement whose truth table contains all F's is called a contradiction. Example 1.6 Use a truth table to show that p ∧ ¬p is a contradiction. Solution: p ¬p T F F T p∧ ¬p F F In other words, a statement and its negation can never both be true. ◊ A statement in propositional logic that is neither a tautology nor a contradiction is called a contingency. A contingency has both T's and F's in its truth table, so its truth is "contingent" on the T/F values of its component statements. For example, p ∧ q, p ∨ q, and p → q are all contingencies. 1.2.2 Derivation Rules Tautologies are important because they show how one statement may be logically deduced from another. For example, suppose we know that the following statements are true. Our professor does not own a spaceship. If our professor is from Mars, then our professor owns a spaceship. We can apply the modus tollens tautology to deduce that "Our professor is not from Mars." This is a valid argument, or derivation, that allows us to conclude this last statement given the first two. Every tautology can be used as a rule to justify deriving a new statement from an old one. There are two types of derivation rules: equivalence rules and inference rules. Equivalence rules describe logical equivalences, while inference rules describe when a weaker statement can be deduced from a stronger statement. The equivalence rules given in Table 1.3 could all be checked using truth tables. If A and B are statements (possibly composed of many other statements joined by connectives), then the tautology A ⇔ B is another way of saying that A and B are logically equivalent.2 Equivalence p ⇔ ¬¬p p → q ⇔ ¬p ∨ q ¬(p ∧ q) ⇔ ¬p ∨ ¬q ¬(p ∨ q) ⇔ ¬p ∧ ¬q p∨q⇔q∨p p∧q⇔q∧p p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r Name double negation implication De Morgan's laws commutativity associativity Table 1.3 Equivalence Rules An equivalence rule of the form A ⇔ B can do three things: 1. Given A, deduce B. 2. Given B, deduce A. 3. Given a statement containing statement A, deduce the same statement, but with statement A replaced by statement B. The third option is a form of substitution. For example, given the following statement, If Micah is not sick and Micah is not tired, then Micah can play. we can deduce the following using De Morgan's laws. If it is not the case that Micah is sick or tired, then Micah can play. In addition to equivalence rules, there are also inference rules for propositional logic. Unlike equivalence rules, inference rules work in only one direction. An inference rule of the form A ⇒ B allows you to do only one thing: 1. Given A, deduce B. Inference Name conjunction modus ponens modus tollens p∧q⇒p p⇒q∨q simplification addition Table 1.4 Inference Rules In other words, you can conclude a weaker statement, B, if you have already established a stronger statement, A. For example, modus tollens is an inference rule: the weaker statement B: Our professor is not from Mars. follows from the stronger statement A: Our professor does not own a spaceship, and if our professor is from Mars, then our professor owns a spaceship. If A is true, then B must be true, but not vice versa. (Our professor might own a spaceship and be from Jupiter, for instance.) Table 1.4 lists some useful inference rules, all of which can be verified using truth tables. 1.2.3 Proof Sequences We now have enough tools to derive some new tautologies from old ones. A proof sequence is a sequence of statements and reasons to justify an assertion of the form A ⇒ C. The first statement, A, is given.3 The proof sequence can then list statements B1, B2, B3, …, etc., as long as each new statement can be derived from a previous statement (or statements) using some derivation rule. Of course, this sequence of statements must culminate in C, the statement we are trying to prove, given A. Example 1.7 Write a proof sequence for the assertion Solution: Statements 1. p 2. p → q 3. q → r 4. q 5. r Reasons given given given modus ponens, 1, 2 modus ponens, 4, 3 ◊ Every time we prove something, we get a new inference rule. The rules in Table 1.4 are enough to get us started, but we should feel free to use proven assertions in future proofs. For example, the assertion proved in Example 1.7 illustrates the transitive property of the → connective. Another thing to notice about Example 1.7 is that it was pretty easy—we just had to apply modus ponens twice. Compare this to the truth table approach: the truth table for would consist of eight rows and several columns. Truth tables are easier to do, but they can be much more tedious. Proof sequences should remind you of the types of proofs you did in high school geometry. The rules are simple: start with the given, see what you can deduce, end with what you are trying to prove. Here's a harder example. Example 1.8 Prove: Solution: Statements 1. p ∨ q 2. ¬p Reasons given given 3. ¬(¬p) ∨ q 4. ¬p → q 5. q double negation, 1 implication, 3 modus ponens, 4, 2 ◊ Notice that in step 3 of this proof, we used one of the equivalence rules (double negation) to make a substitution in the formula. This is allowed: since ¬(¬p) is logically equivalent to p, it can take the place of p in any formula. 1.2.4 Forward–Backward If you are having trouble coming up with a proof sequence, try the ''forward–backward" approach: consider statements that are one step forward from the given, and also statements that are one step backward from the statement you are trying to prove. Repeat this process, forging a path of deductions forward from the given and backward from the final statement. If all goes well, you will discover a way to make these paths meet in the middle. The next example illustrates this technique. Example 1.9 In Section 1.1, we used truth tables to show that a statement is logically equivalent to its contrapositive. In this example we will construct a proof sequence for one direction of this logical equivalence: Solution: We apply the forward–backward approach. The only given statement is p → q, so we search our derivation rules for something that follows from this statement. The only candidate is ¬p ∨ q, by the implication rule, so we tentatively use this as the second step of the proof sequence. Now we consider the statement we are trying to prove, ¬q → ¬p, and we look backward for a statement from which this statement follows. Since implication is an equivalence rule, we can also use it to move backward to the statement ¬(¬q) ∨ ¬p, which we propose as the second-to-last statement of our proof. By moving forward one step from the given and backward one step from the goal, we have reduced the task of proving to the (hopefully) simpler task of proving Now it is fairly easy to see how to finish the proof: we can switch the ∨ statement around using commutativity and simplify using double negation. We can now write down the proof sequence. Statements 1. p → q 2. ¬p ∨ q Reasons given implication 3. q ∨ ¬p 4. ¬(¬q) ∨ ¬p 5. ¬q → ¬p commutativity double negation implication We used the forward–backward approach to move forward from step 1 to step 2, and again to move backward from step 5 to step 4. Then we connected step 2 to step 4 with a simple proof sequence. ◊ You may have noticed that in Section 1.1, we proved the stronger statement using truth tables; the above example proves only the "⇒" direction of this equivalence. To prove the other direction, we need another proof sequence. However, in this case, this other proof sequence is easy to write down, because all of the derivation rules we used were reversible. Implication, commutativity, and double negation are all equivalence rules, so we could write down a new proof sequence with the order of the steps reversed, and we would have a valid proof of the "⇐" direction. Exercises 1.2 1. Use truth tables to establish the modus tollens tautology: 2. Fill in the reasons in the following proof sequence. Make sure you indicate which step(s) each derivation rule refers to. Statements Reasons 1. q ∧ r given 2. ¬(¬p ∧ q) given 3. ¬¬p ∨ ¬q 4. p ∨ ¬q 5. ¬q ∨ p 6. q → p 7. q 8. p 3. Fill in the reasons in the following proof sequence. Make sure you indicate which step(s) each derivation rule refers to. Statements Reasons 1. (p ∧ q)→ r given 2. ¬(p ∧ q) ∨ r 3. (¬p ∨ ¬q) ∨ r 4. ¬p ∨ (¬q ∨ r) 5. p→(¬q ∨ r) 4. Is the proof in Exercise 2 reversible? Why or why not? 5. Is the proof in Exercise 3 reversible? Why or why not? 6. Fill in the reasons in the following proof sequence. Make sure you indicate which step(s) each derivation rule refers to. Statements Reasons 1. p ∧ (q ∨ r) given 2. ¬(p ∧ q) given 3. ¬p ∨ ¬q 4. ¬q ∨ ¬p 5. q →¬p 6. p 7. ¬(¬p) 8. ¬q 9. (q ∨ r) ∧ p 10. q ∨ r 11. r ∨ q 12. ¬(¬r) ∨ q 13. ¬r →q 14. ¬(¬r) 15. r 16. p ∧ r 7. Justify each conclusion with a derivation rule. (a) If Joe is artistic, he must also be creative. Joe is not creative. Therefore, Joe is not artistic. (b) Lingli is both athletic and intelligent. Therefore, Lingli is athletic. (c) If Monique is 18 years old, then she may vote. Monique is 18 years old. Therefore, Monique may vote. (d) Marianne has never been north of Saskatoon or south of Santo Domingo. In other words, she has never been north of Saskatoon and she has never been south of Santo Domingo. 8. Which derivation rule justifies the following argument? If n is a multiple of 4, then n is even. However, n is not even. Therefore, n is not a multiple of 4. 9. Let x and y be integers. Given the statement x > y or x is odd. what statement follows by the implication rule? 10. Let Q be a quadrilateral. Given the statements If Q is a rhombus, then Q is a parallelogram. Q is not a parallelogram. what statement follows by modus tollens? 11. Let x and y be numbers. Simplify the following statement using De Morgan's laws and double negation. It is not the case that x is not greater than 3 and y is not found. 12. Write a statement that follows from the statement It is sunny and warm today. by the simplification rule. 13. Write a statement that follows from the statement This soup tastes funny. by the addition rule. 14. Recall Exercise 31 of Section 1.1. Suppose that all of the following status reports are correct: • Processor B is not working and processor C is working. • Processor A is working if and only if processor B is working. • At least one of the two processors A and B is not working. Let a = "A is working," b = "B is working," and c = "C is working." (a) If you haven't already done so, write each status report in terms of a, b, and c, using the symbols of formal logic. (b) How would you justify the conclusion that B is not working? (In other words, given the statements in part (a), which derivation rule allows you to conclude ¬b?) (c) How would you justify the conclusion that C is working? (d) Write a proof sequence to conclude that A is not working. (In other words, given the statements in part (a), write a proof sequence to conclude ¬a.) 15. Write a proof sequence for the following assertion. Justify each step. 16. Write a proof sequence for the following assertion. Justify each step. 17. Write a proof sequence for the following assertion. Justify each step. 18. Write a proof sequence for the following assertion. Justify one of the steps in your proof using the result of Example 1.8. 19. Write a proof sequence to establish that p ⇔ p ∧ p is a tautology. 20. Write a proof sequence to establish that p ⇔ p ∨ p is a tautology. (Hint: Use De Morgan's laws and Exercise 19.) 21. Write a proof sequence for the following assertion. Justify each step. 22. Write a proof sequence for the following assertion. Justify each step. 23. Consider the following assertion. (a) Find a statement that is one step forward from the given. (b) Find a statement that is one step backward from the goal. (Use the addition rule—in reverse—to find a statement from which the goal will follow.) (c) Give a proof sequence for the assertion. (d) Is your proof reversible? Why or why not? 24. Use a truth table to show that is not a tautology. (This example shows that substitution isn't valid for inference rules, in general. Substituting the weaker statement, q, for the stronger statement, p, in the expression "¬p" doesn't work.) 25. (a) Fill in the reasons in the following proof sequence. Make sure you indicate which step(s) each derivation rule refers to. Statements Reasons 1. p →(q → r) given 2. ¬p ∨ (q → r) 3. ¬p ∨ (¬q ∨ r) 4. (¬p ∨ ¬q) ∨ r 5. ¬(p ∧ q) ∨ r 6. (p ∧ q)→ r (b) Explain why the proof in part (a) is reversible. (c) The proof in part (a) (along with its reverse) establishes the following tautology: Therefore, to prove an assertion of the form A ⇒ B → C, it is sufficient to prove instead. Use this fact to rewrite the tautology as a tautology of the form where C does not contain the → connective. (The process of rewriting a tautology this way is called the deduction method.) (d) Give a proof sequence for the rewritten tautology in part (c). 26. This exercise will lead you through a proof of the distributive property of ∧ over ∨. We will prove: (a) The above assertion is the same as the following: Why? (b) Use the deduction method from Exercise 25(c) to rewrite the tautology from part (a). (c) Prove your rewritten tautology. 27. Use a truth table to show that (a → b) ∧ (a ∧ ¬b) is a contradiction. 28. Is a → ¬a a contradiction? Why or why not? 1.3 Predicate Logic When we defined statements, we said that a sentence of the form is not a statement, because its T/F value depends on x. Mathematical writing, however, almost always deals with sentences of this type; we often express mathematical ideas in terms of some unknown variable. This section explains how to extend our formal system of logic to deal with this situation. Inquiry 1.7 The diagram below shows a standard brick pattern (a "running bond" pattern) composed of two different colors of bricks. The bricklayer had certain rules in mind governing the arrangement of the colors. Devise some possible rules, written as logical statements. Your statements should be as specific as possible, but should also hold true for every brick in the pattern. Inquiry 1.8 Nikola bets you $5 that every player on his basketball team will score a point or earn an assist in tonight's game. What must happen for you to win the bet? Express this condition in the simplest, most natural way possible, and explain your reasoning. Inquiry 1.9 For each of the following statements, give a list of natural numbers that satisfies the statement. Can you find a single list that satisfies both statements? Statement p: There is a number in the list that is greater than every other number in the list. Statement q: Every number in the list is less than some other number in the list. 1.3.1 Predicates Definition 1.3 A predicate is a declarative sentence whose T/F value depends on one or more variables. In other words, a predicate is a declarative sentence with variables, and after those variables have been given specific values the sentence becomes a statement. We use function notation to denote predicates. For example, are predicates. The statement P(8) is true, while the statement is false. Implicit in a predicate is the domain (or universe) of values that the variable(s) can take. For P(x), the domain could be the integers; for Q(x, y), the domain could be some collection of physical objects. We will usually state the domain along with the predicate, unless it is clear from the context. Equations are predicates. For example, if E(x) stands for the equation then E(3) is true and E(4) is false. We regard equations as declarative sentences, where the = sign plays the role of a verb. 1.3.2 Quantifiers By themselves, predicates aren't statements because they contain free variables. We can make them into statements by plugging in specific values of the domain, but often we would like to describe a range of values for the variables in a predicate. A quantifier modifies a predicate by describing whether some or all elements of the domain satisfy the predicate. We will need only two quantifiers: universal and existential. The universal quantifier "for all" is denoted by ∀. So the statement says that P(x) is true for all x in the domain. The existential quantifier "there exists" is denoted by ∃. The statement says that there exists an element x of the domain such that P(x) is true; in other words, P(x) is true for some x in the domain. For example, if E(x) is the real number equation x2 − x − 6 = 0, then the expression says, "There is some real number x such that x2 − x − 6 = 0," or more simply, "The equation x2 − x − 6 = 0 has a solution." The variable x is no longer a free variable, since the ∃ quantifier changes the role it plays in the sentence. If Z(x) represents the real number equation x · 0 = 0, the expression means "For all real numbers x, x · 0 = 0." Again, this is a sentence without free variables, since the range of possible values for x is clearly specified. When we put a quantifier in front of a predicate, we form a quantified statement. Since the quantifier restricts the range of values for the variables in the predicate, the quantified statement is either true or false (but not both). In the above examples, (∃x)E(x) and (∀x)Z(x) are both true, while the statement is false, since there are some real numbers that do not satisfy the equation x2 − x − 6 = 0. The real power of predicate logic comes from combining quantifiers, predicates, and the symbols of propositional logic. For example, if we would like to claim that there is a negative number that satisfies the equation x2 − x − 6 = 0, we could define a new predicate Then the statement translates as "There exists some real number x such that x is negative and x2 − x − 6 = 0." The scope of a quantifier is the part of the formula to which the quantifier refers. In a complicated formula in predicate logic, it is important to use parentheses to indicate the scope of each quantifier. In general, the scope is what lies inside the set of parentheses right after the quantifier: In the statement (∃x)(N(x) ∧ E(x)), the scope of the ∃ quantifier is the expression N(x) ∧ E(x). 1.3.3 Translation There are lots of different ways to write quantified statements in English. Translating back and forth between English statements and predicate logic is a skill that takes practice. Example 1.10 Using all cars as a domain, if then the statement (∀x)(Q(x) → ¬P(x)) could be translated very literally as "For all cars x, if x is large, then x does not get good mileage." However, a more natural translation of the same statement is "All large cars get bad mileage." or "There aren't any large cars that get good mileage." If we wanted to say the opposite—that is, that there are some large cars that get good mileage—we could write the following. We'll give a formal proof that this negation is correct in Example 1.13. The next example shows how a seemingly simple mathematical statement yields a rather complicated formula in predicate logic. The careful use of predicates can help reveal the logical structure of a mathematical claim. Example 1.11 In the domain of all integers, let P(x) = "x is even." We can express the fact that the sum of an even number with an odd number is odd as follows. Of course, the literal translation of this quantified statement is "For all integers x and for all integers y, if x is even and y is not even, then x + y is not even," but we normally say something informal like "An even plus an odd is odd." This last example used two universal quantifiers to express a fact about an arbitrary pair x, y of integers. The next example shows what can happen when you combine universal and existential quantifiers in the same statement. Example 1.12 In the domain of all real numbers, let G(x, y) be the predicate "x > y." The statement says literally that "For all numbers y, there exists some number x such that x > y," or more simply, "Given any number y, there is some number that is greater than y." This statement is clearly true: the number y + 1 is always greater than y, for example. However, the statement translates literally as "There exists a number x such that, for all numbers y, x > y." In simpler language, this statement says, "There is some number that is greater than any other number." This statement is clearly false, because there is no largest number. The order of the quantifiers matters. In both of these statements, a claim is made that x is greater than y. In the first statement, you are first given an arbitrary number y, then the claim is that it is possible to find some x that is greater than it. However, the second statement claims there is some number x, such that, given any other y, x will be the greater number. In the second statement, you must decide on what x is before you pick y. In the first statement, you pick y first, then you can decide on x. 1.3.4 Negation The most important thing you need to be able to do with predicate logic is to write down the negation of a quantified statement. As with propositional logic, there are some formal equivalences that describe how negation works. Table 1.5 lists two important rules for forming the opposite of a quantified statement. It is easy to see the formal pattern of these two rules: to negate a quantified statement, bring the negation inside the quantifier, and switch the quantifier. Let's interpret the negation rules in the context of an example. In the domain of all people, let L(x) stand for "x is a liar." The universal negation rule says that the negation of "All people are liars" is "There exists a person who is not a liar." In symbols, Equivalence Name ¬[(∀x)P(x)] ⇔ (∃x)(¬P(x)) universal negation ¬[(∃x)P(x)] ⇔ (∀x)(¬P(x)) existential negation Table 1.5 Negation rules for predicate logic. Similarly, the existential negation rule says that the negation of "There exists a liar" is "There are no liars." Example 1.13 In Example 1.10, we discussed what the negation of the statement "All large cars get bad mileage." should be. We can answer this question by negating the formal statement using a proof sequence. We'll suppose as given the negation of statement 1.3.1, and deduce an equivalent statement. Statements 1. ¬[(∀x)(Q(x) →¬P(x))] 2. (∃x)¬(Q(x)→¬P(x)) 3. (∃x)¬(¬Q(x) ∨ ¬P(x)) 4. (∃x)(¬(¬Q(x)) ∧ ¬(¬P(x))) 5. (∃x)(Q(x) ∧ P(x)) 6. (∃x)(P(x) ∧ Q(x)) Reasons given universal negation implication De Morgan's law double negation commutativity Notice that the result of our formal argument agrees with the intuitive negation we did in Example 1.10: There exists some car that is both large and gets good mileage. Example 1.14 Let the domain be all faces of the following truncated icosahedron (also known as a soccer ball). Consider the following predicates: Here we say that two polygons border each other if they share an edge. We also stipulate that a polygon cannot border itself. Confirm that the following observations are true for any truncated icosahedron. 1. No two pentagons border each other. 2. Every pentagon borders some hexagon. 3. Every hexagon borders another hexagon. Write these statements in predicate logic, and negate them. Simplify the negated statements so that no quantifier or connective lies within the scope of a negation. Translate your negated statement back into English. Solution: The formalizations of these statements are as follows. 1. (∀x)(∀y)((P(x) ∧ P(y)) → ¬B(x, y)) 2. (∀x)(P(x) → (∃y)(H(y) ∧ B(x, y))) 3. (∀x)(H(x) → (∃y)(H(y) ∧ B(x, y))) We'll negate (2), and leave the others as exercises. See if you can figure out the reasons for each equivalence. This last statement says that there exists an x such that x is a pentagon and, for any y, if y is a hexagon, then x does not border y. In other words, there is some pentagon that borders no hexagon. If you found a solid with this property, it couldn't be a truncated icosahedron. ◊ 1.3.5 Two Common Constructions There are two expressions that come up often, and knowing the predicate logic for these expressions makes translation much easier. The first is the statement All 〈blanks〉 are 〈something〉. For example, "All baseball players are rich," or "All oysters taste funny." In general, if P(x) and Q(x) are the predicates "x is 〈blank〉" and "x is 〈something〉," respectively, then the predicate logic expression translates as "For all x, if x is 〈blank〉, then x is 〈something〉." Put more simply, "All x's with property 〈blank〉 must have property 〈something〉," or even simpler, "All 〈blanks〉 are 〈something〉." In the domain of all people, if R(x) stands for "x is rich" and B(x) stands for "x is a baseball player," then is the statement "All baseball players are rich." The second construction is of the form There is a 〈blank〉 that is 〈something〉. For example, "There is a rich baseball player," or "There is a funny-tasting oyster." This expression has the following form in predicate logic. Note that this translates literally as "There is some x such that x is 〈blank〉 and x is 〈something〉," which is what we want. In the domain of shellfish, if O(x) is the predicate "x is an oyster" and F(x) is the predicate "x tastes funny," then would translate as "There is a funny-tasting oyster." Note that you could also say "There is an oyster that tastes funny," "Some oysters taste funny," or, more awkwardly, "There is a funnytasting shellfish that is an oyster." These statements all mean the same thing. Exercises 1.3 1. In the domain of integers, let P(x, y) be the predicate "x · y = 12." Tell whether each of the following statements is true or false. (a) P(3, 4) (b) P(3, 5) (c) P(2, 6) ∨ P(3, 7) (d) (∀x)(∀y)(P(x, y) → P(y, x)) (e) (∀x)(∃y)P(x, y) 2. In the domain of all penguins, let D(x) be the predicate "x is dangerous." Translate the following quantified statements into simple, everyday English. (a) (∀x)D(x) (b) (∃x)D(x) (c) ¬(∃x)D(x) (d) (∃x)¬D(x) 3. In the domain of all movies, let V(x) be the predicate "x is violent." Write the following statements in the symbols of predicate logic. (a) Some movies are violent. (b) Some movies are not violent. (c) No movies are violent. (d) All movies are violent. 4. Let the following predicates be given. The domain is all mammals. Translate the following statements into predicate logic. (a) All lions are fuzzy. (b) Some lions are fuzzy. 5. In the domain of all books, consider the following predicates. Translate the following statements in predicate logic into ordinary English. (a) (∀x)(H(x) → C(x)) (b) (∃x)(C(x) ∧ H(x)) (c) (∀x)(C(x) ∨ H(x)) (d) (∃x)(H(x) ∧ ¬C(x)) 6. The domain of the following predicates is the set of all plants. Translate the following statements into predicate logic. (a) Some plants are poisonous. (b) Jeff has never eaten a poisonous plant. (c) There are some nonpoisonous plants that Jeff has never eaten. 7. In the domain of nonzero integers, let I(x, y) be the predicate "x/y is an integer." Determine whether the following statements are true or false, and explain why. (a) (∀y)(∃x)I(x, y) (b) (∃x)(∀y)I(x, y) 8. In the domain of integers, consider the following predicates: Let N(x) be the statement "x ≠ 0." Let P(x, y) be the statement "xy = 1." (a) Translate the following statement into the symbols of predicate logic. For all integers x, there is some integer y such that if x ≠ 0, then xy = 1. (b) Write the negation of your answer to part (a) in the symbols of predicate logic. Simplify your answer so that it uses the ∧ connective. (c) Translate your answer from part (b) into an English sentence. (d) Which statement, (a) or (b), is true in the domain of integers? Explain. 9. Let P(x, y, z) be the predicate "x + y = z." (a) Simplify the statement ¬(∀x)(∀y)(∃z)P(x, y, z) so that no quantifier lies within the scope of a negation. (b) Is the statement (∀x)(∀y)(∃z)P(x, y, z) true in the domain of all integers? Explain why or why not. (c) Is the statement (∀x)(∀y)(∃z)P(x, y, z) true in the domain of all integers between 1 and 100? Explain why or why not. 10. The domain of the following predicates is the set of all traders who work at the Tokyo Stock Exchange. Translate the following predicate logic statements into ordinary, everyday English. (Don't simply give a word-for-word translation; try to write sentences that make sense.) (a) (∀x)(∃y)P(x, y) (b) (∃y)(∀x)(Q(x, y) → P(x, y)) (c) Which statement is impossible in this context? Why? 11. Translate the following statements into predicate logic using the two common constructions in Section 1.3.5. State what your predicates are, along with the domain of each. (a) (b) (c) (d) All natural numbers are integers. Some integers are natural numbers. All the streets in Cozumel, Mexico, are one-way. Some streets in London don't have modern curb cuts. 12. Write the following statements in predicate logic. Define what your predicates are. Use the domain of all quadrilaterals. (a) All rhombuses are parallelograms. (b) Some parallelograms are not rhombuses. 13. Let the following predicates be given. The domain is all people. (a) Write the following statement in predicate logic. There is at least one rude child. (b) Formally negate your statement from part (a). (c) Write the English translation of your negated statement. 14. In the domain of all people, consider the following predicate. (a) Write the statement "Everybody needs somebody to love" in predicate logic. (b) Formally negate your statement from part (a). (c) Write the English translation of your negated statement. 15. The domain for this problem is some unspecified collection of numbers. Consider the predicate (a) Translate the following statement into predicate logic. Every number has a number that is greater than it. (b) Negate your expression from part (a), and simplify it so that no quantifier or connective lies within the scope of a negation. (c) Translate your expression from part (b) into understandable English. Don't use variables in your English translation. 16. Any equation or inequality with variables in it is a predicate in the domain of real numbers. For each of the following statements, tell whether the statement is true or false. (a) (∀x)(x2 > x) (b) (∃x)(x2 − 2 = 1) (c) (∃x)(x2 + 2 = 1) (d) (∀x)(∃y)(x2 + y = 4) (e) (∃y)(∀x)(x2 + y = 4) 17. The domain of the following predicates is all integers greater than 1. Consider the following statement. For every x that is not prime, there is some prime y that divides it. (a) Write the statement in predicate logic. (b) Formally negate the statement. (c) Write the English translation of your negated statement. 18. Write the following statement in predicate logic, and negate it. Say what your predicates are, along with the domains. Let x and y be real numbers. If x is rational and y is irrational, then x + y is irrational. 19. Refer to Example 1.14. (a) Give the reasons for each ⇔ step in the simplification of the formal negation of statement (2). (b) Give the formal negation of statement (1). Simplify your answer so that no quantifier or connective lies within the scope of a negation. Translate your negated statement back into English. (c) Give the formal negation of statement (3). Simplify your answer. Translate your negated statement back into English. 20. Let the following predicates be given in the domain of all triangles. Consider the following statements. (a) Write a proof sequence to show that S1 ⇔ S2. (b) Write S1 in ordinary English. (c) Write S2 in ordinary English. 21. Let the following predicates be given. The domain is all computer science classes. (a) Write the following statements in predicate logic. i. All interesting CS classes are useful. ii. There are some useful CS classes that are not interesting. iii. Every interesting CS class has more students than any non-interesting CS class. (b) Write the following predicate logic statement in everyday English. Don't just give a word-for-word translation; your sentence should make sense. (c) Formally negate the statement from part (b). Simplify your negation so that no quantifier lies within the scope of a negation. State which derivation rules you are using. (d) Give a translation of your negated statement in everyday English. 22. Let the following predicates be given. The domain is all cars. (a) Write the following statements in predicate logic. i. All sports cars are fast. ii. There are fast cars that aren't sports cars. iii. Every fast sports car is expensive. (b) Write the following predicate logic statement in everyday English. Don't just give a word-for-word translation; your sentence should make sense. (c) Formally negate the statement from part (b). Simplify your negation so that no quantifier or connective lies within the scope of a negation. State which derivation rules you are using. (d) Give a translation of your negated statement in everyday English. 23. Let P(x) be a predicate in the domain consisting of just the numbers 0 and 1. Let p be the statement P(0) and let q be the statement P(1). (a) Write (∀x)P(x) as a propositional logic formula using p and q. (b) Write (∃x)P(x) as a propositional logic formula using p and q. (c) In this situation, which derivation rule from propositional logic corresponds to the universal and existential negation rules of predicate logic? 24. (a) Give an example of a pair of predicates P(x) and Q(x) in some domain to show that the ∃ quantifier does not distribute over the ∧ connective. That is, give an example to show that the statements are not logically equivalent. (b) It is true, however, that ∃ distributes over ∨. That is, is an equivalence rule for predicate logic. Verify that your example from part (a) satisfies this equivalence. 25. (a) Give an example to show that ∀ does not distribute over ∨. (b) It is a fact that ∀ distributes over ∧. Check that your example from part (a) satisfies this equivalence rule. 1.4 Logic in Mathematics There is much more that we could say about symbolic logic; we have only scratched the surface. But we have developed enough tools to help us think carefully about the types of language mathematicians use. This section provides an overview of the basic mathematical "parts of speech." Most mathematics textbooks (including this one) label important statements with a heading, such as "Theorem," "Definition," or "Proof." The name of each statement describes the role it plays in the logical development of the subject. Therefore it is important to understand the meanings of these different statement labels. Inquiry 1.10 Explain why an integer cannot be both even and odd. Inquiry 1.11 Draw a diagram consisting of straight line segments in which every line segment intersects exactly four other line segments. Inquiry 1.12 Recall that a prime number is a natural number n such that n > 1 and n has no divisors other than n and 1. Prove or disprove the following: Every prime number greater than 3 is the sum of two prime numbers. 1.4.1 The Role of Definitions in Mathematics When we call a statement a "definition" in mathematics, we mean something different from the usual everyday notion. Everyday definitions are descriptive. The thing being defined already exists, and the purpose of the definition is to describe the thing. When a dictionary defines some term, it is characterizing the way the term is commonly used. For example, if we looked up the definition of "mortadella" in the Oxford English Dictionary (OED), we would read the following. Any of several types of Italian (esp. Bolognese) sausage; (now) spec. a thick smoothtextured pork sausage containing pieces of fat and typically served in slices. The authors of the OED have done their best to describe what is meant by the term "mortadella." A good dictionary definition is one that does a good job describing something. In mathematics, by contrast, a definition is a statement that stipulates the meaning of a new term, symbol, or object. For example, a plane geometry textbook may define parallel lines as follows. Definition 1.4 Two lines are parallel if they have no points in common. The job of this definition is not to describe parallel lines, but rather to specify exactly what we mean when we use the word "parallel." Once parallel lines have been defined in this way, the statement "l and m are parallel" means "l and m have no points in common." We may have some intuitive idea of what l and m might look like (e.g., they must run in the same direction), but for the purposes of any future arguments, the only thing we really know about l and m is that they don't intersect each other. The meaning of a mathematical statement depends on the definitions of the terms involved. If you don't understand a mathematical statement, start looking at the definitions of all the terms. These definitions stipulate the meanings of the terms. The statement won't make sense without them. For example, consider Inquiry Problem 1.10 at the beginning of this section. We already know what even and odd numbers are; we all come to this problem with a previously learned concept image of "even" and "odd." Our concept image is what we think of when we hear the term: an even number ends in an even digit, an odd number can't be divided in half evenly, "2, 4, 6, 8; who do we appreciate," etc. When writing mathematically, however, it is important not to rely too heavily on these concept images. Any mathematical statement about even and odd numbers derives its meaning from definitions. We choose to specify these as follows. Definition 1.5 An integer n is even if n = 2k for some integer k. Definition 1.6 An integer n is odd if n = 2k + 1 for some integer k. Given these definitions, we can justify the statement "17 is odd" by noting that 17 = 2 · 8 + 1. In fact, this equation is precisely the meaning of the statement that "17 is odd"; there is some integer k (in this case, k = 8) such that 17 = 2k+1. You already "knew" that 17 is odd, but in order to mathematically prove that 17 is odd, you need to use the definition. Mathematical definitions must be extremely precise, and this can make them somewhat limited. Often our concept image contains much more information than the definition supplies. For example, we probably all agree that it is impossible for a number to be both even and odd, but this fact doesn't follow immediately from Definitions 1.5 and 1.6. To say that some given number n is even means that n = 2k1 for some integer k1, and to say that it is odd is to say that n = 2k2 + 1 for some integer k2. (Note that k1 and k2 may be different.) Now, is this possible? It would imply that 2k1 = 2k2 + 1, which says that 1 = 2(k1 − k2), showing that 1 is even, by Definition 1.5. At this point we might object that 1 is odd, so it can't be even, but this reasoning is circular: we were trying to show that a number cannot be both even and odd. We haven't yet shown this fact, so we can't use this fact in our argument. It turns out that Definitions 1.5 and 1.6 alone are not enough to show that a number can't be both even and odd; to do so requires more facts about integers, as we will see in Section 1.5. One reasonable objection to the above discussion is that our definition of odd integers was too limiting; why not define an odd integer to be an integer that isn't even? This is certainly permissible, but then it would be hard4 to show that an odd integer n can be written as 2k + 1 for some integer k. And we can't have two definitions for the same term. Stipulating a definition usually involves a choice on the part of the author, but once this choice is made, we are stuck with it. We have chosen to define odd integers as in Definition 1.6, so this is what we mean when we say "odd." Since definitions are stipulative, they are logically "if and only if" statements. However, it is common to write definitions in the form [Object] x is [defined term] if [defining property about x]. The foregoing examples all take this form. In predicate logic, if then the above definition really means the following. However, this is not what the definition says at face value. Definitions look like "if … then" statements, but we interpret them as "if and only if" statements because they are definitions. For example, Definition 1.4 is stipulating the property that defines all parallel lines, not just a property some parallel lines might have. Strictly speaking, we really should use "if and only if" instead of "if" in our definitions. But the use of "if" is so widespread that most mathematicians would find a definition like Two lines are parallel if and only if they have no points in common. awkward to read. Since this statement is a definition, it is redundant to say "if and only if." 1.4.2 Other Types of Mathematical Statements Definitions are a crucial part of mathematics, but there are other kinds of statements that occur frequently in mathematical writing. Any mathematical system needs to start with some assumptions. Without any statements to build on, we would never be able to prove any new statements. Statements that are assumed without proof are called postulates or axioms. For example, the following is a standard axiom about the natural numbers. Axioms are typically very basic, fundamental statements about the objects they describe. Any theorem in mathematics is based on the assumption of some set of underlying axioms. So to say theorems are "true" is not to say they are true in any absolute sense, only that they are true, given that some specified set of axioms is true. A theorem is a statement that follows logically from statements we have already established or taken as given. Before a statement can be called a theorem, we must be able to prove it. A proof is a valid argument, based on axioms, definitions, and proven theorems, that demonstrates the truth of a statement. The derivation sequences that we did in Section 1.2 were very basic mathematical proofs. We will see more interesting examples of proofs in the next section. We also use the terms lemma, proposition, and corollary to refer to specific kinds of theorems. Usually authors will label a result a lemma if they are using it to prove another result. Some authors make no distinction between a theorem and a proposition, but the latter often refers to a result that is perhaps not as significant as a full-fledged theorem. A corollary is a theorem that follows immediately from another result via a short argument. One last word on terminology: A statement that we intend to prove is called a claim. A statement that we can't yet prove but that we suspect is true is called a conjecture. 1.4.3 Counterexamples Often mathematical statements are of the form We saw in the previous section that the negation of statement 1.4.1 is So either statement 1.4.1 is true or statement 1.4.2 is true, but not both. If we can find a single value for x that makes ¬P(x) true, then we know that statement 1.4.2 is true, and therefore we also know that statement 1.4.1 is false. For example, we might be tempted to make the following statement. But 2 is an example of a prime number that is not odd, so statement 1.4.3 is false. A particular value that shows a statement to be false is called a counterexample to the statement. Another common logical form in mathematics is the universal if–then statement. To find a counterexample to a statement of this form, we need to find some x that satisfies the negation This last statement is equivalent (using implication and De Morgan's law) to So a counterexample is something that satisfies P and violates Q. Example 1.15 Find a counterexample to the following statement. For all sequences of numbers a1, a2, a3, …, if a1 < a2 < a3 < …, then some ai must be positive. Solution: By the above discussion, we need an example of a sequence that satisfies the "if" part of the statement and violates the "then" part. In other words, we need to find an increasing sequence that is always negative. Something with a horizontal asymptote will work: an = −1/n is one example. Note that −1 < −1/2 < −1/3 < …, but all the terms are less than zero. ◊ 1.4.4 Axiomatic Systems In rigorous, modern treatments of mathematics, any system (e.g., plane geometry, the real numbers) must be clearly and unambiguously defined from the start. The definitions should leave nothing to intuition; they mean what they say and nothing more. It is important to be clear about the assumptions, or axioms, for the system. Every theorem in the system must be proved with a valid argument, using only the definitions, axioms, and previously proved theorems of the system. This sounds good, but it is actually impossible. It is impossible because we can't define everything; before we write the first definition we have to have some words in our vocabulary. These starting words are called undefined terms. An undefined term has no meaning—it is an abstraction. Its meaning comes from the role it plays in the axioms of the system. A collection of undefined terms and axioms is called an axiomatic system. Axiomatic systems for familiar mathematics such as plane geometry and the real number system are actually quite complicated and beyond the scope of an introductory course. Here we will look at some very simple axiomatic systems to get a feel for how they work. This will also give us some experience with logic in mathematics. The first example defines a "finite geometry," that is, a system for geometry with a finite number of points. Although this system speaks of "points" and "lines," these terms don't mean the same thing they meant in high school geometry. In fact, these terms don't mean anything at all, to begin with at least. The only thing we know about points and lines is that they satisfy the given axioms. Example 1.16 Axiomatic system for a four-point geometry. Undefined terms: point, line, is on Axioms: 1. For every pair of distinct points x and y, there is a unique line l such that x is on l and y is on l. 2. Given a line l and a point x that is not on l, there is a unique line m such that x is on m and no point on l is also on m. 3. There are exactly four points. 4. It is impossible for three points to be on the same line. Notice that these axioms use terms from logic in addition to the undefined terms. We are also using numbers ("four" and "three"), even though we haven't defined an axiomatic system for the natural numbers. In this case, our use of numbers is more a convenient shorthand than anything; we aren't relying on any properties of the natural numbers such as addition, ordering, divisibility, etc. It is common to use an existing system to define a new axiomatic system. For example, some modern treatments of plane geometry use axioms that rely on the real number system. The axioms in Example 1.16 use constructions from predicate logic. In any event, these prerequisite systems can also be defined axiomatically, so systems that use them are still fundamentally axiomatic. Definitions can help make an axiomatic system more user-friendly. In the fourpoint geometry of Example 1.16, we could make the following definitions. In these (and other) definitions, the word being defined is in italics. Definition 1.7 A line l passes through a point x if x is on l. Definition 1.7 gives us a convenient alternative to using the undefined term "is on." For example, in the first axiom, it is a bit awkward to say "x is on l and y is on l," but Definition 1.7 allows us to rephrase this as "l passes through x and y." The definition doesn't add any new features to the system; it just helps us describe things more easily. This is basically what any definition in mathematics does. The following definition is a slight restatement of Definition 1.4, modified to fit the terminology of this system. Definition 1.8 Two lines, l and m, are parallel if there is no point x, such that x is on l and x is on m. Now we could rephrase the second axiom of Example 1.16 as follows. 1. Given a line l and a point x that is not on l, there is a unique line m passing through x such that m is parallel to l. A simple theorem and proof would appear as follows. Theorem 1.1 In the axiomatic system of Example 1.16, there are at least two distinct lines. Proof By Axiom 3, there are distinct points x, y, and z. By Axiom 1, there is a line l1 through x and y, and a line l2 through y and z. By Axiom 4, x, y, and z are not on the same line, so l1 and l2 must be distinct lines. □ A model of an axiomatic system is an interpretation in some context in which all the undefined terms have meanings and all the axioms hold. Models are important because they show that it is possible for all the axioms to be true, at least in some context. And any theorem that follows from the axioms must also be true for any valid model. Let's make a model for the system in Example 1.16. Let a "point" be a dot, and let a "line" be a simple closed loop. A point "is on" a line if the dot is inside the loop. Figure 1.3 shows this model. It is easy to check that all the axioms hold, though this model doesn't really match our concept image of points and lines in ordinary geometry. We may think we know what points and lines should look like, but mathematically speaking we only know whatever we can prove about them using the axioms. (In the exercises you will construct a more intuitive model for this system.) The mathematician David Hilbert (1862–1943) was largely responsible for developing the modern approach to axiomatics. Hilbert, reflecting on the abstract nature of axiomatic systems, remarked, "Instead of points, lines, and planes, one must be able to say at all times tables, chairs, and beer mugs" [24]. If we used a word processor to replace every occurrence of "point" with "table" and every occurrence of "line" with "chair" in the above axioms, definitions, theorem, and proof, the theorem would still hold, and the proof would still be valid. The next example is referred to in the exercises. The choice of undefined terms emphasizes that these terms, by themselves, carry no meaning. Figure 1.3 A model for the axiomatic system in Example 1.16 using dots and loops. Example 1.17 Badda-Bing axiomatic system. Undefined terms: badda, bing, hit Axioms: 1. Every badda hits exactly four bings. 2. Every bing is hit by exactly two baddas. 3. If x and y are distinct baddas, each hitting bing q, then there are no other bings hit by both x and y. 4. There is at least one bing. One possible model for the Badda-Bing system is shown in Figure 1.4. The picture shows an infinite collection of squares; the central square connects to four other squares whose sides are half as long. Each of these squares connects to three other smaller squares, and each of those connects to three others, and so on. This is an example of a fractal—a shape with some sort of infinitely repetitive geometric structure. (We'll say more about fractals in Chapter 3.) In this model, a "badda" is a square, and a "bing" is a corner, or vertex, of a square. A square "hits" a vertex if the vertex belongs to the square. Since every square has four vertices, Axiom 1 is satisfied. Axiom 2 holds because every vertex in the model belongs to exactly two squares. Axiom 3 is a little harder to see: if squares x and y share a vertex q, there is no way they can share another vertex. And Axiom 4 is obviously true—there are lots of bings. Figure 1.4 A fractal model for the Badda-Bing geometry. Exercises 1.4 1. Look up the word "root" in a dictionary. It should have several different definitions. Find a definition that is (a) descriptive and another definition that is (b) stipulative. 2. Find another word in the English language that has both descriptive and stipulative definitions. 3. Use Definition 1.5 to explain why 104 is an even integer. 4. Let n be an integer. Use Definition 1.6 to explain why 2n+7 is an odd integer. 5. Let n1 and n2 be even integers. (a) Use Definition 1.5 to write n1 and n2 in terms of integers k1 and k2, respectively. (b) Write the product n1n2 in terms of k1 and k2. Simplify your answer. (c) Write the sum n1+n2 in terms of k1 and k2. Simplify your answer. 6. Consider the following definition of the "◁" symbol. Definition. Let x and y be integers. Write x ◁ y if 3x + 5y = 7k for some integer k. (a) Show that 1 ◁ 5, 3 ◁ 1, and 0 ◁ 7. (b) Find a counterexample to the following statement: If a ◁ b and c ◁ d, then a · c ◁ b · d. 7. Give three adjectives that describe your concept image of a circle. 8. There are several different models for geometries in which the points are ordered pairs (x, y) of real numbers; we plot these points in the usual way in the x y-plane. In such a geometry, there can be a formula for the distance between two points (x1, y1) and (x2, y2). For example, in Euclidean geometry, distance is given by the usual Euclidean distance formula: In any geometry with a distance formula, we can define a circle as follows. Definition 1.9 A circle centered at (a, b) with radius r is the collection of all points (x, y) whose distance from (a, b) is r. (a) Use Definition 1.9 to give an equation for the circle with radius 5 centered at (0, 0) in the Euclidean plane. (b) Plot the circle from part (a) in the x y-plane. (c) In the Taxicab geometry, the distance between two points (x1, y1) and (x2, y2) is given by the following formula. (This is called "taxicab" distance because it models the distance you would have to travel if you were restricted to driving on a rectangular city grid.) In this model, use Definition 1.9 to plot the "circle" with radius 5 centered at (0, 0). (d) Which type of circle (Euclidean or taxicab) agrees with your concept image of circle? 9. Consider the lines y = 2x + 1 and y = x + 2 in the usual x y-plane. Use Definition 1.4 to explain why these lines are not parallel. Be specific. 10. Consider the domain of all quadrilaterals. Let Write the meaning of each mathematical statement in predicate logic, keeping in mind the logical distinction between definitions and theorems. (a) Definition. A quadrilateral is a rectangle if it has four right angles. (b) Theorem. A quadrilateral is a rectangle if it has four right angles. 11. Write Definition 1.5 in predicate logic. Use the predicate E(x) = "x is even" in the domain of integers. 12. Let the following statements be given. Definition. A triangle is scalene if all of its sides have different lengths. Theorem. A triangle is scalene if it is a right triangle that is not isosceles. Suppose ΔABC is a scalene triangle. Which of the following conclusions are valid? Why or why not? (a) All of the sides of ΔABC have different lengths. (b) ΔABC is a right triangle that is not isosceles. 13. What is the difference between an axiom and a theorem? 14. Let P(n, x, y, z) be the predicate "xn + yn = zn." (a) Write the following statement in predicate logic, using positive integers as the domain. For every positive integer n, there exist positive integers x, y, and z such that xn + yn = zn. (b) Formally negate your predicate logic statement from part (a). Simplify so that no quantifier lies within the scope of a negation. (c) In order to produce a counterexample to the statement in part (a), what, specifically, would you have to find? 15. Find a counterexample for each statement. (a) If n is prime, then 2n − 1 is prime. (b) Every triangle has at least one obtuse angle.5 (c) For all real numbers x, x2 ≥ x. (d) For every positive nonprime integer n, if some prime p divides n, then some other prime q (with q ≠ p) also divides n. 16. Find a counterexample for each statement. (a) If all the sides of a quadrilateral have e