Привести функцию к днф – 18 Нормальные формы формул, приведение к днф, кнф. - Санкт-Петербургское государственное бюджетное учреждение социального обслуживания населения

Содержание

Алгоритм построения днф

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

A→B= ךAvB A⇔B=(A^B)v(ךAvךB)

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

ך(AvB)= ךA^ךB ך(A^B)= ךAvךB

3) Избавиться от знаков двойного отрицания.

4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

Пример построения днф

Приведем к ДНФ формулу :F=((X→Y)↓ ך(Y→Z))

Выразим логические операции → и ↓ через :v ^ ך

F=(( ךXvY)↓ ך(ךYvZ))= ך ((ךXvY)v ך (ךYvZ))

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

F= ך ((ךXvY)v ך (ךYvZ))=( ך ךX^ ךY)^( ךYvZ)=(X^ ךY)^( ךYvZ)

Используя закон дистрибутивности, приводим формулу к ДНФ:

F=(X^ ךY^ ךY)v(X^ ךY^Z)

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

Примеры и контр примеры

Формулы в КНФ:

ך A^(BvC) (AvB)^( ך BvCv ך D)^(Dv ך E)A^B

Формулы не в КНФ:

ך (BvC) (A^B)vC A^(Bv(D^E))

Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:

ך B^ ך C (AvC)^(BvC) A^(BvD)^(BvE)

Построение КНФ

Алгоритм построения КНФ

A→B= ך AvB A↔B=(A^B)v(ך A^ ך B)

ך (AvB)= ך A^ ך B ך (A^B)= ך Av ך B

3) Избавиться от знаков двойного отрицания.

Пример построения КНФ

Приведем к КНФ формулу

F=(X→Y)^(( ך Y→Z) → ך X)

Преобразуем формулу F к формуле не содержащей → :

F=( ך XvY)^( ך (ך Y→Z)v ך X)=( ך XvY)^( ך (ך ך YvZ)v ך X)

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

F=( ך XvY)^(( ך Y^ ך Zv ך X)=( ך XvY)^(( ך Y^ ך Z)v ך X)

По закону дистрибутивности получим КНФ:

F=( ך XvY)^( ך Xv ך Y)^( ך Xv ך Z)

k-конъюнктивной нормальной формой называют конъюнктивную нормальную форму, в которой каждая дизъюнкция содержит ровно kлитералов.

Например, следующая формула записана в 2-КНФ:

(AvB)^( ך BvC)^(Bv ך C)

Переход от КНФ к СКНФ

Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в нее выражение : (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:

(XvY)^(Xv ך Yv ך Z)=(XvYv(Z^ ך Z))^(Xv ך Yv ך Z)=(XvYvZ)^(XvY vך Z)^(Xv ךYv ךZ)

Таким образом, из КНФ получена СКНФ.

Переход от КНФ к СКНФ

Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в нее выражение :Z^ ך Z=0 (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:

(XvY)^(Xv ךY ךZ)=(XvYv(Zv ךZ))^(Xv ךYv ךZ)=(XvYvZ)^(XvYv ךZ)^(Xv ךYv ךZ) Таким образом, из КНФ получена СКНФ.

25. Совершенные дизъюнктивные и конъюнктивные нормальные формы и алгоритмы приведения к ним. Примеры.

Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая конъюнктивная нормальная форма, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных дизъюнкций

в каждой дизъюнкции нет одинаковых пропозициональных переменных

каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

Например, следующая формула записана в 2-КНФ:

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных конъюнкций

в каждой конъюнкции нет одинаковых пропозициональных букв

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

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

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


0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

Совершенная ДНФэтой функции:

studfiles.net

Алгоритм перехода от табличного значения булевой функции к скнф.

1. В таблице выбрать все конституенты нуля, т.е. те наборы

> значений переменных

,…,

, на которых=0.

2. Каждому набору поставить в соответствие элементарную дизъюнкцию=.

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

(,…,)_СКНФ=.

Пример 1.Построить СДНФ и СКНФ булевой функции, заданной таблицей 1.5.1.

Таблица 1.5.1
№	x₁	x₂	x₃	f(x₁,x₂,x₃)	Конституенты 1	Конституенты 0
0	0	0	0	1	x₁x₂x₃
1	0	0	1	0		x₁x₂x₃
2	0	1	0	1	x₁x₂x₃
3	0	1	1	0		x₁x₂x₃
4	1	0	0	0		x₁x₂x₃
5	1	0	1	1	x₁x₂x₃
6	1	1	0	0		x₁x₂x₃
7	1	1	1	1	x₁x₂x₃

(

)_СДНФ=

(,,)_СКНФ=()()()()

3. Приведение к дизъюнктивной нормальной форме.

Процедура приведения к ДНФ:

1. Все отрицания “спустить” до переменных с помощью п.5.

2. Раскрыть скобки с помощью п.1, п.3а), п.3б).

3. Удалить лишние конъюнкции и повторения переменных в конъюнкциях с помощью п.4, п.8, п.9.

4. Удалить константы с помощью п.6.

Процедура приведения ДНФ к СКНФ состоит в расщеплении (обратном склеивании) конъюнкций, которые содержат не все переменные.

4. Приведение к конъюнктивной нормальной форме.

Конъюнктивной нормальной формой (КНФ)называется конъюнкция элементарных дизъюнкций. Пример КНФ: ()()(

Пусть ДНФ Fимеет видF=, где– элементарные конъюнкции.

Процедура приведения ДНФ к КНФ:

1. Применить к Fправило двойного отрицанияF=и привестик ДНФ, где– элементарные конъюнкции. Тогда

F===.

2. С помощью правил де Моргана освободиться от второго отрицания и преобразовать отрицания элементарных конъюнкций в элементарные дизъюнкции . Тогда

F==…



…

5.Двойственность.Функцияf*(,…,) называетсядвойственной к функцииf (,…,), еслиf*(,…,)=(,…,).

Отношение двойственности между функциями симметрично, т.е. если f* двойственна кf, тоfдвойственна кf*:

(,…,)=(,…,)=f*(,…,).

Функция, двойственная к самой себе, называется самодвойственной.

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

Принцип двойственности в булевой алгебре: если в формулеF, представляющей функциюf, все конъюнкции заменить на дизъюнкции, дизъюнкции на конъюнкции, 1 на 0, 0 на 1, то получим формулуF*, представляющую функциюf*, двойственнуюf.

Пример 1.Доказать справедливость обобщенного склеивания методом эквивалентных преобразований.

Выполним эквивалентные преобразования:

1.

Пример 2.Получить СДНФ функции, используя эквивалентные соотношения:f (x,y,z,u)=xyxzzu.

f(x,y,z,u)

Пример 3.Упростить булевы формулы:

а) (,,);

б) f (x,y,z).

а) (,,)

1;

б) f (x,y,z)

00z x0xyz xzz.

Пример 4.Представить булеву формулув базисе {&,} и {,}.

а);

б) .

Пример 5.Упростить СДНФ функции

f (x,y,z,u)

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

Рассмотрим метод Блейка-Порецкого “в действии”, для чего пронумеруем элементарные конъюнкции СДНФ:

studfiles.net

Построение минимальных ДНФ

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

Определение 6.5. Булеву функцию [cbm]g[/cbm] называют импликантой булевой функции [cbm]f[/cbm] , если для любых наборов значений переменных из [cbm]g=1[/cbm] следует [cbm]f=1[/cbm] .

Замечание 6.7. Напомним, что функции [cbm]f[/cbm] и [cbm]g[/cbm] можно рассматривать как функции от одного и того же числа переменных. Обозначая это число через [cbm]n[/cbm] , можно так уточнить понятие импликанты: функция [cbm]g\in \mathcal{P}_{2,n}[/cbm] есть импликанта функции [cbm]g\in \mathcal{P}_{2,n}[/cbm] если для каждого набора a [cbm]\widetilde{\alpha}\in\mathbb{B}^n[/cbm] из [cbm]g(\widetilde{\alpha})=1[/cbm] следует [cbm]f(\widetilde{\alpha})=1[/cbm] . Термин “импликанта” естественным образом ассоциируется и с логической связкой, называемой импликацией, и с одноименной булевой функцией. Действительно, если д импликанта [cbm]f[/cbm] , то из [cbm](g\to f)=1[/cbm] и [cbm]g=1[/cbm] следует, что [cbm]f=1[/cbm] , т.е. истинно высказывание

[cbm](\forall\widetilde{\alpha}\in\mathbb{B}^n)\bigl((g(\widetilde{\alpha})=1)\Rightarrow (f(\widetilde{\alpha})=1)\bigr).[/cbm]

Если функция [cbm]f[/cbm] представлена СДНФ, то любая ее элементарная конъюнкция (констпигпуентпа единицы функции [cbm]f[/cbm] ) будет ее импликантой. Полезно заметить также, что если [cbm]g_1[/cbm] и [cbm]g_2[/cbm] — импликанты [cbm]f[/cbm] , то дизъюнкция [cbm]g_1\lor g_2[/cbm] также является импликантой [cbm]f[/cbm] . Действительно, если [cbm]g_1\lor g_2=1[/cbm] , то [cbm]g_1=1[/cbm] или [cbm]g_2=1[/cbm] . Но тогда, поскольку каждая из этих функций есть импликанта [cbm]f[/cbm] , и [cbm]g_1\lor g_2[/cbm] есть импликанта [cbm]f[/cbm] .

Из определения 6.5 и понятия равных булевых функций (см. определение 6.2) следует, что булевы функции [cbm]f[/cbm] и [cbm]g[/cbm] равны, если и только если каждая из них служит импликантой другой: [cbm]f=1\Leftrightarrow g=1[/cbm] .

Определение 6.6. ДНФ называют минимальной, если она содержит наименьшее число литералов среди всех ДНФ, эквивалентных ей.

Обратим внимание на то, что под числом литералов в ДНФ понимают число всех подформул этой ДНФ, которые являются литералами. Так, СДНФ (6.9) содержит 12 литералов (по три литерала в каждой из четырех элементарных конъюнкции).

Пример 6.10. ДНФ [cbm]x_1x_2\lor \overline{x}_1x_2[/cbm] не является минимальной, так как ее можно преобразовать к эквивалентной ДНФ, не содержащей ни одного из литералов [cbm]\widetilde{x}_1:[/cbm]

[cbm]x_1x_2\lor \overline{x}_1x_2=(x_1\lor\widetilde{x}_1)x_2=x_2\,.[/cbm]

Вместо четырех литералов в исходной ДНФ получаем ДНФ, состоящую из одного литерала.
Определение 6.7. Длиной ДНФ называют число входящих в нее элементарных конъюнкций.
ДНФ называют кратчайшей, если она имеет наименьшую длину среди всех эквивалентных ей ДНФ.

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

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

Алгоритм Квайна–Мак-Клоски

Опишем последовательно этапы, составляющие алгоритм Квайна–Мак-Клоски.

1. Склейка. Пусть [cbm]K_1[/cbm] и [cbm]K_2[/cbm] — две элементарные конъюнкции, входящие в исходную СДНФ Ф, которая представляет функцию [cbm]f[/cbm] , причем для некоторого переменного [cbm]x[/cbm] и некоторой элементарной конъюнкции [cbm]K[/cbm] выполняются равенства [cbm]K_1=xK[/cbm] и [cbm]K_2=\overline{x}K[/cbm] . Тогда имеем, согласно тождествам булевой алгебры,

[cbm]K_1\lor K_2=xK\lor \overline{x}=(x\lor \overline{x})K=K\,.[/cbm]

Мы получаем элементарную конъюнкцию [cbm]K[/cbm] , которая содержит на один литерал меньше, чем [cbm]K_1[/cbm] и [cbm]K_2[/cbm] , и является, как и обе конъюнкции [cbm]K_1[/cbm] и [cbm]K_2[/cbm] , импликантой [cbm]f[/cbm] . Образно говоря, мы “склеили” две импликанты в одну, в которой число литералов на единицу меньше.

Операцию получения [cbm]K[/cbm] по [cbm]K_1[/cbm] и [cbm]K_2[/cbm] , описанную выше, можно провести и для любых двух элементарных конъюнкций подобного вида, составляющих любую ДНФ, эквивалентную исходной функции. Такую операцию называют простой склейкой импликант [cbm]K_1[/cbm] и [cbm]K_2[/cbm] по переменному [cbm]x[/cbm] .

Установим геометрический смысл простой склейки* (с точки зрения структуры, или “геометрии”, булева куба).

Из доказательства теоремы о представлении булевой функции в виде ДНФ (см. теорему 6.2) мы знаем, что существует взаимно однозначное соответствие между множеством элементарных конъюнкций СДНФ, представляющей функцию [cbm]f[/cbm] , и множеством [cbm]C_f^1[/cbm] ее конституент единицы. Это соответствие, напомним, таково, что каждому набору [cbm]\widetilde{\alpha}=(\alpha_1,\ldots,\alpha)\in C_f^1[/cbm] отвечает элементарная конъюнкция [cbm]K_{\widetilde{\alpha}}=x_{1}^{\alpha_1}\cdot\ldots x_{n}^{\alpha_n}[/cbm] , принимающая значение 1 только на наборе [cbm]\widetilde{\alpha}[/cbm] . Тогда простая склейка может быть применена только к таким двум элементарным конъюнкциям [cbm]K_{\widetilde{\alpha}}[/cbm] и [cbm]K_{\widetilde{\beta}}[/cbm] , соответствующим наборам [cbm]\widetilde{\alpha}, \widetilde{\beta}\in C_f^1[/cbm] , что для некоторого [cbm]i~(1\leqslant i\leqslant n)[/cbm]

[cbm]\begin{aligned}\widetilde{\alpha}&= (\alpha_1,\ldots, \alpha_{i-1},\alpha_{i}, \alpha_{i+1}, \ldots, \alpha_{n}),\\[2pt] \widetilde{\beta}&= (\alpha_1,\ldots, \alpha_{i-1}, \overline{\alpha}_{i}, \alpha_{i+1}, \ldots, \alpha_{n}).\end{aligned}[/cbm]

Это значит, что наборы [cbm]\widetilde{\alpha}, \widetilde{\beta}[/cbm] таковы, что один из них доминирует над другим (они различаются значением только одной компоненты), т.е. они образуют ребро булева куба [cbm]\mathbb{B}^n[/cbm] .

Следовательно, простой склейке, применяемой к элементарным конъюнкциям исходной СДНФ, представляющей функцию [cbm]f[/cbm] , подлежат те и только те элементарные конъюнкции, которые соответствуют элементам какого-либо ребра булева куба, на котором функция [cbm]f[/cbm] принимает единичное значение. Образно говоря, две соседние вершины куба, на которых функция равна 1, псклеиваются” в ребро, их “соединяющее”.

С алгебраической же точки зрения мы из двух элементарных конъюнкций [cbm]K_{\widetilde{\alpha}}[/cbm] и [cbm]K_{\widetilde{\beta}}[/cbm] получаем новую элементарную конъюнкцию [cbm]x_{1}^{\alpha_1}\ldots x_{i-1}^{\alpha_{i-1}} x_{i+1}^{\alpha_{i+1}}\ldots x_{n}^{\alpha_n}[/cbm] , лишенную литерала [cbm]x_{i}^{\alpha_i}[/cbm] .

Итак, применяя простую склейку к исходной СДНФ [cbm]\Phi[/cbm] , получаем новую ДНФ [cbm]\Phi_1[/cbm] ; к ней также применяем простую склейку — получаем ДНФ [cbm]\Phi_2[/cbm] ; продолжаем выполнять эту операцию до тех пор, пока не окажется, что для некоторого [cbm]k[/cbm] в ДНФ [cbm]\Phi_k[/cbm] уже нельзя склеить никакие две элементарные конъюнкции. Такое [cbm]k[/cbm] всегда найдется, так как СДНФ [cbm]\Phi[/cbm] состоит из конечного числа элементарных конъюнкций, а они, в свою очередь, состоят из конечного числа литералов. Полученную в результате ДНФ [cbm]\Phi_k[/cbm] называют сокращенной ДНФ функции [cbm]f[/cbm] , а ее элементарные конъюнкции — простыми импликантами булевой функции [cbm]f[/cbm] .

Замечание 6.8. Понятие простой импликанты определено через процедуру многократного повторения простой склейки. Иногда простую импликанту булевой функции [cbm]f[/cbm] определяют независимо от понятия о склейке как такую элементарную конъюнкцию в составе некоторой ДНФ, представляющей функцию [cbm]f[/cbm] , что удаление из нее любого литерала лишает ее свойства “быть импликантой”. Например, конъюнкция [cbm]x_1x_2 \overline{x}_3[/cbm] не является простой импликантой мажоритарной функции, так как из ее СДНФ (6.9) можно удалить литерал [cbm]\overline{x}_3[/cbm] и получить конъюнкцию [cbm]x_1x_2[/cbm] , которая будет снова импликантой функции, но уже, как будет показано далее, простой.

Можно доказать, что эти два определения простой импликанты равносильны.

Геометрия описанного выше многократного повторения простой склейки, как можно показать, состоит в дальнейшем “склеивании” каждой пары соседних ребер {граней размерности 1), на которых значение функции равно 1, в грани размерности 2, соседних граней размерности 2 в грани размерности 3 и т.д. Разбираемый ниже пример поясняет эту идею.

Пример 6.11. Зададим функцию [cbm]f[/cbm] от трех переменных следующей СДНФ: [cbm]f=\overline{x}_1\overline{x}_2\overline{x}_3\lor \overline{x}_1\overline{x}_2 x_3\lor x_1\overline{x}_2\overline{x}_3\lor x_1\overline{x}_2x_3\,.[/cbm]

(6.11)

Подвергнем простой склейке первую и третью, а также вторую и четвертую элементарные конъюнкции в (6.11): [cbm]f=\overline{x}_2\overline{x}_3\lor\overline{x}_2x_3\,.[/cbm]

(6.12)

С геометрической точки зрения склейка первой и третьей конъюнкций в формуле (6.11) означает, что функция [cbm]f[/cbm] принимает единичное значение на ребре [000,100] (рис. 6.6), а склейка второй и четвертой конъюнкций точно так же определяет ребро [001,101], Эти ребра являются соседними, и, кроме того, оказывается, что функция / принимает единичное значение и на другой паре соседних ребер: [000, 001] и [100,101]. Здесь сказывается существенное отличие “геометрии” булева куба от классической: в булевом кубе ребро — это пара вершин, между которыми нет никаких “точек”. Тогда любая пара соседних ребер образует грань размерности 2, любая пара соседних граней размерности 2 образует грань размерности 3 и т.д. Таким образом, если функция принимает единичное значение на двух соседних ребрах булева куба, то она равна 1 в любой точке образуемой ими грани размерности 2, если она равна 1 на двух параллельных соседних гранях размерности 2, то она равна 1 на соответствующей грани размерности 3 и т.д.

Применяя простую склейку к (6.12) (по переменному [cbm]x_3[/cbm] ), получаем [cbm]f(x_1,x_2,x_3)=\overline{x}_2[/cbm] . Побочным результатом склейки явилось и удаление фиктивных переменных функции [cbm]x_1[/cbm] и [cbm]x_3[/cbm] .

Пример 6.12. Рассмотрим СДНФ мажоритарной функции (6.9).
Имеем следующие склейки:

[cbm]\overline{x}_1x_2x_3\lor x_1x_2x_3=x_2x_3,\qquad x_1\overline{x}_2x_3\lor x_1x_2x_3=x_1x_3,\qquad x_1x_2\overline{x}_3\lor x_1x_2x_3=x_1x_2.[/cbm]

В данном случае сразу получаем сокращенную ДНФ: [cbm]\Phi_1=x_1x_2\lor x_1x_3\lor x_2x_3[/cbm] .

Карты Карно

Для булевых функций от трех и четырех переменных процедура склейки наглядно и просто выполняется на так называемых картах Карио. Форма карт Карно, представляющих собой прямоугольные таблицы, для функции от трех переменных показана на рис. 6.7, а для функции от четырех переменных — на рис. 6.8. На рис. 6.7 строки отмечены наборами значений переменного [cbm]x_1[/cbm] , а столбцы — [cbm]x_2,x_3[/cbm] , а на рис. 6.8 строки — наборами значений переменных [cbm]x_1,x_2[/cbm] , а столбцы — [cbm]x_3,x_4[/cbm] .

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

С геометрической точки зрения карта Карно есть способ изображения булева куба (размерностей 3 и 4). Любая пара соседних клеток (с учетом “закрученности” карты) определяет некоторое ребро булева куба, а любой прямоугольник, состоящий из [cbm]2^k[/cbm] клеток (или, как говорят, прямоугольник с площадью [cbm]2^k[/cbm] ) для некоторого [cbm]k[/cbm] , определяет грань размерности [cbm]k[/cbm] .

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

Пусть булева функция [cbm]f[/cbm] задана таблицей, представленной в форме карты Карно. Описанный выше итерационный процесс склейки, в результате которого получается сокращенная ДНФ, представляющая функцию [cbm]f[/cbm] , проводится на карте Карно так: любые две соседние клетки, содержащие единицы, обводятся, и “поглотивший” их прямоугольник (он и есть обозначение результата склейки на карте) представляется словом, содержащим “0”, “1” и “×” (“крестик”), причем “крестик” занимает позицию того переменного, по которому произведена склейка (рис. 6.9).

С геометрической точки зрения такой прямоугольник площади 2 соответствует ребру булева куба, в каждой вершине которого функция принимает значение 1. Запись прямоугольника в виде слова можно понимать как обозначение соответствующего ребра. Так, на карте, показанной на рис. 6.9, прямоугольник 11× обозначает ребро [110,111], прямоугольники же 1×1 и ×11 — ребра [101,111] и [011,111] соответственно.

По таким обозначениям легко получить и ту импликанту, которая является результатом простой склейки: для этого достаточно записать литерал [cbm]x_i[/cbm] (соответственно [cbm]\overline{x}_i[/cbm] ), если в i-й позиции стоит 1 (соответственно 0), и пропустить литерал ж», если в i-й позиции стоит “крестик”. Так, по слову 1×0 получим импликанту [cbm]x_1\overline{x}_3[/cbm] .

Наличие на карте Карно двух прямоугольников площади 2, находящихся в соседних столбцах или строках, показывает, что функция принимает значение 1 на некоторой паре соседних ребер, т.е. на некоторой грани размерности 2. Тогда они могут быть объединены в один большой прямоугольник площади 4 (рис. 6.10).

Этот прямоугольник можно записать в виде слова хОх, показывая тем самым, что соответствующая грань (размерности 2) образована любой из двух пар соседних ребер: (×00, ×01) (два вертикальных прямоугольника площади 2) или (00×, 10×) (два горизонтальных прямоугольника площади 2).

Точно так же можно объединять в один прямоугольник площади 8 два соседних прямоугольника площади 4 (рис. 6.11).

Если такие большие прямоугольники находить сразу, то “поглощаемые” ими меньшие прямоугольники уже не рассматриваются. Тем самым, находя на карте Карно прямоугольники максимальной площади и не содержащиеся друг в друге, мы находим грани максимальных размерностей и максимальные по включению, такие, на которых заданная функция принимает единичное значение. Поскольку грань размерности [cbm]k[/cbm] имеет [cbm]2^k[/cbm] вершин, то выделяемые описанным способом прямоугольники могут состоять только из [cbm]2^k[/cbm] клеток (для некоторого [cbm]k[/cbm] , не превышающего числа переменных). Так, на карте, приведенной на рис. 6.12, получим два прямоугольника площади 4: ×0×0 и 0×0×, соответствующие граням размерности 2, и один прямоугольник 01×1, отвечающий ребру, которое не содержится ни в одной из указанных выше граней. Подчеркнем еще раз, что соседство клеток, прямоугольников и само выделение прямоугольников на карте Карно производится с учетом ее “закрученности”. В этой связи интересен ” прямоугольник” на карте, приведенной на рис. 6.12, обозначенный ×0×0. Он образован двумя парами противоположных угловых клеток.

Таким образом, если на карте Карно сразу выделять все максимальные (в указанном выше смысле) прямоугольники площади [cbm]2^k[/cbm] (для некоторого [cbm]k\geqslant0[/cbm] и не превышающего числа переменных), то тем самым мы “геометрически” реализуем описанный ранее алгебраический итерационный процесс склейки и в результате получаем все простые импликанты исходной функции (составляющие сокращенную ДНФ). Эти импликанты восстанавливаются по записям прямоугольников точно так же, как описано выше для простой склейки. Так, для карты, приведенной на рис. 6.12, получим сокращенную ДНФ в виде

[cbm]\overline{x}_2 \overline{x}_4\lor \overline{x}_1 \overline{x}_3\lor \overline{x}_1x_2x_4\,.[/cbm]

2. Определение ядра. Говорят, что элементарная конъюнкция [cbm]K[/cbm] покрывает элементарную конъюнкцию [cbm]L[/cbm] (и пишут [cbm]K\succ L[/cbm] ), если любой литерал, входящий в [cbm]K[/cbm] , входит в [cbm]L[/cbm] . Так,

[cbm]x_1x_2\succ x_1x_2x_3,\qquad x_1x_3\succ x_1 \overline{x}_2x_3[/cbm] , но [cbm]x_1x_3\nsucc x_1x_2\overline{x}_3[/cbm] .

Поскольку вторая конъюнкция содержит литерал [cbm]\overline{x}_3[/cbm] , отсутствующий в первой конъюнкции. Легко понять, что если [cbm]K\succ L[/cbm] , то [cbm]K\lor L=K[/cbm] (согласно тождествам поглощения).

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

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

Множество всех ядровых импликант (склеек) сокращенной ДНФ называют ядром.

Пример 6.13. а. У мажоритарной функции все импликанты являются ядровыми. Напротив, у функции, изображенной на карте Карно на рис. 6.13, ядро пусто, т.е. ядровых импликант нет вовсе.

б. На карте Карно на рис. 6.14 в ядро попадают склейки [cbm]0\times\,\times1,~ 0\times1\times,~ 1\times00[/cbm] .

Если все простые импликанты оказались в ядре, то сокращенная ДНФ и есть единственная минимальная и кратчайшая ДНФ для данной функции. Именно так обстоит дело с мажоритарной функцией (см. пример 6.12). В противном случае смотрят, не эквивалентна ли ДНФ, построенная как дизъюнкция всех ядровых импликант, исходной СДНФ. Это будет иметь место тогда и только тогда, когда ядровые импликанты покрывают в совокупности все элементарные конъюнкции исходной СДНФ. На карте Карно тогда каждая клетка, содержащая единицу, должна быть закрыта прямоугольником, отвечающим некоторой ядровой импликанте. Если это так, то ДНФ, построенная по ядру, как описано выше, есть минимальная и кратчайшая (склейки ядра закрыли все единицы карты Карно). При этом импликанты, не попавшие в ядро, все оказываются “избыточными”, т.е. их удаление из сокращенной ДНФ не приводит к нарушению эквивалентности этой последней с исходной СДНФ.

В остальных случаях переходят к отысканию так называемых тупиковых ДНФ.

3. Перечисление тупиковых ДНФ. Простую импликанту называют избыточной (относительно некоторой ДНФ, содержащей только простые импликанты и эквивалентной исходной СДНФ), если ее можно удалить из этой ДНФ без потери эквивалентности ее исходной СДНФ. Так, сокращенная ДНФ (см. рис. 6.14) содержит избыточные импликанты: импликанта, соответствующая прямоугольнику [cbm]10\times0[/cbm] , или импликанта, соответствующая прямоугольнику [cbm]\times010[/cbm] , может быть удалена (но не обе сразу!). Это значит, что каждая из этих импликант является избыточной относительно сокращенной ДНФ, но удаление одной из них приводит к новой ДНФ, относительно которой вторая из упомянутых импликант уже не будет избыточной. В том случае, когда каждую элементарную конъюнкцию исходной СДНФ покрывает некоторая ядровая импликанта, импликанты, не вошедшие в ядро, можно удалить одновременно.

Тогда можно представить процесс пошагового удаления избыточных импликант, начиная с сокращенной ДНФ, в результате которого получится некоторая ДНФ, уже не содержащая ни одной избыточной склейки.

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

Заметим, что в силу конечности множества всех импликант тупиковая ДНФ обязательно существует, т.е. в упомянутом выше процессе мы рано или поздно доберемся до такого момента, когда удаление хотя бы одной склейки приведет к тому, что “откроется” какая-то единичная клетка на карте Карно и тем самым будет потеряна эквивалентность полученной таким образом ДНФ исходной СДНФ.

Для СДНФ, карта Карно которой приведена на рис. 6.14, имеются две тупиковые ДНФ (первые три конъюнкции соответствуют ядру):

[cbm]\begin{gathered}\overline{x}_1x_4\lor \overline{x}_1x_3\lor x_1\overline{x}_3\cdot \overline{x}_4\lor \overline{x}_2 x_3 \overline{x}_4,\\[2pt] \overline{x}_1x_4\lor \overline{x}_1x_3\lor x_1\overline{x}_3\cdot \overline{x}_4\lor x_1\overline{x}_2\cdot \overline{x}_4. \end{gathered}[/cbm]

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

Присвоим каждой простой импликанте сокращенной ДНФ некоторое имя: т.е. обозначим их, например, как [cbm]K_1,K_2,\ldots,K_m[/cbm] . Для любой единицы карты Карно, не покрываемой ядром, перечислим все простые импликанты, которые ее покрывают, записав их в виде элементарной дизъюнкции, в которой переменными считаются введенные выше имена простых импликант. Переменное, именующее данную простую импликанту, принимает, по определению, значение 1, если данная простая импликанта выбирается для покрытия рассматриваемой единицы
карты Карно.

Записав все элементарные дизъюнкции, составим из них КНФ. Рассмотрим карту Карно на рис. 6.13. Обозначив

[cbm]\begin{array}{lll}K_1=x_1\overline{x}_2(10\times),&\qquad K_2= \overline{x}_2 x_3(\times01), &\qquad K_3= \overline{x}_1x_3(0\times1),\\[2pt] K_4= \overline{x}_1 x_2(01\times), &\qquad K_5=x_2\overline{x}_3(\times10),&\qquad K_6= x_1\overline{x}_3(1\times0), \end{array}[/cbm]

получим [cbm](K_1\lor K_6)\land (K_1\lor K_2)\land (K_2\lor K_3)\land (K_3\lor K_4)\land (K_4\lor K_5)\land (K_5\lor K_6).[/cbm]

(6.13)

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

Для нашего примера поступим так: вычислим конъюнкцию первой и второй скобки в выражении (6.13), а также третьей и четвертой, пятой и шестой скобок, после чего получим

[cbm]\begin{aligned}(K_1\lor K_1 K_2\lor K_6 K_1\lor K_6 K_2) &\land (K_2 K_3\lor K_2 K_4\lor K_3\lor K_3 K_4)\land\\[2pt] &\land (K_4 K_5\lor K_4 K_6\lor K_5\lor K_5 K_6). \end{aligned}[/cbm]

(6.14)

Используя тождества поглощения, в первой скобке в формуле (6.14) мы можем удалить все члены, содержащие [cbm]K_1[/cbm] , во второй скобке — все члены, содержащие [cbm]K_3[/cbm] , в третьей скобке — все члены, содержащие [cbm]K_5[/cbm] . Проделав это, раскрыв все три скобки и применив еще раз поглощение, окончательно получим

[cbm]K_1 K_3 K_5\lor K_1 K_3 K_4 K_6\lor K_1 K_2 K_4 K_5\lor K_2 K_3 K_5 K_6\lor K_2 K_4 K_6.[/cbm]

(6.15)

Элементарные конъюнкции в (6.15) определяют тупиковые ДНФ. Более того, так как в данном случае отсутствуют ядровые импликанты, найденные конъюнкции исчерпывают тупиковые ДНФ. Первая тупиковая ДНФ состоит из конъюнкций [cbm]K_1,\,K_3[/cbm] и [cbm]K_5[/cbm] , т.е. имеет вид [cbm]x_1 \overline{x}_2\lor \overline{x}_1x_3\lor x_2 \overline{x}_3[/cbm] . Точно так же определяются остальные тупиковые ДНФ.

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

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

4. Отыскание среди тупиковых ДНФ кратчайших и минимальных. Среди найденных тупиковых ДНФ находят кратчайшие и минимальные. Можно легко показать, что минимальная ДНФ всегда является кратчайшей, но обратное неверно. Так, [cbm]x_1x_2\lor\overline{x}_2=x_1\lor \overline{x}_2[/cbm] и первая ДНФ кратчайшая, но не минимальная. Действительно, легко сообразить, что вторая из записанных ДНФ минимальна. Следовательно, представляемую ею функцию нельзя представить ДНФ, содержащей менее двух элементарных конъюнкций. Но в первой ДНФ три литерала, а во второй — два. Из пяти тупиковых ДНФ, соответствующих функции Патрика (6.15), кратчайшими являются две. Каждая из них минимальна, так как обе они имеют одинаковое число литералов.

Пример 6.14. Рассмотрим карту Карно на рис. 6.15. В результате проведения склейки получим следующую сокращенную ДНФ*:

[cbm]\overline{x}_1\overline{x}_3\lor \overline{x}_1\overline{x}_2\lor \overline{x}_2 \overline{x}_4\lor \overline{x}_2\overline{x}_3\lor \overline{x}_3x_4\lor x_1x_2x_4\lor x_1x_2x_3\lor x_1x_3\overline{x}_4\,.[/cbm]

Ядро составляют склейки (простые импликанты) [cbm]\overline{x}_1\overline{x}_3[/cbm] и [cbm]\overline{x}_1\overline{x}_3[/cbm] .

Шесть клеток, содержащих единицу, на карте Карно остаются непокрытыми ядровыми склейками. Для неядровых склеек (обозначенных [cbm]K_1,\ldots,K_6[/cbm] ) составляем функцию Патрика в виде

[cbm](K_3\lor K_4) (K_4\lor K_5) (K_5\lor K_6) (K_1\lor K_2) (K_2\lor K_3) (K_1\lor K_6).[/cbm]

Преобразуя ее аналогично функции (6.13), получаем

[cbm]K_1K_3K_5\lor K_2K_4K_6\lor K_2K_3K_5K_6\lor K_1K_2K_4K_5\lor K_1K_3K_4K_6\,.[/cbm]

Имеем, следовательно, пять тупиковых ДНФ. Запишем их, для наглядности, так:

[cbm]\underbrace{\overline{x}_1\overline{x}_3\lor \overline{x}_1 \overline{x}_2}_{\text{yadro}}\lor \begin{cases}\overline{x}_2\overline{x}_4\lor \overline{x}_3x_4\lor x_1x_2x_3,\\ \overline{x}_2\overline{x}_3\lor x_1x_2x_4\lor x_1x_3\overline{x}_4,\\ \overline{x}_2 \overline{x}_3\lor \overline{x}_3x_4\lor x_1x_2x_3\lor x_1x_3\overline{x}_4,\\ \overline{x}_2 \overline{x}_4\lor \overline{x}_2\overline{x}_3\lor x_1x_2x_4\lor x_1x_2x_3,\\ \overline{x}_2 \overline{x}_4\lor \overline{x}_3x_4\lor x_1x_2x_4\lor x_1x_3\overline{x}_4. \end{cases}[/cbm]

Из этих пяти тупиковых ДНФ кратчайшими являются первая и вторая. Из них, в свою очередь, минимальной является первая, так как она содержит на один литерал меньше. В итоге получаем минимальную ДНФ в виде

[cbm]\overline{x}_1\overline{x}_3\lor \overline{x}_1\overline{x}_2\lor \overline{x}_2 \overline{x}_4\lor \overline{x}_3x_4\lor x_1x_2x_3\,.[/cbm]

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

В данном случае минимальная ДНФ оказалась единственной, хотя, как это мы видели в ранее разобранных примерах, в общем случае могут существовать несколько минимальных ДНФ.

Метод Блейка

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

[cbm]\begin{cases}xK_1\lor \overline{x}K_2= xK_1\lor \overline{x}K_2\lor K_1K_2,\\ K_1\lor K_1K_2=K_1.\end{cases}[/cbm]

Первое из тождеств (6.16) называют тождеством (или правилом) обобщенного склеивания, второе — тождеством (или правилом) поглощения.

“Технология” использования метода Блейка такова: применяют тождество обобщенного склеивания до тех пор, пока не перестанут появляться новые элементарные конъюнкции (вида К1К2). После этого применяют тождество поглощения.

Таблицы Квайна

Как только сокращенная ДНФ тем или иным способом найдена, приступают к нахождению ядра. Ядро можно определить (без использования карты Карно) с помощью так называемой таблицы Квайна. Столбцы этой таблицы соответствуют элементарным конъюнкциям исходной СДНФ, а строки — простым импликантам сокращенной ДНФ. На пересечении строки и столбца проставляется знак “+” (плюс), если простая импликанта данной строки покрывает элементарную конъюнкцию данного столбца. Ядро вычисляется так: отмечаем столбцы с единственным знаком “+”, тогда простые импликанты тех и только тех строк, в которые попал этот знак, образуют ядро. Для примера 6.13.6 (см. рис. 6.14) получим таблицу Квайна, изображенную на рис. 6.16. (В целях экономии места элементарные конъюнкции в таблице заменены цифровыми обозначениями соответствующих вершин и граней булева куба — точно так же как при обозначении прямоугольников на картах Карно. Ядровые импликанты выделены жирным шрифтом.)

По таблице Квайна можно составить и функцию Патрика для перечисления тупиковых ДНФ. Для этого нужно отметить все столбцы таблицы, в которых на пересечении со строками, соответствующими ядровым импликантам, не стоит знак “+”. Для разбираемого примера таковым является только последний столбец. Чтобы покрыть соответствующую элементарную конъюнкцию СДНФ, можно выбрать одну из двух простых импликант: [cbm]x_1 \overline{x}_2 \overline{x}_4[/cbm] или [cbm]\overline{x}_2x_3\overline{x}_4[/cbm] .

Построение минимальных ДНФ частичных булевых функций

В заключение рассмотрим очень кратко применение карт Карно к построению минимальных ДНФ частичных булевых функций, т.е. частичных отображений из множества [cbm]\{0;1\}^n[/cbm] в множество [cbm]\{0;1\}[/cbm] .

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

Склейка для частичной функции (заданной картой Карно) проводится таким образом, что выделяются прямоугольники максимальной площади (содержащие [cbm]2^k[/cbm] клеток, для некоторого [cbm]k[/cbm] ), каждая клетка которых содержит либо единицу, либо прочерк, причем существует по крайней мере одна единичная клетка.

Пример 6.15. Пусть частичная функция [cbm]f(x_1,x_2,x_3)[/cbm] задана картой Карно, приведенной на рис. 6.17. Прямоугольник максимальной площади (равной 4), состоящий из единицы и прочерков, записывается как [cbm]0\times\,\times[/cbm] . Следовательно, минимальная ДНФ для заданной функции будет [cbm]\overline{x}_1[/cbm] .

По поводу рассмотренного примера возникает такой вопрос: почему не принят во внимание другой прямоугольник (площади 2), содержащий клетку с единицей и клетку с прочерком: [cbm]\times00[/cbm] ? Связано это вот с чем. Перед тем как выделять упомянутые выше прямоугольники, мы на самом деле доопределяем исходную частичную функцию (получая обычную булеву функцию) так, чтобы в максимальном числе клеток, в которых стоят прочерки (но не нули!), появились единицы. Точнее говоря, среди прямоугольников (с прочерками), содержащих данную единицу, выбирают для замены прочерков единицами такой, который имеет максимальную площадь. Прочерки же в остальных прямоугольниках заменяют нулями.

В примере 6.15 мы доопределяем исходную функцию так, что получается функция [cbm]f_1[/cbm] , задаваемая картой Карно, приведенной на рис. 6.18. Эта функция имеет минимальную ДНФ [cbm]\overline{x}_1[/cbm] . Следовательно, и частичная исходная функция может быть представлена такой ДНФ, поскольку на всех наборах, на которых она определена, она принимает такое же значение, как и функция [cbm]f_1[/cbm] .

Конечно, мы могли бы доопределить функцию [cbm]f[/cbm] по-другому, так, чтобы получилась функция [cbm]f_2[/cbm] , заданная картой Карно, приведенной на рис. 6.19. Ясно, что [cbm]f_2= \overline{x}_2\overline{x}_3[/cbm] поэтому и частичная функция [cbm]f[/cbm] может быть определена такой ДНФ. Но эта ДНФ не минимальна для данной частичной (именно частичной!) функции, поскольку первый способ доопределения дал ДНФ, содержащую лишь один литерал.

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

Пример 6.16. Для карты на рис. 6.20 следует взять обе склейки на четыре позиции: [cbm]00\times\,\times[/cbm] и [cbm]\times\,\times00[/cbm] , получив для заданной этой картой частичной функции минимальную ДНФ в виде [cbm]\overline{x}_1 \overline{x}_2\lor \overline{x}_3 \overline{x}_4[/cbm] .

Заметим, что без использования склеек с прочерками мы вообще не могли бы минимизировать данную функцию. Нужно также отметить, что не всегда использование “частичности” функции позволяет получить минимальную ДНФ для нее. Так, на представленной на рис. 6.20 карте в случае, если мы переместим нижнюю единицу на строку выше, обычная склейка на две позиции дает лучший результат: [cbm]\overline{x}_1\overline{x}_3\overline{x}_4[/cbm] , а записанная выше ДНФ уже не будет минимальной (и даже кратчайшей).

Проверенный сервис ремонта айфонов http://pedant.ru/remont-apple/iphone-6s.В вашем браузере отключен Javascript.
Чтобы произвести расчеты, необходимо разрешить элементы ActiveX!

Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.
Формулы в ДНФ:
Формулы не в ДНФ:
Алгоритм построения ДНФ
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Пример построения ДНФ
Приведем к ДНФ формулу : Выразим логические операции → и ↓ через :
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

Совершенная дизъюнктивная нормальная форма
Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:
в ней нет одинаковых элементарных конъюнкций
в каждой конъюнкции нет одинаковых пропозициональных букв
каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.
Для любой функции алгебры логики существует своя СДНФ, причём единственная.
Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности:
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
В ячейках результата отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.
Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:
Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так:
Переменные второго члена:
в этом случае будет представлен без инверсии: Таким образом анализируются все ячейки . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций). Совершенная ДНФ этой функции:
Переход от ДНФ к СДНФ
Если в какой-то простой конъюнкции недостаёт переменной, например, Z, вставляем в неё выражение
,
после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем, так как по закону идемпотентности). Например:
Таким образом, из ДНФ получили СДНФ.
По материалам Википедии:

forinformatics.blogspot.com
СДНФ. Теорема о представлении в виде СДНФ. Построение СДНФ по таблице / Алгебра логики [Ф.Г. Кораблёв] / 3dstroyproekt.ru
ДНФ
Простой конъюнкцией или конъюнктом называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
Простая конъюнкция
полная, если в неё каждая переменная { или её отрицание } входит ровно 1 раз;
монотонная, если она не содержит отрицаний переменных.
ДНФ { Дизъюнктивная Нормальная Форма } — нормальная форма, в которой булева функция имеет вид дизъюнкции нескольких простых конъюнктов.
Пример ДНФ: $f(x,y,z) = (x \land y) \lor (y \land \neg { z } )$
СДНФ
СДНФ { Совершенная Дизъюнктивная Нормальная Форма } — это такая ДНФ, которая удовлетворяет условиям:
в ней нет одинаковых простых конъюнкций
каждая простая конъюнкция полная
Пример СДНФ: $f(x,y,z) = (x \land \neg { y } \land z) \lor (x \land y \land \neg { z } )$
Теорема: Для любой булевой функции $f(\vec { x } )$, не равной тождественному нулю (), существует СДНФ, ее задающая.
Доказательство:
Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона.
$f(\vec { x } ) = \neg x_i \wedge f(x_1, \dots ,x_ { i-1 } ,0,x_ { i+1 } , \dots ,x_n) \vee x_i \wedge f(x_1, \dots ,x_ { i-1 } ,1,x_ { i+1 } , \dots ,x_n)$
Данное соотношение легко проверить подстановкой всевозможных значений $x_i$ { $0$ и $1$ } . Эта формула позволяет выносить $x_i$ за знак функции. Последовательно вынося $x_1$, $x_2$,.., $x_n$ за знак $f(\vec { x } )$, получаем следующую формулу :
$ f(\vec { x } ) = \neg x_1 \wedge \neg x_2 \wedge …\wedge \neg x_ { n-1 } \wedge \neg x_n \wedge f(0,0,…,0,0)~\vee~$
$\neg x_1 \wedge \neg x_2 \wedge … \wedge \neg x_ { n-1 } \wedge x_n \wedge f(0,0,…,0,1) ~\vee~ $ $\dots $ $~\vee~ x_1 \wedge x_2 \wedge … \wedge x_ { n-1 } \wedge \neg x_n \wedge f(1,1,…,1,0) ~\vee~ $ $x_1 \wedge x_2 \wedge … \wedge x_ { n-1 } \wedge x_n \wedge f(1,1,…,1) $
Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от $n$ переменных мы имеем { { { $2^ { n } $ } } } конъюнктов. Каждый из них соответствует значению функции на одном из { { { $2^ { n } $ } } } возможных наборов значений $n$ переменных. Если на некотором наборе $f(\vec { x } )=0$, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же $ f(\vec { x } )=1$, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
Алгоритм построения СДНФ по таблице истинности
В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.
Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
Все полученные конъюнкции связываем операциями дизъюнкции.
Пример построения СДНФ для медианы
В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.
x y z $\langle x,y,z \rangle$
0 0 0 0
0 0 1 0
0 1 1 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
x y z $ \langle x,y,z \rangle $
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1 $(\neg { x } \land y \land z)$
1 0 0 0
1 0 1 1 $(x \land \neg { y } \land z)$
1 1 0 1 $(x \land y \land \neg { z } )$
1 1 1 1 $(x \land y \land z)$
Все полученные конъюнкции связываем операциями дизъюнкции. $ \langle x,y,z \rangle = (x \land y \land z) \lor (\neg { x } \land y \land z) \lor (x \land \neg { y } \land z) \lor (x \land y \land \neg { z } )$
Примеры СДНФ для некоторых функций
Стрелка Пирса: $x \downarrow y = (\neg { x } \land \neg { y } )$
Исключающее или: $x \oplus y \oplus z = (\overline { x } \land \overline { y } \land z) \lor (\overline { x } \land y \land \overline { z } ) \lor (x \land \overline { y } \land \overline { z } ) \lor (x \land y \land z)$
Совершенной дизъюнктивной нормальной формой формулы $A(x_1,x_2,…,x_n)$ называется ДНФ, обладающая следующими свойствами:
а } в ней нет одинаковых дизъюнктивных элементов;
б } ни одна элементарная конъюнкция не содержит двух одинаковых высказываний;
в } ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;
г } в каждой элементарной конъюнкции содержится либо $X_i$, либо $\overline { X } _i$, где $i = 1, n$.
Условие а } – г } являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:
1) если какая-нибудь элементарная конъюнкция не содержит высказывание $X_i$, то заменим выражением $B\wedge (X_i\vee \overline { X } _i) \equiv (B\wedge X_i)\vee (B\wedge \overline { X } _i)$;
2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;
3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;
4) удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием.
Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.
Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.
Формула называется дизъюнктивной нормальной формой { ДНФ } , если она является дизъюнкцией неповторяющихся элементарных конъюнкций. ДНФ записываются в виде: $A_1\vee A_2\vee …\vee A_n$ , где каждое $A_n$ — элементарная конъюнкция.
Формула $A$ от $k$ переменных называется совершенной дизъюнктивной нормальной формой { СДНФ } , если:
$A$ является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция $k$ переменных $x_1,x_2,…,x_k$, причем на $i$-м месте этой конъюнкции стоит либо переменная $x_i$ либо ее отрицание;
Все элементарные конъюнкции в такой ДНФ попарно различны.
Например: $A = x_1 \wedge$ НЕ $x_2 \vee x_1 \wedge x_2$
Совершенная дизъюнктивная нормальная форма представляет собой формулу, построенную по строго определенным правилам с точностью до порядка следования элементарных конъюнкций { дизъюнктивных членов } в ней.
Она является примером однозначного представления булевой функции в виде формульной { алгебраической } записи.
Теорема о СДНФ: Пусть $f(x_1 x_2, …, x_n)$ – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию $f$.
Алгоритм построения СДНФ по таблице истинности:
В таблице истинности отмечаем наборы переменных, на которых значение функции $f = 1$.
Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
Все полученные конъюнкции связываем операциями дизъюнкции.
3dstroyproekt.ru
Минимизация булевых функций
Минимизация булевых функций.
Совершенные нормальные формы записи логических функций дают однозначное представление логических функций, но иногда являются очень громоздкими. Поэтому для булевых функций, представленных в виде СДНФ или СКНФ, возникает задача минимизации.
Индексом простоты (или сложностью) булевой функции называется функция , определенная на множестве всех ДНФ и удовлетворяющая следующим свойствам:
Свойство неотрицательности: ;
Свойство монотонности: если , где-элементарная конъюнкция,.
Свойство выпуклости:
Свойство инвариантности: если ДНФ =получена из ДНФ =путем переименования переменных без отождествления, то.
Примеры. 1) – число букв переменных, встречающихся в записи. Под буквой понимают символ переменной или ее отрицание, если переменнаявходит в формулуm раз, то говорят, что формула содержит m букв . Например в выражениичисло переменных равно 3, а число букв равно 5, т.е. число букв равно числу вхождений переменных.
2) – число элементарных конъюнкций, входящих в.
3) – число символов отрицаний, встречающихся в записи. Каждый из указанных индексов удовлетворяет перечисленным свойствам.
Пример. Пусть задана вектором состояний. Тогда для нее может быть записана СДНФ в виде
Эту функцию можно упростить
Вычислим индексы простоты для и.
, ;,;
,.
Следовательно, прощедля всех трех индексов простоты.
Задача минимизации заданной логической функции сводится к представлению ее дизъюнктивной (или конъюнктивной) нормальной формой, имеющей наименьший индекс простоты. В качестве индекса простоты наиболее часто используется индекс .
Пример.
Построение сокращенной ДНФ методом Блейка.
Сокращенной д.н.ф. функции называется функция, которая содержит меньшее число букв, чем СДНФ. Если над СДНФ произвести все возможные операции склеивания, а затем все возможные операции поглощения то полученная функция будет иметь вид сокращенной ДНФ.
В основе использования метода Блейка лежат операции склеивания и операции поглощения.
Законы поглощения
,
,
,
Отметим, что формулы во втором столбце получаются из формул первого столбца с помощью принципа двойственности.
Закон склеивания (объединения конъюнкций): .
Закон обобщенного склеивания: .
Пример. Получить сокращенную ДНФ методом Блейка
1).

Минимизация булевых функций методом Квайна– Мак-Класки.
Импликантой функции называется конъюнкция некоторых аргументов из набора и их отрицаний, обладающая следующими свойствами:
1) Если на некотором наборе импликантапринимает значение 1, то ипринимает на этом наборе значение 1.
2 При исключении хотя бы одного множителя из свойство 1) не выполняется.
Пример.
на наборах (0,0,0), (0,0,1), (0,1,1).
Рассмотрим .на наборах (0,0,0), (0,0,1). На этих наборах , т.е. выполняется условие 1).
Если вычеркнуть один множитель из и оставить, например,, то.принимает значение 1 на наборах (0 0 0), (0 0 1),(0 1 0), (0 11), причем на выделенном наборе . Аналогичным образом ,принимает значение 1, причем на выделенных наборах. Следовательно, при вычеркивании одного множителя усвойство 1) не выполняется. Это означает, чтоявляется импликантой функции.
Пусть на некотором наборе функцияобращается в 1. Если на этом наборе импликантафункции обращается в 1, то говорят, чтоимпликанта накрывает эту единицу функции.
Система импликант функции называется полной, если любая единица из таблицы значений функции накрывается хотя бы одной импликантой.
Сокращенной ДНФ функции называется дизъюнкция всех импликант из полной системы импликант.
Утверждение. Сокращенная ДНФ. функции совпадает с самой функцией.
Действительно, дизъюнкция всех импликант из полной системы импликант равна 1 на тех наборах, где равна 1 функция ( в соответствии с определением импликанты ) и равна нулю на тех наборах, где равна нулю функция, т.е. значения сокращенной д.н.ф. функции и функциисовпадают.
Сокращенная д.н.ф. функции содержит меньшее число букв, чем СДНФ Однако, во многих случаях допускается дальнейшее сокращение числа букв за счет того, что некоторые из импликант могут поглощаться дизъюнкциями других импликант.
Система импликант функции называется приведенной, если эта система полна, а никакая ее часть не является полной системой импликант функции .
Тупиковой ДНФ называется дизъюнкция всех импликант, составляющих приведенную систему.
Тупиковая ДНФ- выражение, полученное из сокращенной ДНФ, дальнейшее упрощение которого невозможно в рамках ДНФ.
Минимальной ДНФ называется тупиковая ДНФ, состоящая из наименьшего числа букв.
Одна и та же сокращенная ДНФ может иметь несколько тупиковых ДНФ и несколько минимальных ДНФ.
Процесс минимизации на первом этапе сводится к построению полной системы импликант, затем приведенной системы существенных импликант, из которых строится сокращенная ДНФ, затем строятся тупиковые ДНФ и затем уже выбирается минимальная ДНФ. Решение задачи осуществляется в соответствии со схемой

Получение сокращенной ДНФ (нахождение импликантов функции ).
Пример 1.

Получение сокращенной ДНФ основывается на законе склеивания . Из него следует, что можно склеивать или объединять минтермы, отличающиеся только одним сомножителем. Будем склеивать не минтермы, а наборы. Выпишем все наборы переменных, соответствующие минтермам, входящим в разложение функции, в столбик, разбивая их на группы так, чтобы в каждую группу входили наборы с одинаковым числом единиц.
N
Груп
пы
Наборы

набора
1
0010 *
2 *
2,3
001– *
2,3,
.10,11
–01–
2,10
–010 *
2,10,
3,11
–01–
2
0011 *
3 *
3,11
–011 *
1001 *
()9 *
9,11
10–1
1010 *
10 *
9,13
1–01
1100 *
()12 *
10,11
101– *
10,14
1–10
12,13
110–
12,14
11–0
3
1011 *
()11 *
1101 *
() 13 *
1110 *
14 *
Проводим попарное склеивание наборов из соседних групп (для склеивания наборы должны отличаться на одну переменную). При склеивании общие элементы сохраняются, а элементы, которыми различаются наборы, заменяются чертой. Наборы, участвующие в склеивании, помечаются *. В результате образуется второй столбец, к которому также применяется операция склеивания. При этом склеивают наборы из соседних групп с одинаковым положением черточек. Далее образуется 3-й столбец и т.д. Процесс продолжается до тех пор, пока склеивание возможно.
Импликантами функции будут наборы во всех столбцах, не участвующие в склеивании (не помеченные).
, ,,,,.
Сокращенная ДНФ, ее длина составляет 17 букв

На рис. изображены импликанты и склеиваемые наборы переменных.
Отметим, что на рисунке номера наборов приведены в восьмеричной системе счисления.
2. Следующий этап – построение тупиковой ДНФ. Для этого нужно составить импликантную таблицу. Строки этой таблицы обозначены импликантами функции, а столбцы минтермами функции. Каждая импликанта является частью какого-нибудь дизъюнктивного члена в СДНФ и обращается в единицу на том же наборе, что и соответствующий минтерм. На пересечении строки, в которой записана импликанта, и столбцов соответствующих минтермов, частью которых является импликанта, поставим крестики. Тупиковые формы являются дизъюнкциями тех импликантов, которые накрывают все минтермы, т.е. в таблице нужно выбрать такие строки, чтобы во всех столбцах был как минимум один плюс.
Чтобы построить тупиковую форму, нужно выбрать минимальное число строк, покрывающих крестиками все столбцы. Ясно, что в систему выбранных строк должны обязательно входить строки, содержащие плюсы, которые являются единственными в столбце. Такие строки называются базисными. Простые импликанты, стоящие в базисных строках, образуют ядро рассматриваемой функции. Обведем кружочками плюсы в строках, соответствующих этим импликантам. Из оставшихся импликант выбираем минимальное число таких, которые покрывают крестиками все свободные столбцы (т.е. те, которые не содержат ).
Импликантная таблица
1
2
3
4
5
6
7
8
0010
0011
1001
1010
1100
1011
1101
1110
–01–

+
+
10–1
+
+
1–01
+
+
1–10
+
+
110–
+
+
11–0
+
+
В тупиковую ДНФ обязательно должна входить, иначе первые два столбца не накрываются. Следовательно, первая строка является базисной, а импликантаобразует ядро функции. При таком выборе автоматически накрываются и еще два столбца . Тупиковыми импликантами являются
(8)
(11)
(11)
(11)
(11)
(11)
(11)
На рисунке изображены все тупиковые ДНФ:

Среди всех тупиковых ДНФ выбираем ДНФ наименьшей длины:
МДНФ:
Матричный метод Карно.
Матричный метод основан на некоторых геометрических построениях. Соотношение между двоичными переменными можно представить в наглядной геометрической форме.
Рассмотрим логическую функцию двух переменных. Все четыре конъюнкции двух двоичных переменных (члены СДНФ) могут быть изображены на плоскости в виде точек с координатами 00,01,10,11, где первая цифра соответствует переменной , а вторая – переменной. Эти точки можно соединить линиями и полученный в результате квадрат будет наглядно изображать члены СДНФ двух переменных.

Координаты вершин квадрата, выраженные двоичными числами, соответствуют двоичным номерам конъюнкций.: 00 сответствует , 01 –, 10 – , 11 –. Координаты соседних вершин отличаются только одним двоичным знаком и, следовательно, минтермы, соответствующие этим числам, отличаются только одной переменной. Если объединить члены, соответствующие двум различным вершинам, то эта переменная будет исключена. Например, сложив минтермыи, изображаемые вершинами 00 и 01, получим=. Ту же операцию исключения переменной можно выполнить, сравнивая непосредственно два двоичных числа 00 и 01.В первом разряде двоичные знаки у обоих чисел одинаковы, поэтому в объединении ставим 0, во втором разряде знаки различны, поэтому во втором разряде ставим черту.

Число 0 соответствует переменной . Черта указывает, что исключена переменная. Следовательно, если два двоичных числа отличаются двоичными цифрами только в одном разряде, то их можно заменить двоичным числом, у которого в этом разряде можно поставить черточку. Черточка указывает номер исключенной переменной. Линия, соединяющая вершины 00 и 01 может быть названа линией.
Геометрической моделью функции трех переменных может служить трехмерный куб, вершины которого соответствуют членам СДНФ. Координаты соседних вершин отличаются, как и в случае плоской модели, только одним двоичным знаком, а соответствующие члены только одной переменной. Вследствие этого линии, соединяющие соседние вершины куба можно обозначить двумя переменными, которые на этой линии не меняют свое значение, а грани куба – одной переменной.
studfiles.net
Способы построения сокращенной ДНФ — МегаЛекции

Импликантом функции называется элементарная конъюнкция K такая, что . Импликант называется простым, если после удаления любого его сомножителя он перестает быть импликантом функции .
Интервал функции называется максимальным, если и не существует другого интервала такого, что . Т.е. интервал является максимальным тогда и только тогда, когда K – простой импликант функции . Отсюда
– единичное покрытие есть объединение всех максимальных интервалов.
ДНФ , реализующая функцию и соответствующая покрытию множества всеми максимальными интервалами, называется сокращенной ДНФ функции . Сокращенная ДНФ для данной функции определяется однозначно.
Теорама 5.1. Любая минимальная ДНФ функции , не совпадающая с ее сокращенной ДНФ, может быть получена из сокращенной путем удаления некоторых простых импликант.
Теорема 5.2. Сокращенная ДНФ любой монотонной функции алгебры логики не содержит отрицания переменных и является ее единственной минимальной и кратчайшей ДНФ.

ДНФ , реализующая функцию f и состоящая только из простых импликант, называется тупиковой для f, если удаление из нее хотя бы одной конъюнкции приводит к ДНФ, не реализующей функцию f.
Покрытие множества максимальными интервалами называется неприводимым, если после удаления из него любого интервала оно перестает быть покрытием.
Рассмотрим методы построения сокращенной ДНФ. Используем правила
склеивания (5.1)
поглощения (5.2)
неполного склеивания (5.3)
обобщенного склеивания (.4)
Здесь некоторые элементарные конъюнкции.5
Метод Блейка построения сокращенной ДНФ булевой функции состоит в последовательном применении правил (5.2) и (5.4). Сначала применяется правило (5.4) пока это возможно, а затем – (5.2).

Пример 5.5. Используя метод Блейка, построить сокращенную ДНФ функции .
Решение. =
(одинарной линией подчеркнуты слагаемые, которые при помощи правила (5.4) дают новую элементарную конъюнкция, которая выделена двойным подчеркиванием)

.
Далее применяется правило поглощения (подчеркнуты слагаемые, поглощаемые по правилу (5.2) переменной ):
= .
Слагаемое поглощается по правилу (5.2) слагаемым . Таким образом, получили сокращенную ДНФ .

Рассмотрим табличный метод построения минимальной ДНФ, основанный на использовании карт Карно.

Пример 5.6.Используя карту Карно, построить все минимальные ДНФ функции .
Решение. Строим покрытие всеми максимальными интервалами и выпишем соответствующую этому покрытию сокращенную ДНФ.
Рис. 5.11.
Сокращенная ДНФ данной функции имеет вид
.
Построим неприводимое покрытие и выпишем все тупиковые ДНФ, реализующие заданную функцию .
Рис. 5.12.
,
где L – число литералов в ДНФ.
Рис. 5.13. Рис. 5.14.
. .
Рис. 5.15. Рис. 5.16.
. .
Из полученных тупиковых ДНФ выберем те, которые имеют наименьшее число литералов и выпишем минимальные ДНФ:
; .

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

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

Пример 5.8. Построить сокращенную ДНФ по заданной КНФ функции .
Решение. Раскрываем скобки =
.
Теорема 5.3 (теорема Квайна). Если, исходя из совершенной ДНФ функции, произвести все возможные операции неполного склеивания, а затем – элементарного поглощения, то в результате получится сокращенная ДНФ, т. е. дизъюнкция всех простых импликант.
Рассмотрим алгоритм Квайна построения сокращенной ДНФ. Сперва к совершенной ДНФ функции применяется правило неполного склеивания (5.3) (к каждой паре конъюнкций), а затем при помощи операции поглощения (5.2) удаляются те конъюнкции ранга n, которые могут быть удалены. В результате получается некоторая ДНФ . Процедура повторяется, и на (k+1)-м шаге операции неполного склеивания и поглощения применяются к конъюнкциям ранга ДНФ . В результате получается ДНФ . Алгоритм завершается, если = .

Пример 5.9. Пусть функция f задана своей совершенной ДНФ.
.
Применим к ней алгоритм Квайна получения сокращенной ДНФ. Для этого для первой конъюнкции попарно применяем правило (5.3), затем для второй и т.д. (первая с третьей, вторая с третьей, вторая с четвертой, третья с пятой), после чего применяется правило (5.2). На первом этапе получим . На втором этапе правило (5.3) в применяется ко второй и пятой, третьей и четвертой конъюнкциям, а затем правило (5.2). Поэтому получим .

Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:
megalektsii.ru

x	y	z	$ \langle x,y,z \rangle $
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1	$(\neg { x } \land y \land z)$
1	0	0	0
1	0	1	1	$(x \land \neg { y } \land z)$
1	1	0	1	$(x \land y \land \neg { z } )$
1	1	1	1	$(x \land y \land z)$

N Груп пы	Наборы	набора
1	0010 *	2 *	2,3	001– *	2,3, .10,11	–01–
			2,10	–010 *	2,10, 3,11	–01–
2	0011 *	3 *	3,11	–011 *
	1001 *	()9 *	9,11	10–1
	1010 *	10 *	9,13	1–01
	1100 *	()12 *	10,11	101– *
			10,14	1–10
			12,13	110–
			12,14	11–0
3	1011 *	()11 *
	1101 *	() 13 *
	1110 *	14 *

	1	2	3	4	5	6	7	8
	0010	0011	1001	1010	1100	1011	1101	1110
–01–				+		+
10–1			+			+
1–01			+				+
1–10				+				+
110–					+		+
11–0					+			+

склеивания		(5.1)
поглощения		(5.2)
неполного склеивания		(5.3)
обобщенного склеивания		(.4)