hwC: Relations2.42002/04/102002/09/16IanBarlandian@cs.rice.eduJohnGreinergreiner@cs.rice.eduIanBarlandian@cs.rice.eduPeggyFidelmanpeggy@rice.eduJohnGreinergreiner@cs.rice.edu(Blank Abstract)The information in this module is
outdated. Please see my
course for a table of contents.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.
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?)
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
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
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.
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.
(∃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).
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)))
))
¬(∃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 ∨.]
Alternation of quantifiers:
Determine the truth of
each of the following sentences
in each of the indicated universes.
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".)
\\U0U1U2U3S1 S2 S3 S4
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"