Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 65

Рассмотрим операции
f (X, Y, Z) = X'YZ + XY '+ Y'Z' и g (X ′, Y, Z) = X′YZ + X′YZ ′ + XY
Что из следующего является правильным?
(A) Оба {f} и {g} функционально полны
(B) Только {f} функционально завершен
(C) Только {g} функционально завершен
(D) Ни {f}, ни {g} функционально не полны

Ответ: (Б)
Пояснение: Функция считается функционально завершенной, если она не принадлежит T0, T1, L, M, S, которые

Свойство 1: Мы говорим, что булева функция f сохраняет ноль, если на 0-входе она выдает 0. Под 0-входом мы подразумеваем такой вход, где каждая входная переменная равна 0 (этот вход обычно соответствует первой строке таблица правды). Обозначим класс сохраняющих ноль булевых функций через T0 и запишем f ∈ T0.

Свойство 2: аналогично T0, мы говорим, что булева функция f сохраняет единицу, если на 1-входе она выдает 1. Вход 1 — это вход, где все входные переменные равны 1 (этот вход обычно соответствует последней строке таблица правды). Обозначим класс односохраняющих булевых функций через T1 и запишем f ∈ T1.

Свойство 3: Мы говорим, что булева функция f линейна, если для f выполнено одно из следующих двух утверждений:

  • Для каждого 1-значения f число 1 в соответствующем входе является нечетным, а для каждого 0-значения f количество 1 в соответствующем входе является четным.

или

  • Для каждого 1-значения f число 1 в соответствующем входе является четным, а для каждого 0-значения f количество 1 в соответствующем входе является нечетным.

Если одно из этих утверждений верно для f, мы говорим, что f линейно1. Обозначим класс линейных булевых функций через L и запишем f ∈ L.

Свойство 4: Мы говорим, что булева функция f является монотонной, если для каждого входа переключение любой входной переменной с 0 на 1 может привести только к переключению этой функции значения с 0 на 1, а не с 1 на 0. Обозначим класс монотонные булевы функции с M и записать f ∈ M.

Свойство 5: Мы говорим, что булева функция f (x1,…, xn) является самодуальной, если f (x1,…, xn) = ¬f (¬x1,…, ¬xn).

Функция справа в вышеприведенном равенстве (функция с отрицаниями) называется двойственной функцией f. Мы назовем класс самодвойственных булевых функций S и напишем f ∈ S.

Как и в нашем случае, мы можем видеть, что при задании всех значений i / p для 0 (g) получается 0, поэтому он сохраняет 0 и не может быть функционально завершенным.

Но f не сохраняет ни 0, ни 1.

  • F не является линейным (см. Определение линейного выше)
  • F не является монотонным (см. Определение монотонного выше)
  • F не является самодвойственным, так как f (x, y, z) не равно -f (-x, -y, -z)

Таким образом, функционально полно.

Следовательно, ans является (B) частью
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 65

0.00 (0%) 0 votes