Реферат: Булевы функции

--PAGE_BREAK--3.Булевы функции одной и двух переменных


Рассмотрим наиболее употребимые булевы функции одной и двух переменных. Функции одной переменной представлены в табл. 5.
Таблица 5

f(х)

х

Усл.

Наименование





1

обозн



f0 (х)







тождественный ноль (константа 0);

f1 (х)



1

х

тождественная функция

f2 (х)

1



<img width=«13» height=«21» src=«ref-1_1651687169-91.coolpic» v:shapes="_x0000_i1028">

отрицание х (инверсия);

f3 (х)

1

1

1

тождественная единица (константа 1).



Функции двух переменных представлены в табл. 6.

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

Отметим, что реально элементарной функции соответствует реализующий ее элемент, а суперпозиции булевых функций соответствует соединение элементов.
Таблица 6



х1





1

1

Наименование функции



х2



1



1



f0 (х1, х2)









константа 0

f1 (х1, х2)







1

конъюнкция

f2 (х1, х2)





1



запрет по х2

f3 (х1, х2)





1

1

переменная х1

f4 (х1, х2)



1





запрет по х1

f5 (х1, х2)



1



1

переменная х2

f6 (х1, х2)



1

1



сумма по модулю 2

f7 (х1, х2)



1

1

1

дизъюнкция

f8 (х1, х2)

1







операция Пирса (ф-ция Вебба)

f9 (х1, х2)

1





1

логическая равнозначность

f10 (х1, х2)

1



1



инверсия х2

f11 (х1, х2)

1



1

1

импликация от х2 к х1

f12 (х1, х2)

1

1





инверсия х1

f13 (х1, х2)

1

1



1

импликация от х1 к х2

f14 (х1, х2)

1

1

1



штрих Шеффера

f15 (х1, х2)

1

1

1

1

константа 1



Суперпозиция булевых функций представляется в виде логических формул. Однако следует отметить:

— одна и та же функция может быть представлена разными формулами;

— каждой формуле соответствует своя суперпозиция и, следовательно, своя схема соединений элементов;

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

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



    продолжение
--PAGE_BREAK--4.Основные законы и тождества булевой алгебры


Для булевой алгебры определены одна одноместная (унарная) операция “отрицание” и две двухместные (бинарные) операции конъюнкция и дизъюнкция (обозначаются «Ù», «Ú» соответственно). Приведем некоторые основные формулы.

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

Под унарной операцией на множестве А понимают выделение (фиксацию) какого-либо элемента множества А.

Преобразование формул булевых функций применением только аксиом булевой алгебры малоэффективно. Для упрощения формул используется целый ряд соотношений.  Из коммутативности и ассоциативности дизъюнкции следует, что дизъюнкция нескольких переменных может выполняться последовательно, причем порядок взятия дизъюнкции не влияет на результат. Формулы де Моргана:
<img width=«109» height=«28» src=«ref-1_1651687260-366.coolpic» v:shapes="_x0000_i1029"> <img width=«110» height=«28» src=«ref-1_1651687626-376.coolpic» v:shapes="_x0000_i1030">
Следствия из формул де Моргана:
<img width=«111» height=«31» src=«ref-1_1651688002-392.coolpic» v:shapes="_x0000_i1031"> <img width=«110» height=«31» src=«ref-1_1651688394-394.coolpic» v:shapes="_x0000_i1032">
Формулы для системы функций:

операция поглощения (х поглощает у): хÚху=х; или х(хÚу)=х.

операция склеивания: хуÚх<img width=«13» height=«25» src=«ref-1_1651688788-94.coolpic» v:shapes="_x0000_i1033">=х, или (хÚу)Ù(хÚ<img width=«13» height=«25» src=«ref-1_1651688788-94.coolpic» v:shapes="_x0000_i1034">)=х



5.Аналитическое представление булевых функций


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

Конституентой единицы(коньюнктивным термом) называется функция f(x1,x2,...,xn), принимающая значение 1 только на единственном наборе.

Конституента единицы записывается как логическое произведение nразличных булевых переменных, некоторые из них могут быть с отрицаниями. Можно легко выразить любую булеву функцию как дизъюнкцию конституент единицы, соответствующих тем наборам, на которых функция равна 1.

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

Наборы, на которых функция fпринимает значение 1, часто называются единичными, остальные — нулевыми наборами. Выписывать в СДНФ имеет смысл только конституенты единицы, соответствующие единичным наборам.

Пример. Выпишем СДНФ для функций, заданных таблицей истинности (табл. 7.).






х1х2х3

f(х1, х2, х3)



0 0 0



1

0 0 1

1

2

0 1 0

1

3

0 1 1



4

1 0 0



5

1 0 1

1

6

1 1 0



7

1 1 1

1



fСДНФ(х1, х2, х3)=
<img width=«57» height=«25» src=«ref-1_1651688976-170.coolpic» v:shapes="_x0000_i1035">Ú<img width=«59» height=«25» src=«ref-1_1651689146-172.coolpic» v:shapes="_x0000_i1036">Ú<img width=«59» height=«25» src=«ref-1_1651689318-167.coolpic» v:shapes="_x0000_i1037">Ú<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1038">
fСКНФ(х1, х2, х3)=
<img width=«108» height=«23» src=«ref-1_1651689645-220.coolpic» v:shapes="_x0000_i1039">Ù<img width=«108» height=«25» src=«ref-1_1651689865-233.coolpic» v:shapes="_x0000_i1040">Ù<img width=«108» height=«25» src=«ref-1_1651690098-234.coolpic» v:shapes="_x0000_i1041">Ù<img width=«108» height=«25» src=«ref-1_1651690332-236.coolpic» v:shapes="_x0000_i1042">
Другая известная форма носит название совершенной конъюнктивной номальной формы (СКНФ). Она строится аналогично СДНФ.

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

Конституента нуля записывается в виде элементарной дизъюнкции всех переменных. Каждому набору соответствует своя конституента 0. Например, набору 0110 переменны х1, х2, х3, х4 соответствует конституента нуля <img width=«147» height=«25» src=«ref-1_1651690568-282.coolpic» v:shapes="_x0000_i1043">.

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





    продолжение
--PAGE_BREAK--6.Функционально полные системы булевых функций


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

Определение. Функционально полной системой булевых функций (ФПСБФ) называется совокупность таких булевых функций {f1, f2,..., fk}, что произвольная булева функция fможет быть записана в виде формулы через функции этой совокупности.

К ФПСБФ следует отнести системы: {<img width=«21» height=«19» src=«ref-1_1651690850-156.coolpic» v:shapes="_x0000_i1044">,<img width=«21» height=«19» src=«ref-1_1651691006-155.coolpic» v:shapes="_x0000_i1045">, НЕ}, {<img width=«21» height=«19» src=«ref-1_1651690850-156.coolpic» v:shapes="_x0000_i1046">, <img width=«21» height=«22» src=«ref-1_1651691317-148.coolpic» v:shapes="_x0000_i1047">, НЕ}.

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

1) булевы функции, сохраняющие константу 0;

2) булевы функции, сохраняющие константу 1;

3) самодвойственные булевы функции;

4) линейные булевы функции;

5) монотонные булевы функции.

Определение. К булевым функциям, сохраняющим константу 0, относят такие булевы функции f(x1,x2,...,xn), для которых справедливо соотношение

f(0,..., 0)=0.

Примерами булевых функций, сохраняющих константу 0, являются функции f0 – f7 (табл. 6.).

Определение. К булевым функциям, сохраняющим константу 1, относят такие булевы функции f(x1,x2,...,xn), для которых справедливо соотношение f(1,1, ..., 1)=1.

Примерами булевых функций, сохраняющих константу 1, являются функции f1, f3, f5, f7 (табл. 6).

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

Определение. Булевы функции f1(x1,x2,...,xn) и f2(x1,x2,...,xn), называются двойственными друг другу, если выполняется соотношение f1(x1,x2,...,xn) = <img width=«115» height=«29» src=«ref-1_1651691465-251.coolpic» v:shapes="_x0000_i1048">

Двойственными являются функции из табл. 6 — f0 и f15, f1 и f7 и т. д.

Определение. К самодвойственным булевым функциям относят такие булевы функции, которые двойственны по отношению к самим себе, т. е. справедливо соотношение f1(x1,x2,...,xn) = <img width=«113» height=«29» src=«ref-1_1651691716-248.coolpic» v:shapes="_x0000_i1049">.

Если условиться называть противоположными наборами набор <img width=«12» height=«23» src=«ref-1_1651691964-73.coolpic» v:shapes="_x0000_i1050"><img width=«103» height=«37» src=«ref-1_1651692037-253.coolpic» v:shapes="_x0000_i1051"><img width=«12» height=«23» src=«ref-1_1651691964-73.coolpic» v:shapes="_x0000_i1052">и набор <img width=«103» height=«37» src=«ref-1_1651692363-262.coolpic» v:shapes="_x0000_i1053">, то определение самодвойственных функций дадим следующее.

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

Самодвойственными являются функции f3, f5, f10, f12 из табл. 6… Из определения самодвойственной функции следует, что она полностью определяется своими значениями на первой половине строк таблицы истинности.

Определение. К линейным булевым функциям относят такие булевы функции, которые представимы в виде

f(x1,x2,...,xn)=с0<img width=«21» height=«22» src=«ref-1_1651691317-148.coolpic» v:shapes="_x0000_i1054">с1х1<img width=«21» height=«22» src=«ref-1_1651691317-148.coolpic» v:shapes="_x0000_i1055">...<img width=«21» height=«22» src=«ref-1_1651691317-148.coolpic» v:shapes="_x0000_i1056"> сnхn,

где сі<img width=«12» height=«23» src=«ref-1_1651691964-73.coolpic» v:shapes="_x0000_i1057"><img width=«13» height=«13» src=«ref-1_1651693142-84.coolpic» v:shapes="_x0000_i1058">{0, 1}, а <img width=«21» height=«22» src=«ref-1_1651691317-148.coolpic» v:shapes="_x0000_i1059">  — операция «сумма по mod2».

Линейными являются булевы функции из табл. 6 — f0, f3, f5 и т. д.<img width=«12» height=«23» src=«ref-1_1651691964-73.coolpic» v:shapes="_x0000_i1060">

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

Определение. Двоичный набор <img width=«131» height=«27» src=«ref-1_1651693447-260.coolpic» v:shapes="_x0000_i1061">не меньше двоичного набора <img width=«123» height=«27» src=«ref-1_1651693707-270.coolpic» v:shapes="_x0000_i1062">, (т.е. <img width=«45» height=«21» src=«ref-1_1651693977-138.coolpic» v:shapes="_x0000_i1063">), если для каждой пары <img width=«95» height=«25» src=«ref-1_1651694115-231.coolpic» v:shapes="_x0000_i1064"> справедливо соотношение <img width=«49» height=«23» src=«ref-1_1651694346-149.coolpic» v:shapes="_x0000_i1065">.

Так, набор 1011 ≥1010. Вместе с тем наборы 1011 и 0100 несравнимы в том смысле, что для них не выполняется ни соотношение <img width=«45» height=«21» src=«ref-1_1651693977-138.coolpic» v:shapes="_x0000_i1066">, ни <img width=«45» height=«21» src=«ref-1_1651694633-136.coolpic» v:shapes="_x0000_i1067">.

Определение. Булева функция f(x1,x2,...,xn) называется монотонной, если для любых двух наборов <img width=«133» height=«29» src=«ref-1_1651694769-272.coolpic» v:shapes="_x0000_i1068"> и <img width=«130» height=«28» src=«ref-1_1651695041-285.coolpic» v:shapes="_x0000_i1069"> таких, что <img width=«45» height=«21» src=«ref-1_1651693977-138.coolpic» v:shapes="_x0000_i1070"> имеет место неравенство f<img width=«108» height=«25» src=«ref-1_1651695464-332.coolpic» v:shapes="_x0000_i1071"><img width=«13» height=«16» src=«ref-1_1651695796-87.coolpic» v:shapes="_x0000_i1072">f(<img width=«93» height=«25» src=«ref-1_1651695883-230.coolpic» v:shapes="_x0000_i1073">)

Монотонными являются булевы функции f0, f1,f3, f5 (из табл. 6) и т.д.

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

Теорема. Для того чтобы система Sбулевых функций была функционально полной, необходимо и достаточно, чтобы эта система содержала хотя бы одну булеву функцию, не сохраняющую константу 0, хотя бы одну булеву функцию, не сохраняющую константу 1, хотя бы одну несамодвойственную булеву функцию, хотя бы одну нелинейную булеву функцию и хотя бы одну немонотонную булеву функцию.

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

Рассмотрим примеры ФПСБФ. К таким ФПСБФ, наиболее распространенным в практике построения цифровых автоматов, следует отнести: (<img width=«36» height=«24» src=«ref-1_1651696113-211.coolpic» v:shapes="_x0000_i1074">, НЕ); (<img width=«52» height=«23» src=«ref-1_1651696324-159.coolpic» v:shapes="_x0000_i1075">, НЕ); (V, НЕ); (<img width=«15» height=«13» src=«ref-1_1651696483-86.coolpic» v:shapes="_x0000_i1076">, НЕ), (<img width=«52» height=«23» src=«ref-1_1651696324-159.coolpic» v:shapes="_x0000_i1077">,1); где символами V, <img width=«23» height=«21» src=«ref-1_1651696728-111.coolpic» v:shapes="_x0000_i1078">, <img width=«17» height=«19» src=«ref-1_1651696839-97.coolpic» v:shapes="_x0000_i1079">, НЕ, 1 обозначены булевы функции: «дизъюнкция», «конъюнкция», «сумма по mod2», «отрицание», «константа 1», соответственно.
    продолжение
--PAGE_BREAK--


7.Минимизация булевых функций


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

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

Определение. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

Определение. Минимальной дизъюнктивной нормальной формой булевой функции называется ДНФ, содержащая наименьшее число букв (по отношению ко всем другим ДНФ, представляющим заданную булеву функцию).  Определение. Булева функция g(x1,x2,...,xn) называется импликантой булевой функции f1(x1,x2,...,xn), если для любого набора переменных, на котором g = 1, справедливо f = 1.  Пример. Булева функция fзадана таблицей 8. Там же приведены все ее импликанты. При записи функции и ее импликант в СДНФ имеем
f= <img width=«57» height=«25» src=«ref-1_1651696936-166.coolpic» v:shapes="_x0000_i1080">Ú<img width=«59» height=«25» src=«ref-1_1651697102-168.coolpic» v:shapes="_x0000_i1081">Ú<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1082">

g1=<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1083">

g2=<img width=«59» height=«25» src=«ref-1_1651697102-168.coolpic» v:shapes="_x0000_i1084">

g3=<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1085">V<img width=«59» height=«25» src=«ref-1_1651697102-168.coolpic» v:shapes="_x0000_i1086">=<img width=«39» height=«23» src=«ref-1_1651698086-132.coolpic» v:shapes="_x0000_i1087">

g4=<img width=«57» height=«25» src=«ref-1_1651696936-166.coolpic» v:shapes="_x0000_i1088">

g5=<img width=«57» height=«25» src=«ref-1_1651696936-166.coolpic» v:shapes="_x0000_i1089">vv<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1090">=<img width=«41» height=«23» src=«ref-1_1651698710-135.coolpic» v:shapes="_x0000_i1091">

g6=<img width=«57» height=«25» src=«ref-1_1651696936-166.coolpic» v:shapes="_x0000_i1092">vv<img width=«59» height=«25» src=«ref-1_1651697102-168.coolpic» v:shapes="_x0000_i1093">

g7=<img width=«57» height=«25» src=«ref-1_1651696936-166.coolpic» v:shapes="_x0000_i1094">Ú<img width=«59» height=«25» src=«ref-1_1651697102-168.coolpic» v:shapes="_x0000_i1095">Ú<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1096">
Определение. Импликанта gбулевой функции f, являющаяся элементарной конъюнкцией, называется простой, если никакая часть импликанты g не является импликантой функции f.

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

1. Дизъюнкция любого числа импликант булевой функции f также является импликантой этой функции.

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

Перебор всех возможных импликант для булевой функции fиз рассмотренного примера дает возможность убедиться, что простых импликант всего две: g3 и g5. Следовательно, сокращенная ДНФ функции fимеет вид:
f= g3 Vg5 =<img width=«39» height=«23» src=«ref-1_1651698086-132.coolpic» v:shapes="_x0000_i1097">V<img width=«41» height=«23» src=«ref-1_1651698710-135.coolpic» v:shapes="_x0000_i1098">
Как видно из табл. 6.8., импликанты g3 и g5 в совокупности покрывают своими единицами все единицы функции f. Получение сокращенных ДНФ является первым этапом отыскания минимальных форм булевых функций. Как уже отмечалось, в сокращенную ДНФ входят все простые импликанты булевой функции. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая эквивалентности исходной функции. Такие простые импликанты назовем лишними. Исключение лишних простых импликант из сокращенных ДНФ — второй этап минимизации.

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

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

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

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


    продолжение
--PAGE_BREAK--7.1.Метод Квайна


Метод Квайна основывается на применении двух основных соотношений.

1.     Соотношение склеивания
<img width=«175» height=«21» src=«ref-1_1651699940-283.coolpic» v:shapes="_x0000_i1099">
где А — любое элементарное произведение.

2.     Соотношение поглощения
<img width=«147» height=«25» src=«ref-1_1651700223-275.coolpic» v:shapes="_x0000_i1100"><img width=«12» height=«23» src=«ref-1_1651691964-73.coolpic» v:shapes="_x0000_i1101">
Справедливость обоих соотношений легко проверяется.

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

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

Для доказательства достаточно показать, что произвольная простая импликанта р = <img width=«87» height=«24» src=«ref-1_1651700571-194.coolpic» v:shapes="_x0000_i1102">может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания): <img width=«172» height=«25» src=«ref-1_1651700765-294.coolpic» v:shapes="_x0000_i1103">по всем недостающим переменным исходной функции f, получаем совокупность Sконституент единицы. При склеивании всех конституент из Sполучим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество Sконституент обязательно присутствует в совершенной ДНФ функции fпоскольку р — ее импликанта.

Минимизация по методу Квайна выполняется по следующему алгоитму:

1. Выполняются все склеивания в СДНФ.

2. Выполняются все поглощения.

3. Результирующая функция проверяется на возможность дальнейшего склеивания и поглощения.

4. После получения сокращенной ДНФ строится импликантная матрица, по которой находятся “лишние” импликанты.

Пример. Пусть имеется булева функция, заданная таблицей истинности (табл 9). Ее СДНФ имеет вид:




f= <img width=«79» height=«25» src=«ref-1_1651701059-206.coolpic» v:shapes="_x0000_i1104">Ú<img width=«77» height=«25» src=«ref-1_1651701265-202.coolpic» v:shapes="_x0000_i1105">Ú<img width=«77» height=«25» src=«ref-1_1651701467-202.coolpic» v:shapes="_x0000_i1106">Ú<img width=«76» height=«25» src=«ref-1_1651701669-199.coolpic» v:shapes="_x0000_i1107">Ú<img width=«77» height=«25» src=«ref-1_1651701868-198.coolpic» v:shapes="_x0000_i1108">Ú<img width=«76» height=«23» src=«ref-1_1651702066-188.coolpic» v:shapes="_x0000_i1109">
Для удобства изложения пометим каждую конституенту единицы из СДНФ функции fкаким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой 3 (по переменной х2 ) конституента 2 с конституентой 4 и т. д. В результате получаем:
1-2: <img width=«59» height=«25» src=«ref-1_1651702254-169.coolpic» v:shapes="_x0000_i1110">

1-3: <img width=«59» height=«25» src=«ref-1_1651702423-170.coolpic» v:shapes="_x0000_i1111">

2-4: <img width=«57» height=«25» src=«ref-1_1651702593-167.coolpic» v:shapes="_x0000_i1112">

3-4: <img width=«57» height=«25» src=«ref-1_1651702760-168.coolpic» v:shapes="_x0000_i1113">

4-6: <img width=«60» height=«23» src=«ref-1_1651702928-163.coolpic» v:shapes="_x0000_i1114">

5-6: <img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1115">
Заметим, что результатом склеивания является всегда элементарное произведение, представляющее собой общую часть склеиваемых конституент.

Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:
<img width=«59» height=«25» src=«ref-1_1651702254-169.coolpic» v:shapes="_x0000_i1116">Ú<img width=«57» height=«25» src=«ref-1_1651702760-168.coolpic» v:shapes="_x0000_i1117">=<img width=«59» height=«25» src=«ref-1_1651702254-169.coolpic» v:shapes="_x0000_i1118">Ú<img width=«57» height=«25» src=«ref-1_1651702760-168.coolpic» v:shapes="_x0000_i1119">Ú<img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1120">

<img width=«59» height=«25» src=«ref-1_1651702423-170.coolpic» v:shapes="_x0000_i1121">Ú<img width=«57» height=«25» src=«ref-1_1651702593-167.coolpic» v:shapes="_x0000_i1122">=<img width=«59» height=«25» src=«ref-1_1651702423-170.coolpic» v:shapes="_x0000_i1123">Ú<img width=«57» height=«25» src=«ref-1_1651702593-167.coolpic» v:shapes="_x0000_i1124">Ú<img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1125">
с появлением одного и того же элементарного произведения <img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1126">. Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:
<img width=«60» height=«23» src=«ref-1_1651702928-163.coolpic» v:shapes="_x0000_i1127">Ú<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1128">Ú<img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1129">
Переходим к следующему этапу. Для получения минимальной ДНФ необходимо убрать из сокращенной ДНФ все лишние простые импликанты. Это делается с помощью специальной импликантной матрицы Квайна. Строки такой матрицы отмечаются простыми импликантами булевой функции, т. е. членами сокращенной ДНФ, а столбцы — конституентами единицы, т. е. членами СДНФ булевой функции.

Пример (продолжение). Импликантная матрица имеет вид (табл. 10).
Таблица 10.

Простые

Конституенты единицы

импликанты

<img width=«79» height=«25» src=«ref-1_1651701059-206.coolpic» v:shapes="_x0000_i1130">

<img width=«77» height=«25» src=«ref-1_1651701265-202.coolpic» v:shapes="_x0000_i1131">

<img width=«77» height=«25» src=«ref-1_1651701467-202.coolpic» v:shapes="_x0000_i1132">

<img width=«76» height=«25» src=«ref-1_1651701669-199.coolpic» v:shapes="_x0000_i1133">

<img width=«77» height=«25» src=«ref-1_1651701868-198.coolpic» v:shapes="_x0000_i1134">

<img width=«76» height=«23» src=«ref-1_1651702066-188.coolpic» v:shapes="_x0000_i1135">

<img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1136">

Х

Х

Х

Х





<img width=«60» height=«23» src=«ref-1_1651702928-163.coolpic» v:shapes="_x0000_i1137">







Х



Х

<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1138">









Х

Х



Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной матрицы на пересечении строки (с рассматриваемой простой импликантой) и столбца (с конституентой единицы) отмечается крестиком (табл. 10). Минимальные ДНФ строятся по импликантной матрице следующим образом:

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

2) рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант.

Пример (продолжение). Ядром нашей функции являются импликанты <img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1139"> и <img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1140">. Импликанта <img width=«60» height=«23» src=«ref-1_1651702928-163.coolpic» v:shapes="_x0000_i1141">  — лишняя, так как ядро накрывает все столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ:

fmin=<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1142">Ú<img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1143">

Следует отметить, что число N крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что N = 2n-k, где k— число букв, содержащихся в простой импликанте.

Заметим также, что используя различные соотношения, можно расширить область применения метода Квайна за пределы совершенной ДНФ.


    продолжение
--PAGE_BREAK--7.2 Метод Квайна-Мак-Класки


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

1. Все конституенты единицы из СДНФ булевой функции fзаписываются их двоичными номерами.

2. Все номера разбиваются на непересекающиеся группы. Признак образования і-й группы: і единиц в каждом двоичном номере конституенты единицы.

3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием, звездочкой и т.д.).

4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Нахождение минимальных ДНФ далее производится по импликантной матрице, как и в методе Квайна. Более подробно рассмотрим метод на примере решения следующей задачи: минимизировать методом Квайна-Мак-Класки булеву функцию f, заданную таблицей истинности (табл. 9).

1. В СДНФ функции fзаменим все конституенты единицы их двоичными номерами: f=0001Ú0011Ú0101Ú0111Ú1110Ú1111

2. Образуем группы двоичных номеров. Признаком образования і-й группы является і единиц в двоичном номере конституенты единицы (табл.11).

3. Склеим номера из соседних групп табл.11. Склеиваемые номера обозначим звездочками (номер отмечается в том случае, если участвует в склеивании хотя бы один раз). На месте разрядов, по которым произошло склеивание, проставляются прочерки. Результаты склеивания занесем в табл. 12. Склеим номера из соседних групп табл. 12. Склеиваться могут только номера, имеющие прочерки в одинаковых позициях. Склеиваемые номера отметим. Результаты склеивания занесем в табл. 13.

4. Имеем три простые импликанты: -111, 111-, 0--1.
Таблица 11     Таблица 12   Таблица 13

Номер группы

Двоичные номера кон-ституент 1



Номер

группы

Двоичные номера

импликант



Номер

группы

Двоичные номера

импликант



-



1 (1-2)

00-1 *



1

0--1

1

0001 *





0-01 *





0--1

2

0011 *



2 (2-3)

0-11 *



2

-111



0101 *





01-1 *





111-

3

0111 *



3 (3-4)

-111









1110 *





111-







4

1111 *













Таблица 14

Простые

Конституенты единицы

импликанты

<img width=«79» height=«25» src=«ref-1_1651701059-206.coolpic» v:shapes="_x0000_i1144">

<img width=«77» height=«25» src=«ref-1_1651701265-202.coolpic» v:shapes="_x0000_i1145">

<img width=«77» height=«25» src=«ref-1_1651701467-202.coolpic» v:shapes="_x0000_i1146">

<img width=«76» height=«25» src=«ref-1_1651701669-199.coolpic» v:shapes="_x0000_i1147">

<img width=«77» height=«25» src=«ref-1_1651701868-198.coolpic» v:shapes="_x0000_i1148">

<img width=«76» height=«23» src=«ref-1_1651702066-188.coolpic» v:shapes="_x0000_i1149">

<img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1150">(0--1)

Х

Х

Х

Х





<img width=«60» height=«23» src=«ref-1_1651702928-163.coolpic» v:shapes="_x0000_i1151">(-111)







Х



Х

<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1152">(111-)









Х

Х



5. Строим импликантную матрицу (табл. 14). По таблице определяем совокупность простых импликант — 0--1 и 111-, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам:

fmin=<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1153">Ú<img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1154">

Заметим, что разбиение конституент на группы позволяет уменьшить число попарных сравнений при склеивании.


    продолжение
--PAGE_BREAK--7.3 Метод диаграмм Вейча


Метод позволяет быстро получать минимальные ДНФ булевой функции fнебольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (табл. 15). Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. В табл.15. это соответствие показано. В клетке диаграммы Вейча ставится единица, если булева функция принимает единичное значение на соответствующем наборе. Нулевые значения булевой функции в диаграмме Вейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующий вид (табл. 16). Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (табл. 17). Таким же образом, т. е. приписыванием еще одной диаграммы 4-х переменных, к только что рассмотренной, можно получить диаграмму для функции 5-ти переменных и т. д., однако диаграммы для функций с числом переменных больше 4-х используются редко.

Для приведенных диаграмм характерно следующее:

1)     каждой клетке диаграммы соответствует свой набор;
Таблица 15.    Таблица 16.



<img width=«38» height=«20» src=«ref-1_1651709870-139.coolpic» v:shapes="_x0000_i1155">

<img width=«40» height=«21» src=«ref-1_1651710009-140.coolpic» v:shapes="_x0000_i1156">





<img width=«38» height=«20» src=«ref-1_1651709870-139.coolpic» v:shapes="_x0000_i1157">

<img width=«40» height=«21» src=«ref-1_1651710009-140.coolpic» v:shapes="_x0000_i1158">



<img width=«24» height=«18» src=«ref-1_1651710428-131.coolpic» v:shapes="_x0000_i1159">

11

01



<img width=«24» height=«18» src=«ref-1_1651710428-131.coolpic» v:shapes="_x0000_i1160">

110

111

011

010



<img width=«22» height=«18» src=«ref-1_1651710690-128.coolpic» v:shapes="_x0000_i1161">

10

00



<img width=«22» height=«18» src=«ref-1_1651710690-128.coolpic» v:shapes="_x0000_i1162">

100

101

001

000













<img width=«40» height=«18» src=«ref-1_1651710946-140.coolpic» v:shapes="_x0000_i1163">

<img width=«53» height=«24» src=«ref-1_1651711086-161.coolpic» v:shapes="_x0000_i1164">

<img width=«40» height=«18» src=«ref-1_1651710946-140.coolpic» v:shapes="_x0000_i1165">





Таблица 17.       Таблица 18.



<img width=«41» height=«20» src=«ref-1_1651711387-144.coolpic» v:shapes="_x0000_i1166">

<img width=«42» height=«21» src=«ref-1_1651711531-147.coolpic» v:shapes="_x0000_i1167">







х1

<img width=«19» height=«23» src=«ref-1_1651711678-108.coolpic» v:shapes="_x0000_i1168">

х1

1100

1101

1001

1000

<img width=«22» height=«23» src=«ref-1_1651711786-104.coolpic» v:shapes="_x0000_i1169">



<img width=«24» height=«18» src=«ref-1_1651710428-131.coolpic» v:shapes="_x0000_i1170">

1

1



1

х1

1110

1111

1011

1010

х3



<img width=«22» height=«18» src=«ref-1_1651710690-128.coolpic» v:shapes="_x0000_i1171">







1

<img width=«19» height=«23» src=«ref-1_1651711678-108.coolpic» v:shapes="_x0000_i1172">

0110

0111

0011

0010

х3





<img width=«40» height=«18» src=«ref-1_1651710946-140.coolpic» v:shapes="_x0000_i1173">

<img width=«53» height=«24» src=«ref-1_1651711086-161.coolpic» v:shapes="_x0000_i1174">

<img width=«40» height=«18» src=«ref-1_1651710946-140.coolpic» v:shapes="_x0000_i1175">

<img width=«19» height=«23» src=«ref-1_1651711678-108.coolpic» v:shapes="_x0000_i1176">

0100

0101

0001

0000

<img width=«22» height=«23» src=«ref-1_1651711786-104.coolpic» v:shapes="_x0000_i1177">















<img width=«23» height=«23» src=«ref-1_1651712910-106.coolpic» v:shapes="_x0000_i1178">

х4

х4

<img width=«23» height=«23» src=«ref-1_1651712910-106.coolpic» v:shapes="_x0000_i1179">

















2) соседние наборы расположены рядом в строке либо в столбце. Соседними наборами называются наборы, отличающиеся одной компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются (см. метод Квайна-Мак-Класки). Например, для функции, заданной табл. 18, конституенты, соответствующие паре единиц в левой части таблицы, склеиваются и порождают элементарное произведение из двух букв:
<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1180"><img width=«72» height=«25» src=«ref-1_1651713282-189.coolpic» v:shapes="_x0000_i1181">=<img width=«39» height=«23» src=«ref-1_1651698086-132.coolpic» v:shapes="_x0000_i1182">
О паре единиц в правой части диаграммы можно сказать то же самое: <img width=«59» height=«25» src=«ref-1_1651689146-172.coolpic» v:shapes="_x0000_i1183"><img width=«73» height=«24» src=«ref-1_1651713775-186.coolpic» v:shapes="_x0000_i1184">=<img width=«40» height=«24» src=«ref-1_1651713961-138.coolpic» v:shapes="_x0000_i1185">.
Отметим, что получающееся элементарное произведение легко определить сразу по диаграмме: это произведение переменных, принимающих одно и то же значение в обеих клетках.

Еще одно важное замечание: столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашего примера это означает, что имеет место еще одно склеивание, в результате которого, следуя указанному правилу, получаем элементарное произведение <img width=«43» height=«25» src=«ref-1_1651714099-142.coolpic» v:shapes="_x0000_i1186">. Из рассмотренных ранее методов нам известно, что возможно дальнейшее склеивание получаемых элементарных произведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеивания на диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Число mоставшихся переменных в элементарном произведении определяется легко:

m=n-log2M,

где  n— число переменных,

M— число склеиваемых наборов.

Метод широко используется на практике, благодаря простоте и удобству. После небольшой тренировки достигается элементарный навык определения минимальной ДНФ по диаграмме «с первого взгляда».

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

В диаграмме Вейча необходимо и достаточно, чтобы каждая единичная клетка участвовала в склейке хотя бы один раз.

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

Вся диаграмма должна быть покрыта наименьшим количеством склеек. В склейку может входить 2nсоседних клеток (2, 4, 8, 16. и т.д.).

Рассмотрим несколько примеров.
Таблица 19   Таблица 20

<img width=«29» height=«60» src=«ref-1_1651714241-155.coolpic» v:shapes="_x0000_s1026"><img width=«25» height=«35» src=«ref-1_1651714396-121.coolpic» v:shapes="_x0000_s1027"><img width=«8» height=«78» src=«ref-1_1651714517-118.coolpic» v:shapes="_x0000_s1028"><img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1187"> <img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1188">      X4  X3

<img width=«24» height=«51» src=«ref-1_1651714936-138.coolpic» v:shapes="_x0000_s1029">

<img width=«41» height=«20» src=«ref-1_1651711387-144.coolpic» v:shapes="_x0000_i1189">

<img width=«42» height=«21» src=«ref-1_1651711531-147.coolpic» v:shapes="_x0000_i1190">





<img width=«41» height=«20» src=«ref-1_1651711387-144.coolpic» v:shapes="_x0000_i1191">

<img width=«42» height=«21» src=«ref-1_1651711531-147.coolpic» v:shapes="_x0000_i1192">











<img width=«46» height=«94» src=«ref-1_1651715656-260.coolpic» v:shapes="_x0000_s1030">х1









<img width=«22» height=«23» src=«ref-1_1651711786-104.coolpic» v:shapes="_x0000_i1193">

х1



1

1



<img width=«22» height=«23» src=«ref-1_1651711786-104.coolpic» v:shapes="_x0000_i1194">









<img width=«64» height=«23» src=«ref-1_1651716124-159.coolpic» v:shapes="_x0000_s1031">х1

1

1





х3

х1

1

1

1

1

х3









<img width=«55» height=«46» src=«ref-1_1651716283-183.coolpic» v:shapes="_x0000_s1032"><img width=«19» height=«23» src=«ref-1_1651711678-108.coolpic» v:shapes="_x0000_i1195">



1

1



х3

<img width=«55» height=«46» src=«ref-1_1651716283-183.coolpic» v:shapes="_x0000_s1033"><img width=«19» height=«23» src=«ref-1_1651711678-108.coolpic» v:shapes="_x0000_i1196">

1

1

1

1

х3









<img width=«19» height=«23» src=«ref-1_1651711678-108.coolpic» v:shapes="_x0000_i1197">



1

1



<img width=«22» height=«23» src=«ref-1_1651711786-104.coolpic» v:shapes="_x0000_i1198">

<img width=«19» height=«23» src=«ref-1_1651711678-108.coolpic» v:shapes="_x0000_i1199">



1

1



<img width=«22» height=«23» src=«ref-1_1651711786-104.coolpic» v:shapes="_x0000_i1200">











<img width=«23» height=«23» src=«ref-1_1651712910-106.coolpic» v:shapes="_x0000_i1201">

х4

х4

<img width=«23» height=«23» src=«ref-1_1651712910-106.coolpic» v:shapes="_x0000_i1202">





<img width=«23» height=«23» src=«ref-1_1651712910-106.coolpic» v:shapes="_x0000_i1203">

х4

х4

<img width=«23» height=«23» src=«ref-1_1651712910-106.coolpic» v:shapes="_x0000_i1204">











































f1=<img width=«57» height=«23» src=«ref-1_1651689485-160.coolpic» v:shapes="_x0000_i1205">v<img width=«39» height=«25» src=«ref-1_1651703925-141.coolpic» v:shapes="_x0000_i1206">    f2= X4 vX3


    продолжение
--PAGE_BREAK--7.4 Карты Карно


Иногда удобно пользоваться несколько другим представлением диаграмм с цифровым кодом. Это карты Карно. Примеры карт Карно приведены на рисунке 2. По граням карты проставляются двоичные коды — коды Грея, что дает возможность легко проставлять значения функции и находить результат. Правила минимизации с применение карт Карно такие же, как и для диаграмм Вейча.

<img width=«48» height=«42» src=«ref-1_1651718014-158.coolpic» v:shapes="_x0000_s1034"> <img width=«58» height=«44» src=«ref-1_1651718172-170.coolpic» v:shapes="_x0000_s1035">


х2х3

х1

00

01

11

10



х3х4

х1х2

00

01

11

10





000

001

011

010



00

0000

0001

0011

0010



1

100

101

111

110



01

0100

0101

0111

0110















11

1100

1101

1111

1110















10

1000

1001

1011

1010





а)















б)





Рисунок 2- Карты Карно:

а) функции 3-х переменных;

б) функции 4-х переменных.





8.Особенности минимизации булевых функций большим числом переменных


Рассмотрим некоторые особенности работы с картами Карно для большого числа переменных. При числе переменных, равном или больше пяти, отобразить графически функцию в виде единой плоской карты невозможно. В таких случаях строят комбинированную карту, состоящую из совокупности более простых базовых карт, например карт для функции 4-х переменных. Процедура минимизации в этом случае состоит в том, что сначала находят минимальные формы внутри базовых карт, а затем, расширяя понятия соседних клеток, находят минимальные накрытия для совокупности карт. Соседними клетками являются клетки, совпадающие при наложении базовых карт друг на друга. Примеры карт Карно для булевых функций 5-ти и 6-ти переменных представлены на рис. 3 и 4. соответственно.
<img width=«52» height=«42» src=«ref-1_1651718342-160.coolpic» v:shapes="_x0000_s1036">Рисунок 3-Карта Карно для булевой функции 5-ти переменных

<img width=«52» height=«43» src=«ref-1_1651718502-162.coolpic» v:shapes="_x0000_s1037">х3х4

х1х2

00

01

11

10

00

01

11

10



 
00



















 
01



















 
11



















 
10



















 




х5=0







х5=1





Рисунок 4- Карта Карно для булевой функции шести переменных

х3х4

х1х2

00

01

11

10

00

01

11

10

00

01

11

10

00

01

11

10



00



































01



































<img width=«3» height=«2» src=«ref-1_1651718664-73.coolpic» v:shapes="_x0000_s1038">11



































10







(1)







(2)







(3)







(4)



<img width=«64» height=«24» src=«ref-1_1651718737-137.coolpic» v:shapes="_x0000_s1039">х5х6



00







01







11







10










По рисунку 4 можно сделать вывод, что соседними являются для 1-й базовой карты — 2-я и 4-я; для 2-й — 1-я и 3-я; для 3-й 2-я и 4-я; для 4-й — 1-я и 3-я.

При увеличении количества переменных на одну, площадь карты увеличивается в два раза — к ней пририсовывается еще такая же карта. При этом новая переменная равняется 1 на новой карте, и 0 на той, которая была ранее.





    продолжение
--PAGE_BREAK--