ТУПИКОВЫЕ И СОКРАЩЕННЫЕ ДНФ. ГЕОМЕТРИЧЕСКИЕ И АНАЛИТИЧЕСКИЕ МЕТОДЫ ИХ ПОСТРОЕНИЯ

аранов Виктор Павлович. Дискретная математика. Раздел 5. ДНФ и схемы из ФЭ.

Лекция 225-26. Тупиковые и сокращенные ДНФ. Геометрические и аналитические методы их построения

Лекция 25-26. ТУПИКОВЫЕ И СОКРАЩЕННЫЕ ДНФ.

ГЕОМЕТРИЧЕСКИЕ И АНАЛИТИЧЕСКИЕ МЕТОДЫ ИХ ПОСТРОЕНИЯ

План лекции:

1. Определение тупиковой ДНФ.

2. Построение тупиковых ДНФ методом упрощения совершенной ДНФ.

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

4. Аналитические методы построения сокращенной ДНФ.

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

1. Определение тупиковой ДНФ

Пусть – произвольная ДНФ, которую можно представить следующим образом:

, .

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

Рассмотрим два типа преобразования ДНФ.

1. Операция удаления элементарной конъюнкции. Переход от ДНФ к ДНФ – преобразование, осуществляемое путем удаления элементарной конъюнкция . Данное преобразование определено тогда и только тогда, когда .
2. Операция удаления множителя. Переход от ДНФ к ДНФ – преобразование, осуществляемое путем удаления множителя . Данное преобразование определено тогда и только тогда, когда .

ДНФ , которую нельзя упростить при помощи преобразований I и II, называется тупиковой ДНФ. (ТДНФ).

Например, очевидно, что ДНФ будет тупиковой.

1. Построение тупиковых ДНФ методом упрощения совершенной ДНФ

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

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

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

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

Затем переходят к следующей элементарной конъюнкции. После обработки последней элементарной конъюнкции еще раз просматривают полученную ДНФ слева направо и пробуют применить операцию удаления элементарной конъюнкции. В результате получаем ТДНФ.

Пример1. Рассмотрим функцию . В табличной форме:

Таблица 1

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

В качестве исходной ДНФ выберем совершенную ДНФ

,

рассмотрим ее упорядочение и проследим работу алгоритма.

1. Конъюнкция не может быть удалена, но можно удалить множитель :

.

2. Конъюнкция не может быть удалена, но можно удалить множитель :

.

3. Конъюнкция , может быть удалена так как

.

4. Конъюнкция также может быть удалена (см. п. 1).

5. Конъюнкцию удалить нельзя, но можно удалить множитель :

.

6. Конъюнкцию удалить нельзя, но можно удалить множитель :

.

В результате получаем тупиковую ДНФ:

.

Если для той же функции взять другую упорядоченность ее совершенной ДНФ, например,

,

то в результате работы алгоритма упрощения получим другую тупиковую ДНФ:

.

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

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

Теорема. Пусть – произвольная булева функция () и – ее произвольная тупиковая ДНФ Тогда существует такое упорядочение совершенной ДНФ, из которого при помощи алгоритма упрощения получается тупиковая ДНФ .

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

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

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

Выполним оценку трудоемкости такой процедуры минимизации.

Однократное применение алгоритма упрощения содержит проверок возможности удаления конъюнкции, проверок возможности удаления множителя из и при вторичном просмотре не более проверок возможности удаления конъюнкций, то есть

.

Общее число упорядочения с учетом замечания, равно , причем

.

Это число меньше, чем , то есть этот алгоритм лучше, чем алгоритм перебора всех ДНФ, но все же он остается весьма трудоемким.

1. Определение сокращенной ДНФ и геометрический метод ее построения

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

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

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

,

,

.

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

x3

x2

x1

Рис. 1.

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

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

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

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

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

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

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

,

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

.

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

.

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

Таблица 2

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

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

.

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

,

.

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

.

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

.

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

1. Аналитические методы построения сокращенной ДНФ

Построение сокращенной ДНФ по совершенной ДНФ. Определим следующие операции над ДНФ:

1. Склеивание: .

2. Неполное склеивание: .

3. Поглощение: .

Алгоритм построения сокращенной ДНФ состоит в следующем:

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

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

Пример 4. Рассмотрим функцию, заданную табл. 1. Построим совершенную КНФ:

.

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

.

Отметим, что сокращенная ДНФ может иметь большее число членов, чем совершенная ДНФ.

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

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

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

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

Пусть . Составим таблицу 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

Тогда

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

,

,

,

,

,

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

ТУПИКОВЫЕ И СОКРАЩЕННЫЕ ДНФ. ГЕОМЕТРИЧЕСКИЕ И АНАЛИТИЧЕСКИЕ МЕТОДЫ ИХ ПОСТРОЕНИЯ