3. Определение сокращенной днф и геометрический метод ее построения

Грань , содержащаяся в , называется максимальной, если не существует грани такой, что:

1. ;

2. Размерность грани больше размерности грани .

Пример 2. Пусть (см. пример 1). Рассмотрим конъюнкции , , , которым соответствуют грани

,

,

.

Эти грани имеют соответственно ранги , , и являются соответственно одномерной гранью (ребром), одномерной гранью (ребром) и двумерной гранью, которые представлены на рис. 1.

x₃ 



x₂



  x₁

Рис. 1.

Грани и – максимальные, а грань не максимальная для , так как и размерность больше размерности .

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

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

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

Теорема. Минимальная ДНФ функции состоит из простых импликант.

ДНФ, являющаяся дизъюнкцией всех простых импликант, называется сокращенной.

Пусть множество всех максимальных граней множества . Тогда

,

так как и каждая точка из принадлежит некоторой максимальной грани. Последнее равенство эквивалентно следующему :

.

Так как сокращенная ДНФ реализует функцию , то она имеет вид

.

Пример 3. Пусть функция задана таблицей 2:

Таблица 2

000	1	100	1
001	0	101	1
010	0	110	1
011	0	111	1

Этой функции соответствует множество

.

Имеем две максимальные грани:

,

.

Тогда покрытие для функции имеет вид:

.

Ему соответствует сокращенная ДНФ

.

Рассмотренный пример иллюстрирует геометрический метод построения сокращенной ДНФ Однако желательно иметь также и аналитическое решение.

17

Метод Блейка - Порецкого.

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

Ax v B/x = Ax v B/x v AB,

справедливость которой легко доказать. Действительно,

Ax = Ax v ABx;     B/x = B/x v AB/x.

Следовательно,

Ах v В/х = Ах v АВх v В/х v АВ/х = Ах V В/х V АВ.

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

f = /x₁/x₂ v x₁/x₂/x₃ v x₁x₂.

Найти методом Блейка - Порецкого сокращенную ДНФ функции f. Проводим обобщенные склеивания. Легко видеть, что первый и второй элемент заданной ДНФ допускают обобщенное склеивание по переменной х₁. В результате склеивания имеем:

/x₁/x₂ v x₁/x₂/x₃ = /x₁/x₂ v x₁/x₂/x₃ v /x₂/x₃.

Первый и третий элемент исходной ДНФ допускают обобщенное склеивание как по переменной х₁, так и по х₂. После склеивания по x₁ имеем:

/x₁/x₂ v x₁x₂ = /x₁/x₂ v x₁x₂ v /x₂x₂ = /x₁/x₂ v x₁x₂.

После склеивания по x₂ имеем:

/x₁/x₂ v x₁x₂ = /x₁/x₂ v x₁x₂ v /x₁x₁ = /x₁/x₂ v x₁x₂.

Второй и третий элемент ДНФ допускают обобщенное склеивание по переменной х₂. После склеивания получаем:

x₁/x₂/x₃ v x₁x₂ = x₁/x₂/x₃ v x₁x₂ v x₁x₃.

Выполнив последнее обобщенное склеивание, приходим к ДНФ:

f = /x₁/x₂ v x₁/x₂/x₃ v /x₂/x₃ v x₁x₂ v x₁/x₃.

После выполнения поглощений получаем:

f = /x₁/x₂ v /x₂/x₃ v x₁x₂ v x₁/x₃.

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

Метод Квайна.

"Метод Квайна основывается на применении двух основных соотношений.

1. Соотношение склеивания

Ах V А/х = Ах V А/х V А,

где А - любое элементарное произведение.

2. Соотношение поглощения

А~х V А = А,   ~х E {х; /x}.

Справедливость обоих соотношений легко проверяется. Суть метода заключается в последовательном выполнении всех возможных склеиваний и затем всех поглощений, что приводит к сокращенной ДНФ. Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью. Для доказательства достаточно показать, что произвольная простая импликанта р = x_i1x_i2 ... x_in может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания):

A = A (x v /x) = Ax v A/x

по всем недостающим переменным x_i^(k+l), ..., X_i^n исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта.

Таблица 4.1.1
x4x3x2x1	f
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1

Пример. Пусть имеется булева функция, заданная таблицей истинности (табл. 9.1.1). Ее СДНФ имеет вид

f = /x₁/x₂/x₃x₄ v /x₁/x₂x₃x₄ v /x₁x₂/x₃x₄ v /x₁x₂x₃x₄ v x₁x₂x₃/x₄ v x₁x₂x₃x₄.

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции f каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной x₃) и с конституентой 3 (по переменной х₂), конституента 2 с конституентой 4 и т. д. В результате получаем

1 - 2: /x₁/x₂x₄; 1 - 3: /x₁/x₃x₄; 2 - 4: /x₁x₃x₄; 3 - 4: /x₁x₂x₄; 4 - 6: x₂x₃x₄; 5 - 6: x₁x₂x₃.

Заметим, что результатом склеивания является всегда элементарное произведение, представляющее собой общую часть склеиваемых конституент Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

/x₁/x₂x₄ v /x₁x₂x₄ = /x₁/x₂x₄ v /x₁x₂x₄ v /x₁x₄; /x₁/x₃x₄ v /x₁x₃x₄ = /x₁/x₃x₄ v /x₁x₃x₄ v /x₁x₄,

с появлением одного и того же элементарного произведения /x₁x₄. Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:

x₂x₃x₄ v x₁x₂x₃ v /x₁x₄.

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

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

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

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

2. рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант.

Пример (продолжение). Ядром нашей функции являются импликанты x₁x₂x₃; /x₁x₄. Импликанта x₂x₃x₄ - лишняя, так как ядро накрывает все столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ:

f = x₁x₂x₃ v /x₁x₄

Следует отметить, что число N крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что

N = 2^n-k

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

Метод Квайна.

"Метод Квайна основывается на применении двух основных соотношений.

1. Соотношение склеивания

Ах V А/х = Ах V А/х V А,

где А - любое элементарное произведение.

2. Соотношение поглощения

А~х V А = А,   ~х E {х; /x}.

Справедливость обоих соотношений легко проверяется. Суть метода заключается в последовательном выполнении всех возможных склеиваний и затем всех поглощений, что приводит к сокращенной ДНФ. Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью. Для доказательства достаточно показать, что произвольная простая импликанта р = x_i1x_i2 ... x_in может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания):

A = A (x v /x) = Ax v A/x

по всем недостающим переменным x_i^(k+l), ..., X_i^n исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта.

Таблица 4.1.1
x4x3x2x1	f
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1

Пример. Пусть имеется булева функция, заданная таблицей истинности (табл. 9.1.1). Ее СДНФ имеет вид

f = /x₁/x₂/x₃x₄ v /x₁/x₂x₃x₄ v /x₁x₂/x₃x₄ v /x₁x₂x₃x₄ v x₁x₂x₃/x₄ v x₁x₂x₃x₄.

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции f каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной x₃) и с конституентой 3 (по переменной х₂), конституента 2 с конституентой 4 и т. д. В результате получаем

1 - 2: /x₁/x₂x₄; 1 - 3: /x₁/x₃x₄; 2 - 4: /x₁x₃x₄; 3 - 4: /x₁x₂x₄; 4 - 6: x₂x₃x₄; 5 - 6: x₁x₂x₃.

Заметим, что результатом склеивания является всегда элементарное произведение, представляющее собой общую часть склеиваемых конституент Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

/x₁/x₂x₄ v /x₁x₂x₄ = /x₁/x₂x₄ v /x₁x₂x₄ v /x₁x₄; /x₁/x₃x₄ v /x₁x₃x₄ = /x₁/x₃x₄ v /x₁x₃x₄ v /x₁x₄,

с появлением одного и того же элементарного произведения /x₁x₄. Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:

x₂x₃x₄ v x₁x₂x₃ v /x₁x₄.

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

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

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

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

2. рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант.

Пример (продолжение). Ядром нашей функции являются импликанты x₁x₂x₃; /x₁x₄. Импликанта x₂x₃x₄ - лишняя, так как ядро накрывает все столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ:

f = x₁x₂x₃ v /x₁x₄

Следует отметить, что число N крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что

N = 2^n-k

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

18

Построение тупиковых ДНФ на основе геометрических представлений

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

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

Алгоритм построения тупиковых ДНФ. Будем исходить из покрытия множества системой всех его максимальных граней .

Пусть . Составим таблицу 3, в которой

Таблица 3

		…		…
		…		…
…	…	…	…	…
		…		…
…	…	…		…
		…		…

Очевидно, что в каждом столбце содержится хотя бы одна единица. Для каждого найдем множество всех номеров строк, в которых столбец содержит 1. Пусть

.

Составим конъюнкцию, рассматривая номера строк как булевы переменные:

.

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

Пример 5. Рассмотрим функцию . Для нее множество состоит из 6 вершин, которые занумеруем числами I, II, …, VI. Максимальными гранями являются ребра, которые занумеруем арабскими цифрами (рис. 2).

III 3 IV

2

II  4

1 V

5

6 

I VI

Рис. 2.

Составим таблицу для множеств ( ) (табл. 4). Имеем

Таблица 4

	I	II	III	IV	V	VI
1	1	1	0	0	0	0
2	0	1	1	0	0	0
3	0	0	1	1	0	0
4	0	0	0	1	1	0
5	0	0	0	0	1	1
6	1	0	0	0	0	1

Тогда

Получили пять неприводимых покрытий или пять тупиковых ДНФ:

,

,

,

,

,

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