CMPS 211 Chapter 1 Solutions, Fall 2013
American University of Beirut · Discrete Structures · 33 pages · with solution
Showing the first 10 of 33 pages. Download the PDF to see all of it.
More CMPS 211 files
- Exam 1 · Fall 2017ExamView
- Lecture Chp 1 · Fall 2017LabView
- Lecture Chp 3 · Fall 2017LabView
- Lecture Chp 2 · Fall 2017LabView
- Lecture Chp 4 · Fall 2017LabView
- Homework 6 with Solution · Spring 2016Homework · with solutionView
- Exam 1 with Solution · Spring 2016Exam · with solutionView
- Homework 1 with Solution · Spring 2016Homework · with solutionView
Show the text of this chapter
Section 1.1
Propositional Logic
1
CHAPTER 1
The Foundations: Logic and Proofs
SECTION 1.1
Propositional Logic
2. Propositions must have clearly defined truth values, so a proposition must be a declarative sentence with no
free variables.
a) This is not a proposition; it’s a command.
b) This is not a proposition; it’s a question.
c) This is a proposition that is false, as anyone who has been to Maine knows.
d) This is not a proposition; its truth value depends on the value of x.
e) This is a proposition that is false.
f) This is not a proposition; its truth value depends on the value of n.
4. a) I did not buy a lottery ticket this week.
b) Either I bought a lottery ticket this week or [in the inclusive sense] I won the million dollar jackpot on
Friday.
c) If I bought a lottery ticket this week, then I won the million dollar jackpot on Friday.
d) I bought a lottery ticket this week and I won the million dollar jackpot on Friday.
e) I bought a lottery ticket this week if and only if I won the million dollar jackpot on Friday.
f) If I did not buy a lottery ticket this week, then I did not win the million dollar jackpot on Friday.
g) I did not buy a lottery ticket this week, and I did not win the million dollar jackpot on Friday.
h) Either I did not buy a lottery ticket this week, or else I did buy one and won the million dollar jackpot on
Friday.
6. a) The election is not decided.
b) The election is decided, or the votes have been counted.
c) The election is not decided, and the votes have been counted.
d) If the votes have been counted, then the election is decided.
e) If the votes have not been counted, then the election is not decided.
f) If the election is not decided, then the votes have not been counted.
g) The election is decided if and only if the votes have been counted.
h) Either the votes have not been counted, or else the election is not decided and the votes have been counted.
Note that we were able to incorporate the parentheses by using the words either and else.
8. a) If you have the flu, then you miss the final exam.
b) You do not miss the final exam if and only if you pass the course.
c) If you miss the final exam, then you do not pass the course.
d) You have the flu, or miss the final exam, or pass the course.
e) It is either the case that if you have the flu then you do not pass the course or the case that if you miss
the final exam then you do not pass the course (or both, it is understood).
f) Either you have the flu and miss the final exam, or you do not miss the final exam and do pass the course.
2
Chapter 1
The Foundations: Logic and Proofs
10. a) r ∧ ¬q
b) p ∧ q ∧ r
c) r → p
d) p ∧ ¬q ∧ r
e) (p ∧ q) → r
f) r ↔ (q ∨ p)
12. a) This is T ↔ T, which is true.
b) This is T ↔ F, which is false.
c) This is F ↔ F, which is true.
d) This is F ↔ T, which is false.
14. a) This is F → F, which is true.
b) This is F → F, which is true.
c) This is T → F, which is false.
d) This is T → T, which is true.
16. a) The employer making this request would be happy if the applicant knew both of these languages, so this
is clearly an inclusive or.
b) The restaurant would probably charge extra if the diner wanted both of these items, so this is an exclusive
or.
c) If a person happened to have both forms of identification, so much the better, so this is clearly an inclusive
or.
d) This could be argued either way, but the inclusive interpretation seems more appropriate. This phrase
means that faculty members who do not publish papers in research journals are likely to be fired from their
jobs during the probationary period. On the other hand, it may happen that they will be fired even if they
do publish (for example, if their teaching is poor).
18. a) The necessary condition is the conclusion: If you get promoted, then you wash the boss’s car.
b) If the winds are from the south, then there will be a spring thaw.
c) The sufficient condition is the hypothesis: If you bought the computer less than a year ago, then the
warranty is good.
d) If Willy cheats, then he gets caught.
e) The “only if” condition is the conclusion: If you access the website, then you must pay a subscription fee.
f) If you know the right people, then you will be elected.
g) If Carol is on a boat, then she gets seasick.
20. a) If I am to remember to send you the address, then you will have to send me an e-mail message. (This has
been slightly reworded so that the tenses make more sense.)
b) If you were born in the United States, then you are a citizen of this country.
c) If you keep your textbook, then it will be a useful reference in your future courses. (The word “then” is
understood in English, even if omitted.)
d) If their goaltender plays well, then the Red Wings will win the Stanley Cup.
e) If you get the job, then you had the best credentials.
f) If there is a storm, then the beach erodes.
g) If you log on to the server, then you have a valid password.
h) If you do not begin your climb too late, then you will reach the summit.
22. a) You will get an A in this course if and only if you learn how to solve discrete mathematics problems.
b) You will be informed if and only if you read the newspaper every day. (It sounds better in this order; it
would be logically equivalent to state this as “You read the newspaper every day if and only if you will be
informed.”)
Section 1.1
Propositional Logic
3
c) It rains if and only if it is a weekend day.
d) You can see the wizard if and only if he is not in.
24. a) Converse: If I stay home, then it will snow tonight. Contrapositive: If I do not stay at home, then it will
not snow tonight. Inverse: If it does not snow tonight, then I will not stay home.
b) Converse: Whenever I go to the beach, it is a sunny summer day. Contrapositive: Whenever I do not go
to the beach, it is not a sunny summer day. Inverse: Whenever it is not a sunny day, I do not go to the beach.
c) Converse: If I sleep until noon, then I stayed up late. Contrapositive: If I do not sleep until noon, then I
did not stay up late. Inverse: If I don’t stay up late, then I don’t sleep until noon.
26. A truth table will need 2n rows if there are n variables.
a) 22 = 4
b) 23 = 8
c) 26 = 64
d) 25 = 32
28. To construct the truth table for a compound proposition, we work from the inside out. In each case, we will
show the intermediate steps. In part (d), for example, we first construct the truth tables for p ∧ q and for
p ∨ q and combine them to get the truth table for (p ∧ q) → (p ∨ q). For parts (a) and (b) we have the
following table (column three for part (a), column four for part (b)).
p
¬p
p → ¬p
p ↔ ¬p
T
F
F
F
F
T
T
F
For parts (c) and (d) we have the following table.
p
q
p ∨ q
p ∧ q
p ⊕ (p ∨ q)
(p ∧ q) → (p ∨ q)
T
T
T
T
F
T
T
F
T
F
F
T
F
T
T
F
T
T
F
F
F
F
F
T
For part (e) we have the following table.
p
q
¬p
q → ¬p
p ↔ q
(q → ¬p) ↔ (p ↔ q)
T
T
F
F
T
F
T
F
F
T
F
F
F
T
T
T
F
F
F
F
T
T
T
T
For part (f) we have the following table.
p
q
¬q
p ↔ q
p ↔ ¬q
(p ↔ q) ⊕ (p ↔ ¬q)
T
T
F
T
F
T
T
F
T
F
T
T
F
T
F
F
T
T
F
F
T
T
F
T
30. For parts (a) and (b) we have the following table (column two for part (a), column four for part (b)).
p
p ⊕ p
¬p
p ⊕ ¬p
T
F
F
T
F
F
T
T
For parts (c) and (d) we have the following table (columns five and six).
p
q
¬p
¬q
p ⊕ ¬q
¬p ⊕ ¬q
T
T
F
F
T
F
T
F
F
T
F
T
F
T
T
F
F
T
F
F
T
T
T
F
4
Chapter 1
The Foundations: Logic and Proofs
For parts (e) and (f) we have the following table (columns five and six). This time we have omitted the column
explicitly showing the negation of q. Note that the first is a tautology and the second is a contradiction (see
definitions in Section 1.2).
p
q
p ⊕ q
p ⊕ ¬q
(p ⊕ q) ∨ (p ⊕ ¬q)
(p ⊕ q) ∧ (p ⊕ ¬q)
T
T
F
T
T
F
T
F
T
F
T
F
F
T
T
F
T
F
F
F
F
T
T
F
32. For parts (a) and (b), we have
p
q
r
p ∨ q
(p ∨ q) ∨ r
(p ∨ q) ∧ r
T
T
T
T
T
T
T
T
F
T
T
F
T
F
T
T
T
T
T
F
F
T
T
F
F
T
T
T
T
T
F
T
F
T
T
F
F
F
T
F
T
F
F
F
F
F
F
F
For parts (c) and (d), we have
p
q
r
p ∧ q
(p ∧ q) ∨ r
(p ∧ q) ∧ r
T
T
T
T
T
T
T
T
F
T
T
F
T
F
T
F
T
F
T
F
F
F
F
F
F
T
T
F
T
F
F
T
F
F
F
F
F
F
T
F
T
F
F
F
F
F
F
F
Finally, for parts (e) and (f) we have
p
q
r
¬r
p ∨ q
(p ∨ q) ∧ ¬r
p ∧ q
(p ∧ q) ∨ ¬r
T
T
T
F
T
F
T
T
T
T
F
T
T
T
T
T
T
F
T
F
T
F
F
F
T
F
F
T
T
T
F
T
F
T
T
F
T
F
F
F
F
T
F
T
T
T
F
T
F
F
T
F
F
F
F
F
F
F
F
T
F
F
F
T
34. This time the truth table needs 24 = 16 rows.
Section 1.1
Propositional Logic
5
p
q
r
s
p → q
(p → q) → r
((p → q) → r) → s
T
T
T
T
T
T
T
T
T
T
F
T
T
F
T
T
F
T
T
F
T
T
T
F
F
T
F
T
T
F
T
T
F
T
T
T
F
T
F
F
T
F
T
F
F
T
F
T
T
T
F
F
F
F
T
F
F
T
T
T
T
T
T
F
T
T
F
T
T
F
F
T
F
T
T
F
T
F
T
F
F
T
F
T
F
F
T
T
T
T
T
F
F
T
F
T
T
F
F
F
F
T
T
F
T
F
F
F
F
T
F
T
36. a) Since the condition is true, the statement is executed, so x is incremented and now has the value 2.
b) Since the condition is false, the statement is not executed, so x is not incremented and now still has the
value 1.
c) Since the condition is true, the statement is executed, so x is incremented and now has the value 2.
d) Since the condition is false, the statement is not executed, so x is not incremented and now still has the
value 1.
e) Since the condition is true when it is encountered (since x = 1), the statement is executed, so x is
incremented and now has the value 2. (It is irrelevant that the condition is now false.)
38. a) 1 1000 ∧ (0 1011 ∨ 1 1011) = 1 1000 ∧ 1 1011 = 1 1000
b) (0 1111 ∧ 1 0101) ∨ 0 1000 = 0 0101 ∨ 0 1000 = 0 1101
c) (0 1010 ⊕ 1 1011) ⊕ 0 1000 = 1 0001 ⊕ 0 1000 = 1 1001
d) (1 1011 ∨ 0 1010) ∧ (1 0001 ∨ 1 1011) = 1 1011 ∧ 1 1011 = 1 1011
40. The truth value of “Fred and John are happy” is min(0.8, 0.4) = 0.4. The truth value of “Neither Fred nor
John is happy” is min(0.2, 0.6) = 0.2, since this statement means “Fred is not happy, and John is not happy,”
and we computed the truth values of the two propositions in this conjunction in Exercise 35.
42. This cannot be a proposition, because it cannot have a truth value. Indeed, if it were true, then it would
be truly asserting that it is false, a contradiction; on the other hand if it were false, then its assertion that
it is false must be false, so that it would be true—again a contradiction. Thus this string of letters, while
appearing to be a proposition, is in fact meaningless.
44. No. This is a classical paradox. (We will use the male pronoun in what follows, assuming that we are talking
about males shaving their beards here, and assuming that all men have facial hair. If we restrict ourselves to
beards and allow female barbers, then the barber could be female with no contradiction.) If such a barber
existed, who would shave the barber? If the barber shaved himself, then he would be violating the rule that
he shaves only those people who do not shave themselves. On the other hand, if he does not shave himself,
then the rule says that he must shave himself. Neither is possible, so there can be no such barber.
46. a) If the explorer (a woman, so that our pronouns will not get confused here—the cannibals will be male)
encounters a truth-teller, then he will honestly answer “no” to her question. If she encounters a liar, then the
6
Chapter 1
The Foundations: Logic and Proofs
honest answer to her question is “yes,” so he will lie and answer “no.” Thus everybody will answer “no” to
the question, and the explorer will have no way to determine which type of cannibal she is speaking to.
b) There are several possible correct answers. One is the following question: “If I were to ask you if you
always told the truth, would you say that you did?” Then if the cannibal is a truth teller, he will answer yes
(truthfully), while if he is a liar, then, since in fact he would have said that he did tell the truth if questioned,
he will now lie and answer no.
48. a) “But” means “and”: r ∧ ¬p.
b) “Whenever” means “if”: (r ∧ p) → q.
c) Access being denied is the negation of q, so we have ¬r → ¬q.
d) The hypothesis is a conjunction: (¬p ∧ r) → q.
50. We write these symbolically: u → ¬a, a → s, ¬s → ¬u. Note that we can make all the conclusion true by
making a false, s true, and u false. Therefore if the users cannot access the file system, they can save new
files, and the system is not being upgraded, then all the conditional statements are true. Thus the system is
consistent.
52. This system is consistent. We use L, Q, N , and B to stand for the basic propositions here, “The file system
is locked,” “New messages will be queued,” “The system is functioning normally,” and “New messages will
be sent to the message buffer,” respectively. Then the given specifications are ¬L → Q, ¬L ↔ N , ¬Q → B ,
¬L → B, and ¬B. If we want consistency, then we had better have B false in order that ¬B be true. This
requires that both L and Q be true, by the two conditional statements that have B as their consequence. The
first conditional statement therefore is of the form F → T, which is true. Finally, the biconditional ¬L ↔ N
can be satisfied by taking N to be false. Thus this set of specifications is consistent. Note that there is just
this one satisfying truth assignment.
54. This is similar to Example 17, about universities in New Mexico. To search for hiking in West Virginia, we
could enter WEST AND VIRGINIA AND HIKING. If we enter (VIRGINIA AND HIKING) NOT WEST,
then we’ll get websites about hiking in Virginia but not in West Virginia, except for sites that happen to use
the word “west” in a different context (e.g., “Follow the stream west until you come to a clearing”).
56. If A is a knight, then his statement that both of them are knights is true, and both will be telling the truth.
But that is impossible, because B is asserting otherwise (that A is a knave). If A is a knave, then B ’s
assertion is true, so he must be a knight, and A’s assertion is false, as it should be. Thus we conclude that A
is a knave and B is a knight.
58. We can draw no conclusions. A knight will declare himself to be a knight, telling the truth. A knave will lie
and assert that he is a knight. Since everyone will say “I am a knight,” we can determine nothing.
60. a) We look at the three possibilities of who the innocent men might be. If Smith and Jones are innocent
(and therefore telling the truth), then we get an immediate contradiction, since Smith said that Jones was a
friend of Cooper, but Jones said that he did not even know Cooper. If Jones and Williams are the innocent
truth-tellers, then we again get a contradiction, since Jones says that he did not know Cooper and was out
of town, but Williams says he saw Jones with Cooper (presumably in town, and presumably if we was with
him, then he knew him). Therefore it must be the case that Smith and Williams are telling the truth. Their
statements do not contradict each other. Based on Williams’ statement, we know that Jones is lying, since he
said that he did not know Cooper when in fact he was with him. Therefore Jones is the murderer.
Section 1.2
Propositional Equivalences
7
b) This is just like part (a), except that we are not told ahead of time that one of the men is guilty. Can
none of them be guilty? If so, then they are all telling the truth, but this is impossible, because as we just
saw, some of the statements are contradictory. Can more than one of them be guilty? If, for example, they
are all guilty, then their statements give us no information. So that is certainly possible.
62. This information is enough to determine the entire system.
Let each letter stand for the statement that
the person whose name begins with that letter is chatting. Then the given information can be expressed
symbolically as follows: ¬K → H , R → ¬V , ¬R → V , A → R, V → K , K → V , H → A, H → K .
Note that we were able to convert all of these statements into conditional statements. In what follows we will
sometimes make use of the contrapositives of these conditional statements as well. First suppose that H is
true. Then it follows that A and K are true, whence it follows that R and V are true. But R implies that
V is false, so we get a contradiction. Therefore H must be false. From this it follows that K is true; whence
V is true, and therefore R is false, as is A. We can now check that this assignment leads to a true value for
each conditional statement. So we conclude that Kevin and Vijay are chatting but Heather, Randy, and Abby
are not.
64. Note that Diana’s statement is merely that she didn’t do it.
a) John did it. There are four cases to consider. If Alice is the sole truth-teller, then Carlos did it; but this
means that John is telling the truth, a contradiction. If John is the sole truth-teller, then Diana must be
lying, so she did it, but then Carlos is telling the truth, a contradiction. If Carlos is the sole truth-teller, then
Diana did it, but that makes John truthful, again a contradiction. So the only possibility is that Diana is the
sole truth-teller. This means that John is lying when he denied it, so he did it. Note that in this case both
Alice and Carlos are indeed lying.
b) Again there are four cases to consider. Since Carlos and Diana are making contradictory statements, the
liar must be one of them (we could have used this approach in part (a) as well). Therefore Alice is telling the
truth, so Carlos did it. Note that John and Diana are telling the truth as well here, and it is Carlos who is
lying.
SECTION 1.2
Propositional Equivalences
2. There are two cases. If p is true, then ¬(¬p) is the negation of a false proposition, hence true. Similarly, if p
is false, then ¬(¬p) is also false. Therefore the two propositions are logically equivalent.
4. a) We construct the relevant truth table and note that the fifth and seventh columns are identical.
p
q
r
p ∨ q
(p ∨ q) ∨ r
q ∨ r
p ∨ (q ∨ r)
T
T
T
T
T
T
T
T
T
F
T
T
T
T
T
F
T
T
T
T
T
T
F
F
T
T
F
T
F
T
T
T
T
T
T
F
T
F
T
T
T
T
F
F
T
F
T
T
T
F
F
F
F
F
F
F
b) Again we construct the relevant truth table and note that the fifth and seventh columns are identical.
8
Chapter 1
The Foundations: Logic and Proofs
p
q
r
p ∧ q
(p ∧ q) ∧ r
q ∧ r
p ∧ (q ∧ r)
T
T
T
T
T
T
T
T
T
F
T
F
F
F
T
F
T
F
F
F
F
T
F
F
F
F
F
F
F
T
T
F
F
T
F
F
T
F
F
F
F
F
F
F
T
F
F
F
F
F
F
F
F
F
F
F
6. We see that the fourth and seventh columns are identical.
p
q
p ∧ q
¬(p ∧ q)
¬p
¬q
¬p ∨ ¬q
T
T
T
F
F
F
F
T
F
F
T
F
T
T
F
T
F
T
T
F
T
F
F
F
T
T
T
T
8. We need to negate each part and swap “and” with “or.”
a) Kwame will not take a job in industry and will not go to graduate school.
b) Yoshiko does not know Java or does not know calculus.
c) James is not young, or he is not strong.
d) Rita will not move to Oregon and will not move to Washington.
10. We construct a truth table for each conditional statement and note that the relevant column contains only
T’s. For part (a) we have the following table.
p
q
¬p
p ∨ q
¬p ∧ (p ∨ q)
[¬p ∧ (p ∨ q)] → q
T
T
F
T
F
T
T
F
F
T
F
T
F
T
T
T
T
T
F
F
T
F
F
T
For part (b) we have the following table. We omit the columns showing p → q and q → r so that the table
will fit on the page.
p
q
r
(p → q) → (q → r)
q → r
[(p → q) → (q → r)] → (p → r)
T
T
T
T
T
T
T
T
F
F
T
T
T
F
T
T
T
F
T
F
F
F
F
T
F
T
T
T
T
T
F
T
F
F
T
F
F
F
T
T
T
F
F
F
F
T
T
T
For part (c) we have the following table.
p
q
p → q
p ∧ (p → q)
[p ∧ (p → q)] → q
T
T
T
T
T
T
F
F
F
T
F
T
T
F
T
F
F
T
F
T
For part (d) we have the following table. We have omitted some of the intermediate steps to make the table
fit.
Section 1.2
Propositional Equivalences
9
p
q
r
(p ∨ q) ∧ (p → r) ∧ (p → r)
[(p ∨ q) ∧ (p → r) ∧ (p → r)] → r
T
T
T
T
T
T
T
F
F
T
T
F
T
T
T
T
F
F
F
T
F
T
T
T
T
F
T
F
F
T
F
F
T
F
T
F
F
F
F
T
12. We argue directly by showing that if the hypothesis is true, then so is the conclusion. An alternative approach,
which we show only for part (a), is to use the equivalences listed in the section and work symbolically.
a) Assume the hypothesis is true. Then p is false. Since p ∨ q is true, we conclude that q must be true. Here
is a more “algebraic” solution: [¬p∧(p∨q)] → q ≡ ¬[¬p∧(p∨q)]∨q ≡ ¬¬p∨¬(p∨q)]∨q ≡ p∨¬(p∨q)∨q ≡
(p∨q)∨¬(p∨q) ≡ T. The reasons for these logical equivalences are, respectively, Table 7, line 1; De Morgan’s
law; double negation; commutative and associative laws; negation law.
b) We want to show that if the entire hypothesis is true, then the conclusion p → r is true. To do this, we
need only show that if p is true, then r is true. Suppose p is true. Then by the first part of the hypothesis,
we conclude that q is true. It now follows from the second part of the hypothesis that r is true, as desired.
c) Assume the hypothesis is true. Then p is true, and since the second part of the hypothesis is true, we
conclude that q is also true, as desired.
d) Assume the hypothesis is true. Since the first part of the hypothesis is true, we know that either p or q
is true. If p is true, then the second part of the hypothesis tells us that r is true; similarly, if q is true, then
the third part of the hypothesis tells us that r is true. Thus in either case we conclude that r is true.
14. This is not a tautology. It is saying that knowing that the hypothesis of an conditional statement is false
allows us to conclude that the conclusion is also false, and we know that this is not valid reasoning. To show
that it is not a tautology, we need to find truth assignments for p and q that make the entire proposition
false. Since this is possible only if the conclusion if false, we want to let q be true; and since we want the
hypothesis to be true, we must also let p be false. It is easy to check that if, indeed, p is false and q is true,
then the conditional statement is false. Therefore it is not a tautology.
16. The first of these propositions is true if and only if p and q have the same truth value. The second is true if
and only if either p and q are both true, or p and q are both false. Clearly these two conditions are saying
the same thing.
18. It is easy to see from the definitions of conditional statement and negation that each of these propositions
is false in the case in which p is true and q is false, and true in the other three cases. Therefore the two
propositions are logically equivalent.
20. It is easy to see from the definitions of the logical operations involved here that each of these propositions is
true in the cases in which p and q have the same truth value, and false in the cases in which p and q have
opposite truth values. Therefore the two propositions are logically equivalent.
22. Suppose that (p → q) ∧ (p → r) is true. We want to show that p → (q ∧ r) is true, which means that we
want to show that q ∧ r is true whenever p is true. If p is true, since we know that both p → q and p → r
are true from our assumption, we can conclude that q is true and that r is true. Therefore q ∧ r is true, as
desired. Conversely, suppose that p → (q ∧ r) is true. We need to show that p → q is true and that p → r is
true, which means that if p is true, then so are q and r. But this follows from p → (q ∧ r).
10
Chapter 1
The Foundations: Logic and Proofs
24. We determine exactly which rows of the truth table will have T as their entries. Now (p → q) ∨ (p → r) will
be true when either of the conditional statements is true. The conditional statement will be true if p is false,
or if q in one case or r in the other case is true, i.e., when q ∨ r is true, which is precisely when p → (q ∨ r)
is true. Since the two propositions are true in exactly the same situations, they are logically equivalent.
26. Applying the third and first equivalences in Table 7, we have ¬p → (q → r) ≡ p ∨ (q → r) ≡ p ∨ ¬q ∨ r.
Applying the first equivalence in Table 7 to q → (p ∨ r) shows that ¬q ∨ p ∨ r is equivalent to it. But these
are equivalent by the commutative and associative laws.
28. We know that p ↔ q is true precisely when p and q have the same truth value. But this happens precisely
when ¬p and ¬q have the same truth value, that is, ¬p ↔ ¬q.
30. The conclusion q ∨ r will be true in every case except when q and r are both false. But if q and r are both
false, then one of p ∨ q or ¬p ∨ r is false, because one of p or ¬p is false. Thus in this case the hypothesis
(p ∨ q) ∧ (¬p ∨ r) is false. An conditional statement in which the conclusion is true or the hypothesis is false
is true, and that completes the argument.
32. We just need to find an assignment of truth values that makes one of these propositions true and the other
false. We can let p be true and the other two variables be false. Then the first statement will be F → F,
which is true, but the second will be F ∧ T, which is false.
34. We apply the rules stated in the preamble.
a) p ∧ ¬q
b) p ∨ (q ∧ (r ∨ F))
c) (p ∨ ¬q) ∧ (q ∨ T)
36. If s has any occurrences of ∧, ∨, T, or F, then the process of forming the dual will change it. Therefore
s∗ = s if and only if s is simply one propositional variable (like p). A more difficult question is to determine
when s∗ will be logically equivalent to s. For example, p ∨ F is logically equivalent to its dual p ∧ T, because
both are logically equivalent to p.
38. The table is in fact displayed so as to exhibit the duality. The two identity laws are duals of each other, the
two domination laws are duals of each other, etc. The only law not listed with another, the double negation
law, is its own dual, since there are no occurrences of ∧, ∨, T, or F to replace.
40. Following the hint, we easily see that the answer is p ∧ q ∧ ¬r.
42. The statement of the problem is really the solution. Each line of the truth table corresponds to exactly one
combination of truth values for the n atomic propositions involved. We can write down a conjunction that
is true precisely in this case, namely the conjunction of all the atomic propositions that are true and the
negations of all the atomic propositions that are false. If we do this for each line of the truth table for which
the value of the compound proposition is to be true, and take the disjunction of the resulting propositions,
then we have the desired proposition in its disjunctive normal form.
44. Given a compound proposition p, we can, by Exercise 43, write down a proposition q that is logically equivalent
to p and uses only ¬, ∧, and ∨. Now by De Morgan’s law we can get rid of all the ∨’s by replacing each
occurrence of p1 ∨ p2 ∨ · · · ∨ pn with ¬(¬p1 ∧ ¬p2 ∧ · · · ∧ ¬pn).
46. We write down the truth table corresponding to the definition.
p
q
p | q
T
T
F
T
F
T
F
T
T
F
F
T
Section 1.2
Propositional Equivalences
11
48. We write down the truth table corresponding to the definition.
p
q
p ↓ q
T
T
F
T
F
F
F
T
F
F
F
T
50. a) From the definition (or as seen in the truth table constructed in Exercise 48), p ↓ p is false when p is true
and true when p is false, exactly as ¬p is; thus the two are logically equivalent.
b) The proposition (p ↓ q) ↓ (p ↓ q) is equivalent, by part (a), to ¬(p ↓ q), which from the definition (or
truth table or Exercise 49) is clearly equivalent to p ∨ q.
c) By Exercise 45, every compound proposition is logically equivalent to one that uses only ¬ and ∨. But
by parts (a) and (b) of the present exercise, we can get rid of all the negations and disjunctions by using
NOR’s. Thus every compound proposition can be converted into a logically equivalent compound proposition
involving only NOR’s.
52. This exercise is similar to Exercise 50. First we can see from the truth tables that (p | p) ≡ (¬p) and that
((p | p) | (q | q)) ≡ (p ∨ q). Then we argue exactly as in part (c) of Exercise 50: by Exercise 45, every
compound proposition is logically equivalent to one that uses only ¬ and ∨. But by our observations at the
beginning of the present exercise, we can get rid of all the negations and disjunctions by using NAND’s. Thus
every compound proposition can be converted into a logically equivalent compound proposition involving only
NAND’s.
54. To show that these are not logically equivalent, we need only find one assignment of truth values to p, q, and
r for which the truth values of p | (q | r) and (p | q) | r differ. One such assignment is T for p and F for q
and r. Then computing from the truth tables (or definitions), we see that p | (q | r) is false and (p | q) | r is
true.
56. To say that p and q are logically equivalent is to say that the truth tables for p and q are identical; similarly,
to say that q and r are logically equivalent is to say that the truth tables for q and r are identical. Clearly
if the truth tables for p and q are identical, and the truth tables for q and r are identical, then the truth
tables for p and r are identical (this is a fundamental axiom of the notion of equality). Therefore p and r are
logically equivalent. (We are assuming—and there is no loss of generality in doing so—that the same atomic
variables appear in all three propositions.)
58. If we want the first two of these to be true, then p and q must have the same truth value. If q is true, then
the third and fourth expressions will be true, and if r is false, the last expression will be true. So all five of
these disjunctions will be true if we set p and q to be true, and r to be false.
60. In each case we hunt for truth assignments that make all the disjunctions true.
a) Since p occurs in four of the five disjunctions, we can make p true, and then make q false (and make r
and s anything we please). Thus this proposition is satisfiable.
b) This is satisfiable by, for example, setting p to be false (that takes care of the first, second, and fourth
disjunctions), s to be false (for the third and sixth disjunctions), q to be true (for the fifth disjunction), and
r to be anything.
c) It is not hard to find a satisfying truth assignment, such as p, q, and s true, and r false.
12
Chapter 1
The Foundations: Logic and Proofs
SECTION 1.3
Predicates and Quantifiers
2. a) This is true, since there is an a in orange.
b) This is false, since there is no a in lemon.
c) This is false, since there is no a in true.
d) This is true, since there is an a in false.
4. a) Here x is still equal to 0, since the condition is false.
b) Here x is still equal to 1, since the condition is false.
c) This time x is equal to 1 at the end, since the condition is true, so the statement x := 1 is executed.
6. T