Полнота и замкнутость функций k-значной логики

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

Примерами полных систем является:

2. B= .

3. B= .

4. B= .

5. B= ,где .

Функция называется фуннцией Вебба представляет собой аналог функции Шеффера.

Пусть M – произвольное подмножество функции из . З амыканием M называется множество [M] всех функций из , представленных в виде формул через функции множества M`

Класс M называется (функционально) замкнутым, если замыкание [M]=M.

Таким образом, в терминах замыкания можно определить полноту системы функций, а именно B является полной системой если замыкание [B]= .

Справедлива теорема о функциональной полноте - теорема Кузнецова А.В.:

Можно построить систему замкнутых классов в - M₁, M₂,…,M_s, каждый из которых не содержит целиком ни одного из остальных классов и такую, что подсистема функций из полна тогда и только тогда, когда она целиком не содержится ни в одном из классов M₁, M₂,…,M_s. Это аналог теоремы Поста.

Теорема Кузнецова доказывает, что возможно выразить, условие полноты системы B в терминах принадлежности ее к специальным классам M₁, M₂,…,M_s, однако практическое построение классов даже при небольших k связано с трудоемкими вычислениями. Поэтому возникает вопрос о поиске других более эффективных критериев полноты. Эта цель достигается за счет введения ограничений, т.е. за счет знания дополнительной информации о системе B.

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

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

Пусть система B функций из , где k ³ 3, содержит все функции одной переменной, принимающие не более k -1 значений. Тогда для полноты системы B необходимо и достаточно, чтобы B содержало существенную функцию , принимающую все k значений.

Следствие (критерий Слупецкого):

Пусть система B функций из , где к ³ 3, содержит все функции одной переменной. Тогда для полноты системы B необходимо и достаточно, чтобы B содержало существенную функцию , принимающую все k значений.

Непосредственное использование теоремы и ее следствия не всегда удобно, так как для этого необходимо установить наличие в B всех функций одной переменной, принимающих не более k -1 значения, т.е. функций. С ростом k громоздкость вычислений возрастает. Поэтому это требование целесообразно заменить требованием, в котором система функций B порождало бы множество функций одной переменной.

Известно, что функции из B могут быть получены из конкретных систем функций одной переменной.

Теорема 1 (Пикара).

Все функции одной переменной из могут быть порождены тремя функциями:

1. ,

2. ,

3. .

Теорема 2

Все функции одной переменной из могут быть порождены k функциями

и функцией .

Теорема 3 (Мартина).

Функция из при к ³ 3 является функция Шеффера, тогда и только тогда, когда порождает все функции одной переменной принимающие не более k -1 значений.