Суперпозиция и формулы алгебры логики
Определение. Суперпозицией функций f1, … , fm называется функция f,
полученная с помощью подстановок этих функций друг в друга и переименования переменных.
Пример. Пусть даны функции f1( x1, x2 ) = ( 0, 1, 1, 0 ) и f2( x1, x2 ) = (1, 0, 1, 0).
Тогда функция f( x2, x3, x4 ) = f1[ x2, f2(x3, x4) ] будет суперпозицией функций f1 и f2.
Табличное задание функций f1 и f2 представлено табл. 1.7. С помощью данной таблицы найдем табличное задание искомой функции f( x2, x3, x4 ), которое представле-но в табл. 1.8.
Таблица 1.7
|
x1 |
х2 |
f1 |
f2 |
|
0 |
0 |
0 |
1 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
0 |
Таблица 1.8
|
x2 |
х3 |
х4 |
f2(x3, x4) |
f=f1[x2, f2(x3, x4)] |
|
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
1 |
Для построения табл. 1.8 вначале, пользуясь табл. 1.7, строим функцию f2(x3, x4) для всех строк табл. 1.8. При этом роль переменных х1, х2 табл. 1.7 играют переменные х3, х4 соответственно.
Затем, по табл. 1.7 для f1, строим функцию f1[ x2, f2(x3, x4) ].При этом роль переменных х1, х2 табл. 1.7 играют переменная х2 и f2( x3,x4 ) соответственно.
Полученная функция и будет искомой. Ее векторный вид:
предыдущаяследующая