1.

Let (A, ≤) be a partial order with two minimal elements a, b and a maximum element c. Let P:A –>{True, False} be a predicate defined on A. Suppose that P(a) = True, P(b) = False and P(a) ⇒ P(b) for all satisfying a ≤ b, where ⇒ stands for logical implication. Which of the following statements cannot be true?(a) P(x) = True for all xS such that x ≠ b(b) P(x) = False for all x ∈ S such that b ≤ x and x ≠ c(c) P(x) = False for all x ∈ S such that x ≠ a and x ≠ c(d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ xThe question was asked in an online interview.I would like to ask this question from Relations topic in division Relations of Discrete Mathematics

Answer»

The correct choice is (d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x

To explain I WOULD say: Here, maximum element is c and so c is of a higher order than any other element in A. Minimal elements are a and b: No other element in A is of lower order than either a or b.

We are GIVEN P(a) = True. So, for all x such that a≤x, P(x) must be True. We do have at least one such x, which is c as it is the maximum element. So, P(x) = False for all x ∈ S such that a ≤ x and b ≤ x -> cannot be true. P(x) = True for all xS such that x ≠ b -> can be True as all elements mapped to TRUE doesn’t violate the given implication. P(x) = False for all x ∈ S such that x ≠ a and x ≠ c -> can be True if a is RELATED only to c. P(x) = False for all x ∈ S such that b ≤ x and x ≠ c -> can be True as b≤x ensures x≠a and for all other elements P(x) can be False without violating the given implication.


Discussion

No Comment Found

Related InterviewSolutions