Exercises for First-Order Logic

Throughout these exercises, a b is simply a shorthand for a b .

Relations and Interpretations Consider the binary relation is-a-factor-of on the domain 1 2 3 4 5 6 . List all the ordered pairs in the relation. Display the relation as a directed graph. Display the relation in tabular form. Is the relation reflexive? symmetric? transitive? How would you define addsTo as a ternary relation? Give a prose definition of addsTo x y z in terms of the addition function. List the set of triples in the relation on the domain 1 2 3 4 . Generalize the previous problem to describe how you can represent any k-ary function as a k 1 -ary relation. Are each of the following formulas valid, i.e., true for all interpretations? (Remember that the relation names are just names in the formula; don't assume the name has to have any bearing on their interpretation.) For arbitrary a and b in the domain, atLeastAsWiseAs a b atLeastAsWiseAs b a For arbitrary a in the domain, primea odda primea For arbitrary a and b in the domain, betterThan a b betterThan b a For each, if it is true or false under all interpretations, prove that. For these small examples, a truth table like this one will probably be easier than using Boolean algebra or inference rules. Otherwise, give an interpretation in which it is true, and one in which it is false. As always, look at trivial and small test cases first. Here, try domains with zero, one, or two elements, and small relations. [Practice problem—solution provided.] Suppose we wanted to represent the count of neighboring pirates with a binary relation, such that when location A has two neighboring pirates, piratesNextTo A 2 will be true. Of course, piratesNextTo A 1 would not be true in this situation. These would be analogous with the propositional WaterWorld propositions A-has-2 and A-has-1, respectively. If we only allow binary relations to be subsets of a domain crossed with itself, then what must the domain be for this new relation piratesNextTo? If we further introduced another relation, isNumber?, what is a formula that would help distinguish intended interpretations from unintended interpretations? That is, give a formula that is true under all our intended interpretations of piratesNextTo but is not true for some nonsense interpretations we want to exclude. (This will be a formula without an analog in the WaterWorld domain axioms.) The relation needs to accept locations as well as numbers, so the domain is L , where L is the set of WaterWorld locations. Alternatively, you could use 0 1 2 3 instead of , the set of all natural numbers. The difficulty is that it's possible to ask about nonsensical combinations like piratesNextTo 17 2 and piratesNextTo W B . Adding isNumber?, any interpretation would be expected to satisfy, for arbitrary a and b, piratesNextTo a b isNumber?b isNumber? a b . More interestingly though, imagine we did interpret piratesNextTo over the domain only. We could then pretend that the locations, instead of being named A,…,Z, were just numbered 1,…,24. While this representation doesn't reflect how we model the problem, it is legal. Exercise for the reader: Write a formula which excludes relation piratesNextTo which can't match this convention! Determine whether the relation R on the set of all people is reflexive, antireflexive, symmetric, antisymmetric, and/or transitive, where a b R if and only if … a is older than b. a is at least as old as b. a and b are exactly the same age. a and b have a common grandparent. a and b have a common grandchild. For each of the following, if the statement is true, explain why, and if the statement is false, give a counter-example relation. If R is reflexive, then R is symmetric. If R is reflexive, then R is antisymmetric. If R is reflexive, then R is not symmetric. If R is reflexive, then R is not antisymmetric. If R is symmetric, then R is reflexive. If R is symmetric, then R is antireflexive. If R is symmetric, then R is not antireflexive.

Quantifiers Let Px be the statement has been to Prague, where the domain consists of your classmates. Express each of these quantifications in English. x P x x P x x P x x P x x P x x P x x P x x P x Which of these mean the same thing? Let C x be the statement x has a cat, let D x be the statement x has a dog, and let F x be the statement x has a ferret. Express each of these statements in first-order logic using these relations. Let the domain be your classmates. A classmate has a cat, a dog, and a ferret. All your classmates have a cat, a dog, or a ferret. At least one of your classmates has a cat and a ferret, but not a dog. None of your classmates has a cat, a dog, and a ferret. For each of the three animals, there is a classmate of yours that has one. Determine the truth value of each of these statements if the domain is all real numbers. Where appropriate, give a witness. x x 2 2 x x 2 -1 x x 2 2 1 x x 2 x

Interpreting First-order Formulas Let Px, Qx, Rx, and Sx be the statements x is a duck, x is one of my poultry, x is an officer, and x is willing to waltz, respectively. Express each of these statements using quantifiers, logical connectives, and the relations Px, Qx, Rx, and Sx. No ducks are willing to waltz. No officers ever decline to waltz. All my poultry are ducks. My poultry are not officers. Does the fourth item follow from the first three taken together? Argue informally; you don't need to use the algebra or inference rules for first-order logic here. You come home one evening to find your roommate exuberant because they have managed to prove that there is an even prime number 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 Boolean algebra or inference rules; just give a particular value for y and explain why it satisfies the body of y . Is the formula still true when restricted to the domain of natural numbers two or less? Briefly explain why or why not. Is the formula still true when restricted to the empty domain? Briefly explain why or why not. Give a formula that correctly captures the notion there is an even prime number bigger than 2 . For the sentence x y Ax Bxy Ay state whether it is true or false, relative to the following interpretations. If false, give values for x and y witnessing that. The domain of the natural numbers, where A is interpreted as even?, and B is interpreted as equals The domain of the natural numbers, where A is interpreted as even?, and B is interpreted as is an integer divisor of The domain of the natural numbers, where A is interpreted as even?, and B is interpreted as is an integer multiple of The domain of the Booleans, , 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, the relation symbol A is interpreted as unsafe?, 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?) 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 we'll choose to always interpret as the standard equality relation.) 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 knows that UFOs have kidnapped people knows that Agent Mulder has been kidnapped. (Is this true, presuming that no UFOs have actually visited Earth…yet?) Write a formula for each of the following. Use the two binary relations isFor and isAgainst and domain of all people. All for one, and one for all! We'll take one to mean one particular person, and moreover, that both ones are referring the same particular person, resulting in There is one whom everybody is for, and that one person is for everybody. Dumas' original musketeers presumably meant something different: that each one of them was for each (other) one of the them, making the vice-versa clause redundant. But this is boring for our situation, so we'll leave that interpretation to Athos, Porthos, and Aramis alone.) If you're not for us, you're against us. In aphorisms, you is meant to be an arbitrary person; consider using the word one instead. Furthermore, we'll interpret us as applying to everybody. That is, One always believes that `if one is not for me, then one is against me' . The enemy of your enemy is your friend. By your enemy we mean somebody you are against, and similarly, your friend will mean somebody you are for. (Be carefule! This may be different than somebody who is against/for you). Somebody has an enemy. (We don't know of an aphorism expressing this. None of the following quite capture it: Life's not a bed of roses; It's a dog-eat-dog world; Everyone for themselves; You can't please all the people all the time. ) Two interpretations are considered fundamentally the same (or isomorphic) if you can map one interpretation to the other simply by a consistent renaming of domain elements. [Practice problem—solution provided.] Find two fundamentally different interpretations that satisfy the statement There exists one person who is liked by two people. One interpretation that satisfies this is a domain of three people Alice, Bob, Charlie, with the likes relation: Alice Bob Bob Bob . Bob is liked by two people, so it satisfies the statement. Here's another interpretation that is the same except for renaming, and thus not fundamentally different: a domain of three people Alyssa, Bobby, Chuck, with the likes relation: Chuck Alyssa Alyssa Alyssa . With the substitutions [Chuck↦ Alice] and [Alyssa↦ Bob], we see that the underlying structure is the same as before. Here's an interpretation that is fundamentally different: a domain of three people Alice, Bob, Charlie, with the likes relation: Charlie Bob Alice Bob . No matter how you rename, you don't get somebody liking themself, so you can see its underlying structure is truly different than the preceding interpretations. English is fuzzy enough that it is unclear whether one and two are meant as exact counts. The above two examples each assumed they are. If we change the statement slightly to add a comma: There exists one person, who is liked by two people , we arguably change the meaning significantly. The now-independent first clause arguably means there is only one person existent in total, so the overall statement must be false! There's a quick lesson in the difference between English dependent and independent clauses. For the four Musketeer formulas from a previous exercise, find three fundamentally different interpretations of isFor which satisfy all the formulas 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 Section 9.1, Figure 8 for an example.) One of the interpretations is unintuitive in that isFor and isAgainst don't correspond to what we probably mean in English. Translate the following statements into first-order logic. The domain is the set of natural numbers, and the binary relation kthkn indicates whether or not the kth number of the sequence is n. For example, the sequence 575, is represented by the relation kth 05 17 25 . You can also use the binary relations , , and , but no others. You may assume that kth models a sequence. No index k is occurs multiple times, thus excluding kth 05 17 09 . Thus, kth is a function, as in a previous example representing an array as a function. Also, no higher index k occurs without all lower-numbered indices being present, thus excluding kth 05 17 39 . The sequence is finite. The sequence contains at least three distinct numbers , e.g., 5 6 5 6 7 8 , but not 5 6 5 6 . The sequence is sorted in non-decreasing order, e.g., 3 5 5 6 8 10 10 12 . The sequence is sorted in non-decreasing order, except for exactly one out-of-order element, e.g., 20 30 4 50 60 . Some binary relations can be viewed as the encoding of a unary function, where the first element of the ordered pair represents the function's value. For instance, in a previous exercise we encoded the binary function addition as a ternary relation addsTo. Give one example of a binary relation which does not correspond to the encoding of a function. Write a first-order formula describing the properties that a binary relation R must have to correspond to a unary function. 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. Start with the inner formula (talking about people x,y,z), then add the quantifier for z to get a statement about people x,y, and repeat for the other two quantifiers. Four sentences: x y z likesxy z y likesyz x y z likes x y z y likesyz x y z likesxy z y likesyz x y z likesxy z y likesyz Four domains: The empty domain. A world with one person, who likes herself. A world with Yorick and Zelda, where Yorick likes Zelda, Zelda likes herself, and that's all. 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, similar to Rosen Section 9.1 Figure 8.) Determine the truth of all sixteen combinations of the four statements and four domains.

Modeling Translate the following into first-order logic: Raspberry sherbet with hot fudge (rshf) is the tastiest dessert. Use tastier as your only relation. What is the intended domain for your formula? What is a relation which makes this statement true? One which makes it false? Even allowing for ellision, the list of WaterWorld domain axioms is incomplete, in a sense. The game reports how many pirates exist in total, but that global information is not reflected in the propositions or axioms. We had the same problem with the propositional logic domain axioms First, assume we only use the default WaterWorld board size and number of pirates, i.e., five. What additional axiom or axioms do we need? Next, generalize your answer to model the program's ability to play the game with a different number of pirates. What problem do you encounter? The puzzle game of Sudoku is played on a 99 grid, where each square holds a number between 1 and 9. The positions of the numbers must obey constraints. Each row and each column has each of the 9 numbers. Each of the 9 non-overlapping 33 square sub-grids has each of the 9 numbers. Like WaterWorld, throughout the game, some of the values have not been discovered, although they are determined. You start with some numbers revealed, enough to guarantee that the rest of the board is uniquely determined by the constraints. Thus, like in WaterWorld, when deducing the value of another location, what has been revealed so far would serve as premises in a proof. Fortunately, there are the same number of rows, columns, subgrids, and values. So, our domain is 1 2 3 4 5 6 7 8 9 . To model the game, we will use the following relations: valuercv indicates that at row r, column c is the value v. v w is the standard equality relation. subgridgrc indicates that subgrid g includes the location at row r, column c. Provide domain axioms for Sudoku, and briefly explain them. These will model the row, column, and subgrid constraints. In addition, you should include constraints on our above relations, such as that each location holds one value.

Reasoning with Equivalences Some of the first-order equivalences are redundant. For each of the following, prove the equivalence using the other equivalences. x ϕ θ x ϕ θ Assuming a non-empty domain, x θ ϕ θ x ϕ . We can characterize a prime number as a number n satisfying q r qrn q 1 r 1 . Using the equivalences for first-order logic, show step-by-step that this is equivalent to the formula q r qrn q 1 r 1 . Do not use any arithmetic equivalences. A student claims that x Ax Bx Cz x Ax x Bx Cz by the distribution of quantifiers. This is actually trying to do two steps at once. Rewrite this as the two separate intended steps, determine which is wrong, and describe why that step is wrong. Simplify the formula x y z Ax By Cz , so that the body of each quantifier contains only a single atomic formula involving that quantified variable. Provide reasoning for each step of your simplification.

Reasoning with Inference Rules [Practice problem—solution provided.] Prove that syllogisms are valid inferences. In other words, show that x Rx Sx , Rc ⊢ Sc. 1x Rx Sx Premise 2Rc Premise 3 Rc Sc ∀Elim, line 1 4Xc ⇒Elim, lines 2,3

What is wrong with the following proof of x Ex Ec ? 1subproof: x Ex ⊢ Ec 1.a x Ex Premise for subproof 1.b Ec ∃Elim, line 1.a 2 x Ex Ec ⇒Intro, line 1

Using the inference rules, formally prove the last part of the previous problem about ducks and such. Give an inference rule proof of x Fruitx hasMethodtastyx , y Appley Fruity ⊢ z Applez hasMethodtastyz . Prove the following: x Px , y Py Qy ⊢ z Qz Your proof above used ∃Intro. Why can't we replace that step with the formula z Qz with the justification ∀Intro? Describe an interpretation which satisfies the proof's premises, but does not satisfy z Qz .