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

Каждая из них может быть принята аа мнон<ество элементарных функций. Таким обрааом, длн задания булевых функций можно использовать различные языки формул. Какой именно из языков является более удобным, зависит от характера рассматриваемой задачи, ГЛ. Ь ЛЛГНВРА ЛОГИКИ зз С понятием полноты тесно связано понятие замыкания и аамкнутого класса.

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

1) И Р,. Очевидно, что [И] Р,. 2) И (1, х, + х,). Замыканием этого множества будет класс Ь всех линейных функций, т. е. функций, имеющих вид у (Хтт ° Хи) Се + СтХт + ° ° ° + Сигме где с,=О, 1 (у О, ..., п); существенные переменные входят с коэффициентом 1, фиктивные — с коэффициентом О. Отметим некоторые свойства замыкания; 1) [И] жй; 2) [[И]] [И]; 3) если й, ы И,, то [Ит] ж [И,]; 4) [й, 0 Иа]ив [Ит] 0 [И,]. О п р е д е л е н н е.

Класс (множество) И называется (функционально) замкнутым, если [й] = И. Пример 14. 1) Класс й Р, является замкнутым классом. 2) Класс й (1, х, +х,) не замкнут. 3) Класс Б аамкнут, так как линейное выражение, составленное из линейных выражений, является линейным. Легко видеть, что всякий класс [И] будет замкнутым. Зто дает возможность получать многочисленные примеры замкнутых классов. В терминах замыкания и замкнутого класса можно дать другое определение полноты (эквивалентное исходному): й — полная система, если [И] Р,.

$ б. Важнейшие замкнутые классы. Теорема о полноте Этот параграф мы начинаем с рассмотрения некоторых важнейших замкнутых классов в Р,. 1. Обозначим череа Т. класс всех булевых функций у(х„..., хи), сохраняющих константу О, т. е, функций, 2 Ваеаеиие и аиекретиую математику 34 ч. ь Функциональньге системы с ОпеРАциями для которых выполнено равенство /(О, ...,0)=0. Заметим, что если /ю Т„а /' — функция, равная /, то и /'ж Т, (это достаточно проверить для функций / и /', отличающихся одной переменной). Легко видеть, что функции О, х, х, Ь х„л, ~/л„х, + + з, принадлежат классу Т„а функции 1, х не входят в Т,. Поскольку таблица для функции / из класса Т, в первой строке содержит значение О, то в Т, содержится ровно (1/2) 2"" булевых функций, зависящих от перемен- НЫХ Ко . „Е„.

Покажем, что Т, — замкнутый класс. Так как Т, содержит тождественную функцию, то для обоснования замкнутости Т, достаточно показать, что функция Ф=ЯО ...,/„) принадлежит Т„если /, /„..., /„принадлежат классу Т, Последнее вытекает из цепочки равенств Ф(0,..., О) Я1(0, ..., О), ..., / (О, ..., О)) /(О, ..., О) О. 2. Обозначим через Т, класс всех булевых функций /(яо ..., х„), сохраняющих константу 1, т. е. функций, для которых выполнено равенство /(1, ..., 1)= 1. Очевидно, что класс Т, вместе с любой функцией содержит и любую равную ен функцпю.

Легко видеть, что функции 1, х, х,8~х„х, Ч х, принадлежат классу Т„а функции О, х не входят в Т,. В силу того, что класс Т, состоит из функций, двойственных функциям из класса Т, (или, как мы будем говорить, что класс Т, двойствен классу Т,), нетрудно перенести результаты о классе Т, на класс Т,.

Класс Т, содержит (1/2)2'" функций, зависящих от переменных хо..., л„, и является аамкнутым классом. 3. Обозначим через Я класс всех самодвойственных функций, т. е. функций / из Р, таких, что /~ =/. Как и выше, нетрудно проверить, что добавление равных функций не выводит за пределы класса Я. Очевидно, что самодвойственными функциями будут х, У. Менее тривиальным примером самодвайствепной ГЛ. Ь АЛГЕБРА ЛОГПКП 35 ФУНКЦИИ ЯВЛЯОТСЯ фУПКЦНЯ Й (Хо Хи Хг) = Х~хг Ч Х~хд Ч Чх,т,: йв(х„х„х,) (х,ЧХ,)(х,ЧХ,)(х,ЧХ,) -Х,„Чх,х,Чх,х,-й(хи хихг). Для самодвойственной функции имеет место тождество ~(х1 ° ° ° х ) 1(х~ ° ° ° х ); иначе говоря, на наборах (а„..., а.) и (а„..., а ), которые мы будем нааывать противоположными, само- двойственная функция принимает противоположные значения.

Отсюда следует, что самодвойственная функция полностью определяется своими аначениями на первой половине строк (см, табл. 1). Поэтому число самодвойственных функций, зависящих от переменных хгл ... ...,х„, равно 2'" ' т'2'". Докажем теперь, что класс Я замкнут.

Поскольку класс 8 содержит тождественную функцию, достаточно показать, что функция является самодвойственной, если ~, ~„..., ~„самодвойственны. Последнее устанавливается непосредственно: Докажем теперь лемму о несамодвойственной функции. Лемма 1.

Если Дхи ..., Х„)ФЯ, то ив нее путем подстановки функций и и х можно получить несамодвойственную функцию одного переменного, т. е. константу. Доказательство. Так как ~ФЗ, то найдется набор (а„..., а.) такой, что Лаь ..., а ) 1(а„..., а„)'. рассмотрим функции ф,(х)-х"г (!-(, ..., и) и по.

ложим ф(х)=~(ф,(х), ..., ф,(х)). зс ч. ь ФункциОнАльные системы с ОПБРАцияыи Мы имеем Р(О) =У«Р1(О), ..., Р„(О)) -У(О", ..., О"")- )(а„..., а„) /(а„..., а„) ~(1 ', ..., 1~") - 1 «Р,(1), ..., <р„ (1)) = р (1). Лемма доказана. 4. Здесь мы будем употреблять векторную запись наборов: а = (а„ ..., а„), р (ро ..., р„) и т. и. и вместо 1(ао ..., а„) употреблять запись /(а). Определение.

Для двух наборов а (а„..., а„) и р (~)„..., ~) ) выполнено отношение предшестеоеания а ~~ р, если а,~()ь ..., а„~ р . Например, (О, 1, О, 1) 4 (1, 1, О, 1~. Очевидно, что если а б (1 и р ~ "(, то а ~~т. следует отметить, что не любые пары наборов находятся в отношении предшествования, например, наборы (О, 1) и (1, 0)' в таком отношении не находятся. Таким образом, множество всех наборов длины п по отношению к операции предшествования б является частично упорядоченным.

О п р е д е л е н и е. Функция Яхо ..., х„) называетсл монотонной, если для любых двух наборов а и р таких, что а ~ (), имеет место неравенство 1(а) < /(р). Нетрудно заметить, что функция, равная монотонной функции, также является монотонной. Монотонными функциями, очевидно, будут О, 1, х, х,йх, и х, Чх,. Обозначим через М множество всех монотонных функций.

Покажем, что класс монотонных функций замкнут. Поскольку тождественная функция принадлежит классу М, то для установления аамкнутости М достаточно покааать, что функция Ф-Що ..., 1„) тл. !. АлГеБРА лотнкк является монотонной, если 1, 1„..., 1 монотонны. Пусть 1 ч !р х (х„..., х„), х (х„, ..., х!р,!, ..., х (х3р!! ° ° ! хтпр ) — наборы переменных функций Ф, 1„..., 1, причем множество переменных функции Ф состоит из тех и только тех переменных, которые встречаются у функций Пусть а и р — два набора длины и значений переменных х, причем а ~ (). Эти наборы определяют наборы сс', р!, ..., а", р-.

значений переменных х', ..., х" такие, что а'~()', ..., а"~ ~р . В силу монотонности функций 1„..., 1 1!(а!)<1,(()'), ..., 1 (а )(1 (р-). Поэтому (1 ( !) 1 (а )) (1 (рР ) 1 (Г))' и в силу монотонности 1 имеем 1(1!(а'), ..., 1 (а"))<1(1 (р'), ..., 1 (р")), откуда получаем Ф(а)=1(1,(а'), ..., 1 (а"))(1(1!(р'), „1 ((3 )) Ф(р).

Будем называть наборы а и р соседними (по !-й координате), если а (а„..., а!-!, а, а!т„..., а„), р (а!, ..., а! !, а„а!+„..., а„). Докажем теперь лемму о немонотонной функцпи. Лемма 2. Если 1(х„..„х„)ФМ, то ив нее путем подстановки констант О и ! и функции х морено получить функцию х. Доказательство. Сначала покажем, что найдется пара соседних наборов а и () таких, что а 4 р и 1(а) ~ 1(р). В самом деле, так как 1!а М, то существуют наборы а' н р! такие, что а! *б р' и 1(а')) 1())'). Если наборы $3 ч. ь Функциональные системы с опхглцпями а' и ()» — соседние, то наша цель достигнута.

Если а' н б» нв являются соседпимн, то набор б» отличается от набора а» в с коопдинатах, где с) 1, причем эти с координат в наборе а' имеют значенпв О, а в наборе б'— значенив 1. В силу этого между а' и б' можно вставить à — 1 промежуточных наборов а', а*, ..., а' таких, что а ~1а 1 ° ° . 1а'1~рп . Очевидно, что наборы, стоящие в этой цепочке рядом, будут соседними. Так как ~(сс»))~(д'), то по крайней мере на одной из этих пап соседних наборов — обозна- чим их через а и (3 (а 4 (») — будет ~(а)) ~ф).

Пред- положим, что данные наборы имеют соседство по»'-й ко- ордината и, следовательно, а (сс„..., а» „О, а»+„..., а ), (а„..., а» „1, а»+„..., а ). Рассмотрим функцию »р(х) 1(а„.. „а, „х, а»+„..., а ). Мы имеем »р(0) У(а», ..., а»», О, сс»+„..в а„) У(а))19) /(а„..., а, „1, а»+„..., а„)»р(1). Последнее означает, что»р(0) = 1, а»р(1) = О, т. е. »р(х) х. Лемма доказана. 5. Последним классом является класс Е всех линей- ных функций.

Он, очевидно, содержит константы О, 1, тождествен- ную функцию х, функции х, х, +х, и не содержит функ- ций х,дсх, и х, Чхи Выше было показано, что этот класс также замкнут. Докажем лемму о нелинейной функции. Лемма 3. Если ~(хо ..., х„)Ф.»., то ив нее путем подстановки констант .0 и 1 и функций видо х и х, а также, быть может, путем навея»иванна отрицания над г, можно получить функцию х, д» х,. Д о к а з а т е л ь с т в о. Возьмем полипом Жегавкина для г(хс» ..., х„) ~ а»,...»,х»,... х»,, (»» " »») 39 ГЛ.

», АЛГЕБРА ЛОГИКИ Следовательно, »р(х!1 хз) х! бс хз Лемма доказана полностью. В ааключенпе заметим, что замкнутые классы Т„Т„ Я, М и Т попарно различны, что видно из табл. 8, в которой знак + означает, что функция содержится в классе, а знак — обозначает противоположную ситуацию.

Табл»»»»а 8 т, о » л + + + Теперь мы можем перейти к рассмотрению одного из основных вопросов алгебры логики — вопроса о необхо- В силу нелинейности полинома в нем найдется член, содержащий не менее двух множителей. Без ограничения общности можно считать, что среди зтпх множителей присутствуют х, и х,. Тогда можно преобразовать полипом следующим образом: а,, „»,х»»... х», = х»хз/» (х„..., х„) + (»»" дз) + хА (хз ° ..1 хз) + хаУз (хз, ..., хл) +»»» (хз, ..., хз), где в силу единственности полпнома ~»(х„..., х„)за О.

Пусть а„..., сс. таковы, что Л(аз, ..., а.)= 1. Тогда »р (х„х,) = » (х„х,, а„..., а ) = х,х, + ах, + рхз + (, где а, р, т — константы, равные О илп 1. Рассмотрим функцию»р(х„хз), получаемую из»р(х„х,) следующим образом: »р(х„хз)»р(х, + Р, хз+ а)+ ар+ (. Очевидно, что »р(х,+р, х, +с»)+ар+'(= (х, + р) (х, + сс)+ а(х, + р)+ + р (хз+ сс) + ( + ар + т = х х,. 40 ч. ь Функционллънык снстВмы с опвэацнямн димых и достаточных условиях полноты. Итак, пусть ч! (г! гг °, ! — проиавольная система функций из Р,. Спрашивается, как выяснить, будет лн она полной или нет? Ответ на этот вопрос дает следующая теорема.