Pages From Gri2 PDF
Pages From Gri2 PDF
Pages From Gri2 PDF
of Logic
n the first chapter we derived a summation formula in Example 1.40 (Section 1.4). We
Iobtained this formula by counting the same collection of objects (the statements that were
executed in a certain program segment) in two different ways and then equating the results.
Consequently, we say that the formula was established by a combinatorial proof. This is
one of many different techniques for arriving at a proof.
In this chapter we take a close look at what constitutes a valid argument and a more
conventional proof. When a mathematician wishes to provide a proof for a given situation,
he or she must use a system of logic. This is also true when a computer scientist develops
the algorithms needed for a program or system of programs. The logic of mathematics is
applied to decide whether one statement follows from, or is a logical consequence of, one
or more other statements.
Some of the rules that govern this process are described in this chapter. We shall use these
rules in proofs (provided in the text and required in the exercises) throughout subsequent
chapters. However, at no time can we hope to arrive at a point at which we can apply the
rules in an automatic fashion. As in applying the counting ideas discussed in Chapter 1,
we should always analyze and seek to understand the situation given. This often calls for
attributes we cannot learn in a book, such as insight and creativity. Merely trying to apply
formulas or invoke rules will not get us very far either in proving results (such as theorems)
or in doing enumeration problems.
2.1
Basic Connectives and Truth Tables
In the development of any mathematical theory, assertions are made in the form of sen
tences. Such verbal or written assertions, called statements (orpropositions), are declarative
sentences that are either true or false but not both. For example, the following are state
ments, and we use the lowercase letters of the alphabet (such as p , q , and r) to represent
these statements.
47
48 Chapter 2 Fundamentals of Logic
is not a statement because its truth value (true or false) cannot be determined until a nu
merical value is assigned for x. If x were assigned the value 7, the result would be a true
statement. Assigning jt a value such as \/2 , or 7T, however, would make the resulting
statement false. (We shall encounter this type of situation again in Sections 2.4 and 2.5 of
this chapter.)
In the foregoing discussion, we mentioned the circumstances under which the compound
statements p v q, p )L q are considered true, on the basis of the truth of their components
p, q. This idea of the truth or falsity of a compound statement being dependent only on the
truth values of its components is worth further investigation. Tables 2.1 and 2.2 summarize
the truth and falsity of the negation and the different kinds of compound statements on the
basis of the truth values of their components. In constructing such truth tables, we write
0 for false and 1 for true.
>1
P -p p q pAq p v q p q p++q
0 1 0 0 0 0 0 l 1
1 0 0 1 0 1 1 l 0
1 0 0 1 1 0 0
1 1 1 1 0 i 1
The four possible truth assignments for p , q can be listed in any order. For later work,
the particular order presented here will prove useful.
We see that the columns of truth values for p and -p are the opposite of each other. The
statement p A q is true only when both /?, q are true, whereas p v q is false only when both
the component statements p , q are false. As we noted before, p) Lq is true when exactly
one of p, q is true.
For the implication p > q, the result is true in all cases except where p is true and q
is false. We do not want a true statement to lead us into believing something that is false.
However, we regard as true a statement such as If 2 + 3 = 6, then 2 + 4 = 7, even though
the statements 2 + 3 = 6 and 2 + 4 = 7 are both false.
Finally, the biconditional p q is true when the statements p , q have the same truth
value and is false otherwise.
Now that we have been introduced to certain concepts, let us investigate a little further
some of these initial ideas about connectives. Our first two examples should prove useful
for such an investigation.
The following English sentences provide possible translations for the given (symbolic)
compound statements.
a) (t A -*u) s: If the moon is out and it is not snowing, then Phyllis goes out for a
walk.
50 Chapter 2 Fundamentals of Logic
b) t o (--w o s): If the moon is out, then if it is not snowing Phyllis goes out for a
walk. [So iu > s is understood to mean (--w) > s as opposed to --(w > s).]
c) -'(s o (u v t )): It is not the case that Phyllis goes out for a walk if and only if it is
snowing or the moon is out.
Now we will work in reverse order and examine the logical (or symbolic) notation for
three given English sentences:
d) Phyllis will go out walking if and only if the moon is out. Here the words if
and only if indicate that we are dealing with a biconditional. In symbolic form this
becomes s o t .
e) If it is snowing and the moon is not out, then Phyllis will not go out for a walk.
This compound statement is an implication where the hypothesis is also a compound
statement. One may express this statement in symbolic form as (u A - **t) o --5.
f ) It is snowing but Phyllis will still go out for a walk. Now we come across a new
connective namely, but. In our study of logic we shall follow the convention that
the connectives but and and convey the same meaning. Consequently, this sentence
may be represented as u A s .
Now let us return to the results in Table 2.2, particularly the sixth column. For if this is
ones first encounter with the truth table for the implication p o q, then it may be somewhat
difficult to accept the stated entries especially the results in the first two rows (where p has
the truth value 0). The following example should help make these truth value assignments
easier to grasp.
Consider the following scenario. It is almost the week before Christmas and Penny will be
E X A M P L E 2.2
attending several parties that week. Ever conscious of her weight, she plans not to weigh
herself until the day after Christmas. Considering what those parties may do to her waistline
by then, she makes the following resolution for the December 26 outcome: If I weigh more
than 120 pounds, then I shall enroll in an exercise class.
Here we let p and q denote the (primitive) statements
Row 1: p and q both have the truth value 0. Here Penny finds that on December 26
her weight is 120 pounds or less and she does not enroll in an exercise class. She has not
violated her resolution; we take her statement p -> q to be true and assign it the truth
value 1.
Row 2: p has the truth value 0, q has the truth value 1. This last case finds Penny
weighing 120 pounds or less on December 26 but still enrolling in an exercise class.
Perhaps her weight is 119 or 120 pounds and she feels this is still too high. Or maybe
she wants to join an exercise class because she thinks it will be good for her health. No
matter what the reason, she has not gone against her resolution p > q. Once again, we
accept this compound statement as true, assigning it the truth value 1.
Our next example discusses a related notion: the decision (or selection) structure in
computer programming.
In computer science the if-then and if-then-else decision structures arise (in various for
E X A M P L E 2.3
mats) in high-level programming languages such as Java and C++. The hypothesis p is often
a relational expression such as jc > 2. This expression then becomes a (logical) statement
that has the truth value 0 or 1, depending on the value of the variable x at that point in
the program. The conclusion q is usually an executable statement. (So q is not one of
the logical statements that we have been discussing.) When dealing with if p then q , in
this context, the computer executes q only on the condition that p is true. For p false, the
computer goes to the next instruction in the program sequence. For the decision structure
if p then q else r, q is executed when p is true and r is executed when p is false.
Before continuing, a word of caution: Be careful when using the symbols -+ and +> . The
implication and the biconditional are not the same, as evidenced by the last two columns
of Table 2.2.
In our everyday language, however, we often find situations where an implication is used
when the intention actually calls for a biconditional. For example, consider the following
implications that a certain parent might direct to his or her child.
5 - t: If you do your homework, then you will get to watch the baseball game.
t -> s: You will get to watch the baseball game only if you do your homework.
Case 1: The implication 5 -+ t. When the parent says to the child, If you do your
homework, then you will get to watch the baseball game, he or she is trying a positive
approach by emphasizing the enjoyment in watching the baseball game.
Case 2: The implication t -> s. Here we find the negative approach and the parent who
warns the child in saying, You will get to watch the baseball game only if you do your
homework. This parent places the emphasis on the punishment (lack of enjoyment) to
be incurred.
In either case, the parent probably wants his or her implication be it 5 - t or t -+ 5
to be understood as the biconditional 5 ++ t. For in case 1 the parent wants to hint at the
punishment while promising the enjoyment; in case 2, where the punishment has been
used (perhaps, to threaten), if the child does in fact do the homework, then that child will
definitely be given the opportunity to enjoy watching the baseball game.
52 Chapter 2 Fundamentals of Logic
Before we continue let us take a step back. When we summarized the material that
gave us Tables 2.1 and 2.2, we may not have stressed enough that the results were for any
statements p , q not just primitive statements p , q. Examples 2.4 through 2.6 should help
to reinforce this.
Let us examine the truth table for the compound statement Margaret Mitchell wrote Gone
E X A M P L E 2.4
with the Wind, and if 2 + 3 ^ 5 , then combinatorics is a required course for sophomores.
In symbolic notation this statement is written as q A (-<r > p ), where p , q, and r represent
the primitive statements introduced at the start of this section. The last column of Table 2.3
contains the truth values for this result. We obtained these truth values by using the fact
that the conjunction of any two statements is true if and only if both statements are true.
This is what we said earlier in Table 2.2, and now one of our statements namely, the
implication -<r - p is definitely a compound statement, not a primitive one. Columns
4, 5, and 6 in this table show how we build the truth table up by considering smaller parts
of the compound statement and by using the results from Tables 2.1 and 2.2.
Table 2.3
p q r -r p q A (-./ p )
0 0 0 1 0 0
0 0 1 0 1 0
0 1 0 1 0 0
0 1 1 0 1 1
1 0 0 1 1 0
1 0 1 0 1 0
1 1 0 1 1 1
1 1 1 0 1 1
In Table 2.4 we develop the truth tables for the compound statements p v (q A r) (col
E X A M P L E 2.5
umn 5) and (p v q) A r (column 7).
Table 2.4
p q r q a r P V (q a r) pvq ( p v q ) Ar
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 1 0
0 1 1 1 1 1 1
1 0 0 0 1 1 0
1 0 1 0 1 1 1
1 1 0 0 1 1 0
1 1 1 1 1 1 1
2.1 Basic Connectives and Truth Tables 53
Because the truth values in columns 5 and 7 differ (in rows 5 and 7), we must avoid
writing a compound statement such as p v q A r. Without parentheses to indicate which of
the connectives v and A should be applied first, we have no idea whether we are dealing
with p V (q A r) or (p V q) A r.
Our last example for this section illustrates two special types of statements.
The results in columns 4 and 7 of Table 2.5 reveal that the statement p > {p v q) is true and
E X A M P L E 2.6
that the statement p A ( -- /? A q) is false for all truth value assignments for the component
statements p, q.
Table 2.5
0 0 0 1 1 0 0
0 1 1 1 1 1 0
1 0 1 1 0 0 0
1 1 1 1 0 0 0
Definition 2.1 A compound statement is called a tautology if it is true for all truth value assignments for
its component statements. If a compound statement is false for all such assignments, then
it is called a contradiction.
Throughout this chapter we shall use the symbol 7b to denote any tautology and the
symbol Fq to denote any contradiction.
We can use the ideas of tautology and implication to describe what we mean by a valid
argument. This will be of primary interest to us in Section 2.3, and it will help us develop
needed skills for proving mathematical theorems. In general, an argument starts with a list
of given statements called premises and a statement called the conclusion of the argument.
We examine these premises, say /A, P2 , P 3 , , Pn, and try to show that the conclusion
q follows logically from these given statements that is, we try to show that if each of
Pi, p 2 , /? 3 , , p n is a true statement, then the statement q is also true. To do so one way
is to examine the implication
(P\ A p 2 A p 3 A A p n)f -* q,
where the hypothesis is the conjunction of then premises. If any one of p \, p 2 , Pi, . . . , p n is
false, then no matter what truth value# has, the implication (p\ A p 2 A A A p n) >q
is true. Consequently, if we start with the premises p \, P2 , P?>, , Pn each with truth
value 1 and find that under these circumstances q also has the value 1, then the implication
(p\ A P2 a P3 A A p n) <7
^At this point we have dealt only with the conjunction of two statements, so we must point out that the
conjunction p\ A p 2 a A A p n of n statements is true if and only if each p t , 1 < i < n, is true. We shall
deal with this generalized conjunction in detail in Example 4.16 of Section 4.2.
54 Chapter 2 Fundamentals of Logic
a) /? A g b ) -'pW q c) q > p d ) >q -^p 10. Verify that [p -> {q > r)] -> [(p -> q) -> (p -> r)] is a
tautology.
4. Let p , q , r , s denote the following statements:
11. a) How many rows are needed for the truth table of the
p: I finish writing my computer program before lunch. compound statement (/? V ^ [(-v A s) > t], where
q\ I shall play tennis in the afternoon. p , q , r , s , and t are primitive statements?
r: The sun is shining.
b) Let p\, p 2, . . . , pn denote n primitive statements. Let
s: The humidity is low.
p be a compound statement that contains at least one oc
Write the following in symbolic form. currence each of p t, for 1 < i < n and p contains no
a) If the sun is shining, I shall play tennis this afternoon. other primitive statement. How many rows are needed to
construct the truth table for p i
b) Finishing the writing of my computer program before
lunch is necessary for my playing tennis this afternoon. 12. Determine all truth value assignments, if any, for the prim
itive statements p , q, r, s, t that make each of the following
c) Low humidity and sunshine are sufficient for me to play compound statements false.
tennis this afternoon.
a) [ ( p A ? ) A r ] - > ( s v / )
5. Let p, q , r denote the following statements about a partic
ular triangle ABC. b) \p A (q A r)] -> ( s Y t )
13. If statement q has the truth value 1, determine all truth value
p\ Triangle AB C is isosceles.
assignments for the primitive statements, /?, r, and s for which
q: Triangle AB C is equilateral.
the truth value of the statement
r: Triangle ABC is equiangular.
(q -> [(->p V r) A ->j ]) A [-is -> (-T A q)]
Translate each of the following into an English sentence,
is 1.
a) q p b) -/? -> ->q
14. At the start of a program (written in pseudocode) the inte
c) q +r d) p A ->q ger variable n is assigned the value 7. Determine the value of
e) r -> p n after each of the following successive statements is encoun
6. Determine the truth value of each of the following impli tered during the execution of this program. [Here the value of
cations. n following the execution of the statement in part (a) becomes
the value of n for the statement in part (b), and so on, through
a) If 3 + 4 = 12, then 3 + 2 = 6. the statement in part (d). For positive integers a, b, [a/b\ re
b) If 3 + 3 = 6, then 3 + 4 = 9. turns the integer part of the quotient for example, |_6/2J = 3,
c) If Thomas Jefferson was the third president of the United L7/2J = 3, L2/5J = 0, and |_8/3J = 2.]
States, then 2 + 3 = 5. a) i f ir > 5 th en n : = n + 2
2.2 Logical Equivalence: The Laws of Logic 55
b) i f ( (n + 2 = 8) o r {n - 3 = 6 ) ) t h e n f o r i : = 1 t o m do
n := 2 * n + 1 f o r j := 1 t o n do
c ) if ( (n - 3 = 1 6 ) a n d (|_ n /6 j = 1) ) t h e n i f i / j th e n
n := n + 3 p r in t i + j
d) i f ( ( m < 2 0) a n d ( [ n / 6 J = 1) ) t h e n If only one of these four statements is true and only one of
m := m - n - 5 the four committed this heinous crime, who is the vile culprit
that Aunt Nellie will have to punish severely?
e ) if { { n = 2 * m) o r { [ n / 2 J = 5) ) t h e n
m := m+ 2
16. In the following program segment i, j , m , and n are integer
variables. The values of m and n are supplied by the user earlier
in the execution of the total program.
2.2
Logical Equivalence: The Laws of Logic
In all areas of mathematics we need to know when the entities we are studying are equal or
essentially the same. For example, in arithmetic and algebra we know that two nonzero real
numbers are equal when they have the same magnitude and algebraic sign. Hence, for two
nonzero real numbers x, y, we have jc = y if \x\ = \y \ and xy > 0, and conversely (that is,
if jc = y, then |jc| = \y\ and jcy > 0). When we deal with triangles in geometry, the notion
of congruence arises. Here triangle A B C and triangle D E F are congruent if, for instance,
they have equal corresponding sides that is, the length of side A B = the length of side
D E , the length of side B C = the length of side E F , and the length of side C A = the length
of side FD .
Our study of logic is often referred to as the algebra o f propositions (as opposed to the
algebra of real numbers). In this algebra we shall use the truth tables of the statements,
or propositions, to develop an idea of when two such entities are essentially the same. We
begin with an example.
For primitive statements p and q , Table 2.6 provides the truth tables for the compound
E X A M P L E 2.7
statements -/? v q and p > q. Here we see that the corresponding truth tables for the two
statements - ^ p V q and p > q are exactly the same.
56 Chapter 2 Fundamentals of Logic
Table 2.6
p q -p - p v q p q
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 0 1 1
Definition 2.2 Two statements s\, S2 are said to be logically equivalent, and we write s\ S2 , when the
statement s\ is true (respectively, false) if and only if the statement 52 is true (respectively,
false).
Note that when s\ S2 the statements s\ and 52 provide the same truth tables because
si, S2 have the same truth values for all choices of truth values for their primitive compo
nents.
As a result of this concept we see that we can express the connective for the implication (of
primitive statements) in terms of negation and disjunction that is, (p > q) - 7 ? v q.
In the same manner, from the result in Table 2.7 we have (/? q) (p > q) A (q > p ),
and this helps validate the use of the term biconditional Using the logical equivalence from
Table 2.6, we find that we can also write (p q) ( - ' p v q ) A (-*q v p ) . Consequently,
if we so choose, we can eliminate the connectives - and from compound statements.
Table 2.7
p q p ^ q q^ p (P -?) A (q - p ) p++q
0 0 1 1 1 1
0 1 1 0 0 0
1 0 0 1 0 0
1 1 1 1 1 1
Examining Table 2.8, we find that negation, along with the connectives A and v , are all
we need to replace the exclusive or connective, v. In fact, we may even eliminate either A
or v. However, for the related applications we want to study later in the text, we shall need
both A and v as well as negation.
Table 2.8
>1
pvq pAq - ( p A q) ( p v q ) A - ( p A q)
2^
P q
0 0 0 0 0 1 0
0 1 1 1 0 1 1
1 0 1 1 0 1 1
1 1 0 1 1 0 0
2.2 Logical Equivalence: The Laws of Logic 57
We now use the idea of logical equivalence to examine some of the important properties
that hold for the algebra of propositions.
For all real numbers a, b, we know that (a + b) = (a ) + {b) . Is there a comparable
result for primitive statements p, q l
In Table 2.9 we have constructed the truth tables for the statements -(/? A q), -* p \/ *q,
E X A M P L E 2.8
- ( p v q), and -*p A -*q, where p, q are primitive statements. Columns 4 and 7 reveal
that (/? A q) = ip v -*q\ columns 9 and 10 reveal that ->(/? v q) ->/? A -*q. These
results are known as DeMorgans Laws. They are similar to the familiar law for real numbers,
- (a + b) = ( - a ) + ( - b ) ,
already noted, which shows the negative of a sum to be equal to the sum of the nega
tives. Here, however, a crucial difference emerges: The negation of the conjunction of two
primitive statements p, q results in the disjunction of their negations -/?, *q, whereas
the negation of the disjunction of these same statements p, q is logically equivalent to the
conjunction of their negations /?, ^q.
Table 2.9
p Aq p v q -Q > v q) p >q
<
J
J
p q -(p A q) a
-p -q
0 0 0 1 1 l 1 0 1 1
0 l 0 1 1 0 1 1 0 0
1 0 0 1 0 l 1 1 0 0
1 l 1 0 0 0 0 1 0 0
Although p, q were primitive statements in the preceding example we shall soon learn
that DeMorgans Laws hold for any two arbitrary statements.
In the arithmetic of real numbers, the operations of addition and multiplication are both
involved in the principle called the Distributive Law of Multiplication over Addition: For
all real numbers a, b, c,
a X (b + c) = (a X b) + (a X c).
The next example shows that there is a similar law for primitive statements. There is also
a second related law (for primitive statements) that has no counterpart in the arithmetic of
real numbers.
Table 2.10 contains the truth tables for the statements p A (q v r), (p A q) v (p A r),
E X A M P L E 2.9
p V ( q A r ), and ( p V q ) A ( p V r ) . From the table it follows that for all primitive state
ments p, q, and r,
p A (q v r) (p A q) v (p A r) The Distributive Law of A over v
p v (q A r) <?=> (p v q) A (p v r) The Distributive Law of v over A
The second distributive law has no counterpart in the arithmetic of real numbers. That
is, it is not true for all real numbers a , b , and c that the following holds: a + (b X c) =
{a + b) X {a + c). For a = 2, b = 3, and c 5, for instance, a + (b X c) = 17 but
(a -|- b) X {a -|- c) = 35.
58 Chapter 2 Fundamentals of Logic
Table 2.10
p <1 r p A (qvr) (p a q) v (p a r) p v (q a r) (P v q) a (p V r)
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 0 0 1 1
1 0 0 0 0 1 1
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1
Before going any further, we note that, in general, if s\ , 52 are statements and s\ s2
is a tautology, then s \ , S2 must have the same corresponding truth values (that is, for each
assignment of truth values to the primitive statements in s\ and 52, s\ is true if and only
if 52 is true and s\ is false if and only if S2 is false) and s\ 52. When s\ and S2 are
logically equivalent statements (that is, s\ 52), then the compound statement s\ S2 is
a tautology. Under these circumstances it is also true that -*s\ -*S2 , and -*si --52 is
a tautology.
If 51, 52, and 53 are statements where 51 52 and 52 53 then 51 53. When two
statements s\ and 52 are not logically equivalent, we may write 51 S2 to designate this
situation.
Using the concepts of logical equivalence, tautology, and contradiction, we state the
following list of laws for the algebra of propositions.
We note that because of the Associative Laws, there is no ambiguity in statements of the form p v q v r or
p A q A r.
2.2 Logical Equivalence: The Laws of Logic 59
We now turn our attention to proving all of these properties. In so doing we realize that
we could simply construct the truth tables and compare the results for the corresponding
truth values in each case as we did in Examples 2.8 and 2.9. However, before we start
writing, let us take one more look at this list of 19 laws, which, aside from the Law of
Double Negation, fall naturally into pairs. This pairing idea will help us after we examine
the following concept.
Definition 2.3 Let s be a statement. If 5 contains no logical connectives other than A and v , then the dual
of 5, denoted sd, is the statement obtained from 5 by replacing each occurrence of A and v
by v and A, respectively, and each occurrence of 7q and Fq by Fq and 7q, respectively.
If p is any primitive statement, then p d is the same as p that is, the dual of a primitive
statement is simply the same primitive statement. And ( - 'p Y is the same as -/?. The
statements p v -*p and p A ->/? are duals of each other whenever p is primitive and so
are the statements p v To and p A Fo.
Given the primitive statements p , q , r and the compound statement
5: (p A ~~*q) v ( r A 7o),
we find that the dual of 5 is
sd\ (p V *q) A ( r V Fo).
(Note that -^q is unchanged as we go from 5 to sd.)
We now state and use a theorem without proving it. However, in Chapter 15 we shall
justify the result that appears here.
T H E O R E M 2.1 The Principle o f Duality. Let 5 and t be statements that contain no logical connectives other
than A and v . If 5 f, then sd <=> td.
As a result, laws 2 through 10 in our list can be established by proving one of the laws
in each pair and then invoking this principle.
We also find that it is possible to derive many other logical equivalences. For example,
if q, r, s are primitive statements, the results in columns 5 and 7 of Table 2.11 show us that
(r A s) > q -<(r A s) V q
or that [ ( r A 5 ) ^ ^ h ( r A s ) v ^ ] is a tautology. However, instead of always con
structing more (and, unfortunately, larger) truth tables it might be a good idea to recall from
Example 2.7 that for primitive statements /?, q, the compound statement
( p - * q ) * + (-'P v q)
60 Chapter 2 Fundamentals of Logic
Table 2.11
0 0 0 0 1 1 1
0 0 1 0 1 1 1
0 1 0 0 1 1 1
0 1 1 1 0 0 0
1 0 0 0 1 1 1
1 0 1 0 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 0 1
a) From the first of DeMorgans Laws we know that for all primitive statements p, q,
E X A M P L E 2.10
the compound statement
P: -'(pVq)**(-'pA->q)
is a tautology. When we replace each occurrence of p by r A s, it follows from the
first substitution rule that
Pi: '[(r A s) V q] [-(r A s) A -*q]
is also a tautology. Extending this result one step further, we may replace each occur
rence of q by t > u. The same substitution rule now yields the tautology
Pi- [(/ A s) V (f u)] [- (r A s) A -'(t > w )],
and hence, by the remarks following shortly after Example 2.9, the logical equivalence
'[ ( r A s) v (t * u)] [ - ( r A s) A -< (f > u)].
b) For primitive statements p, q, we learn from the last column of Table 2.12 that the
compound statement [p A (p q)] q is a tautology. Consequently, if r, 5, t, u are
any statements, then by the first substitution rule we obtain the new tautology
[(r s) A [(r - s) - ('t v u)]\ - (W v u)
Table 2.12
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 1 1
a) For an application of the second substitution rule, let P denote the compound statement
E X A M P L E 2.11
(p q) r. Because (p > q) - * p v q (as shown in Example 2.7 and Table 2.6),
if P\ denotes the compound statement (--p v q) r, then P\ <= P. (We also find
that [(p -* q ) ^ r ] + + [(-p v q) > r] is a tautology.)
b) Now let P represent the compound statement (actually a tautology) p > (p v q ).
Since -'-'P p , the compound statement P\ \ p > (->--p v q) is derived from P
by replacing only the second occurrence (but not the first occurrence) of p by
The second substitution rule still implies that Pi P. [Note that P2: /7 >
( 1 ip v q), derived by replacing both occurrences of p by p , is also logically
equivalent to P.]
Our next example demonstrates how we can use the idea of logical equivalence together
with the laws of logic and the substitution rules.
p > q: If Joan goes to Lake George, then Mary will pay for Joans shopping spree.
62 Chapter 2 Fundamentals of Logic
Here we want to write the negation of p - q in a way other than simply -(/? > q). We
want to avoid writing the negation as It is not the case that if Joan goes to Lake George,
then Mary will pay for Joans shopping spree.
To accomplish this we consider the following. Since p > q -'P v q, it follows that
-(/7 > q) /7 v q). Then by DeMorgansLaw we have '( 'P V q) ^ -*-*p A
and from the Law of Double Negation and the second substitution rule it follows that
1 ip A *q p A *q. Consequently,
In Definition 2.3 the dual sd of a statement 5 was defined only for statements involving
E X A M P L E 2.14
negation and the basic connectives A and v . How does one determine the dual of a statement
such as 5: p > q, where p, q are primitive?
Because (p - q) - * p v q, sd is logically equivalent to the statement ( - ' p v q ) d,
which is -'p A q .
The implication p > q and certain statements related to it are now examined in the
following example.
Table 2.13 gives the truth tables for the statements / ? >#, -*q p, q ^ p, and
E X A M P L E 2.15
*p > -'q. The third and fourth columns of the table reveal that
(-iq P)
Table 2.13
1
t
j
j
r
p q p q q p
0 0 1 1 1 1
0 1 1 1 0 0
1 0 0 0 1 1
1 1 1 1 1 1
The statement -*q > *p is called the contrapositive of the implication p > q. Columns
5 and 6 of the table show that
converse q > p also be true. However, it does necessitate the truth of the contrapositive
-'q -> -'P-
Let us consider a specific example where p , q represent the statements
Then we obtain
(The implication: / ? >#). If Jeff is concerned about his cholesterol levels, then he
will walk at least two miles three times a week.
(The contrapositive: -'q > --/?). If Jeff does not walk at least two miles three times a
week, then he is not concerned about his cholesterol levels.
(The converse: q > p). If Jeff walks at least two miles three times a week, then he is
concerned about his cholesterol levels.
(The inverse: -' p > ~,q ) - l f Jeff is not concerned about his cholesterol levels, then he
will not walk at least two miles three times a week.
If p is true and q is false, then the implication p > q and the contrapositive -*q > -'p
are false, while the converse q > p and the inverse *p > -*q are true. For the case where
p is false and q is true, the implication p > q and the contrapositive -'q > *p are now
true, while the converse q > p and the inverse -'p > -'q are false. When p, q are both true
or both false, then the implication is true, as are the contrapositive, converse, and inverse.
We turn now to two examples involving the simplification of compound statements. For
simplicity, we shall list the major laws of logic being used, but we shall not mention any
applications of our two substitution rules.
For primitive statements p, q, is there any simpler way to express the compound statement
E X A M P L E 2.16
(p v q) A -(-/7 A q) that is, can we find a simpler statement that is logically equivalent
to the one given?
Here one finds that
(P V q) A ( ip A q) Reasons
^(pV q) A ( 1 'P V ~^q) DeMorgans Law
^ (p V q) A (p V ->q) Law of Double Negation
<=> (p V (q A ~^q ) Distributive Law of v over A
^ p v F0 Inverse Law
*=>P Identity Law
Consequently, we see that
(P V q) A ( ip A q) ^ p,
so we can express the given compound statement by the simpler logically equivalent state
ment p.
where /?, q, r are primitive statements. This statement contains four occurrences of primitive
statements, three negation symbols, and three connectives.
From the laws of logic it follows that
-'[-'[(P V q) A r ] V->q] Reasons
-'-'[(p V q) A r] A -*-*q DeMorgans Law
<=> \{p V q) A r] A q Law of Double Negation
4= ( p V q ) A ( r A q) Associative Law of A
*=> {p v q) A (q A r) Commutative Law of A
[(p V q) A q] A r Associative Law of A
qAr Absorption Law (as well as the
Commutative Laws for A and v)
Consequently, the original statement
-H (pV i)A r]v^]
is logically equivalent to the much simpler statement
q A r,
where we find only two primitive statements, no negation symbols, and only one connective.
Note further that from Example 2.7 we have
-[[(/? V q) A r] - > -*q\ ~'[~'[(p V q) A r] V -*q\,
so it follows that
-'[[(P V q) A r] - > - q ] q A r.
We close this section with an application on how the ideas in Examples 2.16 and 2.17 can
be used in simplifying switching networks.
A switching network is made up of wires and switches connecting two terminals T\ and
E X A M P L E 2.18
T2. In such a network, each switch is either open (0), so that no current flows through it, or
closed (1 ), so that current does flow through it.
In Fig. 2.1(a) we have a network with one switch. Each of parts (b) and (c) contains two
(independent) switches.
For the network in part (b), current flows from T\ to T2 if either of the switches p, q is
closed. We call this a parallel network and represent it by p v q . The network in part (c)
2.2 Logical Equivalence: The Laws of Logic 65
requires that each of the switches p , q be closed in order for current to flow from T\ to T2 .
Here the switches are in series; this network is represented by p A q.
The switches in a network need not act independently of each other. Consider the network
shown in Fig. 2.2(a). Here the switches labeled t and are not independent. We have
coupled these two switches so that t is open (closed) if and only if *t is simultaneously
closed (open). The same is true for the switches at q, -*q. (Also, for example, the three
switches labeled p are not independent.)
( p V q V r ) A ( p V t v -tq) A (p V V r) Reasons
^ p V [ ( q V r) A ( v **-#) A (~tf v r}] Distributive Law o f v
over A
p v l(q v r) (-f v r) A (f v **#)] Commutative Law o f a
p v [((? A - t ) v r) A (i V **#)] Distributive Law of v
over a
<=*> P V [((</ A ->i) V r) A (--i V ->^)J Law o f Double Negation
> p V {((9 A -;) V r ) A -<(-/ A )J DeMorgans Law
<= p v A q ) A ( (-* A q ) v r)\ Commutative Law of A
(twice)
<=> p V ((i A q ) A (<t A q)) V (<(/ A q ) A r)J Distributive Law of A
over v
4= P V [Fo V (-(-/ A q ) A r)] *>s a s Fo, for any
statement s
<=> p v [(->(-/ A 4 A r] S Fo is the identity for v
4= p V [ r A -(-/ A 9 )] Commutative Law of A
<=4- p V [r a (i v -#)] DeMorgans Law and
the Law of Double
Negation
flows from T\ to T2 in network (a) exactly when it does so in network (b). But network (b)
has only four switches, five fewer than network (a).
a) If 0 + 0 = 0, then 1 + 1 = 1.
EXERCISES 2.2
b) If -1 < 3 and 3 + 7 = 10, then sin ( f ) = -1 .
1. Let p , q , r denote primitive statements. 10. Determine whether each of the following is true or false.
Here p, q are arbitrary statements.
a) Use truth tables to verify the following logical equiva
lences. a) An equivalent way to express the converse of p is
i) p > (q A r) <=> ( p - + q) A (p > r) sufficient for g is p is necessary for g .
ii) \(p vq)-+r]<=> [(p -+ r) A (q -+ r)] b) An equivalent way to express the inverse of p is
iii) [p -+ (q V r)] +> [t -+ (p -+ q)] necessary for g is -# is sufficient for ->p.
b) Use the substitution rules to show that c) An equivalent way to express the contrapositive of
p is necessary for g is -# is necessary for -*p.
IP (q V r)] [(p A ->q) -+ r].
11. Let p, q, and r denote primitive statements. Find a form of
2. Verify the first Absorption Law by means of a truth table.
the contrapositive of p -+ (q -+ r) with (a) only one occurrence
3. Use the substitution rules to verify that each of the follow of the connective -+; (b) no occurrences of the connective -+.
ing is a tautology. (Here p, q, and r are primitive statements.)
a) \p V (q A r)] V -[p V (q A r)] 12. Show that for primitive statements p, q,
b) \(p Vq)-+r]<+ [ t - ( p V <?)] pYq A ->q) V (->p A <?)] <=> ->(p q).
4. For primitive statements p, q,r, and s, simplify the com 13. Verify that [(p +> q) A (q r) A (r +> p)] <<=>
pound statement 1(P q) A (q -+ r) A (r -+ p)], for primitive statements p,
[[[(/? A q) A r] V [(p A q) A - r ] ] V -w?] - + s.
q , and r.
5. Negate and express each of the following statements in 14. For primitive statements p, q,
smooth English. a) verify that p > [q > (p A g)] is a tautology.
a) Kelsey will get a good education if she puts her studies b) verify that (p V g) -+ [g -+ q] is a tautology by using
before her interest in cheerleading. the result from part (a) along with the substitution rules and
b) Norma is doing her homework, and Karen is practicing the laws of logic.
her piano lessons. c) is (p V q) -+ [q -+ (p A g)] a tautology?
c) If Harold passes his C++ course and finishes his data 15. Define the connective Nand or Not . . . and . . . by
structures project, then he will graduate at the end of the (p t q) <=> -'(p A q), for any statements p, q. Represent the
semester. following using only this connective.
6. Negate each of the following and simplify the resulting a) ->p b) p V q c) p A q
statement.
d) p~+ q e) p +> q
a) p A (q V r ) A (-* p V ->q V r)
16. The connective Nor or Not . . . or . . . is defined for
b) (p A q ) - + r any statements p, q by (p | q) ->(p V q). Represent the
c) P -> A r) statements in parts (a) through (e) of Exercise 15, using only
d) p V q V (-* p A *q A r) this connective.
7. a) If p, q are primitive statements, prove that 17. For any statements p, q, prove that
(-/? V q) A (p A (p A q)) ^ ( p A q). a) -(p lq)<=> (-p t '<?)
b) Write the dual of the logical equivalence in part (a). b) -+p t q) <=(P I ?)
8. Write the dual for (a) q -+ p, (b) p -+ (q A r), (c) p +> q, 18. Give the reasons for each step in the following simplifica
and (d) p^Lq, where p, q, and r are primitive statements. tions of compound statements.
9. Write the converse, inverse, and contrapositive of each of a) [(p v q) a ( p v -* g )] v g Reasons
the following implications. For each implication, determine its ^ [ P V ( ? A -u?)] V 0
truth value as well as the truth values of its corresponding con ^(pVfo)V?
verse, inverse, and contrapositive. pv q
2.3 Logical Implication: Rules of Inference 67
b) (p q) A [-># A ( r v ^ ) ] Reasons 19. Provide the steps and reasons, as in Exercise 18, to establish
4= ^ (p q) A -*q th e following logical equivalences.
<= ( ,P V 4 ) A-*q a) p v \p a (p v q)] <=p
( /? V g )
b) p V q V ('p A >q A r) p \/ q\/ r
ir^q A /?) V (->q A g)
4= ^ ( <? A -> p ) V F 0 c) [(/? V >q) > (p A q Ar)] $=$p A q
<= ->q A - . p 20 . Simplify each of the networks shown in Fig. 2.3.
^ ->(g V p )
2.3
Logical Implication: Rules of Inference
At the end of Section 2.1 we mentioned the notion of a valid argument. Now we will begin
a formal study of what we shall mean by an argument and when such an argument is valid.
This in turn will help us when we investigate how to prove theorems throughout the text.
We start by considering the general form of an argument, one we wish to show is valid.
So let us consider the implication
(P\ A P2 A p3A A p n) - q.
Here n is a positive integer, the statements p\, p 2 , /? 3 , . . . , p n are called the premises
of the argument, and the statement q is the conclusion for the argument.
The preceding argument is called valid if whenever each of the premises p\, p 2 , /?3, . . . ,
p n is true, then the conclusion q is likewise true. [Note that if any one of
p i, P2 , P?>, , Pn is false, then the hypothesis p\ A p 2 A p^ A A p n is false and the
implication (/?i A p 2 A p i A A p n) q is automatically true, regardless of the truth
value of q.] Consequently, one way to establish the validity of a given argument is to show
that the statement (p\ A p 2 A p^ A A p n) > q is a tautology.
The following examples illustrate this particular approach.
given in Table 2.14. Because the final column in Table 2.14 contains all 1s, the implication
is a tautology. Hence we can say that (p\ A p 2 A p 3) > g is a valid argument.
Table 2.14
Pi Pi P3 (Pi A p 2 A p 3) - > q
p <1 r P r -q-> p -r [(p - r) A ( - q >p) a ->r] . q
0 0 0 1 0 1 1
0 0 1 1 0 0 1
0 1 0 1 1 1 1
0 1 1 1 1 0 1
1 0 0 0 1 1 1
1 0 1 1 1 0 1
1 1 0 0 1 1 1
1 1 1 1 1 0 1
Let us now consider the truth table in Table 2.15. The results in the last column of this table
E X A M P L E 2.20
show that for any primitive statements p , r, and 5, the implication
\p A ((/? A r) - > 5 )] - > (r -> s)
Table 2.15
P P Pi- (pAr)^s
and conclusion g: (r > s), we know that (p\ A p i) > q is a valid argument, and we may
say that the truth of the conclusion q is deduced or inferred from the truth of the premises
Pu Pi-
The idea presented in the preceding two examples leads to the following.
Definition 2.4 If p, q are arbitrary statements such that p - q is a tautology, then we say that p logically
implies q and we write p => q to denote this situation.*12
From the results in Example 2.8 (Table 2.9) and the first substitution rule, we know that for
E X A M P L E 2.21
statements p, q,
^(pAq)^^pV^q.
Consequently,
- {p A q ) = ( - p V -q) and (-<p V ->7 ) => ->(p A 7 )
for all statements p, q. Alternatively, because each of the implications
'(.P A 7 ) - ( - 7? V -u?) and ( - 7? V ->7 ) -* (/? A 7 )
is a tautology, we may also write
[(/ A 7 ) -* {->p v -.7 )] =* 7o and [{->p v ->7 ) -* -<(p A 7 )] 7b.
70 Chapter 2 Fundamentals of Logic
Returning now to our study of techniques for establishing the validity of an argument, we
must take a careful look at the size of Tables 2.14 and 2.15. Each table has eight rows. For
Table 2.14 we were able to express the three premises p\, p 2 , and 773, and the conclusion
q , in terms of the three primitive statements p, q, and r. A similar situation arose for the
argument we analyzed in Table 2.15, where we had only two premises. But if we were
confronted, for example, with establishing whether
is a logical implication (or presents a valid argument), the needed table would require
25 = 32 rows. As the number of premises gets larger and our truth tables grow to 64, 128,
256, or more rows, this first technique for establishing the validity of an argument rapidly
loses its appeal.
Furthermore, looking at Table 2.14 once again, we realize that in order to establish
whether
is a valid argument, we need to consider only those rows of the table where each of the three
premises p > r ,-*q > p, and -<r has the truth value 1. (Remember that if the hypothesis
consisting of the conjunction of all of the premises is false, then the implication is true
regardless of the truth value of the conclusion.) This happens only in the third row, so a
good deal of Table 2.14 is not really necessary. (It is not always the case that only one row
has all of the premises true. Note that in Table 2.15 we would be concerned with the results
in rows 5, 6, and 8.)
Consequently, what these observations are telling us is that we can possibly eliminate a
great deal of the effort put into constructing the truth tables in Table 2.14 and Table 2.15. And
since we want to avoid even larger tables, we are persuaded to develop a list of techniques
called rules o f inference that will help us as follows:
1) Using these techniques will enable us to consider only the cases wherein all the
premises are true. Hence we consider the conclusion only for those rows of a truth
table wherein each premise has the truth value 1 and we do not construct the truth
table.
2) The rules of inference are fundamental in the development of a step-by-step validation
of how the conclusion q logically follows from the premises /?i, /?2, /?3, Pn in
an implication of the form
(Pi A Pi A p 3 A A p n) - q.
Such a development will establish the validity of the given argument, for it will show
how the truth of the conclusion can be deduced from the truth of the premises.
Each rule of inference arises from a logical implication. In some cases, the logical
implication is stated without proof. (However, several of these proofs will be dealt with in
the Section Exercises.)
Many rules of inference arise in the study of logic. We concentrate on those that we need
to help us validate the arguments that arise in our study of logic. These rules will also help
us later when we turn to methods for proving theorems throughout the remainder of the
text. Table 2.19 (on p. 78) summarizes the rules we shall now start to investigate.
2.3 Logical Implication: Rules of Inference 71
For a first example we consider the rule of inference called Modus Ponens, or the Rule o f
E X A M P L E 2.22
Detachment. {Modus Ponens comes from Latin and may be translated as the method of
affirming.) In symbolic form this rule is expressed by the logical implication
[p A (p -> q)] -> q,
which is verified in Table 2.16, where we find that the fourth row is the only one where both
of the premises p and p - q (and the conclusion q) are true.
Table 2.16
p q p q P A (p q) [ p A ( p -> ? ) ] - q
0 0 l 0 1
0 1 l 0 1
1 0 0 0 1
1 1 l 1 1
The following valid arguments show us how to apply the Rule of Detachment.
a) 1) Lydia wins a ten-million-dollar lottery. p
2) If Lydia wins a ten-million-dollar lottery, then Kay will quit her job. p > q
3) Therefore Kay will quit her job. :.q
b) 1) If Allison vacations in Paris, then she will have to win a scholarship. p > q
2) Allison is vacationing in Paris. p
3) Therefore Allison won a scholarship. :.q
Before closing the discussion on our first rule of inference let us make one final ob
servation. The two examples in (a) and (b) might suggest that the valid argument
\p A (p > q)] q is appropriate only for primitive statements p, q. However,
since [p A {p > q)] q is a tautology for primitive statements p, q, it follows from the
first substitution rule that (all occurrences of) p or q may be replaced by compound state
ments and the resulting implication will also be a tautology. Consequently, if r, s, t , and
u are primitive statements, then
rv s
(r V i )^ (-it A u)
't a u
is a valid argument, by the Rule of Detachment just as [ ( r V i ) A [ ( r V i ) - >
(-'t A ) ] ] - * ( - r A u) is a tautology.
72 Chapter 2 Fundamentals of Logic
A similar situation in which we can apply the first substitution rule occurs for each
of the rules of inference we shall study. However, we shall not mention this so explicitly
with these other rules of inference.
p ^ q
;.p r
This rule, which is referred to as the Law o f the Syllogism, arises in many arguments. For
example, we may use it as follows:
1) If the integer 35244 is divisible by 396, then the integer 35244 is
divisible by 66. p > q
2) If the integer 35244 is divisible by 66, then the integer 35244 is
divisible by 3. q > r
3) Therefore, if the integer 35244 is divisible by 396, then the integer
35244 is divisible by 3. ; . p > r
The next example involves a slightly longer argument that uses the rules of inference
developed in Examples 2.22 and 2.23. In fact, we find here that there may be more than one
way to establish the validity of an argument.
P (*)
p^~> q
g -> T
.. ~~*r
Now we need no longer worry about what the statements actually stand for. Our objective
is to use the two rules of inference that we have studied so far in order to deduce the truth
of the statement -r from the truth of the three premises p, p > *q, and *q > -<r.
2.3 Logical Implication: Rules of Inference 73
This follows from the logical implication [(p q) A -*q] -/?. Modus Tollens comes
from Latin and can be translated as method of denying. This is appropriate because we
deny the conclusion, q, so as to prove -*p. (Note that we can also obtain this rule from the
one for Modus Ponens by using the fact that p > q -*q > --/?.)
The following exemplifies the use of Modus Tollens is making a valid inference:
1) If Connie is elected president of Phi Delta sorority, then Helen will
pledge that sorority. p > q
2) Helen did not pledge Phi Delta sorority. -*q
3) Therefore Connie was not elected president of Phi Delta sorority. -*p
And now we shall use Modus Tollens to show that the following argument is valid (for
primitive statements p, r, s , t , and u).
p > r
r > 5
t v --5
*t v u
-'U
Both Modus Tollens and the Law of the Syllogism come into play, along with the logical
equivalence we developed in Example 2.7.
74 Chapter 2 Fundamentals of Logic
Steps Reasons
i) A Premises
2) p > s Step (1) and the Law of the Syllogism
3) t V 5 Premise
4) --5 'V t Step (3) and the Commutative Law of v
5) 5 > t Step (4) and the fact that -*s v t s > t
6) P ^ t Steps (2) and (5) and the Law of the Syllogism
7) 't V u Premise
8) t ^ U Step (7) and the fact that -*t v u t > u
9) p ^ u Steps (6) and (8) and the Law of the Syllogism
10) 'll Premise
11) p Steps (9) and (10) and Modus Tollens
Before continuing with another rule of inference let us summarize what we have just
accomplished (and not accomplished). The preceding argument shows that
We have not used the laws of logic, as in Section 2.2, to express the statement
For when /? has the truth value 0 and u has the truth value 1, the truth value of *p is 1 while
that of -'ll and (p > r) A (r > s) A (i v -tf) A (-i v u) A is 0.
Let us once more examine a tabular form for each of the two related rules of inference,
Modus Ponens and Modus Tollens.
The reason we wish to do this is that there are other tabular forms that may arise and
these are similar in appearance but present invalid arguments where each of the premises
is true but the conclusion is false.
a) Consider the following argument:
1) If Margaret Thatcher is the president of the United States, then
she is at least 35 years old. p - q
2) Margaret Thatcher is at least 35 years old. q
3) Therefore Margaret Thatcher is the president of the United States. ; .p
Here we find that [ ( /? > g ) A g ] > p is not a tautology. For if we consider the truth
value assignments p: 0 and q : 1, then each of the premises p - q and q is true
while the conclusion p is false. This invalid argument results from the fallacy
(error in reasoning) where we try to argue by the converse that is, while
[{p > q) A p] => q, it is not the case that [(/? q) a q ] ^ p.
2.3 Logical Implication: Rules of Inference 75
b) A second argument where the conclusion doesnt necessarily follow from the premises
may be given by:
1) If 2 + 3 = 6, then 2 + 4 = 6. p q
2) 2 + 3 ^ 6.
3) Therefore 2 + 4 ^ 6 . -^q
In this case we find that [(p > q) A *p]
* - > *q is not a tautology. Once again
the truth value assignments p: 0 and q: 1 show us that the premises p > q and *p
can both be true while the conclusion *q is false. The fallacy behind this invalid
argument arises from our attempt to argue by the inverse for although
\{p > q) A -*q] => --/7, it does not follow that [(/? - q) A ->/?] => -*q.
Before proceeding further we now mention a rather simple but important rule of infer
ence.
The following rule of inference arises from the observation that if p , q are true statements,
E X A M P L E 2.26
then p A q is a true statement.
Now suppose that statements p , q occur in the development of an argument. These
statements may be (given) premises or results that are derived from premises and/or from
results developed earlier in the argument. Then under these circumstances the two statements
p, q can be combined into their conjunction p A q, and this new statement can be used in
later steps as the argument continues.
We call this rule the Rule o f Conjunction and write it in tabular form as
P
q
.\pAq
As we proceed further with our study of rules of inference, we find another fairly simple
but important rule.
The following rule of inference one we may feel just illustrates good old common sense
E X A M P L E 2.27
is called the Rule o f Disjunctive Syllogism. This rule comes about from the logical impli
cation
\ ( p v q ) A /?] - > q,
which we can derive from Modus Ponens by observing that p v q -*p > q .
In tabular form we write
pvq
- 'P
'q
This rule of inference arises when there are exactly two possibilities to consider and we are
able to eliminate one of them as being true. Then the other possibility has to be true. The
following illustrates one such application of this rule.
1) Barts wallet is in his back pocket or it is on his desk. Pv q
2) Barts wallet is not in his back pocket. -p
3) Therefore Barts wallet is on his desk. /. q
76 Chapter 2 Fundamentals of Logic
At this point we have examined five rules of inference. But before we try to validate any
more arguments like the one (with 11 steps) in Example 2.25, we shall look at one more
of these rules. This one underlies a method of proof that is sometimes confused with the
contrapositive method (or proof) given in Modus Tollens. The confusion arises because
both methods involve the negation of a statement. However, we will soon realize that these
are two distinct methods. (Toward the end of Section 2.5 we shall compare and contrast
these two methods once again.)
Let p denote an arbitrary statement, and Fo a contradiction. The results in column 5 of Table
E X A M P L E 2.28
2.17 show that the implication (->/? > Fo) > p is a tautology, and this provides us with
the rule of inference called the Rule o f Contradiction. In tabular form this rule is written as
F Fo
: .p
Table 2.17
1 0 0 1 1
0 1 0 0 1
This rule tells us that if p is a statement and -*p Fo is true, then -p must be false because
Fo is false. So then we have p true.
The Rule of Contradiction is the basis of a method for establishing the validity of an
argument namely, the method of Proof by Contradiction, or Reductio ad Absurdum. The
idea behind the method of Proof by Contradiction is to establish a statement (namely, the
conclusion of an argument) by showing that, if this statement were false, then we would
be able to deduce an impossible consequence. The use of this method arises in certain
arguments which we shall now describe.
In general, when we want to establish the validity of the argument
(P i A p 2 A A p n) -> q ,
we can establish the validity of the logically equivalent argument
(P i A p 2 A A p n A ~*q) - > F0.
[This follows from the tautology in column 7 of Table 2.18 and the first substitution rule
where we replace the primitive statement p by the statement (pi a /?2 a a Pn Y ^
Table 2.18
(p -* q)
>
>
P q Fo p q
0 0 0 0 1 l 1
0 1 0 0 1 l 1
1 0 0 1 0 0 1
1 1 0 0 1 1 1
^In Section 4.2 we shall provide the reason why we know that for any statements p \, p 2, . . . , p n, and q, it
follows that (pi A P2 A A pn) A -*q Pl A P2 A A p n A ->q.
2.3 Logical Implication: Rules of Inference 77
When we apply the method of Proof by Contradiction, we first assume that what we are
trying to validate (or prove) is actually false. Then we use this assumption as an additional
premise in order to produce a contradiction (or impossible situation) of the form s A for
some statement 5. Once we have derived this contradiction we may then conclude that the
statement we were given was in fact true and this validates the argument (or completes
the proof).
We shall turn to the method of Proof by Contradiction when it is (or appears to be) easier
to use *q in conjunction with the premises p \, P2 , , Pn in order to deduce a contradiction
than it is to deduce the conclusion q directly from the premises p \, P2 , . . . , p n. The method
of Proof by Contradiction will be used in some of the later examples for this section
namely, Examples 2.32 and 2.35. We shall also find it frequently reappearing in other
chapters in the text.
Now that we have examined six rules of inference, we summarize these rules and intro
duce several others in Table 2.19 (on the following page).
The next five examples will present valid arguments. In so doing, these examples will
show us how to apply the rules listed in Table 2.19 in conjunction with other results, such
as the laws of logic.
Steps Reasons
1) p - * r Premise
2) - r -* - p Step (1) and p -* r -*r -> - 7?
3) - 7? ^ q Premise
4) Steps (2) and (3) and the Law of the Syllogism
5) q s Premise
6) 'f > s Steps (4) and (5) and the Law of the Syllogism
A second way to validate the given argument proceeds as follows.
Steps Reasons
i) P~> r Premise
2) q ^ s Premise
3) lP ^ Premise
4) p v q Step (3) and ( - 7? - q) (->-p v q) = {p v q), where the
second logical equivalence follows by the Law of Double Negation
5) r v s Steps (1), (2), and (4) and the Rule of the Constructive Dilemma
6) .. ~~*r - Step (5) and (r v s) (--- t v s ) (>r - 5), where the Law of
Double Negation is used in the first logical equivalence
Table 2.19
:.p ^ r
3) p-+q [(P *q) A -<q] -* --p Modus Tollens
-'q
:.~ 'P
4) p Rule of Conjunction
q
:.pAq
5) pvq [(p V q) A - p] -+ q Rule of Disjunctive
-'P Syllogism
:.q
6) - /? -> Fp { - P Fo) ^- p Rule of
p Contradiction
7) p Aq (P A q) p Rule of Conjunctive
:p Simplification
8) p p ^ pvq Rule of Disjunctive
:.py q Amplification
9) p Aq [(p A q) A [p - * ( 4 -* r)]] - * r Rule of Conditional
P^-iq^r) Proof
r
10) p y T [ O -* r) A {q -* r)] -* [(/> V 4 ) - r] Rule for Proof
q - r by Cases
:.(pvq)-*r
11) p -* q [ O - ^ i ) A ( r ^ s ) A ( p V r)] (q V s ) Rule of the
r -> 5 Constructive
pv r Dilemma
:.q V 5
12) p >q [(p -* q) A (r -* s) A V --s)] - * (-ip V - r ) Rule of the
r > 5 Destructive
'q V -5 Dilemma
ip v *r
Steps Reasons
i) p ^ q Premise
2) q (r A S ) Premise
3) (r A S ) Steps (1) and (2) and the Law of the Syllogism
4) p A t Premise
5) P Step (4) and the Rule of Conjunctive Simplification
6) r A s Steps (5) and (3) and the Rule of Detachment
7) r Step (6) and the Rule of Conjunctive Simplification
8) ->r V (-if V u Premise
9) '(r A t ) V u Step (8), the Associative Law of v , and DeMorgans Laws
10) t Step (4) and the Rule of Conjunctive Simplification
ID r At Steps (7) and (10) and the Rule of Conjunction
12) u Steps (9) and (11), the Law of Double Negation, and the
Rule of Disjunctive Syllogism
This example will provide a way to show that the following argument is valid.
EX A M P LE 2.31
If the band could not play rock music or the refreshments were not delivered
on time, then the New Years party would have been canceled and Alicia would
have been angry. If the party were canceled, then refunds would have had to be
made. No refunds were made.
Therefore the band could play rock music.
First we convert the given argument into symbolic form by using the following statement
assignments:
p: The band could play rock music.
q: The refreshments were delivered on time.
r: The New Years party was canceled.
5: Alicia was angry.
t: Refunds had to be made.
The argument above now becomes
In this instance we shall use the method of Proof by Contradiction. Consider the argument
E X A M P L E 2.32
-'p o q
q ^ r
ir
Ap
To establish the validity for this argument, we assume the negation -*p of the conclusion p
as another premise. The objective now is to use these four premises to derive a contradiction
F0. Our derivation follows.
Steps Reasons
l) - t p o q Premise
2) ( - P - +q ) A (q Step (1) and (-/? q) [( /? - > q ) A (q -> /?)]
3) lP Step (2) and the Rule of Conjunctive Simplification
4) q - > r Premise
5) 'P -> r Steps (3) and (4) and the Law of the Syllogism
6) ip Premise (the one assumed)
7) r Steps (5) and (6) and the Rule of Detachment
8) -'V Premise
9) r A t (<=* F0) Steps (7) and (8) and the Rule of Conjunction
10) A P Steps (6) and (9) and the method of Proof by
Contradiction
If we examine further what has happened here, we find that
Before we consider our next example, we need to examine columns 5 and 7 of Table
2.20. These identical columns tell us that for primitive statements p , q , and r,
Using the first substitution rule, let us replace each occurrence of p by the compound
statement (p\ A p 2 A A p n). Then we obtain the new result
(P i A P2 A A p n) A 4 pxA p2 A A p n A q.
2.3 Logical Implication: Rules of Inference 81
Table 2.20
p q r pAq ( p A q) -* r q r
0 0 0 0 1 1 1
0 0 1 0 1 1 1
0 1 0 0 1 0 1
0 1 1 0 1 1 1
1 0 0 0 1 1 1
1 0 1 0 1 1 1
1 1 0 1 0 0 0
1 1 1 1 1 1 1
This result tells us that if we wish to establish the validity of the argument (*) we may be
able to do so by establishing the validity of the corresponding argument (**).
(*) Pi Pi
P2 P2
Pn Pn
:.q ^ r q
r
After all, suppose we want to show that q > r has the truth value 1, when each of
p\, P2 , . . , p n does. If the truth value for q is 0, then there is nothing left to do, since
the truth value for q > r is 1. Hence the real problem is to show that q > r has truth
value 1 , when each of p\, p 2 , . . . , p n, and q does that is, we need to show that when
p\, P2 , . . . , p n, q each have truth value 1 , then the truth value of r is 1 .
We demonstrate this principle in the next example.
(**) u - r
(r A s) > (p V t)
q - * (u A s )
q_____________
:.p
[Note that q is the hypothesis of the conclusion q p for argument (*) and that it becomes
another premise for argument (**) where the conclusion is p .]
82 Chapter 2 Fundamentals of Logic
Examples 2.29 through 2.33 have given us some idea of how to establish the validity
of an argument. Following Example 2.25 we discussed two situations indicating when an
argument is invalid namely, when we try to argue by the converse or the inverse. So now
it is time for us to learn a little more about how to determine when an argument is invalid.
Given an argument
Pi
P2
P3
Pn
.\q
we say that the argument is invalid if it is possible for each of the premises p \ , P2 , P 3 , . . . ,
p n to be true (with truth value 1 ), while the conclusion q is false (with truth value 0).
The next example illustrates an indirect method whereby we may be able to show that
an argument we feel is invalid (perhaps because we cannot find a way to show that it is
valid) actually is invalid.
To show that this is an invalid argument, we need one assignment of truth values for each
of the statements p, q , r , s, and t such that the conclusion -*s > -'t is false (has the truth
value 0) while the four premises are all true (have the truth value 1). The only time the
2.3 Logical Implication: Rules of Inference 83
conclusion -*s -*t is false is when -*s is true and is false. This implies that the truth
value for 5 is 0 and that the truth value for t is 1.
Because p is one of the premises, its truth value must be 1. For the premise p v q to
have the truth value 1, q may be either true (1) or false (0). So let us consider the premise
t > r where we know that t is true. If t > r is to be true, then r must be true (have the
truth value 1). Now with r true (1) and 5 false (0), it follows that r > 5 is false (0), and that
the truth value of the premise q > (r > s) will be 1 only when q is false (0).
Consequently, under the truth value assignments
p: 1 q: 0 r: 1 5: 0 t: 1,
the four premises
P /? v 7 q (r s) t > r
all have the truth value 1 , while the conclusion
--5 -> -'t
has the truth value 0. In this case we have shown the given argument to be invalid.
(P\ A p 2 A Pi A A p n) -* q
presents a valid argument, we need to consider all cases where the premises p\, P2 , pz, . . . ,
p n are true. [Each such case is an assignment of truth values for the primitive statements
(that make up the premises) where p\, P2 , p?>, . . . , p n are true.] In order to do so namely,
to cover the cases without writing out the truth table we have been using the rules of
inference together with the laws of logic and other logical equivalences. To cover all the
necessary cases, we cannot use one specific example (or case) as a means of establishing
the validity of the argument (for all possible cases). However, whenever we wish to show
that an implication (of the preceding form) is not a tautology, all we need to find is one
case for which the implication is false that is, one case in which all the premises are true
but the conclusion is false. This one case provides a counterexample for the argument and
shows it to be invalid.
Let us consider a second example wherein we try the indirect approach of Example 2.34.
What can we say about the validity or invalidity of the following argument? Here p , q , r,
E X A M P L E 2.35
and 5 denote primitive statements.)
p ^ q
q > 5
r > ->5
'P V r
Can the conclusion - 7? be false while the four premises are all true? The conclusion - 7?
is false when p has the truth value 1. So for the premise p > q to be true, the truth value
of q must be 1. From the truth of the premise q > 5, the truth of q forces the truth of
5 . Consequently, at this point we have statements p , q , and 5 all with the truth value 1.
84 Chapter 2 Fundamentals of Logic
Continuing with the premise r > --s, we find that because v has the truth value 1, the truth
value of r must be 0. Hence r is false. But with -*p false and the premise -*p)Lr true, we
also have r true. Therefore we find that p => ( - t a r).
We have failed in our attempt to find a counterexample to the validity of the given
argument. However, this failure has shown us that the given argument is valid and the
validity follows by using the method of Proof by Contradiction.
This introduction to the rules of inference has been far from exhaustive. Several of the
books cited among the references listed near the end of this chapter offer additional material
for the reader who wishes to pursue this topic further. In Section 2.5 we shall apply the ideas
developed in this section to statements of a more mathematical nature. For we shall want to
learn how to develop a proof for a theorem. And then in Chapter 4 another very important
proof technique called mathematical induction will be added to our arsenal of weapons for
proving mathematical theorems. First, however, the reader should carefully complete the
exercises for this section.
Eileens car keys are not on the kitchen table. 9. a) Give the reasons for the steps given to validate the
Therefore Eileens car keys are in her purse. argument
e) If interest rates fall, then the stock market will rise. [(p -> q) A ( t V j) A (p V r)] -> (<? -> s).
Interest rates are not falling.
Therefore the stock market will not rise. Steps Reasons
1) - ( ^ - > 5 )
6. For primitive statements /?, q, and r, let P denote the 2) ->q A ->5
statement
3) - j
[p A (q A r)] V ->[p V (q A r)], 4) >r V s
while Pi denotes the statement 5) -*r
6) p - + q
\p A (q V r)] V ->[p V (q V r)].
7)
a) Use the rules of inference to show that 8)
q A r => q V r. 9) p V r
10) r
b) Is it true that P =>> Pi ?
11) *r A r
7. Give the reason(s) for each step needed to show that the 12) ->q -> 5
following argument is valid.
b) Give a direct proof for the result in part (a).
[p A (p -> q) A 0 V r) A (r > <?)] -> (s V 0
c) Give a direct proof for the result in Example 2.32.
Steps Reasons 10. Establish the validity of the following arguments.
1) P
2) p ^ q a) [(p A ->q) A r] > [(p A r) V q]
3) q b) \p A ( p - * q ) A (-*q V r ) ] - > r
4) r > >q C) p q d) p ^ i
5) r >
^q
6) -*r >r r
7) i V r .- ( P Vr) .-p
8) j
e) P -> (? -> r) f) p A <7
9) .-.5 v t
- ^ P p - > (r A ?)
8. Give the reasons for the steps verifying the following P r -> (s V 0
argument. .r -5
(-^ p V q )-*r
r > (s V t) g) p -+ (q -+ r) h) p V<?
*s A u p VS -*/? V r
>u > 'i t q >r
*.P -*s Aq
.T -
Steps Reasons
1) ->5 A 11. Show that each of the following arguments is invalid by
2) 'M providing a counterexample that is, an assignment of truth
3) values for the given primitive statements p, q, r, and s such
4) that all premises are true (have the truth value 1) while the con
5) '.v clusion is false (has the truth value 0).
6) >s A -i a) [(p A ->q) A [p >(q r)]] - ->r
7) r -> (5 V t) b ) [[(p A q) r] A (-<? V r)] > p
8 ) -1(5 v 0 -> - t
9) (-5 A >t) >-*r c) p o q d) p
q -*r P~+r
10) -*r
r V >s p - + ( q v -*r)
11) (^pvq)-^r
~~*s q >q V ->5
12) -*r -> ->(->/? V g)
.5
13) - t -> (p A -w?)
14) p A >q
15)
86 Chapter 2 Fundamentals of Logic
12. Write each of the following arguments in symbolic form. clauses (p V q) and (-*/? V r ) as premises and the clause
Then establish the validity of the argument or give a counter (q V r) as its conclusion (or, resolvent). Should we have the
example to show that it is invalid. premise (/? A q), we replace this by the logically equiva
a) If Rochelle gets the supervisors position and works lent clause - p v - g , by the first of DeMorgans Laws. The
hard, then shell get a raise. If she gets the raise, then shell premise ->(p V q) can be replaced by the two clauses -*p,
buy a new car. She has not purchased a new car. Therefore >q. This is due to the second DeMorgan Law and the Rule
either Rochelle did not get the supervisors position or she of Conjunctive Simplification. For the premise p V (q A r),
did not work hard. we apply the Distributive Law of V over A and the Rule
of Conjunctive Simplification to arrive at either of the two
b) If Dominic goes to the racetrack, then Helen will be mad.
clauses p v q, p V r. Finally, the premise p -> q becomes
If Ralph plays cards all night, then Carmela will be mad. If
the clause v q.
either Helen or Carmela gets mad, then Veronica (their at
Establish the validity of the following arguments, using
torney) will be notified. Veronica has not heard from either
resolution (along with the rules of inference and the laws
of these two clients. Consequently, Dominic didnt make it
of logic).
to the racetrack and Ralph didnt play cards all night.
(i) p v ( q A r) (ii) P
c) If there is a chance of rain or her red headband is missing, p > s p<+q
then Lois will not mow her lawn. Whenever the tempera :.r V s A?
ture is over 80 F, there is no chance for rain. Today the (iv)
(iti) pwq >p V q V r
temperature is 85F and Lois is wearing her red headband. p -+ r -V
Therefore (sometime today) Lois will mow her lawn. r -> s T
13. a) Given primitive statements p, q, r, show that the :.q V s
implication '/) V S
(V)
[(p V q) A ( r p V r )] - > ( ? V r ) it V (s A r)
is a tautology. *q V r
pWqVt
b) The tautology in part (a) provides the rule of inference
.'.r V s
known as resolution , where the conclusion (q V r) is called
the resolvent. This rule was proposed in 1965 by J. A. Robin c) Write the following argument in symbolic form, then
son and is the basis of many computer programs designed use resolution (along with the rules of inference and the
to automate a reasoning system. laws of logic) to establish its validity.
In applying resolution each premise (in the hypothe Jonathan does not have his drivers license or his new
sis) and the conclusion are written as clauses. A clause is car is out of gas. Jonathan has his drivers license or he does
a primitive statement or its negation, or it is the disjunc not like to drive his new car. Jonathans new car is not out
tion of terms each of which is a primitive statement or the of gas or he does not like to drive his new car. Therefore,
negation of such a statement. Hence the given rule has the Jonathan does not like to drive his new car.
2.4
The Use of Quantifiers
In Section 2.1, we mentioned how sentences that involve a variable, such as x, need not
be statements. For example, the sentence The number jc + 2 is an even integer is not
necessarily true or false unless we know what value is substituted for x. If we restrict our
choices to integers, then when jc is replaced by 5, 1, or 3, for instance, the resulting
statement is false. In fact, it is false whenever jc is replaced by an odd integer. When an
even integer is substituted for jc,however, the resulting statement is true.
We refer to the sentence The number jc + 2 is an even integer as an open statement,
which we formally define as follows.
In the case of q(x, y), there is more than one occurrence of each of the variables jc,y. It is
understood that when we replace one of the jcs by a choice from our universe, we replace
the other x by the same choice. Likewise, when a substitution (from the universe) is made
for one occurrence of y, that same substitution is made for all other occurrences of the
variable y.
With p(x) and q ( x , y ) as above, and the universe still stipulating the integers as our only
allowable choices, we get the following results when we make some replacements for the
variables x, y.
p ( 5): The number 7 (= 5 + 2) is an even integer. (FALSE)
- ,p(7): The number 9 is not an even integer. (TRUE)
q(4, 2): The numbers 4, 2, and 8 are even integers. (TRUE)
We also note, for example, that q(5, 2) and q(4, 7) are both false statements, whereas
--<7(5, 2) and --<7(4, 7) are true.
Consequently, we see that for both p(x) and q (x, y), as already given, some substitutions
result in true statements and others in false statements. Therefore we can make the following
true statements.
Note that in this situation, the statements For some jc, - ' p f c) and For some jc, y,
>q(x, y) are also true. [Since the statements For some jc, p(:c) and For some jc, --/?(jc)
are both true, we realize that the second statement is not the negation of the first even
though the open statement -</?(jc) is the negation of the open statement p(x). And a similar
result is true for the statements involving q{x, y) and -<7(jc, y).]
The phrases For some x and For some x, y are said to quantify the open statements
p(x) and <7(jc, y), respectively. Many postulates, definitions, and theorems in mathematics
involve statements that are quantified open statements. These result from the two types of
quantifiers, which are called the existential and the universal quantifiers.
88 Chapter 2 Fundamentals of Logic
Statement (1) uses the existential quantifier For some jt, which can also be expressed
as For at least one jt or There exists an jc such that. This quantifier is written in symbolic
form as 3x. Hence the statement For some x, p ( x ) becomes 3x p(x), in symbolic form.
Statement (2) becomes 3x 3 y q(x, y) in symbolic form. The notation 3 x , y can be used
to abbreviate 3 x 3 y q(x, y) to 3 x , y q(x, y).
The universal quantifier is denoted by Vx; and is read For all x , For any x , For each
X , or For every x For all x, y, For any x, y, For every x, y, or For all jt and y
The following example shows how these new ideas about quantifiers can be used in
conjunction with the logical connectives.
Here the universe comprises all real numbers. The open statements p(x), q(x), r(x), and
E X A M P L E 2.36
5(x) are given by
p(x): x>0 r(x): x 2 3x 4 = 0
q(x): x2 > 0 5(x): x 2 3 > 0.
Then the following statements are true.
1) 3x [p(x) A r(x)]
This follows because the real number 4, for example, is a member of the universe and is
such that both of the statements p{4) and r( 4) are true.
2) Vx [p(x) -> q{x)]
If we replace x in p{x) by a negative real number a , then p(a) is false, but p(a) > q(a)
is true regardless of the truth value of q(a). Replacing jt in p(x) by a nonnegative real
number b, we find that p(b) and q(b) are both true, as is p(b) > q(b). Consequently,
p(x) > q (jc) is true for all replacements jc taken from the universe of all real numbers, and
the (quantified) statement Vx [p(x) ^ q(x)] is true.
This statement may be translated into any of the following:
a) For every real number jt, if jt > 0, then x 2 > 0.
2.4 The Use of Quantifiers 89
We want to show that the statement is false, so we need exhibit only one counterexample
that is, one value o f x for which q(x) > s (jc) is false rather than prove something
for all jc as we did for statement (2). Replacing jc by 1, we find that q(l) is true and
s( 1) is false. Therefore g (l) > s (l) is false, and consequently the (quantified) statement
V jc [q{x) s(x)] is false. [Note that jc = 1 does not produce the only counterexample:
Every real number a between y/3 and y/3 will make q(a) true and s(a) false.]
Here there are many values for jc, such as 1, | , and 0, that produce counterexamples.
Upon changing quantifiers, however, we find that the statement 3x [r(x) v s(x)] is true.
Now we make the following observations. Let p(x) denote any open statement (in the
variable x) with a prescribed nonempty universe (that is, the universe contains at least one
member). Then if Vx; p(x) is true, so is 3x p(x), or
When we write V jc p(x) = > 3x p{x) we are saying that the implication V jc /?(jc) >
3 jc p(x) is a logical implication that is, 3 jc p(x) is true whenever V jc p(x) is true. Also,
we realize that the hypothesis of this implication is the quantified statement V jc / ? ( jc) , and
the conclusion is 3 jc p(x), another quantified statement. On the other hand, it does not
follow that if 3 jc p(x) is true, then V jc p(x) must be true. Hence 3x p(x) does not logically
imply V jc p(:c), in general.
Our next example brings out the fact that the quantification of an open statement may
not be as explicit as we might prefer.
a) Let us consider the universe of all real numbers and examine the sentences:
E X A M P L E 2.37
1) If a number is rational, then it is a real number.
2) If jc is rational, then jc is real.
90 Chapter 2 Fundamentals of Logic
We should agree that these sentences convey the same information. But we should
also question whether the sentences are statements or open statements. In the case
of sentence (2) we at least have the presence of the variable jc. But neither sentence
contains an expression such as For all, or For every, or For each. Our one and
only clue to indicate that we are dealing with universally quantified statements here is
the presence of the indefinite article a in the first sentence. In situations like these
the use of the universal quantifier is implicit as opposed to explicit.
If we let p(x), q(x) be the open statements
then we must recognize the fact that both of the given sentences are somewhat informal
ways of expressing the quantified statement
Vx [p(x) -* q{x)].
are defined for this universe, then the given sentence can be written in the explicit
quantified form
Vi [e(t) o a(t)].
c) In the typical trigonometry textbook one often comes across the trigonometric identity
sin2 jc + cos2 x = \.
This identify contains no explicit quantification, and the reader must understand or be
told that it is defined for all real numbers x. When the universe of all real numbers is
specified (or at least understood), then the identity can be expressed by the (explicitly)
quantified statement
r\ r\
Vx; [sin X + COS X = 1].
d) Finally, consider the universe of all positive integers and the sentence
The integer 41 is equal to the sum of two perfect squares.
Here we have one more example where the quantification is implicit but this
time the quantification is existential. We may express the result here in a more formal
(and symbolic) manner as
3m 3n [41 = m 2 + n 2].
The next example demonstrates that the truth value of a quantified statement may depend
on the universe prescribed.
2.4 The Use of Quantifiers 91
In the following program segment, n is an integer variable and the variable A is an array
E X A M P L E 2.39
A [l], A[2], . . . , A[20] of 20 integer values.
fo r n := 1 to 2 0 do
A [n] : = n * n - n
The following statements about the array A can be represented in quantified form, where
the universe consists of all integers from 1 to 20, inclusive.
1) Every entry in the array is nonnegative:
Vrc (A[n] > 0 ).
2) There exist two consecutive entries in A where the larger entry is twice the smaller:
3n (A[n + 1] = 2A M ).
3) The entries in the array are sorted in (strictly) ascending order:
Vrc [(1 < n < 19) - (A[n] < A[n + 1])].
Our last statement requires the use of two integer variables m, n.
4) The entries in the array are distinct:
Vra \fn [(ra ^ n) > (A[ra] ^ A[n])], or
Vra, n [(ra < n) > (A[ra] ^ A[n])].
Before continuing, we summarize and somewhat extend, in Table 2.21, what we have
learned about quantifiers.
The results in Table 2.21 may appear to involve only one open statement. However, we
should realize that the open statement p(x) in the table may stand for a conjunction of open
statements, such as q (jc) A r (jt), or an implication of open statements, such as 5 (x) > t (x).
If, for example, we want to know when the statement 3 x [^(x) > t(x)] is true, then we
look at the table for 3 x p(x) and use the information provided there. The table tells us that
3x [s (x) > t (jc)] is true when s (a) > t (a) is true for some (at least one) a in the prescribed
universe.
We will look further into quantified statements involving more than one open statement.
Before doing so, however, we need to examine the following definition. This definition is
comparable to Definitions 2.2 and 2.4 where we defined the ideas of logically equivalent
statements and logical implication. It settles the same types of questions for open statements.
92 Chapter 2 Fundamentals of Logic
Table 2.21
Definition 2.6 Let p(x), q(x) be open statements defined for a given universe.
The open statements p(x) and q ( x ) are called (logically) equivalent, and we write
Vx: [p(x) q(x)] when the biconditional p(a) q(a) is true for each replacement a
from the universe (that is, p(a) q(a) for each a in the universe). If the implication
p(a) > q(a) is true for each a in the universe (that is, p(a) => q(a) for each a in the
universe), then we write Vx: [p(x) => q(x)] and say that p(x) logically implies q(x).
For the universe of all triangles in the plane, let p{x), q{x) denote the open statements
Then for every particular triangle a (a replacement for x) we know that p(a) q (a) is true
(that is, p(a) q(a), for every triangle in the plane). Consequently, Vjc [p(x) = q(x)\.
Observe that here and, in general, Vjc [p(x) <=> q{x)] if and only if Vjc [p(x) => q(x)]
and Vx: [q(x) => p(x)].
We also realize that a definition similar to Definition 2.6 can be given for two open
statements that involve two or more variables.
Now we take another look at the logical equivalence of statements (not open state
ments) as we examine the converse, inverse, and contrapositive of a statement of the form
Vx [p(x) q(x)].
Definition 2.7 For open statements p(x), q(x) defined for a prescribed universe and the universally
quantified statement Vjc [p(x) q(x)], we define:
1) The contrapositive of Vx; [p(x) - q(x)] to be Vjc [-'qix) > -/?(jc)].
2) The converse of Vx: [p(x) q(x)] to be Vx: [q(x) > p ( x )].
3) The inverse of Vjc [p(x) ^ ( jc)] to be Vjc [-/?(jc) ->^(jc)].
For the universe of all quadrilaterals in the plane let s (jc) and e(x) denote the open statements
E X A M P L E 2.40
^(x): x is a square e(x): x is equilateral,
a) The statement
\fx [s(.x;) > e(x)]
is a true statement and is logically equivalent to its contrapositive
\fx [-'eix) -> - ,^(x)]
because [s(a) ^ e(a)\ [-'eia) > --s(a)] for each replacement a . Hence
Vx; [s(x) > e(x)] 4=^ Vx [-'e(x) > -*s(x)].
b) The statement
Vx [e(x) > ^(x)]
is a false statement and is the converse of the true statement
Vx [s(x) > (*)].
The false statement
\fx [-'^(x) -> -'eix)]
is the inverse of the given statement Vjc [s(x) > e(x)].
Since [e(a) ^ s(a)] [--s(a) > --e{a)] for each specific quadrilateral a , we
find that the converse and inverse are logically equivalent that is,
Vx; [e(x) > s(.x;)] 4=^ Vx; > ->^(x)].
as follows:
If a real number is less than or equal to 3, then so is its magnitude,
e) Together with p(x) and q(x) as above, consider the open statement
r(x): x < 3,
which is also defined for the universe of all real numbers. The following four state
ments are all true:
Statement: Vx [p(x) -* (r(x) v <?(x))]
Contrapositive: Vx [-'(r(jc) v q(x)) -* ~'p{x)]
Converse: Vx [(r(x) V q{x)) -* p{x)]
Inverse: Vx [-'i>(x) -* ->(r(x) v q (x))]
In this case (because the statement and its converse are both true) we find that the
statement \fx [p(x) (r(x) v q(x))] is true.
Now we use the results of Table 2.21 once again as we examine the next example.
Here the universe consists of all the integers, and the open statements r ( x ), s(x) are
E X A M P L E 2.42
given by
We see that the statement 3 x [r (jt) A s (jt)] is false because there is no one integer a such
that 2a + 1 = 5 and a 2 = 9. However, there is an integer b (= 2) such that 2b + 1 = 5,
and there is a second integer c ( = 3 or 3) such that c2 = 9. Therefore the statement
3 x r(x) A 3 x s (jc) is true. Consequently, the existential quantifier 3 x does not distribute
over the logical connective A. This one counterexample is enough to show that
is not a tautology.
What, however, can we say about the converse of a quantified statement of this form?
At this point we present a general argument for any (arbitrary) open statements p( x ) , q ( x )
and any (arbitrary) prescribed universe.
Examining the statement
we find that when the hypothesis 3 x [p(x) A q(x)] is true, there is at least one element c
in the universe for which the statement p(c) A q(c) is true. By the Rule of Conjunctive
Simplification (see Section 2.3), [p(c) A q(c)] => /7(c). From the truth of p( c ) we have the
true statement 3x p{x). Similarly we obtain 3 x q(x), another true statement. So 3 x p(x) A
2.4 The Use of Quantifiers 95
3 x q(x) is a true statement. Since 3x p(x) A 3x q(x) is true whenever 3 x [p(x) A q(x)]
is true, it follows that
Arguments similar to the one for Example 2.42 provide the logical equivalences and
logical implications listed in Table 2.22. In addition to those listed in Table 2.22 many other
logical equivalences and logical implications can be derived.
Table 2.22 Logical Equivalences and Logical Implications for Quantified Statements in One
Variable
For a prescribed universe and any open statements p(x), q(x) in the variable x:
3x [p(x) A q(x)] => [3x p(x) A 3 x q(x)]
3x [p(x) V q(x)] P * p(x) V 3x q(x)]
\fx [p(x) A q(x)] [\fx p(x) A \fx q(x)]
[\fx p(x) V \/x q(x)] => V * [p(x) V q(x)]
Our next example lists several of these and demonstrates how two of them are verified.
Let p{x), q(x), and r ( jc) denote open statements for a given universe. We find the following
E X A M P L E 2.43
logical equivalences. (Many more are also possible.)123
1) V* [p(x) A (q{x) A r ( x ) ) ] 4= V x [(p(x) A q(x)) A r ( x ) ]
To show that this statement is a logical equivalence we proceed as follows:
For each a in the universe, consider the statements p(a) A (q{a) A r(a)) and
(p(a) A q(a)) A r(a). By the Associative Law for A , we have
Therefore the statement 3 x [p(x) > q(x)] is true (respectively, false) if and only if
the statement 3 x [->/?(;c) v q(x)] is true (respectively, false), so
3) Other logical equivalences that we shall often find useful include the following.
a) Vx; -i-*p(x) 4==>V* p(x)
b) \fx -'[pix) A q(x)] 4=^ V* [-*p(x) V -'qix)]
c) Vx; -'[pix) V q(x)] V* [~'p(x) A -'q(x)]
96 Chapter 2 Fundamentals of Logic
4) The results for the logical equivalences in 3(a), (b), and (c) remain valid when all of
the universal quantifiers are replaced by existential quantifiers.
The results of Tables 2 .2 1 and 2 . 2 2 and Examples 2 . 4 2 and 2 . 4 3 will now help us with
a very important concept. How do we negate quantified statements that involve a single
variable?
Consider the statement Vjc p(x). Its negation namely, --[Vjc p ( x ) ] can be stated
as It is not the case that for all jc, p( x) holds. This is not a very useful remark, so we
consider --[Vjc p(x)] further. When --[Vjc p(x)] is true, then \fx p( x) is false, and so for
some replacement a from the universe - ' pi a) is true and 3 x ' pix) is true. Conversely,
whenever the statement 3 x -*p(x) is true we know that -p ( b ) is true for some member b of
the universe. Hence Vjc p( x) is false and --[Vjc p(x)] is true. So the statement -<[Vx p(x)]
is true if and only if the statement 3 x - ' p( x ) is true. (Similar considerations also tell us that
-[V;t p(x)] is false if and only if 3 x -*p(x) is false.)
These observations lead to the following rule for negating the statement Vjc p(x):
'[ V x p(x)] <(=$> 3x - >p(x).
In a similar way, Table 2 .2 1 shows us that the statement 3 jc p( x) is true (false) precisely
when the statement \fx - ' p( x ) is false (true). This observation then motivates a rule for
negating the statement 3 jc p(x):
P* p(x)] = Vx; - ' p(x).
These two rules for negation, and two others that follow from them, are given in Table 2.23
for convenient reference.
We use the rules for negating quantified statements in the following example.
Here we find the negation of two statements, where the universe comprises all of the integers.
E X A M P L E 2.44
1) Let p(x) and q(x) be given by
p(x): x is odd q(x): x 2 1 is even.
The statement If jc is odd, then jc2 1 is even can be symbolized as
Vx; [p(x) > q(x)]. (This is a true statement.)
The negation of this statement is determined as follows:
'[Vx (p(x) -> q(x))] 3 x [-'(pix) -> q(x))]
[-'(-'P ix) V q(x))] <<= 3 x [-'-'P ix) A -'qix)]
3 x [p(x) A -'qix)]
In words, the negation says, There exists an integer x such that x is odd and
jc2 1 is odd (that is, not even). (This statement is false.)
2.4 The Use of Quantifiers 97
r(x): 2x + 1 = 5 s(x): x 2 = 9.
The quantified statement 3x [r(x) A (A)] is false because it asserts the existence
of at least one integer a such that 2a + 1 = 5 (a = 2) and a 2 = 9 (a = 3 or -3 ).
Consequently, its negation
Because a mathematical statement may involve more than one quantifier, we continue
this section by offering some examples and making some observations on these types of
statements.
Here we have two real variables x, y, so the universe consists of all real numbers. The
E X A M P L E 2.45
commutative law for the addition of real numbers may be expressed by
Vx Vy (x + y = y + x).
This statement may also be given as
Vy Vx (x + y = y + x).
Likewise, in the case of the multiplication of real numbers, we may write
When dealing with the associative law for the addition of real numbers, we find that for all
E X A M P L E 2.46
real numbers jc,y, and z,
^ + (y + z) = (x + y) + z.
Using universal quantifiers (with the universe of all real numbers), we may express this by
Vx Vy Vz [x + (y + z) = (x + y) + z] or Vy Vx Vz [x + (y + z) = (x + y) + z].
In fact, there are 3! = 6 ways to order these three universal quantifiers, and all six of these
quantified statements are logically equivalent to one another.
This is actually true for all open statements p(x, y, z), and to shorten the notation, one
may write, for example,
In Examples 2.45 and 2.46 we encountered quantified statements with two and three
bound variables each such variable bound by a universal quantifier. Our next example
examines a situation in which there are two bound variables and this time each of these
variables is bound by an existential quantifier.
For the universe of all integers, consider the true statement There exist integers jc, y such
E X A M P L E 2.47
that jc -j- y = 6. We may represent this in symbolic form by
3 x 3y (x + y = 6).
If we let p(x, y) denote the open statement x + y = 6, then an equivalent statement can
be given by 3 y 3x p(x, y).
In general, for any open statement p(x, y) and universe(s) prescribed for the vari
ables x, y,
3 x 3y p(x, y) = 3 y 3 x p(x, y).
Similar results follow for statements involving three or more such quantifiers.
When a statement involves both existential and universal quantifiers, however, we must
be careful about the order in which the quantifiers are written. Example 2.48 illustrates this
case.
We restrict ourselves here to the universe of all integers and let p(x, y) denote the open
E X A M P L E 2.48
statement x + y = 17.
1) The statement
Vx 3y p(x, y)
says that For every integer jt, there exists an integer y such that x + y = 17. (We
read the quantifiers from left to right.)
This statement is true; once we select any x , the integer y = \1 x does exist
and x + y = x + (17 x) = 17. But we realize that each value of x gives rise to a
different value of y.
2) Now consider the statement
3 y \ f x p(x, y).
This statement is read There exists an integer y so that for all integers jc, jc + y =
17. This statement is false. Once an integer y is selected, the only value that x can
have (and still satisfy x + y = 17) is 17 y.
If the statement 3 y V* p(x, y) were true, then every integer (x) would equal
17 y (for some one fixed y). This says, in effect, that all integers are equal!
Consequently, the statements V* 3 y p(x, y) and 3 y Vjc p(x, y) are generally not
logically equivalent.
2) After we translate a mathematical statement into symbolic form, the rules we have
learned should then apply when we want to determine such related statements as the
negation or, if appropriate, the contrapositive, converse, or inverse.
Our last two examples illustrate this, and in so doing, extend the results in Table 2.23.
Let p(x, y), q(x, y), and r(x, y) represent three open statements, with replacements for
E X A M P L E 2.49
the variables x, y chosen from some prescribed universe(s). What is the negation of the
following statement?
We find that
Now suppose that we are trying to establish the validity of an argument (or a mathematical
theorem) for which
is the conclusion. Should we want to try to prove the result by the method of Proof by
Contradiction, we would assume as an additional premise the negation of this conclusion.
Consequently, our additional premise would be the statement
In calculus, one studies the properties of real-valued functions of a real variable. (Functions
E X A M P L E 2.50
will be examined in Chapter 5 of this text.) Among these properties is the existence of limits,
and one finds the following definition: Let I be an open interval containing the real number
a and suppose the function / is defined throughout /, except possibly at a. We say that /
has the limit L as x approaches a , and write \imx^ a f ( x ) = L, if (and only if) for every
6 > 0 there exists a 8 > 0 so that, for all jc in /, (0 < \x - a\ < 8 ) ( \ f ( x ) L\ < e). This
can be expressed in symbolic form as
[Here the universe comprises the real numbers in the open interval /, except possibly a.
Also, the quantifiers Ve > 0 and 38 > 0 now contain some restrictive information.] Then,
to negate this definition, we do the following (in which certain steps have been combined):
lim f ( x ) f L
x-+a
-[V e > 0 38 > 0 Vjc [(0 < |jc - a\ < 8 ) -> ( | / ( jc) - L\ < 6)]]
36 > 0 V<$ > 0 3 x --[(0 < \x a\ < 8 ) > (| f ( x ) L\ < 6)]
3 6 > 0 V<$ > 0 3x -.[-.(0 < \x - a\ < 8 ) v ( \ f ( x ) - L\ < e)]
36 > 0 V<$ > 0 3x [-(0 < \x a\ < 8 ) A - i( \ f ( x ) L\ < 6)]
36 > 0 V<$ > 0 3 x [ ( 0 < \ x - a \ < 8 ) A ( \ f ( x ) - L \ > 6)]
Translating into words, we find that lim * ^ f ( x ) ^ L if (and only if) there exists a
positive (real) number 6 such that for every positive (real) number 8 , there is an x in I such
thatO < \x a\ < 8 (that is, jc ^ a and its distance from is less than 6) but \ f ( x ) L | > 6
[that is, the value of f ( x ) differs from L by at least 6].
If the universe consists of all integers, what are the truth values s(x): x is a square
of the following statements? i(x): x is a triangle
a) q( 1) b ) -/? (3 ) C) p(7) V q(l) Translate each of the following statements into an English sen
d) p(3) A q(4) e) - ( p ( - 4 ) V q(-3)) tence, and determine whether the statement is true or false.
2. Let p(x), q(x) be defined as in Exercise 1. Let r(x) be the c) 3x [i(x) A p(x)] d) Vx [(a(x) A i(x )) e(x)]
open statement x > 0. Once again the universe comprises all e) 3x [q(x) A *r(jv)] f) 3x [r(x) A -*^(x)]
integers. g) Vx [h(x) -> e(x)] h) Vx [t(x) -> -p(x)]
a ) Determine the truth values of the following statements.
i) Vx [.s(x) <-> 0a(x )A /*(*))]
i) p{3) V [q(3) V -*r(3)]
j) Vx [t(x) -> (a(x) <+ h(x))]
ii) p(2) > [q{2) > r(2)]
iii) [p(2) A q{2)] > r(2) 5. Professor Carlsons class in mechanics is comprised of 29
students of which exactly
iv) p(0) > [ '^(1) <-> r (l)]
b ) Determine all values of x for which 1) three physics majors are juniors;
[p (x ) A q(x)] A r(x) resu lts in a true statem ent. 2) two electrical engineering majors are juniors;
3. Let p(x) be the open statement x 2 = 2jc, where the 3) four mathematics majors are juniors;
universe comprises all integers. Determine whether each of
4) twelve physics majors are seniors;
the following statements is true or false.
5) four electrical engineering majors are seniors;
a) p(0) b) p( 1) c) p(2)
6) two electrical engineering majors are graduate students;
d) p ( 2 ) e) 3x p(x) f ) Vx p(x)
and
4. Consider the universe of all polygons with three or four
7) two mathematics majors are graduate students.
sides, and define the following open statements for this uni
verse. Consider the following open statements.
a( x ): all interior angles of x are equal c(x): Student x is in the class (that is,
e(x): x is an equilateral triangle Professor Carlsons mechanics class
h(x): all sides of x are equal as already described).
2.4 The Use of Quantifiers 101
c) Every student in the class is majoring in mathematics or e) 3x [r(x) -> p(x)} f) Vx [ - t f i x ) -> ->i>(x)]
physics. g) 3x [ p ( x ) ^ { q { x ) A r ( x ) ) }
d) No graduate student in the class is a physics major. h ) Vx [(p(x) V q(x)) r(x)]
e) Every senior in the class is majoring in either physics or 9. Let p(x), q(x), and r(x) be the following open statements.
electrical engineering.
p(x): x 2 7x + 10 = 0
6. Let p ( x , y), q( x, y ) denote the following open statements.
q(x): x 2 2x 3 = 0
p( x, y ) : x2 >y q ( x , y ): x + 2 <y
r (jc) : jc < 0
If the universe for each of x, y consists of all real numbers,
determine the truth value for each of the following statements. a) Determine the truth or falsity of the following state
ments, where the universe is all integers. If a statement is
a) p( 2 , 4 ) b) q( 1, tt)
false, provide a counterexample or explanation.
c) p ( - 3, 8) A <7(1, 3) d) p (I, i ) v -< ? (-2 , - 3 )
i) Vx [p(x) > - t (jc)] ii) Vx [q{x) > r(x)]
e) p(2,2)^q(l, 1) f) /> (1, 2 ) * * - < 7( 1, 2 )
iii) 3x [^(x) > r(x)] iv) 3x [p(x) > r(x)]
7. For the universe of all integers, let p(x), q(x), r(x), s(x), b) Find the answers to part (a) when the universe consists
and t(x) be the following open statements. of all positive integers.
p(x): x >0 c) Find the answers to part (a) when the universe contains
q(x): x is even only the integers 2 and 5.
r (x): x is a perfect square 10. For the following program segment, m and n are integer
s(x): x is (exactly) divisible by 4 variables. The variable A is a two-dimensional array A [l, 1],
A [l, 2], . . . , A [l, 20], . . . , A[10, 1], . . . , A[10, 20], with 10
t(x): x is (exactly) divisible by 5 rows (indexed from 1 to 10) and 20 columns (indexed from 1
a ) Write the following statements in symbolic form. to 20).
i) At least one integer is even.
f o r m : = 1 t o 10 do
ii) There exists a positive integer that is even.
f o r n := 1 t o 2 0 do
iii) If x is even, then x is not divisible by 5.
A [m, n] := m + 3 * n
iv) No even integer is divisible by 5.
v) There exists an even integer divisible by 5.
vi) If x is even and x is a perfect square, then x is Write the following statements in symbolic form. (The universe
divisible by 4. for the variable m contains only the integers from 1 to 10 in
clusive; for n the universe consists of the integers from 1 to 20
b ) Determine whether each of the six statements in
inclusive.)
part (a) is true or false. For each false statement, provide a
counterexample. a) All entries of A are positive.
c) Express each of the following symbolic representations b) All entries of A are positive and less than or equal to 70.
in words. c) Some of the entries of A exceed 60.
102 Chapter 2 Fundamentals of Logic
d) The entries in each row of A are sorted into (strictly) f ) Vrc [-pOO -+ -^q(n)]
ascending order. g) Vrc [p(n) is sufficient for q(n)]
e) The entries in each column of A are sorted into (strictly) 15. For each of the following pairs of statements determine
ascending order. whether the proposed negation is correct. If correct, determine
f ) The entries in the first three rows of A are distinct. which is true: the original statement or the proposed negation.
11. Identify the bound variables and the free variables in each If the proposed negation is wrong, write a correct version of the
of the following expressions (or statements). In both cases the negation and then determine whether the original statement or
universe comprises all real numbers. your corrected version of the negation is true.
a) Vy 3 z [cos(x + y) = sin(z - x)] a) Statement: For all real numbers x, y, if x 2 > A then
x > y.
b) 3x 3 y [x2 y 2 = z]
Proposed negation: There exist real numbers x, y such that
12. a) Let p(x, y) denote the open statement x divides y, x 2 > y2 but* < y.
where the universe for each of the variables x, y comprises
b) Statement: There exist real numbers x, y such that x and
all integers. (In this context divides means exactly di
y are rational but x + y is irrational.
vides or divides evenly.) Determine the truth value of
Proposed negation: For all real numbers x, y, if x + y is
each of the following statements; if a quantified statement
rational, then each of x, y is rational.
is false, provide an explanation or a counterexample.
c) Statement: For all real numbers x, if Jt is not 0, then x
i) p(3, 7) ii) p(3, 27)
has a multiplicative inverse.
iii) Vy p( 1, y) iv) Vx p(x, 0)
Proposed negation: There exists a nonzero real number that
v) Vx p ( x , x) vi) Vy 3.x p(x, y)
does not have a multiplicative inverse.
vii) 3 y V* p(x, y)
viii) V* Vy [(p(x, y) A p(y, x)) -+ (x = y)] d) Statement: There exist odd integers whose product is
odd.
b) Determine which of the eight statements in part (a) will
Proposed negation: The product of any two odd integers is
change in truth value if the universe for each of the variables
odd.
x, y were restricted to just the positive integers.
16. Write the negation of each of the following statements as
c) Determine the truth value of each of the following state
an English sentence without symbolic notation. (Here the
ments. If the statement is false, provide an explanation or
universe consists of all the students at the university where
a counterexample. [The universe for each of x, y is as in
Professor Lenhart teaches.)
part (b).]
a) Every student in Professor Lenharts C++ class is
i) V* 3y p{x, y) ii) Vy 3x p{x, y)
majoring in computer science or mathematics.
iii) 3.x Vy p(x, y) iv) 3 y V* p(x, y)
b) At least one student in Professor Lenharts C++ class is
13. Suppose that p(x, y) is an open statement where the uni
a history major.
verse for each of x, y consists of only three integers: 2, 3, 5.
Then the quantified statement 3y p ( 2, y) is logically equiva 17. Write the negation of each of the following true statements.
lent to p ( 2, 2) V p( 2, 3) V p ( 2, 5). The quantified statement For parts (a) and (b) the universe consists of all integers; for
3 x Vy p(x, y) is logically equivalent to [p( 2, 2) A p(2, 3) A parts (c) and (d) the universe comprises all real numbers.
P( 2, 5)] v [p( 3, 2) A p( 3, 3) A p ( 3, 5)] v [p( 5, 2) a p( 5, 3) a) For all integers n, if n is not (exactly) divisible by 2,
A p( 5, 5)]. Use conjunctions and/or disjunctions to express the then n is odd.
following statements without quantifiers.
b) If k, m, n are any integers where k m and m n are
a) Vx p(x, 3) b) 3.x 3 y p(x, y) c) Vy 3.x p(x, y) odd, then k n is even.
14. Let /?(), q(n) represent the open statements c) If x is a real number where x 2 > 16, then x < - 4 or
p(n): n is odd q(n): n2 is odd x > 4.
for the universe of all integers. Which of the following state d) For all real numbers x, if |x 3| < 7, then4 < x < 10.
ments are logically equivalent to each other? 18. Negate and simplify each of the following.
a) If the square of an integer is odd, then the integer is odd. a) 3x [p(x) v q( x )] b) Vx [p(x) A -*g(x)]
b) Vw [p(n) is necessary for q(n] c) Vx [p(x) -> q{x)}
c) The square of an odd integer is odd. d) 3x [O O ) V q(x)) - r(x)]
d) There are some integers whose squares are odd. 19. For each of the following statements state the converse,
e) Given an integer whose square is odd, that integer is inverse, and contrapositive. Also determine the truth value for
likewise odd. each given statement, as well as the truth values for its converse,
2.5 Quantifiers, Definitions, and the Proofs of Theorems 103
inverse, and contrapositive. (Here divides means exactly 0 + a = a for every real number a. This may be expressed in
divides.) symbolic form by
a) [The universe comprises all positive integers.] 3z Va [a + z = z + a = a].
If m > n, then m 2 > n2.
(We agree that the universe comprises all real numbers.)
b) [The universe comprises all integers.]
a) In conjunction with the existence of an additive iden
If a > b, then a2 > b 2.
tity is the existence of additive inverses. Write a quantified
c) [The universe comprises all integers.] statement that expresses Every real number has an addi
If m divides n and n divides p, then m divides p. tive inverse. (Do not use the minus sign anywhere in your
d) [The universe consists of all real numbers.] statement.)
V jc [(jc > 3) (x2 > 9)] b) Write a quantified statement dealing with the existence
e) [The universe consists of all real numbers.] of a multiplicative identity for the arithmetic of real num
For all real numbers x, if x 2 + 4x - 21 > 0, then jc > 3 or bers.
jc < - 7 . c) Write a quantified statement covering the existence of
20. Rewrite each of the following statements in the if-then form. multiplicative inverses for the nonzero real numbers. (Do
Then write the converse, inverse, and contrapositive of your im not use the exponent 1 anywhere in your statement.)
plication. For each result in parts (a) and (c) give the truth value d) Do the results in parts (b) and (c) change in any way
for the implication and the truth values for its converse, inverse, when the universe is restricted to the integers?
and contrapositive. [In part (a) divisibility requires a remain
24. Consider the quantified statement V jc 3 y [ jc+ y = 17]. De
der of 0.]
termine whether this statement is true or false for each of the
a) [The universe comprises all positive integers.] following universes: (a) the integers; (b) the positive integers;
Divisibility by 21 is a sufficient condition for divisibility (c) the integers for jc, the positive integers for y ; (d) the positive
by 7. integers for jc, the integers for y.
b) [The universe comprises all snakes presently slithering
about the jungles of Asia.] 25. Let the universe for the variables in the following state
Being a cobra is a sufficient condition for a snake to be ments consist of all real numbers. In each case negate and sim
dangerous. plify the given statement.
c) [The universe consists of all complex numbers.] a) V* Vy [(x > y) > (x y > 0)]
For every complex number z, z being real is necessary for b) V* Vy [(x < y) 3z (x < z < y)]
z2 to be real.
c) V* Vy [(1*1 = |y|) -> (y = * )]
21. For the following statements the universe comprises all 26. In calculus the definition of the limit L of a sequence of
nonzero integers. Determine the truth value of each statement.
real numbers rls r2, r3, .. . can be given as
a) 3x 3 y [xy = 1] b) 3x Vy [xy = 1]
lim rn = L
n-+oo
c) V* 3 y [xy = 1]
if (and only if) for every e > 0 there exists a positive integer k
d) 3 jc 3 y [(2 jc + y = 5) a (x - 3y = - 8 ) ]
so that for all integers n, if n > k then \rn L\ < e.
e) 3x 3 y [(3jc y = 7) a (2jc + 4y = 3)] In symbolic form this can be expressed as
22. Answer Exercise 21 for the universe of all nonzero real lim rn = L ^ Ve > 0 3k > 0 Vrc [(n > k) -> \rn L\ < e].
numbers. n>oo
23. In the arithmetic of real numbers, there is a real num Express lim rn ^ L in symbolic form.
n>-OG
ber, namely 0, called the identity of addition because a + 0 =
2.5
Quantifiers, Definitions, and the Proofs
of Theorems
In this section we shall combine some of the ideas we have already studied in the prior two
sections. Although Section 2.3 introduced rules and methods for establishing the validity
of an argument, unfortunately the arguments presented there seemed to have little to do
with anything mathematical. [The rare exceptions are in Example 2.23 and the erroneous
104 Chapter 2 Fundamentals of Logic
argument in part (b) of the material preceding Example 2.26.] Most of the arguments dealt
with certain individuals and predicaments they were either in or about to face.
But now that we have learned some of the properties of quantifiers and quantified state
ments, we are better equipped to handle arguments that will help us to prove mathematical
theorems. Before dealing with theorems, however, we shall consider how mathematical
definitions are traditionally presented in scientific writing.
Following Example 2.3 in Section 2.1, the discussion concerned how an implication
might be used in place of a biconditional in everyday conversation. But in scientific writing,
it was noted, we should avoid any and all situations where an ambiguous interpretation
might come about in particular, an implication should not be used when a biconditional
is intended. However, there is one major exception to that rule and it concerns the way that
mathematical definitions are traditionally presented in mathematics textbooks and other
scientific literature. Example 2.51 demonstrates this exception.
a) Let us start with the universe of all quadrilaterals in the plane and try to identify those
E X A M P L E 2.51
that are called rectangles.
One person might say that
If a quadrilateral is a rectangle then it has four equal angles.
Another individual might identify these special quadrilaterals by observing that
If a quadrilateral has four equal angles, then it is a rectangle.
(Here both people are making implicitly quantified statements, where the quantifier is
universal.)
Given the open statements
p(x): x is a rectangle q(x): x has four equal angles,
we can express what the first person says as
Vx [p(x) -* g(x)],
while for the second person we would write
Vx [g(x) -* p(x)].
So which of the preceding (quantified) statements identifies or defines a rectangle?
Perhaps we feel that they both do. But how can that be, since one statement is the
converse of the other and, in general, the converse of an implication is not logically
equivalent to the implication.
Here the reader must consider what is intended not just what each of the two
people has said, or the symbolic expressions we have written to represent these state
ments. In this situation each person is using an implication with the meaning of a
biconditional. They are both intending (though not stating)
V* [p(x) **q(x)],
that is, each is really telling us that
A quadrilateral is a rectangle if and only if it has four equal angles.
b) Within the universe of all integers we can distinguish the even integers by means of a
certain property and so we may define them as follows:
For every integer n we call n even if it is divisible by 2.
2.5 Quantifiers, Definitions, and the Proofs of Theorems 105
(By the expression divisible by 2 we mean exactly divisible by 2 that is, there
is no remainder upon division of the dividend n by the divisor 2.)
If we consider the open statements
Vn [q in ) -> pin)].
After all, the given quantified statement (in the preceding definition) is an implication.
However, the situation here is similar to that given in part (a). What appears to be
stated is not what is intended. The intention is for the reader to interpret the given
definition as
Vn [q(n) p(n)],
that is,
For every integer n , we call n even if and only if n is divisible by 2.
(Note that the open statement n is divisible by 2 can also be expressed by the open
statement n = 2k, for some integer k . Dont be misled here by the presence of
the quantifier for some integer k for the expression 3 k [n = 2 k] is still an open
statement because n remains a free variable.)
So now we see how quantifiers may enter into the way we state mathematical defini
tions and that the traditional way in which such a definition appears is as an implication.
But beware and remember: It is only in definitions that an implication can be (mis)read and
correctly interpreted as a biconditional.
Note how we defined the limit concept in Example 2.50. There we wrote if (and only
if) since we wanted to let the reader know our intention. Now we are free to replace if
(and only if) by simply if.
Having settled our discussion on the nature of mathematical definitions, we continue
now with an investigation of arguments involving quantified statements.
Suppose that we start with the universe that comprises only the 13 integers 2, 4, 6, 8,
E X A M P L E 2.52
24, 26. Then we can establish the statement:
For all n (meaning n = 2, 4, 6, . . . , 26),
we can write n as the sum of at most three perfect squares.
The results in Table 2.24 provide a case-by-case verification showing the given (quanti
fied) statement to be true. (We might call this statement a theorem.)
Table 2.24
2=1 + 1 10 = 9+1 20 = 16 + 4
4= 4 12 = 4+ 4+ 4 22 = 9+ 9+ 4
6 = 4 + 1+ 1 14 = 9 + 4+1 24 = 16 + 4 + 4
8= 4+ 4 16 = 16 26 = 25 + 1
18 = 16 + 1 + 1
106 Chapter 2 Fundamentals of Logic
This exhaustive listing is an example of a proof using the technique we call, rather
appropriately, the method o f exhaustion. This method is reasonable when we are dealing
with a fairly small universe. If we are confronted with a situation in which the universe
is larger but within the range of a computer that is available to us, then we might write a
program to check all of the individual cases.
(Note that for certain cases in Table 2.24 more than one answer may be possible. For
example, we could have written 18 = 9 + 9 and 2 6 = 16 + 9 + 1. But this is all right. We
were told that each positive even integer less than or equal to 26 could be written as the
sum of one, two, or three perfect squares. We were not told that each such representation
had to be unique, so more than one possibility could occur. What we had to check in each
case was that there was at least one possibility.)
In the previous example we mentioned the word theorem. We also found this term used in
Chapter 1 for example, in results like the binomial theorem and the multinomial theorem
where we were introduced to certain types of enumeration problems. Without getting overly
technical, we shall consider theorems to be statements of mathematical interest, statements
that are known to be true. Sometimes the term theorem is used only to describe major
results that have many and varied consequences. Certain of these consequences that follow
rather immediately from a theorem are termed corollaries (as in the case of Corollary 1.1
in Section 1.3). In this text, however, we shall not be so particular in our use of the word
theorem.
Example 2.52 is a nice starting point to examine the proof of a quantified statement.
Unfortunately, a great number of mathematical statements and theorems often deal with
universes that do not lend themselves to the method of exhaustion. When faced with es
tablishing or proving a result for all integers, for example, or for all real numbers, then we
cannot use a case-by-case method like the one in Example 2.52. So what can we do?
We start by considering the following rule.
The Rule of Universal Specification: If an opes statement becomes true for all
replacements by the members in a given universe, then that open statement is true for
each specific individual member in that universe. (A bit more sym bolically if p(x)
is an open statement for a given universe, and if Vjt p(x ) is hue, then p(a) is true for
each a in the universe.)
This rule indicates that the truth of an open statement in one particular instance follows
(as a special case) from the more general (for the entire universe) truth of that universally
quantified open statement. The following examples will show us how to apply this idea.
If we let / represent this particular woman (in our universe) named Leona, then we
can rewrite this argument in symbolic form as
\fx [ m ( x ) c(x )]
m(l)
7MT)
Here the two statements above the line are the premises of the argument, and the
statement c(l) below the line is its conclusion. This is comparable to what we saw in
Section 2.3, except now we have a premise that is a universally quantified statement.
As was the case in Section 2.3, the premises are all assumed to be true and we must
try to establish that the conclusion is also true under these circumstances. Now, to
establish the validity of the given argument, we proceed as follows.
Steps Reasons
1) \fx [m{x) > c(x)] Premise
2) m(l) Premise
3) m(l) > c(l) Step (1) and the Rule of Universal Specification
4) .\c(Z) Steps (2) and (3) and the Rule of Detachment
Note that the statements in steps (2) and (3) are not quantified statements. They are
the types of statements we studied earlier in the chapter. In particular, we can apply
the rules of inference we learned in Section 2.3 to these two statements to deduce the
conclusion in step (4).
We see here that the Rule of Universal Specification enables us to take a universally
quantified premise and deduce from it an ordinary statement (that is, one that is not
quantified). This (ordinary) statement namely, m(l) > c(l) is one specific true
instance of the universally quantified true premise Vjc [m(x) > c(jt)].
b) For an example of a more mathematical nature let us consider the universe of all
triangles in the plane in conjunction with the open statements
Let us also focus our attention on one specific triangle with no two angles of equal
measure. This triangle will be called triangle X Y Z and will be designated by c. Then
we find that the argument
Steps Reasons
1) Vi [p{t) -> q(t)] Premise
2) p ( c ) - > q ( c ) Step (1) and the Rule of Universal Specification
3) Vi [q(t) -> r(f)] Premise
4) q ( c ) - >r ( c ) Step (3) and the Rule of Universal Specification
5) pic) - > r(c) Steps (2) and (4) and the Law of the Syllogism
6) --r(c) Premise
7) /.- / 7 ( c ) Steps (5) and (6) and Modus Tollens
Once again we see how the Rule of Universal Specification helps us. Here it has
taken the universally quantified statements at steps (1) and (3) and has provided us
with the (ordinary) statements at steps (2) and (4), respectively. Then at this point we
were able to apply the rules of inference we learned in Section 2.3 (namely, the Law
of the Syllogism and Modus Tollens) to derive the conclusion --/?(<:) in step (7).
c) Now for one last argument to drive the point home! Here well consider the universe
to be made up of the entire student body at a particular college. One specific student,
Mary Gusberti, will be designated by m.
For this universe and the open statements
j(x): x is a junior 5(*): x is a senior
p(x): x is enrolled in a physical education class
we consider the argument:
No junior or senior is enrolled in a physical education class.
Mary Gusberti is enrolled in a physical education class.
Therefore Mary Gusberti is not a senior.
In symbolic form this argument becomes
Now the following steps (and reasons) establish the validity of this argument.
Steps Reasons
1) Vx [ U M v s(*)) -> - ' P W ] Premise
2) p(m) Premise
3) 0 (m) V s(m)) > Step (1) and the Rule of Universal
Specification
4) p(m) - > - ( j ( m ) V s(m)) Step (3), (q > t) (-it - * #), and the
Law of Double Negation
5) p(m) - > A -'s(m)) Step (4) and DeMorgans Law
6) 'j (m) A 's{m) Steps (2) and (5) and the Rule of
Detachment (or Modus Ponens)
7) Step (6) and the Rule of Conjunctive
Simplification
In Example 2.53 we have had our first opportunity to apply the Rule of Universal Speci
fication. Using the rule in conjunction with Modus Ponens (or the Rule of Detachment) and
2.5 Quantifiers, Definitions, and the Proofs of Theorems 109
Modus Tollens, we are able to state the following corresponding analogs, each of which
involves a universally quantified premise. In either case we consider a fixed universe that
includes a specific member c and make use of the open statements p(x), q(x) defined for
this universe.
These two valid arguments are presented here for the same reason we presented them for the
rules of inference Modus Ponens and ^Todus Tollens in Section 2.3 (in the discussion
between Examples 2.25 and 2.26). We want to examine some possible errors that may arise
when the results in (1) and (2) are not used correctly.
Let us start with the universe of all polygons in the plane. Within this universe we shall
let c denote one specific polygon the quadrilateral E F G H , where the measure of angle
E is 91. For the open statements
And here, as in Section 2.3, the error in reasoning lies in our attempt to argue by the converse.
A second invalid argument from the misuse of argument (2) above can also be
given, as shown in the following.
(2') All squares have four sides.
Quadrilateral E F G H is not a square.
Therefore quadrilateral E F G H does not have four sides.
Translating (2') into symbolic form results in
(2") Vx [p(x) -* q{x)]
-Pic)
.' - 'q ic )
no Chapter 2 Fundamentals of Logic
And now let us look back at the three parts of Example 2.53. Although the arguments
presented there involved premises that were universally quantified statements, there was
never any instance where a universally quantified statement appeared in the conclusion. We
now want to remedy this situation, since many theorems in mathematics have the form of
a universally quantified statement. To do so we need the following considerations.
Start with a given universe and the open statement p(x). To establish the truth of the
statement \fx p ( x ), we must establish the truth of p(c) for each member c in the given
universe. But if the universe has many members or, for example, contains all the positive
integers, then this exhaustive, if not exhausting, task of validating the truth of each p(c)
becomes difficult, if not impossible. To get around this situation we shall prove that p(c)
is true but now we do it for the case where c denotes a specific but arbitrarily chosen
member from the prescribed universe.
Should the preceding open statement p(x) have the form q(x) > r(x), for open state
ments q(x) and r(x), then we shall assume the truth of q(c) as an additional premise and try
to deduce the truth of r(c) by using definitions, axioms, previously proven theorems, and
the logical principles we have studied. For when q(c) is false, the implication q (c) > r{c)
is true, regardless of the truth value of r(c).
The reason that the element c must be arbitrary (or generic) is to make sure that what
we do and prove about c is applicable for all the other elements in the universe. If we are
dealing with the universe of all integers, for example, we cannot choose c in an arbitrary
manner by selecting c as 4, or by selecting c as an even integer. In general, we cannot
make any assumptions about our choice for c unless these assumptions are valid for all the
other elements of the universe. The word generic is applied to the element c here because it
indicates that our choice (for c) must share all of the common characteristics of the elements
for the given universe.
The principle we have described in the preceding three paragraphs is named and sum
marized as follows.
Before we demonstrate the use of this rule in any examples, we wish to look back at
part (1) of Example 2.43 in Section 2.4. It turns out that the explanation given there to
establish that
anticipated what we have now described in detail as the Rules of Universal Specification
and Universal Generalization.
Now well turn to an example which is strictly symbolic. This example provides an
opportunity to apply the Rule of Universal Generalization.
Let p { x ),q (x ), and r{x) be open statements that are defined for a given universe. We show
E X A M P L E 2.54
that the argument
Vx [p(x) -> q(x:)]
\fx [q(x) > r(x)]
.Vx [p(x) -> r(x)]
is valid by considering the following.
Steps Reasons
1 ) Vx; [(p(x) -> q(x)] Premise
2) p ( c ) - * q ( c ) Step (1) and the Rule of Universal Specification
3) Vx; [q(x) > r(x)] Premise
4) q(c) > r(c) Step (3) and the Rule of Universal Specification
5) p(c) -> r(c) Steps (2) and (4) and the Law of the Syllogism
6) /.V s [/?(*) -> r(*)] Step (5) and the Rule of Universal Generalization
Here the element c introduced in steps (2) and (4) is the same specific but arbitrarily
chosen element from the universe. Since this element c has no special or distinguishing
properties but does share all of the common features of every other element in this universe,
we can use the Rule of Universal Generalization to go from step (5) to step (6).
And so at last we have dealt with a valid argument where a universally quantified state
ment appears as the conclusion, as well as among the premises.*1
The question that now may be at the back of the readers mind is one of practicality.
Namely, when would we ever need to use the argument that we validated in Example 2.54?
We may find that we have already used it (perhaps, unknowingly) in earlier algebra and
geometry courses, as we demonstrate in the following example.
a) For the universe of all real numbers, consider the open statements
E X A M P L E 2.55
p(x): 3x 1 = 20 q(x): 3x = 27 r(x): x = 9.
The following solution of an algebraic equation parallels the valid argument from
Example 2.54.
1) If 3x 7 = 20, then 3x = 27. Vx [p(x) > q(x)]
2) If 3x = 27, then x = 9. \fx [q(x) - r(x)]
3) Therefore, if 3x 7 = 20, then x = 9 . Vx; [p(x) > r(x)]
b) When we dealt with the universe of all quadrilaterals in plane geometry, we may have
found ourselves relating something like this:
Since every square is a rectangle, and every rectangle
is a parallelogram, it follows that every square is a parallelogram.
In this case we are using the argument in Example 2.54 for the open statements
The steps and reasons needed to establish the validity of the argument
E X A M P L E 2.56
Vx [p{x) v q(x)]
V* [(~'P(x) A q{x)) -> r(x)]
Vx [ (jc) p ( x )]
are given as follows. [Here the element c is in the universe assigned for the argument. Also,
since the conclusion is a universally quantified implication, we can assume - r ( c ) as an
additional premise as was mentioned earlier when the Rule of Universal Generalization
was first introduced.]
Steps Reasons
i) Vx [ p ( x ) v q ( x ) ] Premise
2) p(c) V q(c) Step (1) and the Rule of Universal
Specification
3) Vx [(-/>(*) A<?(x)) -* r(x)] Premise
4) h p ( c ) A i ( c ) ] -* r(c) Step (3) and the Rule of Universal
Specification
5) ~t (c) -* >[/(:) A q(c)] Step (4) and s t -'t -> -*s
6) -r(c) -+ [p (c) V -q(c)] Step (5), DeMorgans Law, and the Law of
Double Negation
7) -.r(c) Premise (assumed)
8) p(c) V ->q(c) Steps (7) and (6) and Modus Ponens
9) [p{c) V q(c)] A [p(c) V - ^ ( c ) ] Steps (2) and (8) and the Rule of Conjunction
10 ) p(c) V [q(c) A - ^ ( c ) ] Step (9) and the Distributive Law of v over A
ID P(c) Step (10), q{c) A '<7(e) = Fo, and
p(c) v F0 p(c)
12 ) Vx [ - r ( x ) p ( x )] Steps (7) and (11) and the Rule of Universal
Generalization
Before going on we want to point out a convention that the reader may not like but
will have to get used to. It concerns our coverage of the Rules of Universal Specification
and Universal Generalization. In the first case we started with the statement Vx; p(x) and
then dealt with p(c) for some specific element c in our universe. For the Rule of Universal
Generalization we obtained the truth of Vjt p(x) from that of p (c ), where c was arbitrarily
selected from the universe. Unfortunately, well often find ourselves using the letter x
instead of c to denote the element but as long as we understand what is happening we
shall soon find the convention easy enough to work with.
The results of Example 2.54 and especially Example 2.56 lead us to believe that we can
use universally quantified statements and the rules of inference including the Rules of
Universal Specification and Universal Generalization to formalize and prove a variety of
arguments and, hopefully, theorems. When we do so it appears that the validation of some
rather short arguments requires quite a number of steps, because we have been very metic
ulous and included all the steps and reasons we left little, if anything, to the imagination.
The reader should rest assured that when we start to prove mathematical theorems, we shall
present the proofs in the more conventional paragraph style. We shall no longer mention
2.5 Quantifiers, Definitions, and the Proofs of Theorems 113
each and every application of the laws of logic and the other tautologies or the rules of
inference. On occasion we may single out a certain rule of inference, but our attention will
be primarily directed to the use of definitions, mathematical axioms and principles (other
than those we have found in our study of logic), and other (earlier) theorems we have been
able to prove. Why then have we been learning all of this material on validating arguments?
Because it will provide us with a framework to fall back on whenever we doubt whether
a given attempt at a proof really does the job. If in doubt, we have our study of logic to
supply us with a somewhat mechanical but strictly objective means to help us decide.
And now we present paragraph-style proofs for some results about the integers. (These
results may be considered rather obvious to us in fact, we may find we have already
seen and used some of them. But they provide an excellent setting for writing some simple
proofs.) The proofs we shall presently introduce use the following ideas, which we now
formally define. [The first idea was mentioned earlier in part (b) of Example 2.51.]
Definition 2.8 Let n be an integer. We call n even if n is divisible by 2 that is, if there exists an integer
r so that n = 2r. If n is not even, then we call n odd and find for this case that there exists
an integer s where n = 2s + 1 .
T H EO R EM 2.2 For all integers k and /, if k, l are both odd, then k + 1 is even.
Proof: In this proof we shall number the steps so that we may refer to them for some later
remarks. After this we shall no longer number the steps.
1) Since k and / are odd, we may write k = 2a + 1 and / = 2b + 1, for some integers
a, b. This is due to Definition 2.8.
2) Then
by virtue of the Commutative and Associative Laws of Addition and the Distributive
Law of Multiplication over Addition all of which hold for integers.
3) Since a, b are integers, a + b + l = c is an integer; with k + l = 2c, it follows from
Definition 2.8 that k + 1 is even.
Rem arks
1) In step (1) of the preceding proof k and / were chosen in an arbitrary manner, so we
know by the Rule of Universal Generalization that the result obtained is true for all
odd integers.
2) Although we may not realize it, we are using the Rule of Universal Specification
(twice) in step (1). The first argument implicit in this step reads as follows.
i) If n is an odd integer, then n = 2r -j- 1 for some integer r.
ii) The integer k is a specific (but arbitrarily chosen) odd integer.
iii) Therefore we may write k = 2a + 1 for some (specific) integer a.
3) In step (1) we do not have k = 2a + 1 and / = 2a + 1. Since k, l are arbitrarily
chosen, it may be the case that k = l and when this happens we have 2a + 1 =
k = l = 2b -1- 1, from which it follows that a = b. [Since k may not equal /, it follows
114 Chapter 2 Fundamentals of Logic
that (k l) /2 = a may not equal b = (/ l)/2 . Thus we should use the different
variables a and b .]
Before we proceed with another theorem written in the more conventional manner
let us examine the following.
We close at last with three results to demonstrate how we shall write proofs through
out the remainder of the text.
T H E O R E M 2.3 For all integers k and /, if k and / are both odd, then their product kl is also odd.
Proof: Since k and / are both odd, we may write k = 2a + 1 and / = 2Z? -f- 1, for some
integers a and b because of Definition 2.8. Then the product kl = (2a + 1)(2b + 1) =
4ab -1- 2a + 2b + 1 = 2(2ab + a + b) + 1, where 2ab + a + b is an integer. Therefore, by
Definition 2.8 once again, it follows that kl is odd.
The preceding proof is an example of a direct proof. In our next example we shall prove
a result in three ways: first by a direct argument (or proof), then by the contrapositive
method, and finally by the method of proof by contradiction. [For the (method of) proof
by contradiction we put in some extra details, since this is our first opportunity to use this
technique.] The reader should not assume, however, that every theorem can be so readily
proved in a variety of ways.
3) Now assume that ra is even and that ra + 7 is also even. (This assumption is the
negation of what we want to prove.) Then ra + 7 even implies that ra + 7 = 2c for
some integer c. And, consequently, m 2c 1 2c - 8 + 1 = 2(c - 4) + 1 with
c 4 an integer, so ra is odd. Now we have our contradiction. We started with ra even
and deduced ra odd an impossible situation, since no integer can be both even and
odd. How did we arrive at this dilemma? Simple we made a mistake! This mistake
is the false assumption namely, ra + 7 is even that we wanted to believe at the
start of the proof. Since the assumption is false, its negation is true, and so we now
have ra + 7 odd.
The second and third proofs for Theorem 2.4 appear to be somewhat similar. This is
because the contradiction we derived in the third proof arises from the hypothesis of the
theorem and its negation. We shall see as we progress (as early as the next chapter) that a
contradiction may also be obtained by deriving the negation of a known fact a fact that
is not the hypothesis of the theorem we are attempting to prove. For now, however, let us
think about this similarity a little more. Suppose we start with the open statements p(m)
and q{m) for a prescribed universe and consider a theorem of the form Vra [p(m) >
q(m)]. If we try to prove this result by the contrapositive method, then we shall actually
prove the logically equivalent statement Vra [--g(ra) > ->/7(ra)]. To do so we assume the
truth of --g(ra) (for any specific but arbitrarily chosen ra in the universe) and show that
this leads to the truth of --/?(ra). On the other hand, if we wish to prove the theorem
Vra [p(m) q(m)] by the method of proof by contradiction, then we assume that the
statement Vra [p(m) -> q(m)] is false. This amounts to the fact that p(m) -> q(m) is false
for at least one replacement for ra from the universe that is, there is some element ra
in the universe for which p(m) is true and q(m) is false [or -q(m ) is true]. We then use
the truth of p(m) and --g(ra) to derive a contradiction. [In the third proof of Theorem 2.4
we obtained p(m) A - ip(m).] These two methods can be compared symbolically in the
following where ra is specific but arbitrarily chosen for the method of contraposition.
Assumption Result Derived
Contraposition -q(m ) -*p (ra)
Contradiction /?(ra) and -^q{m) Fq
In general, when we are able to establish a theorem by either a direct proof or an indirect
proof, the direct approach is less cumbersome than an indirect approach. (This certainly
appears to be the case for the three proofs presented for Theorem 2.4.) When we do not
have any prescribed directions given for attempting the proof of a certain theorem, we might
start with a direct approach. If we succeed, then all is well. If not, then we might consider
trying to find a counterexample to what we thought was a theorem. Should our search for
a counterexample fail, then we might consider an indirect approach. We might prove the
contrapositive of the theorem, or obtain a contradiction, as we did in the third proof of
Theorem 2.4, by assuming the truth of the hypothesis and the truth of the negation of the
conclusion (for some element ra in the universe) in the given theorem.
We close this section with one more indirect proof by the method of contraposition.
TH EO REM 2.5 For all positive real numbers jt and y, if the product jty exceeds 25, then jc > 5 or y > 5.
Proof: Consider the negation of the conclusion that is, suppose that 0 < jt < 5 and 0 <
y < 5. Under these circumstances we find that 0 = 0 0 < jc y < 5 5 = 25, so the product
116 Chapter 2 Fundamentals of Logic
x y does not exceed 25. (This indirect method of proof now establishes the given statement,
since we know that an implication is logically equivalent to its contrapositive.)
Steps Reasons 12. Give a direct proof (as in Theorem 2.3) for each of the
1) Vx [p(x) Vq(x)] Premise following.
2) 3x -'p (x ) Premise
a) For all integers k and /, if k, l are both even, then k + /
3) ->p(a) Step (2) and the definition of
is even.
the truth for 3x ->p(x). [Here
a is an element (replacement) b) For all integers k and /, if k, l are both even, then kl is
from the universe for which even.
- p (x ) is true.] The reason for 13. For each of the following statements provide an indirect
this step is also referred to as proof [as in part (2) of Theorem 2.4] by stating and proving the
the Rule o f Existential contrapositive of the given statement.
Specification. a) For all integers k and /, if kl is odd, then k, l are both
4) p(a) V q{a) odd.
5) q{a)
b ) For all integers k and /, if k + / is even, then k and / are
6) Vjc [<7(jc) V r(jt)]
both even or both odd.
7) ^( f l ) v r ( f l )
8) ^(a)->r(fl) 14. Prove that for every integer n, if n is odd, then n2 is odd.
9) r(fl) 15. Provide a proof by contradiction for the following: For
10) Vjc [s (jc) -r(jc)] every integer n, if n2 is odd, then n is odd.
11) s () -> -*r(fl) 16. Prove that for every integer n, n2 is even if and only if n is
12) r i a ) -> -*s(a)
even.
13) -.j(fl)
14)1 Step (13) and the definition 17. Prove the following result in three ways (as in Theorem
of the truth for 3x The 2.4): If n is an odd integer, then n + 11 is even.
reason for this step is also 18. Let m, n be two positive integers. Prove that if m, n are
referred to as the Rule of perfect squares, then the product mn is also a perfect square.
Existential Generalization. 19. Prove or disprove: If m, n are positive integers and m, n
11. Write the following argument in symbolic form. Then either are perfect squares, then m + n is a perfect square.
verify the validity of the argument or explain why it is invalid. 20. Prove or disprove: There exist positive integers m, n,
[Assume here that the universe comprises all adults (18 or over) where m, n, and m + n are all perfect squares.
who are presently residing in the city of Las Cruces (in New 21. Prove that for all real numbers x and y, if x + y > 100, then
Mexico). Two of these individuals are Roxe and Imogene.] x > 50 or y > 50.
All credit union employees must know COBOL. All credit
22. Prove that for every integer n, An + 7 is odd.
union employees who write loan applications must know Ex
cel.1 Roxe works for the credit union, but she doesnt know 23. Let n be an integer. Prove that n is odd if and only if In + 8
Excel. Imogene knows Excel but doesnt know COBOL. There is odd.
fore Roxe doesnt write loan applications and Imogene doesnt 24. Let n be an integer. Prove that n is even if and only if
work for the credit union. 3 In + 12 is even.
2.6
Sum m ary and Historical Review
This second chapter has introduced some of the fundamentals of logic in particular, some
of the rules of inference and methods of proof necessary for establishing mathematical
theorems.
The first systematic study of logical reasoning is found in the work of the Greek philoso
pher Aristotle (384-322 B.C.). In his treatises on logic Aristotle presented a collection of
principles for deductive reasoning. These principles were designed to provide a foundation
for the study of all branches of knowledge. In a modified form, this type of logic was taught
up to and throughout the Middle Ages.
considerably. Then, in 1854, Boole detailed his ideas and further research in the notable
work An Investigation in the Laws o f Thought, on Which Are Founded the Mathematical
Theories o f Logic and Probability. The American logician Charles Sanders Peirce (1839
1914), who was also an engineer and philosopher, introduced the formal concept of the
quantifier into the study of symbolic logic.
The concepts formulated by Boole were thoroughly examined in the work of another
German scholar, Ernst Schroder (1841-1902). These results are known collectively as Vor-
lesungen iiber die Algebra der Logik\ they were published in the period from 1890 to
1895.
Further developments in the area saw an even more modern approach evolve in the work
of the German logician Gottlieb Frege (1848-1925) between 1879 and 1903. This work
significantly influenced the monumental Principia Mathematica (1910-1913) by Englands
Alfred North Whitehead (1861-1947) and Bertrand Russell (1872-1970). Here what was
begun by Boole was finally brought to fruition. Thanks to this remarkable effort and the work
of other twentieth-century mathematicians and logicians, in particular the comprehensive
Grundlagen der Mathematik (1934-1939) of David Hilbert (1862-1943) and Paul Bemays
(1888-1977), the more polished techniques of contemporary mathematical logic are now
available.
Several sections of this chapter stressed the importance of proof. In mathematics a proof
bestows authority on what might otherwise be dismissed as mere opinion. Proof embodies
the power and majesty of pure reason. But even more than that, it suggests new mathematical
ideas. Our concept of proof goes hand in hand with the notion of a theorem a mathematical
statement the truth of which has been confirmed by means of a logical argument, namely, a
proof For those who feel they can ignore the importance of logic and the rules of inference,
we submit the following words of wisdom spoken by Achilles in Lewis Carrolls What the
Tortoise Said to Achilles'. Then Logic would take you by the throat, and force you to do
it!
Comparable coverage of the material presented in this chapter can be found in Chapters
2 and 11 of the text by K. A. Ross and C. R. B. Wright [11]. The first two chapters of the
text by S. S. Epp [3] provide many examples and some computer science applications for
those who wish to see more on logic and proof at a very readable introductory level. The
text by H. Delong [2] provides an historical survey of mathematical logic, together with an
examination of the nature of its results and the philosophical consequences of these results.
This is also the case with the texts by H. Eves and C. V. Newsom [4], R. R. Stoll [13], and
R. L. Wilder [14], wherein the relationships among logic, proof, and set theory (the topic
of our next chapter) are examined in their roles in the foundations of mathematics.
For more on resolution (introduced in Exercise 13 of Section 2.3) and automated rea
soning, the reader should examine the texts by J. H. Gallier [6] and M. R. Genesereth and
N. J. Nilsson [7].
The text by E. Mendelson [9] provides an interesting intermediate introduction for those
readers who wish to pursue additional topics in mathematical logic. A somewhat more
advanced treatment is given in the work of S. C. Kleene [8]. Accounts of other work in
mathematical logic are presented in the compendium edited by J. Barwise [1].
The objective of the works by D. Fendel and D. Resek [5] and R. R Morash [10] is to
prepare the student with a calculus background for the more theoretical mathematics found
in abstract algebra and real analysis. Each of these texts provides an excellent introduction
to the basic methods of proof. The unique text by D. Solow [12] is devoted entirely to
introducing the reader who has a background in high school mathematics to the primary
techniques used in writing mathematical proofs.
120 Chapter 2 Fundamentals of Logic
REFERENCES
1. Barwise, Jon (editor). Handbook o f Mathematical Logic. Amsterdam: North Holland, 1977.
2. Delong, Howard. A Profile o f Mathematical Logic. Reading, Mass.: Addison-Wesley, 1970.
3. Epp, Susanna S. Discrete Mathematics with Applications, 2nd ed. Boston, Mass.: PWS Pub
lishing Co., 1995.
4. Eves, Howard, and Newsom, Carroll V. An Introduction to the Foundations and Fundamental
Concepts o f Mathematics, rev. ed. New York: Holt, 1965.
5. Fendei, Daniel, and Resek, Diane. Foundations o f Higher Mathematics. Reading, Mass.:
Addison-Wesley, 1990.
6. Gallier, Jean H. Logic for Computer Science. New York: Harper & Row, 1986.
7. Genesereth, Michael R., and Nilsson, Nils J. Logical Foundations o f Artificial Intelligence.
Los Altos, Calif: Morgan Kaufmann, 1987.
8. Kleene, Stephen C. Mathematical Logic. New York: Wiley, 1967.
9. Mendelson, Elliott. Introduction to Mathematical Logic, 3rd ed. Monterey, Calif.: Wadsworth
and Brooks/Cole, 1987.
10. Morash, Ronald P. Bridge to Abstract Mathematics: Mathematical Proof and Structures. New
York: Random House/Birkhaiiser, 1987.
11. Ross, Kenneth A., and Wright, Charles R. B. Discrete Mathematics, 4th ed. Upper Saddle
River, N.J.: Prentice-Hall, 1999.
12. Solow, Daniel. How to Read and Do Proofs, 3rd ed. New York: Wiley, 2001.
13. Stoll, Robert R. Set Theory and Logic. San Francisco: Freeman, 1963.
14. Wilder, Raymond L. Introduction to the Foundations o f Mathematics, 2nd ed. New York:
Wiley, 1965.
9. For each of the following, fill in the blank with the word
b) Translate the statement in part (a) into words such that
converse, inverse, or contrapositive so that the result is a true
the word not does not appear in the translation.
statement.
3. Let p, q, and r denote primitive statements. Prove or dis
a) The converse of the inverse of p -> q is the
prove (provide a counterexample for) each of the following.
___________________________of p ^ q .
a) [p < -> {q < -> r)] [(p <+q) <+r] b) The converse of the inverse of p -> q is the
b) [p {q r)] [(p q) r] ___________________________of q -> P-
4. Express the negation of the statement p <-> q in terms of c) The inverse of the converse of p -> q is the
the connectives A and v . ___________________________of P -> q
5. Write the following statement as an implication in two d) The inverse of the converse of p q is the
ways, each in the if-then form: Either Kaylyn practices her piano ___________________________of q > p.
lessons or she will not go to the movies. e) The inverse of the contrapositive of p -> q is the
___________________________of P ^ q -
6. Let p, q, r denote primitive statements. Write the converse,
inverse, and contrapositive of 10. Establish the validity of the argument
a) p > (q A r ) b) (pvq)-+r [O -> q) A [(q A r ) - > s ] A r ] - t (p s).
Supplementary Exercises 121
11. Prove or disprove each of the following, where p , q , and r 15. Suppose two opposite comer squares are removed from an
are any statements. 8 X 8 chessboard as in part (a) of Fig. 2.4. Can the remaining
a) [ ( p Y q ) Y r U = > [ p Y ( q Y r)] 62 squares be covered by 31 dominos (rectangles consisting of
two adjacent squares one white and the other blue, as shown
b) [p Y (q -> r)] [(p Y q ) ( p Y r)] in the figure)? (When a domino is placed on the chessboard, a
12. Write the following argument in symbolic form. Then ei square of a given color need not be placed on a square of the
ther establish the validity of the argument or provide a counter same color.)
example to show that it is invalid.
p(x,y): y-x=y+x2
where the universe for each of the variables x, y comprises all E=u=] [=lP
integers. Determine the truth value for each of the following
statements.
Figure 2.4
a) p(0, 0) b) M l, 1)
C) MO, 1 ) d) Vy MO, y) 16. In part (b) of Fig. 2.4 we have an 8 X 8 chessboard where
e)3yp(l,y) f) Vx 3y p( x, y ) two squares (one blue and one white) have been removed from
g) 3y V* p(x, y) h) Vy 3x p(x, y) each of two opposite comers. Can the remaining 60 squares be
covered by 15 T-shaped figures (of three white squares and one
14. Determine whether each of the following statements is true
blue one, or three blue squares and one white one as shown
or false. If false, provide a counterexample. The universe com
in the figure)? [The reader may wish to verify that a 4 X 4
prises all integers.
chessboard (of all 16 squares) can be covered by four of the
a) Vx By Bz {x = l y + 5 z) T-shaped figures. Then it follows that an 8 X 8 chessboard (of
b) Vx By Bz (x = 4y + 6 z) all 64 squares) can be covered by 16 of the T-shaped figures.]
3
Set Theory
3.1
Sets and Subsets
We have a gut feeling that a set should be a well-defined collection of objects. These
objects are called elements and are said to be members of the set.
The adjective well-defined implies that for any element we care to consider, we are able
to determine whether it is in the set under scrutiny. Consequently, we avoid dealing with
sets that depend on opinion, such as the set of outstanding major league pitchers for the
1990s.
We use capital letters, such as A, B, C, .. ., to represent sets and lowercase letters to
represent elements. For a set A we write jc e A if jt is an element of A; y A indicates that
y is not a member of A.
A set can be designated by listing its elements within set braces. For example, if A is the set
E X A M P L E 3.1
consisting of the first five positive integers, then we write A = {1, 2, 3, 4, 5}. Here 2 e A
but 6 ^ A.
123
124 Chapter 3 Set Theory
Another standard notation for this set provides us with A = {x\x is an integer and 1 <
jt < 5}. Here the vertical line | within the set braces is read such that. The symbols {x | ...}
are read the set of all jt such that. . . . The properties following | help us determine the
elements of the set that is being described.
Beware! The notation {jc| 1 < jc < 5} is not an adequate description of the set A unless
we have agreed in advance that the elements we are considering are integers. When such an
agreement is adopted, we say that we are specifying a universe, or universe o f discourse,
which is usually denoted by IL We then select only elements from \l to form our sets. In this
particular problem, if U denotes the set of all integers or the set of all positive integers, then
{x 11 < x < 5} adequately describes A. If U is the set of all real numbers, then {x | 1 < x < 5}
would contain all of the real numbers between 1 and 5 inclusive; if \l consists of only even
integers, then the only members of {x | 1 < x <5} would be 2 and 4.
For U = {1, 2, 3, . ..}, the set of positive integers, we consider the following sets. At the
E X A M P L E 3.2
same time we introduce various notations one may use to describe such sets.
a) A = {1, 4, 9, . . . , 64, 81} = {x2|x e % x 2 < 100} = {x2|x e <Ua x 2 < 100}
b) B = {1, 4, 9, 16} = {y2\y e % y 2 < 20} = {y2\y e % y 2 < 23}
= {y2\y e U a y 2 < 16}.
c) C = {2, 4, 6, 8, ...} = {2k\k e ll}.
Sets A and B are examples of finite sets, whereas C is an infinite set. When dealing with
sets like A or C, we can either describe the sets in terms of properties the elements must
satisfy or list enough elements to indicate what is, we hope, an obvious pattern. For any
finite set A, \A\ denotes the number of elements in A and is referred to as the cardinality,
or size, of A. In this example we find that \A\ = 9 and \B\ = 4 .
Here the sets B and A are such that every element of B is also an element of A. This
important relationship occurs throughout set theory and its applications, and it leads to the
following definition.
Definition 3.1 If C, D are sets from a universe U, we say that C is a subset of D and write C c D, or
D 3 C, if every element of C is an element of D. If, in addition, D contains an element that
is not in C, then C is called a proper subset of D, and this is denoted by C C D or D D C.
However, for H = {1, 2, 3, 4, 5}, C = {1, 2}, and D = {1, 2}, we see that C is a subset of
D (that is, C c D), but it is not a proper subset of D (or, C ( D). So, in general, we do not
find that C C D ^ C c D .
The subset concept may now be used to develop the idea of set equality. First we consider
the following example.
For the universe U = {1, 2, 3, 4, 5}, consider the set A = {1, 2}. If B = {.x\x2 G U}, then
E X A M P L E 3.4
the members of B are 1, 2. Here A and B contain the same elements and no other
element(s) leading us to feel that the sets A and B are equal.
However, it is also true here that A c . B and B c A, and we prefer to formally define
the idea of set equality by using these subset relations.
Definition 3.2 For a given universe U, the sets C and D (taken from U) are said to be equal, and we write
C = D, when C C D and D c C.
From these ideas on set equality, we find that neither order nor repetition is relevant for a
general set. Consequently, we find, for example, that {1, 2, 3} = {3, 1, 2} = {2, 2, 1, 3} =
{1 , 2 , 1,3, 1 }.
Now that we have defined the concepts of subset and set equality, we shall use the
quantifiers of Section 2.4 to examine the negations of these ideas.
For a given universe U, let A, B be sets taken from U. Then we may write
LetU = {1, 2, 3, 4, 5, 6, x, y, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}} (where x, y are the 24th, 25th
E X A M P L E 3.5
lowercase letters of the alphabet and do not represent anything else, such as 3, 5, or {1, 2}).
Then |U| = 11.
a) If A = {1, 2, 3, 4},then |A| = 4 and here we have
i) A c U; ii) A c U; iii) A g U;
iv) {A} c U; v) {A} c U; but vi) {A} ^ U.
b) Now let B = {5, 6, x, y, A} = {5, 6, x, y, {1, 2,3, 4}}. Then \B\ = 5,not$. Andnow
we find that
i) A g B; ii) {A} c B; and iii) {A} c B.
But
iv) {A} ^ B\
v) A ^ B (that is, A is not a subset of B)\ and
vi) A<j_B (that is, A is not a proper subset of B).
T H E O R E M 3.1 Let A, 5 , C c T t
a) If A c B and 5 C C , then A C C . b) If A cB and B C.C, then A c C.
c) If A c 5 and 5 C C, then A C C. d) If A C 5 and 5 C C, then A C C.
Before we prove this theorem we want to recall a comment we made back in Section 2.5. It
concerns our coverage of the Rules of Universal Specification and Universal Generalization
and appears after Example 2.56. For now it is appropriate in this new area on set theory.
When we want to prove, for example, that ; t e A = > j t e C , w e shall start by considering any
fixed but arbitrarily chosen element x in H but we shall want this element x to be such
that jc g A is a true statement (not an open statement). Then we must show that this same
fixed but arbitrarily chosen element x is also in C. The proofs we present are consequently
referred to as element arguments. Always remember that in these proofs x represents a fixed
but arbitrarily chosen element of A and though jc is generic (since it is not a specifically
named element in A), it does remain the same throughout each proof.
3.1 Sets and Subsets 127
Proof: We shall prove parts (a) and (b) and leave the remaining parts for the exercises.
a) To prove that A c C, we need to verify that for all * g U, if * g A then * g C. We start
with an element* from A. Since A C 5 , x g A implies* g B. Then with B c C, * g B
implies * g C. So * g A implies * e C (by the Law of the Syllogism Rule 2 in Table
2.19 since * g A, * g B, and * g C are statements), and A c C.
b) Since A c B, if * g A then * g B. With B c C, it then follows that * g C, so A c C.
However, A c B => there exists an element b e B such that b ^ A. Because 5 C C ,
b G B => b G C . Thus A C C and there exists an element b E C with b A, so
AcC.
Let = {1, 2, 3, 4, 5} with A = {1, 2, 3}, B = {3, 4}, and C = {1, 2, 3, 4}. Then the fol
E X A M P L E 3.6
lowing subset relations hold:
a) A c C b) A c C
c) B c C d) A c A
e) B< A
f ) A < A (that is, A is not a proper subset of A)
The sets A, B are just two of the subsets of C. We are interested in determining how
many subsets C has in total. Before answering, however, we need to introduce the set with
no members.
Definition 3.3 The null set, or empty set, is the (unique) set containing no elements. It is denoted by 0 or { }.
We note that |0| = 0 but {0} ^ 0. Also, 0 ^ {0} because {0} is a set with one element,
namely, the null set.
The empty set satisfies the following property given in Theorem 3.2. To establish this
property we use the method of proof by contradiction (or reductio ad absurdum). Following
the proof of Theorem 2.4 (in Section 2.5), we said that in establishing a theorem by this
method, we assumed the negation of the result and arrived at a contradiction. In our prior
work (as found in Example 2.32 and the third proof of Theorem 2.4), we arrived at a
contradiction of the form r A *r or p(m) A --/?(ra), respectively where -<r was a premise
in Example 2.32 and p{m ) a specific instance of the hypothesis in Theorem 2.4. In proving
Theorem 3.2 things are now a little different. This time we shall find ourselves denying (or
contradicting) an earlier result we have accepted as true, namely, the definition of the null
set.
Returning now to Example 3.6 we determine the number of subsets of the set C = {1, 2,
E X A M P L E 3.7
3, 4}. In constructing a subset of C, we have, for each member jc of C, two distinct choices:
Either include it in the subset or exclude it. Consequently, there are 2 X 2 X 2 X 2 choices,
resulting in 24 = 16 subsets of C. These include the empty set 0 and the set C itself. Should
we need the number of subsets of two elements from C, the result is the number of ways
two objects can be selected from a set of four objects, namely, C(4, 2) or (2). As a result,
the total number of subsets of C, 24, is also the sum (q) + (j) + (^) + (4) + (), where the
first summand is for the empty set, the second summand for the four singleton subsets, the
third summand for the six subsets of size 2, and so on. So 24 = (*)
Definition 3.4 If A is a set from universe U, the power set of A, denoted 2P(A),1" is the collection (or set)
of all subsets of A.
For the set C of Example 3.7, 9>(C) = {0, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3},
E X A M P L E 3.8
{2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, C}.
For any finite set A with |A | n > 0, we find that A has T subsets andthat j 2 P ( A ) | = 2n.
For any 0 < k < n * there are (f) subsets of size L Counting the subsets o f A according
to the number, k, of elements in a subset, we have the combinatorial identity
This identity was established earlier in Corollary 1.1(a). The presentation here is another
example of a combinatorial proof because the identity is established by counting the same
collection of objects (subsets of A) in two different ways.
A systematic way to represent the subsets of a given nonempty set can be accomplished
by using a coding scheme known as a Gray code. This is demonstrated in our next example.
Consider the binary strings (of 0s and l s) in Fig. 3.1. In particular, examine the first column
E X A M P L E 3.9
of the strings in part (b). How did this column come about? First we see 0, then 1 as in
part (a) of the figure. Then we see 1 followed by 0 the reverse order (from bottom to top)
of the two binary strings in part (a). Once we obtain the first column for the binary strings
in part (b), we then list two 0s followed by two l s.
Continuing with the strings in part (c) of the figure, now we concentrate on the first two
columns. The first four entries (binary strings of length 2) are precisely the four strings
in part (b). The last four entries (again, binary strings of length 2) are likewise the binary
strings in part (b) now in reverse order (from bottom to top). For these eight strings of
length 2, we append 0 to the right of the first four and 1 to the right of the last four.
For each Gray code in parts (a), (b), (c) of the figure, as we go from one binary string (in
a column) to the next binary string (in that column), there is exactly one bit that changes.
For instance, in part (b), in going from 10 to 11, we find one change (from 0 to 1) in the
second position. Furthermore, for the third and fourth strings in part (c), as we go from
t In some computer science textbooks the reader may find the notation 2A used for SP(A).
3.1 Sets and Subsets 129
110 to 010, there is exactly one change from 1 to 0 in the first position. The fourth and
fifth strings have the one change from 0 to 1 this time in the third position. Also notice
how the first and last strings for each code differ in the last position. Part (d) of the figure
demonstrates this for the strings of length 3.
This technique, for constructing a Gray code for the strings of length 2 from those of
length 1 and the strings of length 3 from those of length 2, is an example of a recursive
construction. (This idea will be examined in more detail in Section 4.2.)
When we examine each Gray code in parts (a), (b), (c) of Fig. 3.1, we see a listing of
subsets to the right of each of these codes. For example, in part (b), if we start with the set
A = {jc, y} and keep the order of the elements fixed,^ then we can list the subsets of A in
terms of binary strings of length 2. We write 0 for an element when it is not in the subset and
1 when it is. Hence the subset {x} is encoded as 10 because the first element x (of ordered
set A) is in the subset, while the second element y (of ordered set A) is not present as
the 0, in 10, indicates. For part (c), the (ordered) set B = {x, y, z } has its eight subsets listed
next to the elements of the Gray code. As we go from one subset to the next (in a given
column), we see that there is exactly one change in the makeup of the subset. For instance,
in going from {jt, y } (110 ) to {y} (010), exactly one element is deleted as indicated by
the change from 1 to 0 in the first positions of 110 and 010. Likewise, as we go from {z}
(001) to 0 (000), exactly one element is deleted the change from 1 to 0, in the third bits
of 001 and 000, indicates this. Examining the change from {y, z} (011) to {x, y, z} (111),
we see that one new element is added here it is jc. The change from 0 to 1 as we go from
0 11 to 1 1 1 takes this into account.
Note that the first four subsets in part (c) are the four subsets in part (b). Further, the last
four subsets in part (c) come about from the same four subsets in part (b) this time in
reverse order and with the element z included in each subset.
The recursive construction given here shows how we can continue to develop Gray codes
for binary strings of longer length. When this coding scheme was introduced just prior
to the start of this example we spoke of it as a Gray code, not as the Gray code. Other
Gray codes are possible. The code in part (e) of Fig. 3.1 provides a second Gray code for
the eight binary strings of length 3. Furthermore, if we no longer require the first and last
entries in a code to differ in only one position, then the code in part (f) of Fig. 3.1 would
also serve as a Gray code for the eight binary strings of length 3.
^Originally we considered the elements of a set as unordered, so we are making an exception here. In textbooks
dealing with data structures, such ordered sets are often referred to as lists and one finds, for instance, the ordered
set {*, y, z } denoted by [jc, y, z\ or (jc, y, z).
130 Chapter 3 Set Theory
The ability to count certain, or all, subsets of a given set provides a second approach for
the solution of two of our earlier examples.
In Example 1.14, we counted the number of (staircase) paths in the x y -plane from (2, 1) to
E X A M P L E 3.10
(7, 4) where each such path is made up of individual steps going one unit to the right (R)
or one unit upward (U). Figure 3.2 is the same as Fig. 1.1, where two of the possible paths
are indicated.
/ J/
4 ' ---- , k
t 4 '
3 3
2 2
1 --- ( t 1 1
---
\i
*A A
1 2 3 4 5 6 7 I 2 3 4 5 6 7
Figure 3.2
The path in Fig. 3.2(a) has its three upward (U) moves located in positions 2, 5, and 8
of the list at the bottom of the figure. Consequently, this path determines the three-element
subset {2, 5, 8} of the set {1, 2, 3, . . . , 8}. In Fig. 3.2(b) the path determines the three-
element subset {1, 5, 6}. Conversely, if we start, for example, with the subset {1, 3, 7} of
{1, 2, 3, . . . , 8}, then the path that determines this subset is given by U, R, U, R, R, R,
U, R.
Consequently, the number of paths sought here equals the number of subsets A of
/ 8\ 8!
{1, 2, 3, . . . , 8}, where \A\ = 3. There are 1 1 = = 56 such paths (and subsets),
as we found in Example 1.14.
If we had considered the moves R to the right, instead of the upward moves U, we would
have found the answer to be the number of subsets B of {1,2, 3 , . . . , 8}, where \B\ = 5 .
8 8!
There are = 56 such subsets. (The idea presented here was examined earlier
53!
for the result developed in Table 1.4.)
In part (b) of Example 1.37 of Section 1.4 we learned that there are 26 compositions for the
E X A M P L E 3.11
integer 7 that is, there are 26 ways to write 7 as a sum of one or more positive integers,
where the order of the summands is relevant. The result we obtained there used the binomial
theorem in conjunction with the answers for seven cases that were summarized in Table 1.9.
Now we shall obtain this result in a somewhat different and easier way.
First consider the following composition of 7:
+ i + i + i + i + l +
; l ; ;
1st plus 2nd plus ... 5th plus 6th plus
sign sign sign sign
Here we have seven summands, each of which is 1, and six plus signs.
3.1 Sets and Subsets 131
For the set {1, 2, 3, 4, 5, 6} there are 26 subsets. But what does this have to do with the
compositions of 7?
Consider a subset of {1, 2, 3, 4, 5, 6}, say {1, 4, 6}. Now form the following composition
of 7:
(1 + 1) + 1 + (1 + 1) + (1 + 1)
4 4 4
1st plus 4th plus 6th plus
sign sign sign
Here the subset {1,4,6} indicates that we should place parentheses around the l s on either
side of the first, fourth, and sixth plus signs. This results in the composition
2 + 1 + 2 + 2.
If the same way we find that the subset {1, 2, 5, 6} indicates the use of the first, second,
fifth, and sixth plus signs, giving us
(1 + 1 + 1) + 1 + (1 + 1 + 1)
4 4 4 4
1st plus 2nd plus 5th plus 6th plus
sign sign sign sign
or the composition 3 + 1 + 3 .
Going in reverse we see that the composition 1 + 1 + 5 comes from
1 + 1 + (1 + 1 + 1 + 1 + 1)
and is determined by the subset {3, 4, 5, 6} of {1, 2, 3, 4, 5, 6}. In Table 3.1 we have listed
six compositions of 7 along with the corresponding subset of {1, 2, 3, 4, 5, 6} that deter
mines each of them.
Table 3.1
(i) l + l + l + l + l + l + l (i) 0
(ii) 1+2+1+1+1+1 ( ii) {2}
(iii) 1+1+3+1+1 (iii) {3,4}
(iv) 2+ 3+ 2 (iv) { 1 ,3 ,4 ,6 }
(V) 4+ 3 (V) {1,2, 3, 5,6}
(Vi) 7 (Vi) {1,2, 3, 4, 5,6}
The examples we have obtained here indicate a correspondence between the composi
tions of 7 and the subsets of {1, 2, 3, 4, 5, 6}. Consequently, once again we find that there
are 26 compositions of 7. In fact, for each positive integer m, there are 2m_1 compositions
of m.
Before we proceed any further let us reconsider the result of Example 3.12, but this time
we shall do it in light of what we learned in Example 3.10.
Once again we let n, r be positive integers where n > r > 1. Then (n + J) counts the
number of (staircase) paths in the jty-plane from (0, 0) to (n + 1 r, r), where, as in
Example 3.10, each such path has
(n + 1 ) r horizontal moves of the form (jc, y) > (jc + 1 , y), and
r vertical moves of the form (x, y) > (x, y + 1 ).
The last edge in each of these (staircase) paths terminates at the point (n -1-1 r, r) and
starts at either (i) the point (n r, r) or (ii) the point (n + 1 r, r 1 ).
In case (i) we have the last edge horizontal, namely, (n r, r) > (n + 1 r, r)\ the
number of (staircase) paths from (0, 0) to (n r, r) is ((n + r) = (). For case (ii) the
last edge is vertical, namely, (n + 1 r, r 1 ) > (n + 1 r, r); the number of (staircase)
paths from (0, 0) to (n + 1 r, r 1 ) is ((n + 1 ~rrl \ (r 1}) = (r l i). Since these two cases
exhaust all possibilities and have nothing in common, it follows that
We now investigate how the identity of Example 3.12 can help us solve Example 1.35,
E X A M P L E 3.13
where we sought the number of nonnegative integer solutions of the inequality x\ + *2 +
+ xe < 10.
For each integer k, 0 < k < 9, the number of solutions to x\ + X2 + + xe = k is
(6+1 ~ ^ = (5 *). So the number of nonnegative integer solutions to x\ + X2 + + xe <
10 is
3.1 Sets and Subsets 133
In Fig. 3.3 we find a part of the useful and interesting array of numbers called Pascal's
E X A M P L E 3.14
triangle
(n = 0)
(n = 1)
(n = 2)
(n = 3)
(n = 4)
5N
(n = 5)
A
Figure 3.3
Note that in this partial listing the two triangles shown satisfy the condition that the
binomial coefficient at the bottom of the inverted triangle is the sum of the other two terms
in the triangle. This result follows from the identity in Example 3.12.
When we replace each of the binomial coefficients by its numerical value, the Pascal
triangle appears as shown in Fig. 3.4.
(n = 0) 1
( n = 1) 1 1
(n = 2) 1 2 1
(n = 3)
(n = 4)
(n = 5)
Figure 3.4
There are certain sets of numbers that appear frequently throughout the text. Conse
quently, we close this section by assigning them the following designations.
c) proper subsets of A
EXERCISES 3.1
d) nonempty proper subsets of A
1. Which of the following sets are equal? e) subsets of A containing three elements
a) { 1, 2, 3} b) {3,2, 1,3} f) subsets of A containing 1, 2
c) {3, 1 , 2 , 3 } d) {1,2, 2, 3} g) subsets of A containing five elements, including 1, 2
2. Let A = {1, {1}, {2}}. Which of the following statements h) subsets of A with an even number of elements
are true? i) subsets of A with an odd number of elements
a) 1 G A b) {1} G A
9. a) If a set A has 63 proper subsets, what is |A |?
c) { 1 } C A d) {{1}} c A
b ) If a set B has 64 subsets of odd cardinality, what is | B\1
e) {2} g A f ) {2} c A c) Generalize the result of part (b)
g) {{2}} c A h) {{2}} c A
10. Which of the following sets are nonempty?
3. For A = {1, 2, {2}}, which of the eight statements in Exer
cise 2 are true? a) {x\x G N, 2x + 7 = 3}
a) 0 g 0 b) 0 c 0 c)0 c0 c) {x\x G Q, x 2 + 4 = 6}
a) {1 + (l)n| ft g N} f) {x\x G C, x 2 + 3x + 3 = 0}
b) {n + ( \ / n ) \ n e { \ , 2 , 3, 5, 7} } 11. When she is about to leave a restaurant counter, Mrs. Al-
c) {n 3 + n2\ n e {0, 1, 2, 3, 4}} banese sees that she has one penny, one nickel, one dime, one
quarter, and one half-dollar. In how many ways can she leave
6. Consider the following six subsets of Z.
some (at least one) of her coins for a tip if (a) there are no re
A = {2m + 1| m G Z} B = {In + 3| n G Z} strictions? (b) she wants to have some change left? (c) she wants
C = {2p - 3| p G Z} D = {3r + 1| r G Z} to leave at least 10 cents?
E = {3s + 2| j G Z} F = {3i 2|i G Z} 12. Let A = {1, 2, 3, 4, 5, 7, 8, 10, 11, 14, 17, 18}.
Which of the following statements are true and which are false? a) How many subsets of A contain six elements?
a) A = B b) A = C c) B = C b ) How many six-element subsets of A contain four even
d) D = E e) D = F f) F = F integers and two odd integers?
7. Let A, B be sets from a universe ll. (a) Write a quan c) How many subsets of A contain only odd integers?
tified statement to express the proper subset relation A c B.
13. Let S = {1, 2, 3, . . . , 29, 30}. How many subsets A of S
(b) Negate the result in part (a) to determine when A (p_B.
satisfy (a) |A| = 5? (b) |A| = 5 and the smallest element in A
8. For A = {1, 2, 3, 4, 5, 6, 7}, determine the number of is 5? (c) | A | = 5 and the smallest element in A is less than 5?
a) subsets of A 14. a) How many subsets of {1, 2, 3, . . . , 11} contain at least
b) nonempty subsets of A one even integer?
3.1 Sets and Subsets 135
b) How many subsets of {1, 2, 3, , 12} contain at least 20. a) Among the strictly increasing sequences of integers that
one even integer? start with 1 and end with 7 are:
c) Generalize the results of parts (a) and (b). i) 1,7 ii) 1, 3, 4, 7 iii) 1, 2, 4, 5, 6, 7
15. Give an example of three sets W, X, Y such that W e X How many such strictly increasing sequences of integers
and X Y but W & Y. start with 1 and end with 7?
16. Write the next three rows for the Pascal triangle shown in b) How many strictly increasing sequences of integers start
Fig. 3.4 with 3 and end with 9?
17. Complete the proof of Theorem 3.1. c) How many strictly increasing sequences of integers start
with 1 and end with 37? How many start with 62 and end
18. For sets A, B, C c ll, prove or disprove (with a counter
with 98?
example), the following: If A c B, B C, then A ^ C.
d) Generalize the results in parts (a) through (c).
19. In part (i) of Fig. 3.5 we have the first six rows of Pascals
triangle, where a hexagon centered at 4 appears in the last three 21. One quarter of the five-element subsets of {1, 2, 3, . . . , n]
rows. If we consider the six numbers (around 4) at the vertices of contain the element 7. Determine n (> 5).
this hexagon, we find that the two alternating triples namely, 22. For a given universe U, let A c where A is finite
3,1, 10 and 1, 5, 6 satisfy 3 * 1 * 10 = 30 = 1*5*6. Part (ii) with |2P(A)| = n. If B c lt, how many subsets does B have,
of the figure contains rows 4 through 7 of Pascals triangle. Here if (a) B = A U {x}, where x e\i A1 (b) B = A U {x, y},
we find a hexagon centered at 10, and the alternating triples where jc, y eU - A? (c) B = A U { jci, jc2......... xk}, where
at the vertices in this case, 4, 10, 15 and 6, 20, 5 satisfy jti, x2, . . . , x k e ll A?
4 10 15 = 600 = 6 - 2 0 - 5 . 23. Determine which row of Pascals triangle contains three
a) Conjecture the general result suggested by these two consecutive entries that are in the ratio 1 : 2 : 3.
examples. 24. Use the recursive technique of Example 3.9 to develop a
b) Verify the conjecture in part (a). Gray code for the 16 binary strings of length 4. Then list each
of the 16 subsets of the ordered set {w, x, y, z] next to its cor
responding binary string.
25. Suppose that A contains the elements v, w, x, y, z and no
others. If a given Gray code for the 32 subsets of A encodes the
ordered set {u, w] as 01100 and the ordered set {x, y} as 10001,
write A as the corresponding ordered set.
26. For positive integers n, r show that
of all positive integers is not a positive integer or Z+ ^ Z+. a) Write a computer program (or develop an algorithm) to
But the set of all abstractions is an abstraction. generate a random six-element subset of A.
Now in order to develop the paradox let S be the set of b) For B = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37},
all sets A that are not members of themselves that is, S = write a computer program (or develop an algorithm) to gen
{A\A is a set A A A}. erate a random six-element subset of A and then determine
a) Show that if S e S, then S S. whether it is a subset of B.
b) Show that if S S, then S e S. 29. Let A = {1, 2, 3, . . . , 7}. Write a computer program (or
The results in parts (a) and (b) show us that we must avoid develop an algorithm) that lists all the subsets B of A, where
trying to define sets like 5. To do so we must restrict the types 1*1=4.
of elements that can be members of a set. (More about this is 30. Write a computer program (or develop an algorithm) that
mentioned in the Summary and Historical Review in Section lists all the subsets of {1, 2, 3, . . . , n), where 1 < n < 10. (The
3.8.) value of n should be supplied during program execution.)
28. Let A = {1, 2, 3, . . . , 39, 40}.
3.2
Set Operations and the Laws of Set Theory
After learning how to count, a student usually faces methods for combining counting num
bers. First this is accomplished through addition. Usually the students world of arithmetic
revolves about the set Z + (or a subset of Z + that can be spoken and written about, as well
as punched out on a hand-held calculator) wherein the addition of two elements from Z+
results in a third element of Z+, called the sum. Hence the student can concentrate on addi
tion without having to enlarge his or her arithmetic world beyond Z + . This is also true for
the operation of multiplication.
The addition and multiplication of positive integers are said to be closed binary op
erations on Z+. For example, when we compute a + b, for a, b e Z+, there are two
operands, namely, a and b. Hence the operation is called binary. And since a + b e Z+
when a, b e Z +, we say that the binary operation of addition (on Z +) is closed. The binary
operation of (nonzero) division, however, is not closed for Z + we find, for example, that
1/2 (= 1 2) ^ Z+ , even though 1, 2 e Z + . Yet this operation is closed when we consider
the set Q + instead of the set Z +.
We now introduce the following binary operations for sets.
WithU = {1, 2, 3, . . . , 9, 10}, A = {1, 2, 3,4, 5}, B = {3, 4, 5, 6, 7},andC = {7, 8, 9},
E X A M P L E 3.15
we have:
a) A n B = {3, 4, 5} b) A U 5 = {1, 2, 3, 4, 5, 6, 7}
3.2 Set Operations and the Laws of Set Theory 137
c) B n c = {7} d) A n C = 0
e) A A B = {1,2, 6, 7} f) A U C = {1, 2, 3, 4, 5, 7, 8, 9}
g) A A C = { 1 , 2 , 3 , 4 , 5 , 7 , 8, 9}
In Example 3.15 we see that A f l i C A C A U f i . This result is not special for just this
example but is true in general. The result follows because
x E An B (x 6 A A X G fi) XE A
(where the first logical implication is a result of the Rule of Disjunctive Amplification
Rule 8 of Table 2.19).
Motivated by parts (d), (f), and (g) of Example 3.15, we introduce the following general
ideas.
Definition 3.6 Let S, T c U. The sets S and T are called disjoint, or mutually disjoint, when 5 Pi T = 0.
In proving the first part of Theorem 3.3 we showed that if S, T are any sets, then
S A T c ^ U T . The disjointness of S and T was needed only for the opposite inclusion.
After mastering the skill of addition, one usually comes next to subtraction. Here the set
N causes some difficulty. For example, N contains 2 and 5 but 2 5 = 3, and 3 ^ N.
Therefore the binary operation of subtraction is not closed for N, although it is closed for
138 Chapter 3 Set Theory
the superset Z of N. So for Z we can introduce the unary, or monary, operation of negation
where we take the minus or negative of a number such as 3, getting 3.
We now introduce a comparable unary operation for sets.
Definition 3.7 For a set A U, the complement of A, denoted U A, or A, is given by {x|x e\l A x A}.
For the sets of Example 3.15, A = {6, 7, 8, 9, 10}, 5 = {1, 2, 8, 9, 10}, and C = {1, 2, 3,
E X A M P L E 3.16
4, 5, 6, 10}.
For every universe ii and every set A c U, we find that A c U. Therefore 2P(U) is
closed under the unary operation defined by the complement.
The following concept is related to the concept of the complement.
This next theorem now shows us that the four results in Example 3.18 are related in
general. In order to prove this theorem we again make use of Definition 3.2, as we discover
the interplay between the notions of subset, union, intersection, and complement.
T H E O R E M 3.4 For any universe U and any sets A, B c U, the following statements are equivalent:
a) A c b) A U B = B
c) A D B = A d)CA
Proof:In order to prove the theorem, we prove that (a) => (b), (b) => (c), (c) => (d), and
(d) => (a). (The reason this suffices to prove this theorem is based on the idea presented in
Exercise 13 at the end of Section 2.2.)
3.2 Set Operations and the Laws of Set Theory 139
i) (a) => (b) If A, B are any sets, then 5 C A U 5 ( a s mentioned after Example 3.15).
For the opposite inclusion, if x e A U B, then x e A or x e B, but since A c B, in
either case we have x e B . So A U B ^ B and, since we now have both inclusions,
it follows (once again from Definition 3.2) that A U B = B.
ii) (b) => (c) Given sets A, B, we always have A D A D B (as mentioned after Ex
ample 3.15). For the opposite inclusion, let y e A. With A U B = B , y e A ^ y e
A U B => y g B (since A U 5 = B) y e A Pi B, so A c. A f) B and we conclude
that A = A D 5 .
iii) (c) => (d) We know that z B ^ z B. Now if z A D 5 , then z g 5 , since
A D 5 C 5 . The contradiction namely, z B A z G 5 tells us that z ^ A D B.
Therefore, z A because A D B = A. But z A => z A, so 5 c A.
iy) (d) => (a) Last, u > e A = > u ; ^ A . I f u ; ^ B, then w e 5 . With B c A it then follows
that w e A. This time we get the contradiction w A A w e A, and this tells us that
w e B. Hence A c f i .
With a bit of theorem proving under our belts, we now introduce some of the major laws
that govern set theory. These bear a marked resemblance to the laws of logic given in Section
2.2. In many instances these set theoretic laws are similar to the arithmetic properties of the
real numbers, where U plays the role of and D the role of X. However, there are
several differences.
8) A U A = % Inverse Laws
9) A U % * % Domination Laws
AH0 = 0
10) A U (4 n ) A Absorption Laws
A n (A U B) A
140 Chapter 3 Set Theory
All these laws can be established by element arguments, as in the first part of the proof
of Theorem 3.3. We demonstrate this by establishing the first of DeMorgans Laws and the
second Distributive Law, that of intersection over union.
Proof: Let jc g U. Then
x e A U B ^ x AUB
=> x ^ A and x B
=> jc G A and x e B
x GA n B,
The reader undoubtedly expects the pairing of the laws in items 2 through 10 to have
some importance. As with the laws of logic, these pairs of statements are called duals. One
statement can be obtained from the other by replacing all occurrences of U by D and vice
versa, and all occurrences of U by 0 and vice versa.
This leads us to the following formal idea.
Definition 3.9 Let s be a (general) statement dealing with the equality of two set expressions. Each such
expression may involve one or more occurrences of sets (such as A, A, B, B , etc.), one or
more occurrences of 0 and U, and only the set operation symbols D and U. The dual of 5,
denoted sd\ is obtained from s by replacing (1 ) each occurrence of 0 and \l (in s) by \l and
0, respectively; and (2) each occurrence of D and U (in s) by U and D, respectively.
3.2 Set Operations and the Laws of Set Theory 141
As in Section 2.2, we shall state and use the following theorem. We shall prove a more
general result in Chapter 15.
T H E O R E M 3.5 The Principle o f Duality. Let s denote a theorem dealing with the equality of two set
expressions (involving only the set operations D and U as described in Definition 3.9). Then
sd, the dual of s, is also a theorem.
Using this principle cuts our work down considerably. For each pair of laws in items
2 through 10, one need prove only one of the statements and then invoke this principle to
obtain the other statement in the pair.
We must be careful about applying Theorem 3.5. This result cannot be applied to par
ticular situations but only to results (theorems) about sets in general. For example, let
us consider the particular situation where U = {1, 2, 3, 4, 5} and A = {1, 2, 3, 4}, B =
{1, 2, 3, 5}, C = {1, 2}, and D = {1,3}. Under these circumstances
AD B = {1,2, 3} = C U D .
Inasmuch as Definition 3.9 and Theorem 3.5 do not mention anything about subsets, can
E X A M P L E 3.19
we find a dual for the statement A C f i (where A, B c U)?
Here we get an opportunity to use some of the results in Theorem 3.4. We can deal with
the statement A c B by using the equivalent statement A U B = B.
The dual of A U B = B gives us A D B = B. But A D B = B B c A. Consequently,
the dual of the statement A c B is the statement 5 C A . (We could also have obtained this
result by using A C f i ^ A D B = A.)
When we consider the relations that may exist among the sets that are involved in a
set-equality or subset statement, we can investigate the situation graphically.
Named in honor of the English logician John Venn (1834-1923), a Venn diagram is
constructed as follows: \l is depicted as the interior of a rectangle, while subsets of U
are represented by the interiors of circles and other closed curves. Figure 3.6 shows four
Venn diagrams. The (blue) shaded region in Fig. 3.6(a) represents the set A, whereas A is
represented by the unshaded area. The shaded region in Fig. 3.6(b) comprises A U B; the
set A n B is represented by the shaded region in Fig. 3.6(c). The Venn diagram for A B
is given in part (d) of this figure.
In Fig. 3.7 Venn diagrams are used to establish the second of DeMorgans Laws. Figure
3.7(a) has everything except A D B shaded, so the shaded portion represents A (1 B. We
now develop a Venn diagram to depict A U B. In Fig. 3.7(b), A is the shaded region (outside
the circle representing set A). Likewise, B is the shaded region shown in Fig. 3.7(c). When
the results from Fig. 3.7(b) and Fig. 3.7(c) are put together, we get the Venn diagram for
their union in Fig. 3.7(d). Since the shaded region in part (d) is the same as that in part (a),
it follows that A (1 B = A U B.
142 Chapter 3 Set Theory
Figure 3 6
Figure 3.7
We further illustrate the use of these diagrams by showing that for any sets A, B, C c . 0ll,
(A U B) n C = (A D B ) U C .
Instead of shading regions, another approach that also uses Venn diagrams numbers the
regions as shown in Fig. 3.8 where, for example, region 3 is A D B D C and region 7 is
AD B D C . Each region is a set of the form S\ D S2 H S3, where S\ is replaced by A or
A, >2 by B or 5 , and S3 by C or C. Consequently, by the rule of product, there are eight
possible regions.
Consulting Fig. 3.8, we see that A U B comprises regions 2, 3, 5 ,6, 7, 8 and that regions
4, 6, 7, 8 make up set C. Therefore (A U 5 ) D C comprises the regions common to A U #
3.2 Set Operations and the Laws of Set Theory 143
One more technique for establishing set equalities is the membership table. (This method
is akin to using the truth table introduced in Section 2.1.)
We observe that for sets A, B c % an element x eU satisfies exactly one of the fol
lowing four situations:
a) x A, x B b ) x A, x e B.
c) x e A, x B d) x e A, x e B.
When jc is an element of a given set, we write a 1 in the column representing that set in
the membership table; when jc is not in the set, we enter a 0. Table 3.2 gives the membership
tables for A D B, A U B, A in this notation. Here, for example, the third row in part (a) of
the table tells us that when an element jc e \l is in set A but not in B , then it is not in A D B
but it is in A U B.
Table 3.2
A B ADB AUB A A
0 0 0 0 0 1
0 1 0 1 1 0
1 0 0 1
1 1 1 1
(a) (b)
These binary operations on 0 and 1 are the same as in ordinary arithmetic (relative to
and + ) except that 1 U 1 = 1 .
Using membership tables, we can establish the equality of two sets by comparing their
respective columns in the table. Table 3.3 demonstrates this for the Distributive Law of
union over intersection. We see here how each of the eight rows corresponds with exactly
one of the eight regions in the Venn diagram of Fig. 3.8. For example, row 1 corresponds
with region 1: A D B D C; and row 6 corresponds with region 7: A D B D C.
144 Chapter 3 Set Theory
Table 3.3
Before we continue let us make two points. (1) A Venn diagram is simply a graphical
representation of a membership table. (2) The use of Venn diagrams and/or membership
tables may be appealing, especially to the reader who presently does not appreciate writing
proofs. However, neither one of these techniques specifies the logic and reasoning displayed
in the element arguments we presented, for instance, to prove that for any A, B, C c U,
A U B = A D B, and A D (B U C) = (A D B) U (A D C).
We feel that Venn diagrams may help us to understand certain mathematical situations
but when the number of sets involved exceeds three, the diagram could be difficult to
draw.
In summary, let us agree that the element argument (especially with its detailed explana
tions) is more rigorous than these two techniques and is the preferred method for proving
results in set theory.
Now that we have the laws of set theory, what can we do with them? The following
examples will demonstrate how the laws are used to simplify a complicated set expression
or to derive new set equalities. (When more than one law is used in a given step, we list the
principal law as the reason.)
H (p V i)A r ]v ^ ]
3.2 Set Operations and the Laws of Set Theory 145
to the statement
q Ar
in Example 2.17.
A - B = AO B Reasons
= AUB DeMorgans Law
= A UB Law of Double Complement
A A B = (A U B) n (A n B) Reasons
= (A U B) U (A n B) DeMorgans Law
= (A U B) U (A H B) Law of Double Complement
= (A n B) U (A U B) Commutative Law of U
= (A n B) u (A n B) DeMorgans Law
= [(A f l B ) U ] n [(A n B) U B] Distributive Law of U over D
= [(A U A) n (B U A)] n [(A U 5 ) n ( 5 U B)] Distributive Law of U over D
= [it n (B u )] n [(A u B) n U] Inverse Law
= (B U A) n (A U B) Identity Law
= (A U B) n (A U B) Commutative Law of U
= ( u B) n ( n B) DeMorgans Law
=AAB
= (A U B) n ( U B) Commutative Law of D
= (A U 5)n(A ns) DeMorgans Law
=AAB
In closing this section we extend the set operations of U and D beyond three sets.
Definition 3.10 Let I be a nonempty set and U a universe. For each i e I let A t c U. Then I is called an
index set (or set of indices), and each i e I is called an index.
Under these conditions,
When dealing with generalized unions and intersections, membership tables and Venn
diagrams are unfortunately next to useless, but the rigorous element approach, as demon
strated in the first part of the proof of Theorem 3.3, is still available.
T H E O R E M 3.6 GeneralizedDeMorgans Laws. Let I be an index set where for each i G /, A/ c U. Then
a) U A, = f i Ai b) f i A, = U A,
ie l ie l ie l ie l
Proof:We shall prove Theorem 3.6(a) and leave the proof of part (b) for the reader. For each
x eU, x e Uiei Ai <=> x U^/A* ^ ^ A*, for all i g I x g A/, for all i g I <=$
X Pl/g/Aj.
a) A (1 B b) A U B i) E C. C c. A ii) Ac . C c. E
c) d) A A B iii) B c. D iv) D c B
e) A - B f) B - A v) D c A vi) D c A
3.2 Set Operations and the Laws of Set Theory 147
i) C Pi E ii) B U D iii) Ai l B 14. Use membership tables to establish each of the following:
iv) B H D v) A vi) A Pi E a) A(1 B = A U F b) A UA = A
11. Write the dual statement for each of the following set- where m is a fixed positive integer.
theoretic results. 19. Let ll = R and let I = Z+. For each n e Z + let An =
a) = (A n B) U (A n B) U (A fl B) U (A n B) [2n, 3n ]. Determine each of the following:
b) A = A n (A U B) A3 b) A4
c) A U B = (A n B) U (A n B) U (A Pi B) a 3 a 4 d) A3 A A4
7 7
d) A = (A U B) n (A U 0)
12. Let A, B c U. Use the equivalence A c B <=> A i l B = A
U1 A
n=
f> nn=l a
oo
to show that the dual statement of A c B is the statement B c A .
13. Prove or disprove each of the following for sets A , B c U.
UZ+ A
ne
h) n=l
fl A
a) ^ ( A U B ) = ^ ( A ) U ^ ( 5 ) 20. Provide the details for the proof of Theorem 3.6(b).
148 Chapter 3 Set Theory
3.3
Counting and Venn Diagram s
With all of the theoretical work and theorem proving we did in the last section, now is a
good time to examine some additional counting problems.
For sets A , B from a finite universe U, the following Venn diagrams will help us obtain
counting formulas for \A\ and |A U B\ in terms of |U|, |A|, \B\, and |A D B |.
As Fig. 3.9 demonstrates, A U A = TtandA D A = 0, so by the rule of sum, \A\ + \A\ =
|U| or |A| = |U| |A |. The sets A, B, in Fig. 3.10, have empty intersection, so here the
rule of sum leads u s t o | A U 2 ? | = |A| + |5 | and necessitates that A, B be finite but does
not require any condition on the cardinality of IL
Turning to the case where A, B are not disjoint, we motivate the formula for |A U B\
with the following example.
In a class of 50 college freshmen, 30 are studying C++, 25 are studying Java, and 10 are
E X A M P L E 3.25
studying both languages. How many freshmen are studying either computer language?
We let U be the class of 50 freshmen, A the subset of those students studying C++, and
B the subset of those studying Java. To answer the question, we need |A U B\. In Fig. 3.11
the numbers in the regions are obtained from the given information: |A| = 3 0 , \B\ =25,
|A D B\ = 10. Consequently, |A U B\ = 45 ^ 55 = 30 + 25 = |A| + \B\, because |A| +
\B\ counts the students in A D B twice. To remedy this overcount, we subtract |A D B\
from |A| + \B\ to obtain the correct formula: |A U B\ = \A\ + \B\ |A D B\.
An AND gate in an ASIC (Application Specific Integrated Circuit) has two inputs: Ii, I2,
E X A M P L E 3.26
and one output: O. (See Fig. 3.12). Such an AND gate can have any or all of the following
defects:
Di: The input l\ is stuck at 0.
D 2: The input I2 is stuck at 0.
D 3: The output O is stuck at 1
For a sample of 100 such gates we let A, B , and C be the subsets (of these 100 gates) hav
ing defects Di, D2, and D3, respectively. With |A| = 2 3 , \B\ = 2 6 , \C\ = 3 0 , |A D B\ =
7, |A D C\ = 8, \B D C\ = 10, and |A D B D C| = 3, how many gates in the sample have
at least one of the defects Di, D2, D3?
Working backward from \A f) B D C\ = 3 to |A| = 2 3 , we label the regions as shown in
Fig. 3.13 and find th a t\ AU B U C | = |A| + |fl| + \C\ - \A n B\ - \A n C\ - \B n C\ +
|A D B D C\ = 23 -1- 26 -1- 30 7 8 10 -1- 3 = 57. Thus the sample contains 57 AND
gates with at least one of the defects and 100 57 = 43 AND gates with no defect.
We close this section with a problem that uses this last result.
A student visits an arcade each day after school and plays one game of either Laser Man,
E X A M P L E 3.27
Millipede, or Space Conquerors. In how many ways can he play one game each day so that
he plays each of the three types at least once during a given school week?
Here there is a slight twist. The set U consists of all arrangements of size 5 taken from
the set of three games, with repetitions allowed. The set A represents the subset of all
sequences of five games played during the week without playing Laser Man. The sets B
and C are defined similarly, leaving out Millipede and Space Conquerors, respectively.
The enumeration techniques of Chapter 1 give |U| = 35, \A\ = \B\ = \C\ = 25, \A D B\ =
150 Chapter 3 Set Theory
This example can be expressed in an equivalent distribution form, since we are seeking
the number of ways to distribute five distinct objects (Monday, Tuesday,. . . , Friday) among
three distinct containers (the computer games) with no container left empty. More will be
said about this in Chapter 5.
3.4
A First W ord on Probability
When one performs an experiment such as tossing a single fair coin, rolling a single fair
die, or selecting two students at random from a class of 20 to work on a project, a set of all
possible outcomes for each situation is called a sample space. Consequently, {H, T} serves
as a sample space for the first experiment mentioned and {1, 2, 3, 4, 5, 6} is a sample space
for the roll of a single fair die. Moreover, {{, aj}\ \ < i < 20, 1 < j < 20, i ^ j } can be
used for the last experiment, with ai denoting the zth student, for each 1 < i < 20.
In dealing with the sample space if = {1, 2, 3, 4, 5, 6} for the roll of a single fair die, we
feel that each of the six possible outcomes has the same, or equal, likelihood of occurrence.
Using this assumption of equal likelihood, we shall start our study of probability theory with
a definition for probability that was first given by the French mathematician Pierre-Simon
de Laplace (1749-1827) in his Analytic Theory of Probability.
3.4 A First Word on Probability 151
Under the assumption o f equal likelihood, let 3* be the sample space for an experiment
%. Each subset A of SP, including the empty subset, is called an event. Each elem ent of
5f determines an outcome, so if |Sf | n and a SP* A c i f , then
Pr({a}) probability that {a} (on a) occurs ^ and
P r(A ) probability that A occurs
[iVore; We often write P r(a ) for Pr({a}).]
When Daphne tosses a fair coin, what is the probability she gets a head? Here the sample
E X A M P L E 3.28
space if = {H, T} with A = {H} and we find that
]A| 1
Pr(A) =
2
If Dillon rolls a fair die, what is the probability he gets (a) a 5 or a 6, (b) an even number?
E X A M P L E 3.29
For either part the sample space if = {1, 2, 3, 4, 5, 6}. In part (a) we have event A = {5,6}
and Pr{A) = j^j = | For part (b) we consider event B = {2, 4, 6} and find that
Pr(B)
r r \ D) = ^1
\y>\ = ^6 = 12-
Furthermore we also notice here that
i) Pr{i) = | = 1 after all, the occurrence of the event if is a certainty; and
There are 20 students enrolled in Mrs. Arnolds fourth-grade class. Hence, if she wants to
E X A M P L E 3.30
select two of her students, at random, to take care of the class rabbit, she may make her
selection in (22) = 190 ways, so |Sf | = 190.
Now suppose that Kyle and Kody are two of the 20 students in the class and we let A
be the event that Kyle is one of the students selected and B be the event that the selection
includes Kody. Consequently, upon choosing the students, at random, the probability that
Mrs. Arnold selects
a) both Kyle and Kody is Pr ( A Pi B) = Q ) /^ 0) = 1/190;
b) neither Kyle nor Kody is Pr ( A Pi B) = ( 28) / ( 22) = 153/190;
c) Kyle but not Kody is Pr ( A Pi B) = (}) (118) / ( 22) = 18/190 = 9/95.
Consider drawing five cards from a standard deck of 52 cards. This can be done in (552) =
E X A M P L E 3.31
2,598,960 ways. Now suppose that Tanya draws five cards, at random, from a standard
deck. What is the probability she gets (a) three aces and two jacks; (b) three aces and a pair;
(c) a full house (that is, three of one kind and a pair)?
152 Chapter 3 Set Theory
To study some additional sample spaces we need to introduce the idea of the ordered
pair. This arises in the following structure.
Definition 3.11 For sets A, B, the Cartesian product, or cross product, of A and B is denoted by A X B
and equals {{a, b)\a e A, b e B}.
We call the elements of A X B ordered pairs. For (a, b), (c, d) e A X B, we have
(a, b) = (c, d) if and only if a = c and b = d J
If A = {1,2, 3} and B = {x, y}, then A X B = {(1, x), (1, y), (2, x), (2, y), (3, x),
E X A M P L E 3.32
(3, y)} while B X A = {(*, 1), (*, 2), (*, 3), (y, 1), (y, 2), (y, 3)}. Here (1, x) A X B
but (1, x) B X A, although (x, 1) e B X A. So A X B ^ B X A, but \A X B\ = 6 =
2>3 = \A\\B\ = \B\\A\ = \ B X A \ .
Now let us see how the Cartesian product can arise in a probability problem.
Suppose Concetta rolls two fair dice. This experiment can be decomposed as follows. Let %1
E X A M P L E 3.33
be the experiment where the first die is rolled with sample space = {1, 2, 3, 4, 5, 6}.
Likewise we let %2 account for the second die rolled also with sample space ^2 =
{1, 2, 3, 4, 5, 6}. (To keep the two dice distinct we can imagine the first die rolled with the
left hand and the second with the right. Or we can have the first die colored red and the
t More about ordered pairs and the Cartesian product is given in Section 5.1.
3.4 A First Word on Probability 153
second green in order to distinguish them.) Consequently, when Concetta rolls these dice
the sample space
Sf = Sfi X SP2 = {(1 , 1 ), (1 , 2),(1, 3),(1, 4), (1, 5),(1,6), (2, 1),(2,2),(2,3),(2, 4),
(2, 5), (2, 6),(3, 1),(3, 2), (3, 3),(3,4), (3, 5),(3,6),(4,1),(4, 2),
(4, 3), (4, 4),(4, 5),(4, 6), (5, 1),(5,2), (5, 3),(5,4),(5,5),(5, 6),
(6, 1), (6, 2),(6, 3),(6, 4), (6, 5),(6,6)}
= {(x, y)\x, y = 1,2, 3, 4, 5, 6).
Now consider the following events:
A: Concetta rolls a 6 (that is, the top faces of the dice sum to 6);
B : The sum of the dice is at least 7;
C: Concetta rolls an even sum; and
D : The sum of the dice is 6 or less.
a) Here
i) A = {(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)} with Pr(A) = |A|/|SP| = 5/36;
ii) B = {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (2, 6), (3, 5), (4, 4),
(5, 3), (6, 2), (3, 6), (4, 5), (5, 4), (6, 3), (4, 6), (5, 5), (6, 4), (5, 6),
(6, 5), (6, 6)} = {(x, y)|x, y = 1, 2, 3, 4, 5, 6; x + y > 7} with
Pr{B) = \B\/\&>\ = 21/36 = 7/12;
iii) C = {(1, 1), (1, 3), (2, 2), (3, 1), (1, 5), (2, 4), (3, 3), (4, 2), (5, 1),
(2, 6), (3, 5), (4, 4), (5, 3), (6, 2), (4, 6), (5, 5), (6, 4), (6, 6)} with
Pr(C) = |C|/|SP| = 18/36 = 1/2; and
iv) D = {(1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), (1, 4), (2, 3), (3, 2), (4, 1),
(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)} with Pr(D) = \D\/\if\ = 15/36 = 5/12.
b) We notice the following:
i) A U B = {(x, y)|x, y = 1, 2, 3, 4, 5, 6; x + y > 6), so |A U B\ = 26 and
Pr ( A U B) = |A U B|/|P| = 1 = ! + % = P r W + P r ^
ii) C U D = {(1, 1), (1, 2), (2, 1),(1, 3), (2, 2), (3, 1), (1, 4), (2, 3), (3,2)
(4, 1), (1, 5), (2, 4), (3, 3), (4,2), (5, 1), (2, 6), (3, 5), (4, 4), (5, 3),
(6, 2), (4, 6), (5, 5), (6, 4), (6,6)}so |C U D\ = 24 and Pr(C U D) =
|CUZ>|/|Sf| = 2 4 /3 6 = 2/3.
Here, however,
Pr(C U D ) = 24/36 f 33/36 = 18/36 + 15/36 = Pr(C) + Pr(D), although
Pr ( C U D ) = 24/36 = 18/36 + 15/36 - 9/36 = Pr(C) + Pr(D) - P( C Pi D).
The result here and that in part (i) [of (b)] mirror the ideas we saw earlier in the formulas
following Example 3.25.
iii) Finally, Pr(B) = Pr ( D) = 15/36 = 1 - 21/36 = 1 - Pr(B).
Let us consider a second example where the Cartesian product is used. This time well
also learn about another important structure.
An experiment % is conducted as follows: A single die is rolled and its outcome noted, and
E X A M P L E 3.34
then a coin is flipped and its outcome noted. Determine a sample space if for %.
154 Chapter 3 Set Theory
Let %\ denote the first part of experiment and let if\ = {1, 2, 3, 4, 5, 6} be a sample
space for Likewise let if 2 = {H, T} be a sample space for %2 , the second part of the
experiment. Then if = if 1 X if 2 is a sample space for %.
This sample space can be represented pictorially with a tree diagram that exhibits all
the possible outcomes of experiment %. In Fig. 3.14 we have such a tree diagram, which
proceeds from left to right. From the left-most endpoint, six branches originate for the six
outcomes of the first stage of the experiment %. From each point, numbered 1, 2, . . . , 6,
two branches indicate the subsequent outcomes for tossing the coin. The 12 ordered pairs
at the right endpoints constitute the sample space if.
(1H)
(11 T)
(2, H)
(2, T)
(3, H)
(3, T)
(4, H)
(4, T)
(5, H)
(5.7)
(6, H)
(6, T)
Before we continue let us look back at Examples 3.33 and 3.34. We may not realize
it, but we have been making a certain assumption. In Example 3.33 we assumed that the
outcome for the first die had no influence on the outcome for the second die. Likewise, in
Example 3.34 we assumed that the outcome for the die had no bearing on the outcome for
the coin. This concept of independence will be examined more closely in Section 3.6.
In our next example we extend the idea of the Cartesian (or, cross) product to more than
two sets.
If Charles tosses a fair coin four times, what is the probability that he gets two heads and
E X A M P L E 3.35
two tails?
Here the sample space for the first toss is if 1 = {H, T}. Likewise, for the second, third, and
fourth tosses, we have if 2 = i f ^ = i f ^ = {H, T}. So, for this experiment of tossing a fair coin
3.4 A First Word on Probability 155
The next example also requires some of the formulas developed in Chapter 1 for ar
rangements.
The acronym WYSIWYG (for, What you see is what you get!) is used to describe a user-
E X A M P L E 3.36
interface. This user-interface presents material on a VDT (Video-display terminal) in pre
cisely the same format the material appears on hard copy.
There are 7!/(2! 2!) = 1260 ways in which the letters in the acronym WYSIWYG can
be arranged. Of these, 120(= 5!) arrangements have both consecutive Ws and consecutive
Ys. Consequently, if the letters for this acronym are arranged in a random manner, then we
find the probability that the arrangement has both consecutive W s and consecutive Ys is
120/1260 = 0.0952.
The probability that a random arrangement of these seven letters starts and ends with the
letter W is [(5!/2!)]/[(7!/(2! 2!))] = 60/1260 = 0.0476.
In a survey of 120 passengers, an airline found that 48 enjoyed wine with their meals,
E X A M P L E 3.37
78 enjoyed mixed drinks, and 66 enjoyed iced tea. In addition, 36 enjoyed any given pair
of these beverages and 24 passengers enjoyed them all. If two passengers are selected at
random from the survey sample of 120, what is the probability that
a) (Event A) they both want only iced tea with their meals?
b) (Event B) they both enjoy exactly two of the three beverage offerings?
From the information provided, we construct the Venn diagram shown in Fig. 3.15. The
sample space if consists of the pairs of passengers we can select from the sample of 120, so
\if\ = (*2) = 7140. The Venn diagram indicates that there are 18 passengers who drink only
iced tea, s o \A\ = and Pr(A) = 51/2380. The reader should verify that Pr (B) = 3/34.
156 Chapter 3 Set Theory
(c) the second smallest number drawn is 5 and the fourth largest
EXERCISES 3.4 number drawn is 15?
1. The sample space for an experiment is f = {a, b, c, 11. Darci rolls a fair die three times. What is the probability that
d, e, / , g, h}, where each outcome is equally likely. If event (a) her second and third rolls are both larger than her first roll?
A = {a, b, c } and event B = {a, c, e, g}, determine (a) P r ( A ); (b) the result of her second roll is greater than that of her first
(b) P r(B )\ (c) Pr( A Pi B)\ (d) Pr ( A U B)\ (e) Pr(A); roll and the result of her third roll is greater than the second?
( f ) Pr ( A U B)\ and (g) Pr ( A Pi B). 12. In selecting a new server for its computing center, a col
lege examines 15 different models, paying attention to the
2. Joshua draws two ping-pong balls from a bowl of twenty
following considerations: (A) cartridge tape drive, (B) DVD
ping-pong balls numbered 1 to 20. Provide a sample space for
Burner, and (C) SCSI RAID Array (a type of failure-tolerant
this experiment if
disk-storage device). The numbers of servers with any or all of
a) the first ball drawn is replaced before the second ball is these features are as follows: |A| = |B| = |C| = 6, |A Pi B\ -
drawn. \B D C\ = 1, |A D C| = 2, | A D B n C\ = 0. (a) How many of
b) the first ball drawn is not replaced before the second ball the models have exactly one of the features being considered?
is drawn. (b) How many have none of the features? (c) If a model is se
3. A sample space (for an experiment^) contains 25 equally lected at random, what is the probability that it has exactly two
likely outcomes. If an event A (for this experiment %) is such of these features?
that Pr(A) = 0.24, how many outcomes are there in A? 13. At the Gamma Kappa Phi sorority the 15 sisters who are se
niors line up in a random manner for a graduation picture. Two
4. A sample space if (for an experiment %) contains n equally
of these sisters are Columba and Piret. What is the probability
likely outcomes. If an event A (for this experiment %) contains
that this graduation picture will find (a) Piret at the center po
7 of these outcomes and Pr(A) = 0.14, what is nl
sition in the line? (b) Piret and Columba standing next to each
5. The Tuesday night dance club is made up of six married other? (c) exactly five sisters standing between Columba and
couples and two of these twelve members must be chosen to Piret?
find a dance hall for an upcoming fund raiser, (a) If the two
14. The freshman class of a private engineering college has
members are selected at random, what is the probability they
300 students. It is known that 180 can program in Java, 120 in
are both women? (b) If Joan and Douglas are one of the couples
Visual BASIC1, 30 in C++, 12 in Java and C++, 18 in Visual
in the club, what is the probability at least one of them is among
BASIC and C++, 12 in Java and Visual BASIC, and 6 in all
the two who are chosen?
three languages.
6. If two integers are selected, at random and without replace
a) A student is selected at random. What is the probability
ment, from {1, 2, 3, . . . , 99, 100}, what is the probability the
that she can program in exactly two languages?
integers are consecutive?
b) Two students are selected at random. What is the prob
7. Two integers are selected, at random and without replace ability that they can (i) both program in Java? (ii) both
ment, from {1, 2, 3, . . . , 99, 100}. What is the probability their program only in Java?
sum is even?
15. An integer is selected at random from 3 through 17 inclu
8. If three integers are selected, at random and without re sive. If A is the event that a number divisible by 3 is chosen
placement, from {1, 2, 3, . . . , 99, 100}, what is the probability and B is the event that the number exceeds 10, determine
their sum is even? Pr(A), Pr{B), Pr( A Pi B), and Pr( A U B). How is
9. Jerry tosses a fair coin six times. What is the probability Pr( A U B) related to Pr(A), P r ( B ), and Pr( A Pi B)1
he gets (a) all heads; (b) one head; (c) two heads; (d) an even 16. a) If the letters in the acronym WYSIWYG are arranged in
number of heads; and (e) at least four heads? a random manner, what is the probability the arrangement
10. Twenty-five slips of paper, numbered 1, 2, 3, . . . , 25, are starts and ends with the same letter?
placed in a box. If Amy draws six of these slips, without re b) What is the probability that a randomly generated ar
placement, what is the probability that (a) the second smallest rangement of the letters in WYSIWYG has no pair of con
number drawn is 5? (b) the fourth largest number drawn is 15? secutive identical letters?
3.5
The Axiom s of Probability (Optional)
In Section 3.4 our typical experiment had a sample space where each outcome had the same
likelihood, or probability, of occurrence. If this does not happen, what do we do? Let us
start by considering the following examples.
Suppose Trudy tosses a single coin but it is not fair for instance, suppose this coin is loaded
E X A M P L E 3.38
to come up heads twice as often as it comes up tails. Here the sample space if = {H, T),
as in Example 3.28, but unlike that example where PrCH)1 = Pr(T), in this situation
we have Pr ( H) ^ Pr (T). With H, T as the only outcomes, we have 1 = Pr(if) =
Pr({H} U {T}) = Pr{H) + Pr{T). Since Pr{H) = 2Pr(J), it follows that 1 =
Pr ( H) + Pr ( T) = 2Pr(J) + Pr ( T), so Pr ( T) = 1/3 and Pr ( H) = 2/3.
A warehouse contains 10 motors, three of which are defective (D). The other seven are
E X A M P L E 3.39
in good (G) working condition. A first inspector enters the warehouse and selects (and
inspects) one of the motors. For this experiment %\ , we have the sample space Sfi = {D, G}
where Pr(D ) = 3 / 1 0 and Pr ( G) = 7 / 1 0 . The next day a second inspector enters this same
warehouse and selects (and inspects) a motor. For this second experiment call it %2 we
likewise have if2 = {D, G}. But how do we define Pr (D), Pr (G) in this case? The answer
depends on whether the first motor selected remained in the warehouse, or was removed.
The tree diagrams in Fig. 3.16 deal with the two possibilities. For part (a) of the figure
consider, for example, the case where the first motor selected is defective (D), with prob
ability 3/10, and then the second motor selected is also defective (D). Since motors are
not replaced here, when selecting the second motor the inspector is dealing with nine mo
tors two defective (D) and seven in good (G) working condition. Hence the probability
of selecting a defective motor here is 2/9, not 3/10. So this situation, as shown by the top
branching, has probability | = Q ) / ( 2) = | j = B- The comParable case in part (b) of
the figure has probability ^ = ^5
t Recall that when an event consists of a single outcome say a , we may abbreviate Pr{{a}) as Pr{a).
158 Chapter 3 Set Theory
When selecting two motors, either with or without replacement, the sample space is
if = {DD, DG, GD, GG} where, for instance, DG is used to abbreviate (D, G). Yet in neither
situation do the outcomes have the same likelihood of occurrence. If the selections are done
without replacement [as in Fig. 3.16(a)], then Pr(D D ) = Pr(D G ) = Pr(G D ) =
Pr(GG) = with ^ + + + ^ = l = P(if)- When the first motor is replaced
[as in Fig. 3.16(b)], we have Fr(D D ) = ^ , Pr(D G ) = Fr(G D ) = Pr(G G ) =
49_ _9 , _21_ , _2j_ , _49_ _ i _ p r (CP\
100 Wlin 100 + 100 + 100 + 100 1 r r w )
From this point on well deal exclusively with the case where the two selections are
made without replacement. Consider the following events:
A: One (that is exactly one) motor is defective: {DG, GD};
B : At least one motor is defective: {DG, GD, DD};
C: Both motors are defective: {DD};
E: Both motors are in good working condition: {GG}.
Here
21 21 7 21 21 6 _8_
v ' 90 90 15 F r ( 5 ) _ 90 + 90 + 90 _ 15
6 1 42 7
Pr ( E) =
^ 90 = 15 90 15
Further, (i) B = E and Pr(B) = Pr{E) = ^ = 1 - = 1 - Pr(B); and (ii) A U C = B
with A n C = 0, so Pr ( A U C) = Pr(B) = ^ = 13 + 13 = P r (A) + Fr(C).
What we did in the latter part of Example 3.39 now motivates our next observation. This
observation extends our earlier results in Section 3.4 where each outcome of the sample
space had the same likelihood, or probability, of occurring.
Let if be the sample space for an experiment %. Each element a e if is called an outcome,
or elementary event, and we let Pr{{a}) = Pr(a) denote the probability that this outcome
occurs. Each nonempty subset A of if is still called an event. If event A = [a\ , 2 , an],
where at is an outcome, for all 1 < i < n, then P r ( A ) = X ^=i P r (ai)- (Note: When A = 0
we assign Pr(A) = 0, a result we shall actually establish later in this section.)
However, before we get to our axioms of probability, there is a point that needs to be
clarified. We know that when a fair die is rolled, the sample space if = {1, 2, 3, 4, 5, 6},
where each outcome has the same likelihood, or probability, of occurrence namely, 1 / 6.
However, if this die is rolled six times we should not expect to see one occurrence of each
of the possible outcomes 1, 2, . . . , 6. Should this die be rolled 60 times we want each roll
(after the first) to be unaffected by any previous roll that is, each roll (after the first) is
to be independent of any previous roll. Further, we cannot expect each of the six possible
outcomes to occur ten times. In fact, if the 1 comes up 20 times and this die is then rolled
60 more times we cannot expect to see 1 come up 20 times again. So what can we expect?
If, in rolling this fair die n times, the outcome of 1 occurs m times, then as n grows larger
we expect the relative frequency m / n to approach 1 / 6.
So far this discussion has dealt with a sample space where each outcome has the same
likelihood, or probability, of occurrence. However, the idea is still appropriate if we consider
any sample space for example, the sample space of Example 3.38. Equally important is
how one can use the idea of relative frequency in modeling an experiment. For suppose we
have a coin that we believe to be biased perhaps because it is heavier than other similar
3.5 The Axioms of Probability (Optional) 159
coins that we have weighed. In tossing this coin the sample space is if = {H, T}, but how
can we determine Pr(H), Pr ( T)? We might toss the coin n times, assuming the outcome
of each toss (after the first) is not affected by any previous outcome. If H comes up m
times, then we can assign Pr(H) = m / n and Pr(T) = (n m) / n = 1 (m / n ), where the
accuracy of these assigned probabilities improves as n grows larger.
TH EO R EM 3.7 The Rule of Complement. Let if be the sample space for an experiment %. If A is an event
(that is, A c if), then
Pr(A) = 1 - Pr(A).
We know that if = A U A with A D A = 0. So from axioms (2) and (3) it follows that
Proof:
1 = JV(Sf) = P r ( A U A ) = Pr(A) + Pr(A), and Pr(A) = 1 - Pr(A).
Suppose the letters in the word PROBABILITY are arranged in a random manner. Deter
E X A M P L E 3.40
mine Pr{A) for the event
A : The arrangement begins with one letter and ends in a different letter.
^Although our major concern in this chapter (if not the entire text) deals with finite, when T is infinite
Kolmogorov provided the fourth axiom:
4) if A i , A2, A3, . .. are events (taken from and At n Aj = 0 for all 1 < i < j , then
Pr Pr{An).
160 Chapter 3 Set Theory
Due to an intense preseason workout schedule, Coach Davis has honed her volleyball
E X A M P L E 3.41
team into a major contender. Consequently, the probability her team will win any given
tournament is 0.7, regardless of any previous win or loss. Suppose the team is slated to play
eight tournaments.
a) The probability the women will win all eight tournaments is (0.7)8 = 0.057648. Could
they possibly lose all eight tournaments? Yes, with probability (0.3)8 = 0.000066.
b) What is the probability the team wins exactly five of the eight tournaments? One way
this can happen is if the team wins the first and second tournaments, loses the next three,
and then wins the last three. We represent this by WWLLLWWW. The probability for
this outcome is (0.7)2(0.3)3(0.7)3 = (0.7)5(0.3)3. Another possibility that results in
five tournament wins can be represented by WWLLWWLW. The probability here is
(0.7)2(0.3)2(0.7)2(0.3)(0.7) = (0.7)5(0.3)3. At this point we see that the probability
Coach Daviss team wins five of the eight tournaments is
From the material in Sections 1.2 and 1.3, especially Example 1.22, we know that there
are ^ = (8) ways to arrange five W s and three Ls. Consequently, the probability
the team wins five tournaments is
(0.7)5(0.3)3 = 0.254122.
3.5 The Axioms of Probability (Optional) 161
c) Finally, what is the probability the team wins at least one tournament? Let us not do
here what we did in Example 3.40. If we let A be the given event, then Pr(A) =
(f)(0.7)1 (0.3)81. But Pr(A) is more readily determined as 1 - Pr(A), where
Pr(A) = the probability the team loses all eight tournaments = (0.3)8 = 0.000066
[as in part (a)]. Consequently, Pr(A) = 1 (0.3)8 = 0.999934.
Before we go on we want to examine the structure of the answer at the end of part (b)
of Example 3.41. Each tournament in the example results in either a win (success) or
loss (failure). Further, after the first tournament, the outcome of each later tournament is
independent of the outcome of any previous tournament. Such a two-outcome occurrence
is called a Bernoulli trial. If there are n such trials and each trial has probability p of
success and probability q (= 1 p) of failure, then the probability that there are (exactly)
k successes among these n trials is
p kqn- k. 0 <k<n.
(We shall come upon this idea again in Section 16.5 when we study the application of
Abelian groups in coding theory.)
Returning now to the axioms of probability, we know from axiom (3) that, for A, B c-P,
if A D B = 0 then Pr ( A U B) = Pr(A) + Pr{B). But what can we say if A D B ^ 0?
For the Venn diagram in Fig. 3.17 the interior of the rectangle represents the universe
here the sample space if. The shaded region in the diagram denotes the event A B =
A O B. Further,
i) the events A O B and B are disjoint, since ( A D 5 ) n 5 = A D ( 5 n 5 ) = A n 0 =
0; and
ii) (A n B ) U B = (A U B) n (B U B) = (A U B) D if = A U B.
From these two observations and axiom (3) it follows that
(*) Pr{A U B) = Pr(( A D B ) U B ) = Pr ( A f l 5 ) + Pr(B).
Next note that A = A D if = A D (B U B) = (A D B) U (A D B) where (A D B) D
(A fl B) = (A fl A) fl (B fl B) = A n 0 = 0. So once again axiom (3) gives us
Pr(A) = Pr ( A Pi B) -j- Pr ( A Pi B), or
(**) Pr ( A P B ) = Pr(A) - Pr ( A P B).
The results in Eqs. (*) and (**) now establish the following.
162 Chapter 3 Set Theory
T H E O R E M 3.8 The Additive Rule. If iP is the sample space for an experiment % , and A, B c if, then
At this point we use the result in Theorem 3.8 in the following two examples.
Yosi selects a card from a well-shuffled standard deck. What is the probability his card is a
E X A M P L E 3.42
club or a card whose face value is between 3 and 7 inclusive?
Start by defining the events A, B as follows:
A: The card drawn is a club.
B: The face value of the card drawn is between 3 and 7 inclusive.
The answer to the problem is Pr ( A U B).
Here Pr(A) = 13/52 and P r ( B ) = 20/52. Also Pr ( A n B) = 5/52 for the 3 of
clubs, 4 of clubs,. . . , and 7 of clubs. Consequently, by Theorem 3.8, we have
13 20 5 28 7
Pr ( A U B) = Pr(A) + Pr(B) - Pr ( A p 5 ) = - + - =
13
Diane inspects 120 cast aluminum rods and classifies the diameter and surface finish of
E X A M P L E 3.43
each rod as adequate or superior. Her findings are summarized in Table 3.4.
Table 3.4
Diameter
adequate superior
Surface adequate 10 18
Finish superior 12 80
Pr ( A U B) = Pr(A) + Pr(B) - Pr ( A P B)
98 92 80 _ 110 _ 11
0.916667.
_ 120 120 _ 120 ~ 120 ~ 12
So 110 [= 110.40 = (0.92)(120)] of these 120 rods have either a superior diameter or a
superior surface finish, or perhaps both.
3.5 The Axioms of Probability (Optional) 163
In addition,
Pr(A) = the probability the diameter of the rod is classified as adequate = (10+12) 120
_
m = 1 - n s = 1 - / , r ( A) *and
Pr(B) = the probability the surface finish of the rod is classified as adequate = ( 1 0120
+18)
28 92
120 120
1 - Pr(B).
Now we want to extend the result of Theorem 3.8 to more than two events. The following
theorem deals with three events and suggests the pattern for four or more.
T H E O R E M 3.9 Let if be the sample space for an experiment %. For events A , B , C c if,
Pr(AU B U C ) =
Pr{A) + Pr(B) + Pr(C) - Pr ( A OB) Pr ( A P C )- Pr ( B Pi C) + Pr ( A D B Pi C).
Proof: The Laws of Set Theory from Section 3.2 validate what follows:
Well see more formulas like the one in Theorem 3.9 in Section 8.1. For now let us apply
the result of this theorem in the following example.
The game of Roulette is played by initially spinning a small white ball on a circular wheel that
E X A M P L E 3.44
is divided into 38 sections of equal area. These sections are labeled 00, 0, 1, 2, 3, . . . , 36.
164 Chapter 3 Set Theory
As the wheel slows down, the number of the section where the ball comes to rest is the
outcome for that one play of the game.
The numbers on the wheel are colored as follows.
Green: 00 0
Red: 1 3 5 7 9 12 14 16 18
19 21 23 25 27 30 32 34 36
Black: 2 4 6 8 10 11 13 15 17
20 22 24 26 28 29 31 33 35
A player may place bets in various ways, such as (i) odd, even (here 00 and 0 are considered
neither even nor odd); (ii) low (1-18), high (19-36); or (iii) red, black.
Gary enjoys Roulette and decides to place bets according to the events.
A: The outcome is low. B : The outcome is red. C: The outcome is odd.
What is the probability Gary wins at least one of his bets that is, what is P r ( A U 5 U C ) ?
Here Pr(A) = P r ( B ) = Pr(C) = 18/38, Pr ( A n B) = Pr ( A D C) = 9/38,
Pr ( B n C) = 10/38, P r ( A D B n C ) = 5/38, and by Theorem 3.9
18 18 18 9 9 10 5 31 .
Pr ( A U U C ) = - + + - - - + = = 0.815789.
38 38 38 38 38 38 38 38
In closing this section we need to make one more point. The examples weve seen here
and in the previous section have all dealt with finite sample spaces. Yet it is possible to have
situations where a sample space is infinite. For instance, suppose a man takes a drivers test
until he passes it. If he passes the test on his first try, we write P for this outcome. Should
he need three attempts to pass the test, then we write FFP to denote the first and second
failures followed by his passing of the test. Hence the sample space may be given here as
if = {P, FP, FFP, FFFP,. . .}, an example of a countably infinite^ set.
When dealing with sample spaces that are finite or countably infinite, we call the sample
space discrete. The coverage here in Chapter 3 deals strictly with discrete sample spaces
that are finite. However, in Section 9.2, well consider an example where the sample space
is countably infinite.
Finally, suppose an experiment calls for a technician to record the temperature, in degrees
Fahrenheit, of a heated iron rod. Theoretically, the sample space here could comprise an
open interval of real numbers for instance, if = {f|180F < t < 190F}. Here the sample
space is again infinite, but this time it is uncountably* infinite. In this case the sample space
is called continuous and now one needs calculus to solve the related probability problems.
We will not pursue this here but will direct the interested reader to the chapter references
especially, the text by J. J. Kinney [7].
1. Let if be the sample space for an experiment % and 2. Ashley tosses a fair coin eight times. What is the probability
let A, B be events from if, where P r ( A ) = 0.4, P r ( B ) = she gets (a) six heads; (b) at least six heads; (c) two heads; and
0.3, and Pr ( A Pi B) = 0.2. Determine P r(A ), Pr(B), (d) at most two heads?
3. Ten ping-pong balls labeled 1 to 10 are placed in a box. Let A , B denote the events
Two of these balls are then drawn, in succession and without
A: The sample has foam type 1.
replacement, from the box.
B: The sample meets specifications.
a) Find the sample space for this experiment.
b) Find the probability that the label on the second ball Determine Pr(A ), P r ( B ), P r ( A D B ) , P r ( A U B), Pr(A ),
drawn is smaller than the label on the first. P r(B ), Pr( A U B), P r ( A D B ) , Pr( A A B).
c) Find the probability that the label on one ball is even 1 1 . Consider the game of Roulette as described in Example
3.6
Conditional Probability: Independence
(Optional)
Throughout Sections 3.4 and 3.5 especially prior to and at the end of Example 3.35, as
well as in and after Example 3.41 we mentioned the idea of the independence of outcomes.
There we questioned whether the occurrence of a certain outcome might somehow affect the
occurrence of another outcome. In this section we extend this idea from a single outcome to
an event and make it more mathematically precise. To do so we proceed with the following.
Vincent rolls a pair of fair dice. The sample space if for this experiment is shown in Fig. 3.18,
E X A M P L E 3.45
along with the events
A: The sum (on the faces) is at least 9.
B : A double is rolled.
Before we suggest the result at the end of Example 3.45 as a general formula, let us
consider a second example one where the outcomes are not equally likely.
Lindsay has a coin that is biased with Pr(H) = | and P r(T) = She tosses this coin
E X A M P L E 3.46
three times, where the result of each toss is independent of any preceding result. The eight
possible outcomes in the sample space have the following probabilities:
3.6 Conditional Probability: Independence (Optional) 167
/Y(HHH) = ( | ) 3 = i
/Y(HHT) = FY(HTH) = Pr(THH) = ( | ) 2 ( |) = ^
Fr(H TT) = Fr(THT) = /V(TTH) = () ( | ) 2 = ^
Pr(TTT) = Q )3 = .
/V (H H T) = ^ 1 ) = (4 /2 7 ) _ 2 /V (H H H ) = P r (H H H ) _ ( 8 /2 7 ) _ 4
(1 8 /2 7 ) 9 Pr(A ) ( 1 8 /2 7 ) 9
Motivated by the final result in each of the last two examples, we now summarize the
underlying general procedure. We want a formula for Pr(B\A), the conditional probability
of the occurrence of event B given the occurrence of event A. Further, this formula should
help us avoid unnecessary calculations such as those in Example 3.46, where we recalculated
the probability of each outcome in A.
Now once we know that the event A has occurred, the sample space if shrinks to the
outcomes in A. If we divide the probability of each outcome in A by P r ( A ), as in Example
3.46, the sum of these new probabilities sums to 1, so A can serve as the new sample
space. Further, suppose e\, 2 are two outcomes in if with = k P r ( e i), where k is
a constant. If e \ , 2 A, then within the new sample space A the probability of e\ is still k
times that of 2-
To calculate Pr(B\ A) we now consider those outcomes in event A that are in event B.
This gives us the outcomes in event B H A and leads us to the following.
\
If if is the sample space for an experiment % and A, B c if, then
Pr(B f\A )
the conditional probability o f B given A Pr(B\A) =
P r (A )
so long as Pr(A) 0.
Further,
Pr{B n A) = Pr ( A n B) = Pr{A) Pr{B\ A) ,
168 Chapter 3 Set Theory
A cooler contains seven cans of cola and three cans of root beer. Without looking at the
E X A M P L E 3.47
contents, Gustavo reaches in and withdraws one can for his friend Jody. Then he reaches in
again to get a can for himself.
Let A , B denote the events
A: The first selection is a can of cola.
B : The second selection is a can of cola.
a) Using the multiplicative rule, the probability that Gustavo chooses two cans of cola is
Pr ( A D B ) = Pr {A) Pr {B\ A) =
[Here Pr{B\A) = 6/9 because after the first can of cola is removed, the cooler then
contains six cans of cola and three of root beer.]
b) The multiplicative rule and the additive rule (of Theorem 3.8) tell us that the probability
Gustavo selects two cans of cola or two cans of root beer is
Pr ( A D B ) + Pr ( A Pi B) P( A) P( B\ A) + Pr ( A) Pr ( B\ A)
* )( IM * ) ( K
c) Finally, let us determine Pr{B). To do so we develop a new formula with the help of
the Venn diagram (for a sample space if and events A, B) in Fig. 3.19. From the fig
ure (and the laws of set theory) we see that B = B D i f = B O (A U A) = ( B O A) U
(B P A), where (B n A) n (B HA) = B n (A HA) = B n =
Pr{B) = Pr ( B P A) + Pr ( B P A)
= Pr ( A) Pr ( B\ A) + Pr ( A) Pr ( B\ A)
-(*)(IM *)G)- - w
Figure 3.19
3.6 Conditional Probability: Independence (Optional) 169
Pr(B) = Pr ( A) Pr ( B\ A) + Pr ( A) Pr ( B\ A)
is referred to as the Law of Total Probability. Our next example shows how this result can
be generalized.
Emilio is a system integrator for personal computers. As such he finds himself using key
E X A M P L E 3.48
boards from three companies. Company 1 supplies 60% of the keyboards, company 2
supplies 30% of the keyboards, and the remaining 10% comes from company 3. From past
experience Emilio knows that 2% of company l s keyboards are defective, while the per
centages of defective keyboards for companies 2, 3 are 3% and 5%, respectively. If one of
Emilios computers is selected, at random, and then tested, what is the probability it has a
defective keyboard?
Let A denote the event
A: The keyboard comes from company 1.
Events B , C are defined similarly for companies 2, 3, respectively. Event D, meanwhile, is
D: The keyboard is defective.
Here we are interested in Pr(D). Guided by the Venn diagram in Fig. 3.20, we see that
D = D n i f = D n ( A U f i U C ) = ( D n A ) U ( D D 5 ) U ( D n C). But here A D B =
A r ) C = B i ) C = $. So now, for example, the Laws of Set Theory show us that (D D A)
Pi (D Pi fl) = D Pi (A Pi fl) = D Pi 0 = 0. Likewise, (D Pi A) Pi (D n C) = (D Pi B) n
(D f! C) = 0, and (D D A) D (D D B) D (D D C) = 0. Consequently, by Theorem 3.9, we
have
Pr(D) = Pr ( D Pi A) + Pr ( D Pi B) + Pr ( D Pi C)
= Pr { A) Pr { D\ A) + Pr ( B ) P( D\ B) + Pr(C)Pr( D\ C) .
(Here we have the Law of Total Probability for three sets; that is, the sample space if is the
union of three sets, any two of which are disjoint.)
Figure 3.20
From the information given at the start of this example we know that
P r { A ) = 0.6 Pr{B) = 0.3 Pr(C) = 0.1
Pr(D\ A) = 0.02 P r ( D \ B ) = 0.03 Pr(D\C) = 0.05.
So P r ( D ) = (0.6)(0.02) + (0.3)(0.03) + (0.1)(0.05) = 0.026, and this tells us that 2.6%
of the personal computers integrated by Emilio will have defective keyboards.
170 Chapter 3 Set Theory
The next example takes us back to the situation in Example 3.48 and introduces us to
Bayes' Theorem. As with the Law of Total Probability, the situation here likewise general
izes that is, when appropriate, Bayes Theorem may be applied to any sample space if
that is decomposed into two or more events that are disjoint in pairs.
Referring back to the information in the preceding example, now we ask the question If
E X A M P L E 3.49
one of Emilios personal computers is found to have a defective keyboard, what is the
probability that keyboard came from company 3?
Using the notation in Example 3.48 we see that here the given condition is D and that
we want to find Pr(C\D).
Pr( CDD) Pr ( C) Pr ( D\ C)
Pr{C\D) =
Pr(D) Pr ( A) Pr ( D\ A) + P r ( B ) P r ( D \ B ) + Pr ( C) Pr ( D\ C)
(0.1)(0.05) 0.005 5 .
= =0.192308.
(0.6) (0.02) + (0.3)(0.03) + (0.1)(0.05) 0.026 26
[Before leaving this example let us observe a small point. Since we have a choice on how
to rewrite the numerator of , do we know weve made the correct choice? Yes!
The other choice, namely, Pr (C D D) = P r ( D ) P r ( C \ D ), would tell us that Pr(C\D) =
P rjC nD ) _ P r(D )P r(C \D ) _
Pr(D ) Pr(D )
Pr ( C| D) , a correct but not very useful result.
Having dealt with the Law of Total Probability and Bayes Theorem, it is now time to
settle the issue of independence. In our work on conditional probability we learned earlier
that for events A , B, taken from a sample space if, Pr{A D B) = Pr{A) Pr{B\ A) . Should
the occurrence of event A have no effect on that of B, we have Pr(B\ A) = Pr ( B) and
so event B is independent of event A. These considerations now guide us to the following.
Definition 3.12 Given a sample space if with events A , B c if, we call A , B independent when
P r ( A D B ) = Pr ( A) Pr ( B) .
Our next example uses the preceding discussion to decide whether two events are inde
pendent.
Suppose Arantxa tosses a fair coin three times. Here the sample space if = {HHH, HHT,
E X A M P L E 3.50
HTH, THH, HTT, THT, TTH, TIT }, where each outcome has probability | .
Consider the events
A: The first toss is H: A = {HHH, HHT, HTH, HTT} and Pr{A) = \\
B : The second toss is H: B = {HHH, HHT, THH, THT} and Pr(B) = \\
3.6 Conditional Probability: Independence (Optional) 171
C: There are at least two Hs: C = {HHT, HTH, THH, HHH) and Pr(C) = .
T H EO R EM 3.10 Let A, B be events taken from a sample space if. If A, B are independent, then (a) A, B
are independent; (b) A, B are independent; and (c) A, B are independent.
Proof: [We shall prove part (a) and leave the proofs of parts (b), (c) for the Section Exercises.]
Since A = A D if = A D (B U B) = (A D B) U (A D B) and (AH B) Pi (A Pi B) =
A Pi (B Pi B) = A Pi 0 = 0, we have Pr(A) = Pr ( A Pi B) -j- Pr ( A Pi B). With A, B inde
pendent, it follows that Pr ( A D B) = Pr ( A) Pr ( B) . The last two equations imply that
Pr ( A H B)_= P r ( A ) - Pr ( A Pi B) = Pr(A) - Pr {A) Pr{B) = Pr_(A)[ 1 - Pr(B)] =
Pr ( A) Pr ( B) . Consequently, from Definition 3.12 we know that A, B are independent.
Our next example will help motivate the idea of independence for three events.
Tino and Monica each roll a fair die. If we let jc denote the result of Tinos roll and y that of
E X A M P L E 3.51
Monicas, then once again if = {(jc, y)| l < x , y < 6}. Now consider the events A, B , C:
A: Tino rolls a 1, 2, or 6.
B : Monica rolls a 3, 4, 5, or 6.
C : The sum of Tinos and Monicas rolls is 7.
Here Pr(A) = | | = Pr{B) = | = | , and P r ( C ) = = . Further,
A P B = {(<a, b)\a G {1, 2, 6}, b e {3, 4, 5, 6}}, so |A P B\ = 12 and Pr ( A P B) =
| | = \ = ( |) ( |) = P r ( A ) P r ( B ), so A, B are independent;
A n C = {(1, 6), (2, 5), (6, 1)} and Pr ( A n C) = ^ = = (I) ( i) = p r {A)Pr(C),
making A, C independent;
n C = {(4, 3), (3, 4), (2, 5), (1, 6)} and Pr ( B D C) = = | = (f) ( i) =
Pr ( B) Pr ( C) , so B, C are also independent.
Finally,
A n B n C = {(1, 6), (2, 5)} and Pr ( A n B D C) = = ^ = Q ) ( | ) () =
Pr ( A) Pr ( B) Pr ( C) .
Definition 3.13 For a sample space if and events A, B, C c. if, we say that A, B, C are independent if
1) Pr ( A D B ) = Pr ( A) Pr ( B) \
2) P r ( A D C ) = Pr ( A) Pr ( C) \
3) Pr ( B DC) = Pr ( B) Pr ( C) \ and
4) Pr ( A n B D C ) = Pr ( A) Pr ( B) Pr ( C) .
Looking back now at Example 3.51 we see that there we verified the independence of the
events A, B, C. But did we do too much? In particular, do we really need condition (4) in
Definition 3.13? Perhaps we may feel that the first three conditions are enough to insure the
fourth condition. But, perhaps, they are not enough. The next example will help us settle
this issue.
Adira tosses a fair coin four times. So in this case the sample space if =
E X A M P L E 3.52
{*1*2*3*41*1 {H, T}, 1 < i < 4}.
Let A, B, C c if be the events:
A: Adiras first toss is a tail (T);
B: Adiras last toss is a tail (T); and
C: The four tosses yield two heads and two tails.
For these events we find that Pr(A) = ^ Pr(B) = ^ and Pr(C) = -^(2) =
6 _
_ _ 3
16 8*
In addition,
Pr ( A n B) = | = 5 = ( |) ( | ) = Pr{A)Pr{B),
Pr ( A n C ) 4 = 0 ( | ) = Pr ( A) Pr ( C) , and
Pr ( B n C ) 4 = 0 ( |) = Pr ( B) Pr ( C) .
In closing this section we provide a summary of the probability rules and laws we have
learned in this and the preceding section.
1. Recall that in a standard deck of 52 cards there are 12 pic 5 . Let i f be the sample space for an experiment %and let A, B
ture cards four each of jacks, queens, and kings. Kevin draws be events from i f . If A, B are independent, prove that
one card from the deck. Find the probability his card is a king
Pr ( A U B) = P r ( A ) + Pr ( A) Pr ( B)
if we know that the card drawn is an ace or a picture card.
= Pr( B) + Pr( B) Pr( A) .
2.Let A, B be events taken from a sample space if.
If Pr ( A ) = 0.6, Pr{B) = 0.4, and Pr ( A U B) = 0.7, find 6. Ceilia tosses a fair coin five times. What is the probabil
Pr(A\B) and Pr(A\B). ity she gets three heads, if the first toss results in (a) a head;
3. If Coach Mollet works his football team throughout August, (b) a tail?
then the probability the team will be the division champion is 7. One bag contains 15 identical (in shape) coins nine of
0.75. The probability the coach will work his team throughout silver and six of gold. A second bag contains 16 more of these
August is 0.80. What is the probability Coach Mollet works his coins six silver and 10 gold. Bruno reaches in and selects one
team throughout August and the team finishes as the division coin from the first bag and then places it in the second bag. Then
champion? Madeleine selects one coin from this second bag.
4 . The 420 freshmen at an engineering college take either
a) What is the probability Madeleine selected a gold coin?
calculus or discrete mathematics (but not both). Further, both
b) If Madeleines coin is gold, what is the probability
courses are offered providing either an introduction to a CAS
Bruno had selected a gold coin?
(computer algebra system) or using such a system extensively
throughout the course. The results in Table 3.6 summarize how 8. A coin is loaded so that Pr(H ) = 2/3 and Pr( T) = 1/3.
the 420 freshmen are distributed. Todd tosses this coin twice.
Let A , B be the events
CAS CAS A: The first toss is a tail. B: Both tosses are the same.
(Introduction) (Extensive
Coverage) Are A , B independent?
9 . Suppose that A, B are independent with Pr ( A U B) = 0.6
Calculus 170 120
and Pr(A) = 0.3. Find Pr(B).
Discrete Mathematics 80 50
10. Alice tosses a fair coin seven times. Find the probability
a) If Sandrine is taking calculus, what is the probability she gets four heads given that (a) her first toss is a head; (b) her
her class is only being introduced to the use of a CAS? first and last tosses are heads.
174 Chapter 3 Set Theory
11. Paulo tosses a fair coin five times. If A, B denote the events C : The tosses result in one head and one tail.
A: Paulo gets an odd number of tails. Are the events A, B, and C independent?
B : Paulos first toss is a tail. 20. Three missiles are fired at an enemy arsenal. The probabil
ities the individual missiles will hit the arsenal are 0.75, 0.85,
arc A, B independent?
and 0.9. Find the probability that at least two of the missiles hit
12. The probability that a certain mechanical component fails the arsenal.
when first used is 0.05. If the component does not fail immedi
21. Dustin and Jennifer each toss three fair coins. What is the
ately, the probability it will function correctly for at least one
probability (a) each of them gets the same number of heads?
year is 0.98. What is the probability that a new component func
(b) Dustin gets more heads than Jennifer? (c) Jennifer gets more
tions correcdy for at least one year?
heads than Dustin?
13. Paul has two coolers. The first contains eight cans of cola
22. Tiffany and four of her cousins play the game of odd person
and three cans of lemonade. The second cooler contains five
out to determine who will rake up the leaves at their grand
cans of cola and seven cans of lemonade. Paul randomly se
mother Mary Lous home. Each cousin tosses a fair coin. If the
lects one can from the first cooler and puts it into the second
outcome for one cousin is different from that of the other four,
cooler. Five minutes later Betty randomly selects two cans from
then this cousin has to rake the leaves. What is the probability
the second cooler. If both of Bettys selections are cans of cola,
that a lucky cousin is determined after the coins are flipped
what is the probability Paul initially selected a can of lemonade?
only once?
14. Let if be the sample space for an experiment % and let
23. Ninety percent of new airport-security personnel have had
A, B, C c i f . If events A, B are independent, events A, C
prior training in weapon detection. During their first month on
are disjoint, and events B, C are independent, find P r ( B ) if
the job, personnel without prior training fail to detect a weapon
Pr ( A ) = 0.2, Pr ( C ) = 0.4, and Pr ( A U B U C) = 0.8.
3% of the time, while those with prior training fail only 0.5%
15. An electronic system is made up of two components con of the time. What is the probability a new airport-security em
nected in parallel. Consequently, the system fails only when ployee, who fails to detect a weapon during the first month on
both of the components fail. The probability the first component the job, has had prior training in weapon detection?
fails is 0.05 and, when this happens, the probability the second
24. The binary string 101101, where the string is unchanged
component fails is 0.02. What is the probability the electronic
upon reversing order, is called a palindrome (of length 6). Sup
system fails?
pose a binary string of length 6 is randomly generated, with 0 ,
16. Gayla has a bag of 19 marbles of the same size. Nine of 1 equally likely for each of the six positions in the string. What
these marbles are red, six blue, and four white. She randomly is the probability the string is a palindrome if the first and sixth
selects three of the marbles, without replacement, from the bag. bits (a) are both 1 ; (b) are the same?
What is the probability Gayla has withdrawn more red than
25. In defining the notion of independence for three events
white marbles?
we found (in Definition 3.13) that we had to check four con
17. Let A, B, C be independent events taken from a sample ditions. If there are four events, say E\, E2, E3, 4 , then we
space f. If Pr ( A ) = 1/8, P r ( B ) = 1/4, and Pr( A U f iU C ) have to check 11 conditions six of the form Pr(Ei Pi Ej) =
= 1/2, find P r(C ). Pr ( El) Pr { EJ), 1 < i < j < 4; four of the form Pr ( Et fl
18. A company involved in the integration of personal comput Ej Pi Ek) = Pr ( Ei ) Pr ( Ej ) Pr ( Ek), 1 < i < j < k < 4; and
ers gets its graphics cards from three sources. The first source Pr { Ex D E 2 n E 3 n Ea) = Pr ( E{ ) Pr (E2) P r ( E z) Pr ( EA).
provides 20% of the cards, the second source 35%, and the third (a) How many conditions need to be checked for the indepen
source 45%. Past experience has shown that 5% of the cards dence of five events? (b) How many for n events, where n> 2?
from the first source are found to be defective, while those from 26. Let A , B be events taken from a sample space If Pr (A fl
the second and third sources are found to be defective 3% and B) = 0.1 and Pr ( A Pi B) = 0.3, what is Pr( A A | AUZ?)?
2%, respectively, of the time.
27. Urn 1 contains 14 envelopes (of the same size) six each
a) What percentage of the companys graphics cards are contain $1 and the other eight each contain $5. Urn 2 contains
defective? eight envelopes (of the same size as those in urn 1 ) three
b) If a graphics card is selected and found to be defective, each contain $1 and the other five each contain $5. Three en
what is the probability it was provided by the third source? velopes are randomly selected from urn 1 and transferred to um
2. If Carmen now draws one envelope from um 2, what is the
19. Gustavo tosses a fair coin twice. For this experiment con
sider the following events: probability her selection contains $ 1 ?
28. Let A, B be events taken from a sample space (with
A: The first toss is a head.
Pr(A) > 0 and Pr(B) > 0). If Pr( B\ A) < Pr(B), prove that
B : The second toss is a tail. Pr(A\B) < Pr(A).
3.7 Discrete Random Variables (Optional) 175
29. Let A, B be events taken from a sample space f. If 30. Let if be the sample space for an experiment %, with events
Pr ( A ) = 0.5, Pr( B) = 0.3, and Pr( A\ B) + Pr( B\ A) = 0.8, A, B c Sf. If Pr(A\ B) = Pr ( A A B) = 0.5 and Pr(A U B)
what is Pr( A Pi B)1 = 0.7, determine Pr(A) and Pr(B).
3.7
Discrete Random Variables (Optional)
In this section we introduce a fundamental idea in the study of probability and statistics
namely, the random variable. Since we are dealing exclusively with discrete sample spaces,
we shall deal only with discrete random variables. Consequently, whenever the term ran
dom variable arises, it is understood that it is a discrete random variable that is, a random
variable defined for a discrete sample space. [Those interested in continuous random vari
ables should consult the chapter references. Chapter 3 of the text by John J. Kinney [7] is
an excellent starting point.]
We introduce the concept of a random variable in an informal way. The following
example will help us do this.
If Keshia tosses a fair coin four times, the sample space for this random experiment may
E X A M P L E 3.53
be given as
if = {HHHH,
HHHT, HHTH, HTHH, THHH,
HHTT, HTHT, HTTH, THHT, THTH, TTHH,
HTTT, THTT, TTHT, TTTH,
TTTT}.
Now, for each of the 16 strings of H s and T s in if, we define the random variable X as
follows:
For JC1JC2JC3JC4 e if, X (jciJC2JC3JC4) counts the number of H s that appear among the four
components x\, *2, *3, *4. Consequently,
X (HHHH) = 4,
X (HHHT) = X (HHTH) = X (HTHH) = X (THHH) = 3,
X (HHTT) = X (HTHT) = X (HTTH) = X (THHT) = X (THTH) = X (TTHH) = 2,
X (HTTT) = X (THTT) = X (TTHT) = X (TTTH) = 1, and
X (TTTT) = 0.
We see that X associates1 each of the 16 strings of H s and Ts in if with one of the
nonnegative integers in {0, 1, 2, 3, 4} (a subset of R). This allows us to think of an outcome
in if in terms of a real number. Further, suppose we are interested in the event
A: the four tosses result in two H s and two Ts.
^This association by X between the strings in and the nonnegative integers 0, 1, 2, 3, 4 is an example of
a function an idea to be covered in detail in Chapter 5. In general, a random variable is a function from the
sample space of an experiment % to R, the set of real numbers. The domain of any random variable X is and
the codomain is always R. The range in this case is {0, 1, 2, 3, 4}. (The concepts of domain, codomain, and range
are formally defined in Section 5.2.)
176 Chapter 3 Set Theory
Suppose Giorgio rolls a pair of fair dice. This experiment was examined earlier for
E X A M P L E 3.54
instance, in Examples 3.33 and 3.45. The sample space here comprises 36 ordered pairs
and may be expressed as if = {(jc, y )|l < x < 6, 1 < y < 6}.
We define the random variable X, for each ordered pair (x. y) in if, by X ((.v. y )) =
x + y, the sum of the numbers that appear on the (tops of) two fair dice. Then X takes on
the following values:
X ((l, 1 )) = 2
X ((1 ,2 ) ) = X ( ( 2 ,1 ) ) = 3
X ((l, 3)) = X((2, 2)) = X((3, 1)) = 4
X ((l, 4)) = X((2, 3)) = X((3, 2)) = X((4, 1)) = 5
X ((l, 5)) = X((2, 4)) = X((3, 3)) = X((4, 2)) = X((5, 1)) = 6
X ((l, 6)) = X((2, 5)) = X((3, 4)) = X((4, 3)) = X((5, 2)) = X ((6, 1)) = 7
X ((2 , 6)) = X((3, 5)) = X((4, 4)) = X((5, 3)) = X ((6, 2)) = 8
X((3, 6)) = X((4, 5)) = X((5, 4)) = X ((6, 3)) = 9
X((4, 6)) = X((5, 5)) = X ((6, 4)) = 10
X((5, 6)) = X ( ( 6, 5)) = 11
X((6, 6)) = 12
The probability distribution for X is as follows:
Pr(X = 2) = 1/36 Pr(X = 6) = 5 /3 6 P r ( X = 10) = 3/36
Pr(X = 3) = 2/36 Pr(X = 7) = 6/36 P r ( X = 11) = 2 /3 6
Pr(X =4) = 3/36 Pr(X = 8) = 5/36 P r ( X = 12) = 1/36
Pr(X =5) = 4 /3 6 Pr(X =9) = 4 /3 6
3.7 Discrete Random Variables (Optional) 177
x 1
x = 2, 3, 4, 5, 6, 7
36
Pr(X = x)
1 2 - (x - 1 )
x = 8, 9, 10, 11, 12.
The preceding two examples have shown us how a random variable may be described by
its probability distribution. Now we shall see how a random variable can be characterized
by means of two measures its e x p e c te d v a lu e , a measure of central tendency, and its
v a r ia n c e , a measure of dispersion.
When a fair coin is tossed 10 times, our intuition may suggest that we expect to get
five heads and five tails. Yet we know that we could actually see 10 heads, although the
probability for this outcome is only (}o)(|) = ^ 0-000977, while the probability
for five heads and five tails is substantially higher as (s0) ^ ) 5^ ) 5 = = 0.246094.
Similarly, we may want to know how many times we might expect to see a 6 when a fair
die is rolled 50 times. To deal with such concerns we introduce the following idea.
Definition 3.14 Let X be a random variable defined for the outcomes in a sample space if . The m ea n , or
e x p e c te d v a lu e , of X is
E(X) = Pr{X=x),
X
where the sum is taken over all the values jt determined by the random variable X \
^One finds the terms mean (value) and expectation also used to describe E (X ), as well as the alternate notation
Ux Further, although our discussion deals solely with finite sample spaces, the above formula is valid for countably
infinite sample spaces, so long as the infinite sum converges.
178 Chapter 3 Set Theory
a) If a fair coin is tossed once and X counts the number of heads that appear, then
E X A M P L E 3.55
1
if = {H, T}, X(H) = 1, X (T) = 0, Pr ( X = 0) = P r ( X = 1)
2
i 1 1 1
and (X ) = j c - P r ( X = * ) = 0 . - + ! - = - .
(l + 2 + + 6)
Note, once again, that E( X) is not among the values determined by the random vari
able X.
c) Suppose now we have a loaded die, where the probability of rolling the number i
is proportional to i. As in part (b), if = {1, 2, 3, 4, 5, 6} and X(i ) = i for 1 < i < 6.
However, here, if p is the probability of rolling 1, then ip is the probability of roll
ing /, for each of the other five outcomes i , where 2 < i < 6. From axiom (2),
1 = E f= i = K 1 + 2 + + 6) = 2 t / 7, so /? = 1/21 and P r ( X = i ) = i / 21,
1 < i < 6. Consequently,
E(X) = ^ x - JP r ( X = ^ ) = 1 . 2 . + 2 . ^ + . . . + 6 - | r
_ 1 + 4 + 9 + 16 + 25 + 36 _ 91 _ 13
21 21 ~ T '
d) Consider the random variable X in Example 3.53, where a fair coin was tossed four
times. Then here
6 4 1
E( X) = P r ( X = x ) = 0 - - ^ + l -i + 2
x=0 16 16 16 + 3 ' 16 + 4 ' 16
_ 0+ 4+12+12 + 4
= 2.
16
In this case E{X) is found to be among the values determined by the random vari
able X.
e) Finally, for Example 3.54, where Giorgio rolled a pair of fair dice, we find that
6 5
E W ' 2 -36 3 3 6 + ' + " + 7 ' 3 6 + 8 '36 + + n ' h + l 2 h
252
= 7.
16 "
Before continuing let us recall from Section 3.5 that a Bernoulli trial is an experiment
with exactly two outcomes success, with probability p, and failure, with probability
q = 1 p. When such an experiment is performed n times, and the outcome of any one
3.7 Discrete Random Variables (Optional) 179
trial is independent of the outcomes of any previous trials, then the probability that there
are (exactly) k successes among the n trials is ()p kqn~k, 0 < k < n.
Now if we consider the sample space of all 2n possibilities for the n outcomes of these
n Bernoulli trials, then we can define the random variable X , where X counts the number
of successes among the n trials. Under these circumstances X is called a binomial random
variable and
Pr(X =x ) p xqn~x , x = 0, 1 , 2, . . . , n.
This probability distribution is called the binomial probability distribution and it is com
pletely determined by the values of n and p. Further, it is precisely the type of probability
distribution that occurs in Example 3.53, where we regard an H as a success and find that
G)'
*
But why should we be bringing all of this up here in the discussion on the expected value of
a random variable? At this point notice that in part (d) of Example 3.55 we found E (X) = 2,
where X is the binomial random variable described above. For this binomial random variable
X we haven = 4 and/? = 1/2. Is it just a coincidence here that E( X) = 2 = (4) (1/2) = npl
Suppose we were to roll a fair die 12 times and ask for the number of times we expect to
see a 5 come up. Here the binomial random variable X would count the number of times a 5
is rolled among the 12 rolls. Our intuition might suggest the answer is 2 = (12) (1/6) = np.
But is this once again E( X) for this binomial random variable X I Instead of verifying this
result directly by using the formula in Definition 3.14, we shall obtain the result from
the following theorem.
T H EO R EM 3.11 Let X be the binomial random variable that counts the number of successes, each with
probability /?, among n Bernoulli trials. Then E{X) = np.
Proof: From Definition 3.14 we have
E( X) = J 2 x - P r ( X = x) = J 2 JCI \ p xqn~x
x=0 x=0
p xq n - x
E{X) =
>C)
2X = \ x 7
p xq n- x
-E
XT[ x\(n x)!
_ n' x n - x _ v ' (n ~ 1 )! p x- l q n-x
j (x - !)!( - x ) \ P q nP~ [ { x - \ ) \ { n - x ) \
180 Chapter 3 Set Theory
n- 1
(n - 1)!
p yq n~(y+ d upon substituting y = x l ,
= np L
y'.[n - ( y + 1)]! and realizing that y varies from 0 to
n 1 when jc varies from 1 to n
n 1 n-
p y q {n i) - y =
np ( p + q)
1
by the binomial theorem
y= 0 v y
= np, since p + q = 1.
As a result of Theorem 3.11 we now know that upon rolling a fair die 12 times the num
ber of 5s we e x p e c t to see is (12) (1/6) = 2, as our intuition suggested earlier. Better still,
should we roll this fair die 1200 times and let the random variable Y count the num
ber of 5s that appear, then Y is a binomial random variable with n = 1200, p = 1/6, and
Pr(Y = y ) = (Uy ) ( l Y ( l ) U0 y , y = 0, 1, 2, . . . , 1200. Further, instead of trying to
determine E ( Y ) by actually calculating y ( ) y(S) 12 ^ we obtain E ( Y ) =
np = (1200) (1/6) = 200, quite readily from Theorem 3.11.
Having dealt with the concept of the mean, or expected value, of a random variable X,
we turn now to the variance of X a measure of how widely the values determined by
X are dispersed or spread out. If X is the random variable defined on the sample space
if* = {a, b, c}, where X ( a ) = - 1 , X ( b ) = 0, X ( c ) = 1, and P r ( X = x ) = 1/3, for jc =
1,0, 1, then E ( X ) = 0. But then if Y is the random variable defined on the sample
space ify = {r, s , t, u, u}, where Y ( r ) = - 4 , F(s) = - 2 , Y ( t ) = 0, Y { u ) = 2, F(u) = 4 ,
a n d P r(F = y ) = 1/5, for y = 4, 2, 0, 2, 4, we get the same mean that is, E ( Y ) = 0.
However, although E ( X ) = E ( Y ), we can see that the values determined by F are more
spread out about the mean of 0 than the values determined by X. To measure this notion of
dispersion we introduce the following.
Definition 3.15 Let i f be the sample space for an experiment % and let X be a random variable defined on
the outcomes in if. Suppose further that E ( X ) is the mean, or expected value, of X . Then
the v a r ia n c e of X , denoted o \ , or Var(X), is defined by
where the sum is taken over all the values of jc determined by the random variable X.
The s ta n d a r d d e v ia tio n of X , denoted ctx, is defined by
a* = /V ar(X ).
Let X be the random variable defined on the outcomes of the sample space if = [ a , b, c, dj ,
E X A M P L E 3.56
with X ( a ) = 1, X ( b ) = 3, X ( c ) = 4, and X ( d ) = 6.
Suppose the probability distribution for X is
X Pr(X = x)
1 1/5
3 2/5
4 1/5
6 1/5.
3.7 Discrete Random Variables (Optional) 181
Then
1 2 1 1 17
E (X , = 1 . - + 3 . - + 4 . - + 6 . - = t
and
Var(X) = E ( X - E( X) )
Pr ( X = x)
-('-tH +O-tHD
-(f)GM)GMI)GM5
_ / 330 \ /1\ _ 66
U ; 25
Our next result provides a second way by which we can compute Var(X).
T H EO R EM 3.12 If X is a random variable defined on the outcomes of a sample space if, then
Var(X) = E ( X 2) - [ (X )]2.
Proof: From Definition 3.15 we know that
Var(X) = E ( X - E ( X) ) 2 = ^ ( x - E ( X) ) 2 P r ( X = x ).
Jt
Expanding within the summation we have
Var(X) = y ] ( x 2 - 2x E ( X ) + [ (X )]2) Pr ( X = x)
X
= * 2Pr ( X = x) - 2E( X) ^ 2 x P r ( X = x)
X X
and J 2 P r (X = x) = 1
= E ( X 2) - [ (X )]2.
Let us check the result for Var(X) in Example 3.56 by using Theorem 3.12.
182 Chapter 3 Set Theory
Well use the formula of Theorem 3.12 a second time in the following.
In Example 3.53 we studied the random variable X , which counted the number of heads
E X A M P L E 3.58
that result when a fair coin is tossed four times. Soon thereafter we learned that X was
a binomial random variable with n = 4, p = 1/2, q = 1 p = 1/2, and P r ( X = x) =
(2) ()* (^)4 * , x = 0, 1, 2, 3, 4. Further, in part (d) of Example 3.55 we found that
E( X) = 2 (= n p , as we learned later in Theorem 3.11). To compute Var(X) we use the
formula in Theorem 3.12, but first we consider the following.
X x2 Pr(X=x)
0 0 1/16
1 1 4/16
2 4 6/16
3 9 4/16
4 16 1/16
T H E O R E M 3.13 Let X be the binomial random variable that counts the number of successes, each with
probability p, among n independent Bernoulli trials. Then Var(X) = npq and ox y/npq,
where q = 1 p.
As a result of Theorems 3.11 and 3.13 we now find that our next example requires little
calculation.
Due to top-notch recruiting, Coach Jenkins baseball team has probability 0.85 of winning
E X A M P L E 3.59
each of the 12 baseball games it will play during the spring semester. (Here the outcome of
each game is independent of the outcome of any previous game.)
3.7 Discrete Random Variables (Optional) 183
Let X be the random variable that counts the number of games Coach Jenkins
team wins during the spring semester. Then P r ( X = x) = (^2)(0.85)*(0.15)12-*,
x = 0, 1, 2, . . . , 12. Further, with n = 12 and p = 0.85, we readily see that
E( X) = ^ ^ ^ ( ^ ( O . S S ^ i O . l S ) 12-^ = np = 12(0.85) = 10.2 andVar(X) =
Y , l 2=o(x ~ 10.2)2(1JC
2)(0.85)*(0.15)12-* - ^ 2 l2=o ^ 2(1x2)(0.85) x(0.15)12_x - (10.2)2 =
npq = (12)(0.85)(0.15) = 1.53.
Before we introduce the last idea for this section we shall consider an example in order
to motivate and illustrate the idea.
Referring back to Example 3.59, at this point we want to determine a lower bound for
E X A M P L E 3.60
the probability that the random variable X is within k standard deviations ax of the mean
E( X) , for k = 2, 3. When k = 2 we find that Pr ( E( X) - 2 o x < X < E( X) + 2ax ) =
Pr ( \ X E ( X )| < 2ox ). From the calculations in Example 3.59 we know that E( X) =
10.2 and Var(X) = 1.53, so a* = ^/L53 = 1.236932. Consequently, Pr ( \ X - E(X)\ <
2crx ) = Pr{ 10.2 - 2(1.236932) < X < 10.2 + 2(1.236932)) = Fr(7.726136 < X <
12.673864) = P r ( X = 8) + Pr { X = 9) + + Pr ( X = 12) =
E i =8 (*2) (0.85)x(0.15) 12~x = 0.068284 + 0.171976 + 0.292358 + 0.301218 +
0.142242 = 0.976078.
Likewise, for k = 3, Pr ( \ X - E(X)\ < 3ox ) = P r (6.489204 < X < 13.910796) =
Pr ( X = 1) + P r ( X = 8) + + Pr ( X = 12) = 0.019280 + 0.068284 + +
0.142242 = 0.995358.
But where is this lower bound that we mentioned at the start of our discussion? Looking
at the results for k = 2, 3 once more, we see that Pr{\ X E(X)\ < 2ax ) = 0.976078 >
| = 1 - ^ and Pr ( \ X - (X )| < 3ctx ) = 0.995358 > | = 1 - So
T H EO R EM 3.14 Chebyshevs Inequality. Let if be the sample space for an experiment % and let X be a
random variable defined on the outcomes in if. If E( X) is the mean of X and ax its
standard deviation, then for any k > 0,
^The proof presented here is valid for the case where the sample space is countably infinite, so long as all the
summations converge.
184 Chapter 3 Set Theory
(Note that A, B are not necessarily events for they need not be subsets of f. They are
subsets of the set of real numbers determined by the random variable X.)
We know that
Var(X) = a \ = - E( X) ) 2Pr ( X = x)
X
= y ] ( x - E( X) ) 2Pr ( X = x) + y y * - E( X) ) 2Pr ( X = x)
xeA xeB
For x e A , \x E (X) > kax and so it follows that here .v F. (X ) > ka x - Since
(x - E{ X) ) 2 = \ x - E ( X )|2 we now have
=> ^ > /V (|X - (X )| > *crx ) => ~ < Pr ( \ X - E(X)\ > *crx )
Our last example for this section shows how one might apply Chebyshevs Inequality
Angelica is selling boxes of candy for her choirs Christmas fund raiser. The pieces of candy
E X A M P L E 3.61
are packed into each box so that the mean number of pieces is 125 with a standard deviation
of 5 pieces. To find a lower bound on the probability that a box of Angelicas candy contains
between 118 and 132 pieces we proceed as follows.
Here the random variable X counts the number of pieces of candy in a box, with E (X) =
125 and ax = 5. Applying Chebyshevs Inequality we have
Pr(118 < X < 132) = Pr ( 118 - 125 < X - 125 < 132 - 125)
= P r ( - 1 < X - 125 < 7) = Pr ( \ X - 125| < 7)
/ /7 \ \ 1 25 24
v V \5J XJ - (7)2 49 49
Consequently, the probability that a box of Angelicas candy contains between 118 and
132 pieces is at least 24/49 = 0.489796. (Note here that the value of k in Chebyshevs
Inequality is 7/5, which is not an integer.)
3.7 Discrete Random Variables (Optional) 185
|
c(6 x), x = 1, 2, 3, 4, 5 a) Show that E ( X ( X 1)) = n 2p 2 np2.
0, otherwise, b) Using the fact that E ( X ( X - 1)) = E ( X 2 - X) =
where c is a constant. Determine (a) the value of c; E { X 2) E( X) and that E{X) = np , show that Var(X) =
(b) Pr ( X < 2); (c) E(X); and (d) Var(X). npq.
8. Wayne tosses an unfair coin one that is biased so that a 18. In alpha testing a new software package, a software engi
head is three times as likely to occur as a tail. How many heads neer finds that the number of defects per 100 lines of code is a
should Wayne expect to see if he tosses the coin 100 times? random variable X with probability distribution:
Find (a) Pr ( X > 1); (b) Pr ( X = 3\X > 2); (c) E(X); and 20. An assembly comprises three electrical components that
(d)Var(X). operate independently. The probabilities that these components
19. In Mario Puzos novel The Godfather, at the wedding recep function according to specifications are 0.95, 0.9, and 0.88. If
tion for his daughter Constanzia, Don Vito Corleone discusses the random variable X counts the number of components that
with his godson Johnny Fontane how he will deal with the movie function according to specifications, determine (a) the proba
mogul Jack Woltz. And in this context he speaks the famous line bility distribution for X; (b) Pr ( X > 2 \ X > 1); (c) E(X)\ and
(d) Var(X).
Ill make him an offer he cant refuse.
21. An urn contains five chips numbered 1,2, 3,4, and 5. When
If we let the random variable X count the number of letters two chips are drawn (without replacement) from the urn, the
and apostrophes in a randomly selected word (from the above random variable X records the higher value. Find E (X) and ax -
quotation) and we assume that each of the eight words has the
same probability of being selected, determine (a) the probability
distribution for X\ (b) E(X)\ and (c) Var(X).
3.8
Summary and Historical Review
In this chapter we introduced some of the fundamentals of set theory, together with certain
relationships to enumeration problems and probability theory.
The algebra of set theory evolved during the nineteenth and early twentieth centuries.
In England, George Peacock (1791-1858) was a pioneer in mathematical reforms and was
among the first, in his Treatise on Algebra, to revolutionize the entire conception of algebra
and arithmetic. His ideas were further developed by Duncan Gregory (1813-1844), William
Rowan Hamilton (1805-1865), and Augustus DeMorgan (1806-1871), who attempted to
remove ambiguity from elementary algebra and cast it in the strict postulational form.
Not until 1854, however, when Boole published his Investigation o f the Laws o f Thought,
was an algebra dealing with sets and logic formalized and the work of Peacock and his
contemporaries extended.
The presentation here is primarily concerned with finite sets. However, the investigation
of infinite sets and their cardinalities has occupied the minds of many mathematicians and
philosophers. (More about this can be found in Appendix 3. However, the reader may
want to learn more about functions as presented in Chapter 5 before looking into the
material in this appendix.) The intuitive approach to set theory was taken until the time of
the Russian-born mathematician Georg Cantor (1845-1918), who defined a set, in 1895,
in a way comparable to the gut feeling we mentioned at the start of Section 3.1. His
definition, however, was one of the obstacles he was never able to entirely remove from his
theory of sets.
In the 1870s, when Cantor was researching trigonometric series and series of real num
bers, he needed a device to compare the sizes of infinite sets of numbers. His treatment of
the infinite as an actuality, on the same level as the finite, was quite revolutionary. Some of
his work was rejected because it proved to be much more abstract than what many mathe
maticians of his time were accustomed to. However, his work won wide enough acceptance
so that by 1890 the theory of sets, both finite and infinite, was considered a branch of
mathematics in its own right.
By the turn of the century the theory was widely accepted, but in 1901 the paradox
now known as Russells paradox (which was discussed in Exercise 27 of Section 3.1)
showed that set theory, as originally proposed, was internally inconsistent. The difficulty
seemed to be in the unrestricted way in which sets could be defined; the idea of a sets being a
3.8 Summary and Historical Review 187
member of itself was considered particularly suspect. In their work Principia Mathematica,
the British mathematicians Lord Bertrand Arthur William Russell (1872-1970) and Alfred
North Whitehead (1861-1947) developed a hierarchy in the theory of sets known as the
theory o f types. This axiomatic set theory, among other twentieth-century formulations,
avoided the Russell paradox. In addition to his work in mathematics, Lord Russell wrote
books dealing with philosophy, physics, and his political views. His remarkable literary
talent was recognized in 1950 when he was awarded the Nobel prize for literature.
The discovery of Russells paradox even though it could be remedied had a pro
found impact on the mathematical community, for many began to wonder if other contra
dictions were still lurking. Then in 1931 the Austrian-born mathematician (and logician)
Kurt Gdel (1906-1978) formulated that under a specified consistency condition, any
188 Chapter 3 Set Theory
sufficiently strong formal axiomatic system must contain a proposition such that neither it
nor its negation is provable and that any consistency proof for the system must use ideas and
methods beyond those of the system itself. And unfortunately, from this we learn that we
cannot establish in a mathematically rigorous manner that there are no contradictions
in mathematics. Yet despite Godels proof, mathematical research continues on in fact,
to the point where the amount of research since 1931 has surpassed that in any other period
in history.
The use of the set membership symbol e (a stylized form of the Greek letter epsilon)
was introduced in 1889 by the Italian mathematician Giuseppe Peano (1858-1932). The
symbol e is an abbreviation for the Greek word e a r i meaning is.
The Venn diagrams of Section 3.2 were introduced by the English logician John Venn
(1834-1923) in 1881. In his book Symbolic Logic, Venn clarified ideas previously devel
oped by his countryman George Boole (1815-1864). Furthermore, Venn contributed to the
development of probability theory as described in the widely read textbook he wrote on
this subject. The Gray code, which we used in Section 3.1 to store the subsets of a finite set
as binary strings, was developed in the 1940s by Frank Gray at the AT&T Bell Laborato
ries. Originally, such codes were used to minimize the effect of errors in the transmission
of digital signals.
If we wish to summarize the importance of the role of set theory in the development of
twentieth-century mathematics, the following quote attributed to the German mathematician
David Hilbert (1862-1943) is worth pondering: No one shall expel us from the paradise
which Cantor has created for us.
In Section 3.1 we mentioned the array of numbers known as Pascals triangle. We could
have introduced this array in Chapter 1 with the binomial theorem, but we waited until we
had some combinatorial identities that we needed to verify how the triangle is constructed.
The array appears in the work of the Chinese algebraist Chu Shi-kie (1303), but its first
appearance in Europe was not until the sixteenth century, on the title page of a book by
Petrus Apianus (1495-1552). Niccolo Tartaglia (1499-1559) used the triangle in computing
powers of (x + y). Because of his work on the properties and applications of this triangle,
the array has been named in honor of the French mathematician Blaise Pascal (1623-1662).
Although probability theory originated with games of chance and enumeration problems,
we included it here because set theory has evolved as the exact medium needed to state
and solve problems in this important contemporary area of applied mathematics. In the
decade following 1660, probability entered European thought as a way of understanding
stable frequencies in random processes. Ideas, which exemplify this consideration, were put
forth by Blaise Pascal, and these led to the first systematic treatise on probability, written in
1657 by Christian Huygens (1629-1695). In 1812 Pierre-Simon de Laplace (1749-1827)
collected all the ideas developed on probability theory at that time starting with the def
inition in which each individual outcome is equally likely and published them in his
Analytic Theory o f Probability. Among other ideas, this text includes the Central Limit
Theorem a fundamental result at the heart of hypothesis testing (in statistics). Along
with Pierre-Simon de Laplace, Thomas Bayes (1702-1761) also showed how to determine
probabilities by examining certain empirical data. Bayes Theorem honors the name of this
English Presbyterian minister and mathematician. Chebyshevs Inequality (of Section 3.7)
is named for the Russian mathematician Pafnuty Lvovich Chebyshev (1821-1894), who
may be better remembered for his work in number theory and interest in mechanics. Finally,
the axiomatic approach to probability was first given in 1933 by the Russian mathemati
cian Andrei Nikolayevich Kolmogorov (1903-1987) in his monograph Grundbegriffe der
Wahrscheinlichkeitsrechnung (Foundations o f the Theory o f Probability).
Supplementary Exercises 189
More on the history and development of set theory can be found in Chapter 26 of
C. B. Boyer [1]. Formal developments of set theory, including results on infinite sets, can
be found in H. B. Enderton [3], P. R. Halmos [4], J. M. Henle [5], and R C. Suppes [8]. An
interesting history of the origins of probability and statistical ideas, up to the Newtonian
era, can be found in F. N. David [2]. A more contemporary coverage is given in the text
by V. J. Katz [6]. Chapters 1 and 2 of J. J. Kinney [7] are an excellent source for those
interested in learning more about discrete probability.
REFERENCES
a) A C = B C = ^A = B
SUPPLEM ENTARY EXERCISES b) [(A fl C = B fl C) A (A - C = B - C)] = A = B
c) [(A U C = B U C) A (A - C = B - C)] = A = B
1. Let A, B, C c U. Prove that (A B) c C if and only if
(A-C)CB. 4. a ) For positive integers m, n, r, withr < min {m, n}, show
that
2. Give a combinatorial argument to show that for integers
n, r with n > r > 2,
(m-\-n\ {m \in\ (m \( n \ (m \( n \
) = ( o ) ( J +( J C - , ) + ( 2 - 2)
C; M : K : . K : 2>
13
2 8
7
6
5
4
r
b) For n a positive integer, show that rows of the table for which this is true rows 1, 2, and 4, as
indicated by the arrows. For these rows, the columns for B and
A U B are exactly the same, so this membership table shows
that A C B ^ A U B ^ B .
5. a ) In how many ways can a teacher divide a group of seven
students into two teams each containing at least one stu Table 3.7
9. Let A, B , C c U. Prove that dom, what is the probability that the two Os remain together in
the arrangement?
(A D B) U C = A D (B U C) if and only if C c A.
1 7 . At a high school science fair, 34 students received awards
10. Let U be a given universe with A, B c U, |A fl 5 | = 3, for scientific projects. Fourteen awards were given for projects
|A U | = 8 , and |U | = 12. in biology, 13 in chemistry, and 21 in physics. If three students
a) How many subsets C c U satisfy A D B c C c received awards in all three subject areas, how many received
A U 5 ? How many of these subsets C contain an even awards for exactly (a) one subject area? (b) two subject areas?
number of elements? 1 8 . Fifty students, each with 75 jzf, visited the arcade of Example
b) How many subsets D c U satisfy A U 5 C D C 3.27. Seventeen of the students played each of the three com
A U B ? How many of these subsets D contain an even puter games, and 37 of them played at least two of them. No
number of elements? student played any other game at the arcade, nor did any student
11. Let U = R and let the index set I = Q + . For each q e Q + ,
play a given game more than once. Each game costs 25jzfto play,
let A q = [0, 2 q] and Bq = (0, 3q]. Determine and the total proceeds from the student visit were $24.25. How
many of these students preferred to watch and played none of
a) A 7/3 b) A 3 A B 4
the games?
c> u A q d> n B, 1 9 . In how many ways can 15 laboratory assistants be assigned
qel qel
12. For a universe li and sets A, B c prove that to work on one, two, or three different experiments so that each
experiment has at least one person spending some time on it?
2l) A A B = B A A b) A A A = U
20 . Professor Diane gave her chemistry class a test consisting
c) A A U = A
of three questions. There are 21 students in her class, and ev
d) A A 0 = A, so 0 is the identity for A, as well as for U ery student answered at least one question. Five students did
1 3 . Consider the membership table (Table 3.7). If we are given not answer the first question, seven failed to answer the second
the condition that A c B, then we need consider only those question, and six did not answer the third question. If nine stu
Supplementary Exercises 191
dents answered all three questions, how many answered exactly the plane to land safely, all three landing gears (the nose and
one question? both wing landing gears) must have at least one good tire. What
21 .Let U be a given universe with A, B c U, A D B = 0, is the probability that the jet will be able to land safely even on
|A| = 12, and | | = 10. If seven elements are selected from a hard landing?
A U B, what is the probability the selection contains four 32 .Let if be the sample space for an experiment % and let
elements from A and three from B? A, B be events that is, A, B c if. Prove that Pr( A fl B) >
22. For a finite set A of integers, let a (A) denote the sum of Pr(A) + P r ( B ) 1. (This result is known as Bonferronis
the elements of A. Then if U is a finite universe taken from Inequality.)
Z+, HAeoj>(6U)or(A) denotes the sum of all elements of all sub 33. The exit door at the end of a hallway is open half of the time.
sets of U. Determine HAe(<ni)cr(A) for On a table by the entrance to this hallway is a box containing 10
a) U = {1, 2, 3} b) U = {1, 2, 3, 4} keys, but only one of these keys opens the exit door at the end
of the hallway. Upon entering the hallway Mario selects two of
c) U = {1, 2, 3, 4, 5} d) U = {1, 2, 3, . . . , nj
the keys from the box. What is the probability she will be able
e) ll = {a\, a2, a2, . . . , an}, where to leave the hallway via the exit door, without returning to the
5 = ax + a2 + a3 H--------h an box for more keys?
23. a) In chess, the king can move one position in any direc 3 4 . Dustin tosses a fair coin eight times. Given that his first and
tion. Assuming that the king is moved only in a forward last outcomes are the same, what is the probability he tossed
manner (one position up, to the right, or diagonally north five heads and three tails?
east), along how many different paths can a king be moved
35. The probability Coach Sears basketball team wins any
from the lower-left comer position to the upper-right corner
given game is 0.8, regardless of any prior win or loss. If her
position on the standard 8 X 8 chessboard?
team plays five games, what is the probability it wins more
b) For the paths in part (a), what is the probability that a games than it loses?
path contains (i) exactly two diagonal moves? (ii) exactly
36. Suppose that the number of boxes of cereal packaged each
two diagonal moves that are consecutive? (iii) an even num
day at a certain packaging plant is a random variable call it
ber of diagonal moves?
X w it h ( X ) = 20,000 boxes and Var(X) = 40,000 boxes2.
24. Let A, B c R, where A = {x \ x 2 l x - 12} and B = Use Chebyshevs Inequality to find a lower bound on the prob
{.x\x 2 x = 6}. Determine A U f i and A H B. ability that the plant will package between 19,000 and 21,000
25. Let A, B c R, where A = {x \ x 2 l x < 12} and B = boxes of cereal on a particular day.
{x\x 2 x < 6}. Determine A U f i and A H B. 37. Find the probability of getting one head (exactly) two times
26. Four torpedoes, whose probabilities of destroying an en when three fair coins are tossed four times.
emy ship are 0.75, 0.80, 0.85, and 0.90, are fired at such a 38. Devon has a bag containing 22 poker chips eight red,
vessel. Assuming the torpedoes operate independently, what is eight white, and six blue. Aileen reaches in and withdraws
the probability the enemy ship is destroyed? three of the chips, without replacement. Find the probability
27. Travis tosses a fair coin twice. Then he tosses a biased coin, that Aileen has selected (a) no blue chips; (b) one chip of each
one where the probability of a head is 3/4, four times. What is color; or (c) at least two red chips.
the probability Traviss six tosses result in five heads and one 39. Let A be a random variable with probability distribution
tail?
28. Let if be the sample space for an experiment %, with events [ c(x2 + 4), x = 0, 1, 2, 3, 4
Pr(X = x ) = \
A, B c i f . Prove that I 0, otherwise,
Pr(A) + Pr(B) - 1
Pr( A\ B) > -------- ------ . where c is a constant. Determine (a) the value of c;
Pr(B)
(b) Pr ( X > 1); (c) Pr ( X = 3|X > 2); (d) E(X)\ and
29. Let A, B , C be independent events taken from a sample (e)Var(X).
space if. Prove that the events A and B U C are independent. A dozen urns each contain four red marbles and seven green
4 0 .
30. What is the minimum number of times we must toss a fair ones. (All 132 marbles are of the same size.) If a dozen students
coin so that the probability that we get at least two heads is at each select a different urn and then draw (with replacement)
least 0.95? five marbles, what is the probability that at least one student
31. Alarge jet aircraft has two wheels per landing gear for added draws at least one red marble?
safety. The tires are rated so that even with a hard landing the Maureen draws five cards from a standard deck: the 6 of di
4 1 .
probability of any single tire blowing out is only 0.10. (a) What amonds, 7 of diamonds, 8 of diamonds, jack of hearts, and king
is the probability that a landing gear (with two tires) will survive of spades. She discards the jack and king and then draws two
even a hard landing with at least one good tire? (b) In order for cards from the remaining 47. What is the probability Maureen
192 Chapter 3 Set Theory
finishes with (a) a straight flush; (b) a flush (but not a straight 44. A fair die is rolled three times and the random variable X
flush); and (c) a straight (but not a straight flush)? records the number of different outcomes that result. For exam
42. In the game of pinochle the deck consists of 48 cards two ple, if two 5 s and one 4 are rolled, then X records two differ
each of the 9,10, jack, queen, king, and ace for each of the four ent outcomes. Determine (a) the probability distribution for X\
suits. There are four players and each is dealt 12 cards. What is ( b ) ( X ) ; a n d (c)Var(X).
the probability a given player is dealt four kings (one of each 45. When a coin is tossed three times, for the outcome HHT
suit), four queens (one of each suit), and four other cards none we say that two runs have occurred namely, HH and T. Like
of which is a king or queen? (Such a hand is referred to as a wise, for the outcome THT we find three runs: T, H, and T.
bare roundhouse.) (The notion of a run was first introduced in Example 1.41.)
43. A grab bag contains one chip with the number 1, two chips Now suppose a biased coin, with Pr(H) = 3/4, is tossed three
each with the number 2, three chips each with the number times and the random variable X counts the number of runs
3, . . . , and n chips each with the number n, where n e Z+ . that result. Determine (a) the probability distribution for X;
All chips are of the same size, those numbered 1 to m are red, (b) E (X )\and (c) ax .
and those numbered m + 1 to n are blue, where m e Z+ and
m < n. If Casey draws one chip, what is the probability it is the
chip with 1 on it, given that the chip is red?