8,763 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

@arjun Sir how could a<=b since P(a)=true and P(b) =false since true->false is false

I think one very quick way, one can check that $D$ is the wrong option is as follows:

$(S,\leq)$ is a partial order. So it is reflexive, antisymmetric and transitive. Now it is said the $P(a)=True$ But since the partial ordering is reflexive, $a\leq x$ shall include $x=a$ since due to reflexive property $a\leq a$. So as per $D$, $P(a)$ should be $False$. This contradicts the definition.

Option D:

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

is this right??

I think it must be a<x. Here and is written means both a≤x and b≤ x is satisfying .but if a value can be false according to question (given P(x)= False for all x ∈ S) then there won’t be any problem because then False→ anything will be true for a also.

@ASNR1010 @Deepak Poonia Sir what “<=” denote ?? any binary operation or specifically “less than ”operation??

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$

by

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(?)

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.

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

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

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.

1 comment

great explanation!

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

1. True, since ‘a’ and ‘c’ are both true.
2. True, since ‘b’ is false.
3. True, since only (b,b) satisfies the given condition and ‘b’ is false.
4. False, because only x=c satisfies the condition and we know c is true.

by