Skip to content Skip to navigation

Connexions

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

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is '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 (What is 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.

    • External bookmarks
  • E-mail the authors

Recently Viewed

Exercises for First-Order Logic

Module by: Ian Barland, John Greiner, Fuching Chi

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, or transitive?

Exercise 2

How would you define addsToaddsTo as a ternary relation?

  1. Give a prose definition of addsTo⁡(x,y,z)addsTo⁡(x,y,z) in terms of the 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 (kk+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,bb in the domain, (atLeastAsWiseAs⁡(a,b)∨atLeastAsWiseAs⁡(b,a))(atLeastAsWiseAs⁡(a,b)∨atLeastAsWiseAs⁡(b,a))
  • For arbitrary aa in the domain, (prime⁡(a)→(odd⁡(a)→prime⁡(a)))(prime⁡(a)→(odd⁡(a)→prime⁡(a)))
  • For arbitrary aa,bb in the domain, (betterThan⁡(a,b)→¬ betterThan⁡(b,a) )(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 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.

Hint:

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, piratesNextTo⁡(A,2)piratesNextTo⁡(A,2) will be true. Of course, piratesNextTo⁡(A,1)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 5

  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 piratesNextTo⁡(17,2)piratesNextTo⁡(17,2) and piratesNextTo⁡(W,B)piratesNextTo⁡(W,B). Adding isNumber?isNumber?, any interpretation would be expected to satisfy, for arbitray aa,bb, (piratesNextTo⁡(a,b)→(isNumber?⁡(b)∧¬ isNumber?⁡(a,b) ))(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 relations 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 ba b ∈ RR 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.

Quantifiers

Exercise 8

Let P⁡(x)P⁡(x) be the statement “has been to Prague”, where the domain consists of your classmates.

  1. 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)
    • ∃x. ¬P⁡(x)∃x.¬P⁡(x)
    • ∀x. ¬P⁡(x)∀x.¬P⁡(x)
    • ¬ ∃x. ¬P⁡(x) ¬ ∃x. ¬P⁡(x)
    • ¬ ∀x. ¬P⁡(x) ¬ ∀x. ¬P⁡(x)
  2. Which of these mean the same thing?

Exercise 9

Let C⁡(x)C⁡(x) be the statement “xx has a cat”, let D⁡(x)D⁡(x) be the statement “xx has a dog”, and let F⁡(x)F⁡(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=2)∃x.( x 2 2 )
  2. ∃x. (x2=-1)∃x.( x 2 -1 )
  3. ∀x. x2+2≥1∀x. x 2 2 1
  4. ∀x. (x2≠x)∀x.( x 2 x )

Interpreting First-order Formulas

Exercise 11

Let P⁡(x)P⁡(x), Q⁡(x)Q⁡(x), R⁡(x)R⁡(x), and S⁡(x)S⁡(x) 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 P⁡(x)P⁡(x), Q⁡(x)Q⁡(x), R⁡(x)R⁡(x), and S⁡(x)S⁡(x).

  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. ((P⁡(y)∧(y>2))→E⁡(y))∃y.((P⁡(y)∧(y2))→E⁡(y)) , 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 “∃y.∃y.”.
  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. ((A⁡(x)∧B⁡(x,y))→A⁡(y))∀x.∀y.((A⁡(x)∧B⁡(x,y))→A⁡(y)) 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, and 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.

  1. “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
  2. “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'”.
  3. “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”. (Careful — this may be different than “somebody who is against/for you”).
  4. “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 16

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

hint:

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 kth⁡(k,n)kth⁡(k,n) 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 . (This is reminiscent of expressing an array's contents as a function.) You can also use the binary relations =, <, and ≤ but no others.

You may assume that kthkth models a sequence, i.e., it has no “holes”, indices without a corresponding value followed by indices with a corresponding value.

  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-descending 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 expressing “Binary relation RR is a unary function.”

Exercise 20

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

hint:

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.
  • S1: ∀x. ∀y. ∃z. (likes⁡(x,y)∧((z≠y)→¬ likes⁡(y,z) ))∀x.∀y.∃z.(likes⁡(x,y)∧(( z y)→¬ likes⁡(y,z) ))
  • S2: ∃x. ∀y. ∀z. (likes⁡(x,y)∧((z≠y)→¬ likes⁡(y,z) ))∃x.∀y.∀z.(likes⁡(x,y)∧(( z y)→¬ likes⁡(y,z) ))
  • S3: ∃x. ∃y. ∀z. (likes⁡(x,y)∧((z≠y)→¬ likes⁡(y,z) ))∃x.∃y.∀z.(likes⁡(x,y)∧(( z y)→¬ likes⁡(y,z) ))
  • S4: ∀x. ∃y. ∀z. (likes⁡(x,y)∧((z≠y)→¬ likes⁡(y,z) ))∀x.∃y.∀z.(likes⁡(x,y)∧(( z y)→¬ likes⁡(y,z) ))

  • D1: The empty domain.
  • D2: A world with one person, who likes herself.
  • D3: A world with Yorick and Zelda, where Yorick likes Zelda, Zelda likes herself, and that's all.
  • D4: 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 these combinations.
\\D1D2D3D4
S1
S2
S3
S4

Modeling

Exercise 21

Raspberry sherbet with hot fudge (“rshf”) 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 has become popular. It is played on a 9×9 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×3 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 search as axioms 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: value⁡(r,c,v)value⁡(r,c,v) indicates that at row rr, column cc is the value vv. (v=w)(v w) is the standard equality relation. subgrid⁡(g,r,c)subgrid⁡(g,r,c) indicates that subgrid gg includes the location at row rr, column cc.

Provide inference rules for Sudoku. These will modeling 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

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

Exercise 25

A student claims that ∀x. ((A⁡(x)∧B⁡(x))→C⁡(z)) ≡((∀x. A⁡(x) ∧∀x. B⁡(x) )→C⁡(z))∀x. ((A⁡(x)∧B⁡(x))→C⁡(z)) ≡((∀x. A⁡(x) ∧∀x. B⁡(x) )→C⁡(z)) 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.