Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 30
Текст из файла (страница 30)
Если мы ограничимся фактором, что все, что говорит лжец, неверно, то можем заменить множество включений нз (1) — (б) на эквивалентные. Например, если Барбара п Клара правдивы, то, поскольку Алиса говорит, что это так, Алпса тон~э правдива. Следовательно, А ВПС, (1а) С (ЕПЕ)9(Е'ПЕ'), (2а) Р АОВ, (За) В (ЕПЕ')()(Е'ПЕ), (4а) Е АПВ, (5а) Р (ВПС)'.
(ба) Как и рапыпе, А И и Е = И, и поэтому Ллпсв и Элспет никогда не говорят правду. Из (2а), (4а) и (ба) следует, что Е =д'. Таким образом, из (За) и (4а) получаем Р В г'-Ю, откуда с помощью подстановки в (2а) следует С ю. Отсюда следует, что возможпо только одно утверя<доние такое, что х ы А' П В П С' й Р й Е' й Е; это означает, что Алиса, Клара н длспет лгут, а Барбара, Деби и Фпона говорят правду. г" У и р а ж н е н и е 5.5.
1. Показать, что в булевой алгебре (Я, », +, ') для х, р, зыЯ справедливы соотношения: а) (х+ р)»(х'+ у) ° р; б) (э+ х) «(з'+ р) (з» у)+(з' «х); в) ((х» х)+ (у «з') ) ' (х' «з)+ (р' » з'). 2. Доказать, что если в (Я, «, +, ') выполняются соотношения х «р ° х» з и х+ у — х+ з, то р з. 3.
Из схем, изображенных на рис. 519 и 5.20, получить «простые» схемы, эквивалентные исходным. 190 4. Получить алгебраическое представлепие схемы, каображенной на рис. 5.21, в дать табличное представление выходов л и у в вавпспмостк от значений а п Ь на входе. Использовать две такие схемы для построения схемы, Рве. 5.19 Рас. 5.20 соответствующей функции, определяемой табл. 5.8. Связать это с арифметикой из $3 гл. 4. 5. Построить схему, реалнаующую операцию не и, которая имеет четыре входа н выдает на выходе 1 тогда и Рве. 5.21 только тогда, когда все входы равны О. 6. Пусть выполнены укаэанные вдесь условия: а) все гонщики импульсивны; б) все хорошие программисты меланхоличны; в) никто пе может быть и пмпульспвным и меланхоличным; г) читатель меланхоличен.
Таблица 5.8 О О О О О 1 О 1 О О 1 1 О О О 1 О 1 1 О О 1 1 О 1 О 1 1 1 О О 1 О 1 1 1 О 1 1 Является лн читатель хорошим программистом и/или гонщиком? 185 7. Органиааторы международной конференции по компьютерам решили, что для того, чтобы на встрече не доминировали коммерческие интересы, будет только один магавин, которым будут пользоваться вместе все производители компьютеров.
Сами пронаводители будут ответственны за определение того, кто принимает участие в представительстве. Десять компаний — пять европейских и пять американских — дали анать, что они хотят принять участие в конференции. (Обозначим вти компании череа А, В, С, В, Е и Р, С, В, 1, 1 соответственно.) Однако иа-еа обязательств по контрактам и торговой политики должны появиться рааличные ограничения. Европейские предписания требуют, чтобы б и 1 не моглн одновременно принимать участие в конференции; аналогично не могут одновременно привять участие г", С и 1.
Ограничения американских проиаводителей исключают участие А и Р, пока С не примет участия; аналогично исключаются С и О. Если В присутствует на конференции, то должно присутствовать и 1, однако если они принимают участие вдвоем, то В не может быть там. И наконец, В и С не могут вместе принимать участие в конференции. Может ли быть достигнуто соглашение, по которому по три компании из каждой группы могут собраться вместе, не нарушая условий3 Если так, то кто именно примет участием $ 6. Замкнутые полукольца В завершение главы мы опишем довольно увкие, но важные структуры, которые поэволяют осуществлять операции на подмножествах бесконечных множеств.
Пока у нас нет понятий матриц и графов, мы не можем начинать обсуждение приложений, и, следовательно, мы дадим только аксиоматическое определение и покажем принципиальную рааяицу между полукольцами и похожими на них на первый вэгляд полями. Определенна. Замянутын иолукольцом называется множество Б с двумя бинарными операциями ® и ~ такими, что а) ® ассоциативна; б) существует единичный элемент по отношению к ®, который будем обоаначать символом О; в) ® ассоциативна; 1вй г) существует единичный элемент по отношению кЯ, который будем обозначать символом 1; д) для всех жеиб ж®0 0 0®х; е) Ю коммутативна.' хну уюх для всех ж, уыил; нд) ю ндемпотентна: а9х *ж для всех адиев; в) ® дистрпбутивна относительно Э: жЯ(у 9з> (х(9) у) 9(х®з) для всех х,у,ззиЯ, (ж9у)ез (х®з)9(у®з) для всех ж,у,зеву; и) сумма счетного числа элементов иэ Я существует н единственна, т. е.
не зависит от порядка суммирования; к) ® дпстрибутнвна относительно бесконечных счетных сумм, т. е. где Таблица 39 ° О1 +~О 1Д О 1 ~/ О 1 О О О О ! О 1 О 91 1~1 О О О О О О 1 193 13 д, ктн, г. Беев ~~.",ад ад9а,9 ..., ~Ь, Ь,9Ь,9 ..., д ~ (ад ® Ь;) = (ад ® Ь,) 9 (а, ® Ь,) 9 ... ад ... 9 (а ® Ьд) 9 (а ® Ь,) 9 ... 9 (аз ф Ь,) 9 9 (аз ® Ьз) 9 ... 9 ... У Эта достаточно странная структура часто используется в алгоритмах вамыкания для графов (гл. 7 н 8). Чтобы проиллюстрировать результаты, которые могут быть получены в замкнутых полукольцах, сравним системы (Ед, ", +) и (Е„ /~, 'т'), где операции определены табл. 5.9. Рассмотрим определение операции вамыкания. Результат а* применения этой операции к элементу а ваписываем в виде ае=* ~а', ю-о ас = 1, а' а, аэ а э а и а' а'-' е а (в(Хэ Д Ч) сложением является Ч, а умножением Д).
В эамкнутом полукольце (Х„ Д, 7) такое определение имеет смысл я дапуетимо. В частности, 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+0+0+О+...-1, т.
е. эначение суммы пе определено. Следовательно, понятие такого рода замыкания не имеет смысла, если его применять к полю Еэ (которое эапрещает аксиомы ж) и и) полукольца). Упражнение 5.6. Проверить, что ((8, Ю, й, О) является замкнутым полукольцом. ГЛАВА 8 МАТРИЦЫ Наше изложение теории конечных матриц (множества матриц) является более общим, чем принятое в большинстве книг, в которых матрицы обычно определяют как линейные преобразования на векторных пространствах, используя энакомство с координатной геометрией. Хотя иногда мы будем воввращнться (т 3) к этой интерпретации, в основном будем придерживаться точки зрения, что матрицы являются реаливациями абстрактных алгебраических структур в вычислительных целях.
Тогда алгебра абстрактных структур определяет способы, как кадо комбинировать матрицы. Сначала мы определим (т 1) матричное представление бинарных отношений над конечными множествами. Затем последует более общее рассмотрение требуемых свойств абстрактной системы для того, чтобы матричная реализация была разумной. А в эавершение, используя результаты предыдущих исследований, будет рассмотрен важный случай векторного пространства над Й.
5 1. Матрицы и бинарные отношения иа конечных множествах Формально зкатрицей над множеством Я называется отображение И: р),Х)ц,-г, р, йжр). Обычно образ (1, у) обозначают через Ме и изображают всю функцию массивом элементов пэ Я, т. е. -лх„м~ ... лг„- м~ зт~ ... з~м вг. м ... м Говорят, что ета матрица имеет р строк и о столбцов и имеет размер рХ д. Матрица размера рХ д имеет р в д твк 105 влементов.
Когда р = д, матрицу называют квадратной Множество всех матриц рХ д над Я обозначают через к(р, в, Я). Множество Л(р, р, Б) будем обозначать че- реа .Х(р, Я). Рассмотрим бинарное отношение р между множества- ми А и В, где А (а!, ах, ...! ав), В "(Ь!! Ьз! ° ° ° Ьв)! т. е.!А! р, !В! Я. Упорядочение клементов в втих множествах выбрано произвольно, однако, однажды выбранное, оно далее оста- ется фиксированным. Пусть зто отношение р определено посредством выбора пар (а, Ь), где ажА, ЬжВ, Рассмотрим матрицу М над (О, 1), т. е, М: !! ХЬ(,— (О, 1), и свяжем элементы М с отношением р биекцией р: В'(АХВ)-Л(р, а, Хх) (!р отображает произвольное отношение между А и В в матрицу р Х д над (О, 1)); !р: р-!.М, причем (1, если (а!, Ь,) ен р! ~О если (а! Ь!) ф р В случае, когда полезно подчеркнуть, что матрица М была получена из отношения р, мы будем обозначать ее через М(р).
Пример 1.1. Возьмем случай !А! 4, !В! 3 и р ((а!, Ьх), (а!, Ьз), (ам Ь!), (аз, Ь!), (а4, Ьх)), Тогда соответствующая матрица М имеет вид Таким образом, мы имеем способ табулирования илп кодирования отношения и можем закодировать отношение посредством !р илп декодировать посредством !р '. Этот процесс является отображением (3, )) в А Х В или М соответственно. Такое представление более удобно, чем тео« ретико-множественный способ определения отношений, поскольку с ннм можно обращаться формальным образом.
Оио становится даже более пригодным для вычислений, 196 ваннам операции на дру ом множестве посредством подходящего отображения !р. С атой диаграммой обычно связывается тождество (м,!з) !р(р О а) = !р(р) + !р(о), С помощью этого тождества можно дать более точное определение Рпс. 6Л сложения матриц: М+)з'-ф(р)+!р(о)=!р(р О о) !р(<р-'(М)Осу-'(У)). П р и м е р тЛ (продолжение). Пусть А и В те же, что и раньше, и пусть а ((а!, Ь!), (а!, Ьз), (аз, Ь!), (аз, Ьз)), если наложить некоторую структуру на множество, пз которого получается матрица. Возьмем опять (О, !) я определим па этом мионсестве логпчесвое ело!пеппе (вли) в умножение (н).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
