Условие:
Являются ли полными следующие системы булевых функций,
Решение:
Мы покажем, что все три указанные системы функций являются полными, то есть каждая из них (при использовании произвольного числа входов) может задавать любую булеву функцию. Ниже приведён подробный разбор по шагам для каждой системы.
──────────────────────────────
- Система {∨, ⊕, ¬}
Шаг 1. Заметим, что уже известна полнота пары {∨, ¬}. Например, по известной схеме из дизъюнкции и отрицания можно получить конъюнкцию по закону Де Моргана:
x ∧ y = ¬(¬x ∨ ¬y).
Шаг 2. Функция ⊕ (исключающее ИЛИ) здесь дополнительно присутствует, но даже если...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи