28. Замкнутые классы булевых функций s и м, леммы о несамодвойственной и немонотонной функции.

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

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

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

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

Определение. Набор называетсяпротивоположным по отношению к набору . Тогда из определения самодвойственной функции следует, что на противоположных наборах она принимает противоположные значения. Класс всех самодвойственных функций -S. Количество различных самодвойственных функций от n переменных равно .

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

Лемма.Из любой несамодвойственной функции, подставляя вместо её аргументов функции х и, можно получить тождественную константу 0 или 1.

Лемма.Из любой немонотонной функции, подставляя вместо её аргументов константы 0 и 1 и функцию х, можно получить функцию.

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

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

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

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

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

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

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

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называется предполным классом, если сам он не образует полной системы, но для любой булевой функциисистемаполна.

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