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

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

Согласно определению, каждая тупиковая ДНФ определяется таким набором строк, что в таблице, образованной этими строками в каждом столбце имеется одна единица, причём из этого набора нельзя удалить ни одной строки так, чтобы при этом ни один столбец не стал нулевым.

Таблица 3

СДНФ Сокр. ДНФ
P₁	1__0
P₂	101_
P₃	_001
P₄	0_11
P₅	01_1

Пусть в общем случае в таблице имеется N столбцов и m строк. Поставим в соответствие простым импликантам сокращённой ДНФ переменные P₁ … P_m. Фиксируем некоторую дизъюнкцию простых импликант. Будем считать, что P_i = 1, если i-я простая импликанта входит в эту дизъюнкцию и P_i = 0, в противном случае. Запишем в виде формалы условие того, что рассматриваемая дизъюнкция является ДНФ функции. Для этого необходимо, чтобы в каждом столбце таблицы была хотя бы одна единица, т.е.

где — элемент матрицы (таблицы), стоящий в i-й строке и j-м столбце, .

Эту формулу можно трактовать как КНФ некоторой двоичной функции от переменных P₁ … P_m, которая принимает значение 1 только на тех наборах переменных, которые соответствуют некоторым ДНФ исходной функции, и значение 0 — на наборах, которые соответствуют наборам импликант, не являющихся ДНФ исходной функции.

Заметим, что функция монотонна, так как формула 3 не содержит переменных с отрицаниями. Поэтому согласно утверждению 3 для нахождения её сокращённой ДНФ достаточно раскрыть скобки в формуле 3, а затем произвести все поглощения. Наконец, остаётся заметить, что в силу указанного выше свойства этой функции, её простые импликанты и только они будут давать тупиковые ДНФ исходной функции f.

Для табл. 3 функция равна:

Отсюда P₁P₃P₅ даёт для f тупиковую форму:

а P₁P₂P₄P₅ даёт:

Пример.
Задана импликантная матрица (табл. 4.6.1). Найти методом Петрика все тупиковые ДНФ булевой функции f, описываемой данной матрицей.

Таблица 4
Конституенты единицы
Простые импликанты	/x₁/x₂/x₃x₄	/x₁/x₂x₃x₄	/x₁x₂/x₃x₄	/x₁x₂x₃x₄	x₁x₂x₃/x₄	x₁x₂x₃x₄
/x₁x₄	Х	Х	Х	Х
x₂x₃x₄				Х		Х
x₁x₂x₃					Х	Х

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

/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₃."

Тема 21. Пять классов переключательных функций: линейные переключательные функции; переключательные функции, сохраняющие нуль; переключательные функции, сохраняющие единицу; монотонные переключательные функции; самодвойственные переключательные функции. Теорема о функциональной полноте. Основная функционально полная система логических функций. Функционально полные системы логических функций. Примеры функционально полных базисов.

Конечное множество булевых функций называют системой булевых функций. Систему булевых функций называют полной, если любая булева функция может быть выражена в виде формулы над этой системой (другими словами, если она представима через функции данной системы).

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

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

где . В частном случае, полином Жегалкина имеет линейный вид:

Булева функция, представимая в виде линейного полинома Жегалкина, называется линейной.

Существует простой способ выражения любой булевой функции над базисом Жегалкина. Этот способ носит название метода неопределённых коэффициентов. Рассмотрим этот метод на примере:

Рассмотрим функцию . В общем виде полином Жегалкина для этой функции имеет вид:

Вычислим все коэффициенты начиная с , последовательно подставляя в полином известные значения функции f:

Таким образом, функция имеет вид:

и не является линейной.