GATE CSE 2003 | Question: 31

Question

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?

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

Comments

credit (Grok Go Mentor)

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

Let us assume a minimal size poset S with 3 elements

S =  {a,b,c}

We are given that P(a)=true,P(b) = false but P(c) is not given.

Since the relation is partial order, we can list elements of relation.

R={(a,a)(b,b)(c,c)(a,c)(b,c)}

These elements in relation are due to properties of reflexive antisymmetric and .transitive

We are also given that P(x)->P(y) for all values satisfying x<=y

We apply this property to ordered pairs in the relation above:

(a,a) since a<=a P(a)->P(a) and P(a) is given to be true. So True->True

Now, we need to find P(c)

(a,c) is true because a<=c so P(a)->P(c)

True -> P(c)

Also, (b,c) is true since b<=c and P(b)->P(c) so false ->P(c)

The only way above both statements can be true is P(c) is true else first statement will be false.

So, we have P(a)= true, P(b)= false,

P(c) = true

 

1) P(x)= true for all x!=b which is true since P(a)=P(b)= true

2) P(x)= false for all x!=a or c which again can be true since apart from a and c we have only one element b for which P(b)= false

3) P(x)=false for all x!=c such that b<=x which again can be true since x can be only b and P(b)= false. x cannot be a because both a and b are minimal.

4) P(x)= false such that a<=x and b<=x

This can’t be true since x can be c

and P(c)= true

So answer is option D

---

@Sarthak_Patial Yeah you are correct, i missed the logic that false -> anything is true. only option d is always false while other options can be made true in atleast one case.

---

@legend_of_cse can you explain just option c in a easy way.?

Answer 1

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$

Comments

Can you explain the option B, i am not getting it peoperly!

---

How can there be two minimal elements under ‘<=’ ? they must relate no? either a <= b or b<=a has to be true(?)

---

KartikGawande

they are minimal and not minimum it is possible that they are not related .

eg:

                                                 

here 2 and 3 are minimal elements and not related.

Answer 2

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.

Comments

Much better than all the other explanations.

---

Isint option c amiguious bcz acc to c...... x=a is false

---

Option A: Everything is True except b which is False, False -> anything is anyway true, so it is correct

Option B: if a b and c are the only elements then this also is true, because a and c can be true and only b is false

Option C: b is related to some element x and x is not c so it give, false -> false, which is true and all element we can make true easily

Option D: if a and b are related to an element x then x is false, since a is ture it give, true -> false, which is false, so option D is always false.

in all other options A, B, C we can make it true in atleast one case but in option D it is false in all cases.

correct me if i am wrong?

Answer 3

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

Comments

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

---

@rahul

can u explain the options if u have understood them

its confusing

---

easy to understand

Answer 4

I’ll try explaining in the easiest and intuitive way.

Let us divide the explanation into three parts.

part 1] Given data

part 2] How to interpret the given data

part 3] Finally reaching the solution.

Part 1] Given data

• S={a,b,c}
• POSET[S,$\leq$] such that ‘a’ and ‘b’ are the minimal element. And ‘c’ is the maximum element. (wait for it :p)
• It is also given that P is as follows:

• The last information is that all (x,y) ∈POSET satisfy x → y (implication).

Part 2] How to interpret the given info

• What are maximal and minimal element?

           Maximal element ‘z’ of POSET[S,$\leq$] is an element in the set S such that there exists no element ‘y’ such that (z$\leq$y)

exists.

Similarly, Minimal element ‘z’ of POSET[S,$\leq$] is an element in the set S such that there exists no element ‘y’ such that (y$\leq$z)

exists.

• Hence using above definitions we can draw the Hasse diagram as follows:

• We know that POSET means ‘Reflexive’, ‘Anti-Symmetric’ and ‘Transitive’ relation.
• Hence using the Hasse diagram and the definition we can conclude that our POSET[S,$\leq$] = { (a,a)  (b,b)  (c,c)  (a,c)  (b,c) }
• And all these pairs have to satisfy x →y as mentioned in the question. We know P(a)=true and P(b)=false.

              

• Now what can be ‘?’. Yes it has to be ‘TRUE’ to satisfy the implication condition. Hence

             

Part 3] Finally reaching the solution

• A. True, since ‘a’ and ‘c’ are both true.
• B. True, since ‘b’ is false.
• C. True, since only (b,b) satisfies the given condition and ‘b’ is false.
• D. False, because only x=c satisfies the condition and we know c is true.

Hence, the answer is D.

Comments

this is the best solution, One thing I would suggest is give reason for why the implication has to be 'TRUE', 

Now what can be ‘?’. Yes it has to be ‘TRUE’ to satisfy the implication condition.

I believe the reason is the given ordered pairs must exist in the relation for sure for it to be a poset if even one of the condition fails then we cannot form a poset.

---

Yes the best answer as it shows the individual mapping of truth values

---

Great Explanation man!!!

Answer 5

Answer is option D 

we will see why

Answer 6

•  a and b are minimal.
• c is maximum.
• P(a) is true and P(b) is false.
• If x≤y, then p(x)⇒p(y)

element relates to a, that has to be true

so optiod d is wrong

reason p(x) is false under condition a≤x which is wrong