Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
^ (»Tjj • • • 1 Xfti) =•
“ V Іо-i (^l) & ? ? ? & /<7m (xm) & h (0lt . . . , CTm) “ “ V 01 jo 1 (^l) &01 • * » &Qiiam (#m) (<Дц .1*1 M-
ГЛ. X. Л ЗНАЧНАЯ ЛОГИКА
63
Таким образом, функция к {хи ..хт) может быть получена из системы ф. Так как $ содержит все функции одной переменной, принимающие любые два значения, то мы можем также получить из ф все функции, принимающие любые два значения.
2) Пусть из $ построены все функции, принимающие не более I — 1 значений, I — 1 < к. Покажем, что тогда можно построить все функции из Рк, принимающие I значений.
Возьмем функцию }(х1, ..., ?п) . На основании леммы 4 найдутся п подмножеств ..., таких, что ^ I — { (? = 1, * ? -, и), и на & = С1 X ... X функция / принимает I значений Цо, гр, ..., тр_1. Пусть эти значения принимаются соответственно на наборах из &:
»-» = («<?», 4°'.....
г™ = (4», а?>......... ей»).
4'-° = (4'"1’, 4|_1>,.. а»-1’),
т. е.
/{а(0))= Л0, /(аа1)=*Ь • - /(«<1_1,)= *)(-*?
Покажем, что из системы ф можно построить произвольную функцию к(хи ..., хт), принимающую значения Т]о, Т|1» ? • •) Щ-1-
В самом деле, функцию к(хи ..., хт) можно задать
*? ^
при помощи табл. 2, в которой а=(оI, .. от). Определим функции %(яч, ..хт) (У = 1, ..п) так, как указано в табл. 3.
Таблица 2 Таблица 3
*1 <’• *т Л.(Ж| ЩуО
°1 ??? °т %Гс)
Х1 хт 4’} (^1 !*••!
СТ1 ••• от ащЪ)
Тогда
• ? ?) / (^1 (*^1, • * ?, *Гт) , . . ("Я'!* ? • ч «^»0 ) }
64
Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
ибо
/ ($1 ? ? •, °т), . . ., К, ...,От))“
А(аь ..0^)= т]((о>*
Имея все функции с заданными I значениями Цо, ...
. . Г1г-(, можно в случае I < к получить при помощи
функций одной переменной, принимающих менее к значений, остальные функции с I значениями. Таким образом, применяя этот прием, мы дойдем до I = к, и тогда построим все функции из Рк. Этим достаточность доказана.
Следствие (критерий Слупецкого), Пусть система ф функций из Рк> где к ^ 3, содержит все функции одной переменной. Тогда для полноты системы $ необходимо и достаточно, чтобы ф содержала существенную функцию 1(хи ..., хп), принимающую все к значений.
Замечание. Доказанная теорема верна при к > 3 и не может быть распространена на случай к = 2. В самом деле, система
ф — {О, 1, х, х, х1 + х2\
не является полной, так как
Непосредственное использование теоремы и тем более ее следствия не всегда удобно, так как для этого предварительно нужно установить наличие в ф всех функций одной переменной, принимающих не более к — 1 значений, т. е. к? — к\ функций. С ростом к громоздкость указанных построений сильно возрастает. Поэтому целесообразно в формулировках теорем заменить требование, чтобы система ф содержала определенное множество функций одной переменной, требованием, чтобы система ф порождала это множество функций одной переменной. Последнее может быть установлено гораздо более экономичным образом. Например, если известно, что из ф могут быть получены какие-то конкретные системы функций одной переменной, порождающие все функции одной переменной.
В качестве примеров таких систем приведем две системы.
Теорема 8 (С. Пикар [45]). Все функции одной переменной из Рк могут быть порождены тремя Функ-
1\1 . 2. А-ИНАЧЯАН ЛОГИКА
65
циями:
](х) = х — 1 (той к),
ё{х)
( х, 0< к — 3, \к — 1, х ~ к — 2,
\к — 2, х — к — 1,
1, х = О,
.г, х Ф 0.
Теорема 9. Все функции одной переменной из Рк могут быть порождены к функциями
и фуптщей к. (х).
Доказательства этих теорем несложны, поэтому они опускаются.
В заключение рассмотрим еще одно приложение доказанного критерия полноты. Мы дадим характеристическое свойство функции ИЗ Рь, образующей полную систему (функция Шеффера). Это свойство является незначительным усилением теоремы Мартина [44].
Теорема 10. Функция Лхи . .., хп) из Рк, где является функцией Шеффера тогда и только тогда, когда /(лц, ..., лгп) порождает все функции одной переменной, принимающие не более к — 1 значений.
Доказательство. Необходимость очевидна.
Достаточность. Очевидно, f{xu ..., хп) должна принимать все к значений, так как из нее получаются, например, все константы. Если / — несущественная функция, то / есть подстаповка и из нее можно получить только подстановки. В этом случае мы не получим даже констант. Значит, это невозможно, т. е. / является существенной функцией. Применяя критерий полноты, приходим к тому, что одстема $ = {}{хи ..#„)} является полной. Теорема доказана.
§ 5. Особенности /означных догпк
Предыдущий материал показывает, что во многом конечнозначные логики похожи па двузначную логику. В них сохраняются мпогпе результаты, имеющие место в двузначной логике. Правда, рост значноста все-такл
5 С. В. ЯОлон<лтй
I При х = 0,
0 при х = г, х в остальных случаях
(?G ч. . Ч?ушциишуимши vj \jtiE*rллд^п“ш
приводит к известным усложнениям формулиррвок и доказательств.
Однако теперь уже накоплено достаточно много фактов, указывающих на своеобразие ковечнозначных логик, в том числе и фактов, выявляющих существенное отличие Ph при к > 3 от Рг. Эти обстоятельства тем более заслуживают внимания, если иметь в виду работу Поста [46], в которой была выдвинута идея сведения конечнозначных логик к двузначной логике. Он предложил вместо функции f(xI, ..хп) из Pk рассматривать систему функций
