Дизъюнктивная совершенная нормальная форма.
Булевы переменные будем обозначать . Строку булевых переменных обозначаем . Для обозначим
Мы видим, что это просто другое обозначение операции эквивалентности. Если -- булевы строки длины n как и выше, то обозначим
Для подмножества обозначим через ее характеристическую функцию , принимающую значение 1 на строках из B и принимающую значение 0 на строках из дополнения .
ЛЕММА. тогда и только тогда, когда .
ТЕОРЕМА 2.
Имеет место равенство
Для любой булевой функции обозначим через множество . Тогда и представление функции F в виде (3) называется дизъюнктивной нормальной совершенной формой функции .
Заметим, что ДСНФ не всегда экономна. Например, обозначая операцию отрицания штрихом, будем иметь:
Первое равенство объясняется так . Второе можно проверить непосредственно, подставляя
-
Содержание
- Спасское Городище 2012
- Введение
- Список обозначений и терминов
- Немного о бейсиКе
- Делимость целых чисел
- Алгоритм Евклида
- Матричная алгебра
- Определители
- Обратная матрица
- Компьютерная реализация матричной алгебры
- Линейные преобразования плоскости
- Комплексные числа
- Конструкция поля комплексных чисел.
- Сопряжение комплексных чисел
- Тригонометрическая форма записи комплексных чисел
- Комплексная экспонента
- Решение квадратных уравнений.
- Основная теорема алгебры комплексных чисел
- Алгебраические системы
- Операции и отношения на множестве
- Моноиды
- Поля и тела
- Подсистемы алгебраических систем
- Декартово произведение алгебраических систем
- Фактор системы
- Изоморфизм алгебраических систем
- Абелевы группы
- Группа подстановок
- Алгебра многочленов
- Немного комбинаторики
- Биномиальные коэффициенты
- Числа Фибоначчи
- Рациональные числа
- Дерево Штерна-Брокко
- Алгебра высказываний
- Дизъюнктивная совершенная нормальная форма.
- Конъюнктивная нормальная совершенная форма
- Многочлены Жегалкина
- Алгебра кватернионов.
- Литература