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

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

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

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

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

Лемма.Пусть имеются две системы функцийFиG, причем системаFполна, и каждая функция из этой системы выражается в виде формулы через функции системыG. ТогдаG– полная система.

Пример.Рассмотрим систему функцийG = . Каждая функция полной системыF = представима своим полиномом Жегалкина, т.е. формулой через функции системыG:. Следовательно,G= – полная система.