Теорема Поста–Яблонского

Смысл теоремы сводится к следующему.

Набор функций двух переменных, является функционально полной системой, если хотя бы одна из его функций:

Не сохраняет «0»;

Не сохраняет «1» ;

Не самодвойственна;

Не монотонна;

Не линейна.

Эти свойства логических функций разбивают их на классы сохраняющих и не сохраняющих 0; сохраняющих и не сохраняющих 1; самодвойственных и не самодвойственных и т.д. При этом суперпозиция логических функций одного класса дает функцию того же класса.

Свойства логических функций двух переменных, разбивающие их на классы, приведены в табл. 16, где символом «+» отмечено наличие свойства, указанного в шапке таблицы.

Таблица 16
Свойства функций двух переменных, разбивающие их на классы
Функция	Сохранение «0»	Сохранение «1»	Само–двойственная	Монотонная	Линейная
	+			+	+
	+
			+		+
	+
			+		+
	+				+
	+	+		+
		+			+
	+	+	+	+	+
		+
	+	+	+	+	+
		+
	+	+		+
		+		+	+

Пример 1: Применим теорему Поста–Яблонского для доказательства полноты системы { }.

Функция (НЕ) не сохраняет 0 и 1 и не монотонна.

Функция (ИЛИ) не самодвойственна и не линейна.

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