Математическая логика и теория алгоритмов программирования.

Функция f1(x,y,z) = (0 0 1 1 1 1 0 1).
Сохранение нуля. Функция f1 сохраняет 0, ибо f1(0,0,0) = 0.
Сохранение единицы. Функция f1 сохраняет 1, ибо f1(1,1,1) = 1.
Функция не самодвойственна, ибо f1(0,1,0) = f1(1,0,1) = 1.
Линейность. Вычислим полином Жегалкина.
f_1 (x,y,z)=СДНФ=x ̅yz ̅∪x ̅yz∪xy ̅z ̅∪xy ̅z∪xyz=
= (x + 1) y (z + 1) + (x + 1) yz + x (y + 1) (z + 1) + x (y + 1) z + xyz = = (xyz + xy + yz + y) + (xyz + yz) + (xyz + xy + xz + x) + (xyz + xz) +
+ xyz = xyz + x + y.
Функция f1 нелинейна.
Монотонность. Строим сокращенную ДНФ функции f1 с помощью
СКНФ для функции f1. Сокр. ДНФ = x ̅y∪xz∪xyz ̅.
Сокр. ДНФ содержит отрицания переменных, поэтому функция не
монотонна.
Функция f2(x,y) = (1 1 1 1).
Сохранение нуля. Функция f2 не сохраняет 0, ибо f2(0,0) = 1.
Сохранение единицы. Функция f2 сохраняет 1, ибо f2(1,1) = 1.
Функция не самодвойственна, ибо f2(0,0) = f2(1,1) = 1.
Линейность. Функция линейна.
Функция монотонна.
Функция f3(x) = (0 0).
Сохранение нуля. Функция f3 сохраняет 0, ибо f3(0) = 0.
Сохранение единицы. Функция f3 не сохраняет 1, ибо f3(1) = 0.
Функция не самодвойственна, ибо f3(0) = f3(1) = 0.
Линейность. Функция линейна.
Функция монотонна.
Результаты вычислений заносим в следующую таблицу.
]T0 ]T1 ]S ]L ]M
f1 + + +
f2 + +
f3 + + +

По теореме Поста система функций F(f1,f2,f3) функционально полна
поскольку в каждом столбце находится хотя бы один плюс.

Задача 13. Реализовать функции из задач 5 и 6 с помощью мультиплек-сора (в базисе &, ∨, ], MUX(2), MUX(3)).
5.18 1111001000111011
6.18 (0,1,3,5,7,9,10,11,12,13)
Решение
Реализация функции из задачи 5 приведена на рис. 1.

Рис. 1
Реализация функции из задачи 6 приведена на рис. 2.

Рис. 2
Задача 14. Построить простую непересекающуюся декомпозицию
функции f(x1,x2,x3,x4,x5) = f(x1,x2,x3), f2(x4,x5) и реализовать ее с помо-
щью мультиплексора. Каждая функция задана множеством М1 деся-
тичных эквивалентов двоичных наборов, на которых функция прини-
мает значение 1.
14.18 (7,8,9,10,20,21,22,23,31)