21. Булевы функции. Минимизация булевых функций с помощью карт Карно.

Булева функция (или логическая функция, или функция алгебры логики) от n переменных — отображение A_n → A, где A={0,1} — булево множество.

Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству {0,1}.

Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения A_n называют булевыми векторами.

Булева функция f от n аргументов x_1, x_2, …, x_n обозначается так:

f(x_1, x_2, …, x_n)

Арность функции — количество ее аргументов.

Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2^n. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех n-арных булевых функций равно 2^(2^n). То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц.

Такие таблицы носят название таблиц истинности и в общем случае имеют вид:

Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения.

Представление булевых функций

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

f(x, y, z) = (x ∧ y) ∨ (y ∧ ¬z)

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

f(x, y, z) = (x ∨ y) ∧ (y ∨ ¬z)

Совершенная дизъюнктивная нормальная форма, СДНФ — ДНФ, удовлетворяющая условиям:

в ней нет одинаковых слагаемых;
в каждом слагаемом нет одинаковых сомножителей;
в каждом слагаемом ни одна переменная не содержится вместе со своим отрицанием
в каждом слагаемом присутствуют все переменные или их отрицание.

f(x, y, z) = (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ ¬z)

Совершенная конъюнктивная нормальная форма, СКНФ — это такая КНФ, которая удовлетворяет условиям:

в ней нет одинаковых сомножителей;
в каждом множителе нет одинаковых слагаемых;
в каждом множителе ни одна переменная не содержится вместе со своим отрицанием;
в каждом множителе присутствуют все переменные или их отрицание.

f(x, y, z) = (x ∨ ¬y ∨ z) ∧ (x ∨ y ∨ ¬z)

Минимизация булевых функций с помощью карт

Сокращенная ДНФ — форма записи функции, обладающая следующими свойствами:

любые два слагаемых различаются как минимум в двух позициях;
ни один из конъюнктов не содержится в другом.

Пример:

Решение:

Минимальная ДНФ — такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.

Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная — минимальна. Например, запись

(x ∧ y) ∨ (y ∧ z) ∨ (x ∧ z)

является минимальной ДНФ для медианы (она же сокращенная, как видно в примере выше); а запись

(x ∧ y ∧ ¬z) ∨ (¬x ∧ y ∧ z) ∨ (x ∧ z)

не минимальная, но сокращенная ДНФ.