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

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

2015-01-30

81.74 KB

2 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


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

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

Лекция 27. МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ

План лекции:

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

2. Минимизация булевых функций методом карт Карно.

  1.  Минимизация булевых функций методом Квайна-Мак-Класски.

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

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

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

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

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

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

                                                                                                     Минимальные д .н .ф.

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

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

  1.  Минимизация булевых функций методом карт Карно

При использовании этого метода производится покрытие функций алгебры логики (ФАЛ) с помощью правильных конфигураций, содержащих нули или единицы. Правильными конфигурациями на карте Карно для ФАЛ от  переменных являются все прямоугольники (горизонтальные, вертикальные, квадраты), имеющие площадь  . При этом стремятся, чтобы число покрытий ФАЛ на карте было минимально, а площадь, покрываемая каждой конфигурацией – максимальна. Конфигурации могут перекрываться. Принцип минимизации заключается в объединении соседних полей карты в пределах правильной конфигурации.

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

Например, функция от четырех переменных  компактно записывается в форме матрицы размера [], как это показано на рис. 2.

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

00

01

11

10

00

1

1

0

1

01

1

1

0

1

11

0

1

1

0

10

1

1

1

1

                                                                      Рис. 2. Карта Карно

Для функции от четырех переменных имеем.

  1.  Конъюнкции ранга 4 соответствует одна клетка:

00

01

11

10

00

01

11

10

00

00

01

01

11

11

10

10

                                                                  

  1.  Конъюнкции ранга 3 соответствует пара соседних клеток:

00

01

11

10

00

01

11

10

00

01

11

10

00

00

00

01

01

01

11

11

11

10

10

10

                                                                                          

  1.  Конъюнкции ранга 2 соответствуют 4 клетки, образующие горизонтальный или вертикальный ряд, либо подматрицу размера []:

00

01

11

10

00

01

11

10

00

01

11

10

00

00

00

01

01

01

11

11

11

10

10

10

                                                                                                         

00

01

11

10

00

01

11

10

00

00

01

01

11

11

10

10

                                                         

  1.  Конъюнкции ранга 1 соответствуют 8 клеток из двух соседних горизонтальных или вертикальных рядов:

00

01

11

10

00

01

11

10

00

00

01

01

11

11

10

10

                                                                                

Пример 1. Для функции  (см. рис. 1) разобьем множество единичных клеток на следующие подмножества:

00

01

11

10

00

01

11

10

00

1

1

00

1

01

1

1

01

1

11

11

1

10

10

1

                                                                         

00

01

11

10

00

01

11

10

00

00

1

1

01

01

11

1

1

11

10

1

1

10

1

1

                                                                       

Объединение этих подмножеств дает все единичные клетки функции . Поэтому

                               .

  1.  Минимизация булевых функций методом Квайна-Мак-Класски

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

элементарная конъюнкция (набор ) ; номер 010(2); индекс 1;

элементарная конъюнкция (набор ) ; номер 110(6); индекс 2.

В результате реализации данного метода функция разлагается на простые импликанты. Алгоритм Квайна-Мак-Класски формулируется следующим образом: для того, чтобы два числа  и  являлись номерами двух склеивающихся между собой наборов, необходимо и достаточно, чтобы индексы данных чисел отличались на единицу, сами числа отличались на степень числа 2 и число с большим индексом было больше числа с меньшим индексом.

Пример 2. Реализацию алгоритма рассмотрим на примере минимизации функции

.

На первом этапе минимизации определяем номера и индексы каждого набора, записывая функцию в виде

.

На втором этапе группируем наборы, располагая их в порядке возрастания индексов (табл. 1).

                      Таблица 1. Минимизация ФАЛ методом Квайна-Мак-Класски

Индекс

Номер

Результаты склеивания

I

0001(1)

00-1

0-01

-001

0--1

-0-1

0--1

-0-1

II

0011(3)

0101(5)

1001(9)

0-11

-011

01-1

10-1

III

0111(7)

1011(11)

На третьем этапе производим склеивание различных наборов, руководствуясь приведенной выше формулировкой алгоритма. При склеивании не совпадающие в числах разряды отмечаются прочерками. Например, склеивание чисел 0001 и 0011 дает число   00-1. Результат склеивания записывается в следующий столбец таблицы 1, также разделяемый на строки с индексами, отличающимися на единицу. После склеивания всех групп первого столбца таблицы переходят ко второму, записывая результат склеивания в третий столбец. При объединении второго и последующих столбцов таблицы возможно склеивать только числа, содержащие прочерки в одноименных разрядах. Склеивание продолжается до тех пор, пока образование нового столбца станет невозможно.

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

                 Таблица 2. Импликантная таблица минимизируемой функции

Импликаты

Наборы

*

*

*

*

*

*

*

*

В результате минимизации функция  представится в виде

.


Совершенная
ДНФ

Сокращенная ДНФ

Тупиковая ДНФ

Тупиковая ДНФ

Тупиковая ДНФ

Тупиковая ДНФ



 

Другие похожие работы, которые могут вас заинтересовать.
9017. ПРОБЛЕМА МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ 109.86 KB
  ДНФ и схемы из ФЭ. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ План лекции: Понятие дизъюнктивной нормальной формы ДНФ. Понятие ДНФ. Выражение при где – элементарная конъюнкция ранга называется дизъюнктивной нормальной формой ДНФ.
9020. ПРИНЦИП ДВОЙСТВЕННОСТИ. РАЗЛОЖЕНИЕ БУЛЕВЫХ ФУНКЦИЙ ПО ПЕРЕМЕННЫМ. СОВЕРШЕННЫЕ ДИЗЪЮНКТИВНАЯ И КОНЪЮНКТИВНАЯ НОРМАЛЬНЫЕ ФОРМЫ 96.34 KB
  Данная теорема носит конструктивный характер, так как она позволяет для каждой функции построить реализующую ее формулу в виде совершенной д. н. ф. Для этого в таблице истинности для каждой для функции отмечаем все строки, в которых
19728. Методы управления ликвидностью банка в целях минимизации рисков 139.22 KB
  Взаимосвязь финансового рынка и банковской системы в Казахстане более прочна, чем во многих странах, прежде всего из-за финансовой слабости других государственных участников рынка. Поэтому перспективы развития отечественного финансового рынка непосредственно связаны с развитием банковской системы. Современное состояние банковского сектора можно охарактеризовать как неустойчивое в условиях кризиса.
11330. МЕТОДЫ ОСУЩЕСТВЛЕНИЯ ФУНКЦИЙ ГОСУДАРСТВА 52.51 KB
  Целью курсовой работы является освещение основных форм и методов осуществления функций государства. Понимание таких понятий, как функции государства, является сегодня совершенно необходимым условием формирования нашего мировоззрения и профессионализма.
4849. Формы и методы осуществления функций государства 197.3 KB
  Термин «функция» имеет в отечественной и зарубежной научной литературе далеко не одинаковое значение. В философском и общесоциологическом плане, он рассматривается, как «внешнее проявление свойств какого-либо объекта в данной системе отношений»; как совокупность обычных или же специфических действий отдельных лиц или органов
12997. Численные методы поиска экстремума функций одной переменной: метод золотого сечения 198.66 KB
  В архитектуре метод золотого сечения также нашёл своё применение. По законам золотого сечения были построены наиболее известные нам сооружения, такие как Парфенон ( V в. до н.э.), собор Парижской Богоматери (Нотр-дам де Пари). Яркими примерами в русской архитектуре станут Смольный собор в Санкт-Петербурге и храм Василия Блаженного, в котором, если взять высоту собора за единицу, то основные пропорции, определяющие членение целого на части, образуют ряд золотого сечения.
12098. Неинвазивные методы стимуляции спинного мозга для активации нейрональных локомоторных сетей и восстановления локомоторных функций 17.47 KB
  Краткое описание разработки Создаваемый метод стимуляции спинного мозга предназначен для разработки новой эффективной медицинской технологии лечения и двигательной реабилитации спинальных больных. Предложен новый способ активации нейрональных спинальных локомоторных сетей генератора шагательных движений с помощью неинвазивной электрической чрескожной стимуляции спинного мозга. Установлено что чрескожная электрическая стимуляция спинного мозга приложенная к ростральным сегментам поясничного утолщения T11T12 позвонки в условиях внешней...
15259. Методы, применяемые в анализе синтетических аналогов папаверина и многокомпонентных лекарственных форм на их основе [4.1] 3.1. Хроматографические методы [4.2] 3.2. Электрохимические методы [4.3] 3.3. Фотометрические методы [5] Заключение [6] Список л 233.66 KB
  Дротаверина гидрохлорид. Дротаверина гидрохлорид является синтетическим аналогом папаверина гидрохлорида а с точки зрения химического строения является производным бензилизохинолина. Дротаверина гидрохлорид принадлежит к группе лекарственных средств обладающих спазмолитической активностью спазмолитик миотропного действия и является основным действующим веществом препарата но-шпа. Дротаверина гидрохлорид Фармакопейная статья на дротаверина гидрохлорид представлена в Фармакопее издания.
2252. Метод Ньютона минимизации функции многих переменных 47.99 KB
  В этих методах для определения направления убывания функции использовалась лишь линейная часть разложения функции в ряд Тэйлора. Если же минимизируемая функция дважды непрерывно дифференцируема то возможно применение методов минимизации второго порядка которые используют квадратичную часть разложения этой функции в ряд Тэйлора. Разложение функции по формуле Тейлора в окрестности точки можно представить в виде Отсюда видно что поведение функции с точностью до величин порядка описывается квадратичной функцией 7.
19734. Практика управления кредитными рисками коммерческих банков и пути их минимизации 90.34 KB
  Известно, что любой бизнес в условиях рыночной экономики в различных сферах немыслим без риска. Поэтому изучение проблемы риска выступает одной из ключевых в финансовой и производственной деятельности каждого субъекта рынка. Особую актуальность представляют риски в сфере банковской деятельности, возникающие и проявляющиеся в различных направлениях деловой активности банков, то есть нет банковских операций, которые бы полностью исключали риск и заранее гарантировали определенный финансовый результат.
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.