Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 28
Текст из файла (страница 28)
Чтобы подчеркиуть ключевой момент исследования, дадим другое определение решетки в форме предложсппл. 179 П ред ложен ие. Б является решеткой тогда и только тогда, когда ЧХ и ДХ существуют для любого непустого конечного подзгнолгвства Х ив Ь. (Этот факт можно доказать ицкукцией по числу элементов множества Х; оставляем его в качестве упражнения.) г' Если Б — решетка и в ней определен элемент /~Б, то он обозначается символом О и навывается наименьшим элементом Б. Аналогично, если в Б существует элемент ЧЬ, то он обозначается символом т и называется наибольшим элементом Б; по определению ЧИ О. Определение.
Решетка Б называется полной, если ЧХ и /~Х существуют для всея подмножеств Х ив Б. в" Все конечные решетки являются полными. Рассмотрим, однако, мпоягество Я с обычным отношением порядка к. и бесконечное множество аппроксимаций числа н, каждое из которых имеет на один десятичный знак больше. Верхняя грань втой последовательности, очевидно, есть л, однако я ж Й~О, и, следовательно, (Я, <) пе является полной решеткой.
Решетка (К, <) является полной, и Я и Б. Можно показать, что любая решетка может быть расптирена до полной решетки, однако мы не будем ваниматься этим вопросом. 5.2. Булевы алгебры. Мы уже интенсивно занимались алгеброй мноя»еств и упоминали об относительно влогичной» арифметике. Сейчас дадим формальное определение общей булевой алгебры, названной так в честь матема« тика Х)Х в. Дж. Буля. Алгебра множеств — это частный случай булевой алгебры, и, хотя различные булавы алгебры структурпо подобны, следует заметить, что не все оки включают в себя множества обычным образом.
Определение. Булевой алввброй называют мно« жество М вместе с тремя операциямиЧ, /~ и - (Ч называют операцией или, /~ — операцией и, а — операцией дополнения или же операцией нв; кроме того, первые две операции часто называют дизьюнкцией и коньюнкцией соответственно). Бинарные операторы Ч и /~ и унарный оператор (обычно записывается над операндом, например а) вместе с двумя различпыми элементами М, которые обозначаются символами О и », удовлетворяют следующим аксиомам. Для произвольных элементов а, Ь и с в М: а) аЧЬ ЬЧа; б) аЧ(ЬЧе) (аЧЬ)Чс; »7В в) аЧО а; г) аЧа- й д) а~,Ь=ЬДа; е) а~,(Ь/~с) (а/~Ь)/~,с; ж) ай( а; з) а/~а О; и) а~,(ЬЦс) = (а/~ Ь)Ч(а/~ с) к) а)/(Ь/~с) (а~/Ь)Яа~/с). Таким образом, и и или коммутатнвны, ассоциативны и дистрибутивны одна по отношению к другой.
Каждая из зтих операций имеет единичный элемент, н, когда элемент комбинируется вместе со своим дополнением посредством и/или, в результате получается единица по отношению к или/й соответственно. Названия операторов, использованные выше, являются именами, которые непосредственно связаны с компьютерной логикой, используемой при построении схем. В других булевых алгебрах может быть более подходящим читать Ч как объединение, наименьшая верхняя грань или зпргешпш, а /~ как пересечение, наибольшая нижняя грань нли (пйшпш. (Иногда операцию Д обозначают также й.) Операция а может записываться как а' или "1а. л Вулеву алгебру можно определить как дистрибутивную решетку с дополнением.
Поэтому по аналогии с булевой алгеброй (У(Х), О, О, ') для данного непустого множества Х из результатов предыдущего параграфов можно вывести ряд следствий. Доказательства некоторых из них оставлены в качестве упражнений. Наиболее важными из зтнх следствий являются следующие. Инволютивный закон (или закон двойног о о т р и ц а н и я). Дополнение дополнения х, х ж Я (т, е. в рассматриваемой булевой алгебре), есть х. Закон поглощения.
Для любых а, Ь жЯ справедливы соотношения аЯаЧЬ) а, аЧ(а/~Ь) ° а. Закон идемпотентности. Любой елемент Я идемпотентен по отношению к операциям /~ и Ч. Законы де Моргана. Для любых а, Ь жЯ справедливы соотношения а/~Ь аЧЬ, аЧЬ аДЬ. Из инволютивного закона и законов Моргана следует, что если мы берем булеву алгебру Я (более точно, $2 д. ктз, г, вззз зтт (Я, 'ь/, /ь,, )) и образуем новуьо систему или путем отобраяьения каждого л ге Я в й, нли использованием операций/ь и ь/, то(Я, Л, 'ь/, )такяье булеза алгебра. Зтот факт известен как принцип двойственности. Действительно, каждый нз законов Моргана может быть получен из других путем отобраяткня каждого элемента в его дополнение. Сейчас мы выведем теорему, которая показывает, в какой стандартной форме могут записываться булевы выражения; непосредственным следствием этого является утверждение, что достаточно двух операторов, чтобы описать все бинарпые функции.
Как всегда, введем вначале пеобходимую терминологию. Определим две общеупотребительные логические связки следующим образом. Говорят, что булевы формулы А и В эквивалентны (записывается в виде А ~ В или А В), если они выражаьот одну и ту же функцию, В простейшем случае это — отношение эквивалентности. Таблица 53 А В ~ А»В О О О 1 1 О 1 1 Аналогично говорят, что формула А имплицнрует формулу В (записывается е) А - В), если имеют место условия, изображенные в табл.
5.3. (Таблицы такого типа часто нааывают таблицами истинности.) Заметим, что стрелки используются во многих различных контекстах. Поэтому надо обращать особое внимание на расшифровку их вначения. Таким образом, А— - В это то же самое, что н ( ) А)Ь/В, а А В это то же самое, что и (А»В)/1(В-»А). Логически А- В означает «если А, то В» (т. е. если А справедливо, то В также справедливо и обычно так и читается. Другие названия для символов - и это условный и безрсловнььй операторы соответственно.
Обычно вводят операции, которые обозначают отри- ч) Ото вираж»вне ваэызавт также имвлиеациеа.— Примеч. Рез !78 отнкцня ! ~Фтнкння ! О А)В А ~В О "1А А-~В О 1В 1 В-~А О А)В 1 л о» о в о о 1 л о е о в о о О О /', 1О О /„', 1О /» 1О у,'1 «о /„11 О /'„' /',' ь1 1 1 /, О О /, О О /, О О /,' ОО те О / О /, О /, О 1 О О О 1 1 О 1 1 О О О 1 1 О 1 О АДВ Вт А В А~ В А А «ьд А 1/В можем описать все отображенил яз (О, 1)" в (О, 1), используя только 1 или только ( (первая из них называется "етрихои Шеффера и обозначается «)»; в вычислительном контексте 1 называют «не и», а ( называ«от *) «не нли»).
Заметпи, что операции 1 и ) являются удобными сокращепиям»«, но они, например, неассоциативны. Следовательно, по определенвто А 1В1 С есть (А/1В Д /~С)', а, например, не ((АДВ)'/~С)'. Говорят, что множества операторов (1) н (() адекватны. Сейчас мы сформулируем теорему и дадим ее конструктивное доказательство, т. е. ие только локаясем справедливость утверждения теоремы, но и дадим метод получения результата.
Теор еиа. Любав отображение (О, 1)" - (О, 1) может быть представлено в виде вбормулы, содержащей только оператор 1 или только оператор ). Д о к а з а т е л ь с т в о. Рассмотряи произвольное отобра»кение /: (О, 1)" — (О, 1) от переменных рь ..., р„ (и еи Х). Функция может быть полностью определепа е) спуннцнк А 1 Л явоиеоетск твюве стрелкой Ларса.- При.ве. ред. 1О« 179 цания бинарных связок, такие, как А вди В = ~ (А ~ В), А ( В - ~ (А /~ В), А, В= -1(А В), А1В -)(А1/В). Сейчас мол«по описать все бинарные операции (О, 1)«в (О, 1) (здесь стрелка находится между двумя множествами и, следовательно, обозначает множества, которые являются областью определения и множеством значений; не следует путать с логическим операторои - ) в краткой форне, как показано в табл.
5.4. Более того, мы Таблица 5.4 ~-Ч ЛВ;, )-Д 1 Вп. а) б) Аналогично, прихгсняя ваконы де Моргана к (е) пли же рассматривая строки, содержащие нуль, получим 1 ЧВВ. ( *) Следствием этого результата является тот факт, что каж- дое выражение выводимо, а отсюда в свою очередь сле- дует, что число элементов в булевой алгебре, порожден- ной рь ..., р„, равно 2", л' е) Каждая строка соответствует аекоторому двоичному вабору длины л в содержит ввечеккя фувкавл аа етом ааборе.— Примеч.
ред. ° ') 1)усть (ао, ..., и, ), ..., (и ь ..., а „) — все наборы, ва которых фулкалл / резке 1,1 < и ( 2". Дла каждого такого ваборе образуем иолькжклож В, = Вм А . ° А Вьь гле Ви = рь, еслк аи = 1, и Ви — — 1 рь, если аи = О (1г 1...ч л). Легко вкдстгч что 1 = В1 'чг „, ~/ В„.— Примеч. ред, 130 таблицей истинности, имеющей 2" строке). Утверждение очевидно, если в каждой строке таблицы результат равен 1 (тогда 1'=1) пли в каждой строке результат равен 0 (тогда ) =О). Б противном случае существуег лз строк таблицы, в которых результат равен 1. Рассмотрим выражения "е) Вы ..., В; каждое В, соответствует упорядоченному набору (Вм, ..., В„), где В„равно или рь или ) р, в аависимости от того, равно р, единице или нулю для данной строки таблицы. Тогда (=В,))В,У ...ЦВ„=(В,((В,,(...ЦВ„)ч= (В; А В, 'А ...
А В„')' = '(В; Ф В,' ) ... ( В.'), Вг (Вц~1 ВгзД... /~ В,„) = Вц ') В з ( ° ° ° У Вг ° Болев того, если какое-либо В„соответствует нулю в таблице, то надо брать выражение ) рп которое можно получить прн помощи тождества (-) )-() ). Итак, утверждение доказано. В компактном виде атот результат можно записать следующим образом: Пример 5.3.
Получек продставлепие для фуикции м используя только операцию 1; таблица истинности функции 1' дана в паде табл. 5.5. Таблица б.б » е к О О О О О О 1 О ! О 1 О ! 1 О 1 О О 1 О 1 1 1 1 О О 1 1 1 Используя описаввый метод, получаем Е=(х'ЛУЛ Я(х'ЛуЛ ')Ч(хЛу'Лз')!д '1/(хЛу'Лз)ИхЛуЛз). Тапка! образоьг, Е =(х Лу Лз) Л(х ЛуЛ ) Л Л(хЛ у'Лз')'Л(хЛу'Лз)'Л(хЛуЛз)', и позтому (х 1 у 1 з) 1 (х' 1 у 1 з') 1(х 1 у 1 з') 1 1(х 1 у 1 з) 1(х 1 у 1 з), ') 11а самом деле иопыоактиипсй иормапьпой формой вааы- 2» — 1» / лают еырзжепие аппп 1= д~ ~ Ч ) В! ) (си.
»») пз доказа- '=г 1=, тельсгеа теоремы, — Е)рилгч, ргд. 13! где х' х1х, у' у1у, з' з1з. в" Выра!копие (») иазывают дигьюнкгивной нориальной форлгой (ДЕ(сР) — ова имеет вид дизъювкции ковьювкцвй (или от и); выражение, получевиое в (»»)*), вазывается конъюнктиеной нормальной формой (КЕЕФ), В заключение отметим, что утверждевие в булевой алгебре (логвческая формула), которое всегда прикимает звачепие 1, пазывается тавтологией, а выражевие, которое всегда првппмает значение О, пазывается противоречием. 5.3.
ЕЕекоторые приложения булевой алгебры, Существуег ряд проблем, папример в комбинаторвке, которые моншо решить паилучшим образом в подходящей булавок алгебре. Другой путь применевпя булевой алгебры еаключается в моделпровавии реальпой ситуации, или, другими словами, в интерпретации булевой алгебры в терллииах, относящихся к рассматриваемой задаче. Этот метод л1о>кет быть применен в областях, которые так широко распространены, что у ких отсутствует классификация.
Мы рассмотрим только одно приложение, а именно комбинационные и переключателькые схемы а). Другие области приложений будут представлены в виде отдельно выбраяпых примеров и упражнений. Ряс. 5.10 С этой точки зрепия необходимо подчеркнуть, что мы запимаемся только некоторыми вопросами построения и преобразоваиия схем; формальпое исследование лежит за пределами втой книги. Сначала давайте посмотрим, как выражепия булевой алгебры могут быть использованы для описаяия и определения схемы, состоящей из проводников и переключателей. Схема, ивображеяиая ка рис. 5ЛО, состоит из пяти переключателей, источпика питания, лампы и соединяющих проводииков. Из диаграммы нетрудно видеть, что ток течет по замкнутой цепи тогда и только тогда, когда переключатель А замкнут и (или) переключатели В и С оба вамкиуты или переключатели В и Е оба замккуты. Алгебраически зто мояпю записать в виде А ~, (( В ~, СЯ (В ~, Е)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
