Page 43 - Discrete Mathematics and Its Applications

22 1 / The Foundations: Logic and Proofs

p p ∨ ¬r
r
¬r
(p ∨ ¬r) ∧ (¬p ∨ (q ∨ ¬r))
¬p
p
q ¬p ∨ (q ∨ ¬r)
r q ∨ ¬r
¬r

FIGURE 3 The circuit for (p ∨¬r) ∧ (¬p ∨ (q ∨¬r)).

Exercises

In Exercises 1–6, translate the given statement into proposi- “You have a 64-bit processor,” g 1 : “Your processor runs
tional logic using the propositions provided. at 1 GHz or faster,” g 2 : “Your processor runs at 2 GHz or
1. You cannot edit a protected Wikipedia entry unless you faster,” r 1 : “Your processor has at least 1 GB RAM,” r 2 :
are an administrator. Express your answer in terms of e: “Your processor has at least 2 GB RAM,” h 16 :“Youhave
“You can edit a protected Wikipedia entry” and a:“You at least 16 GB free hard disk space,” and h 32 :“Youhave
are an administrator.” at least 32 GB free hard disk space.”
2. You can see the movie only if you are over 18 years old 7. Express these system specifications using the proposi-
or you have the permission of a parent. Express your an- tions p “The message is scanned for viruses” and q “The
swer in terms of m: “You can see the movie,” e: “You are message was sent from an unknown system” together
over 18 years old,” and p: “You have the permission of a with logical connectives (including negations).
parent.”
a) “The message is scanned for viruses whenever the
3. You can graduate only if you have completed the require- message was sent from an unknown system.”
ments of your major and you do not owe money to the b) “The message was sent from an unknown system but
university and you do not have an overdue library book. it was not scanned for viruses.”
Express your answer in terms of g: “You can graduate,”
m: “You owe money to the university,” r: “You have com- c) “It is necessary to scan the message for viruses when-
pleted the requirements of your major,” and b:“Youhave ever it was sent from an unknown system.”
an overdue library book.” d) “When a message is not sent from an unknown system
4. To use the wireless network in the airport you must pay it is not scanned for viruses.”
the daily fee unless you are a subscriber to the service. 8. Express these system specifications using the proposi-
Express your answer in terms of w: “You can use the wire- tions p “The user enters a valid password,” q “Access is
less network in the airport,” d: “You pay the daily fee,” granted,” and r “The user has paid the subscription fee”
and s: “You are a subscriber to the service.” and logical connectives (including negations).
5. You are eligible to be President of the U.S.A. only if you a) “The user has paid the subscription fee, but does not
are at least 35 years old, were born in the U.S.A, or at the enter a valid password.”
time of your birth both of your parents were citizens, and
b) “Access is granted whenever the user has paid the
you have lived at least 14 years in the country. Express
subscription fee and enters a valid password.”
your answer in terms of e: “You are eligible to be Pres-
c) “Access is denied if the user has not paid the subscrip-
ident of the U.S.A.,” a: “You are at least 35 years old,”
tion fee.”
b: “You were born in the U.S.A,” p: “At the time of your
birth, both of your parents where citizens,” and r:“You d) “If the user has not entered a valid password but has
have lived at least 14 years in the U.S.A.” paid the subscription fee, then access is granted.”
6. You can upgrade your operating system only if you have 9. Are these system specifications consistent? “The system
a 32-bit processor running at 1 GHz or faster, at least is in multiuser state if and only if it is operating normally.
1 GB RAM, and 16 GB free hard disk space, or a 64- If the system is operating normally, the kernel is func-
bit processor running at 2 GHz or faster, at least 2 GB tioning. The kernel is not functioning or the system is
RAM, and at least 32 GB free hard disk space. Express in interrupt mode. If the system is not in multiuser state,
you answer in terms of u: “You can upgrade your oper- then it is in interrupt mode. The system is not in interrupt
ating system,” b 32 : “You have a 32-bit processor,” b 64 : mode.”