# 3 Refer to the definitions of reflexive, symmetric, antisymmetric, and transitive relations. If R is reflexive, symmetric, antisymmetric and/or transitive, prove.

Question 1. (a) An English statement should be written down.

(b) With the use of the given predicates, translate the statement into a logical expression. (In the statement, only ∀, ∃, ∧, ∨, ¬, and/or → can be used.)

Question 2 The use of truth tables is recommended in both parts.

Please note that there may be no solution, unique solution, or many solutions. In case of many solutions, all solutions should be included.

Question 3 Refer to the definitions of reflexive, symmetric, antisymmetric, and transitive relations.

If R is reflexive, symmetric, antisymmetric and/or transitive, prove.

If R is not reflexive, symmetric, antisymmetric and/or transitive, counter-example should be given.

Question 4 Consider the definitions of set operations (i.e., Powerset and Difference).

If the statement is true, prove. (General case should be considered.)

If the statement is false, give a counter-example.

Question 5.
Refer to the definitions of injective function and bijective function.
Pre-images of elements could be considered.

Question 6.
If the statement is true, prove by contradiction. Assumption should be written down clearly.
If the statement is false, counter-example should be given.

Question 1. Let C(x, y) be the predicate "Student x is a student of the class y", P(x) be the predicate "Student x visited Po Toi Island", T(x) be the predicate "Student x visited Tai 0", where the domain for x contains all students in the college and y contains all classes in the college.

(a) Translate the following logical expression into an English statement: "∃x (C(x, "Geography") ∧ P(x))"

(b) Express the following statement by a logical expression with quantifiers: "There is exactly one student in the "Culture" class who did not visit Tai 0." (In the expression, you can only use ∀, ∃, ∧, ∨, ¬, and/or →.)

Question 2. (a) On a fictional island, all inhabitants are either knights, who always tell the truth, or knaves, who always lie. Assume that you are a visitor to the island. Based on what the inhabitants say, determine who they are. (Steps required)
A says, "B and C are knights".
B says, "A and C are knaves".
C says, "One and only one of A and B is a knave".

(b) Let`s assume that there are three kinds of people on the island. Besides knights and knaves, there are spies who can either lie or tell the truth. Now, you encounter P, Q, and R. Each of them knows the type of person each of the other two is. Moreover, one of them is a knight, one is a knave, and one is a spy. Based on what they say, determine who they are. (Steps required)
P says, "R is a knight".
Q says, "P is a spy".
R says, "Q is not a knave".

Question 3. The binary relation R is defined on Z such that aRb if and only if a and b have the same parity.
(Two integers have the same parity if they are both odd or both even.)
Determine whether R is reflexive, symmetric, antisymmetric and/or transitive. (Steps required)

Question 4. Without drawing a Venn diagram, prove or disprove the following statement:

P(S - T) = P(S) - P(T),

for any non-empty sets S and 7`. (Steps required)

Question 5. The domain and codomain of the following three functions (i.e., f1(), f2() and f3()) are A and B respectively, where A=RxR and B= R.

Determine whether each of the following functions is injective and/or surjective.
(Steps required.)

(a) f1((a,b)) = a + b
(b) f2((a, b)) = a2 - 5
(c) f3((a,b)) = ([b] - [b]) + [a] - [a]

Question 6. Prove by contradiction, or disprove, the following two statements.
(a) 3√5 is irrational.

(b) For any non-empty binary relation R on the set A = {a, b, c, d} , if R is reflexive, transitive and antisymmetric, then R is not symmetric.
(To prove by contradiction, the assumption should be written down clearly.)