Наборы переменных при табличном задании функций всегда перечисляются в стандартном лексикографическом порядке. В целях экономии объема записи не будем их явно указывать, ограничившись указаниями лишь соответствующих значений функции, расположив сами значения по горизонтали - краткая табличная форма.
Используя геометрическую модель и аналитические методы, построить:
сокращенную ДНФ;
ДНФ Квайна (при наличии непустого ядра у функции);
все тупиковые ДНФ;
выделить из тупиковых ДНФ все минимальные ДНФ для функции, заданной в краткой табличной форме):
20. f(x1, x2 , x3 , x4) = (1001101010111001)
Решение
1) Строим таблицу истинности заданной функции.
x4
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
x3
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x2
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
f 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1
Строим 4-мерный единичный куб и помечаем в нём единичные вершины.
285820223214328578346576263347486124279511172656576262199974165223702569444170036316470232245794164702326304373443371119503716466552157195224823311950372761615608965102138115559842152015206121033470851358902152349155635233470851651635386016511468103347720114617515506702534285
В 4-х мерном кубе (синим кружком) помечены единичные вершины функции. При этом, вершины (0000, 0010,1100,1000) образуют грань куба (куб ограничен синими ребрами), а остальные пары вершин образуют ребра куба (выделены красным цветом), а именно, ребра образуют пары вершин (0100,0110), (0011,1011), (1000,1010),(1010,1011), (1011,1111).
Таким образом, имеем сокращенную ДНФ:
fx1,x2,x3,x4=x3x4⋁x1x2x4⋁x1x2x4⋁
⋁x2x3x4⋁x1x2x3⋁x1x3x4.
Найдем теперь сокращенную ДНФ методом Блейка.
Метод Блейка построения сокращенной ДНФ состоит в многократном использовании следующего соотношения (операция обобщенного склеивания):
Ax⋁Bx=Ax⋁Bx⋁AB.
Этот метод применяется к произвольной ДНФ функции
.
Получим совершенную ДНФ. Для этого строим полную таблицу истинности для заданной функции.
fx1,x2,x3,x4=x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4⋁
⋁x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4.
Теперь используем к построенной СДНФ метод Блейка.
x1x2x3x4⋁x1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x2x3x4;*
x1x2x3x4⋁x1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x1x2x4;*
x1x2x3x4⋁x1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x1x3x4;*
x1x2x3x4⋁x1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x1x2x3;*
x1x2x3x4⋁x1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x1x2x4;*
x1x2x3x4⋁x1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x1x3x4;
x1x2x3x4⋁x1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x2x3x4;
x1x2x3x4⋁x1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x1x3x4;
x1x2x3x4⋁x1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x2x3x4;
Все конституенты поучаствовали в операции обобщенного склеивания.
Продолжаем.
x1x3x4⋁x1x3x4=x1x3x4⋁x1x3x4⋁x3x4;*
x2x3x4⋁x2x3x4=x2x3x4⋁x2x3x4⋁x3x4;
Все возможные операции обобщенного склеивания выполнены