Тема 3.5 Полнота множества функций.

Любую булеву функцию можно выразить в виде формулы через элементарные функции: отрицание, конъюнкцию, дизъюнкцию, двоичное сложение и константу 0 или 1.

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

Система булевых функций {f1, f2, …, fm} называется полной, если любая булева функция может быть выражена через функции этой системы с помощью составления из них сложных функций..

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

Достаточное условие полноты системы.

Пусть система функций {f1, f2, …, fm} (I) полная и любая из функций этой системы может быть выражена через функции g1, g2, …, gl , тогда система { g1, g2, …, gl}(II) тоже полная.

Полноту системы можно доказать , опираясь на то, что любая булева функция представима в виде полинома, или доказав с помощью достаточного условия.