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

"Метод используется для нахождения всех минимальных покрытий конституент единицы и позволяет получить все тупиковые ДНФ по импликантной матрице. Суть метода заключается в следующем. По импликантной матрице строится так называемое конъюнктивное представление мипликантной матрицы. Для этого все простые импли-канты обозначаются разными буквами (обычно прописными латин-скими). После этого, для каждого 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₃."

Алгоритм Квайна

1.Минимизируемая булева функция fот произвольного числаnпеременных записывается в СДНФf₀.

2.Начиная с f₀, строим последовательность ДНФf₀,f₁, . . .,f_i, . . . до тех пор пока две какие либо ДНФf_kиf_k+1не совпадут между собой. Переход от формыf_iкf_i+1по следующему правилу: в формеf_iвыполняются все операции неполного склеивания

применимые к элементарным произведениям длины n=. После этого исключаются все те элементарные произведения длины, которые могут быть исключены на основании формулы элементарного поглощения:

.

3.Результатом алгоритма Квайна к функции fявляется заключительная ДНФf_k.

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

Пример:

Операцию неполного склеивания можно применить к 1 и 3 элементу формулы, к 1 и 2, а также к 1 и 4. В результате получим:

Применяя формулу поглощения, получим:

Поскольку операция неполного склеивания дальше неприменима, f₁– сокращенная ДНФ.

Диаграмма Вейча

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

Для осуществления минимизации в таблице необходимо выделить смежные элементы, которыми являются для матрицы Aэлементыи. Причем, операция сложения выполняется по модулюn, гдеn– размерность матрицы. Таким образом, элементы из первой и последней строки, из первого и последнего столбца могут быть смежными. Затем выбираются группы смежных элементов, количество которых должно быть степенью двойки. Эти группы определяют импликанты. Причем количество сомножителей в импликанте определяется как, гдеn– число аргументов функции,- степень двойки для группы элементов. При составлении импликанты исключаются переменные, для которых единица имеется и в части отрицания для переменной и в части, где отрицание отсутствует. Необходимо выбрать группы так, чтобы их количество было минимально, и все единицы в таблице входили бы в группы (выбираются группы с максимальным). Полученные импликанты связываются знаком дизъюнкции.

Пример: