Критерий Поста полноты системы функций в алгебре логики

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

Теорема 2.1.2 (Пост). Система функций {f} полна в P₂тогда и только тогда, когда она не содержится целиком ни в одном из замкнутых предполных классов Т₀,Т₁,S, Mи L.

Доказательство. Необходимость. Пусть {f} полна в P₂([{f}]=P₂). Докажем, что {f} не содержится ни в одном из классов Т₀,Т₁,S, Mи L. Допустим верно обратное и {f} входит полностью в один из этих классов, обозначим его черезК. Но тогда [{f}]ÍКÌP₂ , т.е. имеет место строгое включение [{f}] ÌP₂, что противоречит определению полноты {f}.

Достаточность. Пусть {f} целиком не содержится ни в одном из классов Т₀, Т₁, S, M ,L. Докажем ее полноту. Из условия невхождения следует, что в {f} можно выделить подмножество из пяти функций {f₀, f₁, f_S, f_M, f_L}, таких, что f₀Ï Т₀, f₁Ï Т₁ , f_S Ï S,f_M Ï M,f_L Ï L(функции не обязательно должны быть все различны). Для полноты достаточно доказать, что из этой подсистемы с помощью суперпозиции всегда можно выделить функции {Ø , & }, так как они образуют полную систему в P₂.

Покажем, что из функций f₀, f₁, f_S всегда можно получить константы 0 и 1. Из условий f₀ÏТ₀, f₁Ï Т₁ следует: f₀ (0,... ,0) =1, f₁(1,...,1) = 0. Рассмотрим все возможные варианты значений f₀ и f₁на противоположных наборах и применим к этим функциям дублирующие подстановки вида f(х,х,...,х).

1. f₀(1,...,1) = 1, f₁(0,...,0) = 0. Дублирующие подстановки f₀(х, ... , х) и f₁(х, ... , х) дают новые функции, являющиеся искомыми константами: f¢₀ º 1, f¢₁ º 0.

2. f₀(1,...,1) = 1, f₁(0,...,0) =1. Дублирующие подстановки дают: f¢₀º 1,f¢₁º`х. Подставляя далее, получим f¢₁(f¢₀ (х)) º 0.

3. f₀(1, ... ,1) = 0, f₁(0, ... ,0) = 0. Из дублирующих подстановок следует: f¢₀º `х , f¢₁ º 0. Применяя взаимную подстановку, получим f¢₀ (f¢₁(х)) º 1.

4. f₀(1, ... ,1)=0, f₁(0, ... ,0) = 1. После дублирующих подстановок получим: f¢₀º `х , f¢<sub>1</sub>º`х . По лемме о несамодвойственной функции из f_S подстановкой`х всегда можно получить одну из констант. Вторую получаем при помощи функции`х .

Таким образом, доказано, что {0,1}Î[{f₀, f₁, f_S}]. По лемме о немонотонной функции из f_M путем подстановки констант 0,1всегда может быть получена функция`х. Отсюда следует: {0, 1,`х}Î [{f₀, f₁, f_S ,f_M}]. По лемме о нелинейной функции из f_L путем подстановки функций 0, 1,`х всегда может быть получена функция умножения ху. В итоге получаем: {Ø , & }Î [{f₀, f₁, f_S , f_M , f_L }]. Так как [{Ø , & }] = P₂ , то отсюда следует [{f₀, f₁, f_S , f_M , f_L}]=P₂ и [{f}]=P₂ , что и требовалось доказать.

Пример 1. Проверить полноту системы функций {f} = {f ₁ = х & у , f ₂ = х® у }в P₂ .

Решение. Используем теорему Поста. Функция f₁ = х & у не входит в классы S, L, но входит в классы Т₀, Т₁, M.Следовательно, у функции f₂ = х® у достаточно проверить ее вхождение в Т₀, Т₁, M.Так как f₂ входит в Т₁, то отсюда следует, что вся система {f}целиком содержится в Т₁. Следовательно, по теореме Поста она не полна в P₂.

Пример 2. Можно ли с помощью операции суперпозиции из системы функций {f}={f₁ = (1010), f₂ = (0110), f₃ = (0011)}получить функции g₁ = (1011), g₂ = (1111).

Решение. Для наглядности решения рассмотрим таблицу истинности функций f₁, f₂, f₃и g₁, g₂. Переменные обозначим х и у.

Как следует из векторов истинности, f₁=`у, f₂= хÅ у, f₃= х. Проверка вхождения данных функций в предполные классы показывает, что все они принадлежат классу L линенйых функций. Так как данный класс замкнут относительно операции суперпозиции, то её применение к функциям f₁, f₂, f₃ будет давать только линейные функции.

Разложение функции g₁ в полином Жегалкина дает выражение 1Å уÅ ху. Данная функция нелинейна и не может быть получена из системы {f} с помощью операции суперпозиции. g₂ является линейной функцией - константой 1. Выражение для неё с использованием {f} может быть получено, например, в результате следующей подстановки: 1 = xÅ`x = f₂(f₃(х),f₁ (х)).

Ответ:1) функция g₁ не может быть получена из системы {f} с помощью операции суперпозиции, 2) g₂ = f₂(f₃(х), f₁(х)).

Cистема, состоящая из одной функции х| у - ‘штрих Шеффера’, полна в P₂. Это следует из возможности представления любой функции алгебры логики в виде ШНФ. Также данная функция не входит ни в один из предполных классов Т₀ , Т₁, S, M и L .

Определение. Если система, содержащая одну функцию f, полна в P₂, то функцию f называют шефферовой.

ЗАДАЧИ

1. Проверить полноту в P₂ систем функций: а){&, `х½у}; б) {Ú,®}; в) {® , х®`у z}; г) {&, 1,Å};д) {®, 0};е){®,Ø}; ж) {& ,Ú,®}; з){х¯`у,`х½у};и){(1011), (10010110)}; к) {х® у z, (1001)} ;л){(1010), (11011101)}.

2. Дополнить систему функций до полной в P₂ при помощи функций, не являющихся шефферовыми: а){(1001), (0110)}, б){® , х®` уz}.

3. Проверить, можно ли только с помощью операции суперпозиции получить:

а) из функции (0001)функцию (1001);

б) из функции {х¯у}функцию х&у ;

в) из функции {х® у}функцию хÚу ;

г) из функций {хÅу, ху}функцию хÚу.

4. Найти все шефферовы функции от двух переменных.