Главная страница
Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей
qrcode

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


Название5. не полностью определенные булевы функции Не полностью определенные бф
Анкорраздел 5.doc
Дата30.09.2017
Размер2.51 Mb.
Формат файлаdoc
Имя файлараздел 5.doc
ТипДокументы
#22559
КаталогОбразовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей
Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей

5. не полностью определенные булевы функции
5.1. Не полностью определенные БФ
Для некоторых БФ значение функции на некоторых наборах может быть неопределенным. Это происходит, если данная комбинация двоичных входных переменных никогда не может образоваться, или не определено значение функции, т. е. не важно, какое значение принимает функция 0 или 1. Если значение БФ на некоторых наборах не определено, то такая БФ называется не полностью определенной. В таблице истинности значения БФ на этих наборах обозначаются крестом (Х), в отличие от определенных значений, обозначаемых 0 или 1. Например, не полностью определенная БФ f1 задана таблицей истинности (табл. 5.1, а).

Таблица 5.1

Таблица истинности БФ f1


Из табл. 5.1 (а) видно, что на 0, 1, 8, 10 наборах данная функция не определена. Эту функцию можно доопределить. Для этого вместо неопределенных значений БФ нужно поставить определенные, т. е. либо 0, либо 1. Очевидно, что в данном случае это можно сделать 16-ю способами, т. е. возможно построить 16 таблиц. Например, один из вариантов – это табл. 5.1 (б). Минимизация такой БФ аналитическими преобразованиями или картами Карно-Вейча будет состоять в рассмотрении всех возможных доопределений функции, минимизации их и выборе наименьшей формулы БФ. Таким образом, задача минимизации усложняется и для некоторых БФ может оказаться очень трудоемкой.

При задании не полностью определенных БФ числовым способом, не определенные наборы заключаются в дополнительные скобки, например, для f1, заданной СДНФ f1=(2,4,9,11(0,1,8,10)), а при задании этой же функции в СКНФ f1=(3,5,6,7,12,13,14,15(0,1,8,10)).
5.2. Минимизация не полностью определенных булевых функций с помощью карт Карно-Вейча
При минимизации не полностью определенных БФ с помощью карт Карно-Вейча алгоритм образования контуров дополняется следующим:

  1. при образовании контура, клетки карты, отмеченные Х, т. е. неопределенным значением, в любой момент времени, если это выгодно для образования контура большего размера, могут считаться отмеченными 1 для СДНФ или 0 для СКНФ;

  2. любой контур не должен покрывать только клетки, отмеченные неопределенными значениями Х;

  3. не все клетки, отмеченные Х, могут быть использованы при образовании контуров.

На рис. 5.1 (а) показана карта Карно, на которую нанесена БФ f1 и проведена ее минимизация.

Рис. 5.1. Минимизация БФ f1 в форме СДНФ

а – не полностью определенная; б – доопределенная по табл. 5.1 (б)
Функция (рис. 5.1, а) покрывается тремя контурами и описывается следующей формулой


Если же БФ доопределить в соответствие с табл. 5.1 (б), то контуры, покрывающие ее будут иметь вид, как на рис. 5.1 (б), а сама функция примет вид:

Очевидно, что второй вариант менее выгоден.

На рис. 5.2 приведены примеры не полностью определенных БФ Si и проведена их минимизация (используются карты Карно и Вейча):

Рис. 5.2. Минимизация не полностью определенных БФ:

  1. БФ S1=(1,2,3,5,7,8,12(0,4,11,13,14,15)) (рис. 4.2 а) (L=6, C=9)



  1. БФ S2=(2,3,5,9,14(0,1,7,11,12,13,15)) (рис. 4.2 б) (L=5, C=7)



  1. БФ S3=(1,3,10,13(0,2,4,15)) (рис. 4.2 в) (L=8, C=11)



  1. БФ S4=(0,1,4,5,6,8,9,13,14(7,10,11,12)) (рис. 4.2 г) (L=3, C=4)



  1. БФ S5=(1,3,5,6,9,13,15(0,2,7,10,11)) (рис. 4.2 д) (L=3, C=4)



  1. БФ S6=(1,3,6,7,8,12,14,15(2,5,10,11)) (рис. 4.2 е) (L=5, C=7)



  1. БФ S7=(0,1,2,3,7(5)) (рис. 4.2 ж) (L=2, C=2)



  1. БФ S8=(0,4,5,6(3,7)) (рис. 4.2 з) (L=3, C=4)


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

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

Основная идея этого метода состоит в следующем:

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

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

  3. из всех возможных тупиковых БФ выбирается самая короткая.

Рассмотрим этот метод на примере БФ:
F=(3,6,8,9,11,13,17,19,23,24,25,29,31).


Все конституенты единицы записываются в столбец конституент в виде их n-разрядных двоичных номеров. При записи производится разбиение на группы, содержащие m единиц в двоичном коде каждой группы (m=0n). Количество единиц в коде m называют индексом группы (в группе, где m=0 может быть только один код 00000, в группе m=n один код 11111). Остальные группы содержат различное число кодов. Для заданной БФ разбиение конституент единицы на группы показано на рис. 5.3.


Рис. 5.3. Разбиение конституент единицы на группы


  1. Образуется первый столбец остатков. Для этого попарно сравниваются двоичные номера всех кодов группы с индексом m с кодами группы с индексом m+1, начиная с группы с наименьшим индексом. Если сравниваемые коды различаются только в одном разряде, т. е. склеиваются, то в первый столбец остатков записываются десятичные номера склеенных конституент и двоичный код (сокращенный код) с прочерком в том разряде, где коды имеют отличие, при этом оба эти кода в столбце конституент отмечаются любым условным значком, например, «V». Значок V ставится только один раз, даже если набор участвует в нескольких операциях склеивания. Указанная операция повторяется для всех групп последовательно в порядке возрастания индекса m. Все неотмеченные в столбце конституент двоичные номера соответствуют простым импликантам (рис. 5.4, а, б). Из рисунка видно, что конституента единицы с номером 6 является простой импликантой, т. к. не склеивается ни с какой другой.

  2. К первому столбцу остатков применяются те же самые правила, и формируется второй столбец остатков. В этом столбце склеиванию подлежат те сокращенные коды, у которых прочерки стоят в одном разряде и имеется отличие только в одном разряде. Таким образом, во втором столбце остатков прочерки будут находиться уже в двух разрядах (рис. 5.4, в).

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

  4. Все неотмеченные импликанты являются простыми. Они во всех столбцах отмечаются последовательно буквами, причем одинаковые импликанты отмечаются одной и той же буквой.



Рис. 5.4. Получение столбцов остатков и

обозначение простых импликант


  1. Чтобы составить тупиковые формы БФ из простых импликант и построить минимальную форму, используют импликантную таблицу, или по-другому ее называют таблицей покрытий. Ее строки соответствуют простым импликантам, отмеченным буквами, а столбцы – конституентам единицы. Если простая импликанта покрывает конституенту единицы, то на пересечении строки и столбца ставится знак “X” (рис. 5.5).



Рис. 5.5. Импликантная таблица (таблица покрытий)


  1. Таблица покрытий просматривается по столбцам. Если в каком-либо столбце находится единственный Х, то импликанта, отмечающая строку, является существенной. Она обводится кружком, а этот столбец вычеркивается (на рис. 5.6 столбцы вычеркнуты сплошной линией). Также вычеркиваются все те столбцы, у которых на пересечении со строкой, отмеченной кружком, есть Х, (на рис. 5.6 столбцы вычеркнуты пунктирной линией). Множество существенных импликант образуют ядро функции. Для данной БФ ядро составляют импликанты A, M, N (рис. 5.6).



Рис. 5.6. Импликантная таблица с выделенными существенными

импликантами


  1. Все остальные импликанты не входят в ядро тупиковой функции. К ним относятся импликанты B, C, D, E, F, G, K, L. Среди них нужно выбрать такие, которые покрывали бы оставшиеся непокрытыми конституенты единицы (3, 11, 17, 19, 23, 31) минимальным способом. Таких вариантов может быть несколько. Например, импликанты B, E, G, K покрывают все оставшиеся конституенты единицы. В другом варианте, импликанты C, D, F, К также покрывают их. При большом количестве строк и столбцов в импликантной таблице задача поиска минимального покрытия перебором вариантов покрытия может оказаться довольно громоздкой и требующей значительных затрат времени.

  2. Существуют различные способы решения этой задачи. Один из них – алгебраический – предложен Петриком:

  • для каждой конституенты, не покрытой ядром функции, записывают дизъюнкцию импликант, покрывающих эту конституенту. Например, конституенту 00011 покрывают импликанты или В, или С, т. е. (В+С);

  • формируется произведение этих дизъюнкций, которое называется функцией покрытия ;

  • в полученной формуле раскрываются скобки по правилам алгебры логики;

  • из полученных конъюнкций выбирают самую короткую или, если их несколько, то любую из них;

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

Так для данной функции:
Ψ=(B+C)(B+D)(E+F)(C+E+G)(G+K)(K+L)=

=(B+BD+CB+CD)(CE+CF+E+EF+EG+FG)(GK+GL+K+KL).
Для упрощения выражения в каждой скобке применим операцию поглощения. Тогда:
Ψ=(B+CD)(E+CF+FG)(K+GL)=

=(BE+BCF+BFG+CDE+CDF+CDFG) (K+GL)=

=BEK+BCFK+BFGK+CDEK+CDFK+CDFGK+BEGL+

+BCFGL+BFGL+CDEGL+CDFGL.
Среди всех полученных конъюнкций минимальной длиной обладает только одна, а именно BEK, т. е. оставшиеся непокрытыми конституенты могут быть покрыты импликантами В, Е и K. Если в импликантой таблице вычеркнуть столбцы, у которых в строках В, Е и К стоит знак Х, то, с учетом ядра функции, должны оказаться вычеркнутыми все столбцы, т. е. покрыться все конституенты единицы (рис. 5.7) (на рис. 5.7 импликанты В, Е, К обведены прямоугольником, а столбцы вычеркнуты двойной линией).

Рис. 5.7. Импликантная таблица с покрытием всех конституент
Тогда функция F имеет вид:

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

Для сравнения минимизируем эту же функцию с помощью карты Карно (рис. 5.8).


Рис. 5.8. Минимизация функции F с помощью карты Карно
В соответствие с картой Карно функция будет иметь вид:
,
т. е. оба способа дают один результат.

При минимизации методом Квайна–Мак-Класки БФ, заданных СКНФ для получения минимальной конъюнктивной формы МКНФ, используется тот же самый алгоритм, но имеются следующие особенности:

  1. склеиванию подлежат пары:


;


  1. двоичные коды в столбцах конституент нуля и в столбцах остатков записываются в инверсной форме. Например, двоичный код числа 8 (1000) записывается как 0111. Индекс группы считается по количеству нулей в коде;

  2. в конечной формуле БФ записывается как произведение дизъюнкций. Причем, если в двоичном коде импликанты на месте разряда стоит единица, то переменная записывается в прямом виде, а если ноль, то в инверсном.

Пусть задана БФ У=П(1,3,6,7,9,13,14,15) и требуется найти ее МКНФ. На рис. 5.9 приведены столбец конституент и столбцы остатков. На основе этих данных строится таблица покрытия функции У (рис. 5.10). Из нее видно, что только F является существенной импликантой и входит в ядро функции. Чтобы найти остальные существенные импликанты составляется функция покрытия Ψ.


Рис. 5.9. Получение простых импликант функции У
Функция покрытия составляется, как и в предыдущем случае:
Ψ=(A+B)(A+C)(B+D)(D+E)=

=(A+AC+AB+BC)(BD+BE+D+DE)=(A+BC)(BE+D)=

=ABE+AD+BCE+BCD.
Наиболее коротким является произведение AD, т. е. простые импликанты A и D нужно присоединить к ядру F функции.

Рис. 5.10. Импликантная таблица функции У

При записи функции следует помнить, что если переменная в импликанте обозначается 1, то переменная в функции записывается в прямом виде, в противоположном случае в инверсном:


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


Рис. 5.11. Карта Карно функции У и минимизированная функция
5.4. Скобочные формы БФ
Тупиковые ДНФ и КНФ могут быть не самыми короткими формулами БФ. Например, формула имеет длину L=4, но если вынести за скобку переменную х1, то получим , и длина формулы уменьшается до L=3. Такая форма БФ носит название скобочной. Рассмотрим БФ от шести переменных:
.
Преобразуем ДНФ в скобочную форму, вынося одинаковые переменные:


Комбинационные схемы, реализующие оба варианта БФ Z, представлены на рис. 5.12.


Рис. 5.12. Реализации БФ Z:

а – по формуле ДНФ; б – по скобочной формуле
Рассмотрим еще один пример построения скобочной формы функции, заданной ДНФ: Q=ABE+ABF+ACDE+BCDF.

Перепишем функцию в несколько ином виде и вынесем за скобки общие сомножители:
Q= ABE+ABF+ACDE+BCDF=AB(AE+BF)+CD(AE+BF)=(АE+BF)(AB+CD).
Цена схемы для исходной функции С=18, для функции после преобразования в скобочную форму С=14. На рис. 5.13 приведены КС, реализующие обе функции.

Рис. 5.13. Реализация функции Q:

а – в форме ДНФ; б – в скобочной форме
Для контактных (релейных) схем скобочные формулы также дают более короткую реализацию.

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

Такой фрагмент БФ реализуется в электронных схемах с помощью элементарной функции «исключающее ИЛИ» (рис. 3.1, е), а в схемах на реле – парой переключающих контактов (рис. 3.13, д).

Задана БФ R=(0,1,3,12,13,15). Минимизация картой Карно дает результат (рис. 5.14, а). Если же минимизировать эту функцию как ДНФ (рис. 5.14, б) или раскрыть скобки в формуле КНФ, то получим другую формулу этой функции

Функция RКНФ реализована на логических элементах (рис. 5.14, в) и на реле (рис. 5.14, д). При реализации RДНФ на электронных элементах использован элемент «исключающее ИЛИ» (рис. 5.14, г), а в релейной схеме (рис. 5.14, е) использованы переключающие контакты реле.

Рис. 5.14. Реализация функции R:

а – карта Карно для КНФ; б – карта Карно для ДНФ;

в – электронная реализация RКНФ; г – релейная реализация RКНФ;

д – электронная реализация RДНФ; е – релейная реализация RДНФ
5.5. Применение законов поглощения для упрощения

формул БФ и КС
Законы поглощения в общем виде для конъюнктивной формы можно записать в следующем виде:


Например, для функции выполним алгебраические преобразования и преобразования с использованием выражения (5.1):



Результаты в обоих случаях одинаковы.

Для функции проведем преобразования с использованием выражения (5.2):



И в этом случае результаты одинаковы. Отсюда следует ряд правил, которые можно использовать для упрощения как контактных (релейных), так и логических схем.

  1. Если на выходе электронной схемы включен логический элемент И, на вход которого поступает переменная А, то на всех входах других элементов схемы вместо одноименных переменных А можно подать постоянный уровень «1», а вместо инверсного значения переменной Ā подать уровень «0». Пример преобразования приведен на рис. 5.15 (а), 5.15 (б).




Рис. 5.15. Упрощение комбинационной схемы:

а – прямая переменная; б – инверсная переменная


  1. Если последовательно с контактной схемой включен одиночный контакт реле, то все одноименные контакты этого реле можно закоротить, а все разноименные контакты исключить из схемы. Пример преобразования приведен на рис. 5.16 (а), 5.16 (б).




Рис. 5.16. Упрощение комбинационной схемы на реле:

а – прямая переменная; б – инверсная переменная
Для дизъюнктивных нормальных форм БФ законы поглощения имеют вид:


Правила упрощения электронных и контактных схем формулируются следующим образом:

  1. если на выходе электронной схемы включен элемент ИЛИ, на вход которого подается переменная хк, то на входах всех элементов вместо этой переменной можно подать 0, а вместо инверсного значения переменной подать 1. Пример приведен на рис. 5.17 (а), рис. 5.17 (б);

  2. если параллельно контактной схеме включен одиночный контакт реле, то все одноименные контакты этого реле можно исключить из схемы, а все разноименные контакты закоротить. Пример преобразования приведен на рис. 5.18 (а), рис. 5.18 (б).

Проведем алгебраические преобразования функций и покажем их тождественность при применении формул (5.1) и (5.2).

БФ, описывающие КС рис. 5.15 (а). Выход каждого логического элемента и всей КС:


Если к выходной функции D8 применить 5.1, то получится следующая формула:




Рис. 5.17. Упрощение комбинационной схемы:

а – прямая переменная; б – инверсная переменная


Рис. 5.18. Упрощение комбинационной схемы на реле:

а – прямая переменная; б – инверсная переменная
Обе формулы совпадают. Для схемы на рис. 5.15 (б)



При использовании формулы 5.1 выход D5 вычисляется как

КС на рис. 5.16 (а) описывается БФ, которая после алгебраических преобразований и преобразований с помощью выражений 5.1 и 5.2 имеют вид:


Для схемы на рис. 5.16 (б):


Для этой же схемы с учетом формулы 5.2:


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


Такие же преобразования для схемы на рис. 5.17 (б):

Для контактной схемы на рис. 5.18 (а)

Для контактной схемы на рис. 5.18 (б)





перейти в каталог файлов

Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей

Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей