Skip to content Skip to navigation

Connexions

You are here: Home » Content » homework C solution

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

homework C solution

Module by: Ian Barland, John Greiner. 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)

Summary: (Blank Abstract)

Warning:

The information in this module is outdated. Please see my course for a table of contents.

browser note:

This page meant to be viewed with a MathML-enabled browser. If you see (∀x. (P(x) → (∃y. (P(y) ∨ φ)))) as a nice version of (forall x . (P(x) -> (exists y . (P(y) v phi)))) you're doing okay; If you further see 𝒜 ⊢ ℬ as a nice version of (script-A |- script-B) you're set! If not, either try using mozilla, or check whether there's a .ps or .pdf version of this file available.

Exercise 1

For the sentence (∀x,y. ((A(x) ∧ A(y))→B(x,y))) 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 {true, false}), 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?)

Solution

  • false (4 and 96 are both even, but not equal)
  • true
  • false (But if A were interpreted as "unsafe?", this would be true on this board.)
  • false

Exercise 2

Translate the following conversational English statements into first-order logic, inventing appropriately-named predicates. For the WaterWorld problems, use the set of locations as the domain, and use predicates neighbors (binary), and unary predicates hasPirate, shows3, and shows2.

  • Raspberry sherbet with hot fudge ("rshf") is the tastiest dessert. (What is the intended domain for your formula? What is a relation which makes this statement true? One which makes it false?)
  • All roads lead to Rome, and you can't get there [Rome] from here [Houston] on one road, and all roads go both ways (e.g. a road to a place is also a road from that place). (You can use either: (i) the binary predicate roadEndPoints(a,b) which will be interpreted as "there is a road starting at a and ending at b" over the domain of cities; or (ii) the unary predicates isARoad, isACity, and a ternary predicate roadLeadsFrom(r,a,b) interpreted as "the road r leads from city a to city b" over the domain of cities ∪ roads.)
  • In WaterWorld, location λ has exactly two neighbors. (Your answer will be a formula with λ free.)
  • If a WaterWorld location shows a 3, then any neighboring location is a pirate.
  • If a WaterWorld location shows a 2, and has exactly two neighbors, then both those neighbors have a pirate

Solution

  • For the domain of all desserts, (∀x. ((tastier(rshf,x) ∧ ¬tastier(x,rshf)) ∨ x==rshf)). This is true when tastier is interpreted as the relation {(rshf,yoghurt), (rhsf,truffles), (rshf,Jell-O) (yoghurt,Jell-O)} (and no other pairs of desserts are related via tastier). The formula is false when interpreted as the relation {(oreoShake,rshf),(rshf,oreoShake)} (and no other pairs of desserts are related). Presumably, the relation tastier is going to be antisymmetric on the domain (no two foods are tastier than each other), but you don't need to require this in the formula: In such a strange domain, our formula still captures the idea of "most tasty").
  • Using the predicate roadEndPoints, intended to be interpreted as "there is a road between the two cities", we get: ((∀x,y. (roadEndPoints(x,y)→y=Rome)) ∧ ¬roadEndPoints(Houston,Rome) ∧ (∀x,y. (roadEndPoints(x,y)→roadEndPoints(y,x)))). Note that the first clause is not the same as (∀x. roadEndPoints(x,rome)) -- this translates to "there is a road from every city to Rome". If instead we use the relations isARoad, isACity, and roadLeadsFrom(r,a,b) we could phrase the solution as: ((∀r. (isARoad(r)→(∃c. (isACity(c) ∧ roadLeadsFrom(r,c,Rome)) )) ) ∧ ¬(∃r. roadLeadsFrom(r,houston,Rome)) ∧ (∀r,x,y. (roadLeadsFrom(r,x,y)→roadLeadsFrom(r,y,x)) )).
  • "There are two unique neighbors, but not three unique neighbors": ((∃,. (Nhbr(λ,μ) ∧ Nhbr(λ,ν) ∧ (λ ≠ μ) ∧ (λ ≠ ν) ∧ (μ ≠ ν)) ) ∧ ¬ (∃,,. (Nhbr(λ,μ) ∧ Nhbr(λ,ν) ∧ Nhbr(λ,ρ) ∧ (λ ≠ μ) ∧ (λ ≠ ν) ∧ (λ ≠ ρ) ∧ (μ ≠ ν) ∧ (μ ≠ ρ) ∧ (ν ≠ ρ)) ) ), interpreted over the domain of WaterWorld locations.
  • (∀x. (shows3(x)→(∀y. (Nhbr(x,y)→hasPirate(y)) )) )
  • (∀. ((shows2(λ) ∧ hasExactly2Nhbrs(λ))→(∃,. ((μ ≠ ν) ∧ Nhbr(λ,μ) ∧ Nhbr(λ,ν) ∧ hasPirate(μ) ∧ hasPirate(ν)) )) ), where really "hasExactly2Nhbrs(λ)" is shorthand for the entire formula from part (c) above. It's a bit strange, to have the hasExactly2Nhbrs part of the formula locate and identify the unique neighbors, and then we forget about them and re-find "(∃,. ...)". This is fine; you could also modify the hasExactly2Nhbrs part to include an assertion that μ and ν have pirates.

Exercise 3

Translate the following statements into predicate logic. The domain is to be numbers, and the binary relation kth(n,k) indicates whether or not n is the kth number, in some sequence-of-numbers. That is, for the sequence <4,7,4>, the relation kth is {(4,1), (7,2), (4,3)}. You can also use the binary relations =, <, and/or <= but no others.

  • The sequence is finite.
  • The sequence contains three unique numbers.
  • 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.

Solution

  • (∃k. ¬(∃n. kth(n,k)))
  • (∃a,b,c,i,j,k. ((a ≠ b) ∧ (a ≠ c) ∧ (b ≠ c) ∧ kth(a,i) ∧ kth(b,j) ∧ kth(c,k)) ). Another phrasing would be (∃a,b,c. ((a ≠ b) ∧ (a ≠ c) ∧ (b ≠ c) ∧ (∃k. kth(a,k)) ∧ (∃k. kth(b,k)) ∧ (∃k. kth(c,k))) ). Observe that the trait "contains three unique numbers" does not mean "only contains three unique numbers" (though you could express that concept as well, if you like).
  • The sequence is sorted ascending (with duplicates allowed) iff (∀a,b,i,j. ((i <= j ∧ kth(a,i) ∧ kth(b,j))→a <= b) ) This holds for both infinite and finite sequences, as long as kth models a sequence as described.
  • We'll let z represent the index of the one (possibly) out-of-order element, and just repeat the above formula but if either of the indices i,j is z, then we don't require the ordering part to hold. This would almost work, but we also need to tack on a clause which allows the empty sequence (which certainly doesn't have more than one out-of-order element in it). ((∃z. (∀a,b,i,j. ((z = i) ∨ (z = j) ∨ ((i <= j ∧ kth(a,i) ∧ kth(b,j))→a <= b)) ) ) ∨ ¬ (∃n,k. kth(n,k)) ) Another equivalent approach is to say "it is not the case, that there exist two out-of-order elements i and j". This is a bit unwieldy, because "i is an out-of-order element" means "there exists k which witnesses i out of order, where k isn't j", and a witness can either be a larger or a smaller index (each case needing its own subformula).

Exercise 4

In class, we characterized a prime number as a number z satisfying ¬(∃q. (∃r. ((q*r = z) ∧ (q ≠ 1) ∧ (r ≠ 1)))) . Using the laws of algebra for predicate calculus (and those for propositional calculus), show step-by-step that this is equivalent to the formula (∀q. (∀r. ((q*r = z)→((q = 1) ∨ (r = 1))) ))

Solution

¬(∃q. (∃r. ((q*r = z) ∧ (q ≠ 1) ∧ (r ≠ 1))))

= (∀q. ¬(∃r. ((q*r = z) ∧ (q ≠ 1) ∧ (r ≠ 1))) ). [law 3.6 (backwards): ¬ over ∀]

= (∀q. (∀r. ¬ ((q*r = z) ∧ (q ≠ 1) ∧ (r ≠ 1)) ) ). [law 3.6 (backwards): ¬ over ∀ again]

= (∀q. (∀r. (¬(q*r = z) ∨ (q = 1) ∨ (r = 1)) ) ). [propositional algebra: DeMorgan's (twice), and expanding the ≠ shorthand.]

= (∀q. (∀r. ((q*r = z)→((q = 1) ∨ (r = 1))) ) ). [propositional algebra: Conversion from → to ∨.]

Exercise 5

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

hint:

To help yourself, you might want to develop an English version of what the logic sentences say.
  • S1: (∀x. (∃y. (∀z. (likes(x, y) ∧ ((z ≠ y)→¬likes(y,z))) ) ) )
  • S2: (∀x. (∀y. (∃z. (likes(x, y) ∧ ((z ≠ y)→¬likes(y,z))) ) ) )
  • S3: (∃x. (∀y. (∀z. (likes(x, y) ∧ ((z ≠ y)→¬likes(y,z))) ) ))
  • S4: (∃x. (∃y. (∀z. (likes(x, y) ∧ ((z ≠ y)→¬likes(y,z))) ) ))

  • U0: The empty universe.
  • U1: A world with one person, who doesn't like herself.
  • U2: A world with Yorick and Zelda, where Yorick likes Zelda, Zelda likes herself, (and that's all).
  • U3: 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. (You may wish to sketch the graph of this universe to yourself, where the edge relation is "likes".)

Table 1
\\U0U1U2U3
S1
S2
S3
S4

Solution

  • S1: "everybody likes Y, and Y dislikes everybody else"
  • S2: "everybody likes everybody, and there's somebody all others dislike"
  • S3: "somebody likes everybody, and everybody dislikes all others"
  • S4: "somebody (X) likes some person (Y) who dislikes all others"
Table 2
//U0U1U2U3
S1 truefalsetruefalse
S2 truefalsefalsefalse
S3 falsefalsefalsefalse
S4 falsefalsetruefalse

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