Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 31

GATE

Пусть (5, ≤) — частичный порядок с двумя минимальными элементами a и b и максимальным элементом c.

Let P : S → {True, False} be a predicate defined on S.
Suppose that P(a) = True, P(b) = False and 
P(x) ⇒ P(y) for all x, y ∈ S satisfying x ≤ y, 
where ⇒ stands for logical implication.

Какое из следующих утверждений не может быть правдой?
(A) P (x) = True для всех x ∈ S, таких что x ≠ b
(B) P (x) = False для всех x ∈ S, таких что x ≠ a и x ≠ c
(C) P (x) = False для всех x ∈ S, таких что b ≤ x и x ≠ c
(D) P (x) = False для всех x ∈ S, таких что a ≤ x и b ≤ x

Ответ: (D)
Объяснение:
«а» и «б» даны как минимальные элементы. Ни один другой элемент в S не имеет более низкого порядка, чем a или b.
«с» задается как максимальный элемент. Таким образом, c имеет более высокий порядок, чем любой другой элемент в S.

P (a) = True означает, что все элементы «x», имеющие ребро от элемента «a», должны быть истинными.
Поскольку существует ребро от 'a', мы должны удовлетворить формулу P (a) => P (x), что можно сделать только установив
P (x) = True.

Элементами, имеющими ребро из b, может быть что угодно, потому что формула P (b) => P (x) выполняется как P (b) = False.

(A) Это утверждение верно, потому что для истинности всех элементов тривиально удовлетворяется формула P (x) => P (y).

(B) Это утверждение верно, если все элементы связаны из b, тогда все элементы могут быть ложными.

(C) Это утверждение верно, потому что b <= x обеспечивает x! = A, а для всех других элементов P (x) может быть ложным, не нарушая данное значение.

(D) Это утверждение неверно. Поскольку P (a) = true, для всех 'x', таких что a <= x, P (x) должно быть истинным. У нас есть по крайней мере один такой «x», который является «c», поскольку это максимальный элемент.

Таким образом, вариант (D) является ответом.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2003 | Вопрос 31

0.00 (0%) 0 votes