Суперпозиция функций алгебры логики

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

Определение.

Рассмотрим конечную систему функций алгебры логики

.

Функция называется элементарной суперпозицией(суперпозицией ранга 1) и обозначается ,если она может быть получена одним из следующих способов.

Способ 1.

Из некоторой функции , ,переименованием некоторой её переменной.

Способ 2.

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

Если описан класс функций, являющихся суперпозициями ранга r функций из системы F, то класс функций состоит из элементарных суперпозиций функций из , т.е. .

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

Полные системы функций. Понятие базиса.

Определения.

Система функций F называется полной, если всякая функция алгебры логики представила посредством суперпозиций функций из системы F.

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

Утверждение 1.

Система функций является полной. Это следует из Теоремы о разложении функций алгебры логики от n переменных по k=n переменным.

Утверждение 2.

Системы функций являются полными, так как и .

Утверждение 3.

Системы функций - штрих Шиффера и стрелка Пирса, являются полными, так как .

Утверждение 4.

Система функций является полной, так как .

Замечание.

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

Алгебра Жегалкина. Полином Жегалкина. Теорема Жегалкина. Линейные функции.

Алгебра над множеством логических функций с двумя бинарными операциями конъюнкции &и сложения по модулю 2 называется алгеброй Жегалкина.

В алгебре Жегалкина, очевидно, имеют место следующие соотношения:

x y=y x

x(y z)=xy xz

x x=0

x 0=x

x 1=

xVy=xy x y

Если в произвольной формуле, выраженной в сигнатуре алгебры Жегалкина, раскрыть скобки и провести возможные сокращения, то получится формула, имеющая вид суммы по модулю 2 элементарных конъюнкций, в которых не содержатся отрицаний. Такая формула называется полиномом Жегалкина.

Исходя из оценки числа различных функций алгебры логики и числа различных полиномов Жегалкина, следует

Теорема Жегалкина.

Для всякой логической функции существует соответствующий ей полином Жегалкина и притом только один.

Функция алгебры логики, для которой полином Жегалкина имеет вид (здесь знак суммирования означает суммирование по модулю 2, а параметры , называется линейной.

Очевидно, что все функции от одной переменной линейны.

Линейными являются, например, функции x yи x y 1=x~y.

Для построения полинома Жегалкина можно воспользоваться следующими двумя схемами:

Схема 1.

Перейти в сигнатуру алгебры Жегалкина (это можно сделать всегда, так как система функций {x&y, x y, 1} ,как это было показано ранее, полна), раскрыть скобки и провести возможные сокращения.

Схема 2.

Воспользоваться приёмом, который называется методом неопределённых коэффициентов.

Этот метод применим лишь тогда, когда функция от n переменных задана своей таблицей истинности. Решается система линейных уравнений с ограничениями, которые задаются через значения функции на двоичных n мерных наборах, и неизвестными - коэффициентами полинома Жегалкина.