Новиков Ф.А. Дискретная математика для программистов (860615), страница 22
Текст из файла (страница 22)
В этом случае говорят, что формула7 реализует ф у н к ц и ю / :func 3 = f .ЗАМЕЧАНИЕДля обозначения реализуемости применяют и другие приёмы. Выбранное обозначениеобладает тем достоинством, что согласовано с другими обозначениями в книге.З н а я таблицы истинности для ф у н к ц и й базиса, можно вычислить таблицу истинности той функции, которую реализует данная формула.Примеры1.
Fi : = ( x i A х2) V ( ( ц A x2) VХ\0011Х20101х\ Лх20010х\Лх20100A x2))(xi A х2) V (xi А х2)0110Таким образом, формула F\ реализует дизъюнкцию.х\ Лх20001Fi0111114Глава 3. Булевы функции2. F2 : =(х\ А х2) —• х\XIх2Х\Лх2F20011010100011111Таким образом, формула F2 реализует константу 1.3. F3 : =((xiЛ х2) + х\) + х2Х\001х2010х\ Л х2000111(zi Л х2) + х\00((zi Л х2) + xi)10+х20111Таким образом, формула F3 также реализует дизъюнкцию.3.2.2. Равносильные формулыОдна функция может иметь множество реализаций (над данным базисом).
Формулы, реализующие одну и ту же функцию, называются равносильными:^=^ 3 / ( f u n c J i = / к funcJz = / ) •Отношение равносильности формул является эквивалентностью. Имеют место,в частности, следующие равносильности:1. а V а = а, а Л а = а.2. а V b = b V а, а Л б = бАа.3. а V (6 V с) = (а V b) V с, а Л (Ь Л с) = (а Л 6) Л с.4. (а Л 6) V а = а, (а V Ь) Л а = а.5. а V (6 Л с) = (а V 6) Л (а V с), а Л (b V с) = (а Л Ь) V (а Л с).6. а V 1 = 1, а Л 0 = 0.7. а V 0 = а, а Л 1 = а.8. ——| <i2 = а.9. ->(а Л Ь) = ->а V->(а V 6) = ->а Л ->Ь.10. а V ->а = 1, а Л ->а = 0.Все они могут быть проверены построением соответствующих таблиц истинности.
Таким образом, (£ 2 ; V, Л, ->) — булева алгебра (см. 2.5.5).3.2. Формулы115ЗАМЕЧАНИЕВвиду выполнения равносилыюстей 2 и 3 для кратных дизъюнкций и конъюнкций используются следующие обозначения:п\у /п/\XiAi-1DefV / . . . Vw Хп,= xi Vг=1Def= Xi Л ••• Л xTL.3.2.3. Подстановка и заменаЕсли в формулу 3 входит переменная х, то это обстоятельство обозначаетсятак: Э г (... х .
. . ) . Соответственно, запись Э г (... S • • •) обозначает, что в формулуЭ входит подформула S- Вместо подформулы (в частности, вместо переменной) в формулу можно подставить другую формулу (в частности, переменную),в результате чего получится новая правильно построенная формула. Наряду соборотом «подставить подформулу в формулу» используется оборот «заменитьподформулу формулой». Если подстановка формулы 9 производится вместо всехвхождений заменяемой переменной х (или подформулы), то результат подстановки обозначается следующим образом: Э г (... х . .
. ){3//х}. Если же подстановкапроизводится вместо некоторых вхождений (в том числе вместо одного), торезультат подстановки обозначается следующим образом: Э г (... Si • • • HS2/S1}.Примеры1. Замена всех вхождений переменной: х V ~>х{у А г / / х } = (у A z) V ->(у A z).2. Замена всех вхождений подформулы: х V у V z{->x//yV zj — х V ->х.3. Замена первого вхождения переменной: х V ->х{у/х} = у V -*х.4. Замена первого вхождения подформулы: х V у V z{-^x/y V zj = х V ->х.Известны два правила: правило подстановки и правило замены,— которые позволяют преобразовывать формулы с сохранением равносильности.1 (Правило подстановки) Если в двух равносильных формулах вместовсех вхождений некоторой переменной х подставить одну и ту же формулу, тополучатся равносильные формулы:ТЕОРЕМАV3№ ( .
. . * . . . )= Э 2 ( . . . У1( . . . Я . . . ) { 9 / / ® }=5,2(...®...){9//®}).Чтобы доказать равносильность двух формул, нужно показать,что они реализуют одну и ту же функцию. А это можно сделать, если взять произвольный набор значений переменных и убедиться, что значения, полученныепри вычислении формул, совпадают.ДОКАЗАТЕЛЬСТВОРассмотрим произвольный набор значений а\,..., аХ}..., ап переменных x i , .
. . ,х,..., хп. Обозначим а: = Eval(S, F, а\,..., ах,..., ап). По определению алгоритма интерпретацииE v a l ( J i { S / / x } , F , a i , . . . , ах,...,ап) = Eval(Ji, F, а ь . . . , а , . . . , а п )116Глава 3. Булевы функциии, аналогично,Eval(^2{S//ic},i^,ai,...,ax,...,an) = E v a l ^ , F , a b ... , a , .
. . ,an).Ho J i = 3*2, и значит,E v a l ( 3 " i , F , a i , . . . , a , . . . , a n ) = Eval(J 2 , F, a b . . . , a , . . . , a n ) ,откудаEval(U'i{S//z}, F , a b . . . , a x , . . . , a n ) = Eval(J 2 {S//x}, F, fll, . . . ,j • • • ) O-nЗАМЕЧАНИЕВ правиле подстановки условие замены всех вхождений существенно: например, x\f-*x = 1и i V -1 х{у//х}=уУ —*у = 1, но х V ->х{у/х} = у V -IX Ф 1!Т Е О Р Е М А 2 (Правило замены) Если в формуле заменить некоторую подформулуравносильной формулой, то получится формула, равносильная исходной:V 7 ( . .
. 9i • • •) (Si = 92 = > Я..Si • • •) = Я • • Si • • • MS2/S1}) •Рассмотрим произвольный набор значений а\,...,ных x i , . . . , хп. Имеем Si = S2» и значит,ДОКАЗАТЕЛЬСТВОап перемен-Eval(Si, F, a i , . . . , а„) = Eval(S 2 , F, a i , . . . , a„),откудаEval(J{Si/Si}, F, a i , . . . , a„) = Eval(3"{S 2 /Si}, F, a b . . . , an).•Пусть F = { / I , .
. . , / m } И G =Тогда говорят, что формулы J[F]и S [G] имеют одинаковое строение, если J совпадает с результатами подстановкив формулу S функций /г вместо функций gi:3.2.4. Алгебра булевых функцийБулевы функции V, А, (и любые другие) могут рассматриваться как операциина множестве булевых функций, V , A : ? n x P n - > Рп, ->: Рп —• Рп.Действительно, пусть формулыи J 2 равносильны и реализуют функцию / ,а формулы Si и S2 равносильны и реализуют функцию д:funcSFi = / ,funcS^ - / ,funcSi = д,funcS 2 - <?•Тогда, применяя правило замены нужное число раз, имеем:3*1 V S i = J 2 V S2, ^ A S i = ^ 2 A g 2 ,=-.У2.Таким образом, если взять любые формулы 7 и S, реализующие функции / и дсоответственно, то каждая из формул J А 9, 7 V S иреализует одну и ту1173.2.
Формулыже функцию, независимо от выбора реализующих формул J и S- Следовательно,функции, которые реализуются соответствующими формулами, можно по определению считать результатами применения соответствующих операций. Другимисловами, еслиfunc= /,func 5 = 9,тоf Ад =f func (У AS),} У 9U= func(J V S),func(^F).Алгебраическая структура (Pn; V,A,->) называется алгеброй булевых функций.ТЕОРЕМААлгебра булевых функций является булевой алгеброй.Действительно, пусть равносильности, перечисленные в подразделе 3.2.2, проверены путем построения таблиц истинности. Ясно, что этитаблицы не зависят от того, откуда взялись значения а, Ь, с.
Таким образом, вместо а, Ь, с можно подставить любые функции, а значит, любые реализующие ихформулы, если только выполнено правило подстановки. Следовательно, аксиомыбулевой алгебры выполнены в алгебре (Р п ; V , A , - > ) .•ДОКАЗАТЕЛЬСТВОПусть [3] — множество формул, равносильных (то есть класс эквивалентностипо отношению равносильности). Рассмотрим множество % классов эквивалентности по отношению равносильности: % = {[3]}^. Пусть операцииV , A : X х ft ^К,определены (на множестве классов эквивалентности формул по отношению равносильности) следующим образом:ИV [ЗУ = f [Ji V У2], [Ji] А [У2][Ji A y 2 ], -пр-i] = f ЬУ 2 ].Тогда алгебра классов равносильных формул (ОС; A, V, —>) (алгебра ЛинденбаумаТарского*) изоморфна алгебре булевых функций и является булевой алгеброй.Носитель этой алгебры — множество классов формул.ОТСТУПЛЕНИЕНа практике мы говорим о функциях, а пишем формулы, хотя формулы и функции —разные вещи.
Например, формул бесконечно много, а функций (булевых функций п переменных) — только конечное число, и свободная алгебра формул не изоморфна алгебрефункций. Но алгебра функций изоморфна алгебре классов равносильных формул, чтопозволяет манипулировать формулами, имея в виду функции.1Альфред Тарский ( 1 9 0 2 - 1 9 8 4 ) .118Глава 3.
Булевы функции3.3. ДвойственностьПонятие двойственности с успехом применяется в самых разных областях математики. Мы рассматриваем двойственность на простейшем примере булевыхфункций.3.3.1. Двойственная функцияПусть / ( х 1 , . . . , хп) е Рп — булева функция. Тогда функция / * ( ® i , . .
. , хп), определённая следующим образом:/ (xi,...,xn)= f{x\,...,хп),называется двойственной к функции / .Из определения легко видно, что двойственность инволютивна: f** = / , и поэтой причине отношение «быть двойственной к» на множестве булевых функцийсимметрично, то есть если /* = д, то д* = / .Если в таблице истинности булевой функции / инвертировать все значения, тополучим таблицу истинности двойственной функции /*.ПримерХ\ Х2 Х\ A Х20001001 00111Х\1100Х2 (xi Лх 2 )*11101100=Xi0011х20101(xi Лх 2 )*0111Таким способом можно определить двойственную функцию для любой булевойфункции.Пример/ГДвойственные функции:10х\ V х 2 xi Л х 201xi Л х 2 xi V х 2XXXXФункция называется самодвойственной, если /* = / .Пример Тождественная функция и отрицание самодвойственны, а дизъюнкция и конъюнкция — нет.3.3.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
