retagged by
11,560 views
57 votes
57 votes

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
retagged by

6 Answers

Best answer
50 votes
50 votes

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. 

Ref: https://en.wikipedia.org/wiki/Partially_ordered_set

Correct Answer: $D$

edited by
22 votes
22 votes

This is the easiest question in the world if you understand what it says.

two minimal elements a and b, and a maximum element c.

This means that no other element relates to a and b, while every element relates to c. (Research on maximal, maximum, minimal and minimum yourself)

So, the partial order looks like this.

Where these crisscrossed lines represent any network that leads from a to c, and b to c.

We know that a and b are not related, because minimal. But c essentially relates to both.

 

Let P: S → {True, False} be a predicate defined on S.

Now we've attached a predicate to our POSET. Of course, it can have only two values — True or False.

 

 

Suppose that P(a) = True,  P(b) = False and P(x) ⟹ P(y) for all x,y∈S satisfying x≤y

With that Predicate, we gave truth values to a and b.  And for any element x related to y, P(x) —> P(y) (implication statement)

So, our Partial Order can look like this now.

By virtue of implications in Predicate Logic, True —> True, but False —> True or False. (And therefore c is definitely true!)


 

Now lets come to the options. Btw Option D is incorrect straightforward because a relates to x, and a is True so x can't be false. But let's see in details.

  • P(x) = True for all x ∈ S such that x ≠ b

    If x is not b, x can be a. And a is True. So this option can be true.

     
  • P(x) = False for all x ∈ S such that x ≠ a and x ≠ c

    If x is not a or c, we can say x is b. So x is False, and this option can also be true.

     
  • P(x) = False for all x ∈ S such that b ≤ x and x ≠ c

    b is related to x. And x isn't c (c is 100% true, see below) So, x can be False. Because False —> True or False both.

     
  • P(x) = False for all x ∈ S such that a ≤ x and b ≤ x

    a and b are related to x. Whatever a relates to has to be True. Whatever b relates to can be anything. So when both relate to some element, it has to be True. So this option is incorrect

    PS: And hence c is also True.
20 votes
20 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/

Answer:

Related questions

40 votes
40 votes
10 answers
2
Kathleen asked Sep 17, 2014
6,936 views
Consider the set \(\{a, b, c\}\) with binary operators \(+\) and \(*\) defined as follows:$$\begin{array}{|c|c|c|c|} \hline \textbf{+} & \textbf{a}& \textbf{b} &\textbf{c...
33 votes
33 votes
2 answers
3