Переход от табличной формы задания булевых функций к аналитическим

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

Для получения СДНФ на основе таблицы истинности необходимо:

1) Каждый из входных наборов, на которых булева функция принимает значения 1, представить в виде элементарного произведения (конъюнкции), причем если переменная равна 0, то она входит в конъюнкцию с инверсией, а если 1 - то без инверсии.

2) Полученные элементарные конъюнкции объединяются знаками дизъюнкции.

Для получения СКНФ на основе таблицы истинности необходимо:

1) Каждый из входных наборов, на которых булева функция принимает значения 0, представить в виде элементарной логической суммы (дизъюнкции), причем если переменная равна 1, то она входит в дизъюнкцию с инверсией, а если 0 - то без инверсии.

2) Полученные элементарные дизъюнкции объединяются знаками конъюнкции.

В качестве примера рассмотрим булеву функцию трех переменных,   f (1,3,5,6,7)=1.   Ниже приведены таблица истинности и полученные на ее основе СДНФ и СКНФ.

x1 x2 x3	f (x1, x2, x3)
0   0   0	0
0   0   1	1
0   1   0	0
0   1   1	1
1   0   0	0
1   0   1	1
1   1   0	1
1   1   1	1

СДНФ  

f = 12x3 v1x2x3 v x12x3 v x1x23 v x1x2x3 СКНФ

f = (x1 v x2 v x3 )· ( x1 v 2 v x3 )· ( 1 v x2 v x3 )

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

ДНФ   f = x1x2 v x3;

КНФ   f = (x1 v x3)· (x2 v x3).

Минимизация логических функций с помощью таблицы Карно

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

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

Пример:

Таблицы истинности для функции "И":

0	0	0
0	1	0
1	0	0
1	1	1

и соответствующая ей Таблица Карно:

	0	1
0	0	0
1	0	1

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

0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1	0
1	0	1	0	1
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

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

Для ячейки, расположенной правее, следует записать

Когда наконец будет составлена логическая сумма всех произведений, помимо других в ней встретится и такой фрагмент:

Он упрощается следующим образом:

Отсюда следует общее правило упрощения логических функций для таблиц Карно:

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

Замечание: Количество единиц в контуре должно быть максимальным, а количество контуров минимальным.

Таким образом, в этом примере логическое произведение для группы B, состоящие из двух ячеек, равно

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

Для столбца D, стоящего из четырех ячеек логическая функция будет

Для контура С

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

Для дизъюнктивной нормальной формы сразу найдем максимально упрощенный результат:

Логические блоки

Таблицы истинности для функции "И":

0	0	0
0	1	0
1	0	0
1	1	1

Таблицы истинности для функции "ИЛИ":

0	0	0
0	1	1
1	0	1
1	1	1

Система булевских функций S называется функционально полной, если любая булевская функция f(X1, X2,..., Xn) может быть построена путем суперпозиции функций Х1, Х2,..., Хn и функций системы S, взятых любое конечное число раз.

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

1) В таблице истинности выделяют строки, в которых выходная переменная Yимеет значение 1;

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

3) Наконец, записывая логическую сумму всех найденных произведений, получают искомую функцию.

Рассмотрим на примере.

Таблица истинности

Строка
1	0	0	0	0
2	0	0	1	0
3	0	1	0	1
4	0	1	1	0
5	1	0	0	1
6	1	0	1	0
7	1	1	0	1
8	1	1	1	0

В строчках 3,5,7 переменная . Прежде всего, следует составить конъюнкцию для этих строк:

Искомая функция записывается в виде логической суммы произведений:

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

Произведем аналитическую минимизацию:

Произведем минимизацию с помощью карт Карно:

x1x2	00	01	11	10
x3
0	0	1	1	1
1	0	0	0	0

, результат аналогичный аналитическому упрощению.

Представим полученную минимизированную функцию в виде логических блоков: