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

Укажем еще несколько групп тождеств (правил), от- носящихся уже к системе елементарныл функций (О, 1, ..., й — 4, 1,(х), ..., 1,,(х), Ш(П(Х„хз), Шал(Х„хз)). 3. Правила спуска символа 1 «вглубьэ формулы: (й — 1 прп с- о, 1,(с) = ~ (о,с 0,1, ...,й — 1); при с~о 1«(х) Ч ... Ч1« з(х)Ч1«+з (х)Ч... Ч1„1(х) при о О, 1«(1« (Х)) 0 при 0(о <й — (, 1(х) при о й — $; 1,(х,х,)= 1.(х,)(1.(х,)Ч ...

Ч 1.,(х,))Ч Ч 1. (х,) (1.(х,)Ч ... Ч 1, ,(*,) ); 1,(х Чхз) 1з(хз)(1з(хз)Ч...Ч1з(хз))Ч Ч1,(хз) (1з(х,)Ч...Ч1.(хз)). 4. Свойства дистрибутивности: (х, Ч х,) х, (хзх,) Ч (хзхз), (х,х,) Ч хз (х, Ч х,) (хз Ч х,). 5. Правило исключения «чистылэ вхождений переменной: х = 1 1, (х) Ч 2 1з (х) Ч " ° Ч (й — 1) 1з- з (х) . Гл.

т. А-ЗЯАЧНАя логпка 6. Правило введения переменной: х, =х,(1,(х,)Ч... Ч1,,(х,)). 7. Правила упрощений: (1,(х) при т= о„ О прп тФо; от ш(п(о, т); а Ч т = шах(о, т); 47 (й — 1)х=х; О х=О; (й — 1)Чх й — 1; ОЧх=х. Опираясь на некоторый запас тождеств (например, тождества 1 — 7) для системы элементарных функций (О, 1, ..., й — 1, 1,(х), ..., 1,,(х), ш(п(х„х,), шах(х„хз) ), можно при помощи эквивалентных преобразований полу- чить новые тождества. Рассмотрение свойств элементарных функций показы- вает, что не для всех обобщений булевых функций сохра- няются соответствующие свойства.

Поясним зто на при- мерах. Пример 1. 1) -(-х)= х, но х чь х (при й > 3). 2) ппп(х„х,) шах(-хо - х,), но шш(хо х ) Ф шах(х~ Уз) ° В заключение приведем тождество, представляющее аналог совершенной д. н. ф. и играющее важную роль в последующем изложении: /(хы ..., х„)= Ч 1с,(х,)Ь...Д1е„(х,)гб~(о„...,о„). (ао,,ад) Доказывается оно прямой проверкой. Нетрудно видеть, что каждая формула над множеством элементарных функций (О, 1, ..., й — 1, 1,(х), ...

..., 1„,(х), шш(хо х,), шах(х„х,)) может быть при помощи тождеств 1 — 7 преобразована к д. н. ф. Отсюда легко показать, что правила 1 — 7 позволяют перейти от любой формулы над данным множеством к любой другой формуле, аквивалентной исходной. Последнее свидетельствует о том, что система тождеств 1 — 7 в известном смысле обладает полнотой. 43 ч. ь Функционлльиые системы с ОпеРАциями и 2, Примеры полных систем В Р„определение полноты выглядит так же, как и в Р,. Определение. Система $ функций ~о ~и ..., ~., из Р, называется (функционально) полной, если любая Функция иэ Р, может быть записана в виде формулы че- рез функции этой системы.

Нин<е рассматриваются примеры полных систем. Для обоснования полноты мы будем использовать принцип сведения задачи о полноте одних систем к задаче о иол- ноте других (см. $ 5, гл. 1). 1. Система $ Р, полна. Очевидно, что множество всех функций иэ Р„ представляет полную систему. 2.

Система $ «О, 1, ..., й — 1, 1,(х); ..., 1,,(х)', 1ПШ(ХИ Хо), Шал(ХИ Хо)) является полной. Теорема 2. Система Ф вЂ” «О, 1, ..., й — 1, Ео(х),, 1а-в(х), ш«п(х„х,), шах(х„х,)) является полной в Рэ. Докааательство. Пусть 1(хи ..., х„) — произвольная функция из Р„. Для нее имеет место разложение 1(х„..., хо)- ~/ Уо1(х1) б ° ° ° ~ ~о„(хо) бс У(о„° ° ыо,). «о1„ ,о„) Данная формула (правая часть) построена иэ функций, входящих в $. Теорема доказана. 3. Система $ «х, шах(хи хо)) является полкой.

Теорема 3. Система $ «х, шае(х„,з,)) полно вР„. Доказательство. а) Построение коис т а нт, Из функции х *= х+ 1 получаем функции я+2=(х+1)+1, ..., х+.й — 1 (х+й — 2)+1, х х+ й =(х+(й — 1) )+ 1. Легко видеть, что шах(х, х+1, ..., х+ й — 1)=й — 1. Отсюда при помощи х получаем остальные константы Гл. й.

а-Значная лОГикА б) Построение -функций одной переменной. Сначала получаем функции 1,(х) (в ° О,..., й — 1): 1в(х) ° 1+ шах (х + и). а~ в-в-в В самом деле, если х 3, то левая часть равна й — 1, а правая часть есть 1+ шах (! + св) 1+ шах (1 + вв» а~ в-г-в в+а~в-1 1 + й — 2 й — 1; если х ть 1, то левая часть равна О, а правая— 1 + шах (х + а) 1 + (х + (х — 1 — х)) й О. авва-1-! Введем функции ),, «(х), где (а при (О прн хчь1, Покажем, что у,,в(х) в+1+шах'(Цх), й — 1 — е1. Последнее 'легко усматривается ив графиков, изображенных на рис. 1.

-И у у НГИ Н Ф г ЕУГГвт И у в Ив'в'ч И 445 иаеД гад л-г-а1 звг+иав~4 га,лува) Рис. 1 Если л(х)- произвольная функция одной переменной из Р„ то Я(х) Шал ЦВ<ВЬВ(Х), ~ВОЬ В(х)в ° ° °, ~ВВВ-ВВ В-В(х))в и, в частности, х шах(Д-в,в(х), ~в-в,в(х), . Д,в-в(х)). в) Получение Ш1п(х„хв). Мы видели, что -шш(х„х,) шах(-х„-хв).

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

Вопрос о ее полноте может быть легко сведен к полноте системы 3. С понятием полноты связано понятие замыкания и замкнутого класса. О п р е д е л е н и е. Пусть йй — произвольное подмножество функций из Р,. Замыканием йй называется множество [зй] всех функций из Р„, представимых в виде формул через функции множества й.

Определение. Класс (множество) йй называется (функционально) ваА1кнутым, если [зй] И. Для данных понятий справедливы высказывания, которые были сделаны при рассмотрении аналогичных понятий в Р,. Приведем примеры замкнутых множеств. Пример 2. 1) Класс йй=Р„очевидно, является аамкнутым. 2) Пусть Ф ~= 8,. Обозначим через Тб множество всех функций )(х„..., х„) из Р, таких, что ~(аь ..., а„) ж Ю, если и,1и д' (1= 1, ..., и). Другими словами, Тб — множество всех функций из Р„, сохраняющих Ю'; будем записывать зто так: Класс бй = Ти, очевидно, является замкнутым. В терминах замыкания можно дать другое определение полноты, эквивалентное исходному: эй — полная система, если [тл] = Р„. гл.

з. а-значнля логика Понятие замкнутого класса может быть приложено к решению вопроса об обосновании неполноты некоторых систем. П р и и е р 3. Рассмотрим систему $=(-х, шах (хи ха) ). Пусть Ю' (О, й — 1). Так как обе функции сохраняют д', то [% а Тв. Поскольку при й > 3, Ю ча Еа, то Тх не содержит, например, константу 1. Значит при й > 3 $ не будет полной системой. На этом примере видно, что, хотя система ( х, шах(хи х,)) и является обобщением системы (х, х, Чх«) булевых функций, она не является полной. $3. Расповнаваиие полноты.

Теорема о полноте Теперь мы перейдем к обсуждению вопросов полноты для произвольных систем $. Следовательно, здесь нас будет интересовать, каким образом по множеству $ можно узнать, будет оно полным или нет. Мы рассмотрим два подхода к решению этой задачи. Первый подход алгорнтмический. Он требует уточнения слов «задана произвольная система $». Ввиду этого мы несколько сузим задачу и будем предполагать, что система $ конечна: Е-(Ь, ~а.....

и и, стало быть, она может быть явно задана либо перечнем таблиц, либо списком формул. Так же как и в случае й ° 2, можно считать, что каждая из функций системы $ зависит от переменных хи х», ..., х„. Наша задача может быть сформулирована следующим образом: существует ли алгоритм, позволяющий для каждой конечной системы Ф выяснять, будет она полной или нет (задача распознавания полноты), Для произвольного р > 1 обозначим в"в«(ха ° ° «хз) ' А и через йй»,„. — множество всех функций из йй, зависящих от переменных х„..., х». Теорема 4.

Существует иагоритз«для распознавания полноты. Е2 ч. ь ФункциОКАльные системы с ОпеРАцнями Доказательство. Построим по индукции последовательность множеств Ио! И!! функций от двух переменных х, и х,. Базис индукции. Положим И,=Л, где Л вЂ” пустое множество. Индуктивный переход. Пусть уже построены множества И„И„..., И;, покажем, как определяется множество И,+,. Для етого выпишем функции, входящие в И, (г~О): И„= [Ь,(х1, хз), ..., Ь,,(х„х,)) (з„О при г О), и для каждоге ! (1=1, ..., з) рассмотрим всевозможные формулы вида ~! (Н, (х„х,), „Н. (х„х,) ), где Н!(х„х!) есть либо функция Ь,(х„х,) (у = 1, ..., з,), либо й~~ (х„хз). Таким образом, просматривая з(г, + 2)" формул, мы, быть может, получим функции, не вошедшие в И,.

Обо- значим их через Ь»!+! (х!! хз)! ! Ь! ! г(х!! х») Положим И,+1= И,[) [Ь,,+,(х„х,), ..., Ь,„.,(х, х,)). Очевидно, что И! — И! — ° ° . ж И, ж... Из построения ясно, что если И,»! И„то И, И,+, т. е. цепочка множеств стабилизируется. Обозначим через г» минимальный номер множества, начиная с которого наступает стабилизация.

Тогда цепочка множеств И»~И,с-... сИ„» строго возрастает. Так как мощность И! не больше, чем Ь~, то г»( Ь . Значит, момент стабилизации может быть обнаружен через ограниченное число шагов. Рассмотрим множество И,». Возможны два случая. 1) И!» содержит все функции от двух переменных х„х, и, значит, содержит )1,(х„х,). Тогда исходная система полна. 2) И,» нв содеря1ит всех функций от двух переменных. Поскольку в етом случае [И)»» = И!» (см.

заме- гл, а юеггачная логггкя чание 1 из т 2 гл. 1), то Щ не содерягпт всех функций от переменных х, п х,. Следовательно, $ не полна. Иа данных рассуждений легко иавлекается алгоритм: строим классы И„И„..., И,р до момента стабилизации и рассматриваем класс И,*, по которому и определяем, имеет место полнота для $ или вет. Теорема доказана. Теорема 5. Лз всякой полной в Р„системьг $ можно выделить конечную подсистему, являющуюся также полной. Доказательство. Пусгь 9 (~„Д„..., г'„...).

В силу полноты функция У,(х„хе) может быть выражена череа функции системы $ в впде формулы Уе (х„хе) П (гг, ° ° ° 1г„~ Очевидно, что подсистема ',г';,, ..., гг„) является искомой. Теорема доказана. Таким образом, существенно бесконечных полных систем не бывает, и тем самым введенное выше ограничение в задаче распознавания полноты является не столь сильным, как это могло казаться первоначально. Второй подход в решении вопроса о полноте связан с проверкой некоторых свойств класса $. Введем одно понятие и докажем относительно него две леммы.

Пусть И вЂ” класс функций Ь (у„..., у,) иа Р„ааввсящих от р переменных у„..., у,. Предположим, что он содержит функции у;(у„..., у,)- у, (г 1, ..., р). Определение. Фупкция г(хо ..., х„) сохраняет множество И, если для любых функцийЬг,(у„...,ур),..., ..., Ь;„(у„..., у„) из И 1(Ьг,(у " у) " Ь (у °" ур))енИ Обозначим через Б кл1сс всех функций иа Р„сохраняющих множество И.