Классы булевых функций Т0, Т1, S

Класс функций, сохраняющих 0

Определение

Функция сохраняет ноль, если

Класс функций, сохраняющих 0:

Пример

x&y

Покажем, что класс замкнут

1. Он содержит тождественную функцию

сохраняет 0.

2. Если єи новые переменные, то очевидно, что є

3. Суперпозиция.

Пусть є исуперпозиция функций, тогда

Класс функций, сохраняющих 1

Определение

Функция сохраняет единицу, если

Класс функций, сохраняющих 1:

Пример

Доказательство замкнутости аналогично

Самодвойственные функции

Определение

Функция fсамодвойственная, если она равна своей двойственной функции.

Пример

и.

Покажем замкнутость класса самодвойственных функций.

1) содержитx, так как x – самодвойственная функция.

2) Пусть єТ* и - новый набор переменных. Тогда поскольку =выполняется для значений переменных, то оно будет выполняться и для.Следовательно, єТ*.

3) Пусть и.

Если выполняется условие , (1)

то выполняется и следующее условие

(2)

= в силу равенства (2) = ,…,. Следовательно,*.

Лемма о несамодвойственной функции

Пусть *, тогда замыкание класса функцийF=(, -)содержит константы 0 и 1.

Доказательство

Так как *, тотакие, что

Так как функция f может принимать только два значения, из этого неравенства следует равенство .

Для удобства предположим, что . Тогда последнее равенство примет вид

; отделяет к-й аргумент от (к+1)-го.

Рассмотрим функцию

, так как получена из функции fпутем переименования аргументов.

Следовательно - одна из констант 0 или 1, а так как , то обе константы принадлежат классуF.