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

е. значение «основания» равно значению «показателя». Теорема 3 (о рвало>кении функций по переменным). Каждую Яункь>ию алгебры логики Г'(хо ..., х„) яри любовь яь (1 < >л < а) иажяа представать е еа ч. 1. ФункциОнАльные снстемы с Опеглциями следующей форме: ~(Х1! ..., Хт! Хи+11 °, Ха)- Х,' 8! ... 8! Хи '" Ь ДО1!... ! О„, Х„+1,..., Ха), (а) где дизъюнкцил берегся по есееозможным наборам значений переменных х„..., х . Это представление называется разложением функции по тл переменныи х„..., х . Д о к а а а т е л ь с т в о. Рассмотрим произвольный набор аначенпй перемепных (а„..., аа) и покажем, что левая и правая части соотношения ( ° ) принимают на нем одно и то же значение.

Левая часть дает 1(а„... ..., а.). Правая— ( ~ а!181 ... да '"81~(о„...! о ! а +„..., а„) !"11 81 ° ° ° 81 а»! 81 | (а1! ... ! аа!! аа!+1! ° ° ° ! аа) а а'!а ~(а11...! аа). В качестве следствий получаем два специальных случая рааложения. 1) Разложение по переменной: 1(Х!! ! Ха-!! Ха) Х„Ы(х„.. а х„„() Ч х„д! |(х„..., ха „О). ФуНКцИИ ДХ„..., Х„„О) И ~(Х„..., Ха 1, 1) НаЗЫВаются компонентами разложенил. Данное разложение полезно, когда какие-либо свойства булевых функций устанавливаются по индукции.

2) Разложение по всем и переменным: у(Х1, ° °, Ха) („) Х 81 ... 81 Х„а 81 ~(0„..., 0»). При ~(х„..., х.)Ф О оно может быть преобразовано: х,' 81 ... 81 хаа 81 ~ (о„..., о») (»1 - '!а) Ч хе! 8! ... 8; хаа. (а1,...,а») 1(аг, ,тза) 27 Гл. ь ллгевгл логики В результате окончательно получим 1(х1 ° ° х)= Ч х Д ...дх„". ("") (оо...,о„) !(о1 " оо)=г Такое разложение носит название совершенной дигъюнктивной нормальной формы (совершенной д. н. ф.).

Непосредственно к понятию совершенной д. н. ф. примыкает следующая теорема. Теорема 4. Каждая функцил алгебры логики может быть вьгражена в виде формулы нерее отрицание, конъюнкцию и дигъюнкцию. Доказательство. 1) Пусть Дхо ..., х„) О. Тогда, очевидно, 1(хо ° ° .> хо) = х~ 4 хо 2) Пусть )(хо ..., х„) Ф О.

Представим ее в совершенной д. н. фл )(х» ... х ) Ч х01дг ... Ахол, (оо ...,о„) 1(о1 - хм)еа Таким образом, в обоих случаях функция 1 выражается в виде формулы через отрицание, конъюнкцию и дизъюнкцию. Итак, оказалось, что любую булеву функцию можно задать формулой над 9, взяв в качестве $ множество, состоящее из трех функций: отрицания, конъюнкции и дизъюнкцпи. Данная теорема носит конструктивный характер, так как она позволяет для каждой.

функции фактически построить формулу, ее реалпзующую (в виде совершенной д.н.ф.): в таблице для функции Дхо ..., х ) (~ге 0) отмечаем все строки (о„..., а ), в которых ~(о„..., о ) =" $; для каждой такой строки образуем логическое проиаведение хог д, д хоп и затем все полученные конъюнкции соединяем знаком дизъюнкции. П р и и е р $0. $) Найти совершенную д. н. ф. для функции х, - х.. 23 ч. 1. ФункцпонАлш1ые системы с опеРАцняын Мы имеем трн набора (О, 0), (О, 1) и (1, 1), на которых эта функция равпа 1 (см.

табл. 3). Поэтому о о о х1-+ х = х, 1с хо ')/ х, д х, )/ х, д х, х, Д х, )/ х, й х, ~/ х, Д х,. 2) найти совер1пенную д. н. ф. для функции, заданной табл. 7. Имеем 1(хо хь хо) х,хохл '/*,хохл ~/х~хохо 7х<хохо. Совершенная д. н.ф. есть выражение типа ХП, т. е. а1 логическая сумма произведений хо . Спрашивается, нельзя ли для булевых функций получить разложение типа Таблица 7 л, 1(ха л„лп О О О О О 1 О 1 О О 1 1 О О 1 О 1 О 1 1 1 ПХ? Покажем, что прн 1 чь 1 это возможно, для чего рааложнм функцию )о (очевидно, )а оеО) в совершенную д. н.

ф.: а1 ал ~ ( ° ° ° ) Ч (О1, ° ° ал) 1л(а1,.,ал) 1 Возьмем тождество для двойственных формул 1 (ххо ° ~ ° о хл) бо (х1 ~/ ° ° ° )/ хл ). (а1 " ол) 1л(а1,...,ол) 1 Рл. 1. Алгквгл логики 29 Левая часть есть )(хн ..., х„), а правая может быть преобразована далее: б, (х', Ч".Ч".)- 8 (х Ч... Ч..'")- (аь,...,о„) (оь,...,о„) Ьа(оь,...,о„) ь /(а,,...,ао)=0 л, (х~ь')/ ... ')/ х~а). (аь,...,оо) !(оь,...,ао)=а Таким образом, получаем разложение ~(хь, ..., х„) бь (х,' ~/ ... ')/х„",). (оь " оа) Ь(аь,....оа) =а Это выражение носит название совершенной коньюнктивной нормальной форлььь (совершенной к.

н. ф.) . Пример 11. 1): Построить совершенную к.н. ф, для функции х, — х,. Имеем х, -~. х, = х, ь/ х, — х, )/ хз р о 2) Построить совершенную к. н.ф. для функции 1(хо х„х,), ааданной табл. 7. Имеем ~(х„хь, х,)=(х, Чхь7хь) (х, Ч х, ~! х,)Х Х(хь Чх,Ух ) (х, Чхь Чха). Итак, в качестве средства для задания булевых функ- ций наряду с таблицами можно использовать язык фор- мул над множеством функций, состоящим из отрицания, конъюнкции и диаъюнкции.

Поскольку табличный язык по громоздкости примерно эквивалентен языку совер- шенных .д.н.ф. (совершенных к.н.ф), то можно ут- верждать, что язык формул, использующий отрицания, конъюнкции и дизъюнкции, не хуже языка таблиц. Мож- но показать, что на самом деле он существенно лучше табличного языка. Для пояснения рассмотрим функцию ь(хо '' у хьь) х!Ч... /хйО, Данная формула в правой части насчитывает 39 симво- лов (20 символов переменных и 19 символов о'), таб- лица для 1(х» ...> х„) содержит 2", т.

е. более мил- лиона строк. ЗО Ч. 1. ФУНКЦПОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦПЯЫИ в 5. Полнота н замкнутость Выше мы видели, что всякая функция алгебры логики может быть выражена в виде формулы через элементарные функции х, х,дгх, и х, !/х,. В связи с этим возникает вопрос, в какой мере является случайным наличие таких систем элементарных функций7 Сейчас мы не собираемся давать исчерпывающего ответа иа поставленный вопрос, а лишь покажем, что такого рода свойством обладают и некоторые другие системы влементар« ных функций.

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

Теорема 5. Пусть даны две системы функций из Р;. В=((о Ь, ".), (1) (~ = (уо уь ...), (П) относительно которых известно, что система 1 полна и каждая ее функция выражается в виде формулы через функции системьь 11. Тогда система П является полной. Доказательство. Пусть й — произвольная функция ив Р,. В силу полноты системы 1 можно выразить Ь формулой над $, т.

е. й=с[1~~ 6~" ~ 1.~ ° 1 (в скобках мы выписываем все функции системы $, хотя в формуле фактически встречается лишь конечное их число). По условию теоремы (,-С,[у„ум ...1 (.=С,(уь у., з( гл. з. Алгевга логики Поэтому мы можем в формуле С[1„)„...] исключить вхождения функций ~„1„..., заменив их формулами над 0е). Это можно записать так: С[(„(„...] - С[С,[д„д„...], С,[б„дм ...], ...]. Последнее выражение определяет формулу над 0 со строениеы С'. Мы получаем С[сз[бзз бзз ° ° ], Сз[бзз Уз, ° ° .], ° ° ] С [Уо Узз ° ° ]з илн, окончательно, й=С [до дм ...], т, е. мы выразнлн й в виде формулы над О.

Теорема докааана. Опираясь на эту теорему, можно установить полноту еще ряда систем и тем самым расширить список примеров полных систем. 3. Система з3 = (х, х,8гхз) является полной. Для доказательства возьмем аа систему 1 систему 2 (стр. 30), а за систему 11 — систему 3 и используем тождество х, Чх, У,8зУ„ которое вытекает из свойств 4 элементарных функций. 4. Система $ (х, х, Чх,) является полной. Этот факт доказывается либо аналогично предыдущему, либо через принцип двойственности. 5.

Система зз (хз/хз) является полной. Для доказательства эа систему 1 возьмем систему 3, а за систему 11 — систему 5. Легко видеть, что хзlхз=У„(хзlхз)l(хзlхз) х,lх, х,8гх,. 6. Система $=(0, 1, х,хз, хз+хз) является полной. «) Не всегда эти замены можно произвести все одновременно, так как прн замене, вообще говоря, могут возникнуть новые вхождения символов (зуь ... Например, если й лз азль лз из Чль гз лз+ ль в = лз сз (аз аз аз) то зз = аз бз лз аз+ гз+ (лз Чаз), сз сз (аз Ь аз) = аз+ (аз аз гз) + (гз Ч (лз аз аз)) *з -(- *а+ *а+ (лз Ч лз) + (*з Ч (*з + аз + (лз Ч аз) ) ) 32 ч. 1.

Функпконлльные системы с опеглщ<ями Для доказательства опять за систему 1 возьмем систему 3, а за систему П вЂ” систему 6. Мы имеем х,+1-хм хх, х,д»х,. Так как формула, построенная из констант О, 1 н функций х,х, и х,+ х„после раскрытия скобок и несложных алгебраических преобразований переходит в полинам по <но»(2, то мы получаем следующую теорему, принадлежащую И. И. )Кегалкину. Т е о ре и а б, Каждая функция иг Р, может быть выражена при помощи полинома по <пой 2 (полинома Жегалкина) .

Подсчитаем число полияомов Жегалкпна от перемепных х„..., х, т. е. число выражений вида а,, „;,х<,„,х»,. (<1.-.,»$) Число членов х»,... х<, равно количеству подмножеств (1„..., <,) из и чисел (1, ..., и), т. е. 2". Поскольку а» .. < равно О или 1, ис<»омое число поликанов равно 2™, т. е. числу всех булевых функций от тех же первменных. Отсюда, как следствие, получаем единственность представления функций посредстеом полиномое Жегалкина. П ример 12. Выразить х, Чх, в виде полинома Жегалкина.

Ищем выражение для х, Чх, в виде полннома с неопределенными коэффициентами: х, Ч х, = ах,х, + Ьх, + сх, + А При х, =х,=О имеем О д, при х, =О, х,= 1 имеем 1 с, при х, 1, хи О имеем 1-Ь, при х, х, 1 имеем 1 а+Ь+с, т. е. а 1. Мы получаем х, Ч х, = х,х, + х, + х,. Из приведенных примеров видно, что суп<ествует целый ряд полных систем.