Let (S, ≤) be a partial order with two minimal elements a and b, and a maximum…

GATE · 2003 · CS

Let (S, ≤) be a partial order with two minimal elements a and b, and a maximum element c.

Let P : S → {True, False} be a predicate defined on S.
Suppose that P(a) = True, P(b) = False and 
P(x) ⇒ P(y) for all x, y ∈ S satisfying x ≤ y, 
where ⇒ stands for logical implication.

Which of the following statements CANNOT be true ?

A.
P(x) = True for all x ∈ S such that x ≠ b
B.
P(x) = False for all x ∈ S such that x ≠ a and x ≠ c
C.
P(x) = False for all x ∈ S such that b ≤ x and x ≠ c
D.
P(x) = False for all x ∈ S such that a ≤ x and b ≤ x

Attempted by 72 students.

Explore the full course: Gate Guidance By Sanchit Sir