Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 21
Текст из файла (страница 21)
Тогда полученная в конце предыдущего параграфа булеза функция реализуется в виде интегрального модуля со схемой, изображенной на рнс. 2.4. Обозначим операцию, реализуемую этим элементом, Рис. 2Л как С)(а, 6, с, а) и рассмотрим алгебру высказываний вида (М, П), где М вЂ” логические высказывания и П(а, 6, с, а) = а(д Ч Ьс. Установим, можно ли любую булеву функцию /(хд, хэ, ..., х„) выразить в виде суперпозиции системы у' = 1П), как это возможно для случая системы (Ч, ас, Суперпозицией системы э = 1!Рд(хд! хэ! . ' ! хь!)! !Рэ(хд! хэ!...! хьэ)! ..! !Р((хд! хэ! . ! хь!)) называется любая функция /, полученная: а) из 3э (хд, хз, ..., хь,) переименованием переменных, <р Е,3; б) подстановкой вместо некоторых переменных функции фа(хд! х2, ..., Хьо) функций !ру(хд! Хэ,..., Хь ), !ра! !р Е У; в с помощью многократного применения пп.
а) и б). истема Я называется полной в РЬ, если любая функция / Е б Рь представима в виде суцерпозиции этой системы; система у' называется базисом, если полнота л теряется при удалении хотя бы одной функции, где Рь — (с-значная логика.
Выразим дизъюнкцию и отрицание через П(а, 6, с, с(); тогда согласно разложению Шеннона и закону де Моргана любую булеву функцию /(хд, хз, ..., х„) можно выразить через 3 = 1П)д ст = П((тэ (т, (д, а); сэ Ч (3 = (тсь Ч /3/3 = П(ст, (3, Д, (д) = = П(П((т, (т, ст, (т), /у, П((3, (3, (3,,3), П(а, (т, (т, (т)). В общем случае для установления полноты системы Я буле- вых функций /( (Я в Рэ) используют критерий полноты Поста- Яблонского.
Определим предварительно пять классов булевых функций. Классом Ко Булевых функций /((хд, хз, ..., х„), сохраняющих константу О, называется множество функций вила Щхд, хз, ..., х„)//((О, О, ..., О) = 0). Классом Кд булевых функций /((хд, хз, ..., х„), сохраняющих конспданпду 1, называется множество функций вида дь((хд хэ ° х )/ у((1 1 1) Ц На примере системы б = (О) рассмотрим тесты распаанаваиия !руикпий, обладающих этими свойствами: О(о, Ь, с, с() = Оь( ч Ьс, О(0,0,0,0) =ООЧОб=1Ч0=1, П(а, Ь,с,д) 4 Ка, С1(1 1 1 1) = 11 ч 11 = 0 Ч 0 = 0 П(а Ь с й) й К!. Классом К„линейных булевых функций /((хд, хз, ..., х„) на- зывается множество функций вида (( Яхд, хт, ..., х )/ Яхд, хэ, ..., х, ) = со 9 ~~ь с(х(1! 1 где дд( — знак операции сложения по модулю 2: 090 = О, 091 = 1, 190 сс 1, 191 ее О.
Установим, является ли булева !Уунккия О(а, Ь, с, !() линейной. Прекисло. иим, что она линейная и, следовательно, представима в виде П(а, Ь, с, И) =со 9е„а 9 сьЬ9с,с9сы(. Определим каэ!Р!Рипиент са: П(0, О, О, 0) = 1, по по предполаиению О(0, О, О, 0) = са. Следовательно, со = 1. Аналогично определим коэф$ипиеиты с, сь, с„сь, 4!икснруя соответствен- на наборы 1000, 0100, 0010, 0001.
Имееьс О(1,0,0,0)=1 ОЧО ° ОмОЧОтО, 19с„19сь О 9с, 09сь О = 19 с„, 19с„= О, с = 1; Н(0,1,0,0)=0 ОЧ1 Оээ1Ч1=1, 191 09сь ° 19 с, ° 09сь.О м 19сь, 19сь= 1, сь =0; Гл. 2. Матпема>пическал логика По 12.4. Полнота. Построение суперпозпций булевых функций 111 П(0 0 1 0) =О ОС>О Т=1ЧОю1 191'090'09сс'1Юсл'0 1Фс 1Фс 1 с 0" П(0,0,0,1)=0 1с>0 ОюОи0=0, 1Ф1 090 ОЮО ОФсл 1=0, 19сл=О> се=1. Подстввляя внвчения козффнктюигов в приведенное выше вырвиение, получаем П(а, Ь, с, а) = 1 Ф а Ф с1. Это равенства в кендой из остальных 11 точек не сохраняется. Действительна, в течке (1, 1, 1, 1) имеем п(1,1, 1, 1) =Т Тст1 о=оио=о, 19191-1, Оф1. Следоввтельио, сделанное предпююиение является неверным.
Функция П(а, Ь, с, д) нелвнейнея: П(а, Ь, с, >4) й К,. Классом самодвойстпвенных булевых функций Яхт, хт, ... ..., х„) называется множество булевых функций вида 1У>(Х1> Хт, ...> Хя)/ У(Х1> Х2,..., Хк) = Ус(Х1> Х2, ..., Хк)У'. Рассмотрим свойство семодвойственностн булевой функции П(а, Ь, с, а). Построим теблипу знвчеиий 2 х 2" (и ю 4), в ксторай в первой строке респолвгеются десятячные зквивеленты, соствегствующиенвборзм Х ю (а, Ь, с, сО, ва второй — внесения функции у(Х) = П(а, Ь, с, сО, которые соответствуют зтнм изберем. Таблица 2.15 Х 0 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 у Х 1 0 1 0 1 1 1 0 0 О 1 0 1 1 0 0 Функция самодвойстпвенная, если на любой паре противоположных наборов (наборов, сумма десятичных эквивалентов которых равна 2" — 1) функция принимает противоположные значения. Фупккия П(а, Ь, с, >1) ие является свмодвойстзепиай: С1(7) = П(8). Классом Кн монотпонных булевых функций Яхт, хэ, ..., х„) называется множество булевых функций вида (ут(Х1, Хт, ..., Х„)/ (Стт, От > ..., Ст„) ) (>71, Стэ, ..., ая) 4+ <-ь(ат>стс, 1=1,2,...,п)-+ ~ с (ст1> от» ' ая) ) У(о1> стт» сто)т.
Для тестирования функции П(а, Ь, с, ст) нв монотонность построим гиперкуб и кроеневизнруем распределение в нем знз сепий зтай функции (рис. 2.5). Если найдется хотя бы одно ребро, концем которого сопоставлены двои сиые наборы (о>,от,...,о,',) и (ос,ег,,о ) виде (а,',аз,...,сс„') > (ос,сст,...,>т„), для которых у(а;, оз,..., о'„) < у(о>, от,..., а„), та теквя булевв функция является немопетт~ной. Другими сввввин, в гиперкубе нзйдется хотя бы один О, нокрывзюший 1. 0011 Рис. 2.5 Рзссмзтрнвеемея булевв функция П(а, Ь, с, >1) иемонотоннвя (рнс. 2.5): (1,0,0, 0) > (0,0,0, 0), У(1>0,0, 0) (У(0>0,0,0). Критерий полноты. СисптемаЯбулевых функций ут являетпсв полной тпогда и тполько тпогда, когда выполняютпсд пятив условий.
"сущестпвуетп функция Д Е 5, не сохраняющая констпантпу О, ус ф Ко, 'функция ус Е Я, не сохраняющая констпантпу 1, Д (с К1, нелинейная функция, несамодвойстпвенная функция и немонотпонная функция в систпеме Я. Используя критерий полноты и метод Петрика, построим возможные базисы в Рт с нуль-, одно- и двуместными операциями. Построим все булевы функции от двух переменных (табл.
2.16). Таблице 2.18 Индекс з функциональной переменной 11, с = О, 1, 2, ..., 15, равен десятичному эквивалентному набору значений этой функции, читаемому сверху вниз. Приведем эти булевы функции: уо(х1, хэ) = Π— констпантпа О; Уг(Х1> Хэ) = Х1Х2 — КОНЪЮНКЦил> Гл. 2. Маадемаидичгсхая логика 112 Д 2.4. Полнота. Построение супероозииий булевых функций 113 ~2(хд> х2) = хдхэ = хд Ч х2 = хд -+ хэ = хд .<+ хз — леваю коимиликация (читается "не если хд, то хэ",' префикс ко — от лат.
сопдгегзив — обратный); тз(хд, х2) = х1хэ Ч х1х2 = х1, Яхь хэ) = хдхз — — хд ч хт = хд т= х2 — — хд + хт — правою коимпликация; ~з(хд, хз) = хдх2 Ч хдхт = хт', Д(хд, хэ) = хдх2 Ч хдхз — — хд йт хэ — сложение ио модулю 2 или функция неравнозначноспди, неэквивалентностпи; ут(хд, хт) = хд ч х2 — дизъюнкция; ~в(хд, хт) = Хдхэ = хд Ч хз — — хд о хэ — фунхцию Вебба; уэ(хд, хэ) = хдхт Ч хдхт = хд хэ — функция эквивалентности, равнозначности; Ло(хь Х2) = хт — отрицание; Удд(хь Х2) = хдхэчхдхтчхдх2 = хзчх = хд +- Х2 — прав ю имиликация (читается "если хз, то хд"); )12(хд, Х2) = хд — отрицание; удз(хд, х2) = хд хэ Ч хдхэ Ч хдхэ = хд ч х2 — — хд ~ хт — левая импликация (читается "если хд, то Х2"); т14(хд хт) хдхз Ч хдхз Ч хдхт хд Ч хз хд (хт функция Шеффера; Лз(хд, хт) = 1 — константа 1.
Для порождения всех базисов в Р2 построим двумерную табл. 2.17, каждой строке которой взаимно однозначно сопоставим Табанаа 2.17 одиннадцать функций (функции дз, ую, уз удо, удд не рассматриваем), столбцу — класс Ко (функции, сохраняющие константу 0), Кд (функции, сохраняющие константу 1), К„(линейные функции), К, (самодвойственные функции), К„(монотонные функций) и в клетке (д, 1) ставим 1, если д-я функция не принадлежит у'-му классу, в противном случае клетку (д, у) оставляем пустой.
Методам Петрика преобразуя мультипликативно-аддитивную форму в аддитивно-мультипликатнвную, порождаем все покрытия столбцов строками этой таблицы: (д Ч Й Ч т Ч п Ч р Ч г) (а Ч с Ч д Ч д Ч т Ч р) (6 Ч с Ч е Ч д Ч п Ч р) гс Ьс(ач6чсчдчечдчЬчиЧрчг)(счдчдчйчтчичр) = = (д Ч аЬ Ч йс Ч Ы Ч т Ч аи Ч сп Ч йп Ч р Ч аг Ч сг Ч гд() Й Ьс(ЬЧсЧеЧдЧиЧр)(сЧдЧдЧЬЧтЧпЧр) = = (д Ч аЬ Ч Ьс Ч Ы Ч т Ч ап Ч сп Ч бп Ч р Ч аг Ч сг Ч гд) Й Й (сЧд Ч п ЧрЧ 6НЧ ЬЬЧ 6тпЧ ед(Ч еЬ Ч ет) = = д Ч р Ч аЬЬ Ч Йс Ч аи Ч сп Ч Йп Ч аЬе Ч йЫ Ч Мед Ч ч тсч тп ч 6тчтеч сгч гЬбчгей = = д Ч р Ч Йс Ч ап Ч сп Ч д(п Ч тпс Ч пдп Ч 6т Ч те Ч Ч сг Ч аЬЬ Ч аЬе Ч ЙЬИ Ч Йес~ч гЬд Ч гед(. Каждое из полученных покрытий яд порождает базис В;: хд — — (д) е+ Вд — (о) — базис Вебба; хэ — — (р) М Вэ = (() — базис Шеффера; =(Ь, ) ~В =(,-); хю = (а, и) е+ Вю = (-+, 0) — и.мпликативный базис; тгз = (с, п) т+ Вз = (-+,- хе (д() тд) ++ Вв (~) 9)р кт — — (т, с) <+ Вт = (-, ) — коимпликативный базис; п'а —— (пд, и) гт Вв — — (-т, ) — имплихативный базис; кэ — — (6> т) <-т Вэ — — (Й, ) — хонъют(хтивный базис Буля; тгдо = (ид, е) гд Вдо = (вд, ) — дизъюнкпдивный базис Буля; тгы = (с, г) ++ Вд д — — (, 1) — коимиликатливный базис, тгд2 = (а, Ь, Ь) <-~ Вдэ — (, гтд, О); тгдз=(а, Ь, е)++ Вдз = (, Ч, 0); тгы = (Ь, Ь, д() ь+ В14 — (9, вд, хдв — — (Ь, е, д) т+ Вдз = (ддд, ч, а'щ = (г, Ь, т() д+ Вдв = (йт, ес, Ц вЂ” базис Жегалхина; ядт = (г, е, И) д-д Вдт = (йт, ч, 1).
Получено 17 базисов, в каждом из которых нельзя вычеркнуть ни одну функцию без потери полноты в Рт. Каждому сложному высказыванию в системе (Ч, Й, ) соответствует эквивалентное высказывание в любом из этих базисов. Например, высказыванию Гл. 2. Матгматичгскал логика 114 Рис. 2.б ане а или 6 и с" в импликативном базисе 1-+, 1 соответствует эквивалентное высказывание "если а, то не если 6, то не с": а ч Ьс са а ~ Ьс зт а ~ Ь ч с = а ~ (Ь -+ с) . Техническая реализация базисных функций может быть основана на использовании различных физических явлений, например, импликация и коимплнкация может быть основана на использовании магнитных явлений, а функции Шеффера и Вебба — на использовании явлений в полупроводниках.
Базисные элементы графически изображают в виде прямоугольников, в которых инверсные входы и выход изображают в виде незаштрихованных кружков и в верхнем правом углу ставят 1, если внешняя связка — дкзъюнкция, и Й, если — конъюнкция, за исключением сложения по модулю 2 (тогда сверху ставят М2) и эквивалентности (обозначают :†) (рис. 2.6,а). Более сложные элементы графически изображают в виде композиций перечисленных элементов на основе представления реализуемой этим элементом булевой функции в виде ДНФ или КНФ.
Например, рассмотренный выше элемент П(а, 6, с, с() графически можно представить в виде прямоугольника (рис. 2.6, б), соответствующего ДНФ функции П(а, Ь, с, а) = ас( Ч Ьс. Рассмотрим метод построения суперпозиций булевых функций в заданном базисе — метод непосредственного моделирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
