Your bag is empty
Don't miss out on great deals! Start shopping or Sign in to view products added.
Shop What's New Sign inSolution Manual For Discrete Mathematics With Applications, 5th Edition
Preview Extract
Instructorโs Manual: Chapter 2
1
Chapter 2: The Logic of Compound Statements
The ability to reason using the principles of logic is essential for solving problems in abstract mathematics and computer science and for understanding the reasoning used in mathematical proof and
disproof. Because a signi๏ฌcant number of students who come to college have had limited opportunity to develop this ability, a primary aim of Chapters 2 and 3 is to help students develop an inner
voice that speaks with logical precision. Consequently, the various rules used in logical reasoning are
developed both symbolically and in the context of their somewhat limited but very important use
in everyday language. Exercise sets for Sections 2.1โ2.3 and 3.1โ3.4 contain sentences for students
to negate, write the contrapositive for, and so forth. Virtually all students bene๏ฌt from doing these
exercises. Another aim of Chapters 2 and 3 is to teach students the rudiments of symbolic logic as
a foundation for a variety of upper-division courses. Symbolic logic is used in, among others, the
study of digital logic circuits, relational databases, arti๏ฌcial intelligence, and program veri๏ฌcation.
Suggestions
1. In Section 2.1 a surprising number of students apply De Morganโs law to write the negation of,
for example, โ1 3.โ You may ๏ฌnd that it takes some e๏ฌort to teach them to
avoid making this mistake.
2. In Sections 2.1 and 2.4, students have more di๏ฌculty than you might expect simplifying statement
forms and circuits. Only through trial and error can you learn the extent to which this is the case
at your institution. If it is, you might either assign only the easier exercises or build in extra time to
teach students how to do the more complicated ones. Discussion of simpli๏ฌcation techniques occurs
again in Chapter 6 in the context of set theory. At this later point in the course most students are
able to deal with it successfully.
3. In ordinary English, the phrase โonly ifโ is often used as a synonym for โif and only if.โ But it
is possible to ๏ฌnd informal sentences for which the intuitive interpretation is the same as the logical
de๏ฌnition. It is helpful to give examples of such statements when you introduce the logical de๏ฌnition.
For instance, it is not hard to get students to agree that โThe team will win the championship only
if it wins the semi๏ฌnal gameโ means the same as โIf the team does not win the semi๏ฌnal game then
it will not win the championship.โ Once students see this, you can suggest that they remember this
example when they encounter more abstract โonly ifโstatements.
Through guided discussion, students also come to agree that the statement โWinning the semi๏ฌnal game is a necessary condition for winning the championshipโ translates to โIf the team does
not win the semi๏ฌnal game then it will not win the championship.โ They can be encouraged to use
this (or a similar statement) as a reference to help develop intuition for general statements of the
form โA is a necessary condition for B.โ
With students who have weaker backgrounds, you may ๏ฌnd yourself tying up excessive amounts
of class time discussing โonly ifโ and โnecessary and su๏ฌcient conditions.โ You might just assign
the easier exercises, or you might assign exercises on these topics to be done for extra credit (putting
corresponding extra credit problems on exams) and use the results to help distinguish A from B
students. It is probably best not to omit these topics altogether, though, because the language of
โonly ifโ and โnecessary and su๏ฌcient conditionsโ is a standard part of the technical vocabulary of
textbooks used in upper-division courses, as well as occurring regularly in non-mathematical writing.
4. In Section 2.3, many students mistakenly conclude that an argument is valid if, when they
compute the truth table, they ๏ฌnd a single row in which both the premises and the conclusion are
true. The source of studentsโ di๏ฌculty appears to be their tendency to ignore quanti๏ฌcation and to
misinterpret if-then statements as โandโ statements. Since the de๏ฌnition of validity includes both
a universal quanti๏ฌer and if-then, it is helpful to go back over the de๏ฌnition and the procedures for
testing for validity and invalidity after discussing the general topic of universal conditional statements
2
Solutions for Exercises: The Logic of Compound Statements
in Section 3.1. As a practical measure to help students assess validity and invalidity correctly, the
๏ฌrst example in Section 2.3 is of an invalid argument whose truth table has eight rows, several
of which have true premises and a true conclusion. To further focus studentsโ attention on the
situations where all the premises are true, the truth values for the conclusions of arguments are
omitted when at least one premise is false.
5. In Section 2.3, you might suggest that students just familiarize themselves with, but not memorize,
the various forms of valid arguments covered in Section 2.3. It is wise, however, to have them learn
the terms modus ponens and modus tollens (because these are used in some upper-division computer
science courses) and converse and inverse errors (because these errors are so common).
Section 2.1
1. Common form:
Therefore,
If p then q.
p
q
(a + 2b)(a2 โ b) can be written in pre๏ฌx notation. All algebraic expressions can be written in
pre๏ฌx notation.
2. Common form:
Therefore,
If p then q.
โผq
โผp
All prime numbers are odd. 2 is odd
3. Common form:
Therefore,
pโจq
โผp
q
My mind is shot. Logic is confusing.
4. Common form:
Therefore,
If p then q.
If q then r.
If p then r.
Has 4 vertices and 6 edges. Is complete; Any two of its vertices can be joined by a path
5. a. It is a statement because it is a true sentence. 1,024 is a perfect square because 1,024 = 322 ,
and the next smaller perfect square is 312 = 961, which has fewer than four digits.
b. The truth or falsity of this sentence depends on the reference for the pronoun โshe.โ
Considered on its own, the sentence cannot be said to be either true or false, and so it is not
a statement.
c. This sentence is false; hence it is a statement.
d. This is not a statement because its truth or falsity depends on the value of x.
6. a. s โง i
b. โผs โง โผi
7. m โง โผ c
8. a. (h โง w) โง โผs
b. โผ w โง (h โง s)
d. (โผw โง โผs) โง h
c. โผ wโง โผ h โง โผ s
e. wโง โผ (h โง s) (w โง (โผ h โจ โผ s) is also acceptable)
9. a. p โจ q
b. r โง p
c. r โง ( p โจ q)
10. a. p โง q โง r
b. p โง โผ q
c. p โง (โผq โจ โผr)
d. (โผ p โง q) โง โผ r
e. โผ p โจ (q โง r)
Instructorโs Manual: Section 2.1
3
11. Inclusive or. For instance, a team could win the playo๏ฌ by winning games 1, 3, and 4 and
losing game 2. Such an outcome would satisfy both conditions.
12.
p
T
T
F
F
q
T
F
T
F
โผp
F
F
T
T
โผp โง q
F
F
T
F
p
q
pโงq
pโจq
โผ (p โง q)
โผ (p โง q) โจ (p โจ q)
T
T
F
F
T
F
T
F
T
F
F
F
T
T
T
F
F
T
T
T
T
T
T
T
13.
14.
p
q
r
qโงr
p โง (q โง r)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
T
F
F
F
T
F
F
F
T
F
F
F
F
F
F
F
p
q
r
โผq
โผqโจr
p โง (โผ q โจ r)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
T
T
F
F
T
T
T
F
T
T
T
F
T
T
T
F
T
T
F
F
F
F
p
q
pโงq
p โจ (p โง q)
p
T
T
F
F
T
F
T
F
T
F
F
F
T
T
F
F
T
T
F
F
}
15.
16.
|
{z
same truth values
The truth table shows that p โจ (p โง q) and p always have the same truth values. Thus they
are logically equivalent. (This proves one of the absorption laws.)
4
Solutions for Exercises: The Logic of Compound Statements
17.
p
T
T
F
F
q
T
F
T
F
pโงq
T
F
F
F
โผp
F
F
T
T
โผq
F
T
F
T
โผ (p โง q)
F
T
T
T
|
โผ pโง โผ q
F
F
F
T
{z
โ
โ
}
di๏ฌerent truth values in rows 2 and 3
The truth table shows that โผ (p โง q) and โผ p โง โผ q do not always have the same truth values.
Therefore they are not logically equivalent.
18.
p
t
pโจt
T
F
T
T
|
T
T
{z
}
same truth values
The truth table shows that p โจ t and t always have the same truth values. Thus they are
logically equivalent. (This proves one of the universal bound laws.)
19.
p
t
p โงt
p
T
F
T
T
T
F
T
F
|
{z
}
same truth values
The truth table shows that p โง t and p always have the same truth values. Thus they are
logically equivalent. This proves the identity law for โง.
20.
p
T
F
p โงc
F
F
c
F
F
|
p โจc
T
F
{z
โ
}
di๏ฌerent truth values in row 1
The truth table shows that p โง c and p โจ c do not always have the same truth values. Thus
they are not logically equivalent.
21.
p
q
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
p
q
T
F
T
F
T
F
T
F
r
pโงq
q โงr
(p โง q) โง r
p โง (q โง r )
T
T
F
F
F
F
F
F
T
F
F
F
T
F
F
F
T
F
F
F
F
F
F
F
T
F
F
F
F
F
F
F
|
{z
}
same truth values
The truth table shows that (p โง q) โง r and p โง (q โง r) always have the same truth values. Thus
they are logically equivalent. (This proves the associative law for โง.)
Instructorโs Manual: Section 2.1
22.
p
q
r
qโจr
pโงq
pโงr
p โง (q โจ r)
(p โง q) โจ (p โง r)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
T
T
T
F
T
T
T
F
T
T
F
F
F
F
F
F
T
F
T
F
F
F
F
F
T
T
T
F
F
F
F
F
T
T
T
F
F
F
F
F
|
{z
5
}
same truth values
The truth table shows that p โง (q โจ r) and (p โง q) โจ (p โง r) always have the same truth values.
Therefore they are logically equivalent. This proves the distributive law for โง over โจ.
23.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
pโงq
T
T
F
F
F
F
F
F
q โจr
T
T
T
F
T
T
T
F
(p โง q) โจ r
T
T
T
F
T
F
T
F
|
p โง (q โจ r )
T
T
T
F
F
F
F
F
{z
โ
โ
}
di๏ฌerent truth values in rows 5 and 7
The truth table shows that (p โง q) โจ r and p โง (q โจ r) have di๏ฌerent truth values in rows 5 and
7. Thus they are not logically equivalent. (This proves that parentheses are needed with โง
and โจ.)
24.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
pโจq
T
T
T
T
T
T
F
F
pโงr
T
F
T
F
F
F
F
F
(p โจ q) โจ (p โง r)
T
T
T
T
T
T
F
F
|
(p โจ q) โง r
T
F
T
F
T
F
F
F
{z
โ
โ
โ
}
di๏ฌerent truth values in rows 2, 3, and 6
The truth table shows that (p โจ q) โจ (p โง r) and (p โจ q) โง r have di๏ฌerent truth values in rows
2, 3, and 6. Hence they are not logically equivalent.
25. Hal is not a math major or Halโs sister is not a computer science major.
26. Sam is not an orange belt or Kate is not a red belt.
27. The connector is not loose and the machine is not unplugged.
28. The train is not late and my watch is not fast.
6
Solutions for Exercises: The Logic of Compound Statements
29. This computer program does not have a logical error in the ๏ฌrst ten lines and it is not being
run with an incomplete data set.
30. The dollar is not at an all-time high or the stock market is not at a record low.
31. a. 01, 02, 11, 12
b. 21, 22
c. 11, 10, 21, 20
32. โ2 โฅ x or x โฅ 7
33. โ10 โฅ x or x โฅ 2
34. 2 โค x โค 5
35. x > โ1 and x โค 1
36. 1 โค x or x < โ3
37. 0 โค x or x 500) and num instock โฅ 200.
39. The statementโs logical form is (p โง q) โจ ((r โง s) โง t), so its negation has the form
โผ ((p โง q) โจ ((r โง s) โง t))
โก
โก
โก
โผ (p โง q) โง โผ ((r โง s) โง t))
(โผ p โจ โผ q) โง (โผ (r โง s)โจ โผ t))
(โผ p โจ โผ q) โง ((โผ r โจ โผ s) โจ โผ t)).
Thus a negation is (num orders โฅ 50 or num instock โค 300) and ((50 > num orders or
num orders โฅ 75) or num instock โค 500).
40.
p
q
โผp
โผq
pโงq
pโงโผq
โผ p โจ (pโง โผ q)
(p โง q) โจ (โผ p โจ (p โง โผ q))
T
T
F
F
T
F
T
F
F
F
T
T
F
T
F
T
T
F
F
F
F
T
F
F
F
T
T
T
T
T
T
T
Since all the truth values of (p โง q) โจ (โผp โจ (p โง โผq)) are T, (p โง q) โจ (โผp โจ (p โง โผq)) is a
tautology.
41.
p
q
โผp
โผq
pโงโผq
โผpโจq
(p โง โผ q)(p โจ q)
T
T
F
F
T
F
T
F
F
F
T
T
F
T
F
T
F
T
F
F
T
F
T
T
F
F
F
F
Since all the truth values of (p โง โผq) โง (โผp โจ q) are F, (p โง โผq) โง (โผp โจ q) is a contradiction.
Instructorโs Manual: Section 2.1
42.
7
p
q
r
โผp
โผq
โผpโงq
qโงr
((โผ p โง q) โง (q โง r))
((โผ p โง q) โง (q โง r))โง โผ q
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
F
F
T
T
T
T
F
F
T
T
F
F
T
T
F
F
F
F
T
T
F
F
T
F
F
F
T
F
F
F
F
F
F
F
T
F
F
F
F
F
F
F
F
F
F
F
{z
all F โฒ s
|
}
Since all the truth values of ((โผ p โง q) โง (q โง r))โง โผ q are F , ((โผ p โง q) โง (q โง r))โง โผ q is a
contradiction.
43.
p
q
โผp
โผq
โผpโจq
pโง โผ q
(โผ p โจ q) โจ (p โง โผ q)
T
T
F
F
T
F
T
F
F
F
T
T
F
T
F
T
T
F
T
T
F
T
F
F
T
T
T
T
{z
all T โฒ s
|
}
44. a. No real numbers satisfy this inequality
b. No real numbers satisfy this inequality.
45. Let b be โBob is a double math and computer science major,โ m be โAnn is a math major,โ
and a be โAnn is a double math and computer science major.โ Then the two statements can
be symbolized as follows: a. (b โง m)โง โผ a and b. โผ (b โง a) โง (m โง b). Note: The entries
in the truth table assume that a person who is a double math and computer science major is
also a math major and a computer science major.
b
T
T
T
T
F
F
F
F
m
T
T
F
F
T
T
F
F
a
T
F
T
F
T
F
T
F
โผa
F
T
F
T
F
T
F
T
bโงm
T
F
T
F
F
F
F
F
mโงb
T
T
F
F
F
F
F
F
bโงa
T
F
T
F
F
F
F
F
โผ (b โง a)
F
T
F
T
T
T
T
T
(b โง m)โง โผ a
โผ (b โง a) โง (m โง b)
F
F
T
T
F
F
F
F
F
F
F
F
F
F
F
F
|
{z
}
same truth values
The truth table shows that (b โง m)โง โผ a and โผ (b โง a) โง (m โง b) always have the same truth
values. Hence they are logically equivalent.
46. a. Solution 1: Construct a truth table for p โ p using the truth values for exclusive or.
p
T
F
pโp
F
F
because an exclusive or statement is false when both components are true and when both
components are false, and the two components in p โ p are both p.
Since all its truth values are false, p โ p โก c, a contradiction.
8
Solutions for Exercises: The Logic of Compound Statements
Solution 2: Replace q by p in the logical equivalence p โ q โก (p โจ q) โง โผ(p โง q), and simplify
the result.
p โ p โก (p โจ p) โง โผ(p โง p) by de๏ฌnition of โ
โก p โง โผp
by the identity laws
โกc
by the negation law for โง
b. Yes.
p
q
r
pโq
qโr
(p โ q) โ r
p โ (q โ r)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
T
T
T
T
F
F
F
T
T
F
F
T
T
F
T
F
F
T
F
T
T
F
T
F
F
T
F
T
T
F
|
{z
same truth values
}
The truth table shows that (p โ q) โ r and p โ (q โ r) always have the same truth values. So
they are logically equivalent.
c. Yes.
p
q
r
pโq
pโงr
qโงr
(p โ q) โง r
(p โง r) โ (q โง r)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
T
T
T
T
F
F
T
F
T
F
F
F
F
F
T
F
F
F
T
F
F
F
F
F
T
F
T
F
F
F
F
F
T
F
T
F
F
F
|
{z
same truth values
}
The truth table shows that (p โ q) โง r and (p โง r) โ (q โง r) always have the same truth values.
So they are logically equivalent.
47. There is a famous story about a philosopher who once gave a talk in which he observed that
whereas in English and many other languages a double negative is equivalent to a positive,
there is no language in which a double positive is equivalent to a negative. To this, another
philosopher, Sidney Morgenbesser, responded sarcastically, โYeah, yeah.โ
[Strictly speaking, sarcasm functions like negation. When spoken sarcastically, the words โYeah,
yeahโ are not a true double positive; they just mean โno.โ]
48.
a. the distributive law
c. the negation law for โจ
49.
a. the commutative law for โจ
c. the negation law for โง
b. the commutative law for โจ
d. the identity law for โง
50. (p โง โผq) โจ p โก p โจ (p โง โผq)
โกp
51. Solution 1 : p โง (โผ q โจ p)
โก
โก
b. the distributive law
d. the identity law for โจ
by the commutative law for โจ
by the absorption law (with โผq in place of q)
p โง (p โจ โผ q)
p
commutative law for โจ
absorption law
Instructorโs Manual: Section 2.2
52.
Solution 2 : p โง (โผ q โจ p)
โก
โก
โก
(p โง โผ q) โจ (p โง p)
(p โง โผ q) โจ p
p
โผ (p โจ โผ q) โจ (โผ p โง โผ q)
โก
โก
โก
โก
โก
(โผ p โง โผ (โผ q)) โจ (โผ p โง โผ q)
(โผ p โง q) โจ (โผ p โง โผ q)
โผ p โง (qโจ โผ q)
โผ pโง t
โผp
53. โผ((โผp โง q) โจ (โผp โง โผq)) โจ (p โง q)
54.
(p โง (โผ (โผ p โจ q))) โจ (p โง q)
โก
โก
โก
โก
โก
โก
โก
โก
โก
โก
โก
โก
โก
distributive law
identity law for โง
by exercise 50.
De Morganโs law
double negative law
distributive law
negation law for โจ
identity law for โง
โผ[โผp โง (q โจ โผq)] โจ (p โง q)
โผ(โผp โง t) โจ (p โง q)
โผ(โผp) โจ (p โง q)
p โจ (p โง q)
p
(p โง (โผ (โผ p)โง โผ q)) โจ (p โง q)
(p โง (pโง โผ q)) โจ (p โง q)
((p โง p)โง โผ q)) โจ (p โง q)
(p โง โผ q)) โจ (p โง q)
p โง (โผ q โจ q)
p โง (qโจ โผ q)
pโง t
p
by the distributive law
by the negation law for โจ
by the identity law for โง
by the double negative law
by the absorption law
De Morganโs law
double negative law
associative law for โง
idempotent law for โง
distributive law
commutative law for โจ
negation law for โจ
identity law for โง
Section 2.2
1. If this loop does not contain a stop or a go to, then it will repeat exactly N times.
2. If I catch the 8:05 bus, then I am on time for work.
3. If you do not freeze, then Iโll shoot.
4. If you donโt ๏ฌx my ceiling, then I wonโt pay my rent.
5.
p
T
T
F
F
q
T
F
T
F
โผp
F
F
T
T
โผq
F
T
F
T
p
q
โผp
โผpโงq
pโจq
(p โจ q) โจ (โผ p โง q)
(p โจ q) โจ (โผ p โง q) โ q
T
T
F
F
T
F
T
F
F
F
T
T
F
F
T
F
T
T
T
F
T
T
T
F
T
F
T
T
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
6.
7.
r
T
F
T
F
T
F
T
F
โผq
F
F
T
T
F
F
T
T
โผpโจq
T
F
T
T
p โงโผq
F
F
T
T
F
F
F
F
โผ p โจ q โโผ q
F
T
F
T
p โงโผq โr
T
T
T
F
T
T
T
T
9
10
Solutions for Exercises: The Logic of Compound Statements
8.
p
q
r
โผp
โผpโจq
โผpโจq โr
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
F
F
T
T
T
T
T
T
F
F
T
T
T
T
T
F
T
T
T
F
T
F
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
โผr
F
T
F
T
F
T
F
T
p โงโผr
F
T
F
T
F
F
F
F
p
q
r
pโr
qโr
(p โ r) โ (q โ r)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
T
F
T
F
T
T
T
T
T
F
T
T
T
F
T
T
T
T
T
F
T
F
T
T
9.
10.
11.
q โงr
T
T
T
F
T
T
T
F
p โงโผr โq โจr
F
T
F
F
F
F
F
T
p
q
r
qโr
p โ (q โ r)
pโงq
pโงq โr
(p โ (q โ r)) โ (p โง q โ r)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
T
F
T
T
T
F
T
T
T
F
T
T
T
T
T
T
T
T
F
F
F
F
F
F
T
F
T
T
T
T
T
T
T
T
T
T
T
T
T
T
12. If x > 2 then x2 > 4, and if x 4.
13. a.
p
q
โผp
pโq
โผp โงq
T
T
F
F
T
F
T
F
F
T
F
T
T
F
T
T
T
F
T
T
|
{z
}
same truth values
Instructorโs Manual: Section 2.2
11
The truth table shows that p โ q and โผp โจ q always have the same truth values. Hence they
are logically equivalent.
b.
p
q
โผq
pโq
โผ (p โ q)
pโงโผq
T
T
F
F
T
F
T
F
F
T
F
T
T
F
T
T
F
T
F
F
F
T
F
F
|
{z
}
same truth values
The truth table shows that โผ (p โ q) and p โง โผ q always have the same truth values. Hence
they are logically equivalent.
14. a.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
โผq
F
F
T
T
F
F
T
T
โผr
F
T
F
T
F
T
F
T
qโจr
T
T
T
F
T
T
T
F
pโง โผ q
F
F
T
T
F
F
F
F
pโง โผ r
F
T
F
T
F
F
F
F
pโqโจr
T
T
T
F
T
T
T
T
|
pโงโผqโr pโงโผrโq
T
T
T
T
T
T
F
F
T
T
T
T
T
T
T
T
{z
}
same truth values
The truth table shows that the three statement forms p โ q โจ r, p โง โผ q โ r, and p โง โผ r โ q
always have the same truth values. Thus they are all logically equivalent.
b. If n is prime and n is not odd, then n is 2.
And: If n is prime and n is not 2, then n is odd.
15.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
qโr
T
F
T
T
T
F
T
T
pโq
T
T
F
F
T
T
T
T
p โ (q โ r) (p โ q) โ r
T
T
F
F
T
T
T
T
T
T
T
F
T
F
T
F
|
{z
}
โ
โ
โ
di๏ฌerent truth values
The truth table shows that p โ (q โ r) and (p โ q) โ r do not always have the same truth
values. (They di๏ฌer for the combinations of truth values for p, q, and r shown in rows 6, 7,
and 8.) Therefore they are not logically equivalent.
16. Let p represent โYou paid full priceโ and q represent โYou didnโt buy it at Crown Books.โ
Thus, โIf you paid full price, you didnโt buy it at Crown Booksโ has the form p โ q. And
โYou didnโt buy it at Crown Books or you paid full priceโ has the form q โจ p.
12
Solutions for Exercises: The Logic of Compound Statements
p q
T T
T F
F T
F F
pโq
T
F
T
T
|
q โจp
T
T
T
F
{z
โ
โ
}
di๏ฌerent truth values
These two statements are not logically equivalent because their forms have di๏ฌerent truth
values in rows 2 and 4.
(An alternative representation for the forms of the two statements is p โ โผq and โผq โจ p. In
this case, the truth values di๏ฌer in rows 1 and 3.)
17. Let p represent โ2 is a factor of n,โ q represent โ3 is a factor of n,โ and r represent โ6 is a
factor of n.โ The statement โIf 2 is a factor of n and 3 is a factor of n, then 6 is a factor of nโ
has the form p โง q โ r. And the statement โ2 is not a factor of n or 3 is a not a factor of n
or 6 is a factor of nโ has the form โผ p โจ โผ q โจ r.
p
q
r
โผp
โผq
pโงq
pโงq โr
โผ pโจ โผ q โจ r
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
F
F
T
T
T
T
T
T
F
F
T
T
F
F
T
T
F
F
F
F
F
F
T
F
T
T
T
T
T
T
T
F
T
T
T
T
T
T
|
{z
}
same truth values
The truth table shows that p โง q โ r and โผ p โจ โผ q โจ r always have the same truth values.
Therefore they are logically equivalent.
18. Part 1 : Let p represent โIt walks like a duck,โ q represent โIt talks like a duck,โ and r represent
โIt is a duck.โ The statement โIf it walks like a duck and it talks like a duck, then it is a duckโ
has the form p โง q โ r. And the statement โEither it does not walk like a duck or it does not
talk like a duck or it is a duckโ has the form โผ p โจ โผ q โจ r.
p
q
r
โผp
โผq
p โงq
โผ pโจ โผ q
p โงq โr
(โผ p โจ โผ q) โจ r
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
F
F
T
T
T
T
F
F
T
T
F
F
T
T
T
T
F
F
F
F
F
F
F
F
T
T
T
T
T
T
T
F
T
T
T
T
T
T
T
F
T
T
T
T
T
T
|
{z
}
same truth values
The truth table shows that p โง q โ r and (โผ p โจ โผ q) โจ r always have the same truth values.
Thus the following statements are logically equivalent:โIf it walks like a duck and it talks like
a duck, then it is a duckโ and โEither it does not walk like a duck or it does not talk like a
duck or it is a duck.โ
Instructorโs Manual: Section 2.2
13
Part 2 : The statement โIf it does not walk like a duck and it does not talk like a duck then
it is not a duckโ has the form โผ p โง โผ q โโผ r.
p
q
r
โผp
โผq
โผr
p โงq
โผ pโง โผ q
p โงq โr
(โผ p โง โผ q) โโผ r
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
F
F
T
T
T
T
F
F
T
T
F
F
T
T
F
T
F
T
F
T
F
T
T
T
F
F
F
F
F
F
F
F
F
F
F
F
T
T
T
F
T
T
T
T
T
T
T
T
T
T
T
T
F
T
|
{z
di๏ฌerent truth values
โ
โ
}
The truth table shows that p โง q โ r and (โผ p โง โผ q) โโผ r do not always have the same
truth values. (They di๏ฌer for the combinations of truth values of p, q, and r shown in rows 2
and 7.) Thus they are not logically equivalent, and so the statement โIf it walks like a duck
and it talks like a duck, then it is a duckโ is not logically equivalent to the statement โIf it
does not walk like a duck and it does not talk like a duck then it is not a duck.โ In addition,
because of the logical equivalence shown in Part 1, we can also conclude that the following
two statements are not logically equivalent: โEither it does not walk like a duck or it does not
talk like a duck or it is a duckโ and โIf it does not walk like a duck and it does not talk like a
duck then it is not a duck.โ
19. False. The negation of an if-then statement is not an if-then statement. It is an and statement.
20. a. Negation: P is a square and P is not a rectangle.
b. Negation: Today is New Yearโs Eve and tomorrow is not January.
c. Negation: The decimal expansion of r is terminating and r is not rational.
d. Negation: n is prime and both n is not odd and n is not 2. Or: n is prime and n is neither
odd nor 2.
e. Negation: x is nonnegative and x is not positive and x is not 0.
Or: x is nonnegative but x is not positive and x is not 0.
Or: x is nonnegative and x is neither positive nor 0.
f. Negation: Tom is Annโs father and either Jim is not her uncle or Sue is not her aunt.
g. Negation: n is divisible by 6 and either n is not divisible by 2 or n is not divisible by 3.
21. By assumption, p โ q is false. By de๏ฌnition of a conditional statement, the only way this can
happen is for the hypothesis, p, to be true and the conclusion, q, to be false.
a. The only way โผ p โ q can be false is for โผ p to be true and q to be false. But since p is
true, โผ p is false. Hence โผ p โ q is not false and so it is true.
b. Since p is true, then p โจ q is true because if one component of an and statement is true,
then the statement as a whole is true.
c The only way q โ p can be false is for q to be true and p to be false. Thus, since q is false,
q โ p is not false and so it is true.
22. a. Contrapositive: If P is not a rectangle, then P is not a square.
b. Contrapositive: If tomorrow is not January, then today is not New Yearโs Eve.
c. Contrapositive: If r is not rational, then the decimal expansion of r is not terminating.
d. Contrapositive: If n is not odd and n is not 2, then n is not prime.
14
Solutions for Exercises: The Logic of Compound Statements
e. Contrapositive: If x is not positive and x is not 0, then x is not nonnegative.
Or: If x is neither positive nor 0, then x is negative.
f. Contrapositive: If either Jim is not Annโs uncle or Sue is not her aunt, then Tom is not her
father.
g. Contrapositive: If n is not divisible by 2 or n is not divisible by 3, then n is not divisible
by 6.
23. a. Converse: If P is a rectangle, then P is a square.
Inverse: If P is not a square, then P is not a rectangle.
b. Converse: If tomorrow is January, then today is New Yearโs Eve.
Inverse: If today is not New Yearโs Eve, then tomorrow is not January.
c. Converse: If r is rational then the decimal expansion of r is terminating.
Inverse: If the decimal expansion of r is not terminating, then r is not rational.
d. Converse: If n is odd or n is 2, then n is prime.
Inverse: If n is not prime, then n is not odd and n is not 2.
e. Converse: If x is positive or x is 0, then x is nonnegative.
Inverse: If x is not nonnegative, then both x is not positive and x is not 0.
Or: If x is negative, then x is neither positive nor 0.
f. Converse: If Jim is Annโs uncle and Sue is her aunt, then Tom is her father.
Inverse: If Tom is not Annโs father, then Jim is not her uncle or Sue is not her aunt
g. Converse: If n is divisible by 2 and n is divisible by 3, then n is divisible by 6
Inverse: If n is not divisible by 6, then n is not divisible by 2 or n is not divisible by 3.
24.
p
T
T
F
F
q
T
F
T
F
pโq
T
F
T
T
|
qโp
T
T
F
T
{z
โ
โ
}
di๏ฌerent truth values
The truth table shows that p โ q and q โ p have di๏ฌerent truth values in the second and
third rows. Hence they are not logically equivalent.
25.
p
T
T
F
F
q
T
F
T
F
โผp
F
F
T
T
โผq
F
T
F
T
pโq
T
F
T
T
|
โผ p โโผ q
T
T
F
T
{z
}
โ
โ
di๏ฌerent truth values
The truth table shows that p โ q and โผ p โโผ q have di๏ฌerent truth values in rows 2 and 3,
so they are not logically equivalent. Thus a conditional statement is not logically equivalent
to its inverse.
Instructorโs Manual: Section 2.2
26.
p
q
โผp
โผq
โผ q โโผ p
pโq
T
T
F
F
T
F
T
F
F
F
T
T
F
T
F
T
T
F
T
T
T
F
T
T
|
{z
15
}
same truth values
The truth table shows that โผq โ โผp and p โ q always have the same truth values and
thus are logically equivalent. It follows that a conditional statement and its contrapositive are
logically equivalent to each other.
27.
p
q
โผp
โผq
qโp
โผ p โโผ q
T
T
F
F
T
F
T
F
F
F
T
T
F
T
F
T
T
T
F
T
T
T
F
T
|
{z
}
same truth values
The truth table shows that q โ p and โผ p โโผ q always have the same truth values and thus
are logically equivalent. It follows that the converse and inverse of a conditional statement are
logically equivalent to each other.
28. The if-then form of โI say what I meanโ is โIf I mean something, then I say it.โ
The if-then form of โI mean what I sayโ is โIf I say something, then I mean it.โ
Thus โI mean what I sayโ is the converse of โI say what I mean,โ and so the two statements
are not logically equivalent.
29. The corresponding tautology is (p โ (q โจ r)) โ ((p โง โผq) โ r)
p
q
r
โผq
q โจr
pโงโผq
p โ (q โจ r )
pโงโผq โr
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
T
T
F
F
T
T
T
T
T
F
T
T
T
F
F
F
T
T
F
F
F
F
T
T
T
F
T
T
T
T
T
T
T
F
T
T
T
T
(p โ (q โจ r )) โ
((p โง โผ q) โ r )
T
T
T
T
T
T
T
T
The truth table shows that (p โ (q โจ r)) โ ((p โง โผq) โ r) is a tautology because all of its
truth values are T.
30. The corresponding tautology is p โง (q โจ r) โ (p โง q) โจ (p โง r)
16
Solutions for Exercises: The Logic of Compound Statements
p
q
r
qโจr
p โงq
p โงr
p โง (q โจ r)
(p โง q) โจ (p โง r)
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
T
T
T
F
T
T
T
F
T
T
F
F
F
F
F
F
T
F
T
F
F
F
F
F
T
T
T
F
F
F
F
F
T
T
T
F
F
F
F
F
p โง (q โจ r) โ
(p โง q) โจ (p โง r)
T
T
T
T
T
T
T
T
|
{z
}
all T โs
The truth table shows that p โง (q โจ r) โ (p โง q) โจ (p โง r) is always true. Hence it is a tautology.
31. The corresponding tautology is (p โ (q โ r)) โ ((p โง q) โ r).
p
q
r
qโr
p โงq
p โ (q โ r)
(p โง q) โ r)
p โ (q โ r) โ (p โง q) โ r
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
T
F
T
T
T
F
T
T
T
T
F
F
F
F
F
F
T
F
T
T
T
T
T
T
T
F
T
T
T
T
T
T
T
T
T
T
T
T
T
T
{z
all T โs
|
}
The truth table shows that (p โ (q โ r)) โ ((p โง q) โ r) is always true. Hence it is a
tautology.
32. If this quadratic equation has two distinct real roots, then its discriminant is greater than zero,
and if the discriminant of this quadratic equation is greater than zero, then the equation has
two real roots.
33. If this integer is even, then it equals twice some integer, and if this integer equals twice some
integer, then it is even.
34. If the Cubs do not win tomorrowโs game, then they will not win the pennant.
If the Cubs win the pennant, then they will have won tomorrowโs game.
35. If Sam is not an expert sailor, then he will not be allowed on Signeโs racing boat.
If Sam is allowed on Signeโs racing boat, then he is an expert sailor.
36. The Personnel Director did not lie. By using the phrase โonly if,โ the Personnel Director set
forth conditions that were necessary but not su๏ฌcient for being hired: if you did not satisfy
those conditions then you would not be hired. The Personnel Directorโs statement said nothing
about what would happen if you did satisfy those conditions.
37. If a new hearing is not granted, payment will be made on the ๏ฌfth.
38. If it doesnโt rain, then Ann will go.
39. If a security code is not entered, then the door will not open.
40. If I catch the 8:05 bus, then I am on time for work.
41. If this triangle has two 45โฆ angles, then it is a right triangle.
Instructorโs Manual: Section 2.2
17
42. If this number is not divisible by 3, then it is not divisible by 9.
If this number is divisible by 9, then it is divisible by 3.
43. If Jim does not do his homework regularly, then Jim will not pass the course.
If Jim passes the course, then he will have done his homework regularly.
44. If Jonโs team wins the rest of its games, then it will win the championship.
45. If this computer program produces error messages during translation, then it is not correct.
If this computer program is correct, then it does not produce error messages during translation.
46. a. This statement is the converse of the given statement, and so it is not necessarily true.
For instance, if the actual boiling point of compound X were 200โฆ C, then the given statement
would be true but this statement would be false.
b. This statement must be true. It is the contrapositive of the given statement.
c. must be true
d. not necessarily true
e. must be true
f. not necessarily true
Note: To solve this problem, it may be helpful to imagine a compound whose boiling point is
greater than 150โฆ C. For concreteness, suppose it is 200โฆ C. Then the given statement would
be true for this compound, but statements a, d, and f would be false.
47. a. p โง โผq โ r โก โผ(p โง โผq) โจ r
b.
p โง โผq โ r
โก
โผ(p โง โผq) โจ r
โก
โก
โผ[โผ(โผ(p โง โผq)) โง โผr]
โผ[(p โง โผq) โง โผr]
by the identity for โ shown in
the directions [an acceptable answer]
by De Morganโs law [another acceptable answer]
by the double negative law
[another acceptable answer]
Any of the expressions in part (b) would also be acceptable answers for part (a).
48. a.
pโจ โผ q โ r โจ q
โก
โผ (p โจ โผ q) โจ (r โจ q)
โก
(โผ p โง โผ (โผ q)) โจ (r โจ q)
โก
(โผ p โง q) โจ (r โจ q)
by the identity for โ shown in the
directions [an acceptable answer]
by De Morganโs law
[another acceptable answer]
by the double negative law
[another acceptable answer]
โก (โผ p โง q) โจ (r โจ q)
by part (a)
โก โผ (โผ (โผ p โง q)โง โผ (r โจ q))
by De Morganโs law
โก โผ (โผ (โผ p โง q) โง (โผ r โง โผ q)) by De Morganโs law
Any of the expressions in part (b) would also be acceptable answers for part (a).
b.
49. a.
pโจ โผ q โ r โจ q
(p โ r) โ (q โ r)
โก
โก
(โผp โจ r) โ (โผq โจ r)
[โผ(โผp โจ r) โจ (โผq โจ r)] โง [โผ(โผq โจ r) โจ (โผp โจ r)]
by the identity for โ shown in the
โก
[(p โง โผr) โจ (โผq โจ r)] โง [(q โง โผr) โจ (โผp โจ r)]
directions [an acceptable answer]
by De Morganโs law [another acceptable answer]
b.
(โผp โจ r) โ (โผq โจ r)
โก
โผ[โผ(p โง โผr) โง โผ(โผq โจ r)] โง โผ[โผ(q โง โผr) โง โผ(โผp โจ r)]
โก
โผ[โผ(p โง โผr) โง (q โง โผr)] โง โผ[โผ(q โง โผr) โง (p โง โผr)]
by De Morganโs law
by De Morganโs law
Any of the expressions in part (b) would also be acceptable answers for part (a).
18
Solutions for Exercises: The Logic of Compound Statements
50. a.
(p โ (q โ r)) โ ((p โง q) โ r)
โก
โก
โก
[โผ p โจ (q โ r)] โ [โผ (p โง q) โจ r]
[โผ p โจ (โผ q โจ r)] โ [โผ (p โง q) โจ r]
โผ [โผ p โจ (โผ q โจ r)] โจ [โผ (p โง q) โจ r]
โงโผ [โผ (p โง q) โจ r] โจ [โผ p โจ (โผ q โจ r)]
b. By part (a), De Morganโs law, and the double negative law,
(p โ (q โ r)) โ ((p โง q) โ r)
โก
โผ [โผ p โจ (โผ q โจ r)] โจ [โผ (p โง q) โจ r]
โงโผ [โผ (p โง q) โจ r] โจ [โผ p โจ (โผ q โจ r)]
โก โผ [โผ p โจ (โผ q โจ r)]โง โผ [โผ (p โง q) โจ r]
โง โผ โผ [(p โง q)โง โผ r]โง โผ [โผ p โจ (โผ q โจ r)]
โก โผ โผ [p โง โผ (โผ q โจ r)] โง [(p โง q)โง โผ r]
โง โผ โผ [(p โง q)โง โผ r] โง [p โง โผ (โผ q โจ r)]
โก โผ โผ [p โง (q โง โผ r)] โง [(p โง q)โง โผ r]
โง โผ โผ [(p โง q)โง โผ r] โง [p โง (qโง โผ r)].
Any of the expressions in the right-hand column would also be acceptable answers for part (a).
51. Yes. As in exercises 47-50, the following logical equivalences can be used to rewrite any
statement form in a logically equivalent way using only โผ and โง:
p โ q โกโผ p โจ q
p โจ q โกโผ (โผ p โง โผ q)
p โ q โก (โผ p โจ q) โง (โผ q โจ p)
โผ (โผ p) โก p
The logical equivalence p โง q โก โผ (โผ p โจ โผ q) can then be used to rewrite any statement form
in a logically equivalent way using only โผ and โจ.
Section 2.3
1.
โ
2 is not rational.
2. 1 โ 0.99999… is less than every positive real number.
3. Logic is not easy.
4. This graph cannot be colored with two colors.
5. They did not telephone.
6.
premises
p
T
T
F
F
q
T
F
T
T
}|
{
z
pโq pโq
T
T
F
T
T
F
T
T
conclusion
pโจq
T
critical row
F
critical row
Rows 2 and 4 of the truth table are the critical rows in which all the premises are true, but
row 4 shows that it is possible for an argument of this form to have true premises and a false
conclusion. Thus this argument form is invalid.
Instructorโs Manual: Section 2.3
7.
premises
19
conclusion
z
}|
{
p
q
r
โผq
p p โq โผq โจr
r
T T T
F
T
T
T
T critical row
T T F
F
T
T
F
T F T
T
T
F
T
T F F
T
T
F
T
F T T
F
F
T
T
F T F
F
F
T
F
F F T
T
F
T
T
F F F
T
F
T
T
This row describes the only situation in which all the premises are true. Because the conclusion
is also true here, the argument form is valid.
8.
premises
conclusion
z
}|
{
p
q
r
โผ q p โจ q p โโผ q p โ r
r
T T T
F
T
F
T
T T F
F
T
F
F
T F T
T
T
T
T
T critical row
T F F
T
T
T
F
F T T
F
T
T
T
T critical row
F T F
F
T
T
T
F critical row
F F T
T
F
T
T
F F F
T
F
T
T
This row shows that it is possible for an argument of this form to have true premises and a
false conclusion. Thus this argument form is invalid.
9.
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
โผq
F
F
T
T
F
F
T
T
โผr
F
T
F
T
F
T
F
T
pโงq
T
T
F
F
F
F
F
F
z
p โง q โโผ r
F
T
T
T
T
T
T
T
premises
}|
pโจ โผ q
T
T
T
T
F
F
T
T
conclusion
{
โผqโp
T
T
T
T
T
T
F
F
โผr
T
F
T
critical row
critical row
critical row
Rows 2, 3, and 4 of the truth table are the critical rows in which all the premises are true, but
row 3 shows that it is possible for an argument of this form to have true premises and a false
conclusion. Hence the argument form is invalid.
10.
premise
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
โผp
F
F
F
F
T
T
T
T
โผq
F
F
T
T
F
F
T
T
โผr
F
T
F
T
F
T
F
T
โผ pโง โผ q
F
F
F
F
F
F
T
T
p โจq
T
T
T
T
T
T
F
F
r
T
F
T
F
T
F
T
F
p โจq โr
T
F
T
F
T
F
T
T
conclusion
โผ r โ โผ pโง โผ q
T critical row
F
T
F
T
F
T
T
critical row
critical row
critical row
critical row
20
Solutions for Exercises: The Logic of Compound Statements
This form of argument has just one premise. Rows 1, 3, 5, 7, and 8 of the truth table represent
all the situations in which the premise is true, and in each of these rows the conclusion is also
true. Therefore, the argument form is valid.
11.
p
q
r
โผp
โผq
โผr
qโจr
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
F
F
F
T
T
T
T
F
F
T
T
F
F
T
T
F
T
F
T
F
T
F
T
T
T
T
F
T
T
T
F
premises
z
}|
{
p โ qโจr โผ qโจ โผ r
T
T
T
F
T
T
T
T
F
T
T
T
F
T
T
T
conclusion
โผ pโจ โผ r
T
F
critical row
critical row
T
T
T
critical row
critical row
critical row
Rows 2, 3, 6, 7, and 8 of the truth table represent the situations in which all the premises are
true, but row 3 shows that it is possible for an argument of this form to have true premises
and a false conclusion. Hence the argument form is invalid.
12. a.
premises
p
T
T
F
F
q
T
F
T
T
z }|
pโq
T
F
T
T
{
q
T
F
T
F
conclusion
p
T
critical row
F
critical row
Rows 1 and 3 of the truth table represent the situations in which all the premises are true,
but row 3 shows that it is possible for an argument of this form to have true premises and a
false conclusion. Hence the argument form is invalid.
b.
premises
p
T
T
F
F
z
}|
{
pโq โผp
T
F
F
T
T
F
T
T
q
T
F
T
T
conclusion
โผq
T
critical row
F
critical row
Rows 2 and 4 of the truth table represent the situations in which all the premises are true,
but row 4 shows that it is possible for an argument of this form to have true premises and a
false conclusion. Hence the argument form is invalid.
13.
p
q
T
T
F
F
T
F
T
F
premises
conclusion
}|
{
z
pโq โผq
โผp
T
F
T
T
F
T
F
T
T
critical row
Row 4 of the truth table represents the only situation in which all the premises are true, and
in this row the conclusion is also true. Therefore, the argument form (modus tollens) is valid.
Instructorโs Manual: Section 2.3
14.
premise
conclusion
pโจq
T
critical row
T
critical row
p
q
p
T
T
F
F
T
F
T
F
T
F
T
F
21
The truth table shows that in the two situations (represented by rows 1 and 3) in which the
premise is true, the conclusion is also true. Therefore, Generalization, version (a), is valid.
15.
premise
conclusion
pโจq
T
critical row
T
critical row
p
q
q
T
T
F
F
T
F
T
F
T
F
T
F
The truth table shows that in the two situations (represented by rows 1 and 3) in which the
premise is true, the conclusion is also true. Therefore, Generalization, version (b), is valid.
16.
premise
conclusion
p
p
q
p โงq
T
T
F
F
T
F
T
F
T
F
F
F
T
critical row
The truth table shows that in the only situation (represented by row 1) in which both premises
are true, the conclusion is also true. Therefore, Specialization, version (sa), is valid.
17.
premise
conclusion
q
p
q
p โงq
T
T
F
F
T
F
T
F
T
F
F
F
T
critical row
The truth table shows that in the only situation (represented by row 1) in which both premises
are true, the conclusion is also true. Therefore, Specialization, version (b), is valid.
22
Solutions for Exercises: The Logic of Compound Statements
18.
premises
p
T
T
F
F
q
T
F
T
T
conclusion
z
}|
{
p โจq โผq
T
F
T
T
T
F
F
T
p
T
critical row
Row 2 represents the only situation in which both premises are true. Because the conclusion
is also true here the argument form is valid.
19.
premises
conclusion
q
p
q
z
}|
{
pโจq โผp
T
T
F
F
T
F
T
F
T
T
T
F
F
F
T
T
T
critical row
The truth table shows that in the only situation (represented by row 3) in which both premises
are true, the conclusion is also true. Therefore, Elimination, version (b), is valid.
20.
premises
p
q
r
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
z
}|
{
pโq qโr
T
T
F
F
T
T
T
T
T
F
T
T
T
F
T
T
conclusion
pโr
T
critical row
T
critical row
T
T
critical row
critical row
The truth table shows that in the four situations (represented by rows 1, 5, 7, and 8) in which
both premises are true, the conclusion is also true. Therefore, Transitivity is valid.
21.
premises
p
q
r
z
pโจq
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
T
T
T
T
T
T
F
F
conclusion
}|
pโr
{
qโr
T
F
T
F
T
T
T
T
T
F
T
T
T
F
T
T
r
T
critical row
T
critical row
T
critical row
The truth table shows that in the three situations (represented by rows 1, 3, 5) in which all
three premises are true, the conclusion is also true. Therefore, proof by division into cases is
valid.
Instructorโs Manual: Section 2.3
23
22. Let p represent โTom is on team Aโ and q represent โHua is on team B.โ Then the argument
has the form
โผp โ q
โผq โ p
โด โผp โจ โผq
premises
p
q
โผp
โผq
T
T
F
F
T
F
T
F
F
F
T
T
F
T
F
T
conclusion
z
}|
{
โผpโq โผq โp
T
T
T
F
T
T
T
F
โผpโจโผq
F
T
T
critical row
critical row
critical row
Rows 1, 2, and 3 of the truth table are the critical rows in which all the premises are true, but
row 1 shows that it is possible for an argument of this form to have true premises and a false
conclusion. Thus this argument form is invalid.
23.
form:
…
p โจq
pโr
qโจ โผ r
premises
p
q
r
โผr
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
F
T
F
T
F
T
F
T
z
}|
{
p โจq pโr
T
T
T
T
T
T
F
F
T
F
T
F
T
T
T
T
conclusion
qโจ โผ r
T
critical row
F
critical row
T
T
critical row
critical row
Rows 1, 3, 5, and 6 represent the situations in which both premises are true, but in row 3 the
conclusion is false. Hence, it is possible for an argument of this form to have true premises
and a false conclusion, and so the given argument is invalid.
24. form: p โ q
q
…
p
invalid: converse error
25. form: p โจ q
โผp
…
q
valid: elimination
26. form: p โ q
qโr
…
pโr
valid: transitivity
27. form: p โ q
โผp
…
โผq
invalid: inverse error
24
Solutions for Exercises: The Logic of Compound Statements
pโq
q
p
invalid, converse error
pโq
โผp
โผq
invalid, inverse error
invalid, converse error
…
pโq
q
p
31.
form:
…
p โงq
q
valid, generalization
32.
form:
pโr
qโr
pโจq โr
28.
form:
…
29.
form:
…
30.
form:
…
valid, proof by division into cases
33. A valid argument with a false conclusion must have at least one false premise. In the following
example, the second premise is false. (The ๏ฌrst premise is true because its hypothesis is false.)
If the square of every real number is positive, then no real number is negative.
The square of every real number is positive.
Therefore, no real number is negative.
34. An invalid argument with a true conclusion can have premises that are either true or false.
In the following example the ๏ฌrst premise is true for either one of following two reasons: its
hypothesis is false and its conclusion is true.
If the square of every real number is positive, then some real numbers are positive.
Some real numbers are positive.
Therefore, the square of every real number is positive.
35. A correct answer should indicate that for a valid argument, any argument of the same form
that has true premises has a true conclusion, whereas for an invalid argument, it is possible to
๏ฌnd an argument of the same form that has true premises and a false conclusion. The validity
of an argument does not depend on whether the conclusion is true or not. The validity of an
argument only depends on the formal relationship between its premises and its conclusion.
36. The program contains an undeclared variable.
One explanation:
1. There is not a missing semicolon and there is not a misspelled variable name. (by (c) and
(d) and definition of โง)
2. It is not the case that there is a missing semicolon or a misspelled variable name. (by (1)
and De Morganโs laws)
3. There is not a syntax error in the ๏ฌrst ๏ฌve lines. (by (b) and (2) and modus tollens)
4. There is an undeclared variable. (by (a) and (3) and elimination)
37. The treasure is buried under the ๏ฌagpole.
One explanation:
1. The treasure is not in the kitchen. (by (c) and (a) and modus ponens)
2. The tree in the front yard is not an elm. (by (b) and (1) and modus tollens)
3. The treasure is buried under the ๏ฌagpole. (by (d) and (2) and elimination)
Instructorโs Manual: Section 2.3
38. a. A is a knave and B is a knight.
One explanation:
1. Suppose A is a knight.
2. โด What A says is true. (by definition of knight)
3. โด B is a knight also. (Thatโs what A said.)
4. โด What B says is true. (by definition of knight)
5. โด A is a knave. (Thatโs what B said.)
6. โด We have a contradiction: A is a knight and a knave. (by (1) and (5))
7. โด The supposition that A is a knight is false. (by the contradiction rule)
8. โด A is a knave. (negation of supposition)
9. โด What B says is true. (B said A was a knave, which we now know to be true.)
10. โด B is a knight. (by definition of knight)
b. C is a knave and D is a knight
One explanation:
1. Suppose C is a knight.
2. … C is a knave (because what C said was true).
3. … C is both a knight and a knave (by (1) and (2)), which is a contradiction.
4. … C is not a knight (because by the contradiction rule the supposition is false).
5. … What C says is false (because since C is not a knight he is a knave and knaves
always speak falsely).
6. … At least one of C or D is a knight (by De Morganโs law).
7. … D is a knight (by (4) and (6) and elimination).
8. … C is a knave and D is a knight (by (4) and (7)).
To check that the problem situation is not inherently contradictory, note that if C is a
knave and D is a knight, then each could have spoken as reported.
c. One is a knight and the other is a knave.
One explanation:
There is one knave. E and F cannot both be knights because then both would also be
knaves (since each would have spoken the truth), which is a contradiction. Nor can E and
F both be knaves because then both would be telling the truth which is impossible for
knaves. Hence, the only possible answer is that one is a knight and the other is a knave.
But in this case both E and F could have spoken as reported, without contradiction.
d. U , Z, X, and V are knaves and W and Y are knights.
One explanation:
1. The statement made by U must be false because if it were true then U would not
be a knight (since none would be a knight), but since he spoke the truth he would be a
knight and this would be a contradiction.
2. … there is at least one knight, and U is a knave (since his statement that there are
no knights is false).
3. Suppose Z spoke the truth. Then so did W (since if there is exactly one knight then
it is also true that there are at most three knights). But this implies that there are at
least two knights, which contradicts Z โฒ s statement. Hence Z cannot have spoken the
truth.
4. … there are at least two knights, and Z is a knave (since his statement that there is
exactly one knight is false). Also X โฒ s statement is false because since both U and Z are
knaves it is impossible for there to be exactly ๏ฌve knights. Hence X also is a knave.
5. … there are at least three knaves (U , Z, and X), and so there are at most three
knights.
6. … W โฒ s statement is true, and so W is a knight.
25
26
Solutions for Exercises: The Logic of Compound Statements
7. Suppose V spoke the truth. Then V , W , and Y are all knights (otherwise there would
not be at least three knights because U , Z, and X are known to be knaves). It follows
that Y spoke the truth. But Y said that exactly two were knights. This contradicts the
result that V , W , and Y are all knights.
8. … V cannot have spoken the truth, and so V is a knave.
9. … U , Z, X, and V are all knaves, and so there are at most two knights.
10. Suppose that Y is a knave. Then the only knight is W , which means that Z spoke
the truth. But we have already seen that this is impossible. Hence Y is a knight.
11. By 6, 9, and 10, the only possible solution is that U , Z, X, and V are knaves and W
and Y are knights. Examination of the statements shows that this solution is consistent:
in this case, the statements of U , Z, X, and V are false and those of W and Y are true.
39. The chau๏ฌeur killed Lord Hazelton.
One explanation:
1. Suppose the cook was in the kitchen at the time of the murder.
2. โด The butler killed Lord Hazelton with strychnine. (by (c) and (1) and modus ponens)
3. โด We have a contradiction: Lord Hazelton was killed by strychnine and a blow on the
head. (by (2) and (a))
4. โด The supposition that the cook was in the kitchen is false. (by the contradiction rule)
5. โด The cook was not in the kitchen at the time of the murder. (negation of supposition)
6. โด Sara was not in the dining room when the murder was committed. (by (e) and (5) and
modus ponens)
7. โด Lady Hazelton was in the dining room when the murder was committed. (by (b) and
(6) and elimination)
8. โด The chau๏ฌeur killed Lord Hazelton. (by (d) and (7) and modus ponens)
40. One solution: Suppose Socko is telling the truth. Then Fats is also telling the truth because
if Lefty killed Sharky then Muscles didnโt kill Sharky. Consequently, two of the men were
telling the truth, which contradicts the fact that all were lying except one. Therefore, Socko
is not telling the truth: Lefty did not kill Sharky. Hence Muscles is telling the truth and all
the others are lying. It follows that Fats is lying, and so Muscles killed Sharky.
Another solution: The statements of Socko and Muscles contradict each other, which implies
that one is lying and the other is telling the truth. If Socko is telling the truth, then Fats
is also telling the truth, which contradicts the fact that only one person told the truth. So
Muscles is the only one who told the truth. Hence Muscles is telling the truth and all the
others are lying. It follows that Fats is lying, and so Muscles killed Sharky.
41. (1) p โ t by premise (d)
โผp
by premise (c)
โด โผp
by modus tollens
(2) โผp
โด โผp โจ q
by (1)
by generalization
(3) โผp โจ q โ r
โผp โจ q
โด r
(4) โผp
r
โด โผp โง r
by premise (a)
by (2)
by modus ponens
by (1)
by (3)
by conjunction
(5) โผp โง r โ โผs by premise (e)
โผp โง r
by (4)
โด โผs
by modus ponens
Instructorโs Manual: Section 2.3
(6) s โจ โผq
โผs
โด โผq
42.
(1)
…
(2)
…
qโr
โผr
โผq
by premise (b)
by premise (d)
by modus tollens
p โจq
โผq
p
by premise (a)
by (1)
by elimination
…
โผq โuโงs
โผq
uโงs
(4)
…
uโงs
s
by (3)
by specialization
(5)
p
s
p โงs
by (2)
by (4)
by conjunction
(3)
…
(6)
…
43.
by premise (b)
by (5)
by elimination
p โงsโt
p โงs
t
(1) โผw
uโจw
โด u
by premise (e)
by (1)
by modus ponens
by premise (c)
by (5)
by modus ponens
by premise (d)
by premise (e)
by elimination
(2) u โ โผp by premise (c)
u
by (1)
โด โผp
by modus ponens
(3) โผp โ r โง โผs by premise (a)
โผp
by (2)
โด r โง โผs
by modus ponens
(4) r โง โผs by (3)
โด โผs
by specialization
44.
(5) โผt โ s
โผs
โด โผt
by premise (b)
by (4)
by modus tollens
โผqโจs
โผs
โผq
by premise (d)
by premise (e)
by elimination
pโq
โผq
โผp
by premise (a)
by (1)
by modus tollens
rโจs
โผs
r
by premise (b)
by premise (e)
by elimination
(1)
…
(2)
…
(3)
…
(4)
…
โผp
r
โผp โงr
by (2)
by (3)
by conjunction
27
28
Solutions for Exercises: The Logic of Compound Statements
(5)
…
(6)
…
(7)
…
(8)
…
โผp โงr โu
โผp โงr
u
โผ s โโผ t
โผs
โผt
by premise (f)
by (4)
by modus ponens
by premise (c)
by premise (e)
by modus ponens
wโจt
โผt
w
by premise (g)
by (6)
by elimination
u
w
uโงw
by (5)
by (7)
by conjunction
Section 2.4
1. R = 1
2. R = 1
3. S = 1
4. S = 1
5. The input/output table is as follows:
Input
Output
P
1
1
0
0
R
1
1
0
1
Q
1
0
1
0
6. The input/output table is as follows:
Input
Output
P Q R
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
S
1
0
1
1
1
0
1
0
7. The input/output table is as follows:
Input
P
1
1
0
0
Q
1
0
1
0
Output
R
0
1
0
0
Instructorโs Manual: Section 2.4
8. The input/output table is as follows:
Input
P
1
1
1
1
0
0
0
0
Q
1
1
0
0
1
1
0
0
Output
R
1
0
1
0
1
0
1
0
S
1
1
1
1
1
1
1
1
9. P โจ โผQ
10. (P โจ Q)โง โผ Q
11. (P โง โผQ) โจ R
12. (P โจ Q)โจ โผ (Q โง R)
13.
P
NOT
OR
Q
14.
P
R
NOT
OR
Q
15.
P
OR
NOT
AND
NOT
Q
16.
P
AND
Q
R
OR
NOT
29
30
Solutions for Exercises: The Logic of Compound Statements
17.
P
AND
Q
S
OR
NOT
NOT
AND
R
18. a. (P โง Q โง โผR) โจ (โผP โง Q โง R)
b. P
Q
AND
R
NOT
OR
NOT
AND
19. a. (P โง Qโง โผ R) โจ (P โง โผ Qโง โผ R) โจ (โผ P โง Q โง โผ R)
b. One circuit (among many) having the given input/output table is the following:
P
Q
R
AND
NOT
NOT
AND
NOT
NOT
AND
NOT
20. a. (P โง Q โง R) โจ (P โง โผQ โง R) โจ (โผP โง โผQ โง โผR)
OR
S
Instructorโs Manual: Section 2.4
b.
P
Q
AND
R
OR
NOT
AND
NOT
AND
NOT
NOT
21. a. (P โง Q โง โผ R) โจ (โผ P โง Q โง R) โจ (โผ P โง Q โง โผ R)
b. One circuit (among many) having the given input/output table is the following:
P
Q
R
AND
NOT
NOT
AND
OR
S
NOT
AND
NOT
22. The input/output table is
Input
Output
P Q R
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
S
0
1
0
0
0
0
1
0
One circuit (among many) having this input/output table is shown below.
31
32
Solutions for Exercises: The Logic of Compound Statements
P
Q
AND
R
NOT
OR
NOT
AND
NOT
23. The input/output table is as follows:
Input
P
1
1
1
1
0
0
0
0
Q
1
1
0
0
1
1
0
0
Output
R
1
0
1
0
1
0
1
0
S
1
0
0
0
0
0
0
1
One circuit (among many) having this input/output table is the following:
P
Q
R
AND
OR
NOT
NOT
S
AND
NOT
24. Let P and Q represent the positions of the switches in the classroom, with 0 being โdownโ
and 1 being โup.โ Let R represent the condition of the light, with 0 being โo๏ฌโ and 1 being
โon.โ Initially, P = Q = 0 and R = 0. If either P or Q (but not both) is changed to 1, the
light turns on. So when P = 1 and Q = 0, then R = 1, and when P = 0 and Q = 1, then
R = 1. Thus when one switch is up and the other is down the light is on, and hence moving
the switch that is down to the up position turns the light o๏ฌ. So when P = 1 and Q = 1, then
R = 0. It follows that the input/output table has the following appearance:
Input
Output
P
1
1
0
0
R
0
1
1
0
Q
1
0
1
0
Instructorโs Manual: Section 2.4
33
One circuit (among many) having this input/output table is the following:
P
AND
Q
NOT
R
OR
NOT
AND
25. Let P , Q, and R indicate the positions of the switches, with 1 indicating that the switch is in
the on position. Let an output of 1 indicate that the security system is enabled. The complete
input/output table is as follows:
Input
P
1
1
1
1
0
0
0
0
Q
1
1
0
0
1
1
0
0
Output
R
1
0
1
0
1
0
1
0
S
1
1
1
0
1
0
0
0
One circuit (among many) having this input/output table is the following:
P
Q
R
AND
AND
NOT
OR
NOT
S
AND
NOT
AND
Note: One alternative answer interchanges the 1โs and 0โs.
26. The Boolean expression for (a) is (P โง Q) โจ Q, and for (b) it is (P โจ Q) โง Q. We must show
that if these expressions are regarded as statement forms, then they are logically equivalent.
34
Solutions for Exercises: The Logic of Compound Statements
Now
(P โง Q) โจ Q
โก
โก
โก
โก
Q โจ (P โง Q)
(Q โจ P ) โง (Q โจ Q)
(Q โจ P ) โง Q
(P โจ Q) โง Q
by the commutative law for โจ
by the distributive law
by the idempotent law
by the commutative law for โง
Alternatively, by the absorption laws, both statement forms are logically equivalent to Q.
27. The Boolean expression for circuit (a) is โผ P โง(โผ (โผ P โงQ)) and for circuit (b) it is โผ (P โจQ).
We must show that if these expressions are regarded as statement forms, then they are logically
equivalent. Now
โผ P โง (โผ (โผ P โง Q))
โก
โก
โก
โก
โก
โก
โก
โก
โผ P โง (โผ (โผ P )โจ โผ Q)
โผ P โง (P โจ โผ Q)
(โผ P โง P ) โจ (โผ P โง โผ Q)
(P โง โผ P ) โจ (โผ P โง โผ Q)
c โจ(โผ P โง โผ Q)
(โผ P โง โผ Q)โจc
โผPโงโผQ
โผ (P โจ Q)
by De Morganโs law
by the double negative law
by the distributive law
by the commutative law for โง
by the negation law for โง
by the commutative law for โจ
by the identity law for โจ
by De Morganโs law.
28. The Boolean expression for circuit (a) is (P โง Q) โจ (P โง โผ Q) โจ (โผ P โง โผ Q) and for circuit
(b) it is P โจ โผ Q. We must show that if these expressions are regarded as statement forms,
then they are logically equivalent. Now
(P โง Q) โจ (P โง โผ Q) โจ (โผ P โง โผ Q)
โก
((P โง Q) โจ (P โง โผ Q)) โจ (โผ P โง โผ Q)
โก
โก
โก
โก
โก
โก
โก
(P โง (Qโจ โผ Q)) โจ (โผ P โง โผ Q)
(P โง t) โจ (โผ P โง โผ Q)
P โจ (โผ P โง โผ Q)
(P โจ โผ P ) โง (P โจ โผ Q)
t โง (P โจ โผ Q)
(P โจ โผ Q) โง t
Pโจ โผ Q
by inserting parentheses (which is
legal by the associative law for โจ)
by the distributive law
by the negation law for โจ
by the identity law for โง
by the distributive law
by the negation law for โจ
by the commutative law for โง
by the identity law for โง.
29. The Boolean expression for circuit (a) is (P โง Q) โจ (โผ P โง Q) โจ (P โง โผ Q) and for circuit
(b) it is P โจ Q. We must show that if these expressions are regarded as statement forms, then
they are logically equivalent. Now
(P โง Q) โจ (โผ P โง Q) โจ (P โง โผ Q)
โก
((P โง Q) โจ (โผ P โง Q)) โจ (P โง โผ Q)
โก
โก
โก
โก
โก
โก
โก
โก
((Q โง P ) โจ (Qโง โผ P )) โจ (P โง โผ Q)
(Q โง (P โจ โผ P )) โจ (P โง โผ Q)
(Qโง t) โจ(P โง โผ Q)
Q โจ (P โง โผ Q)
(Q โจ P ) โง (Q โจ โผ Q)
(Q โจ P )โง t
QโจP
P โจQ
by inserting parentheses (which is
legal by the associative law for โจ)
by the commutative law for โง
by the distributive law
by the negation law for โจ
by the identity law for โง
by the distributive law
by the negation law for โจ
by the identity law for โง
by the commutative law for โจ.
Instructorโs Manual: Section 2.4
30. (P โง Q) โจ (โผP โง Q) โจ (โผP โง โผQ) โก (P โง Q) โจ ((โผP โง Q) โจ (โผP โง โผQ)
โก (P โง Q) โจ (โผP โง (Q โจ โผQ))
โก (P โง Q) โจ (โผP โง t)
โก (P โง Q) โจ โผP
โก โผP โจ (P โง Q)
โก (โผP โจ P ) โง (โผP โจ Q)
โก (P โจ โผP ) โง (โผP โจ Q)
โก t โง (โผP โจ Q)
โก (โผP โจ Q) โง t
โก โผP โจ Q
by inserting parentheses (which is
legal by the associative law)
by the distributive law
by the negation law for โจ
by the identity law for โง
by the commutative law for โจ
by the distributive law
by the commutative law for โจ
by the negation law for โจ
by the commutative law for โง
by the identity law for โง
31. (โผ P โง โผ Q) โจ (โผ P โง Q) โจ (P โง โผ Q) โก ((โผ P โง โผ Q) โจ (โผ P โง Q)) โจ (P โง โผ Q)
โก
โก
โก
โก
โก
โก
โก
โก
โก
โก
(โผ P โง (โผ Q โจ Q)) โจ (P โง โผ Q)
(โผ P โง (Qโจ โผ Q)) โจ (P โง โผ Q)
(โผ P โง t) โจ(P โง โผ Q)
โผ P โจ (P โง โผ Q)
(โผ P โจ P ) โง (โผ P โจ โผ Q)
(P โจ โผ P ) โง (โผ P โจ โผ Q)
t โง(โผ P โจ โผ Q)
(โผ P โจ โผ Q)โง t
โผPโจโผQ
โผ (P โง Q)
by inserting parentheses (which is
legal by the associative law)
by the distributive law
by the commutative law for โจ
by the negation law for โจ
by the identity law for โง
by the distributive law
by the commutative law for โจ
by the negation law for โจ
by the commutative law for โง
by the identity law for โง
by De Morganโs law.
32. (P โง Q โง R) โจ ((P โง โผ Q โง R) โจ (P โง โผ Qโง โผ R)
โก
((P โง (Q โง R)) โจ (P โง (โผ Q โง R))) โจ (P โง (โผ Qโง โผ R)) โจ (P โง โผ Q)
by inserting parentheses (which is
legal by the associative law)
โก
โก
โก
โก
โก
โก
โก
โก
โก
(P โง [(Q โง R) โจ (โผ Q โง R)] โจ (P โง [โผ Qโง โผ R])
P โง ([(Q โง R) โจ (โผ Q โง R)] โจ [โผ Qโง โผ R])
P โง ([(R โง Q) โจ (Rโง โผ Q)] โจ [โผ Qโง โผ R])
P โง ([(R โง (Qโจ โผ Q)] โจ [โผ Qโง โผ R])
P โง ([(Rโง t] โจ[โผ Qโง โผ R])
P โง (R โจ [โผ Qโง โผ R])
P โง ((R โจ โผ Q) โง (Rโจ โผ R))
P โง ((R โจ โผ Q) โง t])
P โง (R โจ โผ Q)
by the distributive law
by the distributive law
by the commutative law for โง
by the distributive law
by the negation law for โจ
by the identity law for โง
by the distributive law
by the negation law for โจ
by the identity law for โง.
33. a.
(P | Q) | (P | Q)
โก
โก
โก
โก
โผ [(P | Q) โง (P | Q)]
โผ (P | Q)
โผ [โผ (P โง Q)]
P โงQ
by de๏ฌnition of |
by the idempotent law for โง
by de๏ฌnition of |
by the double negative law.
b.
P โง (โผ Q โจ R) โก (P | (โผ Q โจ R)) | (P | (โผ Q โจ R))
by part (a)
โก (P | [(โผ Q |โผ Q) | (R | R)]) | (P | [(โผ Q |โผ Q) | (R | R)])
by Example 2.4.7(b)
โก (P | [((Q | Q) | (Q | Q)) | (R | R)]) | (P | [((Q | Q) | (Q | Q)) | (R | R)])
by Example 2.4.7(a)
35
36
Solutions for Exercises: The Logic of Compound Statements
34. a.
(P โ Q) โ (P โ Q)
b.
P โจQ
c.
P โงQ
d.
P โQ
e.
P โQ
โก โผ(P โ Q)
by part (a)
โก โผ[โผ(P โจ Q)] by de๏ฌnition of โ
โกP โจQ
by the double negative law
โก
โก
โก
โผ (โผ (P โจ Q))
by the double negative law
โผ (P โ Q)
by de๏ฌnition of โ
(P โ Q) โ (P โ Q) by part (a).
โก
โก
โก
โผ (โผ P โจ โผ Q)
by De Morganโs law and the double negative law
โผ P โโผ Q
by de๏ฌnition of โ
(P โ P ) โ (Q โ Q) by part (a).
โก
โก
โก
โผP โจQ
by Exercise 13(a) of Section 2.2
(โผ P โ Q) โ (โผ P โ Q)
by part (b)
((P โ P ) โ Q) โ ((P โ P ) โ Q) by part (a).
โก
(P โ Q) โง (Q โ P )
โก
([(P โ P ) โ Q] โ [(P โ P ) โ Q)]) โง ([(Q โ Q) โ P ] โ [(Q โ Q) โ P )])
โก
(([(P โ P ) โ Q] โ [(P โ P ) โ Q)]) โ ([(P โ P ) โ Q] โ [(P โ P ) โ Q)]))
โ (([(Q โ Q) โ P ] โ [(Q โ Q) โ P )]) โ ([(Q โ Q) โ P ] โ [(Q โ Q) โ P )]))
by the truth table on page 46 of the text
by part (d)
by part (c)
Section 2.5
1. 1910 = 16 + 2 + 1 = 100112
2. 55 = 32 + 16 + 4 + 2 + 1 = 1101112
3. 287 = 256 + 16 + 8 + 4 + 2 + 1 = 1000111112
4. 45810 = 256 + 128 + 64 + 8 + 2 = 1110010102
5. 1609 = 1024 + 512 + +64 + 8 + 1 = 110010010012
6. 1424 = 1024 + 256 + 128 + 16 = 101100100002
7. 11102 = 8 + 4 + 2 = 1410
8. 101112 = 16 + 4 + 2 + 1 = 2310
9. 1101102 = 32 + 16 + 4 + 2 = 5410
10. 11001012 = 64 + 32 + 4 + 1 = 10110
11. 10001112 = 64 + 4 + 2 + 1 = 7110
12. 10110112 = 64 + 16 + 8 + 2 + 1 = 9110
13.
1
1
1
1 0 1 12
+
1 0 12
1 0 0 0 02
Instructorโs Manual: Section 2.5
14.
0
1
1
1 0 0 12
+ 1 0 1 12
1 0 1 0 02
15.
1
1
1
1
1 0 1 1 0 12
+
1 1 1 0 12
1 0 0 1 0 1 02
16.
1
1
1
1
1
1
1
1 1 0 1 1 1 0 1 12
+
1 0 0 1 0 1 1 0 1 02
1 0 0 0 0 0 1 0 1 0 12
17.
1
1
10
10
1
1 0
โ 1
1
1
1
0
0
1
02
12
12
10
18.
10
0
0
10
0
1
โ
1
1
1
0
1
1
1 02
0 12
0 12
19.
0
10
1 0 1 1
โ 1 0 0
1 1 0
0
1
1
20.
12
12
02
1
10
1
10
1
0
10
0
10
0
10
10
1
โ
0
1
1
1
0
0
1
1
1
1
0
1
0
02
12
12
1
21. a. S = 0, T = 1
b. S = 0, T = 1
c. S = 0, T = 0
22. Note that
+
111111112
12
1000000002
and 1000000002 = (28 )10 . Because 12 = 110 , we have that
โ
111111112 + 12
12
111111112
=
โ
=
23. |โ23|10 = 2310 = (16 + 4 + 2 + 1)10 = 000101112
11101001. So the answer is 11101001.
(28 )10
110
(28 โ 1)10
flip the bits
โโ
add 1
11101000 โโ
37
38
Solutions for Exercises: The Logic of Compound Statements
24. |โ67|10 = 6710 = (64 + 2 + 1)10 = 010000112
flip the bits
โโ
add 1
10111100 โโ 10111101.
So the 8-bit twoโs complement is 10111101.
25. |โ4|10 = 410 = 000001002
flip the bits
โโ
add 1
11111011 โโ 11111100. So the answer is 11111100.
26. |โ115|10 = 11510 = (64 + 32 + 16 + 2 + 1)10 = 011100112
flip the bits
โโ
add 1
10001100 โโ 10001101
So the 8-bit twoโs complement is 10001101.
27. Because the leading bit is 1, this is the 8-bit twoโs complement of a negative integer.
11010011
flip the bits
โโ
add 1
00101100 โโ 001011012 = (32 + 8 + 4 + 1)10 = |โ45|10 .
So the answer is โ45.
28. Because the leading bit is 1, this is the 8-bit twoโs complement of a negative integer. 10011001
add 1
01100110 โโ 011001112 = (64 + 32 + 4 + 2 + 1)10 = |โ103|10 . So the answer is โ103.
flip the bits
โโ
29. Because the leading bit is 1, this is the 8-bit twoโs complement of a negative integer.
11110010
flip the bits
โโ
add 1
00001101 โโ 000011102 = (8 + 4 + 2)10 = |โ14|10 .
So the answer is โ14.
30. Because the leading bit is 1, this is the 8-bit twoโs complement of a negative integer. 10111010
add 1
01000101 โโ 010001102 = (64 + 4 + 2)10 = |โ70|10 . So the answer is โ70.
flip the bits
31. 5710 = (32 + 16 + 8 + 1)10 = 1110012 โ 00111001
|โ118|10 = (64 + 32 + 16 + 4 + 2)10 = 011101102
flip the bits
โโ
add 1
10001001 โโ 10001010.
So the 8-bit twoโs complements of 57 and โ118 are 00111001 and 10001010. Adding the 8-bit
twoโs complements in binary notation gives
+
00111001
10001010
11000011
Since the leading bit of this number is a 1, the answer is negative. Converting back to decimal
flip the bits
add 1
form gives 11000011
โโ
00111100 โโ 001111012 = (32 + 16 + 8 + 4 + 1)10 = |61|10 .
So the answer is โ61.
32. 6210 = (32 + 16 + 8 + 4 + 2)10 = 1111102 โ 00111110
|โ18|10 = (16 + 2)10 = 00010010
flip the bits
โโ
add 1
11101101 โโ 11101110
Thus the 8-bit twoโs complements of 62 and โ18 are 00111110 and 10110111. Adding the 8-bit
twoโs complements in binary notation gives
+
00111110
11101110
00101100
Truncating the 1 in the 28 th position gives 00101100. Since the leading bit of this number is
a 0, the answer is positive. Converting back to decimal form gives
00101100 โ 1011002 = (32 + 8 + 4)10 = 4410 .
So the answer is 44.
โโ
Instructorโs Manual: Section 2.5
33. |โ6|10 = (4 + 2)10 = 1102
flip the bits
โโ
|โ73|10 = (64 + 8 + 1)10 = 01001001
39
add 1
00000110 โ 11111001 โโ 11111010
flip the bits
add 1
โโ
10110110 โโ 10110111
Thus the 8-bit twoโs complements of โ6 and โ73 are 11111010 and 10110111. Adding the
8-bit twoโs complements in binary notation gives
+
11111010
10110111
10110001
Truncating the 1 in the 28 th position gives 10110001. Since the leading bit of this number is
a 1, the answer is negative. Converting back to decimal form gives
10110001
flip the bits
โโ
add 1
01001110 โโ 010011112 = (64 + 8 + 4 + 2 + 1) = 7910 = |โ79|10
So the answer is โ79.
34. 8910 = (64 + 16 + 8 + 1)10 = 010110012
|โ55|10 = (32 + 16 + 4 + 2 + 1)10 = 001101112
flip the bits
โโ
add 1
11001000 โโ 11001001
So the 8-bit twoโs complements of 89 and โ55 are 01001111 and 11010101. Adding the 8-bit
twoโs complements in binary notation gives
01011001
11001001
100100010
+
Truncating the 1 in the 28 th position gives 00100010. Since the leading bit of this number is
a 0, the answer is positive. Converting back to decimal form gives
001000102 = (32 + 2)10 = 3410 .
So the answer is 34.
35. |โ15|10 = (8 + 4 + 2 + 1)10 = 000011112
flip the bits
|โ46|10 = (32 + 8 + 4 + 2)10 = 001011102
โโ
flip the bits
โโ
add 1
11110000 โโ 11110001
add 1
11010001 โโ 11010010
So the 8-bit twoโs complements of โ15 and โ46 are 11110001 and 10100010. Adding the 8-bit
twoโs complements in binary notation gives
+
11110001
11010010
111000011
Truncating the 1 in the 28 th position gives 11000011. Since the leading bit of this number is
a 1, the answer is negative. Converting back to decimal form gives
11000011
flip the bits
โโ
So the answer is โ61.
add 1
00111100 โโ 001111012 = โ(32 + 16 + 8 + 4 + 1)10 = |โ61|10 .
40
Solutions for Exercises: The Logic of Compound Statements
36. 12310 = (64 + 32 + 16 + 8 + 2 + 1)10 = 011110112
|โ94|10 = (64 + 16 + 8 + 4 + 2)10 = 010111102
flip the bits
add 1
โโ
10100001 โโ 10100010
So the 8-bit twoโs complements of 123 and โ94 are 01111011 and 10100010. Adding the 8-bit
twoโs complements in binary notation gives
+
01111011
10100010
100011101
Truncating the 1 in the 28 th position gives 00011101. Since the leading bit of this number is
a 0, the answer is positive. Converting back to decimal form gives
000111012 = (16 + 8 + 4 + 1)10 = 2910 .
So the answer is 29.
37. a. The 8-bit twoโs complement of โ128 is computed as follows:
|โ128|10 = 12810 = (27 )10
= 100000002
flip the bits
โโ
add 1
01111111 โโ 10000000.
So the 8-bit twoโs complement of โ128 is 10000000. If the twoโs complement procedure is
flip the bits
add 1
applied to this result, the following is obtained 10000000
โโ
01111111 โโ 10000000.
So the 8-bit twoโs complement of the 8-bit twoโs complement of โ128 is 10000000, which is
the 8-bit twoโs complement of โ128.
b. Suppose a, b, and a + b are integers in the range from 1 through 128. Then
1 โค a โค 128 = 27
1 โค b โค 128 = 27
1 โค a + b โค 128 = 27 .
Multiplying all parts of all three inequalities by โ1 gives
โ1 โฅ โa โฅ โ27
โ 1 โฅ โb โฅ โ27
โ 1 โฅ โ(a + b) โฅ โ27 .
Thus
28 โ (a + b) โฅ 28 โ 27 โฅ 27 (2 โ 1) = 27 ,
and
(28 โ a) + (28 โ b) = 28 + (28 โ (a + b)) โฅ 28 + 27 .
Therefore, the 8-bit twoโs complement of (28 โ a) + (28 โ b) has 1โs in both the 28 th and the
27 th positions. The 1 in the 28 th position is truncated, and the 1 in the 27 th position shows
that the sum is negative.
38. A2BC16 = 10ยท163 + 2ยท162 + 11ยท16 + 12 = 41,66010
39. E0D16 = 14ยท162 + 0 + 13 = 359710
40. 39EB16 = 3ยท163 + 9ยท162 + 14ยท16 + 11 = 14, 82710
41. 0001 1100 0000 1010 1011 11102
42. B53DF 816 = 1011 0101 0011 1101 1111 10002
43. 4ADF 8316 = 0100 1010 1101 1111 1000 00112
44. 2E16
45. 1011 0111 1100 01012 = B7C516
Instructorโs Manual: Section 2.5
41
46. 1011 0111 1100 01012 = B7C516
47. a. 6ยท84 + 1ยท83 + 5ยท82 + 0ยท8 + 2ยท1 = 25,41010
b. 207638 = 2ยท84 + 0ยท83 + 7ยท82 + 6ยท8 + 3 = 8, 69110
c. To convert an integer from octal to binary notation:
(i) Write each octal digit of the integer in ๏ฌxed 3-bit binary notation (and include leading zeros
as needed). Note that
octal digit
3-bit binary equivalent
0
000
1
001
2
010
3
011
4
100
5
101
6
110
7
111
(ii) Juxtapose the results.
As an example, consider converting 615028 to binary notation:
68 = 1102 18 = 0012 58 = 1012 08 = 0002 28 = 0102 .
So in binary notation the integer should be 110 001 101 000 0102 . This result can be checked by
writing the integer in decimal notation and comparing it to the answer obtained in part (a):
110 001 101 000 0102 = (1 ยท 214 + 1 ยท 213 + 1 ยท 29 + 1 ยท 28 + 1 ยท 26 + 1 ยท 2)10 = 2541010 .
This is the same as the answer obtained in part (a). So the two methods give the same result.
To convert an integer from binary to octal notation:
(i) Group the digits of the binary number into sets of three, starting from the right and adding
leading zeros as needed:
(ii) Convert the binary numbers in each set of three into octal digits;
(iii) Juxtapose those octal digits.
As an example consider converting 11010111012 to octal notation. Grouping the binary digits
in sets of three and adding two leading zeros gives
001 101 011 101.
To convert each group into an octal digit, note that
0012 = 18 1012 = 58 0112 = 38 1012 = 58 .
So the octal version of the integer should be 15358 . To check this result, observe that
1 101 011 1012 = (1 ยท 29 + 1 ยท 28 + 1 ยท 26 + 1 ยท 24 + 1 ยท 23 + 1 ยท 22 + 1)10 = 86110
and
15358 = (1 ยท 83 + 5 ยท 82 + 3 ยท 8 + 5)10 = 86110
also. So the two methods give the same result.
Document Preview (41 of 732 Pages)
You are viewing preview pages of the document. Purchase to get full access instantly.
-37%
Solution Manual For Discrete Mathematics With Applications, 5th Edition
$18.99 Save:$11.00(37%)
Store
Isabella Jones
Best Selling
Test Bank for Strategies For Reading Assessment And Instruction: Helping Every Child Succeed, 6th Edition
$18.99 Save:$11.00(37%)
Chemistry: Principles And Reactions, 7th Edition Test Bank
$18.99 Save:$11.00(37%)
Test Bank for Hospitality Facilities Management and Design, 4th Edition
$18.99 Save:$11.00(37%)
Solution Manual for Designing the User Interface: Strategies for Effective Human-Computer Interaction, 6th Edition
$18.99 Save:$11.00(37%)
The World Of Customer Service, 3rd Edition Test Bank
$18.99 Save:$11.00(37%)
2023-2024 ATI Pediatrics Proctored Exam with Answers (139 Solved Questions)
$18.99 Save:$11.00(37%)
