Тексты лекций / Текст лекции 5

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

Элементарная конъюнкция, ранг элементарной конъюнкции. Дизъюнктивная нормальная форма (ДНФ), сложность ДНФ. Минимальная ДНФ. Импликанта, простая импликанта. Сокращенная ДНФ. Тупиковая ДНФ. Представление булевой функции в виде сокращенной, тупиковой и минимальной ДНФ.

Базовые понятия и утверждения

1. Постановка задачи минимизации ДНФ. Пусть задан алфавит переменных =

все переменные разные ( ≠ , если ≠ ), называют элементарной конъюнкцией ранга r над множеством X.

Константу 1 считают элементарной конъюнкцией ранга 0.

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

Например, пусть задан алфавит переменных = { , , , }. Тогда формула ̄ - элементарная конъюнкция ранга 3, а формула ̄- элементарная конъюнкция ранга 2 над множеством . Формула ̄ , напротив, элементарной конъюнкцией не является, так как в этой формуле дважды упоминается переменная .

Пример 1. Перечислить все элементарные конъюнкции над множеством { , }: 1,

, ̄, , ̄, ,̄ , ̄, ̄̄.

Вообще, используя алфавит из переменных = { , ,..., }, можно составить 3 элементарных конъюнкций. Действительно, произвольную элементарную конъюнкцию можно составить за этапов. На первом этапе принять решение относительно переменной(естьтривозможности-включитьеевконъюнкциюсамупосебе,включитьееотрицание или не включать ее вовсе), на втором - принять решение относительно переменной (вновь имеем три возможности) и т.д. Действуя описанным образом, мы составим 3 3 ... 3 = 3 элементарных конъюнкций (в их число входит и константа 1 - сопоставим

ее случаю, когда ни одна из переменных в конъюнкцию не включена).

Пример 2. Перечислить все элементарные конъюнкции ранга 3 над множеством

{ , , , }, обращающиеся в 1 на наборе (0,1,0,0).

◄ Произвольная элементарная конъюнкция равна 1 в том и только в том случае, когда всеобразующиееемножителиодновременноравны1. Значит, переменная может войти в элементарную конъюнкцию, обращающуюся в 1 на наборе (0,1,0,0), только без отрицания, а остальные переменные - обязательно с отрицанием. Таким образом, перебрав все вари-

1

Тема 5 «Минимизация дизъюнктивных нормальных форм» Олейник Т.А., 2020

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

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

Например, = ̄̄ - ДНФ сложности 6; = ̄̄ -

ДНФ сложности 4; = ̄ - ДНФ сложности 3 над множеством = { , , }. Заметим, что формулы , , равносильны и, следовательно, реализуют одну и ту жефункцию( , , ).Такимобразом,однаи тажефункция можетбытьзадананесколь-

кими ДНФ, причем эти ДНФ могут иметь различную сложность.

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

Так, для функции ( , , ), реализуемой рассмотренными выше ДНФ , , , дизъюнктивная нормальная форма = ̄ является минимальной.

Задача минимизации ДНФ формулируется так: для всякой булевой функции

( , ,..., ) найти представление в виде минимальной ДНФ.

Задачу минимизации ДНФ можно решить методом полного перебора, организовав его следующим образом.

1. Построить все ДНФ над множеством = { , ,..., }.

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

2. Отобрать из построенных ДНФ те, которые задают функцию .

Заметим, что для всякой булевой функции ( , ,..., ), тождественно отличной от нуля, есть, по крайней мере, одна представляющая ее ДНФ - это СДНФ.

3.Для каждой отобранной ДНФ определить сложность; ДНФ наименьшей сложности

иесть искомые минимальные ДНФ функции .

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

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

юнкция равна 1, функция также обращается в 1.

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

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

.

Пример 3. Перечислить все простые импликанты функции ( ,) = → .

2

◄ Имеем девять элементарных конъюнкций над переменными { , }: 1, , ̄, , ̄,, ̄, ̄, ̄̄. Относительно каждой из них выясним, является ли она импликантой, и если это так, то простая ли она.

Для удобства дальнейших рассуждений перечислим значения функции на всех набо-

рах значений переменных: (0,0) = 1, (0,1) = 1, (1,0) = 0, (1,1) = 1.

1 импликантой не является, так как обращается в 1 на всех наборах, в то время как

(1,0) = 0.

не является импликантой , так как на наборе (1,0) она обращается в 1, в то время как f (1,0) 0.

̄обращается в 1 на наборах (0,0), (0,1), и на каждом из этих наборов также равна 1, следовательно, ̄- импликанта . Эта импликанта простая, так как конъюнкция 1, полученная из нее путем удаления ̄, импликантой не является.

обращается в 1 на наборах (0,1), (1,1), и на каждом из этих наборов также равна 1, следовательно, - импликанта . Эта импликанта простая, так как конъюнкция 1, полученная из нее путем удаления , импликантой не является.

̄обращается в 1 на наборах (0,0) и (1,0), а (1,0) = 0, следовательно, ̄не является импликантой .

обращается в 1на одном наборе (1,1), и (1,1) = 1, следовательно, - импликанта. Однако простой эта импликанта не является, так как конъюнкция , полученная из нее путем удаления буквы , является импликантой.

̄обращается в 1 на одном наборе (0,1) и (0,1) = 1, следовательно, ̄- импликанта. Однако простой эта импликанта не является, поскольку конъюнкция ̄, полученная из нее путем удаления буквы , является импликантой.

̄обращается в 1 на наборе (1,0), а (1,0) = 0, следовательно, ̄не является импликантой .

̄̄обращаетсяв1нанаборе(0,0), (0,0) = 1,следовательно, ̄̄импликанта .Однако простой эта импликанта не является, так как конъюнкция ̄, полученная из нее путем удаления ̄, является импликантой.

Таким образом, функция имеет две простые импликанты: ̄и . ► Упражнение 2.18. Перечислить всепростыеимпликанты функции ( , ) = (1011).

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

Например, для функции ( , ) = → (см. пример 3) сокращенная ДНФ имеет вид

̄ .

Из определения сокращенной ДНФ непосредственно следует, что сокращенная ДНФ у функции единственна.

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

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

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

3

Тема 5 «Минимизация дизъюнктивных нормальных форм» Олейник Т.А., 2020

Имеетместоследующийтеоретическийфакт:минимальнаяДНФфункцииявляетсятупиковой ДНФ (доказательство приведено во второй части параграфа).

3. Построение минимальных ДНФ. Рассмотрим алгоритм построения минимальных ДНФ функции, исходя из СДНФ. Обоснование данного алгоритма можно найти в [1].

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

1-й этап: получение сокращенной ДНФ функции. Сокращенную ДНФ можно по-

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

а) операция неполного склеивания, состоящая в замене выражения ̄на ̄ ;

б) операция поглощения, состоящая в замене выражения на ; в) операция удаления дублируемых членов, состоящая в замене выражения на .

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

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

В качестве примера построим методом Квайна сокращенную ДНФ функции = (1001 1011):

2-й этап: построение тупиковых ДНФ.

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

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

Пусть - произвольная булева функция. Назовем носителем функции множество булевых векторов, на которых функция принимает значение 1. Пусть булевы векторы, ,..., - элементы носителя функции , , ,..., - совокупность простых импликант функции. Составим таблицу, строки которой соответствуют простым импликантам функции, столбцы - элементамносителя, а в ячейках на пересечении строки и столбца проставлено число , равное 1, если импликанта на наборе обращается в единицу, и равное 0 в противном случае (табл. 2.20). Назовем эту таблицу импликантной.

4

леву вектору (1 ≤ ≤ ) сопоставим дизъюнкцию тех импликант, значение которых наравно 1, и запишем конъюнкцию всех выписанных дизъюнкций.

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

ДНФ функции = (1001 1011). Ранее мы нашли сокращенную ДНФ этой функции, сле-

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

5

= ̄̄ ̄̄ ̄̄ ̄ ̄ ̄ ̄= ̄̄ ̄.

2-й и 3-й этапы для данной функции можно опустить. Действительно, нетрудно убедиться, что при опускании любой буквы в сокращенной ДНФ, получается формула, функцию не представляющая. Следовательно, сокращенная ДНФ ̄̄ ̄функции является также тупиковой и минимальной.

Переход I: операция неполного склеивания применена к парам конъюнкций 1 и 2, 1 и 4, 2 и 5, 3 и 7, 4 и 5, 5 и 6, 6 и 7.

6

Тема 5 «Минимизация дизъюнктивных нормальных форм» Олейник Т.А., 2020

Переход II: применена операция поглощения-каждая изконъюнкций4-горангапогло- щена какой-то из конъюнкций 3-го ранга.

Переход III: операция неполного склеивания применена к парам конъюнкций 8 и 12, 9

и 10.

Переход IV: применена операция поглощения и убраны дублирующие члены.

3-й этап. Тупиковые ДНФ функции имеют одинаковую сложность (равную 8), и, следовательно, обе являются минимальными. ►

Упражнение 2.19. Построить минимальные ДНФ функции:

а) = (1101 1001 ); б) = (1111 0001 0000 0011).

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

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

1, т.е. ( , ,..., ) = 1.

7

Тема 5 «Минимизация дизъюнктивных нормальных форм» Олейник Т.А., 2020

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

Теорема 2.7. Минимальная ДНФ функции является дизъюнкцией простых импликант этой функции.

Доказательство.Пусть -произвольнаяминимальнаяДНФфункции( , ,..., ). Поскольку задает , товсевходящиев элементарныеконъюнкции являютсяимпликантами .

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

Докажем, что задает функцию . Запишем в виде = ( ). Тогда =

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

Теорема 2.8. Минимальная ДНФ функции является тупиковой ДНФ.

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

Задачи повышенной сложности

2.13.Найти число элементарных конъюнкций ранга r над множеством { , ,..., }, обращающихся в единицу на наборе { , ,..., }.

2.14.Найти число всех элементарных конъюнкций над множеством { , ,..., }, обращающихся в единицу на наборе { , ,..., }.

2.15.Подсчитать число функций от n переменных, для которых данная элементарная конъюнкция ранга r является импликантой.

2.16.Пусть множества = { , ,..., } и = { , ,..., } не пересекаются, -

2.17.Назовем число элементарных конъюнкций, образующих ДНФ, ее длиной. Найти длину сокращенной ДНФ функции ... .

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

Ответы и указания к упражнениям

8

Тема 5 «Минимизация дизъюнктивных нормальных форм» Олейник Т.А., 2020

2.17. Переменная может войти в элементарную конъюнкцию, обращающуюся в единицу на наборе (1,0,0), только сама по себе, а переменные , - обязательно с отрицанием. Последовательно перебрав варианты выбора трех, двух и одной переменной из множества

9