Булевы функции и их форма

     9)

     10)  

     III. Найти КНФ для формулы 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     IV. Найти СКНФ для формулы 

     1)

     2)

     3)  

     4)

     5)  

     6)

     7)

     8)

     9)

     10)  

     V. Найти полином Жегалкина для  формулы 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

     Контрольные вопросы 

     

1. Разложение  булевых функций по переменным.
2. ДНФ и КНФ. Алгоритм их нахождения.
3. СДНФ и СКНФ. Алгоритмы их нахождения.
4. Полином Жегалкина, алгоритмы его нахождения.

 

     Рекомендованная литература 

     

1. В.Г. Карпов, В.А. Мощенский. Математическая логика и дискретная математика. Минск, «Вышэйшая  школа», 1977.
2. В.А. Мощенский. Лекции по математической логике. Минск, 1973.
3. А.А. Столяр. Математическая логика. Минск, 1991.
4. С.В. Яблонский. Введение в дискретную математику. Москва, 1979.

 

 

     Лабораторная  работа №3. Минимизация булевых функций 

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

     Заметим, что если некоторый символ в формуле, скажем встречается, например, два раза, то при подсчете числа символов в формуле он учитывается два раза.

     Рангом правильной элементарной конъюнкции называется число символов, входящих в нее.

     Сопоставим  каждой булевой функции 

     подмножество  

      ,  

     которое будем называть областью истинности функции  .

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

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

     Если  - список всех максимальных интервалов подмножества , то

 

      . 

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

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

     Рассмотрим  алгоритмы построения сокращенная  ДНФ.

     1 алгоритм – табличный.

     Пример 1. Найти сокращенную ДНФ для  

      . 

     Найдем

     Интервалы и - все максимальные интервалы - сокращенная ДНФ.

     2 алгоритм – метод Блейка:

     1) находим ДНФ;

     2) производим обобщенные склеивания до тех пор, пока это возможно;

     3) применяем правило поглощения.

     Пример 2. Найти сокращенную ДНФ для.

     Применяя  правило обобщенного склеивания, получаем:

     Затем правило поглощения и находим  сокращенную ДНФ.

     3 алгоритм – метод Нельсона:

     1) находим КНФ;

     2) разрываем скобки в соответствии  с дистрибутивным законом;

     3) применяем правило поглощения.

     Пример 3. Найти сокращенную ДНФ для функции

 

      . 

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

      .  

     Так как  , , то имеем  

      .  

     Применяя  правило поглощения, получаем сокращенную  ДНФ.

     IV алгоритм – метод минимизирующих  карт.

     Пример 4. Найти сокращенную ДНФ для функции  

      . 

     Составим  минимизирующую карту для данной функции.

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

     Выпишем все максимальные интервалы 

        

        

        

        

 

     Итак,  

        

     - требуемая сокращенная ДНФ.

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

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

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

     Всякая  минимальная ДНФ является тупиковой.

     Общая схема решения задачи минимизации  булевых функций состоит в  следующем:

1. выделяются все максимальные интервалы и строится сокращенная ДНФ;
2. строятся все тупиковые ДНФ;
3. среди всех тупиковых ДНФ выделяются все минимальные ДНФ.

     Рассмотрим  алгоритм построения всех тупиковых ДНФ. Суть данного алгоритма состоит в следующем:

1. для булевой функции строим сокращенную ДНФ;
2. для каждого набора из , выделяем в сокращенной ДНФ функции все такие элементарные конъюнкции , что , ;
3. составляем выражение вида

 

       (*) 

     

4. применяем к выражению вида (*) законы дистрибутивности и поглощения. В результате получаем

 

       

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

     Рассмотрим  работу данного алгоритма на следующем  примере.

     Пример 5. Найти все тупиковые ДНФ для булевой функции .

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

       

     Применяя  закон дистрибутивности, получаем: 

       

     Обозначим , , , , , . 

        

     составляем  выражение (*)

 

       

     Таким образом, имеет шесть тупиковых ДНФ 

     

     

     

     

     

       

     Две из них  и являются минимальными ДНФ. (метод Квайна)

     Рассмотрим  метод импликантных матриц нахождения минимальных ДНФ.

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

 

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

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

     Пример 6. Найти минимальные ДНФ для функции  

      . 

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

     Строим  импликантную матрицу