Метод диаграмм Вейча

Метод получает МДНФ булевой функции небольшого числа переменных. Булевы функции задаются в виде специальных диаграмм. Для функции 2-х переменных и 3-х переменных:

Добавление к диаграмме 3-х переменных еще такой же даст диаграмму 4-х переменных, если приписать еще одну диаграмму 4-х переменных, то получим диаграмму для функции 5-ти переменных.

Правила склеивания конституэнт "1" на диаграммах Вейча: склеиванию подлежат прямоугольные конфигурации, заполненные конституэнтами "1" и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Минимизация булевой функции заключается в нахождении минимального накрытия всех единиц диаграммы Вейча блоками из единиц, расположенных в соседних клетках диаграммы.

Примеры: Булевы функции заданы диаграммами Вейча. Найти их МДНФ.

17. Минимизация конъюнктивных нормальных форм

Минимизация КНФ проводится аналогично минимизации ДНФ булевых функций. Конституэнта "0" – функция = 0 на одном наборе.

Определение: Имплицентой булевой функции называется функция, принимающая значение 0 на подмножестве нулевых наборов функции . Простой имплицентой функции называется элементарная дизъюнкция, являющаяся имплицентой функции , причем никакая ее собственная часть уже имплицентой функции не является.

Задача минимизации КНФ – определение МКНФ – решается в два этапа: поиск СкКНФ (конъюнкция всех простых имплицент) и затем нахождение МКНФ с помощью таблицы Квайна, где рассматривается, поглощает ли данная простая имплицента конституэнту "0" или нет в соответствии с соотношением поглощения:

Для первого этапа: соотношения склеивания по Квайну

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

Пример: функция, заданная МДНФ дает возможность определить ее СкКНФ:

По диаграмме Вейча для поиска МКНФ анализируются лишь нулевые наборы и переменные выписываются с инверсиями:

МKНФ:

МДНФ:

18. Метод Петрика

Метод используется для нахождения всех минимальных покрытий конституент единицы и позволяет получить все тупиковые ДНФ по импликантной матрице. Суть метода заключается в следующем. По импликантной матрице строится так называемое конъюнктивное представление мипликантной матрицы. Для этого все простые импли-канты обозначаются разными буквами (обычно прописными латин-скими). После этого, для каждого i -ro столбца импликантной матрицы строится дизъюнкция всех букв, обозначающих строки матрицы, пересечение которых с i -м столбцом отмечено крестиком. Конъюнктивное представление импликантной матрицы образуется как конъюнкция построенных дизъюнкций для всех столбцов матрицы. К конъюнктивному представлению матрицы могут быть применены все соотношения булевой алгебры с целью его упрощения. После раскрытия скобок и выполнения всех возможных поглощений получается дизъюнкция конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ.
Пример.
Задана импликантная матрица (табл. 4.6.1). Найти методом Петрика все тупиковые ДНФ булевой функции f, описываемой данной матрицей.

Таблица 4.6.1
Простые импликанты	Конституенты единицы
/x1/x2/x3x4	/x1/x2x3x4	/x1x2/x3x4	/x1x2x3x4	x1x2x3/x4	x1x2x3x4
/x1x4	X	X	X	X
x2x3x4				X		X
x1x2x3					Х	Х

Имеющиеся простые импликанты обозначим буквами:

/x₁x₄ = A. x₂x₃x₄ = B. x₁x₂x₃ = C.

Тогда конъюнктивное представление w матрицы имеет вид

w = A*A*A*(A v B)*C(B v C).

Упростим его.

w = A*(A v B)*C(B v C) = AC.

Тупиковая ДНФ содержит две простые импликанты: А = /x₁x₄ и C = x₁x₂x₃ и имеем вид f = /x₁x₄ v x₁x₂x₃."