С.В. Яблонский - Введение в дискретную математику, страница 9

Пример 4. Пусть Ь 2, р= 1 и И=(у, у). Тогда функция г(хо .. ч х„), сохраняющая множество И, удовлетворяет соотношенвю ~(у ', " , у ") - у', откуда (о„..., о.)= ~(оо ..., о.). Значпт, функция Г'(хи..., х.) — самодвойственная, и класс 54 ч. 1. Фуннционлльные системы с ОпеРАциями сохранения множества И есть класс Я самодвойственных функций. Лемма т. Класс И всех функций, сохраняющих И, является замкну тьиь. Д о к а з а т е л ь с т в о. Очевидно, что класс И содержит тождественную функцию.

Поэтому для обоснования замкнутости класса И достаточно показать, что функция Ф 1(1о ..., 1 ) принадлежит классу И, если функции принадлежат классу И. Пусть Ф зависит от и переменных. Возьмем произвольные функции Ь;,, ..., Ьг„из класса И. Тогда Ф(Ь11$",Ьгь)=1(11(Ь111 °,Ь!г)г...,1т(Ь11, „Ь,д))- (Н„..., Н где функции Н„..., Н„принадлежат классу И, поэтому и 1(Нь ..., Н ) принадлежит И.

Лемма доказана. Лемма 2. Если класс й таков, что (й)р,,„р й, то для класса й, сохраняющего И, имеет место равенство И„,„,г И. Доказательство. Пусть Ь(у„..., у ) ж й. Тогда если Ь1„..., Ь, ен й, то Ь(Ь1 Ь' )~[И) р й т. е. Ьы Иг,„,„„. С другой стороны, если 1(У1 ' ' ' Ур) ~ Игг."гр го, подставляя вместо у„..., у, функции у„..., у„получим 1(уи ..„ур)жй или 1(у„..., ур)гий.

Лемма доказана. Теорема 6 (о функциональной полноте, А. В. Кузнецов ($5]). Можно построить систему замкнутых классов вР, Ио Ига ' 1йь каждый из которых целиком не содержит ни одного из остальных классов, и такую, что подсистема функций из Р, полна тогда и только тогда, когда она целиком не содержится ни в одном из классов Иь ..., И,. Гл. 2. а-знАчнАя логикА Доказательство. Построение системы классов йо ..., й,. Пусть И„Иа, ..., И,— система всех таких собственных подмножеств функций из Р„зависящих от двух переменных ла и им которые удовлетворяют следующим условиям (а = 1, ..., 1): 1) И; содержит обе функции яа(к„ха) ла, да(хоза) Ха~ 2) (И ),, = Ио Указанные подмножества строятся путем просмотра всех собственных подмножеств множества функций из аьа1 Р„зависящих от переменных за и ха (их(2 ).

При этом оставляются те подмножества, которые содержат обе функции яа и я„и далев для каждого оставшегося подмножества проверяют условие [И)..., . И, что может быть осуществлено так же, как в теореме о распознавании полноты. а Обозначим далее через йа класс сохранения подмноа жества И,. В силу лемм 1 и 2 й; — замкнутый класс такой, что [йа)хааа = Ио Отсюда следует, что все классы й;(1 = 1, ..., 1) различны и не являются полными.

Далее остается только удалить те классы, которые содержатся в каком-либо иа остальных классов. Мы получим систему й„й„..., й,. Необходимость вытекает иэ свойств замкнутости и неполноты классов й, (1= 1, ..., э). Достаточность. Пусть йыР, — система функций, целиком не содержащаяся ни в одном из классов й, (у 1, ..., г). Можно считать, что й — замкнутый класс. Обозначим через й' класс [й0 (б„даЦ. Очевидно, что классы й и й' либо одновременно полны, либо неполны, так как й'-й() [(ло я,)1, и фУнкциЯ Ра (зо х,) либо входит в й и й', либо не содержится ни в одном из зтих классов. Возьмем И' й,,, Покажем, что И' содержит все функции, зависящие от 56 Ч. Е ФУПКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ переменных х, и х,.

В самом деле, если это не так, то очевидно, что Я' =Яг и й' с='И; с= Из. Так как Иж И', то получаем, что й жИА что противоречиво. Таким образом, я', а значит и й', содержит функцию Уг(хч х,). Отсюда вытекает полнота класса й', а следовательно и класса И. Теорема доказана. Следует обратить внимание ва то обстоятельство, что теорема Кузнецова доказывает, что возможно выразить условия полноты системы $ з терминах принадлежности ее к специальным классам й„..., й,. Однако фактичбское построение классов даже при небольших й связано с трудоемкими вычислениями, которые невозможно осуществить.

В силу этого возникает вопрос о поиске других, более эффективных критериев. Мы увидим, что эта цель достижима, но за счет введения ограничений, т. е. за счет знания дополнительной информации об исходной системе Ф. 3 4. Некоторые свойства существенных функций. Критерий полноты Целью этого параграфа является доказательство одного критерия полноты. Однако для этого нам необходимо несколько подробнее изучить свойства функций Дхь ... ..., х„) иа Р„которые зависят существенно не менее чем от двух переменных. Данные функции мы будем называть сущестеенньсии. Докажем три леммы. Лемма 3.

Пусть 1(хо..., х„) — существенная функция, принимающая г (1 г 3) значений. Пусть хс — ее существенная переменная. Тогда найдутся дел таких набора (а, а„..., а„) и (р, а„..., а„), что ~(а, а,,..., а.)чь у(Р, а... сс„) и ((а, х„..., х„) принимает значение, отличное и от 1(а, а„..., а„), и от )(р, аь ..., сс ). Доказательство. Так как х,— существенная переменная функции ~, то найдутся такие значения а„ ...

..., а„, что последовательность 1(0, аь ..., а,), 1(1, аь ..., а„), ... ..., Дгс — 1, а„..., сс.) (е) ГЛ. Х. Ь-ЗНАЧНАЯ ЛОГИКА содержит не менее двух различных значений. Возможны два случая. Ц В последовательности («) содержатся не все значений. Рассмотрим набор (а, ть ..., т ) такой, что значение )(а, т«, ..., т„) не встречается в («).

Очевидно, что у(а, аь ..., а.) чь ~(а, т„..., т„). Примем за р любое из значений, для которых 1(р, а„..., а„)Ф ~(а, а„..., а„). Очевидно также, что т(р, ам ..., а.) чь 1(а, тм ..., т„). 2) В последовательности (») встречаются все 1 значений. Из существенности функции 1 вытекает, что существует а такое, что 1(а, хм ..., х„)чь сопз1 (иначе бы ( зависела существенно только от одной переменной).

Отсюда следует, что найдутся наборы (и, а«,... ..., а ) и (а, т„ ..., т.) такие, что 1(а, аь ..., а.)-" Ла, т,, т.). Так как последовательность («) содержит ( () > 3) значений, то найдется такое р, что Я, а„..., а.)чала, аь ..., а.), 1(р а а )~1(а т ° " т.). Лемма доказана. Пусть 6 — конечное множество. Обозначим через )6) число элементов в 6.

Лемма 4 (основная). Если ((хь ..., х„) — существенная функция, принимающая не менее ) ((-«3) значений, то найдутся п подмножеств 6„..., 6„множества Е, таких, что 1» ! 6,), ..., ! 6.! -= 1 — 1 и на множестве наборов (а„..., а„), зде а~~и 6< (~ ° 1, ..., п), т. е. на 6, Х 6,Х... Х 6„, функция 1 принимает 1 значений. Доказательство. Можно считать, что х, — существенная переменная функции (. На основании предыду- ба ч.

1, Фв<ИБЦМОИАльные системы с ОпеРАциями щей леммы найдутся три набора (а, а„..., а ), (р, а„..., а ), (а, (в, ..., "(.), на которых ~ принимает три различных значения. Добавим к зтим наборам еще < — 3 набора (Все бсо ... 6'") ... (6" " бо " ...,6с з') на которых ~ принимает остальные < — 3 значений. Положим <"„= (а„, у„,б'„", ..., 6'„' "(. Построенные множества, очевидно, удовлетворяют условиям леммы. Лемма доказана. О и р е д е л е н и е. Система наборов вида (а„..., а< „аь а<+„..., а> „а>, ссы< ° а ) (а„..., а, „р„а<+„..., а> „а>, а>+„..., а ), (а„..., а, „р<, аа„..., сс> „рь а>+„..., а„), (сс„..., а, <, и<, аа„..., а> «Р>» а>з ., сс.) называется квадратом, если а» Ф р< и а> чь р>.

Л е ми а 5. Пусть ((х„..., х„) — существенная функция, принима>ощая < (< > 3) значений. Тогда найдется квадрат, на котором >' принимает либо более двух значений, либо два значения, причем одно из них только в одной его точке. Доказательство. Можно считать, что х, — существенная переменная функции ~. Тогда на основании леммы 3 найдутся наборы (а, ав, ..., а.), (р, а„..., и.), (а, („..., 1„), на которых ( принимает три различных значения. Эти наборы порождают куб размера 2, т. е. куб, имеющий проекцию на каждую ось не более чем из двух точек, а размерность куба не более и. Данный куб определяется как (и, р) Х (и„"(,) Х...

Х (а„, )» ). гл. к А-знАч!тАя логпех Рассмотрим в этом кубе его гиперплоскости х, = а и л, р (см. рис. 2). В гиперплоскости л, =а соединим точку (а„ ..., а ) с точкой ((ь ..., '(„) цепочкой ребер, принадлежащих этой гнперплоскостп (каждое ребро— пара соседних наборов, т. е. наборов, принадлежащих гиперплоскостн и отличающихся значением ровно в одной координате). Данная цепочка ребер определяет цепочку ребер в гиперплос- 11 кости л, р, являющуюся ее 5~1Лз 11 ! 1лт проекцией.

Пара соответ; 1 1 11 11 11 ствующих ребер этих цепо- ! чек образует квадрат. Следовательно, мы имеем цепочку з'гквадратов. На ребре В, пер- (ит...,и„> 1)),...,уз) вого квадрата функция принимает значения ~(и, а„... ..., а„) и Лр, с!ь ..., с!.), а на ребре В, последнего квадрата функция ~ пе принимает хотя бы одно нз этих значений. В таком случае в цепочке найдется квадрат (пусть его номер !) такой, что на ребре В, функция принимает значения ((а, аь ...

..., а ) н /((), аь ..., а.), а на ребре В„, не принимает по крайней мере одно из этих значений. Квадрат с номером ! является искомым. Лемма доказана. Доказанные леммы допускают простую геометрическую интерпретацию. Пусть ~(з„..., х.) — существенная функция, принимающая ( аначенпй, где ( ) 3. Тогда: 4. Существует куб размера 2 такой, что на нем функция ~ принимает по крайней мера три значения (лемма 3).

2. Существует куб размера ! — т такой, что на нем функция ~ принимает все ( значений (лемма 4). 3. Существует квадрат, на котором функция / принимает либо более двух значений, либо ровно два, из которых одно в одной точке (лемма 5). Замечание т. Леммы 3 и 4 не имеют смысла для й ° 2, лемма 5 имеет смысл, но неверна, так как функция ~(ло з~)=в~+к, в своей области определения — а она есть квадрат,— принимает два значения, и оба с кратностью два. со ч 1 ФуикциоиАлы!ые системы с опеРАциямн 3 а м е ч а н и е 2.