logic questions redux Flashcards Preview

logic > logic questions redux > Flashcards

Flashcards in logic questions redux Deck (103):
1

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.

2

Explain the difference between ∅ and {∅}.

Set {∅} is a set with a member ∅, but ∅ is a set containing no member

3

What is the composition of {(n, n + 2) | n ∈ N} with itself?

It is {(n, n + 4) | n ∈ N}

4

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.

5

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)

6

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.

7

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.

8

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.

9

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.

10

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.

11

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

12

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

13

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.

14

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 r

15

Write 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”.

16

Which of the following are formulas in propositional logic:
• p → ¬q
• ¬¬ ∧ q ∨ p
• p¬q

Only the first one

17

Construct truth tables for the following formula:
• (p → q) ∨ (q → p),

(p → q) ∨ (q → p)

0 1 0 1 0 1 0
0 1 1 1 1 0 0
1 0 0 1 0 1 1
1 1 1 1 1 1 1

18

Construct truth tables for the following formulas:
• ((p ∨ ¬q) ∧ r) ↔ (¬(p ∧ r) ∨ q).

((p ∨ ¬ q) ∧ r) ↔ (¬ (p ∧ r) ∨ q)

0 1 1 0 0 0 0 1 0 0 0 1 0
0 1 1 0 1 1 1 1 0 0 1 1 0
0 0 0 1 0 0 0 1 0 0 0 1 1
0 0 0 1 0 1 0 1 0 0 1 1 1
1 1 1 0 0 0 0 1 1 0 0 1 0
1 1 1 0 1 1 0 0 1 1 1 0 0
1 1 0 1 0 0 0 1 1 0 0 1 1
1 1 0 1 1 1 1 0 1 1 1 1 1

19

Using truth tables, investigate all formulas that can be readings of
¬p → q ∨ r
(by inserting brackets in appropriate places), and show that they are not equivalent

e.g.
(¬p → q) ∨ r and ¬(p → (q ∨ r))

20

Using a truth table, determine if the two formulas
¬p → (q ∨ r), ¬q
together logically imply
(1) p ∧ r.
(2) p ∨ r.
Display the complete truth table, and use it to justify your answers to (1) and (2).

p q r ¬p ¬q q ∨ r ¬p →
(q ∨ r)
p ∧ r p ∨ r
0 0 0 1 1 0 0 0 0
0 0 1 1 1 1 1 0 1
0 1 0 1 0 1 1 0 0
0 1 1 1 0 1 1 0 1
1 0 0 0 1 0 1 0 1
1 0 1 0 1 1 1 1 1
1 1 0 0 0 1 1 0 1
1 1 1 0 0 1 1 1 1

You can check by inspecting the rows of the table that p ∧ r is not a valid consequence
and p ∨ r is.

21

Which of the following pairs are logically equivalent? Confirm your answer using
truth tables:
(1) ϕ → ψ and ψ → ϕ
(2) ϕ → ψ and ¬ψ → ¬ϕ
(3) ¬(ϕ → ψ) and ϕ ∨ ¬ψ
(4) ¬(ϕ → ψ) and ϕ ∧ ¬ψ
(5) ¬(ϕ ↔ ψ) and ¬ϕ ↔ ¬ψ
(6) ¬(ϕ ↔ ψ) and ¬ϕ ↔ ψ
(7) (ϕ ∧ ψ) ↔ (ϕ ∨ ψ) and ϕ ↔ ψ

By comparing the first and the second tables below you can determine that the equivalence does not hold for item (3)
while by comparing the first and the third tables below you can determine that the equivalence does hold for item (4).
The other items are similar.

¬ (p → q)
0 0 1 0
0 0 1 1
1 1 0 0
0 1 1 1


p ∨ ¬ q
0 1 1 0
0 0 0 1
1 1 1 0
1 1 0 1


p ∧ ¬ q
0 0 1 0
0 0 0 1
1 1 1 0
1 0 0 1

22

Check if the following is a valid consequence:
¬(q ∧ r), q |= ¬r

¬(q ∧ r)
=⇒
q
q r
_ _
q r q r
_ _
q r q r
_ _ _ _ _
q r q r q r

23

Check if the following is a valid consequence:
¬p ∨ ¬q ∨ r, q ∨ r, p |= r

¬p ∨ ¬q ∨ r
q ∨ r
p



p q r
_
p q r p q r
_ _
p q r p q r
_ _ _ _
p q r p q r p q r
_ _ _
p q r p q r p q r
_ _ _ _ _
p q r p q r p q r
_ _ _ _ _ _
p q r p q r p q r p q r
_ _ _ _ _ _ _ _ _
p q r p q r p q r p q r

24

Give truth tables for the following formula:
(p ∨ q) ∨ ¬(p ∨ (q ∧ r))

(p ∨ q) ∨ ¬ (p ∨ (q ∧ r))
0 0 0 1 1 0 0 0 0 0 1
0 0 0 1 1 0 0 0 0 1 1
0 1 1 1 1 0 0 1 0 0 1
0 1 1 1 0 0 1 1 1 1 1
1 1 0 1 0 1 1 0 0 0 1
1 1 0 1 0 1 1 0 0 1 1
1 1 1 1 0 1 1 1 0 0 1
1 1 1 1 0 1 1 1 1 1 1

25

Give truth tables for the following formula:
¬((¬p ∨ ¬(q ∧ r)) ∨ (p ∧ r))


¬ ((¬ p ∨ ¬ (q ∧ r)) ∨ (p ∧ r))
0 1 0 1 1 0 0 0 1 0 0 0 0
0 1 0 1 1 0 0 1 1 0 0 1 0
0 1 0 1 1 1 0 0 1 0 0 0 0
0 1 0 1 0 1 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 0 0 1 1 1 1 1 0
0 0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 0 0 1 1 1 1 1 1 1 0

26

Give truth tables for the following formula:
(p → (q → r)) → ((p → q) → (p → r))


(p → (q → r)) → ((p → q) → (p → r))
0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 1 1 0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 1 1 0 1 1 1
1 1 0 1 0 1 1 0 0 1 1 0 0 1
1 1 0 1 1 1 1 0 0 1 1 1 1 1
1 0 1 0 0 1 1 1 1 0 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1

27

Give truth tables for the following formula:
(p ↔ (q → r)) ↔ ((p ↔ q) → r)

(p ↔ (q → r)) ↔ ((p ↔ q) → r)
0 0 0 1 0 1 0 1 0 0 0 1
0 0 0 1 1 0 0 1 0 1 1 0
0 1 1 0 0 1 0 0 1 1 0 1
0 0 1 1 1 0 0 0 1 1 1 0
1 1 0 1 0 1 1 0 0 1 0 1
1 1 0 1 1 1 1 0 0 1 1 1
1 0 1 0 0 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1

28

Give truth tables for the following formula:
((p ↔ q) ∧ (¬q → r)) ↔ (¬(p ↔ r) → q)

((p ↔ q) ∧ (¬ q → r)) ↔ (¬ (p ↔ r) → q)
0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0
0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 0
0 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0
0 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0
1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1
1 0 0 0 1 0 1 1 0 0 1 1 1 1 0 0
1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 1
1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1

29

Define all connectives in terms of ¬ and ∧.

ϕ ∨ ψ ≡ ¬(¬ϕ ∧ ¬ψ)
ϕ → ψ ≡ ¬ϕ ∨ ψ
ϕ ↔ ψ ≡ (ϕ → ψ) ∧ (ψ → ϕ)
ϕ ⊕ ψ ≡ ¬(ϕ ↔ ψ)
ϕ | ψ ≡ ¬(ϕ ∧ ψ)

30

Define all connectives in terms of ¬ and →

ϕ ∧ ψ ≡ ϕ → ¬ψ
ϕ ∨ ψ ≡ ¬(¬ϕ ∧ ¬ψ)
ϕ ↔ ψ ≡ (ϕ → ψ) ∧ (ψ → ϕ)
ϕ ⊕ ψ ≡ ¬(ϕ ↔ ψ)
ϕ | ψ ≡ ¬(ϕ ∧ ψ)

31

Prove that all propositional connectives are definable with the ‘Sheffer stroke’
ϕ | ψ,
defined by ¬ϕ ∨ ¬ψ


p q s1: ¬P = P|P s2: P∧Q = p | q s3: (?) q | q s4: True = p | s1 s5: (?) p | s2 s6: p→q q | s1 s7: p^q = s1 | s3 s2 | s4 s2 | s7
1 1 0 0 0 1 1 1 1 1 1
1 0 0 1 1 1 0 1 1 0 0
0 1 1 1 0 1 1 0 1 0 0
0 0 1 1 1 1 1 1 0 0 1

32

Give an example of a formula φ and a Kripke model M, with the following properties:
(i) M |= φ, and (ii) M | φ 6|= φ. In other words, public announcement of φ has the
effect that φ becomes false.

The simplest example is a model where p is true but agent a does not know
that. Then publicly announcing ‘p is true, but you don’t know it’ will result in a
situation where what gets announced is falsified by the announcement itself. The
formula for this is p ∧ ¬Kap.

33

Prove that lfp (λS.S ∪ (Sˇ ◦ S)) R is the euclidean closure of R.

similar to the reasoning in the previous exercise. Let f = λS.S ∪ (Sˇ ◦ S),
and let E = lfp f R.
Then f is monotone, i.e., for all arguments X, X ⊆ f(X). In particular, R ⊆
f(R) ⊆ . . . ⊆ E. This shows that R ⊆ E.
We show that E is euclidean. Since E is a fixpoint, E = f(E), i.e., E = E∪(Eˇ◦E).
In other words, Eˇ◦E ⊆ E. It follows from this that E is euclidean by an argument
given in the course slides.
Finally, we show that E is the smallest euclidean relation that includes R. Let S be
an arbitrary euclidean relation with R ⊆ S. From euclideanness of S it follows that
Sˇ ◦ S ⊆ S. Therefore, S = f(S), i.e., S is a fixpoint. Since E is the least fixpoint
it follows that E ⊆ S.

34

Prove that lfp (λS.S ∪(S ◦ S)) R is the transitive closure of R. (lfp f c is the least fixpoint of the operation f, starting from c.)

Let f = λS.S ∪ (S ◦ S), and let T = lfp f R.
Then f is monotone, i.e., for all arguments X, X ⊆ f(X). In particular, R ⊆ f(R) ⊆ . . . ⊆ T. This shows that R ⊆ T.
We show that T is transitive. Since T is a fixpoint, T = f(T), i.e., T = T ∪(T ◦ T).
In other words, T ◦ T ⊆ T. It follows from this that T is transitive by the result of the first exercise

Finally, we show that T is the smallest transitive relation that includes R. Let S be an arbitrary transitive relation with R ⊆ S. From transitivity of S it follows that S ◦ S ⊆ S. Therefore, S = f(S), i.e., S is a fixpoint. Since T is the least fixpoint it follows that T ⊆ S.

35

Prove that
R ∪ (Rˇ ◦ (R ∪ Rˇ)∗ ◦ R)
is the euclidean closure of R.

Let E be the relation R ∪ (Rˇ ◦ (R ∪ Rˇ)∗ ◦ R). Clearly, R ⊆ E.
We show that E is euclidean. Let (x, y) ∈ E,(x, z) ∈ E. Then there are three cases to consider.
Case 1. (x, y) ∈ R,(x, z) ∈ R. Then (y, z) ∈ Rˇ ◦ R. Since Rˇ ◦ R ⊆ E, it follows that (y, z) ∈ E.
Case 2. (x, y) ∈ R, (x, z) ∈ Rˇ ◦ (R ∪ Rˇ)m ◦ R, for some m ∈ N.
From the givens, (y, z) ∈ Rˇ ◦ Rˇ ◦ (R ∪ Rˇ)m ◦ R.
It follows that (y, z) ∈ Rˇ ◦ (R ∪ Rˇ)m+1 ◦ R, and therefore (y, z) ∈ E.

Case 3. (x, y) ∈ Rˇ ◦ (R ∪ Rˇ)∗ ◦ R, (x, z) ∈ Rˇ ◦ (R ∪ Rˇ)∗ ◦ R. Now we get from the euclideanness of Rˇ ◦ (R ∪ Rˇ)∗ ◦ R (proved in a previous exercise) that (y, z) ∈ Rˇ ◦ (R ∪ Rˇ)∗ ◦ R, and therefore (y, z) ∈ E.

Finally, we have to prove that E is the smallest relation with the required properties.
Let S be an arbitrary euclidean relation that includes R. We must show that E ⊆ S.
Since S is euclidean, we know from the previous exercise that Sˇ◦ (S ∪Sˇ)∗ ◦S ⊆ S.
Since R ⊆ S we also have
Rˇ ◦ (R ∪ Rˇ)∗
◦ R ⊆ Sˇ ◦ (S ∪ Sˇ)∗
◦ S ⊆ S.
From this, together with R ⊆ S, it follows that E ⊆ S.

36

Prove by induction that if R is an euclidean relation, then Rˇ ◦ (R ∪ Rˇ)∗ ◦ R ⊆ R.

Basis: Rˇ ◦ R ⊆ R. This follows from the euclideanness of R.
Induction step. The induction hypothesis is that Rˇ◦ (R ∪ Rˇ)n ◦ R ⊆ R. We must prove that Rˇ ◦ (R ∪ Rˇ)n+1 ◦ R ⊆ R.
We are done if we can prove the following two facts: (i) Rˇ◦ R ◦ (R ∪ Rˇ)n ◦ R ⊆ R, and (ii) Rˇ ◦ Rˇ ◦ (R ∪ Rˇ)n ◦ R ⊆ R.

(i) Assume (x, y) ∈ Rˇ ◦ R ◦ (R ∪ Rˇ)n ◦ R. Then there is a z with (x, z) ∈ Rˇ ◦ R and (z, y) ∈ (R ∪ Rˇ)n ◦ R.
By the fact that Rˇ◦R is symmetric, (z, x) ∈ Rˇ◦R. From this and euclideanness of R, (z, x) ∈ R, and therefore (x, z) ∈ Rˇ. Combining this with (z, y) ∈ (R ∪ Rˇ)n ◦ R
we get that (x, y) ∈ Rˇ ◦ (R ∪ Rˇ)n ◦ R, from which it follows by the induction hypothesis that (x, y) ∈ R.

(ii) Assume (x, y) ∈ Rˇ◦ Rˇ◦ (R ∪ Rˇ)n ◦ R. Then there is a z with (x, z) ∈ Rˇ and (z, y) ∈ Rˇ ◦ (R ∪ Rˇ)n ◦ R. From the first of these, (z, x) ∈ R. From the second of these, by induction hypothesis, (z, y) ∈ R. From (z, x) ∈ R and (z, y) ∈ R by euclideanness of R, (x, y) ∈ R

37

Show that for any relation R, the relation Rˇ◦ (R∪Rˇ)∗ ◦R is symmetric, transitive and euclidean.

Use E for Rˇ◦(R∪Rˇ)∗ ◦R. For symmetry of E, let (x, y) ∈ E. Then there is some m ∈ N with (x, y) ∈ Rˇ ◦ (R ∪ Rˇ)m ◦ R. So there are z, u with (x, z) ∈ Rˇ, (z, u) ∈ (R ∪ Rˇ)m, (u, y) ∈ R. But then (y, u) ∈ Rˇ, (u, z) ∈ (R ∪ Rˇ)m, (z, x) ∈ R.

It follows that (y, x) ∈ Rˇ ◦ (R ∪ Rˇ)m ◦ R. and therefore (y, x) ∈ E.
For transitivity, assume (x, y) ∈ E, (y, z) ∈ E. Then there are m, k ∈ N with (x, y) ∈ Rˇ ◦ (R ∪ Rˇ)m ◦ R. (y, z) ∈ Rˇ ◦ (R ∪ Rˇ)k ◦ R. It follows that (x, z) ∈ Rˇ ◦ (R ∪ Rˇ)m+k+2 ◦ R, and therefore (x, z) ∈ E.
Euclideanness: any transitive and symmetric relation is euclidean.

38

Give the euclidean closure of the relation {(1, 2),(2, 3)}.

the relation {(1, 2),(2, 2),(2, 3),(3, 2),(3, 3)}.

39

A partition P of a set A is a set of subsets of A with the following properties:
(a) every member of P is non-empty.
(b) every element of A belongs to some member of P.
(c) different members of P are disjoint.

If R is an equivalence relation on A and a ∈ A then |a|R, the R-class of a, is the set
{b ∈ A | bRa}. Show that the set of R-classes
{|a|R | a ∈ A}
of an equivalence relation R on A forms a partition of A.

We have to check the three properties of partitions.

Since R is a reflexive relation on A, we have that for each a ∈ A it holds that a ∈ |a|R. This takes care of (a) and (b).
Let |a|R and |b|R be two R-classes, and assume that they are not disjoint. Then we have c ∈ |a|R ∩ |b|R.

This means that we have both aRc and bRc. Since R is symmetric, we have cRb, and by transitivity of R, aRb, and again by symmetry of R, bRa.

We can show now that |a|R = |b|R, as follows:
Assume d ∈ |a|R. Then dRa. From this and aRb, by transitivity of R, dRb, i.e., d ∈ |b|R. This shows: |a|R ⊆ |b|R.

Assume d ∈ |b|R. Then dRb. From this and bRa, by transitivity of R, dRa, i.e., d ∈ |a|R. This shows: |b|R ⊆ |a|R.
So if two R-classes |a|R and |b|R are not disjoint, then they are in fact equal. This takes care of (c).

40

Prove that R ∪ Rˇ is the symmetric closure of R

Clearly, R ∪ Rˇ is symmetric, and R ⊆ R ∪ Rˇ.
Let S be any symmetric relation that includes R. By symmetry of S and by the fact that R ⊆ S it follows that Rˇ ⊆ S. Thus R ∪ Rˇ ⊆ S.

41

Let R be a binary relation on a set A. Prove that R∪{(x, x) | x ∈ A} is the reflexive closure of R.

Let I = {(x, x) | x ∈ A}. It is clear that R ∪ I is reflexive, and that
R ⊆ R ∪ I.
To show that R ∪ I is the smallest relation with these two properties, suppose S is reflexive and R ⊆ S. Then by reflexivity of S, I ⊆ S. It follows that R ∪ I ⊆ S.

42

Give an example of a transitive binary relation R with the property that R◦R 6= R.

The simplest example is a relation consisting of a single pair, say R = {(1, 2)}. This relation is transitive, but R ◦ R = ∅ ≠ R.

43

Prove that a binary relation R is transitive iff R ◦ R ⊆ R

⇒: Assume R is a transitive binary relation on A.
To be proved: R ◦ R ⊆ R.
Proof. Let (x, y) ∈ R ◦ R. We must show that (x, y) ∈ R. From the definition of ◦: ∃z ∈ A : (x, z) ∈ R,(z, y) ∈ R. It follows from this and transitivity of R that
(x, y) ∈ R.
⇐: Assume R ◦ R ⊆ R.
To be proved: R is transitive.
Proof. Let (x, y) ∈ R,(y, z) ∈ R. Then (x, z) ∈ R ◦ R. Since R ◦ R ⊆ R, it follows from this that (x, z) ∈ R. Thus, R is transitive.

44

Please paraphrase the following statement: A ⊆ B

set A is a subset of the set B; set A is a non-strict subset of the set B; A is included in B

45

Please paraphrase the following statement:
B ∈ P(A) (or: B ∈ 2^A),

B is a subset of A; B is an element in a set of all subsets of A; B is an element in the power set of A

46

A ⋂ B ≠ ∅

the intersection of A and B is empty; A and B do not have common elements

47

Which set is given by the following specification:
{2n + 1 | n 2 N}
(N is nats)

odd integer numbers

48

A is a set with three elements. Suppose B is a subset of A. What can you say about the
number of elements of B?

B has at most three elements and at least zero

49

A is a set with five elements. f is a one-to-one function from A to B. How many elements can B have?

at least five; five or more

50

A is set with four elements. The power set of A is the set of all subsets of A. How many elements does the power set of A have?

|2^A| = 2^|A| = 2^4 = 16

51

N is the set of natural numbers. How many elements does the power set of N have? The same number of elements as N? More elements? But what does that mean?

N is infinite but countable, 2N is uncountable (lengthy explanation was in the old version of the assignment); it means that we cannot have a bijective mapping between those two

52

Which of the following relations are transitive? Symmetric? Reflexive?:
{(1, 2),(2, 3),(3, 4)}

non-transitive because (1,3); not symmetric because (2,1); irreflexive because (1,1)

53

Which of the following relations are transitive? Symmetric? Reflexive?:
{(1, 1),(1, 2),(1, 3),(2, 1),(2, 2),(3, 2),(3, 3)}

non-transitive because (2,3); not symmetric because (2,3); reflexive

54

Which of the following relations are transitive? Symmetric? Reflexive?:
{(1, 2),(2, 3),(3, 4),(1, 3),(2, 4),(1, 4)}

transitive; not symmetric because (2,1); irreflexive because (1,1)

55

Which of the following relations are transitive? Symmetric? Reflexive?:
{(1, 2),(2, 1)}

non-transitive because (1,1); symmetric; irreflexive because (1,1)

56

Which of the following relations are transitive? Symmetric? Reflexive?:
{(1, 1),(2, 2)}

transitive; symmetric; reflexive

57

Give the transitive closures of each of the relation:
non-transitive because (1,3); not symmetric because (2,1); irreflexive because (1,1)

{(1, 2),(2, 3),(3, 4)}+ =

{(1, 2),(1, 3),(1, 4),(2, 3),(2, 4),(3, 4)}

58

Give the transitive closures of each of the relation:
non-transitive because (2,3); not symmetric because (2,3); reflexive

{(1, 1),(1, 2),(1, 3),(2, 1),(2, 2),(3, 2),(3, 3)}+ =

{(1, 1),(1, 2),(1, 3),(2, 1),(2, 2),(2, 3),(3, 1),(3, 2),(3, 3)}

59

Give the transitive closures of each of the relation:
transitive; not symmetric because (2,1); irreflexive because (1,1)

{(1, 2),(2, 3),(3, 4),(1, 3),(2, 4),(1, 4)}+ =

{(1, 2),(1, 3),(1, 4),(2, 3),(2, 4),(3, 4)}

60

Give the transitive closures of each of the relation:
non-transitive because (1,1); symmetric; irreflexive because (1,1)

{(1, 2),(2, 1)}+ =

{(1, 1),(1, 2),(2, 1),(2, 2)}

61

Give the transitive closures of each of the relation
transitive; symmetric; reflexive

{(1, 1),(2, 2)}+ =

{(1, 1),(2, 2)}

62

If
  v
c
  t

is substitution of v with t in c, then what are the results of the following substitutions?
            y
(∀xRxy)  =
            z

∀XRxz

63

If
  v
c
  t

is substitution of v with t in c, then what are the results of the following substitutions?
                            x
(∀x∀y(Rxy ∨ Ryz)) =
                            y

unchanged

64

If
  v
c
  t

is substitution of v with t in c, then what are the results of the following substitutions?
                              x
((∃xRxy) ^ (∃yRxy))  =
                              y

(∃xRxy) ^ (∃zRyz)

65

Rephrase the following independent statement in natural language:
A ∈ 2^B or A ∈ P(B)

set A is an element of a power set of B; set A is a subset of the set B

66

A = ∅

set A is an empty set; set A has no elements

67

∀x, f

f holds for all x

68

Rephrase the following independent statements with quantifiers (∀, ∃, etc; do not use ∩, ∪, \):

A ⊆ B \ C

∀x ∈ A, x ∈ B ∧ x ∉ C, or ∀x, x ∈ A ⇒ x ∈ B ∧ x ∉ C

69

Rephrase the following independent statements with quantifiers (∀, ∃, etc; do not use ∩, ∪, \):

|A ∪ B| = 0

∄x : x ∈ A ∨ x ∈ B

70

Rephrase the following independent statements with quantifiers (∀, ∃, etc; do not use ∩, ∪, \):
A ∩ B ∈ 2 ^C

∀x : x ∈ A ∧ x ∈ B ⇒ x ∈ C

71

Rephrase the following independent statements with relations on sets (⊆, \, ∪, ∩, etc; do not use any quantifiers):

∀x ∉ A, x ∈ B

_
A = B, or I \ A = B, or I \ B = A
(where I is the universal set)

72

Rephrase the following independent statements with relations on sets (⊆, \, ∪, ∩, etc; do not use any quantifiers):

∃x ∉ A, x ∈ B

B \ A ≠ ∅

73

Rephrase the following independent statements with relations on sets (⊆, \, ∪, ∩, etc; do not use any quantifiers):

∃A ∈ 2^B, ∃x ∈ A

B ≠ ∅, or |B| > 0

74

Consider the following less than relation on natural numbers:
< = {(n, m) | n ∈ N, m ∈ N, n < m}

N is Nat

Is < reflexive? Irreflexive? Symmetric? Asymmetric? Antisymmetric? Transitive?

Not reflexive because (1, 1) ∉

75

Define the transitive closure and the reflexive transitive closure of the relation from the previous question.

Any (preferably formal) definition of the following:

76

is this statement true (a tautology):
|= ∃xP x ∨ ¬∃xP x.

Yes

77

is this statement true (a tautology):
|= ∃xP x ∨ ∀x¬P x.

Yes

78

is this statement true (a tautology):
|= ∀xP x ∨ ∀x¬P x

No

79

is this statement true (a tautology):
|= ∀xP x ∨ ∃x¬P x

Yes

80

is this statement true (a tautology):
|= ∃x∃yRxy → ∃xRxx.

No

81

is this statement true (a tautology):
|= ∀x∀yRxy → ∀xRxx

Yes

82

is this statement true (a tautology):
|= ∃x∃yRxy → ∃x∃yRyx

No

83

is this statement true (a tautology):
|= ∀xRxx ∨ ∃x∃y¬Rxy.

No

84

is this statement true (a tautology):
|= ∀xRxx → ∀x∃yRxy

Yes

85

is this statement true (a tautology):
|= ∃xRxx → ∀x∃yRxy

No

86

is this statement true (a tautology):
|= ∀x∀y∀z((Rxy ∧ Ryz) → Rxz)

No

87

does the following statement hold?
∀xP x |= ∃xP x

Holds because we assume nonempty domains

88

does the following statement hold?
∃xP x |= ∀xP x

Doesn’t hold:
D = {1, 2}, I(P) = {1},

89

does the following statement hold?
∀xRxx |= ∀x∃yRxy

Holds because we can chose the same object twice

90

does the following statement hold?
∀x∀yRxy |= ∀xRxx

Doesn’t hold: D = {1, 2}, I(R) = {(1, 2),(2, 1)},

91

does the following statement hold?
∃x∃yRxy |= ∃xRxx

Doesn’t hold: D = {1, 2}, I(R) = {(1, 2)},

92

does the following statement hold?
∀x∃yRxy |= ∀xRxx

Doesn’t hold: D = {1, 2}, I(R) = {(1, 2),(2, 2)},

93

does the following statement hold?
∃y∀xRxy |= ∀x∃yRxy

Holds because we can reuse the choice for
y in the premise when we chose again in the conclusion

94

does the following statement hold?
x∃yRxy |= ∃y∀xRxy

Doesn’t hold: D = {1, 2}, I(R) = {(1, 2),(2, 1)}

95

does the following statement hold?
∃x∃yRxy |= ∃x∃yRyx

Doesn’t hold: D = {1, 2}, I(R) = {(1, 2)}

96

does the following statement hold?
∀xRxx |= ∀x∃yRxy

Holds because we can chose the same object twice

97

does the following statement hold?
∃xRxx |= ∃x∃yRxy

Holds because the same object can be chosen for both x and y in the conclusion.

98

does the following statement hold?
∀x∀y(Rxy → Ryx), Rab |= Rba

Holds

99

does the following statement hold?
∀x∀y(Rxy → Ryx), Rab |= Raa

doesn't Hold

100

does the following statement hold?
∀x∀y∀z((Rxy ∧ Ryz) → Rxz), Rab, Rac |= Rbc

doesn't Hold

101

does the following statement hold?
∀x∀y∀z((Rxy ∧ Ryz) → Rxz), Rab, Rab |= Rac

doesn't Hold

102

does the following statement hold?
∀x∀y∀z((Rxy ∧ Ryz) → Rxz), Rab, ¬Rac |= ¬Rbc

Holds,

103

does the following statement hold?
∀x∀y∀z((Rxy ∧ Ryz) → Rxz), ∀x∀y(Rxy → Ryx), Rab |= Raa

Holds,