4.16. Теорема Поста

Ответ на вопрос о полноте произвольной системы F булевых функций дает теорема Поста. Для ее формулировки вводятся определения классов Поста.

1) P₀ – класс булевых функций, сохраняющих 0, т.е. функций ƒ (x₁, x₂,…,x_n), для которых ƒ (0,….0) = 0.

2) P₁ – класс булевых функций, сохраняющих единицу, т.е. ƒ (x₁, x₂,…,x_n), для которых ƒ (1,…,1) = 1

3) S – класс самодвойственных функций

Функция ƒ⁺(x₁,x₂,…,x_n) называется двойственной по отношению к функции ƒ(x₁,x₂,…,x_n), если , т.е. функция, получающаяся из исходной путем замены значения всех переменных и значений функций на противоположные. В таблице истинности заменяется 0 на 1 и 1 на 0.

Например:

(xy)⁺ = xy; (xy)⁺ = x; (x̅)⁺ = x̅.

Функция ƒ (x₁, x₂,…,x_n) называется самодвойственной, если ƒ⁺ (x₁, x₂,…,x_n) = ƒ (x₁, x₂,…,x_n).

4) М – класс монотонных функций.

Булева функция ƒ (x₁, x₂,…,x_n) называется монотонной, если для любых двух наборов (α₁, α₂,…,α_n) и (β₁, β₂,…,β_n) у которых α_i ≤ β_i для всех i = 1,…,n следует, что ƒ(α₁, α₂,…,α_n) ≤ ƒ (β₁, β₂,…,β_n).

5) L – класс линейных функций, т.е. линейных полиномов Жегалкина.

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

Теорема Поста. Для того, чтобы система функций F была полной необходимо и достаточно, чтобы она полностью не содержалась ни в одном из пяти замкнутых классов P₀, P₁, S, M, L.

Пример ƒ(x,y) = x | y.

Определим, к каким классам Поста относится x | y. Т.к. ƒ(0,0) = 1, а ƒ(1,1) = 0, то и . Т.к. , то . Т.к. ƒ(0,0)> ƒ(1,1), то . Полином Жегалкина для данной функции имеет вид 1 xy, т.е. эта функция нелинейна, следовательно .

Таким образом, имеем:

Таблица 14

ФУНКЦИЯ	КЛАССЫ
	P0	P1	S	M	L
x|y	Нет	Нет	Нет	Нет	Нет

В силу теоремы Поста функция x|y образует полную систему, т.е. с помощью штриха Шеффера можно получить любую булеву функцию.

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

Каждый базис содержит не более четырех булевых функций.

Примеры:

Следующие системы булевых функций являются базисами:

1) {, -}; {, -}; {→, -}; {|}; {↓}; {↔, , 0}; {, , ↔}.

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

4.17. Нечеткая логика

Нечетким высказыванием называется повествовательное предложение А, степень четности которого принимает значение на отрезке [0.1].

Если то, о чем говорится в предложении не определено, то это предложение называется высказывательной функцией или предикатом. Аргументом предиката являются предметные переменные. Нечеткой предметной переменной называется переменная, степень истинности которой принадлежит отрезку [0.1].

Как правило, нечеткой предметной переменной является лингвистическая переменная, значениями которой являются слова и словосочетания естественного языка. Лингвистическая переменная служит для качественного описания явления, факта или события. Множество лингвистических переменных называются терм-множеством и обозначаются T(x).

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

Степень истинности сложного высказывания определяется по следующим правилам:

В логике нечетких высказываний операция импликации, отличается от классической. Чаще всего она используется в виде: «Если А, то В, иначе С». Такое высказывание определяется через нечеткое отношение на декартовом произведении множеств, т.е. Истинность такого высказывания определяется по формуле.

В частном случае, когда