Дискретная математика (998286), страница 15
Текст из файла (страница 15)
Замена всех вхождений переменной: х ч х(д л г//х) = (д д з)ч (д л г); 2. замена всех вхождений подформулы: хч дчг( х//дчз) = х ч х; 3. замена первого вхождения переменной: х ч ~х(у/х) = у ч х; 4. Замена первого вхождения подформулы: х Ч д Ч х( х/у Ч г) = х Ч х. Правило подстановки: если в равносильных формулах вместо всех вхождений некоторой переменной х подставить одну и ту же формулу, то получатся равносильные формулы: Ч 9 (Уг (...
х .... ) = Уг(...х... ) =ь Уг (... х... ) (9//х) =, Уг(...х... )(9//х)). ЗАМЕЧАНИЕ В правиле подстановки условие замены всех вхождений существенно: например, хч х = 1 и х ч х = 1(в//х) = к ч в = 1, но х ч х(д/х) = в ч х у1 1! Правило замены: если в формуле заменить некоторую подформулу на равносильную, то получится равносильная формула: ЧУ(. " 9г. ) 9г = 9г =ь У(...9г...) = У( 9г " )(9г/91).
Пусть Р = (/„..., У ) и С = (д„..., д ). Тогда говорят, что формулы У[Р[ и 9[С] имеют одинаковое строение, если У совпадает с результатами подстановки в формулу 9 функций /у вместо функций д;: У[Р) = 9[С)(/у//дг);=,. 3.2.4. Алгебра булевых функций Булевы функции Ч, д, (и любые другие) являются операциями на множестве булевых функций Ч, д: Р„х Р„-+ Р„,: Р„-у Р„. Действительно, пусть формулы Уг и Уг равносильны и реализуют функцию У, а формулы 9г и 9г равносильны и реализуют функцию д: 6гпсУг =/, 6шсУг = /, йгпс9г = д, гппс9г — — д. Тогда, применяя правило замены нужное число раз, имеем: Уг Ч 91 — Уг Ч 9г~ Уг Л 9г = Уг Л 9г~ Уг — ~чг Таким образом, если взять любые формулы У и 9, реализующие функции У и д, соответственно, то каждая из формул У Л 9, У Ч 9 и - У реализует одну и ту же функцию, независимо от выбора реализующих формул У и 9.
Следовательно, Глава 3. Булавы функции функции, которые реализуются соответствующими формулами, можно цо определению считать результатами применения соответствующих операций. Другими словами, если йшсд =,(, бгпс9 = д, то .Г Лд:=бгпс(в Л 9)Г,Г Ч д:=йшс(ГЧ Я), -(. "=бас(-,У) Алгебраическая структура (Р„; Ч, Л, - ) назыпается алгеброй булевых функций. Алгебра булевых функг[ий является булевой алгеброй. Действительно, пусть равносильности, перечисленные в подразделе 3.2.2, проверены путем построения таблиц истинности. Ясно, что эти таблицы не зависят от того, откуда взялись значения а, Ь, с.
Таким образом, вместо а, Ь, с можно подставить любые функции, а значит, любые реализующие их формулы, если только выполнено правило подстановки. Таким образом, аксиомы булевой алгебры выполнены в алгебре (Р„;Ч, Л, ). Пусть ٠— множество формул, равносильных з (то есть класс эквивалентности по отношению равносильности). Рассмотрим множество Х классов эквивалентности по отношению равносильности Х: =([Щю Пусть операции Ч, Л: Х х Х -+ Х,: Х -Ф Х определены (на множестве классов эквивалентности формул по отношению раве посильности) следующим образом: [д;[ЧРг[:=[к, ЧЗ;1, Р,[ЛР;[:=Р;ЛЗ;[, -Щ:=[-К,] Тогда алгебра классов равносильных формул (Х; Л, Ч, - ) (алгебра ЛинденбаумаТарского) изоморфна алгебре булевых функций и является булевой алгеброй. (Носитель этой алгебры — множество классов формул.) ОТСТУПЛЕНИЕ На практике мы говорим о функциях, а пишем формулы, хотя формулы и функции — разные вещи.
Например, формул бесконечно много, а функций только конечное число, и свободная алгебра формул не изоиорфна алгебре функций. Но алгебра функций изпморфна алгебре классов равносильных формул, что позволяет манипулировать формулами, имея в виду функции. 3.3. Принцип двойственности Пусть Г" (хг,..., х„) Б Є— булеза функция. Тогда функция г '(хы..., х„)1 опре- деленная следующим образом: у"(х,,...,х„):=у(Н„...,х„), называется двойственной к функции у. Из определения видно, что дяойствеиность инволютивна: у*" = 1.
87 3.3. ПРинцип двойственности Прыаавр Двойственные функции: у 1 О х1'ч'хз хг Лхз х Н У О 1 хг Лха хг мха х Функция называется самодвойственной, если у' = у. Прмааер Тождественная функция и отрицание самодвойственны, а дизъюнкция и коньюнкция — нет, ЗАМЕЧАНИЕ Далее используется обозначение: т( ):=у( ), ТЕОРЕМА Если функция у(хы..., х„) реализована формулой г (гг(хы...,хп)~ ° ° ° 1Уп(хг ° ° - х~)) то формула у*(д (хы..., х„),..., д(хм..., х„) ) реализует функцию р" (хм..., х„). у*(х„...,х„) = ~р(х„...,хв) =7(Л(хм...,х„),...,Ув(Е„...,х„)) = = У(7,(ХЫ...,Х„),...,(т"„(Ем...,ки)) = =У(гг (хы * ) г (хы . х ))= = ~*(Д(х„..., х„),..., Д(хы..., х„)).
П ТЕОРЕМА (Принцип двойственности) Пусть Р = (Ум..., У ). Пололсим Р': =(у*,..., у' ). Тогда если формула у над базисом Р реализует функцию У, то формула з' над базисом Р", полученная из формулы У заменой функций г'; на двойстпвенные функции уг", реализует функцию У*: йгпсУ[Р] = у =~ Гипс У" [Р"] = у', где У" [Р"]: = з[Р]Ц;((Я,, Доказательство Иидукцня по структуре формулы У. База: если формула у имеет вид Дхм...,х„), где г' е Р, то формула Я = г *(хы..., х„) реализует функцию )'" по определению.
Индукционный переход по предыдущей теореме. П 88 Глава 3. Булавы функции ОТСТУПЛЕНИЕ Хорошо известен принцип математической индукции для натуральных чисел: (Р(1) й(Р(п) =Е Р(п + 1))) =Ф Чп Б )Ч Р(п). Этот принцип является справедливым и для других множеств, упорядоченных более сложным образом, нежели натуральные числа. Например, в доказательстве предыдущей теоремы был использован принцип математической индукции в следующей форме Пусть задана некоторая иерархия (ориентированное дерево). Тогда если 1, некоторое утверждение Р справедливо для всех узлов иерархии нижнего уровня (листьев дерева) и 2. из того, что утверждение Р справедливо для всех узлов, подчиненных данному узлу, следует, что утверждение Р справедливо для данного узла, то утверждение Р справедливо для всех уалов иерархии (дерева).
СЛЕДСТВИЕ зг — — Эз =ь Эг" —— аз". Пример Из ххг гД хз = Ег Ч Ез по пРинЦипУ Двойственности сРазУ имеем хг 'г хз = хг Л Ез. 3.4. Нормальные формы В данном разделе на примере булевых функций обсуждается важное понятие анормальной формы», то есть синтаксически однозначного способа записи фор- мулы, реализующей заданную функцию. 3.4.1. Разложение булевых функций по переменным Пусть хз: = х . р ь' х у (здесь обозначает конъюнкцию).
Очевидно, что ТЕОРЕМА (О разложении булевой функции по переменным) г(хг,...,х,х +г,...,х„) = — у/ х~г' Л ° Лха д у(аг,...,апъ~хгь+ы '~хе)~ ( к,-, ) где дизьюихцил беретсл по всем возможнььи наборам (аг,..., а ). е , р = О, у=1, 11, х=р, х"= х"=хщу. (О, х~р, 89 Зли Нормальные формы Доказательство ( ~/ х1' Л" Лх~д ЛУ(о1~",о~ц,хп,+1,,хь))(а„...,а„) ж (о-, ) ~/ а1' Л .Ла„, Л((ог,...,о„„а,„+1,...,а„) = ,(ат -,» ) =а1' Л ° ° Л а„" Л Ца1,...,аа„а,„+1,...,ал) = ((а1,...,а„). ЗАМЕЧАНИЕ Здесь доказывается, что некоторая формула реализует заданную функцию»Для этого достаточно взять нроизвсльный набор значений аргументов функции, вычислить на атом наборе значение формулы, и если оно окажется равным значению функции на этом наборе аргументов, то из этого следует доказываемое утверждение.
СЛЕДСТВИЕ ,((х1,...,х„г,х„) = х„л у(х1,...,х„1, 1) )т х„л ((х1,...,х„1,0). СЛЕДСТВИЕ ((хг,..., х„) = 1)/ х1»' Л - Л х»" Л-,((ог,...,о„). у(ао...,а„) =1 3.4.2. Совершенные нормальные Формы Представление булевой функции у(х1,..., х„) в виде Ч х'Л ° Лх" 1 и называется совершенной дизьюнктивной нормальной формой (СДНФ).
ЗАМЕЧАНИЕ СДНФ называется совершенной, потому что каждое слагаемое в дизъюню(ии включает все переменные; дизьюпктивной, потому что главная операция — дизъюпкция, а почему она называется нормалыюй, объяснено в следующем отступленпи, ТЕОРЕМА Всякол булева функция (кроме 0) имеет единственную СДНФ. Доказательство У(х„...,х„) = )/ х»' Л" Лх»- Л((ото..,о„) = »т ...,» )/ х ' л . л х„" л г(»1,...,о„).= т(ао...,а )=1 1 — 1тт ха' Л ° Л х»". П У(ао.„,» )=1 90 Глава 3. Булавы функции ТЕОРЕМА Всякая булеза функция может быть выражена через дизьюнкцию, коныонкцию и отрицание: УУ Б Р» ЭУ[)1/,Л, )] [( = йтпс9.
ДОКАЗАТЕЛЬСТВО Если )' = О, то 0 = х д х. Если Г ф О, то см. предыдущую теорему. ТЕОРЕМА Всякая булеза функция (кроме 1) может быть единственным образом выражена е виде совершенной коиьюнктивной нормальной формы (СКНФ)1 Г[хг,...,х„) = )'11 х,' У... 1/х„". Г ц еь...,ь„) =1 ДОКАЗАТЕЛЬСтво Но принципу двойственности из предыдущей теоремы. ОТСТУПЛЕНИЕ . Говорят, что некоторый класс формул Х имеет нормальную форму, если существует другой класс формул Х', которые называются нормальными формами, такой что любая формула класса Х имеет единственную равносильную формулу из класса Х'. Наличие у класса формул нормальной формы очень редкое, сильное и полезное свонство.
Опо обеспечивает разрешимость, то есть наличие алгоритма проверки равносильности. Один и тот же класс Х может иметь несколько различных нормальных форм, то есть несколько различных классов Х'. 3.4.3. Построение СДНФ СДНФ булевой функции может быть построена по заданной таблице истинности с помощью следующего алгоритма. Алгоритм 3.2.
Построение СДНФ Вход: вектор Х: аггау [1зм) о( агний идентификаторов переменных, матрица и: аггау (1..2",1..п] о! 0..1 всех различных наборов значений переменных, вектор Р: аггау [1..2"] о( 0..1 соответствующих значений функции. Выход: последовательность символов, образующих запись формулы СДНФ для заданной функции. ): = Га1зе ! признак присутствия левого операнда дизъюнкции ) Гог 1 Ггое 1 то 2" до 1Т Р[!] = 1 Г1геп гт г" Гйеп у!е1д Ъ' 1 добавление в формулу знака дизъюнкции ) е)зе 1: =Сгне епд Ы д: =Га!зе ( признак присутствия левого операнда конъюнкции ) 91 3.4. Нормальные формы рог.г Егош 1 го и Йо Е д тЬеп у!е!Й 'Л' ( добавление в формулу знака конъюнкции ) е!эе д: =стае епд !Е )Е У[(,,у] = 0 ГЬеп у!е!д ' ' ( добавление в формулу знака отрицания ) епг! !Е , у!е!и Х[Я ( добавление в формулу идентиФикатора переменной ) епб Еог епд Е епй Еог ЗАМЕЧАНИЕ Если зафиксировать порядок перечисления переменных в таблице истинности н порядок перечисления кортежей значений, то алгоритм построения СДНФ дает синтаксически однозначный результат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
