Dark Mode

8,763 views

51 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?

- P(x) =
**True**for all x \(\in\) S such that x ≠ b - P(x) =
**False**for all x \(\in\) S such that x ≠ a and x ≠ c - P(x) =
**False**for all x \(\in\) S such that b ≤ x and x ≠ c - P(x) =
**False**for all x \(\in\) S such that a ≤ x and b ≤ x

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.

5

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

0

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

0

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

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

Correct Answer: $D$

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/

0

17 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) =Falseand 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.

3 votes

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.

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

- 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

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

Hence, the answer is D.