+30 votes
2.5k views

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?

1. P(x) = True for all x $\in$ S such that x ≠ b
2. P(x) = False for all x $\in$ S such that x ≠ a and x ≠ c
3. P(x) = False for all x $\in$ S such that b ≤ x and x ≠ c
4. P(x) = False for all x $\in$ S such that a ≤ x and b ≤ x
asked
retagged | 2.5k views
+6

This problem is solved at 1:00:22. See for better explanation

## 2 Answers

+26 votes
Best answer

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.

• A can be TRUE as all elements mapped to TRUE doesn't violate the given implication.
• B can be TRUE if $a$ is related only to $c$.
• C can be TRUE as $b \leq x$ ensures $x \neq a$ and for all other elements $P(x)$ can be FALSE without violaing the given implication.

Correct Answer: $D$

answered by Veteran (399k points)
edited
0

Sir , I am unable to get the meaning of the question itself , can you please explain it pecisely what do u mean by

• A can be TRUE as all elements mapped to TRUE doesn't violate the given implication.
0
Question is simple- it just has two parts. S is a partial order. So, for any two elements we have a lub and glb.

Now, the second part says if a <= b, then P(a) implies P(b).

After this we can simply try out the four options.
+1
Sir, I am not getting the part that how can we conclude P(x) to be true or false until we know whether x<=y or not and it's the implication part only which we can be sure of , since here for one minimal element P(b) is false ,and for other minimal element P(a) is true , a bit confused with  the terminology used here .
+4
they used the terminology to create confusion only :)

We are given bottom most element a has TRUE value (P(a) = TRUE). Now, whatever element is related to a must be TRUE rt? Not every element need to be related to a (this is a partial order and not a total order) but c being the top element, it must be related to a and hence must be TRUE. See option C, without x != c, that also would be FALSE.
0
Sir ,just last confusion in option D , it says that an element is related to both a and b ,Now for P(a) we have its truth value as true while for P(b),its truth value is false , so then how are we concluding that P(x) will be true.
+4
x is related to both b and a. But P(b) is FALSE so it won't affect x (FALSE -> FALSE and FALSE implies TRUE are both TRUE). We have a problem with a only as P(a) is TRUE and hence we need to ensure P(x) is TRUE if x is related to a.
+1
i think : this hasse diag. can describe all

c

/      \

a.       b
0
Terminology is really confusing!
0
@Arjun : Does this question is assuming that there is only three elements in poset S i.e. {a,b,c}
0
No. No restriction like that.
0

@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.

+1
FOR OPTION C :

Now here b≤x(ensures that x cannot be a)

according to question

P(x) ⟹P(y) whenever x≤y

b is minimal element therefore

P(b) ⟹P(x) (as b is always smaller than x)

p(b) is given to be false

false ⟹anything is TRUE

thus option c is true

(in implication only true implies false is false)
+20

Question has four parts-

• $a$ and $b$ are minimal.
• $c$ is maximum.
• $P(a)$ is true and $P(b)$ is false.
• If $x \leq y$, then $P(x) \Rightarrow P(y)$.

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.

–1
@Arjun sir ,How do we satisfy c option. The one case i can think is of poset with only a b and c.Now excluding a and c.Now we can say say all x s.t b≤x is true since there is no such element except c and if nothing is there,we can assume it is true. Is there any other case possible?I mean is there by anyway we can make any p(x) false,except b?
0

@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 , 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).

0
Thank you, Arjun sir for such a nice solution and discussion.
0
Thank u sachin mittal for a simple and clear solution.
0
x $\leq$ a and a $\leq$ x holds in the above case (symmetric)

Then how the relation be in Partial order ?
+6 votes

‘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/

answered by Boss (25.4k points)
–1
In B option ,all elements cant be connected to b only as we have only one maximum element and 2 minimal.Even if you take minimal elements in poset, c must be connected to both a and b otherwise we will have 2 maximal.

Moreover False=> anything is true always
0
@rahul

can u explain the options if u have understood them

its confusing
Answer:

+25 votes
5 answers
2
+19 votes
1 answer
4
+16 votes
5 answers
6
+13 votes
3 answers
7