Основные понятия. Пусть задан алфавит переменных {x1, x2, , xn}

Пусть задан алфавит переменных { x ₁, x ₂, …, x_n }. Логическое произведение K_i = x_{i 1} ^{s 1} & x_{i 2} ^{s 2} &…& x_ir^sr, где 0 £ r £ n и x^s = x при s =1 и x^s =при s =0, называется элементарной конъюнкцией ранга r, если все переменные в нем различны (т.е. i_a ¹ i_b при a¹b).

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

Логическая сумма D_i = x_{i 1} ^{s 1} Ú x_{i 2} ^{s 2} Ú…Ú x_ir^sr, где 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 соответственно, называется конъюнктивной нормальной формой (КНФ).

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

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

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

Доказательство:

В дизъюнктивную нормальную форму для функций от n переменных { x ₁, x ₂,…, x_n } могут входить конъюнкции нулевого, первого, второго и т.д, n -го рангов. Причем, число конъюнкций нулевого ранга может быть не больше единицы. (Его можно рассматривать как число нуль элементных подмножеств n -множества, оно равно биномиальному коэффициенту и равно 1.)

Число конъюнкций 1–го ранга равно 2 n. Каждую конъюнкцию 1–го ранга можно рассматривать как одноэлементное подмножество n -множества. А число таких подмножеств равно , но элемент в конъюнкции может быть либо x_i, либо , поэтому общее число конъюнкций 1–го ранга будет вдвое больше и равно 2 n.

Конъюнкции 2–го ранга можно рассматривать как двухэлементные подмножества n -множества. Число таких подмножеств равно , но каждый из двух элементов конъюнкции может быть либо x_i, либо , поэтому общее число конъюнкций 2–го ранга будет вчетверо больше и равно 2²

Аналогично определяется число конъюнкций k– го ранга, оно равно 2 ^k . И общее число различных конъюнкций над алфавитом { x ₁, x ₂,…, x_n } равно сумме: . Поскольку различные ДНФ отличаются друг от друга совокупностью входящих в них конъюнкций, то их общее число равно 2^{3 n}. Так как число различных функций алгебры логики от n переменных равно 2^{2 n}, и 2^{2 n} < 2^{3 n}, то представление функции в виде ДНФ не может быть единственным.

Из этой теоремы следует также, что число различных СДНФ для функций алгебры логики от n переменных равно 2^{2 n}, так как СДНФ состоят только из конъюнкций ранга n, а их число равно 2 ⁿ =2 ⁿ. Тем самым, каждая функция представляется в виде СДНФ единственным образом.

Пример:

Таблица 19

x	y	z	f (x, y, z)

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

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

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

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

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

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

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

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

Для решения задачи минимизации разработано довольно много других алгоритмов, которые легко могут быть запрограммированы для ЭВМ. Рассмотрим простейшие из них.

Дата добавления: 2014-01-07