Булевы функции

Добавление  к ней еще такой же таблицы  дает диаграмму для функции 4-х  переменных (табл. 4.4.3).

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

• каждой клетке диаграммы соответствует свой набор;
• соседние наборы расположены рядом в строке либо в столбце.

Соседними наборами называются наборы, отличающиеся одной  компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются (см. метод Квайна- Мак-Класки). Например, для функции, заданной табл. 9.22,

конституенты, соответствующие паре единиц в левой  части таблицы, склеиваются и  порождают элементарное произведение из 2-х букв:

х₁х₂/х₃ v x₁x₂x ₃ = x₁x₂

 
О паре единиц в правой части диаграммы можно сказать то же самое:

/х₁х₂/х₃ v /x₁/x₂/x ₃ = /x₁/x₃

 
Отметим, что получающееся элементарное произведение легко определить сразу  по диаграмме: это произведение переменных, принимающих одно и то же значение в обеих клетках. 
Еще одно важное замечание: столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашего примера это означает, что имеет место еще одно склеивание, в результате которого, следуя указанному правилу, получаем элементарное произведение x₂/x₃ Из рассмотренных ранее методов нам известно, что возможно дальнейшее склеивание получаемых элементарных произведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеивания на диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Число m оставшихся переменных в элементарном произведении определяется легко:

m = n - log₂M

 
где n - число переменных функции, М - число склеиваемых наборов. Метод широко используется на практике, благодаря простоте и удобству. После небольшой тренировки достигается элементарный навык определения минимальной ДНФ по диаграмме "с первого взгляда". Минимизация булевой функции заключается в нахождении минимального накрытия всех единиц диаграммы Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы. При этом всегда считается, что левый край диаграммы Bейча 4-х переменных примыкает к ее правому краю, а верхний oкрай диаграммы примыкает к нижнему ее краю. После получения минимального накрытия всех единиц диаграммы Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме.

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

"Минимизация  КНФ производится аналогично  рассмотреным методам минимизации  ДНФ булевых функций, поэтому остановимся лишь на основных положениях. 
Напомним, что конституентой нуля называется функция, принимающая значение 0 на одном наборе. Она выражается дизъюнкцией всех переменных функций. Например, набору 0110 соответствует конституента нуля x₁v/x₂v/x₃vx₄.

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

 

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

 
Задачей минимизации КНФ является определение минимальной КНФ. Эта  задача также решается в два этапа - поиск сокращенной КНФ (конъюнкция всех простых имплицент) и затем  нахождение минимальной КНФ. Второй этап минимизации выполняется с помощью таблицы Квайна точно так же, как при поиске минимальной ДНФ, так как возможны только два варианта: либо данная простая имплицента поглощает данную конституенту нуля, либо нет в соответствии с соотношением поглощения

(A v x)A = A

 
Что касается первого этапа - поиска всех простых имплицент, то практически  все методы минимизации ДНФ имеют  свои аналоги для КНФ. Расссмотрим  это подробнее. 
Соотношение склеивания по Квайну

(A v x)(A v /x) = (A v x)(A v /x)A.

 
Соотношение склеивания по Блейку

(A v x)(B v /x) = (A v x)(B v /x)(A v B)

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

(x₁ v /x₁)(x₁ v x₂) (/x₂ v /x₁)(x₂ v /x₂) = (x₁ v x₂)(/x₁ v /x₂)

По диаграмме  Вейча поиск минимальной КНФ  осуществляется так же просто, как  в случае ДНФ. Отличие состоит  лишь в том, что анализируются  нулевые наборы и переменные выписываются с инверсиями. Например, для функции, заданной диаграммой (табл. 4.5.1)

минимальной КНФ, является

(/x₁ v x₃)(x₂ v x₃)(/x₁ v /x₂ v /x₃)

Для сравнения  найдем минимальную ДНФ: /x₁x₂ v /x₂x₃ v x₃/x₄. В данном случае ДНФ оказалась проще, В общем случае о сравнительной сложности минимальных ДНФ и КНФ нельзя говорить заранее, но можно отметить следующее: количество букв минимальной ДНФ произвольной функции f и минимальной КНФ функции /f одинаково."

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

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

Минимизация систем булевых функций.

"На практике  очень часто приходится реализовывать  совокупности булевых функций.  Если произвести минимизацию  булевых функций, входящих в  систему, независимо друг от друга, то общая схема будет состоять из изолированных подсхем. Ее можно иногда упростить за счет объединения участков подсхем, реализующих одинаковые члены, входящие в несколько булевых функций системы. Задача минимизации систем булевых функций хорошо исследова на в классе функционально полных систем: "дизъюнкция", "конъюнк ция", "отрицание". Рассмотрим один из наиболее распространенных методов минимизации. Пусть задана система полностью определенных булевых функций, представленных в дизъюнктивной нормальной форме, например:

f₁(x₁,x₂,x₃) = x₁/x₃ v x₁/x₂ v /x₁x₃; 
f₂(x₁,x₂,x₃) = x₁/x₂ v /x₁x₃ v /x₁x₂; 
f₃(x₁,x₂,x₃) = x₁x₂ v /x₁/x₂/x₃,

Все различные  элементарные конъюнкции системы функций  объединим в множество А, которое  назовем полным множеством элементарных конъюнкций cистемы функций. В нашем случае А = {x₁/x₃; x₁/x₂; /x₁x₃; /x₁x₂; x₁x₂; /x₁/x₂/x₃}. Сумма рангов (число букв) элементарных конъюнкций множества А является удобным критерием оценки сложности заданной системы булевых функций.

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

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

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