Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 24

GATE

Рассмотрим бинарное отношение:

S = {(x, y) | y = x+1 and x, y ∈ {0, 1, 2, ...}}

Рефлексивное транзитивное замыкание S является
(A) {(x, y) | y> x и x, y ∈ {0, 1, 2,…}}
(B) {(x, y) | y ≥ x и x, y ∈ {0, 1, 2,…}}
(C) {(x, y) | y <x и x, y ∈ {0, 1, 2,…}}
(D) {(x, y) | y ≤ x и x, y ∈ {0, 1, 2,…}}

Ответ: (Б)
Объяснение:
Рефлексивное замыкание отношения R на множестве S является наименьшим рефлексивным отношением, которое содержит R.

Если S = {(0, 1), (1, 2)}, мы делаем его рефлексивным, принимая его объединение с множеством {(0, 0), (1, 1), (2, 2)}.
Таким образом, рефлексивное замыкание S = {(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)}.

Теперь транзитивное замыкание определяется как наименьшее транзитивное отношение, которое содержит S.

Мы проверяем, где это нарушает свойство транзитивности, затем добавляем соответствующую пару.
У нас есть (0, 1) и (1, 2), но нет (0, 2).
Итак, S = {(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2)} сейчас.

Таким образом, вариант (B) соответствует окончательному набору S.

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

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

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

ВОРОТА | GATE-CS-2004 | Вопрос 24

0.00 (0%) 0 votes