Let $(S, \leq)$ be a partial order with two minimal elements a and b, and a maximum element c. Let P: S \(\to\) {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) \(\implies\) P(y) for all $x, y \in S$ satisfying $x \leq y$, where $\implies$ stands for logical implication. Which of the following statements CANNOT be true?
This problem is solved at 1:00:22. See for better explanation
Maximum element is $c$: So, $c$ is of higher order than any other element in $S$
Minimal elements are $a$ and $b$: No other element in $S$ is of lower order than either $a$ or $b$.
We are given $P(a) = \text{TRUE}$. So, for all $x$ such that $a \leq x$, $P(x)$ must be $ \text{TRUE}$. We do have at least one such $x$, which is $c$ as it is the maximum element. So, D CANNOT be true.
Ref: https://en.wikipedia.org/wiki/Partially_ordered_set
Sir , I am unable to get the meaning of the question itself , can you please explain it pecisely what do u mean by
@arjun sir...how C option is true
P(x) = False for all x ∈ S such that b ≤ x and x ≠ c
x is related to b when we do not know, x is related to a or not.
Question has four parts-
This tells that whatever element relates to $a$, that has to be TRUE, i.e if $x$ relates to $a$ ($a \leq x$) then $P(x)$ has to be true to hold $P(a) \Rightarrow P(x)$ formula. In option D, $x$ relates to $a$ but they are showing $P(x)$ as false, which can NOT be true.
@Arjun sir...how C option is true
x is related to b , but x can also be related to a as a ≤ x , and in this case P(x)= true since P(a) is true . P(b) is FALSE so it won't affect x (FALSE -> FALSE and FALSE implies TRUE are both TRUE).
‘a’ and ‘b’ are given as minimal elements. No other element in S is of lower order than either a or b. ‘c’ is given as maximum element. So, c is of higher order than any other element in S. P(a) = True means all elements ‘x’ which have an edge from element ‘a’ have to be true. Since there is an edge from ‘a’, we have to satisfy formula P(a) => P(x), which can only be done by setting P(x) = True. Elements which have an edge from b can be anything because formula P(b) => P(x) is satisfied as P(b) = False. (A) This statement is true because making all elements true trivially satisfy formula P(x) => P(y). (B) This statement is true if all elements are connected from b then all elements can be false. (C) This statement is true because b<=x ensures x!=a and for all other elements P(x) can be false without violating the given implication. (D) This statement is false. Since, P(a) = true , 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. Thus, option (D) is the answer. Source - http://quiz.geeksforgeeks.org/gate-gate-cs-2003-question-31/
Gatecse