Page 76 - Discrete Mathematics and Its Applications

1.4 Predicates and Quantifiers 55

32. Express each of these statements using quantifiers. Then Exercises 38–42 deal with the translation between system
form the negation of the statement so that no negation is specification and logical expressions involving quantifiers.
to the left of a quantifier. Next, express the negation in 38. Translate these system specifications into English where
simple English. (Do not simply use the phrase “It is not the predicate S(x, y) is “x is in state y” and where the
the case that.”)
domain for x and y consists of all systems and all possible
a) All dogs have fleas. states, respectively.
b) There is a horse that can add. a) ∃xS(x, open)
c) Every koala can climb.
b) ∀x(S(x, malfunctioning) ∨ S(x, diagnostic))
d) No monkey can speak French.
c) ∃xS(x, open) ∨∃xS(x, diagnostic)
e) There exists a pig that can swim and catch fish.
d) ∃x¬S(x, available)
33. Express each of these statements using quantifiers. Then
form the negation of the statement, so that no negation e) ∀x¬S(x, working)
is to the left of a quantifier. Next, express the negation in 39. Translate these specifications into English where F(p) is
simple English. (Do not simply use the phrase “It is not “Printer p is out of service,” B(p) is “Printer p is busy,”
the case that.”) L(j) is “Print job j is lost,” and Q(j) is “Print job j is
a) Some old dogs can learn new tricks. queued.”
b) No rabbit knows calculus. a) ∃p(F(p) ∧ B(p)) →∃jL(j)
c) Every bird can fly. b) ∀pB(p) →∃jQ(j)
d) There is no dog that can talk. c) ∃j(Q(j) ∧ L(j)) →∃pF(p)
e) There is no one in this class who knows French and d) (∀pB(p) ∧∀jQ(j)) →∃jL(j)
Russian.
40. Express each of these system specifications using predi-
34. Express the negation of these propositions using quanti- cates, quantifiers, and logical connectives.
fiers, and then express the negation in English.
a) When there is less than 30 megabytes free on the hard
a) Some drivers do not obey the speed limit. disk, a warning message is sent to all users.
b) All Swedish movies are serious.
b) No directories in the file system can be opened and
c) No one can keep a secret. no files can be closed when system errors have been
d) There is someone in this class who does not have a detected.
good attitude.
c) The file system cannot be backed up if there is a user
35. Find a counterexample, if possible, to these universally currently logged on.
quantified statements, where the domain for all variables
d) Video on demand can be delivered when there are at
consists of all integers.
least 8 megabytes of memory available and the con-
2
a) ∀x(x ≥ x)
nection speed is at least 56 kilobits per second.
b) ∀x(x > 0 ∨ x< 0)
41. Express each of these system specifications using predi-
c) ∀x(x = 1) cates, quantifiers, and logical connectives.
36. Find a counterexample, if possible, to these universally a) At least one mail message, among the nonempty set
quantified statements, where the domain for all variables of messages, can be saved if there is a disk with more
consists of all real numbers. than 10 kilobytes of free space.
2
2
a) ∀x(x = x) b) ∀x(x = 2) b) Whenever there is an active alert, all queued messages
c) ∀x(|x| > 0) are transmitted.
37. Express each of these statements using predicates and c) The diagnostic monitor tracks the status of all systems
quantifiers. except the main console.
a) A passenger on an airline qualifies as an elite flyer if d) Each participant on the conference call whom the host
the passenger flies more than 25,000 miles in a year of the call did not put on a special list was billed.
or takes more than 25 flights during that year.
42. Express each of these system specifications using predi-
b) A man qualifies for the marathon if his best previ- cates, quantifiers, and logical connectives.
ous time is less than 3 hours and a woman qualifies
for the marathon if her best previous time is less than a) Every user has access to an electronic mailbox.
3.5 hours. b) The system mailbox can be accessed by everyone in
c) A student must take at least 60 course hours, or at least the group if the file system is locked.
45 course hours and write a master’s thesis, and re- c) The firewall is in a diagnostic state only if the proxy
ceive a grade no lower than a B in all required courses, server is in a diagnostic state.
to receive a master’s degree.
d) At least one router is functioning normally if the
d) There is a student who has taken more than 21 credit throughput is between 100 kbps and 500 kbps and
hours in a semester and received all A’s. the proxy server is not in diagnostic mode.