Homework 3 Translating into logic

1. Translating into logic (12 points)
Translate the following sentences into predicate logic. The domain of discourse is the set of all positive
integers. You can use the predicates: Even(x); Odd(x); Prime(x); Greater(x; y); Equal(x; y); Sum(x; y; z)
from Lecture 5 and 6.
(a) [3 Points] For all positive integers x, if x is a prime, there exist primes y and z such that x = y +z.
(b) [3 Points] For all positive integers x, there exist prime integers y and z such that y x and z x
and z = y + 2.
(c) [3 Points] There exists a positive integer x that is a prime such that for all positive integers y, if
y is even, then y ≥ x.
(d) [3 Points] There is no positive integer x such that x is even and also a prime.
2. Not So Negative (20 points)
For each of the following, translate the English statement into first-order logic using as detailed predicates
as possible, and then negate it. Your answer should push negation symbols as far in as possible; any
negation symbol should be directly in front of a predicate. Don’t forget to define predicates.
(a) [5 Points] Let the domain of discourse be all people.
“Everyone has two parents.”
(b) [5 Points] Let the domain of discourse be all CSE courses.
“Every 300-level CSE course has a prerequisite CSE course but some have more than one CSE
course prerequisite.”
For each of the following, negate the the first-order logic statement, and then translate it into English.
Your answer should push negation symbols as far in as possible; any negation symbol should be directly
in front of a predicate.
1(c) [5 Points] Let the domain of discourse be all activities. Let P (x; y) be “x is more fun than y”.
8x9y(P (x; y) ! :P (y; x))
(d) [5 Points] Let the domain of discourse be courses at UW. Let P (x; y) be “x is a pre-requisite for
y”. Let Q(y) be “I am currently taking y”.
8x8y((P (x; y) ⊕ Q(y)) ! :9zQ(z))
3. Formal Proofs (25 points)
(a) [15 Points] Write a formal proof using inference rules that given (p ^ :q) _ (:p ^ q), r ! :s, and
(s ^ p) ! r, the proposition s ! q must also be true.
(b) [10 Points] Write a formal proof using inference rules of ((p ! q) ^ (r ! :q)) ! (r ! :p)
4. Spoofclusions (13 points)
Theorem: Given (p ^ r) ! (q ^ r), :s ! (r ^ q), and s ! (p ^ q), prove q.
“Spoof:”
1: (p ^ r) ! (q ^ r) [Given]
2: :s ! (r ^ q) [Given]
3: s ! (p ^ q) [Given]
4: :s ! q [Elim ^: 2]
5: p ! (q ^ r) [Elim ^: 1]
6:1: s [Assumption]
6:2: p ^ q [MP: 6.1, 3]
6:3: p [Elim ^: 6.2]
6:4: q ^ r [MP: 6.3, 5]
6:5: q [Elim ^: 6.4]
6: s ! q [Direct Proof Rule]
7: (s ! q) ^ (:s ! q) [Intro ^: 4, 6]
8: (:s _ q) ^ (::s _ q) [Law of Implication]
9: (q _ :s) ^ (q _ ::s) [Commutativity]
10: q ^ (:s _ ::s) [Distributivity]
11: q ^ T [Law of Negation]
12: q [Domination]
(a) [3 Points] Is the conclusion of the “spoof” correct? Explain why or why not.
2(b) [10 Points] The “spoof” makes a critical error in at least one step. Explain which step(s) are faulty
and why.
5. Mind Your P’s and Q’s (15 points)
Using the logical inference rules and equivalences we have given, write a formal proof that given
8x (Q(x) ! :P (x)), 8x ((P (x) ^ :Q(x)) ! R(x)), and 9x P (x), you can conclude that 9x R(x).
6. odd x odd = odd (15 points)
Recall that a number n is odd $ 9(k 2 Z); n = 2k + 1. Prove using an English proof that if n; m are
odd, then nm is odd.
7. EXTRA CREDIT: Aarh! Me Hearties (-NoValue- points)
Five pirates, called Ann, Brenda, Carla, Danielle and Emily, found a treasure of 100 gold coins.
On their ship, they decide to split the coins using the following scheme.
• The first pirate in alphabetical order becomes the chief pirate.
• The chief proposes how to share the coins, and all other pirates (excluding the chief) vote for or
against it.
• If 50% or more of the pirates vote for it, then the coins will be shared that way.
• Otherwise, the chief will be thrown overboard, and the process is repeated with the pirates that
remain.
Thus, in the first round Ann is the chief: if her proposal is rejected, she is thrown overboard and Brenda
becomes the chief, etc; if Ann, Brenda, Carla, and Danielle are thrown overboard, then Emily becomes
the chief and keeps the entire treasure.
The pirates’ first priority is to stay alive: they will act in such a way as to avoid death. If they can stay
alive, they want to get as many coins as possible. Finally, they are a blood-thirsty bunch, if a pirate
would get the same number of coins if she voted for or against a proposal, she will vote against so that
the pirate who proposed the plan will be thrown overboard.
Assuming that all 5 pirates are intelligent (and aware that all the other pirates are just as aware, intelligent,
and bloodthirsty), what will happen? Your solution should indicate which pirates die, and how many
coins each of the remaining pirates receives.
3