30. Теорема Поста о полноте системы булевых функций, алгоритм проверки системы на полноту, базис.

Определение. Функцияотnаргументовназывается булевой функцией (или функцией алгебры логики), если каждому наборуона ставит в соответствие число.

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

Определение.Замыканием системыFбулевых функций называется множество всех функций, представимых в виде формул через функции множестваF. ЗамыканиеFбудем обозначать через [F].

Определение.СистемаFбулевых функций называется полной системой, если [F] = Р₂, т.е. любую булеву функцию можно задать формулой через функции системыF.

Теорема.Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из пяти классов Т₀, Т₁,S,MиL.

Пример.Система, состоящая из одной только функции штрих Шеффера, является полной, поскольку она не принадлежит ни одному из пяти классов Т₀, Т₁,S,MиL. В то же время система всех булевых функций от одного аргумента {0,1,x,} неполна, так как все эти функции линейны. Из теоремы о полноте следует, что любой неполный замкнутый класс целиком содержится хотя бы в одном из пяти классов Т₀, Т₁,S,MиL, так как если бы некоторый неполный замкнутый класс не лежал целиком ни в одном из классов Т₀, Т₁,S,MиL, то он образовывал бы полную систему. Таким образом, классы Т₀, Т₁,S,MиLв некотором смысле являются максимальными во множестве Р₂неполными замкнутыми классами.

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

Определение.Система булевых функцийназывается базисом класса Р₂, если эта система полна, а после удаления из неё любой функции оставшаяся система будет неполна.