bulevy-funktsii-i-postr.-log.-skhem (1016573), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Действительно, предположим, что для функции f су110ществует КНФ с меньшим числом символов переменных, чем вМДНФ функции  f . Тогда отрицание от этой КНФ даст ДНФфункции f с меньшим числом символов переменных, чем в любой из минимальных ДНФ функции f . Получаем противоречие сминимальностью найденных ДНФ для функции f , следовательно, наше предположение неверное. Поэтому КНФ для функцииf , полученные из МДНФ функции  f , будут минимальными.Этапы минимизации в классе КНФ показаны на рис.18.6.2.СДНФфункцииСокр. ДНФфункцииПо методу Квайна-МакКласкиПо матрице Квайна (с помощью функции Петрика)ТДНФфункцииПо сложности ТДНФМДНФфункцииПо отрицанию МДНФМКНФфункции f18.6.2. Этапы минимизации в классе КНФ.111Запишем алгоритм минимизации булевых функций в классеКНФ:1.

Строим СДНФ функции f .2. По методу Квайна-МакКласки находим сокращённуюДНФ функции f .3. С помощью матрицы Квайна и функции Петрика находимвсе ТДНФ функции f .4. Среди построенных ТДНФ выбираем все минимальныеДНФ функции f .5. Взяв от каждой минимальной ДНФ функции f отрицание,получим все минимальные КНФ функции f.Обычно для булевой функции f находят обе минимальныеформы – МДНФ и МКНФ. Для реализации выбирают ту из них,которая содержит минимальное число символов переменных иприводит к наиболее простой логической схеме.Алгоритм минимизации функции в классе нормальных форм:1. Строим все МДНФ функции f.2. Строим все МКНФ функции f.3. Из построенных минимальных форм выбираем формы, содержащие наименьшее число символов переменных.Пример 18.6.1.

В классе нормальных форм минимизироватьфункцию f  1101 1011 .Решение.1. Находим все МДНФ функции f.СДНФ функции f : f ( x, y, z )  x yz  x yz  xyz  x yz  xyz  xyz.1.2.3.4.5.6.000 +001 +100 +011 +110 +111 +I столбец1.2.3.4.5.6.Таблица 18.6.1.001-2-001-30-12-41-03-5-114-6115-6II столбец112По методу Квайна-МакКласки находим сокращённую ДНФфункции f .Для нахождения простых импликант выписываем элементарные конъюнкции в формализованном виде и проводим операциюсклеивания (табл. 18.6.1.).Строим таблицу соответствий между полученными троичными векторами степеней и простыми импликантами(табл. 18.6.2):Таблица 18.6.2.Троичные вектораПростые импликантыстепеней001.xy2.3.4.5.6.-000-11-0-1111-yzxzxzyzxyСокращённая ДНФ данной булевой функции имеет вид:f  x, y, z   x y  yz  xz  xz  yz  xy .Строим матрицу Квайна (рис. 18.6.3.).18.6.3.

Матрица Квайна для функции.113Строк, содержащих только одну единицу, нет, поэтому нетядровых импликант.Составляем вспомогательную функцию Петрика:K  f    K1  K2   K1  K3  K3  K5   K2  K4   K4  K6  K5  K6    K1  K2 K3  K4  K2 K6  K5  K3K6    K1K4  K1K2 K6  K2 K3 K4  K2 K3 K6  K5  K3 K6   K1K 4 K5  K1K 2 K5 K 6  K 2 K3 K 4 K5  K 2 K3 K5 K 6  K1K3 K 4 K6  K1K 2 K3 K 6  K 2 K3 K 4 K 6  K 2 K3 K 6  K1K 4 K5  K 2 K3 K6  K1K 2 K5 K6  K 2 K3 K 4 K5  K1K3 K 4 K6 .По конъюнкциям вспомогательной ДНФ выписываем тупиковые ДНФ функции f :D1f  x y  xz  yz ; D2f  yz  xz  xy ;D3f  x y  yz  yz  xy ; D4f  yz  xz  xz  yz ;D5f  x y  xz  xz  xy .Минимальные ДНФ функции f :ffDmin1 x y  xz  yz ; Dmin2  yz  xz  xy .2.

Находим все МКНФ функции f.Повторяем указанные выше этапы для функции f .Выписываем СДНФ функции f : f ( x, y, z )  xyz  x yz .Находим сокращённую ДНФ функции f .Для нахождения простых импликант выписываем элементарные конъюнкции в формализованном виде (табл. 18.6.3.).Таблица18.6.3.1. 0102. 101I столбецОперация склеивания для данных троичных векторов степеней не определена, следовательно, сокращённая ДНФ данной булевой функции совпадает с СДНФ.114Строим матрицу Квайна (рис.

18.6.4.).18.6.4. Матрица Квайна для функции f .Импликанты P1 и P2 - ядровые, поэтому СДНФ функции fявляется для неё тупиковой и минимальной, т.е.fDmin xyz  x yz .Найдём минимальную КНФ функции f :ffKmin Dmin xyz  x yz  ( x  y  z )( x  y  z ).3. Из построенных минимальных форм выбираем формы,содержащие наименьшее число символов переменных.Построенные МДНФ и МКНФ имеют одно и то же числосимволов переменных равное шести, поэтому все они составляютминимальные формы для функции f :fDmin1 x y  xz  yz ;fDmin2  yz  xz  xy ;fKmin ( x  y  z )( x  y  z ) .18.7.

Карты КарноСамым удобным методом для быстрого решения задачи минимизации булевой функции от достаточно большого числа аргументов, является метод карт Карно, изобретённый в 1950-ыхгодах для разработки логических схем. После его примененияполучается минимальная форма функции в базисе (И, ИЛИ, НЕ).Прежде, чем приступить к рассмотрению карт Карно, покажем на простых примерах, как осуществляется соседнее кодирование для произвольного числа переменных.115Для одной переменной x1 существует только соседнее кодирование, так как она кодируется нулём и единицей.

Покажем соседнее кодирование для трёх переменных. Предлагается следующая операция:1. Напишем в один столбец коды переменной x1 . Между нулём и единицей в этом столбце проведём ось, которую назовёмосью симметрии 1-го ранга (рис.18.7.1).ось 1-го рангаРис. 18.7.1. Кодирование переменной.2.

Под столбцом для переменной x1 проведём ось симметрии,которую назовём осью симметрии 2-го ранга. Продолжим столбец кодов для переменной x1 симметрично относительно этойоси (симметрично относительно оси симметрии 2-го ранга разместятся и оси симметрии 1-го ранга) (рис.18.7.2).ось 1-го рангаось 2-го рангаось 1-го рангаРис.

18.7.2. Построение оси 2-го ранга.3. Дополним одноразрядный код до двухразрядного, вписавво втором разряде для переменной x2 нули выше оси 2-го ранга иединицы ниже этой оси (рис. 18.7.3).116Рис. 18.7.3. Кодирование переменной.Таким образом, мы осуществили соседнее кодирование длядвух переменных.4. Чтобы построить соседние коды для трёх переменных,проведём под столбцами двухразрядных кодов ось симметрии 3го ранга и продолжим столбцы кодов для переменных x1 и x2симметрично относительно этой оси, т.е. осуществим симметричное отображение относительно оси 3-го ранга (симметричноотносительно оси симметрии 3-го ранга разместятся и оси симметрии 1-го и 2-го рангов) (рис.18.7.4).ось 2-го рангаось 3-го рангаось 2-го рангаРис. 18.7.4.

Построение оси 3-го ранга.5. Дополним двухразрядный код до трёхразрядного, вписав втретьем разряде для переменной x3 нули выше оси 3-го ранга иединицы ниже этой оси. Получим соседнее кодирование для трёхпеременных (рис.18.7.5).117Рис. 18.7.5. Кодирование переменной.Следовательно, для того, чтобы осуществить соседнее кодирование для  n  1 переменной, если известно соседнее кодирование для n переменных, необходимо выполнить следующий алгоритм:1) под столбцом известного n -разрядного соседнего кодирования провести ось симметрии  n  1 -го ранга;2) осуществить симметричное отображение относительно осисимметрии  n  1 - ранга всех n -разрядных кодов и осей симметрии всех рангов до ранга n включительно;3) дополнить n -разрядные коды слева одним разрядом, в котором записать 0 для всех кодов выше оси симметрии  n  1 -горанга и 1 для кодов, расположенных ниже оси симметрии  n  1 го ранга.Карта Карно – это наглядная схема задания булевой функции, предназначенная для обнаружения целых групп соседнихэлементарных конъюнкций, к которым можно применить операцию склеивания.Для функции n переменных f  x1, x2 ,..., xn  карта Карнопредставляет собой таблицу, состоящую из 2n клеток.

Каждойклетке таблицы соответствует определённый набор переменных,при этом клетки закодированы так, чтобы соседним клеткам соответствовали соседние наборы переменных.118Для соседнего кодирование карт Карно по вышеизложенномуалгоритму производится разбиение множество n переменныхx1, x2 ,..., xn  на две группы в порядке возрастания их номеровx1, x2 ,..., xk  и xk 1, xk 2 ,..., xn  . Для каждой группы проводитсясоседнее кодирование.

Кодировке первой группы переменныхx1, x2 ,..., xk  ставятся в соответствие строки таблицы, кодировкевторой группы переменных  xk 1, xk 2 ,..., xn  – столбцы. В построенной таблице границы между строками и столбцами таблицы будут играть роль осей симметрии соответствующих соседнихкодировок групп переменных.На рисунке 18.7.6. представлены Карты Карно для 2, 3, 4 переменных.

Оси симметрии, необходимые для соседнего кодирования групп переменных, отмечены рангами.18.7.6. Карты Карно для 2, 3, 4, переменных.119В любой карте Карно соседними клетками, к которым можноприменить правило склеивания, являются не только смежныеклетки, но и клетки находящиеся на противоположных концахлюбой строки и любого столбца.18.7.7.

Карта Карно для 4-х переменных с соседними клетками, обозначенными буквой р.Например, на рисунке 18.7.7. в поле карты для 4-х переменных соседними будут клетки обозначенные буквой р. Им соответствуют наборы: (0000), (0010), (1000), (1010).Под прямоугольником Карно будем понимать некоторую выделенную группу 2k соседних клеток, закодированных соседними наборами, зачастую образующих разрозненную фигуру покрытия карты.18.7.8. Карта Карно для 5-ти переменных спрямоугольником Карно t.120Например, на рисунке 18.7.8.

в поле карты для 5-ти переменных изображён прямоугольник Карно t, состоящий из 23  8 элементарных квадратов Карно и описываемый соседними наборами: (00000), (00010), (01100), (01110), (10000), (10010), (11100),(11110).Возникает вопрос: как определить, будет ли выделенная накарте фигура прямоугольником Карно? Определение достоверности прямоугольника Карно основано на принципе симметрии иосуществляется с помощью приводимого ниже алгоритма.Алгоритм проверки достоверности прямоугольника Карно(принцип симметрии):1. Если предполагаемый прямоугольник Карно (ППК) охватывает одну ось симметрии, либо не охватывает ни одной, то перейти к п.4.2. Если ППК располагается по обе стороны от несколькихосей симметрии, то он должен быть симметричен относительнотой из этих осей, которая имеет максимальный ранг, иначе данная фигура не является прямоугольником Карно.3.

Характеристики

Список файлов учебной работы