Условие:
Выберите функцию, при добавлении которой к множеству функций \{x ⊕ y, x ≤ftrightarrow y\} получается полная система.
(11110001)
(01101001)
(00110011)
(00000000)
Решение:
Наша задача – выбрать такую булеву функцию f, добавление которой к имеющемуся набору функций {x ⊕ y, x ↔ y} ведёт к полной системе, то есть системе, из которой можно получить любую булеву функцию.
Шаг 1. Анализ исходного набора функций
Набор {x ⊕ y, x ↔ y} состоит из двух функций: • x ⊕ y (исключающее ИЛИ) – линейная функция; • x ↔ y (эквиваленция) – функция, обратная исключающему ИЛИ, и также линейна.
Заметим, что обе функции линейны. Любая система, состоящая только из линейных функций, не является функционально полной (она не позволяет выразить, например, нелинейные функции).
Шаг 2. Не...