 |
Переход от табличной формы задания булевых функций к аналитическим
|
|
|
|
Особый интерес представляет переход от табличных формы представления булевых функций к аналитическим. Для получения СДНФ и СКНФ исходя из таблицы истинности, можно сформулировать следующие правила.
Для получения СДНФ на основе таблицы истинности необходимо:
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 1 | |
| 0 1 0 | |
| 0 1 1 | |
| 1 0 0 | |
| 1 0 1 | |
| 1 1 0 | |
| 1 1 1 |
СДНФ
f = 
1 2x3 v 1x2x3 v x1 2x3 v x1x2 3 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).
Инверсные функции
Так как в булевой алгебре функции принимают только два значения 0 и 1, то существует особый класс функций, являющихся инверсными по отношению к рассматриваемым функциям, т.е. на тех наборах, где данная функция принимает значение 0 (1), инверсная функция принимает значение 1 (0) соответственно.
|
|
|
На основании закона Де-Моргана можно сформулировать правило получения инверсной функции.
Для получения аналитического выражения инверсной функции необходимо в исходной функции все переменные заменить на инверсные им, все знаки дизъюнкции заменить на знаки конъюнкции и наоборот.
Например, для ДНФ f = x1x2 v x3, 
= ( 1 v 2)· 3; Полученную таким образом инверсную функцию называют обратной КНФ.
Для КНФ f = (x1 v x3)· (x2 v x3), = 1 3 v 2 3; Полученную таким образом инверсную функцию называют обратной ДНФ.
Минимизация логических функций.
Используя законы булевой алгебры, можно преобразовывать исходные выражения в более простые (минимизировать их). По упрощенным выражениям можно построить техническое устройство, имеющее минимальные аппаратные затраты.
Минимизация производится с помощью применения законов склеивания и поглощения.
Пример.
Найти минимальную ДНФ функции Y=f (x1, x2, x3); f (0,2,3,4,5,7)=1.
Решение.
Построим таблицу истинности функции Y.
| x1 x2 x3 | f (x1, x2, x3) |
| 0 0 0 | |
| 0 0 1 | |
| 0 1 0 | |
| 0 1 1 | |
| 1 0 0 | |
| 1 0 1 | |
| 1 1 0 | |
| 1 1 1 |
По данным таблицы запишем аналитическое выражение:
Y= 1 2 3 v 1x2 3 v 1x2x3 v x1 2 3 v x1 2x3 v x1x2x3
Применим склеивание следующим образом: Fx v F = F
Получим:
Y= 1x2 v x2x3 v x1x3 v x1 2 v 2 3 v 1 3
Данная ДФ является избыточной, так как отдельные конъюнкции могут быть лишними, т.е. их составные части могут включаться в другие конъюнкции. У данной функции существует пять безызбыточных ДФ, из которых только две являются минимальными:
Y1= 1x2 v x1x3 v 2x3;
Y2= 1x2 v x2x3 v x1 2 v 1 3;
Y3= 1x2 v x1x3 v x1 2 v 1 3;
Y4= 1 3 v x2x3 v x1 2;
Y5= 1 3 v 1x2 v x1x3 v x1 2.
Их приведенных зависимостей видно, что только функции Y1 и Y4 являются минимальными формами функций, так как они содержат наименьшее число конъюнкций и имеют минимальный ранг этих конъюнкций.
Индивидуальное задание.
Для функций, заданных по Вашему варианту, построить таблицы истинности, аналитическое выражение в КФ и ДФ и попытаться его минимизировать. Записать инверсную функцию.
|
|
|
Варианты:
1) f (1,2,3,4) = 1; f (2,4,5,6,7) = 1; f (1,2,3,8,13,14,15) = 1;
2) f (1,2,4,5) = 1; f (3,4,5,6,7) = 1; f (1,2,4,8,12,14,15) = 1;
3) f (1,2,5,6) = 1; f (1,3,5,6,7) = 1; f (1,2,5,7,13,14,15) = 1;
4) f (1,2,6,7) = 1; f (1,3,4,6,7) = 1; f (1,2,4,9,11,12,15) = 1;
5) f (0,2,4,6) = 1; f (1,2,4,5,7) = 1; f (0,3,5,10,12,13,14) = 1;
6) f (0,3,5,6) = 1; f (0,1,2,6,7) = 1; f (1,2,3,5,7,10,14) = 1;
7) f (1,2,5,7) = 1; f (0,3,4,5,7) = 1; f (1,2,4,5,8,12,13) = 1;
8) f (0,4,5,7) = 1; f (1,2,3,6,7) = 1; f (4,5,6,8,9,11,12) = 1;
9) f (0,1,2,3) = 1; f (3,4,5,6,7) = 1; f (8,9,11,12,13,14,15) = 1;
10) f (2,3,4,5) = 1; f (0,1,3,6,7) = 1; f (7,10,11,12,13,14,15) = 1;
11) f (3,4,5,6) = 1; f (0,1,2,5,7) = 1; f (0,4,8,12,13,14,15) = 1;
12) f (1,2,3,5) = 1; f (0,3,4,6,7) = 1; f (2,4,7,8,9,12,15) = 1;
13) f (1,2,3,6) = 1; f (0,2,4,5,7) = 1; f (3,6,9,12,13,14,15) = 1;
14) f (1,2,3,7) = 1; f (0,1,4,6,7) = 1; f (2,4,6,8,11,13,15) = 1;
15) f (1,2,4,6) = 1; f (0,1,4,5,7) = 1; f (0,5,7,10,11,12,13) = 1;
16) f (1,2,4,7) = 1; f (0,2,4,6,7) = 1; f (1,6,9,10,11,12,14) = 1;
17) f (0,1,3,6) = 1; f (1,2,4,5,6) = 1; f (0,2,4,9,11,12,13) = 1;
18) f (0,1,4,5) = 1; f (1,2,3,4,6) = 1; f (0,1,4,5,8,9,12) = 1;
19) f (0,1,3,5) = 1; f (1,2,4,6,7) = 1; f (1,2,4,15,9,10,12) = 1;
20) f (1,5,6,7) = 1; f (0,1,2,3,4) = 1; f (6,7,9,11,12,13,15) = 1;
21) f (1,2,6,7) = 1; f (0,1,3,6,7) = 1; f (1,2,4,8,12,14,15) = 1;
22) f (1,2,5,6) = 1; f (0,3,4,5,7) = 1; f (8,9,11,12,13,14,15) = 1;
23) f (0,1,2,3) = 1; f (1,2,3,6,7) = 1; f (2,4,6,8,11,13,15) = 1;
24) f (3,4,5,6) = 1; f (3,4,5,6,7) = 1; f (1,2,4,8,12,14,15) = 1.
25) f (0,5,6,7) = 1; f (0,1,2,3,4) = 1; f (7,9,11,12,13,15) = 1;
26) f (1,2,6) = 1; f (0,3,6,7) = 1; f (1,2,4,8,14,15) = 1;
27) f (2,5,6) = 1; f (3,4,5,7) = 1; f (8,9,11,12,13,15) = 1;
28) f (1,2,3,6) = 1; f (1,2,4,5,6) = 1; f (1,2,4,9,11,12,15) = 1;
29) f (0,3,5,6) = 1; f (0,1,2,5,7) = 1; f (1,2,4,9,11,12,15) = 1;
30) f (1,2,5,7) = 1; f (3,4,5,6,7) = 1; f (2,4,6,8,11,13,15) = 1;
31) f (1,2,5,6) = 1; f (2,4,5,6,7) = 1; f (8,9,11,12,13,14,15) = 1;
32) f (1,2,4,6) = 1; f (3,4,5,6,7) = 1; f (1,2,4,8,12,14,15) = 1.
Отчет о лабораторной работе представить в печатном виде с необходимыми иллюстрациями.
|
|
|
12 |
