Критерий полноты системы функций алгебры логики.
Опр: Функцией алгебры-логики 
, зависящей от переменных 
, будем называть функцию
Опр: Пусть имеется непустая система функций алгебры-логики B, будем говорить что система B полная, если каждая функция алгебры логики может быть представлена в виде формулы над B.
Примеры полных систем:
-
– множество всех функций алгебры логики. - B –
Теорема: О полноте.
Утверждение: О несамодвойственной функции.
Пусть 
, тогда путём подстановки вместо независимых переменных функции вида 
или 
можно получить из функции 
константу.
Утверждение: О немонотонной функции.
Пусть функция 
, тогда путём подстановки вместо констант и функций вида можно получить из отрицание .
Утверждение: О нелинейной функции.
Пусть функция 
, тогда путём подстановки вместо независимых переменных функций вида 
или 
и констант, а также путём возможного перехода к самой функции можно получить из функции конъюнкцию.
Критерий полноты:
Пусть 
, B – непустая система функций из ,
Тогда B – полная ó B – не содержится целиком ни в одном из следующих классов: 
Замечание:
класс всех булевых функций , сохраняющих константу 0. Т.е. функций для которых выполнено 
.
класс всех булевых функций , сохраняющих константу 1. Т.е. функций для которых выполнено 
.
класс самодвойственных функций, т.е. функций на 
таких, что 
.
М – множество всех монотонных функций. L – класс линейных функций.
Док-во:
(=>) Пусть B – полная система и B содержится в каком-то из перечисленных классов, т.е. 
, но тогда мы получи следующую цепочку включений: 
. Получили противоречие.
(<=) Пусть B – не содержится ни в одном из перечисленных классов, тогда
Эти функции необязательно различны. Покажем, что подмножество 
является полной системой (воспользуемся теоремой о полных системах).
Шаг 1. Получение констант.
Покажем, что константы 0 и 1 могут быть представлены в виде формулы над 
. Рассмотрим функции 
возможны 4-е случая:
1) 
, 
2) , 
3) 
,
4) ,
Введём вспомогательные функции: 
и 
В случае 1) получим:
(т.к. 
),
,
, 
Т.о. отрицание представляется в виде формулы над , но тогда использую функцию 
по утверждению о несамодвойственной фцнкуции, можно получить в виде формулы над какую-нибудь константу 
(0 или 1). Вторая константа 
получается из с помощью уже полученного отрицания, т.е. 
.
В случае 2) получим:
, 
т.к. 
, 
В случае 3) получим:
, 
, 
В случае 4) получим:
, 
, 
Шаг 2. Получение отрицания.
Если отрицание не было получено на первом шаге (случай 3), то представим его в виде формулы над , используя функцию 
и это можно сделать благодаря утверждению о немонотонной функции.
Шаг 3. Получение конъюнкции.
Конъюнкцию можно получить из функции 
по утверждению о нелинейной функции. Т.о. мы получили, что 
представляются в виде формулы над , а т.к. система 
- полная, то по теореме о полных системах мы получили, что и - полная и => 
- полная.
Примеры полных систем функций к-значной логики с доказательством полноты.
Опр: Система функций К -значной логики наз. полной, если замыкание совпадает со всеми 
, т.е:
Теорема: О полных системах.
Пусть 
для которых выполняются условия:
1) 
– полная система;
2) Каждая функция 
Тогда система 
– полная.
Теорема: Пример полной системы к-значной логики.
– система функций, состоящая: 
, тогда эта система полна.
Док-во:
Рассмотрим систему 
– эта система полная. Выразим каждую функцию этой системы через функции системы .
Шаг 1. Получение константы. Рассмотрим функции:
Очевидно, что эти функции 
и рассмотрим функцию:
=> 
. Используя отрицание, получим из константы
k-1 все остальные константы: 
Шаг 2. Получение функций 
.
, рассмотрим функцию 
Если 
, то среди элементов 
есть элемент 
, но тогда => 
, но тогда 
, если 
, то 
и => 
, т.е. 
Шаг 3. Получение функций 
.
Рассмотрим функция 
Если 
, то 
, тогда 
тогда 
Если , то 
, тогда 
тогда 
=>
Шаг 4. Получение произвольной функции от одной переменной.
Рассмотрим произвольную функцию 
Шаг 5. Получение конъюнкции.
На 4-ом этапе мы получили все функции от одной переменной в виде формулы над , в частности отрицание тоже представляется в виде формулы над ,но тогда конъюнкцию можно получить следующим образом: 
=> система полная по теореме о полной системе.