Homework 3  Translating into logic

Homework 3 
Directions: Write up carefully argued solutions to the following problems. The first task is to be complete and correct. The more subtle task is to keep it simple and succinct. Your solution should be clear enough that it should explain to someone who does not already understand the answer why it works. You may use any results proven in lecture without proof. Anything else must be argued rigorously. Unless otherwise specified, all answers are expected to be given in closed form.
1. Translating into logic (12 points) Translate the following sentences into predicate logic. The domain of discourse is the set of all positive integers. Youcanusethepredicates: 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”. ∀x∃y(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”. ∀x∀y((P(x,y)⊕Q(y)) →¬∃zQ(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 ∀x (Q(x) →¬P(x)), ∀x ((P(x)∧¬Q(x)) → R(x)), and ∃x P(x), you can conclude that ∃x R(x).
6. odd x odd = odd (15 points) Recall that a number n is odd ↔∃(k ∈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. Assumingthatall5piratesareintelligent(andawarethatalltheotherpiratesarejustasaware, intelligent, and bloodthirsty), what will happen? Your solution should indicate which pirates die, and how many coins each of the remaining pirates receives.
3