Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Дизъюнктивные нормальные формы




ЗАДАЧИ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ

Выражение вида

называется дизъюнктивной нормальной формой (ДНФ). Здесь есть элементарная конъюнкция (состоит из попарно различных литералов), ранг i -ой конъюнкции (число литералов в элементарной конъюнкции), mдлина ДНФ (число слагаемых). Если ранг , то элементарная конъюнкция называется пустой. При m =0 ДНФ полагается равной нулю и называется пустой.

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

 

Пример 5.1. Рассмотрим функцию . Ее можно представить в виде двух различных ДНФ и . При этом содержит только два литерала, а содержит шесть литералов.

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

 

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

 

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

Задача минимизации ДНФ заключается в построении для произвольной ее минимальной или кратчайшей ДНФ. Минимальная (кратчайшая) ДНФ булевой функции может оказаться не единственной.

Утверждение. Число различных ДНФ, составленных из переменных , равно .

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

Множество называется единичным покрытием функции . Для любой функции существует единичное покрытие и это соответствие является взаимнооднозначным. Говорят, что функция поглощает функцию , если .

 

Пример 5.3. Для построим единичное покрытие. Запишем таблицу истинности функции.

x y z
       
       
       
       
       
       
       
       

Отметим на кубе единичные наборы черными точками:

Рис. 5.1.

.

 

Подмножество есть интервал ранга r, соответствующий элементарной конъюнкции . Число называется размерностью интервала . Интервал можно рассматривать как множество наборов (вершин из ), у которых координат зафиксировано ..., , а остальные – принимают произвольные значения из множества . На рис. 5.2. приведены различные интервалы.

 

Рис. 5.2.

 

Для любой ДНФ функции , где элементарная конъюнкция, выполняется теоретико-множественное соотношение

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

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

Пусть – двоичный набор, являющийся представлением целого числа

,

тогда код Грея , соответствующий двоичному набору определяется по следующему правилу

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

Рассмотрим карты Карно для случаев . На рис. 5.3 показано как происходит кодирование наборов.

Рис. 5.3.

Карты Карно при n =1,2 приведены на рис. 5.4 (а, б), при n =3 – на рис. 5.5, при n =4 – на рис. 5.6.

Рис. 5.4.

Рис. 5.5. Рис. 5.6.

 

Пример 5.4. Рассмотрим задание функций при помощи карт Карно.

а) Для карта Карно имеет вид

Рис. 5.7.

б) Пусть функция задана при помощи карты Карно:

Рис. 5.8.

Выделим интервалы на карте

Рис. 5.9.

.

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

Рис. 5.10.

и для данной функции ее минимальная и кратчайшая ДНФ будет иметь вид .

 

Поделиться:





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



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...