9

Лекция №11

Тема: Минимизация булевых функций

План:

1. Основные понятия

2. Аналитическое построение сокращённой ДНФ.

3. Геометрическое представление функций алгебры логики

4. Локальные алгоритмы

5. Алгоритм Куайна.

6. Диаграммы Вейча –Карно.

1. Основные понятия

Пусть задан алфавит переменных {x₁, x₂, … , x_n}. Логическое произведение K_i = x_i1^1 & x_i2^2 &…& x_ir^r, где 0  r  n и x^= x при  =1 и x^= при  =0, называется элементарной конъюнкцией ранга r, если все переменные в нем различны (т.е. i_i_ при ).

Константа 1 считается элементарной конъюнкцией нулевого ранга.

Логическая сумма D_i = x_i1^1  x_i2^2 … x_ir^r, где 0  r  n, называется элементарной дизъюнкцией ранга r, если все переменные в ней различны.

Константа 0 считается элементарной дизъюнкцией нулевого ранга.

Формула вида D = K₁  K₂ … K_s, где K₁, K₂,…, K_s – различные элементарные конъюнкции рангов r₁, r₂,…, r_s соответственно, называется дизъюнктивной нормальной формой (ДНФ).

Формула вида K = D₁ & D₂ &…& D_s, где D₁, D₂,…, D_s – различные элементарные дизъюнкции рангов r₁, r₂,…, r_s соответственно, называется конъюнктивной нормальной формой (КНФ).

Всякая истинностная функция, не равная тождественно нулю (единице) может быть выражена в виде ДНФ (КНФ). Будет ли такое представление единственным?

Теорема: О числе различных ДНФ.

Число различных ДНФ, которые могут быть построены для функций от n переменных равно 2³ⁿ.

Пример:

Таблица 1

x	y	z	f(x,y,z)
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Пусть функция задана таблицей истинности (см. таблицу 19). Тогда для неё можно записать СДНФ:

СДНФ=. (Здесь и далее для компактности записи пропущен знак «&».) Выполнив преобразования, получим ДНФ₁=, затем ДНФ₂=. Далее ДНФ₃=. Нетрудно убедиться, что у этой функции имеются и другие ДНФ.

Среди всех ДНФ (КНФ), реализующих некоторую функцию, естественно можно выбрать наиболее простую. Критерием простоты может служить число букв в записи ДНФ, или число элементарных конъюнкций, или число символов «» над буквами.

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

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

Построение минимальных и кратчайших ДНФ –это две различные задачи. Множества МДНФ и КДНФ для одной и той же функции могут находиться в любых отношениях: содержаться одно в другом, или не иметь пересечения, или пересекаться. Но на начальном этапе эти задачи имеют много общего, и поэтому можно ограничиться каким-то конкретным критерием. Обычно в качестве такого критерия рассматривается число букв в ДНФ.

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

Заметим, что в силу двойственности ДНФ и КНФ, в задаче минимизации булевой функции обычно рассматривают только построение минимальных ДНФ. При этом исходными данными обычно считают таблицу истинности функции или совершенную ДНФ (СДНФ). Существует так называемый тривиальный алгоритм построения всех МДНФ для произвольной булевой функции f(x₁, x₂, …, x_n). Он состоит в просмотре всех различных ДНФ, которые могут быть построены над алфавитом {x₁, x₂, …, x_n}, и выделении тех из них, которые реализуют функцию f и имеют наименьшую сложность. Однако, в виду того, что общее число ДНФ от n переменных равно 2³ⁿ, тривиальный алгоритм фактически неприменим даже при небольших значениях n.

ДНФ, которую нельзя упростить с помощью этих двух преобразований, называют тупиковой ДНФ (ТДНФ) относительно удаления конъюнкции и множителей в конъюнкциях. Например, ДНФ= является тупиковой.

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