Skip to content Skip to navigation

Connexions

You are here: Home » Content » Comp280 hw03: 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.

      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
  • E-mail the authors
  • Rate this 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)

Recently Viewed

This feature requires Javascript to be enabled.

Comp280 hw03: First-order logic

Module by: Ian Barland, John Greiner

Summary: Solve these problems!

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.

Due:

2004.Feb.10 (Tues), 17:00, Duncan 3117.

Exercise 1

(2pts) Add yourself to the online grade-database. This part is due by Monday Feb.09, 17:00, so that we can return earlier homeworks to you in class on Tuesday 10th!

First-order logic

Exercise 2

(3 pts.) Rosen, Section 1.3, pg.44, #58.

N.B.:

Carried over from original hw02 assignment.

Hint:

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.

Exercise 3

(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 ∧ y>2 → Ey∃y.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…

  • …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 yy and explain why it does satisfy the body of "∃y.∃y.".)
  • Is their formula still true, when restricted to the domain of natural numbers two or less? (Using the same interpretation of PP, EE. 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".

Exercise 4

(Extra Credit 2 pts) For the sentence ∀x. ∀y. Ax ∧ Bxy → Ay∀x.∀y.Ax ∧ Bxy → Ay state whether it is true or false, relative to the following interpretations:

  1. The domain of the natural numbers, where AA is interpreted as "even?" and BB is interpreted as "equals"
  2. The domain of the Booleans (just {true, false}), where AA is interpreted as "false?" and BB is interpreted as "equals"
  3. 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 AA is interpreted as "safe?" and BB is interpreted as "neighbors"
  4. All WaterWorld boards, where AA is interpreted as "safe?" and BB is interpreted as "neighbors". (That is, is the formula valid for WaterWorld?)

Exercise 5

(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 nhbrnhbr (binary), and unary predicates hasPiratehasPirate, shows3shows3, and shows2shows2.

  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 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?)
  3. "In WaterWorld, location λλ has exactly one neighbor." (Your answer will be a formula with λλ free, just as in the notes we developed formulas like "nn is prime" where nn was free.)
  4. "If a WaterWorld location shows a 3, then any neighboring location is a pirate." (This is only true for certain boards.)
  5. "If a WaterWorld location shows a 1, and has exactly one neighbors, then that neighbor has a pirate." Re-use existing code!

Exercise 6

(Extra Credit 2pts) Write a formula that is the conjunction of

  1. All for one, and one for all!
  2. If you're not for us, you're against us.
  3. The enemy of your enemy is your friend.
  4. Somebody has an enemy. (Not sure of an aphorism expressing this. Maybe, ``Life's not a bed of roses''?)
Use just the relations isForisFor, and isAgainstisAgainst, both to be interpreted on pairs of people. Clarifying some of the ambiguous English:
  • We'll take "one" to mean "one particular person". 1
  • 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").

Aside:

For clarity feel free to express the formula in parts: "φ1 ∧ φ2 ∧ φ3 ∧ φ4φ1 ∧ φ2 ∧ φ3 ∧ φ4, where φ1φ1 = …, φ2φ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.

Exercise 7

(Extra Credit 2pts) For the four-part "Musketeer" formula from the preceding exercise, find two (fundamentally different) interpretations of isForisFor 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.)

Exercise 8

(7pts) Translate the following statements into first-order logic. The domain is to be natural numbers, and the binary relation kthknkthkn indicates whether or not the kkth number of the sequence is nn. That is, for the sequence <5,7,5>, the corresponding relation kthkth is {(1,5), (2,7), (3,5)}. You can also use the binary relations ==, <<, and/or <=<= but no others.

  1. The sequence is finite.
  2. The sequence contains three unique numbers

    Note:

    Containing three numbers doesn't preclude it containing more than three.
  3. 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.)
  4. The sequence is sorted except for (up to) one location. (For example, the sequence < 20, 30, 1, 40, 50 >.)

Exercise 9

(7 pts) 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.
  • S2: ∀x. ∀y. ∃z. likesxy ∧ ¬z=y → ¬likesyz∀x.∀y.∃z.likesxy ∧ ¬=z y → ¬likesyz
  • S3: ∃x. ∀y. ∀z. likesxy ∧ ¬z=y → ¬likesyz∃x.∀y.∀z.likesxy ∧ ¬=z y → ¬likesyz
  • S4: ∃x. ∃y. ∀z. likesxy ∧ ¬z=y → ¬likesyz∃x.∃y.∀z.likesxy ∧ ¬=z y → ¬likesyz
  • S5: ∀x. ∃y. ∀z. likesxy ∧ ¬z=y → ¬likesyz∀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 likeslikes 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 likeslikes.

Table 1: Determine the truth of these combinations.
\\D0D1D2D3
S2
S3
S4
S5

Reasoning with Equivalences

Exercise 10

(4pts) In class, we characterized a prime number as a number zz satisfying ∀q. ∀r. qr=z → q=1 ∨ r=1∀q.∀r.=q r z → =q 1 ∨ =r 1 . Using the algebraic equivalences for first-order logic, show step-by-step that this is equivalent to the formula ¬ ∃q. ∃r. qr=z ∧ ¬q=1 ∧ ¬r=1 ¬ ∃q. ∃r. =qr z ∧ ¬=q 1 ∧ ¬=r 1 .

Exercise 11

(5pts) Simplify the following formula, so that the body of each quantifier contains only a single atomic formula involving that quantified variable. (Recall, an atomic formula is one with no connectives.) Provide reasoning for each step of your simplification.

∀x. ∀y. ∃z. Ax ∧ By → Cz∀x.∀y.∃z.Ax ∧ By → Cz

Reasoning with Inference Rules

Deferred:

These final three exercises will be deferred to hw04 (after we have discussed the first-order inference rules in lecture).

Exercise 12

(4pts) Using the inference rules, formally prove problem (2e).

Exercise 13

(3pts) 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. Ex∃x.Ex premise for subproof
1.b  EcEc ∃∃Elim, by line 1.1
2∃x. Ex → Ec∃x. Ex → Ec  →→Intro, by line 1

Exercise 14

(6pts)

  1. (4pts)Prove the following: ∃x. Px ∀y. Py → Qy ⊢ ∃z. Qz ∃x. Px ∀y. Py → Qy ⊢ ∃z. Qz
  2. Give an interpretation in which these premises are true.
  3. Why can't and shouldn't we conclude ∀z. Qz∀z.Qz ?

Footnotes

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

Comments, questions, feedback, criticisms?

Send feedback