Page 87 - Discrete Mathematics and Its Applications

66 1 / The Foundations: Logic and Proofs

13. Let M(x, y) be “x has sent y an e-mail message” and b) There is a student in this class who owns a personal
T (x, y) be “x has telephoned y,” where the domain con- computer.
sists of all students in your class. Use quantifiers to ex- c) Every student in this class has taken at least one com-
press each of these statements. (Assume that all e-mail puter science course.
messages that were sent are received, which is not the d) There is a student in this class who has taken at least
way things often work.) one course in computer science.
a) Chou has never sent an e-mail message to Koko. e) Every student in this class has been in every building
b) Arlene has never sent an e-mail message to or tele- on campus.
phoned Sarah. f) There is a student in this class who has been in every
c) José has never received an e-mail message from Deb- room of at least one building on campus.
orah. g) Every student in this class has been in at least one
d) Every student in your class has sent an e-mail mes- room of every building on campus.
sage to Ken. 16. A discrete mathematics class contains 1 mathematics ma-
e) No one in your class has telephoned Nina. jor who is a freshman, 12 mathematics majors who are
f) Everyone in your class has either telephoned Avi or sophomores, 15 computer science majors who are sopho-
sent him an e-mail message. mores, 2 mathematics majors who are juniors, 2 computer
g) There is a student in your class who has sent everyone science majors who are juniors, and 1 computer science
else in your class an e-mail message. major who is a senior. Express each of these statements in
h) There is someone in your class who has either sent an terms of quantifiers and then determine its truth value.
e-mail message or telephoned everyone else in your a) There is a student in the class who is a junior.
class. b) Every student in the class is a computer science major.
i) There are two different students in your class who c) There is a student in the class who is neither a math-
have sent each other e-mail messages. ematics major nor a junior.
j) There is a student who has sent himself or herself an d) Every student in the class is either a sophomore or a
e-mail message. computer science major.
k) There is a student in your class who has not received e) There is a major such that there is a student in the class
an e-mail message from anyone else in the class and in every year of study with that major.
who has not been called by any other student in the 17. Express each of these system specifications using predi-
class. cates, quantifiers, and logical connectives, if necessary.
l) Every student in the class has either received an e- a) Every user has access to exactly one mailbox.
mail message or received a telephone call from an- b) There is a process that continues to run during all error
other student in the class. conditions only if the kernel is working correctly.
m) There are at least two students in your class such that c) All users on the campus network can access all web-
one student has sent the other e-mail and the second sites whose url has a .edu extension.
student has telephoned the first student. ∗ d) There are exactly two systems that monitor every re-
n) There are two different students in your class who mote server.
between them have sent an e-mail message to or tele-
18. Express each of these system specifications using predi-
phoned everyone else in the class.
cates, quantifiers, and logical connectives, if necessary.
14. Use quantifiers and predicates with more than one vari-
a) At least one console must be accessible during every
able to express these statements.
fault condition.
a) There is a student in this class who can speak Hindi. b) The e-mail address of every user can be retrieved
b) Every student in this class plays some sport. whenever the archive contains at least one message
c) Some student in this class has visited Alaska but has sent by every user on the system.
not visited Hawaii. c) For every security breach there is at least one mecha-
d) All students in this class have learned at least one pro- nism that can detect that breach if and only if there is
gramming language. a process that has not been compromised.
e) There is a student in this class who has taken ev- d) There are at least two paths connecting every two dis-
ery course offered by one of the departments in this tinct endpoints on the network.
school. e) No one knows the password of every user on the sys-
f) Some student in this class grew up in the same town tem except for the system administrator, who knows
as exactly one other student in this class. all passwords.[
g) Every student in this class has chatted with at least 19. Express each of these statements using mathematical and
one other student in at least one chat group. logical operators, predicates, and quantifiers, where the
15. Use quantifiers and predicates with more than one vari- domain consists of all integers.
able to express these statements. a) The sum of two negative integers is negative.
a) Every computer science student needs a course in dis- b) The difference of two positive integers is not neces-
crete mathematics. sarily positive.