Задание 2.1

2.1.1. Доопределить функции f(x,y,z), g(x,y,z), h(x,y,z) так, чтобы .

Если построение какой-либо функции невозможно, докажите это.

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

Доопределим функции f(x,y,z), g(x,y,z), h(x,y,z) так чтобы f(x,y,z), была монотонная, g(x,y,z)- линейная, а h(x,y,z) - самодвойственная.

Составим таблицу состояний

Функция называется линейной, если она может быть задана линейным многочленом Жегалкина вида где при i=0, 1, 2,..., n.

Выпишем, что нам известно про коэффициенты

=0

Итого 4 условия:

С учетом условия

Получили противоречие и

Вывод: g(x,y,z) невозможно доопределить, так чтобы она была линейной.

Функция называется самодвойственной, если для любого набора аргументов имеет место равенство:

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

Доопределим h= (11 1 0 1 0 0 0) –самодвойственная.

Задание 2.2.

2.2.1. Можно ли из функции f(x,y,z) с помощью суперпозиций получить g(x,y,z)?

Из таблицы, очевидно, что не сохраняет 0 и 1, не монотонная, и не самодвойственная.

Составим многочлен Жегалкина

Последовательно подставляя значения переменных и f из таблицы, получаем:

дальше можно не считать, функция не линейна, но досчитаем.

=0

Следовательно, функция представляется многочленом Жегалкина

Итак,

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

То есть из f при помощи суперпозиции можно получить любую булеву функцию.