University of California Davis Transition to Advanced Mathematics Questions

Description

Prove that (Z; #), where a#b = a + b + 1, is a group (i.e. prove that # is associative, that there is an identity element, and that every element has an inverse).
hint 1: For proving that the system has an identity element, we can provide an example such as e=0, and then show that it works as an identity element

hint 2: to solve if something is associative, we need to prove that (a∗b)∗c=a∗(b∗c). For this question, there is only one operation, #, so you would start with (a#b)#chint 3: a, b, and c are arbitrary integers here.

1 attachmentsSlide 1 of 1attachment_1attachment_1

Unformatted Attachment Preview

62025_10_front endsheet.qxd
4/22/10
11:09 PM
Page 1
Transition to Advanced Mathematics, 7th Edition
Sections and Prerequisites
Chapter 6
Chapter 5
Chapter 7
6.1, 6.2, 6.3, 6.4, 6.5
7.1, 7.2, 7.3, 7.4, 7.5
5.1, 5.2, 5.3, 5.4, 5.5
4.6
4.5
Chapter 4
4.1, 4.2, 4.3, 4.4
3.4
Chapter 3
3.5
3.1, 3.2, 3.3
2.6
Chapter 2
2.1, 2.2, 2.3, 2.4, 2.5
1.7
Chapter 1
1.1, 1.2, 1.3, 1.4, 1.5, 1.6
Preface to
the Student
Core
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page i
A TRANSITION
TO
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page iii
S E V E N T H
E D I T I O N
A TRANSITION
TO
Douglas Smith
University of North Carolina Wilmington
Maurice Eggen
Trinity University
Richard St. Andre
Central Michigan University
Australia • Brazil • Japan • Korea • Mexico • Singapore • Spain • United Kingdom • United States
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page iv
7th Edition
Douglas Smith, Maurice Eggen, and
Richard St. Andre
Publisher: Richard Stratton
Associate Editor: Daniel Seibert
Editorial Assistant: Shaylin Walsh
Senior Marketing Manager: Jennifer Pursley
Jones
Marketing Communications Manager:
Mary Anne Payumo
Marketing Coordinator: Erica O’Connell
Content Project Manager: Alison Eigel Zade
Art Director: Jill Ort
Text Permissions Account Manager:
Margaret Chamberlain-Gaston
Photo Permissions Account Manager: Don
Schlotman
Production Service: Elm Street Publishing
Services
Compositor: Integra Software Services, Inc.
© 2011, 2006, 2001 Brooks/Cole, Cengage Learning
copyright herein may be reproduced, transmitted, stored, or used
in any form or by any means graphic, electronic, or mechanical,
including but not limited to photocopying, recording, scanning,
digitizing, taping, Web distribution, information networks, or
information storage and retrieval systems, except as permitted
under Section 107 or 108 of the 1976 United States Copyright Act,
without the prior written permission of the publisher.
Cengage Learning Customer & Sales Support, 1-800-354-9706
For permission to use material from this text or product,
submit all requests online at www.cengage.com/permissions.
Further permissions questions can be emailed to
permissionrequest@cengage.com.
Library of Congress Control Number: 2009939573
Student Edition:
ISBN-13: 978-0-495-56202-3
ISBN-10: 0-495-56202-5
Brooks/Cole
20 Channel Center Street
Boston, MA 02210
USA
Cengage Learning is a leading provider of customized learning
solutions with ofﬁce locations around the globe, including
Singapore, the United Kingdom, Australia, Mexico, Brazil and Japan.
Locate your local ofﬁce at international.cengage.com/region
Cengage Learning products are represented in Canada by Nelson
Education, Ltd.
For your course and learning solutions, visit
www.cengage.com.
Purchase any of our products at your local college store
or at our preferred online store www.cengagebrain.com.
Printed in the United States of America
1 2 3 4 5 6 7 14 13 12 11 10
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page v
To our wives
Karen, Karen, and Karen
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page vi
C O N T E N T S
Preface viii
Preface to the Student xii
C H A P T E R
C H A P T E R
C H A P T E R
1
Logic and Proofs
1.1
1.2
1.3
1.4
1.5
1.6
1.7
Propositions and Connectives 1
Conditionals and Biconditionals 9
Quantifiers 18
Basic Proof Methods I 27
Basic Proof Methods II 40
Proofs Involving Quantifiers 48
2
Set Theory
2.1
2.2
2.3
2.4
2.5
2.6
Basic Concepts of Set Theory 71
Set Operations 79
Extended Set Operations and Indexed Families of Sets 89
Mathematical Induction 100
Equivalent Forms of Induction 114
Principles of Counting 122
3
Relations and Partitions
1
71
135
3.1 Cartesian Products and Relations 135
3.2 Equivalence Relations 147
vi
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page vii
Contents
vii
3.3 Partitions 157
3.4 Ordering Relations 163
3.5 Graphs 174
C H A P T E R
C H A P T E R
C H A P T E R
C H A P T E R
4
Functions
185
4.1
4.2
4.3
4.4
4.5
4.6
Functions as Relations 185
Constructions of Functions 195
Functions That Are Onto; One-to-One Functions 205
One-to-One Correspondences and Inverse Functions 213
Images of Sets 220
Sequences 225
5
Cardinality
5.1
5.2
5.3
5.4
5.5
Equivalent Sets; Finite Sets 233
Infinite Sets 242
Countable Sets 251
The Ordering of Cardinal Numbers 259
Comparability of Cardinal Numbers and the Axiom of Choice 267
6
Concepts of Algebra
6.1
6.2
6.3
6.4
6.5
Algebraic Structures 275
Groups 283
Subgroups 292
Operation Preserving Maps 298
Rings and Fields 306
7
Concepts of Analysis
7.1
7.2
7.3
7.4
7.5
Completeness of the Real Numbers 316
The Heine–Borel Theorem 324
The Bolzano–Weierstrass Theorem 336
The Bounded Monotone Sequence Theorem 341
Equivalents of Completeness 347
233
275
315
Index 393
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page viii
P R E F A C E
Excerpts from the Preface to the First Edition
“I understand mathematics but I just can’t do proofs.”
Our experience has led us to believe that the remark above, though contradictory,
expresses the frustration many students feel as they pass from beginning calculus
to a more rigorous level of mathematics. This book developed from a series of
lecture notes for a course at Central Michigan University that was designed to
address this lament. The text is intended to bridge the gap between calculus and
advanced courses in at least three ways. First, it provides a firm foundation in the
major ideas needed for continued work. Second, it guides students to think and to
express themselves mathematically—to analyze a situation, extract pertinent
facts, and draw appropriate conclusions. Finally, we present introductions to
modern algebra and analysis in sufficient depth to capture some of their spirit and
characteristics.
Exercises marked with a solid star (多) have complete answers at the back of the
text. Open stars (夡) indicate that a hint or a partial answer is provided. “Proofs to
Grade” are a special feature of most of the exercise sets. We present a list of claims
with alleged proofs, and the student is asked to assign a letter grade to each “proof”
and to justify the grade assigned. Spurious proofs are usually built around a single
type of error, which may involve a mistake in logic, a common misunderstanding
of the concepts being studied, or an incorrect symbolic argument. Correct proofs
may be straightforward, or they may present novel or alternate approaches. We
have found these exercises valuable because they reemphasize the theorems and
counterexamples in the text and also provide the student with an experience similar
to grading papers. Thus the student becomes aware of the variety of possible errors
and develops the ability to read proofs critically.
In summary, our main goals in this text are to improve the student’s ability to
think and write in a mature mathematical fashion and to provide a solid understanding of the material most useful for advanced courses. Student readers, take comfort
viii
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page ix
Preface
ix
from the fact that we do not aim to turn you into theorem-proving wizards. Few of
you will become research mathematicians. Nevertheless, in almost any mathematically related work you may do, the kind of reasoning you need to be able to do is
the same reasoning you use in proving theorems. You must first understand exactly
what you want to prove (verify, show, or explain), and you must be familiar with the
logical steps that allow you to get from the hypothesis to the conclusion. Moreover,
a proof is the ultimate test of your understanding of the subject matter and of mathematical reasoning.
We are grateful to the many students who endured earlier versions of the manuscript and gleefully pointed out misprints. We acknowledge also the helpful comments of Edwin H. Kaufman, Melvin Nyman, Mary R. Wardrop, and especially
Douglas W. Nance, who saw the need for a course of this kind at CMU and did a
superb job of reviewing the manuscript.
To the Seventh Edition
The seventh edition is based on the same goals and core material as previous editions, but with new organization in several places and many new and revised expositions, examples, and exercises. In the expanded Preface to the Student, we have
gathered together preliminary ideas that should already be familiar to students
(including properties of the number systems, definitions of even, odd and prime
numbers, naive notions of sets, and the basic terminology of functions). This
arrangement makes the prerequisite material easier to locate and keeps the focus of
the text on the use of mathematical reasoning.
The rewritten introduction to concepts of elementary number theory in Section
1.7 is deliberately placed early in the text, before any discussion of inductive proofs
and the Well-Ordering Principle, as an opportunity to practice basic proof methods
on a coherent set of results about divisibility, the greatest common divisor, and linear combinations. Placing this content here (and accepting the Division Algorithm
without proof until inductive proofs are introduced in Chapter 2) allows students to
experience significant results that are achieved with relatively simple proof forms.
Later, students can observe the power of inductive methods to prove the Division
Algorithm and related results.
In Chapter 4 properties of one-to-one and onto functions are now grouped
more efficiently and there is a separate section on one-to-one correspondences and
permutations of a set. In Section 5.3 on countable sets, the major results (that subsets and unions of countably many countable sets are countable) are moved up to
make them more accessible. In Chapter 7, there is even more emphasis on the
meaning of the completeness property of the real number system.
Chapter 1 introduces the propositional and predicate logic required by
mathematical arguments, not as formal logic, but as tools of reasoning for more
complete understanding of concepts (including some ideas of arithmetic, analytic geometry, and calculus with which the student is already familiar). We
present methods of proof and carefully analyze examples of each method, giving
special attention to the use of definitions and denials. The techniques in this
chapter are used and referred to throughout the text. In Chapters 2, 3, and 4 on
62025_00a_fm_pi-xviii.qxd
x
4/22/10
3:12 AM
Page x
Preface
sets, relations, and functions, we emphasize writing and understanding proofs
that require the student to deal precisely with the concepts of set operations,
equivalence relations and partitions, and properties of injective and surjective
functions.
These first four chapters contain the core material of the text and, in addition,
offer the opportunity for further work in several optional sections: basics of number
theory (Section 1.7), combinatorial counting (Section 2.6), order relations and
graph theory (Sections 3.4 and 3.5), and image sets and sequences (Sections 4.5 and
4.6). See the diagram on the inside front cover for a diagram that highlights the core
and shows the prerequisite relationships among sections. For a one-semester
course, we recommend the core material along with any one of Chapters 5, 6, or 7,
or a selection of optional sections and excursions into one or two of the later chapters—for example, Sections 4.6, 5.1, 5.2, 5.3, 7.1, and 7.2.
Chapters 5, 6, and 7 make use of the skills and concepts the student has acquired
in the first four chapters, and thus are a cut above the earlier chapters in terms of level
and rigor. Chapter 5 emphasizes a working knowledge of cardinality: finite and infinite sets, denumerable sets and the uncountability of the real numbers, and properties
of countable sets. We include sections on the ordering of cardinals and applications of
the Cantor–Schröder–Bernstein Theorem and a brief discussion of the Axiom of
Choice. In Chapter 6 we consider properties of algebras with a binary operation,
groups, substructures, and homomorphisms, and relate these concepts to rings and
fields. Chapter 7 considers the completeness property of the real numbers by tracing
its consequences: the Heine–Borel Theorem, the Bolzano–Weierstrass Theorem, and
the Bounded Monotone Sequence Theorem, and back to completeness.
We sincerely thank our reviewers for the seventh edition: David Bayer,
Columbia University; Fernando Burgos, University of South Florida; Yves
Nievergelt, Eastern Washington University; and Don Redmond, Southern Illinois
University.
We also thank our reviewers of earlier editions: Mangho Ahuja, Southeast
Missouri State University; William Ballard, University of Montana; David
Barnette, University of California at Davis; Gerald Beer, California State
University–Los Angeles; Harry Conce, Mankato State University; Sherralyn
Craven, Central Missouri State University; Robert Dean, Stephen F. Austin State
University; Ron Dotzel, University of Missouri; Harvey Elder, Murray State
University; Michael J. Evans, North Carolina State University; Gerald Farrell.
California Polytechnic State University; Benjamin Freed, Clarion University of
Pennsylvania; Robert Gamble, Winthrop College; Dennis Garity, Oregon State
University; Robert P. Hunter, Pennsylvania State University; Jack Johnson,
Brigham Young University–Hawaii; L. Christine Kinsey, Canisuis College; Daniel
Kocan, State University of New York, Potsdam; James McKinney, California
Polytechnic State University; Blair Madore, The State University of New York at
Potsdam; Andrew Martin, Morehead State University; Edward Mosley, Lyon
College; Van C. Nall, University of Richmond; Yves Nievergelt, Eastern
Washington University; Yewande Olubummo, Spelman College; Hoseph H.
Oppenheim, San Francisco State University; John S. Robertson, Georgia College &
State University; Victor Schneider, University of Southwestern Louisiana; Dale
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page xi
Preface
xi
Schoenefeld, University of Tulsa; Kenneth Slonnegar, State University of New
York at Fredonia; Douglas Smith, University of the Pacific; Joseph Teeters,
University of Wisconsin; Mary Treanor, Valparaiso University; and Lawrence
Williams, University of Texas, San Antonio.
We also wish to thank Roger Lipsett for his suggestions after proofreading of
the final manuscript and the staff at Cengage for their exceptional professional
assistance in the development of this edition and previous editions.
access to complete solutions for all exercises via Cengage’s Solution Builder service at www.cengage.com/solutionbuilder.
Douglas D. Smith
Richard St. Andre
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page xii
P R E F A C E
T O
T H E
S T U D E N T
Welcome to the study of mathematical reasoning. The authors know that many students approach this material with some apprehension and uncertainty. Some students
feel that “This isn’t like other mathematics courses,” or expect that the study of
proofs is something they won’t really have to do or won’t use later. These feelings
are natural as you move from calculation-oriented courses where the goals emphasize performing computations or solving certain equations, to more advanced
courses where the goal may be to establish whether a mathematical structure has certain properties. This textbook is written to help ease the transition between these
courses. Let’s consider several questions students commonly have at the beginning
of a “transition” course.
Why write proofs?
Mathematicians often collect information and make observations about particular
cases or phenomena in an attempt to form a theory (a model) that describes patterns
or relationships among quantities and structures. This approach to the development
of a theory uses inductive reasoning. However, the characteristic thinking of the
mathematician is deductive reasoning, in which one uses logic to develop and
extend a theory by drawing conclusions based on statements accepted as true.
Proofs are essential in mathematical reasoning because they demonstrate that the
conclusions are true. Generally speaking, a mathematical explanation for a conclusion has no value if the explanation cannot be backed up by an acceptable proof.
Why not just test and repeat enough examples to confirm
a theory?
After all, as is typically done in natural and social sciences, the test for truth of a
theory is that the results of an experiment conform to predictions, and that when
the experiment is repeated under the same circumstances the result is always the
same. The difference is that in mathematics we need to know whether a given
xii
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page xiii
Preface to the Student
xiii
statement is always true, so while the statement may be true for many (even infinitely many) examples, we would never know whether another example might
show the statement to be false. By studying examples, we might conclude that the
statement
“x 2 − 3x + 43 is a prime number”
is true for all positive integers x. We could reach this conclusion testing the first 10
or 20 or even the first 42 integers 1, 2, 3, Á , 42. In each of these cases and others,
such as 44, 45, 47, 48, 49, 50 and more, x 2 − 3x + 43 is a prime number. But the
statement is not always true because 432 − 3(43) + 43 = 1763, which is 41 · 43.
Checking examples is helpful in gaining insight for understanding concepts and
relationships in mathematics, but is not a valid proof technique unless we can
somehow check all examples.
Why not just rely on proofs that someone else has done?
One answer follows from the statement above that deductive reasoning characterizes the way mathematicians think. In the sciences, a new observation may force a
complete rethinking of what was thought to be true; in mathematics what we know
to be true (by proof) is true forever unless there was a flaw in the reasoning. By
learning the techniques of reasoning and proof, you are learning the tools of the
The first goal of this text is to examine standard proof techniques, especially
concentrating on how to get started on a proof, and how to construct correct proofs
using those techniques. You will discover how the logical form of a statement can
serve as a guide to the structure of a proof of the statement. As you study more
advanced courses, it will become apparent that the material in this book is indeed
fundamental and the knowledge gained will help you succeed in those courses.
Moreover, many of the techniques of reasoning and proof that may seem so difficult at first will become completely natural with practice. In fact, the reasoning that
you will study is the essence of advanced mathematics and the ability to reason
abstractly is a primary reason why applicants trained in mathematics are valuable
to employers.
What am I supposed to know before beginning Chapter 1?
The usual prerequisite for a transition course is at least one semester of calculus. We
will sometimes refer to topics that come from calculus and earlier courses (for
example, differentiable functions or the graph of a parabola), but we won’t be solving equations or finding derivatives.
You will need a good understanding of the basic concepts and notations from
earlier courses. The list of definitions and relationships below includes the main
things you will need to have ready for immediate use at any point in the text.
62025_00a_fm_pi-xviii.qxd
xiv
4/22/10
3:12 AM
Page xiv
Preface to the Student
Be aware that definitions in mathematics, however, are not like definitions in ordinary English, which are based on how words are typically used. For example, the ordinary English word “cool” came to mean something good or popular when many people
used it that way, not because it has to have that meaning. If people stop using the word
that way, this meaning of the word will change. Definitions in mathematics have precise, fixed meanings. When we say that an integer is odd, we do not mean that it’s
strange or unusual. Our definition below tells you exactly what odd means. You may
form a concept or a mental image that you may use to help understand (such as “ends
in 1, 3, 5, 7, or 9”), but the mental image you form is not what has been defined. For this
reason, definitions are usually stated with the “if and only if ” connective because they
describe exactly—no more, no less—the condition(s) to meet the definition.
Sets
A set is a collection of objects, called the elements, or members of the set. When
the object x is in the set A, we write x 僆 A; otherwise x 僆 A. The set
K = {6, 7, 8, 9} has four elements; we see that 7 僆 K but 3 僆 K. We may use setbuilder notation to write the set K as
{x: x is an integer greater than 5 and less than 10},
which we read as “the set of x such that x is . . .” Observe that the set whose only
element is 5 is not the same as the number 5; that is, {5} =
5. The empty set ⭋ is
a set with no elements.
We say that A is a subset of B, and write A ⊆ B, if and only if every element of
A is an element of B. If sets A and B have exactly the same elements, we say they
are equal and write A = B.
We use these notations for the number systems:
⺞ = {1, 2, 3, Á} is the set of natural numbers.
⺪ = {Á −3, −2, −1, 0, 1, 2, Á} is the set of integers.
⺡ is the set of all rational numbers.
⺢ is the set of all real numbers.
⺓ is the set of all complex numbers.
A set is finite if it is empty or if it has n elements for some natural number n.
Otherwise it is infinite. Thus the set {6, 7, 8, 9} is finite. All the number systems
listed above are infinite.
The Natural Numbers
The properties below describe the basic arithmetical and ordering structure of the set ⺞.
1.
Successor properties
1 is a natural number.
Every natural number x has a unique successor x + 1.
1 is not the successor of any natural number.
62025_00a_fm_pi-xviii.qxd
4/22/10
3:12 AM
Page xv
Preface to the Student
2.
3.
xv
Closure properties
The sum of two natural numbers is a natural number.
The product of two natural numbers is a natural number.
Associativity properties
For all x, y, z 僆 ⺞, x + ( y + z) = (x + y) + z.
For all x, y, z 僆 ⺞, x (yz) = (xy)z.
4.
Commutativity properties
For all x, y 僆 ⺞, x + y = y + x.
For all x, y 僆 ⺞, xy = yx.
5.
Distributivity properties
For all x, y, z 僆 ⺞, x (y + z) = xy + xz.
For all x, y, z 僆 ⺞, ( y + z)x = yx + zx.
6.
Cancellation properties
For all x, y, z 僆 ⺞, if x + z = y + z, then x = y.
For all x, y, z 僆 ⺞, if xz = yz, then x = y.
For natural numbers a and b we say a divides b (or a is a divisor of b, or b is
a multiple of a) if and only if there is a natural number k such that b = ak. For
example, 7 divides 56 because there is a natural number (namely 8) such that
56 = 7 · 8.
A natural number p is prime if and only if p is greater than 1 and the only natural numbers that divide p are 1 and p. A composite is a natural number that is
neither 1 nor prime.
The Fundamental Theorem of Arithmetic:
Every natural number larger than 1 is prime or can be expressed uniquely as a product of primes. For example, 440 can be expressed as 440 = 23 · 5 · 11. If we list the
prime factors in increasing order, then there is only one prime factorization: the
primes and their exponents are uniquely determined.
The Integers
The integers share properties 2 through 6 listed above for ⺞ (with the exception that
we can’t cancel z = 0 from the product xz = yz). Other important properties are:
For all x in ⺪, x + 0 = 0, x · 0 = 0 and x + (−x) = 0.
have a truth value. That is, they are either true or false. We call these sentences
propositions. Other sentences, such as “What time is it?” and “Look out!” are interrogatory or exclamatory; they express complete thoughts but have no truth value.
DEFINITION A proposition is a sentence that has exactly one truth
value: true, which we denote by T, or false, which we denote by F.
Some propositions, such as “72 = 60,” have easily determined truth values. It
will take years to determine the truth value of the proposition “The North Pacific
right whale will be an extinct species before the year 2525.” Other statements, such
1
62025_01_ch01_p001-070.qxd
2
CHAPTER 1
4/22/10
1:42 AM
Page 2
Logic and Proofs
as “Euclid was left-handed,” are propositions whose truth values may never be
known.
Sentences like “She lives in New York City” and “x 2 = 36” are not propositions because each could be true or false depending upon the person to whom “she”
refers and what numerical value is assigned to x. We will deal with sentences like
these in Section 1.3.
The statement “This sentence is false” is not a proposition because it is neither
true nor false. It is an example of a paradox—a situation in which, from premises
that look reasonable, one uses apparently acceptable reasoning to derive a conclusion that seems to be contradictory. If the statement “This sentence is false” is true,
then by its meaning it must be false. On the other hand, if the given statement is
false, then what it claims is false, so it must be true. The study of paradoxes such as
this has played a key role in the development of modern mathematical logic. A
famous example of a paradox formulated in 1901 by Bertand Russell* is discussed
in Section 2.1.
By applying logical connectives to propositions, we can form new propositions.
DEFINITION The negation of a proposition P, denoted ∼P, is the
proposition “not P.” The proposition ∼P is true exactly when P is false.
The truth value of the negation of a proposition is the opposite of the truth
value of the proposition. For example, the negation of the false proposition “7 is
divisible by 2” is the true statement “It is not the case that 7 is divisible by 2,” or “7
is not divisible by 2.”
DEFINITIONS Given propositions P and Q, the conjunction of P and
Q, denoted P ∧ Q, is the proposition “P and Q.” P ∧ Q is true exactly
when both P and Q are true.
The disjunction of P and Q, denoted P ∨ Q, is the proposition
“P or Q.” P ∨ Q is true exactly when at least one of P or Q is true.
Examples. If C is the proposition “19 is composite” and M is “45 is a multiple of
3,” we know C is false and M is true. Thus “19 is composite and 45 is a multiple of
3,” written using logical connectives as C ∧ M, is a false proposition, while “19 is
composite or 45 is a multiple of 3,” which has form C ∨ M, is true. The false proposition “Either 19 is composite or 45 is not a multiple of 3” has the form C ∨ ∼M.
The English words but, while, and although are usually translated symbolically
with the conjunction connective, because they have the same meaning as and. For
* Bertrand Russell (1872–1970) was a British philosopher, mathematician, and advocate for social
reform. He was a strong voice for precision and clarity of arguments in mathematics and logic. He coauthored Principia Mathematica (1910–1913), a monumental effort to derive all of mathematics from a
specific set of axioms and well-defined rules of inference.
62025_01_ch01_p001-070.qxd
4/22/10
1:42 AM
Page 3
1.1
Propositions and Connectives
3
example, we would write “19 is not composite, but 45 is a multiple of 3” in symbolic form as: (∼C) ∧ M.
An important distinction must be made between a statement and the form of a
statement. In the previous example “19 is composite and 45 is a multiple of 3” is a
proposition with truth value F. We used the form C ∧ M to represent this proposition, but the form C ∧ M itself has no truth value unless C and M are assigned to be
specific propositions. If we let C be “Copenhagen is the capital of Denmark” and M
be “Madrid is the capital of Spain,” then C ∧ M would have the value T.
To repeat: a propositional form does not have a truth value. Instead, each form
has a list of truth values that depend on the values assigned to its components. This
list is displayed by presenting all possible combinations for the truth values of its
components in a truth table. Since the connectives ∧ and ∨ involve two components,
their truth tables must list the four possible combinations of the truth values of those
components:
P
Q
P∧Q
P
Q
P∨Q
T
F
T
F
T
T
F
F
T
F
F
F
T
F
T
F
T
T
F
F
T
T
T
F
Since the value of ∼P depends only on the two possible values for P, its truth
table is
P
∼P
T
F
F
T
Frequently you will encounter compound propositions formed from more than
two propositional variables. The propositional form (P ∧ Q) ∨ ∼R has three variables P, Q, and R; it follows that there are 23 = 8 possible combinations of truth
values. The two main components are P ∧ Q and ∼R. We make truth tables for
these and combine them by using the truth table for ¡.
P
Q
R
P∧Q
∼R
(P ∧ Q) ∨ ∼R
T
F
T
F
T
F
T
F
T
T
F
F
T
T
F
F
T
T
T
T
F
F
F
F
T
F
F
F
T
F
F
F
F
F
F
F
T
T
T
T
T
F
F
F
T
T
T
T
The statement “Either 7 is prime and 9 is even or else 11 is not less than 3” may
be symbolized by (P ∧ Q) ∨ ∼R, where P is “7 is prime,” Q is “9 is even,” and R
62025_01_ch01_p001-070.qxd
4
CHAPTER 1
4/22/10
1:42 AM
Page 4
Logic and Proofs
is “11 is less than 3.” We know P is true, Q is false and R is false. Therefore,
(P ∧ Q) is false and ∼R is true. Thus ( P ∧ Q) ∨ ∼R is true, in agreement with line
7 of the table. Thus the proposition “Either 7 is prime and 9 is even or else 11 is not
less than 3” is a true statement.
Some compound forms always yield the value true just because of the way they
are formed; others are always false.
DEFINITIONS A tautology is a propositional form that is true for
every assignment of truth values to its components.
A contradiction is a propositional form that is false for every assignment
of truth values to its components.
For example, the Law of Excluded Middle, P ∨ ∼P, is a tautology because
P ∨ ∼P is true when P is true and true when P is false. We know that a statement
like “The absolute value function is continuous or it is not continuous” must be true
because it has the form of the Law of Excluded Middle.
Example.
Show that (P ∨ Q) ∨ (∼P ∧ ∼Q) is a tautology.
The truth table for this propositional form is
P
Q
P∨Q
∼P
∼Q
∼P ∧ ∼Q
(P ∨ Q) ∨ (∼P ∧ ∼Q )
T
F
T
F
T
T
F
F
T
T
T
F
F
T
F
T
F
F
T
T
F
F
F
T
T
T
T
T
Since the last column is all true, ( P ∨ Q) ∨ (∼P ∧ ∼Q) is a tautology.
Both ∼(P ∨ ∼P) and Q ∧ ∼Q are examples of contradictions. The negation
of a contradiction is, of course, a tautology.
Writing a proof requires the ability to connect statements so that the truth
of any given statement in the proof follows logically from previous statements
in the proof, from known results, or from basic assumptions. Particularly
important is the ability to recognize or write a statement equivalent to another.
Sometimes, it is the form of a compound statement that may be used to find a
useful equivalent.
DEFINITION Two propositional forms are equivalent if and only
if they have the same truth tables.
62025_01_ch01_p001-070.qxd
4/22/10
1:42 AM
Page 5
1.1
Propositions and Connectives
5
Example. The propositional forms P and ∼(∼P) are equivalent. The truth tables
for these forms may be combined in one table to show that they are the same:
P
∼P
∼( ∼P)
T
F
F
T
T
F
The fact that P and ∼(∼P) have the same truth value for each line of the truth
table means that whatever proposition we choose for P, the truth value of P and
∼(∼P) are identical.
Some of the most commonly used equivalent forms are presented in the following theorem.
Theorem 1.1.1
For propositions P, Q, and R, the following are equivalent:
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
P
P∨Q
P∧Q
P ∨ (Q ∨ R)
P ∧ (Q ∧ R)
P ∧ (Q ∨ R)
P ∨ (Q ∧ R)
∼(P ∧ Q)
∼(P ∨ Q)
and
and
and
and
and
and
and
and
and
∼( ∼P)
Q∨P
Q∧P
(P ∨ Q) ∨ R
(P ∧ Q) ∧ R
(P ∧ Q) ∨ (P ∧ R)
(P ∨ Q) ∧ (P ∨ R)
∼P ∨ ∼Q
∼P ∧ ∼Q
Double Negation Law
f
Commutative Laws
f
Associative Laws
f
Distributive Laws
f
DeMorgan’s* Laws
Proof.
(a)
See the discussion above.
(h) By examining the fourth and seventh columns of their combined truth tables
as shown here,
P
Q
P∧Q
∼( P ∧ Q )
∼P
∼Q
∼P ∨ ∼Q
T
F
T
F
T
T
F
F
T
F
F
F
F
T
T
T
F
T
F
T
F
F
T
T
F
T
T
T
we see that the truth tables for ∼(P ∧ Q) and ∼P ∨ ∼Q are identical. Thus
∼(P ∧ Q) and ∼P ∨ ∼Q are equivalent propositional forms.
Proofs of the remaining parts are left as exercises.

In addition to making tables to verify the remaining parts of Theorem 1.1.1,
you should also think about why two propositional forms are equivalent by looking
* Augustus DeMorgan (1806–1871) was an English logician and mathematician whose contributions
include his notational system for symbolic logic. He also introduced the term “mathematical induction”
(see Section 2.4) and developed a rigorous foundation for that proof technique.
62025_01_ch01_p001-070.qxd
6
CHAPTER 1
4/22/10
1:42 AM
Page 6
Logic and Proofs
at their meanings. For part (h), negation is applied to a conjunction. The form
∼ ( P ∧ Q) is true precisely when P ∧ Q is false. This happens when one of P or Q
is false, or in other words, when one of ∼P or ∼Q is true. Thus, ∼ ( P ∧ Q) is
equivalent to ∼P ∨ ∼Q. That is, to say “You don’t have both P and Q” is the same
as saying “You don’t have P or you don’t have Q.”
As an example of how this theorem might be useful in dealing with statements,
suppose we are told that the statement “The function f is increasing and concave
upward” is false. The statement has the form P ∧ Q, where P is the statement “f is
increasing” and Q is the statement “f is concave upward.” The negation ∼ ( P ∧ Q)
is “It is not the case that f is increasing and f is concave upward.” By part (h) above,
this is equivalent to ∼P ∨ ∼Q, which is
“It is not the case that f is increasing or it is not the case that f is concave
upward.”
An easier way to say this is
“f is not increasing or f is not concave upward.”
A denial of a proposition P is any proposition equivalent to ∼P. A proposition
has only one negation, ∼P, but always has many denials, including ∼P, ∼∼∼P,
∼∼∼∼∼P, etc. DeMorgan’s Laws provide others ways to construct useful denials.
Example. A denial of “Either Miss Scarlet is not guilty or the crime did not take
place in the ballroom” is “The crime took place in the ballroom and Miss Scarlet is
guilty.” This can be verified by writing the two propositions symbolically as
(∼S) ∨ (∼B) and B ∧ S, respectively, and checking that their truth tables have
exactly opposite values. We could also observe that B ∧ S is equivalent to S ∧ B so
a denial of B ∧ S is equivalent to ∼ ( S ∧ B), which we know by DeMorgan’s Laws
is equivalent to (∼S) ∨ (∼B).
Example. The statement “Line L1 has slope 3/5 or line L2 does not have slope −4”
may be symbolized using the form P ∨ ∼Q, so its negation is ∼(P ∨ ∼Q). We can
write a simpler denial (∼P) ∧ Q by applying DeMorgan’s Laws and the Double
Negation Law. The simplified denial says “Line L1 does not have slope 3/5 and line
L2 has slope −4.”
Notice that someone might read the negation ∼(P ∨ ∼Q) as “It is not the case
that L1 has slope 3/5 or line L2 does not have slope −4.” This sentence is ambiguous because without some further explanation, it is not clear if the phrase “It is not
the case” refers to the entire remainder of the sentence or to just “L1 has slope 3/5.”
Ambiguities like the one above are sometimes allowable in English but can
cause trouble in mathematics. To avoid ambiguities, you should use delimiters,
such as parentheses ( ), square brackets [ ], and braces { }.
To avoid writing large numbers of delimiters, we use the following rules,
which we refer to as the hierarchy of connectives.
First, ∼ always is applied to the smallest proposition following it.
Then, ¿ always connects the smallest propositions surrounding it.
Finally, ¡ connects the smallest propositions surrounding it.
62025_01_ch01_p001-070.qxd
4/22/10
1:42 AM
Page 7
1.1
Propositions and Connectives
7
Thus, ∼P ∨ Q is an abbreviation for (∼P) ∨ Q, but ∼( P ∨ Q) is the only way to
write the negation of P ∨ Q. Here are some other examples:
P ∨ Q ∧ R abbreviates P ∨ ( Q ∧ R).
P ∧ ∼Q ∨ ∼R abbreviates [P ∧ (∼Q)] ∨ (∼R).
∼P ∨ ∼Q abbreviates (∼P) ∨ (∼Q).
∼P ∧ ∼R ∨ ∼P ∧ R abbreviates [(∼P) ∧ (∼R)] ∨ [(∼P) ∧ R].
When the same connective is used several times in succession, parentheses
may be omitted. We reinsert parentheses from the left, so that P ∨ Q ∨ R is really
(P ∨ Q) ∨ R. For example, R ∧ P ∧ ∼P ∧ Q abbreviates [(R ∧ P) ∧ (∼P)] ∧ Q,
whereas R ∨ P ∧ ∼P ∨ Q, which does not use the same connective consecutively,
abbreviates (R ∨ [P ∧ (∼P)]) ∨ Q. Leaving out parentheses is not required;
some propositional forms are much easier to read with a few well-chosen “unnecessary” parentheses.
Exercises 1.1
1. Use your knowledge of number systems to determine whether each is true or
false.
(a) 11 is a rational number.

(c) There are exactly 3 prime numbers between 40 and 50.
(d) There are exactly 5 prime numbers less than 10.
(e) 29 is a composite number.
(f) 0 is a natural number.

(h) 18 is a multiple of 12.
2. Which of the following are propositions? Give the truth value of each proposition.
(a) What time is dinner?
(b) It is not the case that 5 + π is not a rational number.

(d) 2x + 3y is a real number.
(e) Either 3 + π is rational or 3 − π is rational.

(g) Either 5π is rational and 4.9 is rational, or 3π is rational.
(h) −12 is rational, and either 3π < 10 or 3π > 15.
(i) It is not the case that 39 is prime, or that 64 is a power of 2.
(j) There are more than three false statements in this book and this statement is one of them.
3. Make truth tables for each of the following propositional forms.

(b) P ∨ ∼P.

(d) P ∧ (Q ∨ ∼Q).

(f) ∼(P ∧ Q).
(g) (P ∨ ∼Q) ∧ R.
(h) ∼P ∧ ∼Q.
62025_01_ch01_p001-070.qxd
8
CHAPTER 1
4/22/10
1:42 AM
Page 8
Logic and Proofs

(j) (P ∧ Q) ∨ (P ∧ R).
(k) P ∧ P.
(l) (P ∧ Q) ∨ (R ∧ ∼S).
4. If P, Q, and R are true while S and T are false, which of the following are true?

(b) Q ∨ (R ∧ S).

(d) (∼P ∨ ∼Q) ∨ (∼R ∨ ∼S).
(e) ∼P ∨ ∼Q.

5. Use truth tables to prove the remaining parts of Theorem 1.1.1.
6. Which of the following pairs of propositional forms are equivalent?

(b) P ∨ P, P.

(d) (∼P) ∨ (∼Q), ∼ (P ∨ ∼Q).

(f) ∼(P ∧ Q), ∼P ∧ ∼Q.

(h) (P ∧ Q) ∨ R, P ∨ (Q ∧ R).
7. Determine the propositional form and truth value for each of the following:
(a) It is not the case that 2 is odd.
(b) f (x) = e x is increasing and concave up.
(c) Both 7 and 5 are factors of 70.
(d) Perth or Panama City or Pisa is located in Europe.
8. P, Q, and R are propositional forms, and P is equivalent to Q, and Q is equivalent to R. Prove that

(b) P is equivalent to R.
(c) ∼Q is equivalent to ∼P.
9. Use a truth table to determine whether each of the following is a tautology, a
(a) (P ∧ Q) ∨ (∼P ∧ ∼Q).
(b) ∼(P ∧ ∼P).

(d) (A ∧ B) ∨ (A ∧ ∼B) ∨ (∼A ∧ B) ∨ (∼A ∧ ∼B).
(e) (Q ∧ ∼P) ∧ ∼ (P ∧ R).
(f) P ∨ [(∼Q ∧ P) ∧ (R ∨ Q)].
10. Suppose A is a tautology and B is a contradiction. Are the following tautologies, contradictions, or neither?

(b) A ∧ ∼B.

(d) ∼( ∼A ∧ B).
11. Give a useful denial of each statement.

(b) Cleveland will win the first game or the second game.

(d) 641,371 is a composite integer.

(f) T is not bounded or T is compact. (Assume that T is a fixed object.)
(g) M is odd and one-to-one. (Assume that M is some fixed function.)
62025_01_ch01_p001-070.qxd
4/22/10
1:42 AM
Page 9
1.2
Conditionals and Biconditionals
9
(h) The function f has positive first and second derivatives at x0. (Assume
that f is a fixed function and x0 is a fixed real number.)
(i) The function g has a relative maximum at x = 2 or x = 4 and a relative
minimum at x = 3. (Assume that g is a fixed function.)
(j) Neither z < s nor z ≤ t is true. (Assume that z, s, and t are fixed real numbers.) (k) R is transitive but not reflexive. (Assume that R is a fixed object.) 12. Restore parentheses to these abbreviated propositional forms. (a) ∼∼P ∨ ∼Q ∧ ∼S. (b) Q ∧ ∼S ∨ ∼ (∼P ∧ Q). (c) P ∧ ∼Q ∨ ∼P ∧ ∼R ∨ ∼P ∧ S. (d) ∼P ∨ Q ∧ ∼∼P ∧ Q ∨ R. 13. Other logical connectives between two propositions P and Q are possible. (a) The word or is used in two different ways in English. We have presented the truth table for ¡, the inclusive or, whose meaning is “one or the other or both.” The exclusive or, meaning “one or the other but not both” and denoted ∨ , has its uses in English, as in “She will marry Heckle or she will marry Jeckle.” The “inclusive or” is much more useful in mathematics and is the accepted meaning unless there is a statement to the contrary. 多 (i) Make a truth table for the “exclusive or” connective ∨. (ii) Show that A ∨ B is equivalent to (A ∨ B) ∧ ∼ (A ∧ B). (b) “NAND” and “NOR” circuits are commonly used as a basis for flash memory chips. A NAND B is defined to be the negation of “A and B.” A NOR B is defined to be the negation of “A or B.” (i) Write truth tables for NAND and NOR connectives. (ii) Show that (A NAND B) ∨ (A NOR B) is equivalent to (A NAND B). (iii) Show that (A NAND B) ∧ (A NOR B) is equivalent to (A NOR B). 1.2 Conditionals and Biconditionals Sentences of the form “If P, then Q” are the most important kind of propositions in mathematics. You have seen many examples of such statements in mathematics courses: from precalculus, “If two lines in a plane have the same slope, then the lines are parallel”; from trigonometry, “If sec u = 53, then sin u = 45.”; from calculus, “If f is differentiable at x0 and f (x0) is a relative minimum for f, then f (x0) = 0.” DEFINITIONS For propositions P and Q, the conditional sentence P ⇒ Q is the proposition “If P, then Q.” Proposition P is called the antecedent and Q is the consequent. The conditional sentence P ⇒ Q is true if and only if P is false or Q is true. Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. 62025_01_ch01_p001-070.qxd 10 CHAPTER 1 4/22/10 1:42 AM Page 10 Logic and Proofs The truth table for P ⇒ Q is P Q P⇒Q T F T F T T F F T T F T According to this table, there is only one way that P ⇒ Q can be false: when P is true and Q is false. Thus, this truth table agrees with the way we understand promises: the only situation where a promise is broken is when the antecedent is true but the person making the promise fails to make the consequent true. Example. Suppose someone says to a friend “If the concert is sold out, I’ll take you sailing.” This promise is broken (the conditional sentence is false) only when the concert was sold out (the antecedent is true) and the person who made the promise did not take the other person sailing (the consequent is false). This is line 3 of the truth table. In all other situations, the promise is true. If there were tickets left (lines 2 and 4 of the table), we don’t say the promise was broken, regardless of whether the friends decided to go sailing. The promise is also kept in the situation where the concert is sold out and the friends went sailing, which is line 1 of the table. One curious consequence of the truth table for P ⇒ Q is that a conditional sentence may be true even when there is no connection between the antecedent and the consequent. The reason for this is that the truth value of P ⇒ Q depends only on the truth value of components P and Q, not on their interpretation. For this reason all of the following are true: “If sin π = 1, then 6 is prime.” (line 4 of the truth table) “13 > 7 ⇒ 2 + 3 = 5.” (line 1 of the truth table)
“π = 3 ⇒ Paris is the capital of France.” (line 2 of the truth table)
and both of these are false by line 3 of the truth table:
“If Saturn has rings, then (2 + 3)2 = 22 + 32.”
“If 4π > 10, then 1 is a prime number.”
Other consequences of the truth table for P ⇒ Q are worth noting. When P is
false, it doesn’t matter what truth value Q has: P ⇒ Q will be true by lines 2 and 4.
When Q is true, it doesn’t matter what truth value P has: P ⇒ Q will be true by lines
1 and 2. Finally, when P and P ⇒ Q are both true (on line 1), Q must also be true.
Example.
Both propositions
“If Isaac Newton was born in 1642, then 3 · 5 = 15”
“If Isaac Newton was born in 1643, then 3 · 5 = 15”
are true because the consequent “3 · 5 = 15” is true.
62025_01_ch01_p001-070.qxd
4/22/10
1:42 AM
Page 11
1.2
Conditionals and Biconditionals
11
Our truth table definition for P ⇒ Q captures the same meaning for “If Á ,
then Á ” that you have always used in mathematics. For example, if we think of x
as some fixed real number, we all know that
“If x > 8, then x > 5”
is a true statement, no matter what number x we have in mind. Let’s examine why
we say this sentence is true for some specific values of x, where the antecedent P is
“x > 8” and the consequent Q is “x > 5.”
In the case x = 11, both P and Q are true, as in line 1 of the truth table. The case
x = 7 corresponds to the second line of the table, and for x = 3 we have the situation in
line 4. There is no case corresponding to line 3 because P ⇒ Q is true. Note that when
we say “If P, then Q” is true, we don’t claim that either P or Q is true. What we do say
is that no matter what number we think of, if it’s larger than 8, it’s also larger than 5.
Two propositions closely related to P ⇒ Q are its converse and contrapositive.
DEFINITION Let P and Q be propositions.
The converse of P ⇒ Q is Q ⇒ P.
The contrapositive of P ⇒ Q is (∼Q ) ⇒ (∼P).
For the conditional sentence “If π is an integer, then 14 is even,” the converse
of the sentence is “If 14 is even, then π is an integer” and the contrapositive is “If
14 is not even, then π is not an integer.” The converse is false, but the sentence and
its contrapositive are true.

+ 1 = 2, then 10 > 3,” the converse
For the sentence “If 1√
√ and contrapositive are, respectively, “If 10 > 3, then 1 + 1 = 2 ” and “If 10 is not greater
than 3, then 1 + 1 is not equal to 2.” In this example, all three sentences are true.
The previous two examples suggest that the truth values of a conditional sentence and its contrapositive are related, but there seems to be little connection
between the truth values of P ⇒ Q and its converse. We describe the relationships
in the following theorem.
Theorem 1.2.1
For propositions P and Q,
(a)
(b)
P ⇒ Q is equivalent to its contrapositive (∼Q) ⇒ (∼P).
P ⇒ Q is not equivalent to its converse Q ⇒ P.
Proof. The proofs are carried out by examination of the truth tables.
P
Q
P⇒Q
∼P
∼Q
(∼Q ) ⇒ (∼P )
Q⇒P
T
F
T
F
T
T
F
F
T
T
F
T
F
T
F
T
F
F
T
T
T
T
F
T
T
F
T
T
62025_01_ch01_p001-070.qxd
12
CHAPTER 1
4/22/10
1:42 AM
Page 12
Logic and Proofs
(a)
(b)
P ⇒ Q is equivalent to (∼Q) ⇒ (∼P) because the third column in the truth
table is identical to the sixth column in the table.
P ⇒ Q is not equivalent to Q ⇒ P because column 3 in the truth table differs from column 7 in rows 2 and 3.

We have seen cases where a conditional sentence and its converse have the
same truth value. Theorem 1.2.1(b) simply says that this need not always be the
case—the truth values of P ⇒ Q cannot be inferred from its converse Q ⇒ P.
The next connective we need is the biconditional connective ⇐
⇒. The double
arrow ⇐
⇒ reminds one of both ⇐ and ⇒, and this is no accident, because P ⇐
⇒Q
is equivalent to (P ⇒ Q) ∧ (Q ⇒ P).
DEFINITION For propositions P and Q, the biconditional sentence
P⇐
⇒ Q is the proposition “P if and only if Q.” P ⇐
⇒ Q is true exactly
when P and Q have the same truth values. We also write P iff Q to abbreviate P if and only if Q.
The truth table for P ⇐
⇒ Q is
P
Q
P⇐
⇒Q
T
F
T
F
T
T
F
F
T
F
F
T
Examples. The proposition “23 = 8 iff 49 is a perfect
√ square” is true because both
components are true. The proposition “π = 22/7 iff 2 is a rational number” is true
because both components are false. The proposition “6 + 1 = 7 iff Lake Michigan
is in Kansas” is false because the truth values of the components differ.
Definitions, fully stated with the “if and only if” connective, are important
examples of biconditional sentences because they describe exactly the condition(s)
to meet the definition. Although sometimes a definition does not explicitly use the
iff wording, biconditionality does provide a good test of whether a statement could
serve as a definition or just a description.
Example. The statement “Vertical lines have undefined slope” could be used as a
definition because a line is vertical iff its slope is undefined. However, “A zebra is
a striped animal” is not a definition, because the sentence “An animal is a zebra iff
the animal is striped” is false.
Because the biconditional sentence P ⇐
⇒ Q is true exactly when the truth
values of P and Q agree, we can use the biconditional connective to restate the
meaning of equivalent propositional forms:
62025_01_ch01_p001-070.qxd
4/22/10
1:42 AM
Page 13
1.2
Conditionals and Biconditionals
13
The propositional forms P and Q are equivalent precisely when P ⇐
⇒ Q is a
tautology.
Thus each statement in Theorem 1.1.1 may be restated using the ⇐
⇒ connective. For example, DeMorgan’s Laws are:
∼( P ∧ Q) ⇐
⇒ (∼P ∨ ∼Q) and
∼( P ∨ Q) ⇐
⇒ (∼P ∧ ∼Q).
All of the statements in Theorem 1.1.1 are used regularly in proofs. The next theorem contains several additional important pairs of equivalent propositional forms
that involve implication. They, too, will be used often.
Theorem 1.2.2
For propositions P, Q, and R,
(a)
(b)
(c)
(d)
(e)
(f)
(g)
P ⇒ Q is equivalent to ∼P ∨ Q.
P⇐
⇒ Q is equivalent to (P ⇒ Q) ∧ (Q ⇒ P).
∼(P ⇒ Q) is equivalent to P ∧ ∼Q.
∼(P ∧ Q) is equivalent to P ⇒ ∼Q and to Q ⇒ ∼P.
P ⇒ (Q ⇒ R) is equivalent to (P ∧ Q) ⇒ R.
P ⇒ (Q ∧ R) is equivalent to (P ⇒ Q) ∧ ( P ⇒ R).
(P ∨ Q) ⇒ R is equivalent to (P ⇒ R) ∧ (Q ⇒ R).
Exercise 8 asks you to prove each part of Theorem 1.2.2. The natural way to
proceed is by constructing and then comparing truth tables, but you should also
think about the meaning of both sides of each statement of equivalence. With part
(a), for example, we reason as follows: P ⇒ Q is false exactly when P is true and
Q is false, which happens exactly when both ∼P and Q are false. Since this happens
exactly when ∼P ∨ Q is false, the truth tables for P ⇒ Q and ∼P ∨ Q are identical.
Note that many of the statements in Theorems 1.1.1 and 1.2.2 are related. For
example, once we have established Theorem 1.1.1 and 1.2.2(a), we reason that part
(c) is correct as follows:
∼(P ⇒ Q) is equivalent, by part (a), to
∼ (∼P ∨ Q), which is equivalent, by Theorem 1.1.1(i), to
∼ (∼P) ∧ ∼Q, which is equivalent, by Theorem 1.1.1(a), to
P ∧ ∼Q.
Recognizing the structure of a sentence and translating the sentence into symbolic form using logical connectives are aids in determining its truth or falsity. The
translation of sentences into propositional symbols is sometimes very complicated
because some natural languages such as English are rich and powerful with many
nuances. The ambiguities that we tolerate in English would destroy structure and
usefulness if we allowed them in mathematics.
Even the translations of simple sentences can present special problems. Suppose a teacher says to a student
“If you score 74% or higher on the next test, you will pass this course.”
62025_01_ch01_p001-070.qxd
14
CHAPTER 1
4/22/10
1:42 AM
Page 14
Logic and Proofs
This sentence clearly has the form of a conditional sentence, although almost everyone will interpret the meaning as a biconditional.
Contrast this with the situation in mathematics where “If x = 2, then x is a
solution to x 2 = 2x” must have only the meaning of the connective ⇒, because
x 2 = 2x does not imply x = 2.
Shown below are some phrases in English that are ordinarily translated by
⇒. In the accompanying examples, think of a and t as
using the connectives ⇒ or ⇐
fixed real numbers.
Use P ⇒ Q to translate:
Examples:
If P, then Q.
P implies Q.
P is sufficient for Q.
P only if Q.
Q, if P.
Q whenever P.
Q is necessary for P.
Q, when P.
If a > 5, then a > 3.
a > 5 implies a > 3.
a > 5 is sufficient for a > 3.
a > 5 only if a > 3.
a > 3, if a > 5.
a > 3 whenever a > 5.
a > 3 is necessary for a > 5.
a > 3, when a > 5.
⇒ Q to translate:
Use P ⇐
Examples:
P if and only if Q.
P if, but only if, Q.
P is equivalent to Q.
P is necessary and sufficient for Q.
|t |
|t|
|t|
|t|
= 2 if and only if t2 = 4.
= 2 if, but only if, t 2 = 4.
= 2 is equivalent to t 2 = 4.
= 2 is necessary and sufficient
for t 2 = 4.
The word unless is one of those connective words in English that poses special
problems because it has so many different interpretations. See Exercise 11.
Examples. In these sentence translations, we assume that S, G, and e have been
specified. It is not necessary to know the meanings of all the words because the
form of the sentence is sufficient to determine the correct translation.
“S is compact is sufficient for S to be bounded” is translated
S is compact ⇒ S is bounded.
“A necessary condition for a group G to be cyclic is that G is abelian” is
translated
G is cyclic ⇒ G is abelian.
“A set S is infinite if S has an uncountable subset” is translated
S has an uncountable subset ⇒ S is infinite.
“A necessary and sufficient condition for the graph G to be a tree is that
G is connected and every edge of G is a bridge” is translated
⇒ (G is connected ¿ every edge of G is a bridge).
G is a tree ⇐
Example. If we let P denote the proposition “Roses are red” and Q denote the
proposition “Violets are blue,” we can translate the sentence “It is not the case that
62025_01_ch01_p001-070.qxd
4/22/10
1:42 AM
Page 15
1.2
Conditionals and Biconditionals
15
roses are red, nor that violets are blue” in at least two ways: ∼(P ∨ Q) or
(∼P) ∧ (∼Q). Fortunately, these are equivalent by Theorem 1.1.1(h). Note that the
proposition “Violets are purple” requires a new symbol, say R, since it expresses a
new idea that cannot be formed from the components P and Q.
The sentence “17 and 35 have no common divisors” shows that the meaning,
and not just the form of the sentence, must be considered in translating; it cannot be
broken up into the two propositions: “17 has no common divisors” and “35 has no
common divisors.” Compare this with the proposition “17 and 35 have digits totaling 8,” which can be written as a conjunction.
Example. Suppose b is a fixed real number. The form of the sentence “If b is an
integer, then b is either even or odd” is P ⇒ (Q ∨ R), where P is “b is an integer,”
Q is “b is even,” and R is “b is odd.”
Example. Suppose a, b, and p are fixed integers. “If p is a prime number that
divides ab, then p divides a or b” has the form (P ∧ Q) ⇒ (R ∨ S), where P is “p
is a prime,” Q is “p divides ab,” R is “p divides a,” and S is “p divides b.”
The hierarchy of connectives in Section 1.1 that governs the use of parentheses
for propositional forms can be extended to the connectives ⇒ and ⇐
⇒:
The connectives ∼, ∧, ∨, ⇒, and ⇐
⇒ are always applied in the order listed.
Thus, ∼ applies to the smallest possible proposition, then ¿ is applied with the next
smallest scope, and so forth. For example,
P ⇒ ∼Q ∨ R ⇐
⇒ S is an abbreviation for (P ⇒ [(∼Q ) ∨ R]) ⇐
⇒ S,
P ∨ ∼Q ⇐
⇒ R ⇒ S is an abbreviation for [P ∨ (∼Q)] ⇐
⇒ (R ⇒ S),
and
P ⇒ Q ⇒ R is an abbreviation for (P ⇒ Q) ⇒ R.
Exercises 1.2
1. Identify the antecedent and the consequent for each of the following conditional sentences. Assume that a, b, and f represent some fixed sequence,
integer, or function, respectively.

(b) If the moon is made of cheese, then 8 is an irrational number.
(c) b divides 3 only if b divides 9.

(e) A sequence a is bounded whenever a is convergent.

(g) 1 + 2 = 3 is necessary for 1 + 1 = 2.
62025_01_ch01_p001-070.qxd
16
CHAPTER 1
4/22/10
1:42 AM
Page 16
Logic and Proofs

(h) The fish bite only when the moon is full.

Olympic team.
2. Write the converse and contrapositive of each conditional sentence in Exercise 1.
3. What can be said about the truth value of Q when
(a) P is false and P ⇒ Q is true? (b) P is true and P ⇒ Q is true?
⇒ Q is true?
(c) P is true and P ⇒ Q is false? (d) P is false and P ⇐
⇒ Q is false?
(e) P is true and P ⇐
4. Identify the antecedent and consequent for each conditional sentence in the
following statements from this book.
(a) Theorem 1.3.1(a)
(b) Exercise 3 of Section 1.6
(c) Theorem 2.1.4
(d) The PMI, Section 2.4
(e) Theorem 2.6.4
(f) Theorem 3.4.2
(g) Theorem 4.2.2
(h) Theorem 5.1.7(a)
5. Which of the following conditional sentences are true?

(b) If a hexagon has six sides, then the moon is made of cheese.

(d) If 5 < 2, then 10 < 7. 多 (e) If one interior angle of a right triangle is 92°, then the other interior angle is 88°. (f) If Euclid’s birthday was April 2, then rectangles have four sides. √ (g) 5 is prime if 2 is not irrational. (h) 1 + 1 = 2 is sufficient for 3 > 6.
6. Which of the following are true?

(b) 7 + 5 = 12 iff 1 + 1 = 2.

(d) m is odd iff m2 is odd. (Assume that m is some fixed integer.)
(e) 5 + 6 = 6 + 5 iff 7 + 1 = 10.
(f) A parallelogram has three sides iff 27 is prime.
(g) The Eiffel Tower is in Paris if and only if the chemical symbol for
helium
is√H.

10 + 13 < 11 + 12 iff 13 − 12 < 11 − 10. (h) (i) x 2 ≥ 0 iff x ≥ 0. (Assume that x is a fixed real number.) (j) x 2 − y 2 = 0 iff (x − y)(x + y) = 0. (Assume that x and y are fixed real numbers.) (k) x 2 + y 2 = 50 iff (x + y) 2 = 50. (Assume that x and y are fixed real numbers.) 7. Make truth tables for these propositional forms. ⇒ P). (a) P ⇒ (Q ∧ P). 多 (b) (∼P ⇒ Q) ∨ (Q ⇐ ⇒ P). 多 (c) ∼Q ⇒ (Q ⇐ (d) (P ∨ Q) ⇒ (P ∧ Q). (e) (P ∧ Q) ∨ (Q ∧ R) ⇒ P ∨ R. (f) [(Q ⇒ S) ∧ ( Q ⇒ R)] ⇒ [(P ∨ Q) ⇒ ( S ∨ R)]. Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. 62025_01_ch01_p001-070.qxd 4/22/10 1:42 AM Page 17 1.2 Conditionals and Biconditionals 17 8. Prove Theorem 1.2.2 by constructing truth tables for each equivalence. 9. Determine whether each statement qualifies as a definition. (a) y = f (x) is a linear function when its graph is a straight line. (b) y = f (x) is a quadratic function when it contains an x 2 term. (c) m is a perfect square when m = n2 for some integer n. (d) A triangle is a right triangle when the sum of two of its interior angles is 90°. (e) Two lines are parallel when their slopes are the same number. (f) A sundial is an instrument for measuring time. 10. Rewrite each of the following sentences using logical connectives. Assume that each symbol f, x0, n, x, S, B represents some fixed object. 多 (a) If f has a relative minimum at x0 and if f is differentiable at x0, then f (x0) = 0. (b) If n is prime, then n = 2 or n is odd. (c) A number x is real and not rational whenever x is irrational. 多 (d) If x = 1 or x = −1, then |x| = 1. 多 (e) f has a critical point at x0 iff f (x0 ) = 0 or f (x0 ) does not exist. (f) S is compact iff S is closed and bounded. (g) B is invertible is a necessary and sufficient condition for det B = 0. (h) 6 ≥ n − 3 only if n > 4 or n > 10.
(i) x is Cauchy implies x is convergent.
(j) f is continuous at x0 whenever lim f (x) = f ( x0).
x→x0
11.

12.

13.

14.
(k) If f is differentiable at x0 and f is strictly increasing at x0, then f (x0) > 0.
Dictionaries indicate that the conditional meaning of unless is preferred, but
there are other interpretations as a converse or a biconditional. Discuss the
translation of each sentence.
(a) I will go to the store unless it is raining.
(b) The Dolphins will not make the playoffs unless the Bears win all the rest
of their games.
(c) You cannot go to the game unless you do your homework first.
(d) You won’t win the lottery unless you buy a ticket.
Show that the following pairs of statements are equivalent.
(a) (P ∨ Q) ⇒ R and ∼R ⇒ (∼P ∧ ∼Q).
(b) (P ∧ Q) ⇒ R and (P ∧ ∼R) ⇒ ∼Q.
(c) P ⇒ (Q ∧ R) and (∼Q ∨ ∼R) ⇒ ∼P.
(d) P ⇒ (Q ∨ R) and ( P ∧ ∼R) ⇒ Q.
(e) (P ⇒ Q) ⇒ R and (P ∧ ∼Q) ∨ R.
⇒ Q and (∼P ∨ Q) ∧ (∼Q ∨ P).
(f) P ⇐
Give, if possible, an example of a true conditional sentence for which
(a) the converse is true.
(b) the converse is false.
(c) the contrapositive is false.
(d) the contrapositive is true.
Give, if possible, an example of a false conditional sentence for which
(a) the converse is true.
(b) the converse is false.
(c) the contrapositive is false.
(d) the contrapositive is true.
62025_01_ch01_p001-070.qxd
18
CHAPTER 1
4/22/10
1:42 AM
Page 18
Logic and Proofs
15. Give the converse and contrapositive of each sentence of Exercises 10(a), (b),
(c), and (d). Tell whether each converse and contrapositive is true or false.
16. Determine whether each of the following is a tautology, a contradiction, or neither.

⇒ P ∧ (P ∨ Q).
(b) P ⇐
⇒ P ∧ ∼Q.
(c) P ⇒ Q ⇐

⇒ P.
(e) P ∧ (Q ∨ ∼Q) ⇐
(f) [Q ∧ (P ⇒ Q)] ⇒ P.
⇒ Q) ⇐
⇒ ∼(∼P ∨ Q) ∨ (∼P ∧ Q).
(g) (P ⇐
(h) [P ⇒ (Q ∨ R)] ⇒ [(Q ⇒ R) ∨ (R ⇒ P)].
⇒ Q) ∧ ∼Q.
(i) P ∧ (P ⇐
(j) (P ∨ Q) ⇒ Q ⇒ P.
(k) [P ⇒ (Q ∧ R)] ⇒ [R ⇒ ( P ⇒ Q)].
(l) [P ⇒ (Q ∧ R)] ⇒ R ⇒ (P ⇒ Q).
17. The inverse, or opposite, of the conditional sentence P ⇒ Q is ∼P ⇒ ∼Q.
(a) Show that P ⇒ Q and its inverse are not equivalent forms.
(b) For what values of the propositions P and Q are P ⇒ Q and its inverse
both true?
(c) Which is equivalent to the converse of a conditional sentence, the contrapositive of its inverse, or the inverse of its contrapositive?
1.3
Quantifiers
Unless there has been a prior agreement about the value of x, the statement “x ≥ 3” is
neither true nor false. A sentence that contains variables is called an open sentence or
predicate, and becomes a proposition only when its variables are assigned specific values. For example, “x ≥ 3” is true when x is given the value 7 and false when x = 2.
When P is an open sentence with a variable x, the sentence is symbolized by
P(x). Likewise, if P has variables x1, x2, x3, Á , xn, the sentence may be denoted by
P(x1, x2, x3, Á , xn). For example, for the sentence “x + y = 3z” we write P(x, y, z),
and we see that P(4, 5, 3) is true because 4 + 5 = 3(3), while P(1, 2, 4) is false.
The collection of objects that may be substituted to make an open sentence a
true proposition is called the truth set of the sentence. Before a truth set can be
determined, we must be given or must decide what objects are available for consideration; that is, we must have specified a universe of discourse. In many cases the
universe will be understood from the context. For a sentence such as “x likes chocolate,” the universe is presumably the set of all people. We will often use the number
systems ⺞, ⺪, ⺡, ⺢, and ⺓ as our universes. (See the Preface to the Student.)
Example. The truth set of the open sentence “x2 < 5” depends upon the collection of objects we choose for the universe of discourse. With the universe specified as the set ⺞, the truth set is {1, 2}. For the universe ⺪, the truth set {−2, −1, 0, 1, 2}. √ is √ When the universe is ⺢, the truth set is the open interval (− 5, 5). Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. 62025_01_ch01_p001-070.qxd 4/22/10 1:42 AM Page 19 1.3 Quantifiers 19 DEFINITION With a universe specified, two open sentences P(x) and Q(x) are equivalent iff they have the same truth set. Examples. The sentences “3x + 2 = 20” and “x = 6” are equivalent open sentences in any of the number systems we have named. On the other hand, “x 2 = 4” and “x = 2” are not equivalent when the universe is ⺢. They are equivalent when the universe is ⺞. The notions of truth set, universe, and equivalent open sentences should not be new concepts for you. Solving an equation such as (x 2 + 1)(x − 3) = 0 is a matter of determining what objects x make the open sentence “(x 2 + 1)(x − 3) = 0” true. For the universe ⺢, the only solution is x = 3 and thus the truth set is {3}. But if we choose the universe to be ⺓, the equation may be replaced by the equivalent open sentence (x + i)(x − i)(x − 3) = 0, which has truth set (solutions) {3, i, −i}. A sentence such as “There is a prime number between 5060 and 5090” is treated differently from the propositions we considered earlier. To determine whether this sentence is true in the universe ⺞, we might try to individually examine every natural number, checking whether it is a prime and between 5060 and 5090, until we eventually find any one of the primes 5077, 5081, or 5087 and conclude that the sentence is true. (A quicker way is to search through a complete list of the first thousand primes.) The key idea here is that although the open sentence “x is a prime number between 5060 and 5090” is not a proposition, the sentence “There is a number x such that x is a prime number between 5060 and 5090” does have a truth value. This sentence is formed from the original open sentence by applying a quantifier. DEFINITION For an open sentence P (x), the sentence (E x) P (x) is read “There exists x such that P (x)” or “For some x, P (x).” The sentence (E x) P (x) is true iff the truth set of P(x) is nonempty. The symbol E is called the existential quantifier. An open sentence P (x) does not have a truth value, but the quantified sentence (E x) P (x) does. One way to show that (E x) P (x) is true for a particular universe is to identify an object a in the universe such that the proposition P (a) is true. To show (E x) P (x) is false, we must show that the truth set of P (x) is empty. Examples. (a) (b) (c) Let’s examine the truth values of these statements for the universe ⺢: (Ex)(x ≥ 3) (Ex)(x 2 = 0) (Ex)(x 2 = −1) Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. 62025_01_ch01_p001-070.qxd 20 CHAPTER 1 4/22/10 1:42 AM Page 20 Logic and Proofs Statement (a) is true because the truth set of x ≥ 3 contains 3, 7.02, and many other real numbers. Thus the truth set contains at least one real number. Statement (b) is true because the truth set of x 2 = 0 is precisely {0} and thus is nonempty. Since the open sentence x 2 = −1 is never true for real numbers, the truth set of x 2 = −1 is empty. Statement (c) is false. In the universe ⺞, only statement (a) is true. The three statements are all true in the universe {0, 5, i} and all three statements are false in the universe {1, 2}. Sometimes we can say (E x) P (x) is true even when we do not know a specific object in the universe in the truth set of P(x), only that there (at least) is one. Example. Show that ( Ex)(x 7 − 12x 3 + 16x − 3 = 0) is true in the universe of real numbers. For the polynomial f (x) = x 7 − 12x 3 + 16x − 3, f (0) = −3 and f (1) = 2. From calculus, we know that f is continuous on [0, 1]. The Intermediate Value Theorem tells us there is a zero for f between 0 and 1. Even if we don’t know the exact value of the zero, we know it exists. Therefore, the truth set of x 7 − 12x 3 + 16x − 3 = 0 is nonempty. Hence (Ex)(x 7 − 12x 3 + 16x − 3 = 0) is true. The sentence “The square of every number is greater than 3” uses a different quantifier for the open sentence “x2 > 3.” To decide the truth value of the given
sentence in the universe ⺞ it is not enough to observe that 32 > 3, 42 > 3, and so
on. In fact, the sentence is false in ⺞ because 1 is in the universe but not in the truth
set. The sentence is true, however, in the universe [1.74, ∞ ) because with this universe the truth set for x2 > 3 is the same as the universe.
DEFINITION For an open sentence P( x), the sentence (∀x) P (x) is read
“For all x, P (x)” and is true iff the truth set of P(x) is the entire universe.
The symbol ∀ is called the universal quantifier.
Examples. For the universe of all real numbers,
(∀x)(x + 2 > x) is true.
(∀x)(x > 0 ∨ x = 0 ∨ x < 0) is true. That is, every real number is positive, zero or negative. (∀x)(x ≥ 3) is false because there are (many) real numbers x for which x ≥ 3 is false. (∀x)(|x| > 0) is false, because 0 is not in the truth set.
There are many ways to express a quantified sentence in English. Look for key
words such as “for all,” “for every,” “for each,” or similar words that require universal quantifiers. Look for phrases such as “some,” “at least one,” “there exist(s),”
“there is (are),” and others that indicate existential quantifiers.
You should also be alert for hidden quantifiers because natural languages allow for
imprecise quantified statements where the words “for all” and “there exists” are not
62025_01_ch01_p001-070.qxd
4/22/10
1:42 AM
Page 21
1.3 Quantifiers
21
present. Someone who says “Polynomial functions are continuous” means that “All
polynomial functions are continuous,” but someone who says “Rational functions have
vertical asymptotes” must mean “Some rational functions have vertical asymptotes.”
We agree that “All apples have spots” is quantified with ∀, but what form does
it have? If we limit the universe to just apples, a correct symbolization would be
(∀x)(x has spots). But if the universe is all fruits, we need to be more careful. Let
A(x) be “x is an apple” and S(x) be “x has spots.” Should we write the sentence as
(∀x)[A(x) ∧ S( x)] or (∀x)[A(x) ⇒ S( x)]?
The first quantified form, (∀x)[A( x) ∧ S(x)], says “For all objects x in the universe, x is an apple and x has spots.” Since we don’t really intend to say that all fruits are
spotted apples, this is not the meaning we want. Our other choice, ( ∀x)[A(x) ⇒ S(x)],
is the correct one because it says “For all objects x in the universe, if x is an apple then
x has spots.” In other words, “If a fruit is an apple, then it has spots.”
Now consider “Some apples have spots.” Should this be (Ex)[A(x) ∧ S( x)] or
(Ex)[A(x) ⇒ S(x)]? The first form says “There is an object x such that it is an apple
and it has spots,” which is correct. On the other hand, (Ex)[A( x) ⇒ S(x)] reads
“There is an object x such that, if it is an apple, then it has spots,” which does not
ensure the existence of apples with spots. The sentence (Ex)[A( x) ⇒ S( x)] is true
in every universe for which there is an object x such that either x is not an apple or
x has spots, which is not the meaning we want.
In general, a sentence of the form “All P (x) are Q (x)” should be symbolized
( ∀x)[P(x) ⇒ Q( x)]. And, in general, a sentence of the form “Some P (x) are Q (x)”
should be symbolized ( Ex)[P(x) ∧ Q( x)].
Examples. The sentence “For every odd prime x less than 10, x 2 + 4 is prime”
means that if x is prime, and odd, and less than 10, then x 2 + 4 is prime. It is written symbolically as
(∀x)(x is prime ∧ x is odd ∧ x < 10 ⇒ x2 + 4 is prime). The sentence “Some functions defined at 0 are not continuous at 0” can be written symbolically as (E f )( f is defined at 0 ∧ f is not continuous at 0). Example. The sentence “Some real numbers have a multiplicative inverse” could be symbolized (Ex)(x is a real number ∧ x has a real multiplicative inverse). However, “x has an inverse” means there is some number that is an inverse for x (hidden quantifier), so a more complete symbolic translation is (Ex)[x is a real number ∧ (Ey)( y is a real number ∧ xy = 1)]. Example. One correct translation of “Some integers are even and some integers are odd” is ( Ex)(x is even) ∧ ( Ex)(x is odd) Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. 62025_01_ch01_p001-070.qxd 22 CHAPTER 1 4/22/10 1:42 AM Page 22 Logic and Proofs because the first quantifier (Ex) extends only as far as the word “even.” After that, any variable (even x again) may be used to express “some are odd.” It would be equally correct and sometimes preferable to write (Ex)(x is even) ∧ ( Ey)(y is odd), but it would be wrong to write (Ex)(x is even ∧ x is odd), because there is no integer that is both even and odd. Several of our essential definitions given in the Preface to the Student are in fact quantified statements. For example, the definition of a rational number may be symbolized: r is a rational number iff (Ep)( Eq)( p 僆 ⺪ ∧ q 僆 ⺪ ∧ q = 0 ∧ r = q B p Statements of the form “Every element of the set A has the property P” and “Some element of the set A has property P” occur so frequently that abbreviated symbolic forms are desirable. “Every element of the set A has the property P” could be restated as “If x 僆 A, then . . .” and symbolized by (∀x 僆 A) P (x). “Some element of the set A has property P” is abbreviated by ( Ex 僆 A) P (x). Examples. The definition of a rational number given above may be written as r is a rational number iff (Ep 僆 ⺪)( Eq 僆 ⺪)(q = 0 ∧ r = q B . p The statement “For every rational number there is a larger integer” may be symbolized by (∀x)[x 僆 ⺡ ⇒ ( Ez)(z 僆 ⺪ and z > x)]
or
(∀x 僆 ⺡)(Ez 僆 ⺪)(z > x).
DEFINITION Two quantified sentences are equivalent in a given
universe iff they have the same truth value in that universe. Two quantified sentences are equivalent iff they are equivalent in every universe.
Example. (∀x)(x > 3) and ( ∀x)(x ≥ 4) are equivalent in the universe of integers
(because both are false), the universe of natural numbers greater than 10 (because
both are true), and in many other universes. However, if we chose a number
between 3 and 4, say 3.7, and let U be the universe of real numbers larger than 3.7,
62025_01_ch01_p001-070.qxd
4/22/10
1:42 AM
Page 23
1.3 Quantifiers
23
then (∀x)(x > 3) is true and ( ∀x)(x ≥ 4) is false in U. The sentences are not equivalent in this universe, so they are not equivalent sentences.
As was noted with propositional forms, it is necessary to make a distinction
between a quantified sentence and its logical form. With the universe all integers, the sentence “All integers are odd” is an instance of the logical form
(∀x) P (x), where P( x) is “x is odd.” The form itself, (∀x) P (x), is neither true nor
false, but becomes false when “x is odd” is substituted for P( x) and the universe
is all integers.
The pair of quantified forms (Ex)([P(x) ∧ Q( x)] and ( Ex)([Q( x) ∧ P(x)] are
equivalent because for any choices of P and Q, P ∧ Q and Q ∧ P are equivalent
propositional forms. Another pair of equivalent sentences is (∀x)[P(x) ⇒ Q(x)]
and (∀x)[∼Q(x) ⇒ ∼P(x)].
The next two equivalences are essential for reasoning about quantifiers.
Theorem 1.3.1
If A(x) is an open sentence with variable x, then
(a)
(b)
∼(∀x) A (x) is equivalent to ( Ex) ∼A(x).
∼(Ex) A (x) is equivalent to (∀x) ∼A(x).
Proof.
(a)
Let U be any universe.
The sentence ∼(∀x) A (x) is true in U
iff (∀x) A (x) is false in U
iff the truth set of A(x) is not the universe
iff the truth set of ∼ A(x) is nonempty
iff (Ex) ∼A(x) is true in U.
(b)
The proof of this part is Exercise 7.

Theorem 1.3.1 is helpful for finding useful denials (that is, simplified forms of
negations) of quantified sentences. For example, in the universe of natural numbers,
the sentence “All primes are odd” is symbolized (∀x)(x is prime ⇒ x is odd). The
negation is ∼(∀x)(x is prime ⇒ x is odd). By applying Theorem 1.3.1(a), this
becomes (Ex)[∼(x is prime ⇒ x is odd)]. By Theorem 1.2.2(c) this is equivalent to
(Ex)[x is prime ∧ ∼(x is odd)]. We read this last statement as “There exists a number that is prime and is not odd” or “Some prime number is even.”
Example. A simplified denial of (∀x)(Ey)(Ez)(∀u)(Ev)(x + y + z > 2u + v)
begins with its negation
‘ (∀x)(Ey)(Ez)(∀u)(Ev)(x + y + z > 2u + v).
After 5 applications of Theorem 1.3.1, beginning with the outermost quantifier
(∀x), we arrive at the simplified form
(E x)(∀y)(∀z)(Eu)(∀v)(x + y + z ≤ 2u + v).
Example. For the universe of all real numbers, find a denial of “Every positive
real number has a multiplicative inverse.”
62025_01_ch01_p001-070.qxd
24
CHAPTER 1
4/22/10
1:42 AM
Page 24
Logic and Proofs
The sentence is symbolized (∀x)[x > 0 ⇒ (Ey)(xy = 1)]. The negation and
successively rewritten equivalents are:
∼( ∀x)[x > 0 ⇒ (Ey)(xy = 1)]
(Ex) ∼[x > 0 ⇒ (Ey)(xy = 1)]
(Ex)[x > 0 ∧ ∼ (Ey)(xy = 1)]
(Ex)[x > 0 ∧ (∀y) ∼(xy = 1)]
(Ex)[x > 0 ∧ (∀y)(xy = 1)]
This last sentence may be translated as “There is a positive real number that has no
multiplicative inverse.”
Example. For the universe of living things, find a denial of “Some children do not
like clowns.”
The sentence is (Ex) [x is a child ∧ (∀y) (y is a clown ⇒ x does not like y)]. Its
negation and several equivalents are:
∼ (Ex) [x is a child ∧ (∀y)(y is a clown ⇒ x does not like y)]
(∀x) ∼ [x is a child ∧ (∀y)(y is a clown ⇒ x does not like y)]
(∀x) [x is a child ⇒ ∼(∀y)(y is a clown ⇒ x does not like y)]
(∀x) [x is a child ⇒ (Ey) ∼( y is a clown ⇒ x does not like y)]
(∀x) [x is a child ⇒ (Ey)(y is a clown ∧ ∼ x does not like y)]
(∀x) [x is a child ⇒ (Ey)(y is a clown ∧ x likes y)]
The denial we seek is “Every child has some clown that he/she likes.”
We sometimes hear statements like the complaint one fan had after a great Little
League baseball game. “The game was fine,” he said, “but everybody didn’t get to
play.” We easily understand that the fan did not mean this literally, because otherwise
there would have been no game. The meaning we understand is “Not everyone got to
play” or “Some team members did not play.” Such misuse of quantifiers, while tolerated in casual conversations, is always to be avoided in mathematics.
The E! quantifier, defined next, is a special case of the existential quantifier.
DEFINITION For an open sentence P (x), the proposition ( E!x) P (x) is
read “there exists a unique x such that P(x)” and is true iff the truth set
of P (x) has exactly one element. The symbol E! is called the unique existential quantifier.
62025_01_ch01_p001-070.qxd
4/22/10
1:42 AM
Page 25
1.3 Quantifiers
25
Recall that for (E x) P (x) to be true it is unimportant how many elements are in
the truth set of P(x), as long as there is at least one. For (E!x) P (x) to be true, the
number of elements in the truth set of P(x) is crucial—there must be exactly one.
In the universe of natural numbers, (E!x) (x is even and x is prime) is true
because the truth set of “x is even and x is prime” contains only the number 2. The
sentence (E!x)(x 2 = 4) is true in the universe of natural numbers, but false in the
universe of all integers.
Theorem 1.3.2
If A(x) is an open sentence with variable x, then
(a)
(b)
(E!x) A(x) ⇒ (Ex) A(x).
(E!x) A(x) is equivalent to (Ex) A(x) ∧ ( ∀y)(∀z)(A( y) ∧ A(z) ⇒ y = z).
Part (a) of Theorem 1.3.2 says that E! is indeed a special case of the quantifier
E . Part (b) says that “There exists a unique x such that A(x)” is equivalent to “There
is an x such that A(x) and if both A( y) and A(z), then y = z.” The proofs are left to
Exercise 11.
Exercises 1.3

1. Translate the following English sentences into symbolic sentences with quantifiers. The universe for each is given in parentheses.

(b) All precious stones are not beautiful. (All stones)
(c) Some isosceles triangle is a right triangle. (All triangles)
(d) No right triangle is isosceles. (All triangles)
(e) All people are honest or no one is honest. (All people)
(f) Some people are honest and some people are not honest. (All people)
(g) Every nonzero real number is positive or negative. (Real numbers)

(i) Every integer is greater than some integer. (Integers)

(k) Between any integer and any larger integer, there is a real number. (Real
numbers)

(n) Everybody loves someone. (All people)
(o) For every positive real number x, there is a unique real number y such
that 2 y = x. (Real numbers)
2. For each of the propositions in Exercise 1, write a useful denial, and give a
translation into ordinary English.
3. Translate these definitions from the Preface to the Student into quantified
sentences.
(a) The integer x is even.
(b) The integer x is odd.
62025_01_ch01_p001-070.qxd
26
CHAPTER 1
4/22/10
1:42 AM
Page 26
Logic and Proofs
4.

5.
6.

(c) The integer a divides the integer b.
(d) The natural number n is prime.
(e) The natural number n is composite.
Translate these definitions in this text into quantified sentences. You need not
know the specifics of the terms and symbols to complete this exercise.
(a) The relation R is symmetric. (See page 147.)
(b) The relation R is transitive. (See page 147.)
(c) The function f is one-to-one. (See page 208.)
(d) The operation * is commutative. (See page 277.)
The sentence “People dislike taxes” might be interpreted to mean “All people
dislike all taxes,” “All people dislike some taxes,” “Some people dislike all
taxes,” or “Some people dislike some taxes.” Give a symbolic translation for
each of these interpretations.
Let T = {17}, U = {6}, V = {24}, and W = {2, 3, 7, 26}. In which of these
four different universes is the statement true?
a) (Ex) (x is odd ⇒ x > 8).
b) (Ex) (x is odd ∧ x > 8).
(∀x) (x is odd ⇒ x > 8).
c)
d) (∀x) (x is odd ∧ x > 8).
7. (a)

8.

Complete this proof of Theorem 1.3.1(b):
Proof: Let U be any universe.
The sentence ∼ (Ex) A(x) is true in U
iff . . .
iff (∀x) ∼ A(x) is true in U.
(b) Give a proof of part (b) of Theorem 1.3.1 that uses part (a).
Which of the following are true? The universe for each statement is given in
parentheses.
(a) (∀x)(x + x ≥ x). (⺢)
(b) (∀x)(x + x ≥ x). (⺞)
(c) (Ex)(2x + 3 = 6x + 7). (⺞)
(d) (Ex)(3x = x 2). (⺢)
(e) (Ex)(3x = x). (⺢)
(f) (Ex)(3(2 − x) = 5 + 8(1 − x)). (⺢)
(g) (∀x)(x 2 + 6x + 5 ≥ 0). (⺢)
(h) (∀x)(x 2 + 4x + 5 ≥ 0). (⺢)
(i) (Ex)(x 2 − x + 41 is prime). (⺞)
(j) (∀x)(x 2 − x + 41 is prime). (⺞)
(k) (∀x)(x 3 + 17x 2 + 6x + 100 ≥ 0). (⺢)
(l) (∀x)(∀y)[x < y ⇒ (Ew)(x < w < y)]. (⺡) 9. Give an English translation for each. The universe is given in parentheses. (a) (∀x)(x ≥ 1). (⺞) 多 (b) (E!x)(x ≥ 0 ∧ x ≤ 0). (⺢) (c) (∀x)(x is prime ∧ x = 2 ⇒ x is odd). (⺞) 多 (d) (E!x)( loge x = 1). (⺢) Copyright 2011 Cengage Learning, Inc. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. 62025_01_ch01_p001-070.qxd 4/22/10 1:42 AM Page 27 1.4 10. 多 多 多 多 11. 夡 夡 Basic Proof Methods I 27 (e) ∼ (Ex)(x2 < 0). (⺢) (f) (E!x)(x2 = 0). (⺢) (g) (∀x)(x is odd ⇒ x2 is odd). (⺞) Which of the following are true in the universe of all real numbers? (a) (∀x)(Ey)(x + y = 0). (b) (Ex)(∀y)(x + y = 0). (c) (Ex)(Ey)(x2 + y2 = −1). (d) (∀x)[x > 0 ⇒ ( Ey)(y < 0 ∧ xy > 0)].
(e) (∀y)(Ex)(∀z)(xy = xz).
(f) (Ex)(∀y)(x ≤ y).
(g) (∀y)(Ex)(x ≤ y).
(h) (E!y)(y < 0 ∧ y + 3 > 0).
(i) (E!x)(∀y)(x = y2).
(j) (∀y)(E!x)(x = y2).
(k) (E!x)(E!y)(∀w)(w2 > x − y).
Let A(x) be an open sentence with variable x.
(a) Prove Theorem 1.3.2 (a).
(b) Show that the converse of Theorem 1.3.2 (a) is false.
(c) Prove Theorem 1.3.2 (b).
(d) Prove that ( E!x) A (x) is equivalent to (Ex)[A(x) ∧ (∀y)(A(y) ⇒ x = y)].
(e) Find a usef…

attachment

Tags:
real numbers

mathematical equations

Mathematical Values

Compute the values

arbitrary integers

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.

Reviews, comments, and love from our customers and community:

This page is having a slideshow that uses Javascript. Your browser either doesn't support Javascript or you have it turned off. To see this page as it is meant to appear please use a Javascript enabled browser.

Peter M.
So far so good! It's safe and legit. My paper was finished on time...very excited!
Sean O.N.
Experience was easy, prompt and timely. Awesome first experience with a site like this. Worked out well.Thank you.
Angela M.J.
Good easy. I like the bidding because you can choose the writer and read reviews from other students
Lee Y.
My writer had to change some ideas that she misunderstood. She was really nice and kind.
Kelvin J.
I have used other writing websites and this by far as been way better thus far! =)
Antony B.
I received an, "A". Definitely will reach out to her again and I highly recommend her. Thank you very much.