logic questions Flashcards
Explain why ∅ ⊆ A holds for every set A.
If every member of a set A is also a member of set B we say that A is a subset of B.
But there is no element which is a member of ∅, the precondition of the definition is false, so the conditional in whole holds vacuously.
That is, for every set A, ∅ ⊆ A.
Explain the difference between ∅ and {∅}.
Set {∅} is a set with a member ∅, but ∅ is a set containing no member
What is the composition of {(n, n + 2) | n ∈ N} with itself?
It is {(n, n + 4) | n ∈ N}
Show that it follows from Rˇ⊆ R that R = Rˇ
We need to show R ⊆ Rˇ.
For every x, y, (x, y) ∈ R, (y, x) ∈ Rˇ.
Then (y, x) ∈ R since Rˇ⊆ R.
It follows that (x, y) ∈ Rˇ, as required.
Which of the following relations are transitive?
(1) {(1, 2),(2, 3),(3, 4)}
(2) {(1, 2),(2, 3),(3, 4),(1, 3),(2, 4)}
(3) {(1, 2),(2, 3),(3, 4),(1, 3),(2, 4),(1, 4)}
(4) {(1, 2),(2, 1)}
(5) {(1, 1),(2, 2)}
(3) and (5)
Check that a relation R is transitive if and only if it holds that R ◦ R ⊆ R
First check the direction from left to right.
Suppose R is transitive and for arbitrary x, y, (x, y) ∈ R ◦ R.
It means that there exists some z such that (x, z) ∈ R and (z, y) ∈ R.
Since R is transitive, we can have that (x, y) ∈ R as well. Next check the direction from right to left.
Suppose R ◦ R ⊆ R and for arbitrary x, y, z, (x, y) ∈ R and (y, z) ∈ R.
Then (x, z) ∈ R ◦ R.
It follows that (x, z) ∈ R since R ◦ R ⊆ R, as required.
Can you give an example of a transitive relation R for which R ◦ R = R does not hold?
Yes.
Please see the relation < on N.
It is clear that this relation is transitive but < ◦ <=< (over N) does not hold.
Show that any asymmetric relation has to be irreflexive. (Hint: assume that a relation is asymmetric, and suppose it contains a loop (x, x). Why is this impossible?)
Assume that a relation R is asymmetric, and suppose it contains a loop (x, x).
But by the definition of asymmetric, for every x, y, (x, y) ∈ R → (y, x) ∈/ R.
It follows (x, x) ∈/ R since (x, x) ∈ R, a contradiction.
So any asymmetric has to be irreflexive.
Consider the three predicate logical sentences (A.1), (A.3) and (A.6), These sentences together express that a certain binary relation R is an equivalence relation: symmetric, transitive and reflexive.
Show that none of these sentences is semantically entailed by the other ones by choosing for each pair of sentences a model (situation) that makes these two sentences true but makes the third sentence false.
In other words: find three examples of binary relations,
each satisfying just two of the properties in the list (A.1), (A.3) and (A.6).
This shows, essentially, that the definition of being an equivalence cannot be simplified (why?).
(/R)TS = {(2, 1),(1, 2)};
R(/T)S = {(1, 1),(2, 2),(3, 3),(1, 2),(2, 1),(2, 3),(3, 2)};
RT(/S) = {(1, 1),(2, 2),(1, 2)}.
What these examples show is that reflexivity does not follow from transitivity and symmetry, that transitivity does not follow from reflexivity and symmetry, and that symmetry does not follow from reflexivity and transitivity.
Consider the following predicate logical formulas:
• ∀x∀y(Rxy → ¬Ryx) (R is asymmetric)
• ∀x∃yRxy (R is serial)
• ∀x∀y∀z((Rxy ∧ Ryz) → Rxz) (R is transitive).
Take any situation with a non-empty domain of discourse, with a binary relation on it.
Show: if the three formulas are true of this situation, then the domain of discourse must be infinite.
(Hint: start with a domain consisting of a single individual d1.
Then by seriality there has to be an R successor to d1. Suppose we take d1 as its own R-successor. Then this would get us in conflict with we are in conflict with asymmetry.
So there has to be a d2 with (d1, d2) in R.
And so on . . . )
Base case: Proved in the text.
Induction Hypothesis: If |M| < n then ∃x∃y(Rxy ∧ Ryx) or ∃x∀y¬Rxy or ∃x∃y∃z(Rxy ∧ Ryx ∧ ¬Rxz).
Induction step:
take an arbitrary model such that |M| = n − 1
and build M0 with dom(M0) = dom(M) ∪ {a}, such that R0 = R ∪ Ra
where Ra ⊆ RA
with RA = {(x, y) | x ∈ dom(M), y = a} ∪ {(x, y) | y ∈ dom(M), x = a} ∪ {(x, y) | x = a, y = a}.
If ∃x∃y∃z(Rxy ∧ Ryx ∧ ¬Rxz)
then ∃x∃y∃z(R’xy∧R’yx∧¬R’xz) and we are done.
If ∃x∃y(Rxy∧Ryx) then ∃x∃y(R’xy∧R’yx) and we are done.
If ¬∃x∃y(Rxy ∧ Ryx) and ¬∃x∃y∃z(Rxy ∧ Ryx ∧ ¬Rxz) and ∃x∀y¬Rxy then if for some x ∈ M that has no successor we have ¬R’xa we are done.
Suppose that for all x ∈ M that have no successors we have R’xa, then in order for M’ to be serial we need to have R’ay for some y ∈ M’.
If Raa then asymmetry is violated and we are done.
Take an arbitrary z ∈ M’
such that R’za and z (/=) a then if we have R’az, asymmetry is again violated and we are
done. If, for arbitrary z, y ∈ M’ we have R’za, R’ay and y (/=) z we have to consider two cases.
If ¬Ryz then transitivity is violated and we are done. In case Ryz then we have R’ay, R’yz, and R’za.
If we satisfy transitivity of R’ then we must also have R’aa which in turn violates the asymmetry condition.
The successor function s : N ↦ N on the natural numbers is given by n ↦ n + 1.
What is the composition of s with itself?
n ↦ n + 2
≤ is a binary relation on the natural numbers.
What is the corresponding characteristic function?
The corresponding characteristic function is f : N² → {True, False}.
For every pair (m, n) ∈ N²,
if m ≤ n
then f((m, n)) = True,
otherwise, f((m, n)) = false.Let f : A → B be a function. Show that the relation R ⊆ A² given by (x, y) ∈ R if and only if f(x) = f(y) is an equivalence relation (reflexive, transitive and symmetric) on A.
Let f : A → B be a function. Show that the relation R ⊆ AN² given by (x, y) ∈ R if and only if f(x) = f(y) is an equivalence relation (reflexive, transitive and symmetric) on A.
Suppose relation R ⊆ AN² given by (x, y) ∈ R if and only if f(x) = f(y).
We need to show that R is an equivalence relation.
First check reflexivity:
for every x ∈ A, we havef(x) = f(x) since f is a function. It follows that (x, x) ∈ R, as required.
Next check symmetry:
for every pair (x, y) ∈ R, we have x, y ∈ A and then f(x) = f(y).
It’s clear f(y) = f(x) meaning that (y, x) ∈ R.
Similarly we can check transitivity: for every x, y, zA, (x, y) ∈ R and (y, z) ∈ R, it follows that f(x) = f(y) and f(y) = f(z) by the premise.
Then we have f(x) = f(z).
It follows by the same reason that (x, z) ∈ R, as required.
Consider the case where there are three facts that you are interested in.
You wake up, you open your eyes, and you ask yourself three things:
“Have I overslept?”,
“Is it raining?”,
“Are there traffic jams on the road to work?”.
To find out about the first question, you have to check your alarm clock, to find out about the second you have to look out of the window, and to find out about the third you have to listen to the traffic info on the radio.
We can represent these possible facts with three basic propositions, p, q and r, with p expressing “I have overslept”, q expressing “It is raining”, and r expressing “There are traffic jams.”
Suppose you know nothing yet about the truth of your three facts.
What is the space of possibilities?
_
p q r p q r
_ _ _
p q r p q r
_ _ _
p q r p q r
_ _ _ _ _
p q r p q rWrite in propositional logic:
• I will only go to school if I get a cookie now.
• John and Mary are running.
• A foreign national is entitled to social security if he has legal employment or if he has had such less than three years ago, unless he is currently also employed abroad.
• I will only go to school if I get a cookie now:
(p → q) ∧ (q → p)
where p =“I get a cooky now” and q =“I will go to school”.
• John and Mary are running:
p ∧ q
where p =“John is running” and q =“Mary is running”.
• A foreign national is entitled to social security if he has legal employment or if he
has had such less than three years ago, unless he is currently also employed abroad:
((p ∨ q) ∧ ¬r) → s
where p =“A foreign national has legal employment”, q =“A foreign national has
had legal employment less then three years ago”, r =“A foreign national is currently
also employed abroad” and s =“A foreign national is entitled to social security”.
