given – ∃x∃y∃z ( R(x,y)∧R(z,y)∧R(x,z)∧¬R(z,x) ).
we only need one set of x, y, z to make this true.
Option A: U = N, R(x,y) : x < y
R(x,y)∧R(z,y)∧R(x,z)∧¬R(z,x) → (x<y) ∧ (z<y) ∧ (x<z) ∧ (z>=x). any value of x, y, z such that x < z < y makes this true.
Option B: U = N, R(x,y) : y = x + 1
R(x,y)∧R(z,y)∧R(x,z)∧¬R(z,x) → (y=x+1) ∧ (y=z+1) ∧ (z=x+1) ∧ (x≠z+1).
if this (y=x+1) ∧ (y=z+1) is true, then z = x which makes this (z=x+1) false. Thus, the formula will always be false in this case.
Option C: U = P(N), R(A,B) : A ⊆ B.
R(x,y)∧R(z,y)∧R(x,z)∧¬R(z,x) → (x⊆y) ∧ (z⊆y) ∧ (x⊆z) ∧ ¬(z⊆x). any set x, y, z such that x ⊂ z and z ⊆ y makes this true.
Option D: U = set of all binary strings of length >=1, R(x,y) : y = x0 or y = x1. ( here x0 = x concatination 0 )
R(x,y)∧R(z,y)∧R(x,z)∧¬R(z,x) → (y=x0 v y=x1) ∧ (y=z0 v y=z1) ∧ (z=x0 v z=x1) ∧ (x=z0 v x=z1).
if this (y=x0 v y=x1) ∧ (y=z0 v y=z1) is true, then len(z) = len(x) which makes this (z=x0 v z=x1) false. Thus, the formula will always be false in this case.
Answer:- A, C