Skip to content Skip to navigation

Connexions

You are here: Home » Content » Exercises for First-Order Logic

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

Exercises for First-Order Logic

Module by: Ian Barland, John Greiner, Fuching Chi. E-mail the authors

User rating (How does the rating system work?)
Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

:
(0 ratings)

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

Throughout these exercises, a≠b a b is simply a shorthand for ¬a=b a b .

Relations and Interpretations

Exercise 1

Consider the binary relation is-a-factor-ofis-a-factor-of on the domain 123456 1 2 3 4 5 6 .

  1. List all the ordered pairs in the relation.

  2. Display the relation as a directed graph.

  3. Display the relation in tabular form.

  4. Is the relation reflexive? symmetric? transitive?

Exercise 2

How would you define addsToaddsTo as a ternary relation?

  1. Give a prose definition of addsToxyz addsTo x y z in terms of the addition function.

  2. List the set of triples in the relation on the domain 1234 1 2 3 4 .

Exercise 3

Generalize the previous problem to describe how you can represent any kk-ary function as a k+1 k 1 -ary relation.

Exercise 4

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 aa and bb in the domain, atLeastAsWiseAsab∨atLeastAsWiseAsba atLeastAsWiseAs a b atLeastAsWiseAs b a
  • For arbitrary aa in the domain, primea⇒ odda⇒primea primea odda primea
  • For arbitrary aa and bb in the domain, betterThanab⇒¬betterThanba 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.

Note:

As always, look at trivial and small test cases first. Here, try domains with zero, one, or two elements, and small relations.

Exercise 5

[Practice problem——solution provided.]

Suppose we wanted to represent the count of neighboring pirates with a binary relation, such that when location AA has two neighboring pirates, piratesNextToA2 piratesNextTo A 2 will be true. Of course, piratesNextToA1 piratesNextTo A 1 would not be true in this situation. These would be analogous with the propositional WaterWorld propositions A-has-2A-has-2 and A-has-1A-has-1, respectively.

  1. 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 piratesNextTopiratesNextTo?

  2. If we further introduced another relation, isNumber?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 piratesNextTopiratesNextTo 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.)

Solution

  1. The relation needs to accept locations as well as numbers, so the domain is L⋃ℕ L , where LL is the set of WaterWorld locations. Alternatively, you could use 0123 0 1 2 3 instead of ℕ, the set of all natural numbers.

  2. The difficulty is that it's possible to ask about nonsensical combinations like piratesNextTo172 piratesNextTo 17 2 and piratesNextToWB piratesNextTo W B . Adding isNumber?isNumber?, any interpretation would be expected to satisfy, for arbitrary aa and bb, piratesNextToab⇒isNumber?b∧¬isNumber?ab piratesNextTo a b isNumber?b isNumber? a b .

    Aside:
    More interestingly though, imagine we did interpret piratesNextTopiratesNextTo over the domain ℕ only. We could then pretend that the locations, instead of being named AA,…,ZZ, 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 piratesNextTopiratesNextTo which can't match this convention!

Exercise 6

Determine whether the relation RR on the set of all people is reflexive, antireflexive, symmetric, antisymmetric, and/or transitive, where a b∈R a b R if and only if …

  1. aa is older than bb.

  2. aa is at least as old as bb.

  3. aa and bb are exactly the same age.

  4. aa and bb have a common grandparent.

  5. aa and bb have a common grandchild.

Exercise 7

For each of the following, if the statement is true, explain why, and if the statement is false, give a counter-example relation.

  1. If RR is reflexive, then RR is symmetric.

  2. If RR is reflexive, then RR is antisymmetric.

  3. If RR is reflexive, then RR is not symmetric.

  4. If RR is reflexive, then RR is not antisymmetric.

  5. If RR is symmetric, then RR is reflexive.

  6. If RR is symmetric, then RR is antireflexive.

  7. If RR is symmetric, then RR is not antireflexive.

Quantifiers

Exercise 8

Let Px Px be the statement “has been to Prague”, where the domain consists of your classmates.

  1. Express each of these quantifications in English.

    • ∃x:Px x P x
    • ∀x:Px x P x
    • ¬∃x:Px x P x
    • ¬∀x:Px x P x
    • ∃x:¬Px x P x
    • ∀x:¬Px x P x
    • ¬∃x:¬Px x P x
    • ¬∀x:¬Px x P x

  2. Which of these mean the same thing?

Exercise 9

Let CxC x be the statement “xx has a cat”, let DxD x be the statement “xx has a dog”, and let FxF x be the statement “xx has a ferret”. Express each of these statements in first-order logic using these relations. Let the domain be your classmates.

  1. A classmate has a cat, a dog, and a ferret.

  2. All your classmates have a cat, a dog, or a ferret.

  3. At least one of your classmates has a cat and a ferret, but not a dog.

  4. None of your classmates has a cat, a dog, and a ferret.

  5. For each of the three animals, there is a classmate of yours that has one.

Exercise 10

Determine the truth value of each of these statements if the domain is all real numbers. Where appropriate, give a witness.

  1. ∃x:x2=2x x 2 2
  2. ∃x:x2=-1x x 2 -1
  3. ∀x:x2+2≥1x x 2 2 1
  4. ∀x:x2≠xx x 2 x

Interpreting First-order Formulas

Exercise 11

Let PxPx, QxQx, RxRx, and SxSx be the statements “xx is a duck”, “xx is one of my poultry”, “xx is an officer”, and “xx is willing to waltz”, respectively. Express each of these statements using quantifiers, logical connectives, and the relations PxPx, QxQx, RxRx, and SxSx.

  1. No ducks are willing to waltz.

  2. No officers ever decline to waltz.

  3. All my poultry are ducks.

  4. My poultry are not officers.

  5. 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.

Exercise 12

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∧y>2⇒Eyy Py y2 Ey , for the domain of natural numbers, with PP interpreted as “is prime?” and EE interpreted as “is even?”. While they are celebrating their imminent fame at this amazing mathematical discovery, you ponder…

  1. …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 yy and explain why it satisfies the body of “ ∃yy ”.

  2. Is the formula still true when restricted to the domain of natural numbers two or less? Briefly explain why or why not.

  3. Is the formula still true when restricted to the empty domain? Briefly explain why or why not.

  4. Give a formula that correctly captures the notion “ there is an even prime number bigger than 2 ”.

Exercise 13

For the sentence ∀x:∀y:Ax∧Bxy⇒Ayx y Ax Bxy Ay state whether it is true or false, relative to the following interpretations. If false, give values for xx and yy witnessing that.

  1. The domain of the natural numbers, where AA is interpreted as “even?”, and BB is interpreted as “equals”
  2. The domain of the natural numbers, where AA is interpreted as “even?”, and BB is interpreted as “is an integer divisor of”
  3. The domain of the natural numbers, where AA is interpreted as “even?”, and BB is interpreted as “is an integer multiple of”
  4. The domain of the Booleans, truefalse , where AA is interpreted as “false?”, and BB is interpreted as “equals”
  5. The domain of WaterWorld locations in the particular board where locations YY and ZZ contain pirates, but all other locations are safe, the relation symbol AA is interpreted as “unsafe?”, and BB is interpreted as “neighbors”
  6. All WaterWorld boards, where AA is interpreted as “safe?”, and BB is interpreted as “neighbors”. (That is, is the formula valid for WaterWorld?)

Exercise 14

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.)

  1. “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”?
  2. “ 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?)

Exercise 15

Write a formula for each of the following. Use the two binary relations isForisFor and isAgainstisAgainst 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 “one”s are referring the same particular person, resulting in “There is one whom everybody is for, and that one person is for everybody.” 1
  • “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. 2)

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.

Exercise 16

[Practice problem——solution provided.]

Find two fundamentally different interpretations that satisfy the statement “There exists one person who is liked by two people”.

Solution

One interpretation that satisfies this is a domain of three people Alice, Bob, Charlie, with the likeslikes relation: Alice Bob Bob Bob 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 likeslikes relation: Chuck Alyssa Alyssa Alyssa Chuck Alyssa Alyssa Alyssa . With the substitutions [Chuck↦ Alice][Chuck↦Alice] and [Alyssa↦ Bob][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 likeslikes relation: Charlie Bob Alice Bob 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.

Aside:
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.

Exercise 17

For the four “Musketeer” formulas from a previous exercise, find three fundamentally different interpretations of isForisFor 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.)

Note:

One of the interpretations is unintuitive in that isForisFor and isAgainstisAgainst don't correspond to what we probably mean in English.

Exercise 18

Translate the following statements into first-order logic. The domain is the set of natural numbers, and the binary relation kthknkthkn indicates whether or not the kkth number of the sequence is nn. For example, the sequence 575575, is represented by the relation kth=051725 kth 05 17 25 . You can also use the binary relations =, <, and ≤, but no others.

You may assume that kthkth models a sequence. No index kk is occurs multiple times, thus excluding kth=051709 kth 05 17 09 . Thus, kthkth is a function, as in a previous example representing an array as a function. Also, no higher index kk occurs without all lower-numbered indices being present, thus excluding kth=051739 kth 05 17 39 .

  1. The sequence is finite.
  2. The sequence contains at least three distinct numbers , e.g., 5 6 5 6 7 8 5 6 5 6 7 8 , but not 5 6 5 6 5 6 5 6 .

  3. The sequence is sorted in non-decreasing order, e.g., 3 5 5 6 8 10 10 12 3 5 5 6 8 10 10 12 .

  4. The sequence is sorted in non-decreasing order, except for exactly one out-of-order element, e.g., 20 30 4 50 60 20 30 4 50 60 .

Exercise 19

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 addsToaddsTo.

  1. Give one example of a binary relation which does not correspond to the encoding of a function.

  2. Write a first-order formula describing the properties that a binary relation RR must have to correspond to a unary function.

Exercise 20

Alternation of quantifiers: Determine the truth of each of the following sentences in each of the indicated domains.

Note:

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 xx,yy,zz), then add the quantifier for zz to get a statement about people xx,yy, and repeat for the other two quantifiers.

Four sentences:

  1. ∀x:∀y:∃z:likesxy∧ z≠y⇒¬likesyz x y z likesxy z y likesyz
  2. ∃x:∀y:∀z:likesxy∧ z≠y⇒¬likesyz x y z likes x y z y likesyz
  3. ∃x:∃y:∀z:likesxy∧ z≠y⇒¬likesyz x y z likesxy z y likesyz
  4. ∀x:∃y:∀z:likesxy∧ z≠y⇒¬likesyz x y z likesxy z y likesyz

Four domains:

  1. The empty domain.
  2. A world with one person, who likes herself.
  3. A world with Yorick and Zelda, where Yorick likes Zelda, Zelda likes herself, and that's all.
  4. 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 likeslikes relation, similar to Rosen Section 9.1 Figure 8.)

Determine the truth of all sixteen combinations of the four statements and four domains.

Modeling

Exercise 21

Translate the following into first-order logic: “ Raspberry sherbet with hot fudge (rshfrshf) is the tastiest dessert. ” Use tastiertastier 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?

Exercise 22

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

  1. 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?
  2. 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?

Exercise 23

The puzzle game of Sudoku is played on a 9×999 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 3×333 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 123456789 1 2 3 4 5 6 7 8 9 .

To model the game, we will use the following relations:

  • valuercvvaluercv indicates that at row rr, column cc is the value vv.
  • v=wv w is the standard equality relation.
  • subgridgrcsubgridgrc indicates that subgrid gg includes the location at row rr, column cc.

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

Exercise 24

Some of the first-order equivalences are redundant. For each of the following, prove the equivalence using the other equivalences.

  1. ∀x:ϕ⇒θ≡∃x:ϕ⇒θ x ϕ θ x ϕ θ

  2. Assuming a non-empty domain, ∃x:θ⇒ϕ≡θ⇒∃x:ϕ x θ ϕ θ x ϕ .

Exercise 25

We can characterize a prime number as a number nn satisfying ∀q:∀r:qr=n⇒q=1∨r=1q 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:qr=n∧q≠1∧r≠1 q r qrn q 1 r 1 . Do not use any arithmetic equivalences.

Exercise 26

A student claims that ∀x:Ax∧Bx⇒Cz≡∀x:Ax∧∀x:Bx⇒Cz 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.

Exercise 27

Simplify the formula ∀x:∀y:∃z:Ax∧By⇒Czx 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

Exercise 28

[Practice problem——solution provided.]

Prove that syllogisms are valid inferences. In other words, show that ∀x:Rx⇒Sx, Rc ⊢ Scx Rx Sx , Rc ⊢ Sc.

Solution

Table 1
1∀x:Rx⇒Sxx Rx Sx Premise
2RcRc Premise
3Rc⇒Sc Rc Sc ∀Elim, line 1
4XcXc ⇒Elim, lines 2,3

Exercise 29

What is wrong with the following “proof” of ∃x:Ex⇒Ec x Ex Ec ?

Table 2
1subproof: ∃x:Ex ⊢ Ec x Ex ⊢ Ec  
1.a  ∃x:Exx Ex Premise for subproof
1.b  EcEc ∃Elim, line 1.a
2∃x:Ex⇒Ec x Ex Ec   ⇒Intro, line 1

Exercise 30

Using the inference rules, formally prove the last part of the previous problem about ducks and such.

Exercise 31

Give an inference rule proof of ∀x:Fruitx⇒hasMethodtastyx, ∀y:Appley⇒Fruity ⊢ ∀z:Applez⇒hasMethodtastyzx Fruitx hasMethodtastyx , y Appley Fruity ⊢ z Applez hasMethodtastyz .

Exercise 32

  1. Prove the following: ∃x:Px , ∀y:Py⇒Qy ⊢ ∃z:Qz x Px , y Py Qy ⊢ z Qz
  2. Your proof above used ∃Intro. Why can't we replace that step with the formula ∀z:Qzz Qz with the justification “∀Intro”?
  3. Describe an interpretation which satisfies the proof's premises, but does not satisfy ∀z:Qzz Qz .

Footnotes

  1. 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.)
  2. 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”.

Content actions

Give Feedback:

E-mail the module authors | Rate module ( How does the rating system work?)

Rating system

Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

(0 ratings)

Download:

Module PDF

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.

| A lens (?)

Definition of a lens

Lenses

A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual Connexions member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks