Булевы функции. Основные булевы функции, их преобразования. Нормальные формы. Полнота системы булевых функций

Булевы функции. Основные булевы функции, их преобразования. Нормальные формы. Полнота системы  булевых функций.

Булева функция от n аргументов — в дискретной математике — отображение Bⁿ → B, где B = {0,1} — булево множество. Элементы булева множества {1, 0} обычно интерпретируют как логические значения «истинно» и «ложно». Неотрицательное целое число n называют арностью или местностью функции, в случае n =0 булева функция превращается в булеву константу. Элементы декартова произведения (n-я прямая степень) Bⁿ называют булевыми векторами. Множество всех булевых функций от любого числа аргументов часто обозначается P₂, а от n аргументов — P₂(n). Переменные, принимающие значения из булева множества называются булевыми переменными. Булевы функции названы по фамилии математика Джорджа Буля.

Каждая булева функция  арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2ⁿ.

Практически все булевы функции  малых арностей (0, 1, 2 и 3) сложились исторически и имеют конкретные имена.

Булева функция задаётся конечным набором значений, что позволяет  представить её в виде таблицы истинности.

Нульарные функции

При n = 0 количество булевых функций сводится к двум 2²⁰ = 2¹ = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица (тавтология).

Унарные функции

При n = 1 число булевых функций равно 2²¹ = 2² = 4. (тождественный ноль, тождественная единица(тавтология), отрицание, тождественная функция).

Бинарные функции

При n = 2 число булевых функций равно 2²² = 2⁴ = 16. (тождественный ноль, стрелка Пи́рса, инверсия обратной импликации, отрицание первого операнда, инверсия прямой импликации, отрицание второго операнда, сложение по модулю 2,штрих Ше́ффера, конъюнкция, эквивалентность, второй операнд, прямая импликация, первый операнд, обратная импликация , дизъюнкция, тождественная единица.)

Тернарные функции

При n = 3 число булевых функций равно 2⁽²³⁾ = 2⁸ = 256

Система булевых функций  называется полной, если можно построить их суперпозицию, тождественную любой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством  .

Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:

• Функции, сохраняющие константу   и  ;
• Самодвойственные функции S;
• Монотонные функции M;
• Линейные функции L.

Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций.

Совершенной дизъюнктивной  нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке.

Конъюнктивной нормальная форма  КНФ — это конъюнкция простых дизъюнкций.

Совершенной конъюнктивной  нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке.

КНФ может быть преобразована  к эквивалентной ей ДНФ по правилу:

      От ДНФ к КНФ

Любая булева формула может быть приведена к КНФ и ДНФ. Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.

Алгебраическая  нормальная форма или полином Жегалкина  — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции («И»), а в качестве сложения — сложение по модулю 2 (исключающее «ИЛИ», XOR). Для получения полинома Жегалкина следует выполнить следующие действия:

1. Получить СДНФ функции
2. Все ИЛИ заменить на Исключающее ИЛИ
3. Во всех термах заменить элементы с отрицанием на конструкцию: («элемент» «исключающее ИЛИ»)
4. Раскрыть скобки по правилам алгебры Жегалкина и привести попарно одинаковые термы