CSE260
Solutions to Homework Set #3
23. Translate in two ways each of these statements into logical expressions using predicates, quantifiers, and logical connectives. First, let the domain consist of the students in your class and second, let it consist of all people.
Let C(x) be the propositional function “x is in your class”.
a) Someone in your class can speak Hindi.
$xH(x) and $x(C(x) /\ (H(x)), where H(x) is “x can speak Hindi”.
b) Everyone in your class is friendly.
"F(x) and "x(C(x) → F(x)), where F(x) is “x is friendly”.
c) There is a person in your class who was not born in California.
$x¬B(x) and $x(C(x) /\ ¬B(x)), where B(x) is “x was born in California”.
d) A student in your class has been in a movie.
$xM(x) and $x(C(x) /\ M(x)), where M(x) is “x has been in a movie”.
e) No student in your class has taken a course in logic programming.
"x¬L(x) and "x(C(x) → ¬L(x)), where L(x) is “x has taken a course in logic programming”.
41. Express each of these system specifications using predicates, quantifiers, and logical connectives.
a) At least one mail message, among the nonempty set of messages, can be saved if there is a disk with more than 10 kilobytes of free space.
($xF(x, 10)) → $xS(x), where F(x, y) is “Disk x has more than y kilobytes of free space”, and S(x) is “mail message x can be saved”.
b) Whenever there is an active alert, all queued messages are transmitted.
$xA(x) → "x(Q(x) → T(x)), where A(x) is “Alert x is active”, Q(x) is “Message x is queued”, and T(x) is “Message x is transmitted”.
c) The diagnostic monitor tracks the status of all systems except the main console.
"x(x ≠ the main console) → T(x)), where T(x) is “The diagnostic monitor tracks the status of system x”.
d) Each participant on the conference call whom the host of the call did not put on a special list was billed.
"x(¬L(x) → B(x)), where L(x) is “The host of the conference call put participant x on a special list” and B(x) is “Participant x was billed”.
52. As mentioned in the text, the notation $!xP(x) denotes “There exists a unique x such that P(x) is true”. If the domain consists of all integers, what are the truth values of these statements.
c) $!x(x + 3 = 2x)
True
60. Let P(x), Q(x), and R(x) be the statements “x is a clear explanation”, “x is satisfactory”, and “x is an excuse”, respectively. Suppose that the domain for x consists of all English text. Express each of these statements using quantifiers, logical connectives, and P(x), Q(x), and R(x).
a) All clear explanations are satisfactory.
"x(P(x) → Q(x))
b) Some excuses are unsatisfactory.
$x(R(x) /\ ¬Q(x))
c) Some excuses are not clear explanations.
$x(R(x) /\ ¬P(x))
d) Does (c) follow from (a) and (b)?
Yes. The unsatisfactory excuse guaranteed by part (b) cannot be a clear explanation by part (a).
9. Let L(x, y) be the statement “x loves y”, where the domain for both x and y consists of all people in the world. Use quantifiers to express each of these statements.
a) Everybody loves Jerry.
"xL(x, Jerry)
b) Everybody loves somebody.
"x$y(x, y)
c) There is somebody whom everybody loves.
$x"yL(x, y)
d) Nobody loves everybody.
"x$y¬L(x, y)
e) There is somebody whom Lydia does not love.
$x¬L(Lydia, x)
f) There is somebody whom no one loves.
$x"y¬L(y, x)
g) There is exactly one person whom everybody loves.
$x("yL(y, x) /\ "z("wL(w, z)) → z = x))
h) There are exactly two people whom Lynn loves.
$x$y(x ≠ y /\ (Lynn, x) /\ L(Lynn, y) /\ "z(L(Lynn, z) → (z = x \/ z = y)))
i) Everyone loves himself or herself.
"xL(x, x)
j) There is someone who loves no one besides himself or herself.
$x"y(L(x, y) ↔ x = y)
23. Express each of these mathematical statements using predicates, quantifiers, logical connectives, and mathematical operators.
a) The product of two negative real numbers is positive.
"x"y((x < 0) /\ (y < 0) → (xy > 0))
b) The difference of a real number and itself is zero.
"x(x – x = 0)
c) Every positive real number has exactly two square roots.
"x$a$b(a ≠ b /\ "c(c² = x ↔ (c = a \/ c = b)))
d) A negative real number does not have a square root that is a real number.
"x((x < 0) → ¬$y(x = y²))
37. Express each of these statements using quantifiers. Then form the negation of the statement so that no negation is to the left of a quantifier. Next, express the negation in simple English.
a) Every student in this class has taken exactly two mathematics classes at this school
There is someone in this class such that for every two different math courses, these are not the two and only two math courses this person has taken.
b) Someone has visited every country in the world except Libya.
Every person has either visited Libya or has not visited a country other than Libya
c) No one has climbed every mountain in the Himalayas.
Someone has climbed every mountain in the Himalayas.
d) Every movie actor has either been in a movie with Kevin Bacon or has been in a movie with someone who has been in a movie with Kevin Bacon.
There is someone who has neither been in a movie with Kevin Bacon nor has been in a movie with someone who has been in a movie with Kevin Bacon.
1. Consider the universe of discourse N (all integers ≥ 0). Let p(n) = “n is prime” and e(n) = “n is even”. Write the following in ordinary English:
a) $m"n(e(n) /\ p(m + n))
There is an integer m such that for all integers n, n is even and m + n is prime.
b) "n$m(¬e(n) → e(m + n))
For all integers n, there is an integer m such that if n is odd, then m + n is even.
Translate the following into logical notation using p and e.
a) There are two prime integers whose sum is even.
$x$y(x ≠ y /\ p(x) /\ p (y) /\ e(x + y))
b) If the sum of two primes is even, then neither of them equals 2.
"x"y((p(x) /\ p(y) /\ e(x + y)) → (x ≠ 2 /\ y ≠ 2))
c) The sum of two prime integers is odd.
"x"y((p(x) /\ p(y)) → ¬e(x + y))