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

Леммы 4 н 5 не допускают усилений. В самом деле, пусть 3 < (( й — 1, п > 3 и при х1 ... = х„~, 1() — $, (О в остальных точках. Пусть 6„..., 6„— произвольные множества из Е„и 1 <!6,1, ..., !6„! ( ( — 2. Тогда на 6, Х... Х б„функция (, не может принимать все 1 значений. Далее, на любом квадрате Д принимает не более двух значений. При рассмотренна функций Дхь ..., х.) нз Р„обладающих определенными свойствами на некотором множестве В' = 6, Х... Х 6„, часто приходится переходить к функциям ~'(хь ..., Е.), обладающим аналогичными свойствами, но, может быгь, на другом множестве Е' 61 Х ..

° Х 6 Переход от функции ( к функции 1' мы будем называть нормировкой. Следовательно, норми,ровка связана с преобразованием переменных и преобразованием значений функции вида ~'(кь ..., к„) = $(1'($,(х,), ..., $.(Х.))). В этих преобразованиях ыы исходим из того, что (61 ~ (61( = („...,! 6„( — (6„( = ( . Обозначим через значения, которые принимает ~ на множестве Е, и через Чп ° ., Ч1-1 — набор из попарно различных чисел множества Е,. Таким образом, нормировка определяется указанием взаимно однозначных соответствий между множествами: ю (Чз з Ч~-1) (Чо ° з Ч~-1!з Р 6ы 6„6„.

Эти взаимно однозначные соответствия могут быть подчинены дополнительному требованию, например, чтобы фиксиРованнаЯ точка (аь ..., а„) из Ф' соответствовала фиксированной точке (а„..., и,) из Ю' и чтобы Ч< со- Р ответствовало Чр Ясно, что эти соответствия могут быть осуществлены при помощи функций 1р (к), ф (з) ° ... Е1 гл. г. а-знлчнля логика ..., ц„(х) из Р„которые всегда можно выбрать из мноягества подстановок; если 1, 1„..., („» Й вЂ” 1, то их можно выбрать из множества функций одной переменной, принимающих не болев Й вЂ” 1 значений. Очевидно, что при нормировке кратности аначеннй функции (' на Е' такие же, как кратности соответствующих значений функции ) на гу. В дальнейшем нормировка используется в следующих видах: Ф 1) (Ч " т)-г) =(Чь, ", ц'-,), р(х) = х, 6, = (О, ..., 1, — 1) (ю' = 1,, „и).

2) 6; = 6~, ф (х) = х (1 = 1, ..., и), („,', ..., ц, ',) - (О, ..., 1 — Ц. 3) (ць . ° ° ц~ 1] (О, . ° ., 1 — Ц, 6', = (О, ..., 1, — 1) (1 = 1, ..., и). Случаи 1 (преобразование переменных) и 2 (преобразование аначений) — случаи неполной нормировки. В каче- Р ь стае фиксированных точек тв и (и„..., и„> обычно берутся 0 и (О, ..., 0). Докажем теперь теорему, являющуюся обобщением известной теоремы Слупецкого ([50]). Теорема 7.

Пусть система $ функций из Р„где Й > 3, содержит все функции одной переменной, принимающие не более Й вЂ” 1 значений. Тогда для полноты системы' $ необходимо и достаточно, чтобы $ содержала существенную функцию ((хь ..., х ), принимающую все Й значений. Доказательство.

Необходимость. Пусть ц) — полная система. Предположим, что $ не содержит существенной функции, принимающей все Й значений. Очевидно, что тогда из $ нельзя получить существенной функции, принимающей все Й значений. Мы пришли к противоречию. Значит 9 содернвит существенную функцию, принимающую все Й значений.

Достаточность. Пусть $ удовлетворяет условию теоремы и содержит существенную функцию т(хь...,х ), принимающую все Й вначений. Покажем, польвуясь индукцией, что $ полна. 1) Базис индукции. Покажем, что из $ можно получить все функции из Р„принимающие два значения. е2 ч.

ь фгнкпиональныв спсткмы с опяглцпямп На основании леммы 5 найдется квадрат (а» ..., а, » аь аа» ..., и>» аь аы» ..., а.), (а» ..., а, » рь а~+» ..., а, » ссь аы» ..., а), (сс . ас- ()ь ас+» а~-1 Ь аы " а ) (а» ..., а, » аь а+» ..., а~ » гь аы ..., а ), где арчь~, и а,чар» на котором функция ~ принимает не менее двух значений, причем одно нз них, ц, — в одной точке. Возьмем функцию ~р(х) такую, что (О при х ц, при х чь и. Очевидно, что ср(х) ы $. Пусть й(х» хз)- 'Р()(а» ° ..~ а~-» х» ас+» ° °, а~-» х» аы» °... а )). Функция б(х» х,) на квадрате ((а» а,), фь а,), (~ь ~,), (сц, ~,)) принимает два значения, 0 н 1, причем значе- ние 0 в одной точке; обозначим ее (аз» ас).

Осуществляя неполную нормировку так, чтобы (О, 0) отображалось в (сс» а',), а квадрат ((О, 0), (1, 0), (1,1), (1, 0)) — в ука- ванный выше квадрат, получим функцию б'(х» х,), где е (х х1) б(фФ (х ) фс(хз) ) и й» фснп. Функция б'(х» х,), очевидно, есть максимум на множестве 10, 1) Х 10, 1). Обозначим ее через х, Ч„х,. Так как система $ содержит функции )<(х), где при х — 1, (О при хчь1, то хю ос»ха )о ()о (хс) ~/ м!о(хс) ) есть минимум на множестве (О, 1) Х (О, 1). Пусть Ь(х» ..., х ), Ьчь сопз$,— произвольная функция, принимающая два значения, 0 и 1; тогда й(х,...,х ) Ч !е, (х,) бс ... бс у, (х ) бс Ь (о» ..., о ) (е»...,е ,1 Чы )е1 (хг) Йзс ° ° ° йзс)ещ(хи) бсзг)с(пм ь ош).

(е». „ем) ГЛ. 3. »-ЗНА»(НАЯ ЛОГИКА Таким образом, функция Ь(х„..., х ) может быть получена из системы $. Так как з) содержит все функции одной переменной, принимающие любые два значения, то мы можем также получить из $ все функции, принимающие любые два значения.

2) Пусть из з) построены все функции, принимающие не более 1 — $ значений, 1 — 1( Ь. Покажем, что тогда можно построить все функции из Рь принимающие значений. Возьмем функцию 1(х„..., х ). На основании леммы 4 найдутся и подмножеств С„..., ("„таких, что (( (~ <1 — 1 (1 $, ..., и), и на с) 6,Х...ХС„функ- циЯ( пРинимает 1 значений Ц„ць ..., )),-» ПУсть этк аначения принимаются соответственно на наборах из 8': (О) ( (0) (О) (0)1 (1) ( (1) (1) (1)~ (1-1) ( ((-)) (( 1) (1-1)» а (а), и», ..., ((„), т.

е. 1(а")) = Ц., 1((а(")- Цо ..., Ла" ") = Ц-». Покажем, что из системы з) можно построить произвольную функцию Ь(хо ..., х ), принимающую значения Ч»~ ))(1 ° 1 ))(-). В самом деле, функцию Ь(х„..., х ) можно задать при помощи табл. 2, в которой а =(о„..., о ). Определим функции )())(х„..., х ) (1 1, ..., и) так, как указано в табл. 3.

Таблица 3 Таблица 2 Е) (а~ '" ам) о(((а)) 3 о, ...о„ Тогда Ь(хо ..., х ) = Щ(х„.. а х ), ..., ф,(х», ..., х„,)), а4 ч. ь фтнкцнонгльныв снствмы с опвгацнями ибо г ()р) (о„..., о„), ..., )()»(о„..., о„)) / (йг)) П(»))1 Ьсг) г ° ~ и» ) Чкви Й (оь ..., О») - т) и») Имея все функции с заданными 1 значениями цп ...

..., тр „можно в случае 1(Й получить при помощи функций одной переменной, принимающих менее Й значений, остальные функции с 1 аначениями. Таким образом, применяя этот прием, мы дойдем до 1 Й, и тогда построим все функции из Р,. Этим достаточность докааана. С л е д с т в и е (критерий Слупецкого). Пусть система $ функций иг Р„, вде Й > 3, содержит все функции одной переменной. Тогда для полноты системы $ необходимо и достаточно, чтобы $ содержала существенную функцию )(хи ..

» х ), принимающую все .Й значений. 3 а м е ч а и и е. Доказанная теорема верна прн Й > 3 и не может быть распространена на случай Й = 2. В самом деле, система Ф (0,1,х,х,х~+Ы не является полной, так как )р )и Ь. Непосредственное использование теоремы и тем более ее следствия не всегда удобно, так как для этого предварительно нужно установить наличие в ч) всех функций одной переменной, принимающих ве более Й вЂ” 1 аначений, т.

е. Йл — Й! функций. С ростом Й громоздкость указанных построений сильно возрастает. Поэтому целесообразно в формулировках теорем заменить требование, чтобы система ч) содержала определенное множество функций одной переменной, требованием, чтобы система ч) порождала это множество функций одной переменной.

Последнее может быть установлено гораадо более экономичным образом. Например, если известно, что из 9 могут быть получены какие-то конкретные системы функций одной переменной, порождающие все функции одной переменной. В качестве примеров таких систем приведем две системы. Теорема 8 (С. Пикар (451). Все функции одной переменной иг Рь могут быть порождены тремя функ- ГЛ. 3. А-ЗНАЧНАЯ ЛОРИКА циялуи Дх) = х — 1(отой Й), х, Ок х(Й вЂ” 3, у(х)= Й вЂ” 1, х-Й вЂ” 2, Й вЂ” 2, х=Й вЂ” 1, Й() <1 (х, х~О. Теорема 9.