First-order logic (3 pts.) Rosen, Section 1.3, pg.44, #58. Carried over from original hw02 assignment. Express all formulas using ∀, to make your life easier for part (d). No ducks are willing to waltz No officers ever decline to waltz All my poultry are ducks My poultry are not officers Does (d) follow from (a), (b), (c) ? Argue informally; you don't need to use the algebra or inference rules for first-order logic here. (4pts) You come home one evening to find your roommate exuberant because they have managed to prove that there is an even prime numbers bigger than two. More precisely, they have a correct proof of ∃y.Py ∧ y2 → Ey , for the domain of natural numbers with P interpreted as "is prime?" and E interpreted as "is even?". While they are celebrating their imminent fame at this amazing mathematical discovery, you ponder… …and realize the formula is indeed true for that interpretation. Briefly explain why. (You don't need to give a formal proof using inference rules or boolean algebra; just give a particular value for y and explain why it does satisfy the body of "∃y.".) Is their formula still true, when restricted to the domain of natural numbers two or less? (Using the same interpretation of P, E. Briefly explain why. Is their formula still true, when restricted to the empty domain? Briefly explain why. Give a formula that does actually capture the notion "there is an even prime number bigger than 2". (Extra Credit 2 pts) For the sentence ∀x. ∀y. Ax ∧ Bxy → Ay state whether it is true or false, relative to the following interpretations: The domain of the natural numbers, where A is interpreted as "even?" and B is interpreted as "equals" The domain of the Booleans (just {, }), where A is interpreted as "false?" and B is interpreted as "equals" The domain of WaterWorld locations in the particular board where locations Y and Z contain pirates, but all other locations are safe, and the relation symbol A is interpreted as "safe?" and B is interpreted as "neighbors" All WaterWorld boards, where A is interpreted as "safe?" and B is interpreted as "neighbors". (That is, is the formula valid for WaterWorld?) (5pts) Translate the following conversational English statements into first-order logic, using the suggested predicates, or inventing appropriately-named ones if none provided. (You may also freely use =, which (for us) is always interpreted as equality.) For the WaterWorld problems, use the set of locations as the domain, and use predicates nhbr (binary), and unary predicates hasPirate, shows3, and shows2. "All books rare and used". This is claimed by a local bookstore; what is the intended domain? Do you believe they mean to claim "all books rare or used"? "Everybody who has truly been kidnapped by a UFO knows that Agent Mulder is alive." (Is this true, presuming that no UFOs have actually visited Earth…yet?) "In WaterWorld, location λ has exactly one neighbor." (Your answer will be a formula with λ free, just as in the notes we developed formulas like "n is prime" where n was free.) "If a WaterWorld location shows a 3, then any neighboring location is a pirate." (This is only true for certain boards.) "If a WaterWorld location shows a 1, and has exactly one neighbors, then that neighbor has a pirate." Re-use existing code! (Extra Credit 2pts) Write a formula that is the conjunction of All for one, and one for all! If you're not for us, you're against us. The enemy of your enemy is your friend. Somebody has an enemy. (Not sure of an aphorism expressing this. Maybe, ``Life's not a bed of roses''?) Use just the relations isFor, and isAgainst, both to be interpreted on pairs of people. Clarifying some of the ambiguous English: We'll take "one" to mean "one particular person". Dumas' original musketeers presumably meant something different -- that each one of them was for all; but this makes the sentence more boring for domains which include everybody, rather than just Athos, Porthos, and Aramis.) The English is meant to convey group unity -- so, the first part is trying to say "All for [the same] one particular person", rather than "each for their own one favorite." (Whew, natural language sure can be ambiguous! 'Course, that's one of its strengths, in non-engineering areas.) For "us", we'll take it to mean "any one particular individual". You can think of it as each person saying to each other, "if you're not for me, you're against me". Similarly for "you". This captures the intent of the English -- these sayings are meant to apply to everybody, not just one particular person. "your enemy" will mean "somebody you are against", and "your friend" will mean "somebody you are for". (Careful -- this may be different than "somebody who is against/for you"). For clarity feel free to express the formula in parts: "φ1 ∧ φ2 ∧ φ3 ∧ φ4, where φ1 = …, φ2 = …, …." This is akin simplifying code into subroutines -- even in situations where you don't call the subroutine more than once, it still adds clarity. You don't have to split up your answer like this; some people might want to have quantifiers that span all four concepts; that's okay, though still strive for an formula that clearly corresponds to the question. (Extra Credit 2pts) For the four-part "Musketeer" formula from the preceding exercise, find two (fundamentally different) interpretations of isFor which satisfy the formula on a domain of three people. (Depict each of these interpretations as a graph -- draw three circles (nodes) representing the three people, and an arrow (edge) from a person to each person they like. (You can glance at Rosen p.542 (Section 8.1), Figure 8 for one such example of a graph.) (7pts) Translate the following statements into first-order logic. The domain is to be natural numbers, and the binary relation kthkn indicates whether or not the kth number of the sequence is n. That is, for the sequence <5,7,5>, the corresponding relation kth is {(1,5), (2,7), (3,5)}. You can also use the binary relations =, <, and/or <= but no others. The sequence is finite. The sequence contains three unique numbers Containing three numbers doesn't preclude it containing more than three. The sequence is sorted. (What, exactly, does your formula "sorted" capture -- ascending, descending; allowing duplicates (i.e. non-decreasing or non-increasing)? Any of those four are fine, but say which yours is.) The sequence is sorted except for (up to) one location. (For example, the sequence < 20, 30, 1, 40, 50 >.) (7 pts) Alternation of quantifiers: Determine the truth of each of the following sentences in each of the indicated domains. To help yourself, you might want to develop an English version of what the logic sentences say. S2: ∀x. ∀y. ∃z. likesxy ∧ ¬=z y → ¬likesyz S3: ∃x. ∀y. ∀z. likesxy ∧ ¬=z y → ¬likesyz S4: ∃x. ∃y. ∀z. likesxy ∧ ¬=z y → ¬likesyz S5: ∀x. ∃y. ∀z. likesxy ∧ ¬=z y → ¬likesyz D0: The empty domain. D1: A world with one person, who doesn't like herself. D2: A world with Yorick and Zelda, where Yorick likes Zelda, Zelda likes herself, and that's all. D3: A world with many people, including CJ (Catherine Zeta-Jones), JC (John Cusack), and JR (Julia Roberts). Everybody likes themselves; everybody likes JC; everybody likes CJ except JR; everybody likes JR except CJ and IB. Any others may or may not like each other, as you choose, subject to the preceding. (You may wish to sketch a graph of this likes relation.) Note how we don't just specify the domain which the logic variables range over, but also how to interpret the logic's relation-symbol likes. Determine the truth of these combinations. \\D0D1D2D3S2 S3 S4 S5