Дискретная математика (998286), страница 17
Текст из файла (страница 17)
Пусть ~,~„...,)'„е Т, и Ф = ~(~~(хм...,х„),...,Яхы...,х„)). Тогда Ф' =У'(Д(хм...,х„),..., У'„'(хм...,х„)) = =у'(Яхм...,х„),...,У„(хм...,х„)) = Ф. Следовательно, Ф е Т.. 4. Пусть |,Л,.:.,У„Е Тя и Ф = У(Л(х„...,х„),...,1„(ха,...,х„)). Тогда а <;9 =ь(~,(а),...,~„(а)) < (Я)у),...,~„(13)) =ь =«~(Л(а),..., ~„(а)) < У(6~(1у),..., У„()3)) =~ Ф(а) < Ф(1у). Следовательно, Ф е Тя. 5. Пусть ~, ~м..., Д„, е Ть и Ф = Щ~(хм..., х„),..., У„(х„..., х„)). Тогда у' =се+ с~хг + + с х„, у~ =са + с, хг + ° ",+ с„х„, 1 1 1 ~„=се +с"х~+ . +с,",х„. Подставим эти формулы в формулу для Ф.
Имеем: Ф(хы..., х„) =са + сг(се + с~х~ + + с„'х„) + " + с (с~ + с",хг + ° " + сл) = =пе+4гхг+ "+Н х„. Следовательно, Ф е Ть. Пример Таблица принадлежности некоторых булевых функций рассмотренным замкнутым классам: Глава 3. Булеаы функции т т т тс т + + хг Лхе Таким образом, рассмотренные классы попарно различны, не пусты и не совпа- дают с Р„. 3.6. Полнота Класс функций Р называется полным, если его замыкание совпадает с Р„;.
[Р] = Р„. Другими словами, множество функций Р образует полную систему, если любая функция реализуема в виде формулы над Р. ТЕОРЕМА Пусть заданы двв системы функций: Р = (Цм..., 1 ) и С = (ды..., дь). Тогда, если система Р полна и всв функции из Р реализуемы формулами над С, то система С также полна; ([Р] = Р„йг Угг,б = 1цпс 9г [С]) =ь [С] = Р„.
Доказательство Пусть Ь вЂ” произвольная функция, Ь Е Р„. Тогда [Р] = Р„=ь Ь = 6шс 9[Р] =ь У(9гОЯ вЂ” формула над С. Следовательно, Ь = Йшс 9[С]. П Пример Система (м, л, ) — полная, как показано в подразделе 3.4.2. Следовательно, 1. система (, Л) полная, так как хг уг хг = - ( х, Л хз); 2. система (,Н) полная, так как хг л хг = — (- хг уг — хз); 3. система (Ц полная, так как. х = х [ х, хт лайз = (хг ] хг) = (хг ] хз) ] (хг ] хз): 4. система (0,1, Л, +) полная, так как х = х+1 (здесь + означает сложение по модулю 2).
Представление булевой функции над базисом (О, 1, л, +) называется полиномом Жвгалгзгна. Таким образом, всякая булева функция представима в виде а;„з.хц ... х;., Е 01,...з ) где Š— сложение по модулю 2, знак . обозначает конъюнкцию и ац;, Б Ез. 3.6. Полнота ТЕОРЕМА (Пост) Система булевых функций Г нолна тогда и только тогда, когда она содержит хотя бы одну функцию, не сохраняющую нуль, хотя бы одну функцию, не сохраняющую единицу, хотя бы одну несамодвойственную функцию, хотя бы одну немонотонную функцию и хотя бы одну нелинейную функцию: [Г] = Рл <=ь -1(Г С Тл '4 Г С Тг Ч Г С 7; Ч Г С Т< Ч Г С Ть). Док заткпьство Необходимость.
От противного. Пусть [Г] = Р„и Г С 7в Ч Г С Т, Ч Г С Т. Ч Г С Т< Ч Г С Ть. Введем обозначение: 1 — один из индексов О, 1, в, < нли Ь. Тогда Т; = [Тг] =ь [Г] с Т; =ь Р„с Тг =ь Р„= Т,, но Р„ф Тг по таблице из подраздела 3.5,2. достаточность. Пусть - (Г с Тв у Г С Тг ч Г с Т. ч Г с Т< ч Г с Ть). Тогда 3 Г = (7э,,~ы ~„,,~<,,~~,) ув Е 7в й уг ф Т1 й ~; ф Т, й 7< ф Т< й 7с ф Тг,.
Функции 7в,~,7.,7<,7ь не обязательно. различны и не обяззтельно исчерпывают Г. Покажем, что отрицание н конъюнкция реализуются в виде формул над Г . Тем самым теорема будет доказана. Построение проводится в три этапа; на первом строятся формулы, реализующие константы О и 1, которые нужны на третьем этапе. На втором этапе строится формула, реализующая отрицание. На третьем этапе строится формула, реализующая конъюнкцию.
1. Построим формулу, реализующую 1. Пусть ~р(х): = Ях,..., х). Тогда р(0) =7в(0,...,0) теб=ь р(0) =1. Возможны два случая: у(1) = 1 н ~р(1) = 1. 1) у(1) = 1. В этом случае формула ~р реализует 1. 2) яг(1) = О. В этом случае формула вг реализует отрипание.
Тогда рассмотрим функцию 7.. Имеем: 7, к Т, = Заы...,а„у (аы.,.,а„) ф /,(ады...,а„). Следовательно, 7,(аы...,а„) = Б,(ды...,ал). Пусть теперь ф(х): = 7,(хл1,..., х'"). Тогда ф(0) =ЯО"г,...,0 ") = 7.(аы...,ан) = =1 (аы, ал) = У (1",..., 1'") = ф(1) Таким образом, ф(О) = ф(1), откуда 4 = 1'~ ф = О. Если чу = 1, то требуемая константа 1 построена. В противном случае ф реализует О, и значит Чг(ф(х)) = ф(х) реализует 1. Построение 0 аналогично, только вместо гв нужно использовать уь 98 Глава 3. Булавы Функции 2, Построим формулу, реалнзуюшую отрицание. Рассмотрим функцию Г< Имеем: Гя ГС Т< =~ Ла = (аз,...,а„),~у = (Ь1,...,Ь„) а < 11»з,Г<(а) > ~я(11) Тогда а < ~3 =ь 'т'1 аз = Ь, ч аз = 08з Ьз = 1, Но У<(а) уз У<(Р) =ь а ~1У =ь БАС 1..ну Е з =Ф а = ОззЬ, = 1.
Другими словами, .7 — зто множество индексов 1, для которых а, ф ь;» пусть у(х): =у<(сз,...,с„), где с: =х, если 1 Е.г, и с,: =а (= Ь,), если з ф .7. Тогда у1(0) = ~<(с1,...,с»)(ООх) = У<(а) > у<ф) = У~(с1,...,с„)(10х) = у(1), Имеем: уз(0) > р(1) =Ь Зг(0) = 1зз у1(1) = О =Ь уг(х) = х. 3, Построим формулу, реализуюшую конъюнкцию. Рассмотрим функцию Уь.
Имеем: ~ь е Р„=~ ~ь = 2 и 1 а „, „, х,1,..., х1, Но ~ь ф Ть, следовательно, в полиноме Жегалкина существует нелинейное слагаемое, содержащее конъюнкцию по крайней мере двух переменных.'Пусть, для определенности, это х1 и хг. Тогда з ь = х1 ' хг ' за(ха~ ° ° ° ~ х») + х1 ' гь(ха~ ° ° ° 1 х») + + хг ' Ыхз, ° ° х») + за(хз ° ° ° х ) причем Г',(хз,...,х„) ~ О. Следовательно, йаз,...,а„,г',(аз,...,а„) = 1. Пусть Ь:=~ь(аз,...,а„), с:=Яаз, °,а„), 11:=Ыаз ",а„) и у1(хз,хг): =й(хз,хг,аз,...,а„) = х1 хг+ Ь х1+с ° хг+ 1(. Пусть далее 1Ь(х1, хг): = у1(х1 + с, хг + Ь) + Ь с + 4.
Тогда 4 (хм х,) = (х1 + с) (хг + Ь) + Ь (х1+ с) + с (х, + Ь) + 1(+ Ь. с+ 4 = = х, ° хг+с хг+Ь х1+Ь ° с+Ь. х1+ Ь с+с ° ха+ Ь ° с+». с+ + 11 + Ь ° с+ д = х1 хг. (Функции х+ а выразимы, так как х+ 1 = х, х+ 0 = х, а константы О, 1 и отрицание уже построены.) П Комментарии Прекрасным руководством по булевым функциям являются книги (25) и (17), в которых можно найти обширный дополнительный материал, в частности, опушенные за недостатком места различные алгоритмы построения, упрощения и минимизации нормальных форм.
Упражнения 3.1. Доказать, что число булевых функций от о переменных, среди которых Ь фиктивных, равно 2г Упражнения 3.2. Проверить равносильности подраздела 3.2.2 путем построения таблиц истинности. 3.3. Какие функции являются двойственными для +, м, ~, 4? ЗА. Построить СДНФ для х1 ~ хг, хг 4 хг, хг -«хг, хг + хг. 3.5. Проверить принадлежйость классам Те, Тг, Т„, Т<, Ть функций ~., ~, ч, -«, у.
3.6. Доказать, что У ФТе — — «У Ф Т.ч (~ к Т, йУ ФТ<). ГЛАВА 4 Логические исчисления С древнейших времен человечеству известна логика, или искусство правильно рассуждать. Вообще, способность к рассуждениям — это именно искусство. Имея какие-то утверждения (посылки), истинность которых проверена, скажем, на опыте, логик путем умозрительных построений приходит к другому утверждению (заключению), которое также оказывается истинным (в некоторых случаях). Опыт древних (чисто наблюдательный) был систематизирован Аристотелем. Он рассмотрел конкретные виды рассуждений, которые назвал силлогизмами.
А именно, Аристотель рассмотрел так называемые категорические утверждения четырех видов: ь все А обладают свойством В (все А суть В); ь некоторые А обладают свойством В (некоторые А суть В); ~ь все А не обладают свойством В (все А суть не В); ~ некоторые А не обладают свойством В (некоторые А суть не В) и зафиксировал все случаи, когда из посылок такого вида выводятся заключения одного из этих же видов. Пример 1.
Все люди смертны. Сократ — человек. Следовательно, Сократ смертен. Это рассуждение правильно, потому что подходит под один из образцов силлогизмов Аристотеля. 2. Все дикари раскрашивают свои лица. Некоторые современные женщины раскрашивают свои лица.
Следовательно, некоторые современные женщины— дикари. Это рассуждение неправильно, хотя, видимо, все входящие в него утверждения истинны. Логика Аристотеля — зто классическая логика, то есть наука, традиционно относящаяся к гуманитарному циклу и, тем самым, находящаяся вне рамок данной книги. 4.1. Логические связки Предметом этой главы являются некоторые элементы логики математической, которая соотносится с логикой классической примерно так, как язык Паскаль соотносится с английским языком.
Эта аналогия довольно точна и по степени формализованности, и по широте применимости в реальной жизни, и по значимости для практического программирования. План главы состоит,в том, чтобы на основе небольшого предварительного рассмотрения ввести понятие «формальной теории» или «исчисления» в его наиболее общем виде, а затем конкретизировать это понятие примерами двух наиболее часто используемых исчислений; исчисления высказываний н исчисления предикатов. 4.1. Логические связки Цель данною раздела — ввести специфическую «логическую» терминологию и указать на ее связь с материалом предшествующих глав. 4.1.1. Высказывания Элементами логических рассуждений являются утверждения, которые либо истинны, либо ложны, но не то и другое вместе.
Такие утверждения называются (простыми) высказываниями. Простые высказывания обозначаются пропозициональными переменными, принимающими истинностные значения «И» и «Л». Из простых высказываний с помощью логических связок могут быть построены составные высказывания. Обычно рассматривают следующие логические связки: Обозначение Прочтение Название Отрицание Конъюнкция Дизъюнкцил Импликация не и или если ... то 4.1.2. Формулы Правильно построенные составные высказывания называются (пропозициональ ными) формулами. Формулы имеют следующий синтаксис: (формула):: = И ! Л ! (пропозициональная переменная) ~ (-(формула))( ((формула) 8г(формула)) ) ((формула) ~l (формула)) ) ((формула) -+ (формула)) Для упрощения записи вводится старшинство связок (, ег, ъ', — ») н лишние скобки опускаются. ТОЕ Глава 4. Логические исчисления Истинностное значение формулы определяется через нстинностные значения ее составляющих в соответствии со следующей таблицей: 4.1.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
