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

Необходимость. От противного. Пусть и .

Введем обозначение: i – один из индексов 0, 1, *, ≤, L .

Тогда , но по таблице

Таблица принадлежности некоторых булевых функций рассмотренным замкнутым классам:

	+	-	-	+	+
	-	+	-	+	+
	-	-	+	-	+
	+	+	-	+	-

Таким образом, рассмотренные классы , , , , попарно различны, не пусты и не совпадают с ().

Функции двух переменных z = f(x,y).

Различных функций двух переменных существует уже шестнадцать. Эти функции, их названия и обозначения приведены в табл. 4.1. Число этих функций равно 2⁴ = 16. Перенумеруем и расположим их тоже в естественном порядке.

 

Таблица 4.1 х Название функции Обозначение Класс y T0 T1 S M L f0(x,y) Константа “0” +     + + f1(x,y) Конъюнкция x ∧ y, xy + +   +   f2(x,y) Операция запрета по y x +         f3(x,y) Переменная x x + + + + + f4(x,y) Операция запрета по x y +         f5(x,y) Переменная y y + + + + + f6(x,y) Сумма по модулю 2 x ⊕ y +       + f7(x,y) Дизъюнкция x ∨ y + +   +   f8(x,y) Операция Пирса x ↓ y           f9(x,y) Равнозначность x ∼ y   +     + f10(x,y) Инверсия y       +   + f11(x,y) Импликация от y к x y → x   +       f12(x,y) Инверсия x       +   + f13(x,y) Импликация от x к y x → y   +       f14(x,y) Операция Шеффера x / y           f15(x,y) Константа “1”   +   + +

 

Таблица принадлежности некоторых булевых функций рассмотренным замкнутым классам:

	K0	K1	S	M	L
	+	-	-	+	+
	-	+	-	+	+
	-	-	+	-	+
	+	+	-	+	-

Таким образом, рассмотренные классы K₀, K₁, S, M, L попарно различны, не пусты и не совпадают с P₂.