С.В. Яблонский - Введение в дискретную математику (1060464), страница 43
Текст из файла (страница 43)
Последнее означает, что коду, полученному на выходе канала связи, соответствует точка, которая принадлежит ровно одному шару. Данная теорема дает геометрический подход для построения самокорректирующихся кодов. С пей также связало и следующее утверя«дениз. Теорема 11. а) При 1=2' — 1 единичный 1-мерный куб мозкет быть разбит в прямую сумму единичных шаров (т, е. шаров с радиусом 1). б) При 1=2' единичный )-мерный куб может быть разбит в прямую сумму единичных сфер.
Доказательство. а) В единичном 1-мерном кубе с 1 2' — 1 возьмем код Хзмминга Н). Очевидно, имеем к=1, т=2' — 1 — 1. Около каждой точки из Н) опишем шар радиуса 1. Покажем, что система всех таких шаров и задает искомое разбиение. Данные шары попарно не пересекаются (см. теорему 9). Отсюда сумарпое число точек, содержащихся в ч. «ч. ткогия коднговлния 295 втой системе шаров, равно (1 -) 1) 2т 2ю2«'-с-«2»'-«2с Значит, эта система шаров содержит все точки единичного 1-мерного куба.
б) Пусть | 2'. При фиксированной последней координате единичный 1-мерный куб может быть «разрезан» на два единичных 1 — 1-мерных куба. Для этих кубов существует естественное взаимно однозначное соответствие ()', где (16* (1о ", В-ь 0), 1«=ее ..., (1-о 1). Так как 1 — 1 = 2' — 1, то 1 — 1-мерный единичный куб на основании пункта а) может быть разбит в прямую сумму Рве.
17 Рвс. 19 единичных шаров. Выберем в олпом из 3 — 1-мерных кубов разбиение в прямую сумму единичных шаров. Разбиение в другом 1 — 1-мерном кубе можно построить, пспользуя естественное взаимно однозначное соответстспе между этими кубами. Рассмотрим пару соответствующих шаров (см. рис. 16) Ц,(Р») и У(-, (Р'). Дза данных 1 — 1-мерных единичных шара моя<но прообразовать в дзе 1-мерные единичные сферы (рис. 17).
В самом деле, 1 — 1-мерные единичные шары являются объединение»«1 — 1-мерной единичной сферы и своего центра, т. е. Й- (Р)-Й- Ф') () Р'Ь Й-«(Р') = И-«(Р') () (Р'). Очевидно, что для 1-мерных единичных сфер имеют мес- ч. тч. тковия кодитовлния то равенства у1 уо1 р1 ~ро1 ц ро1 р1 оо1 уо Пр1 ~ бо) Таким образом, если осуществить зто преобразование для всех пар соответствующих шаров разбиений, получим искомое разбиение куба в прямую сумму единичных сфер. Теорема доказана. Определение. Кодовое множество, принадлежащее 1-мерному единичному кубу и являющееся самокорректирующимся для данного источника помех, называется максимальным, если оно имеет наибольшую мощность.
Следствие. При 1 2' — 1 код Хэмминга Н~ является максимальным. ЧАСТЬ (г НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ Глава ДИЗЪЮНКТИВНЫЕ НОРМАЛЫ1ЫЕ ФОРМЫ 5 1. Понятие д.н.ф. Проблема минимизации булевых функций Пусть задан алфавит переменных (х», ..., х,). Определение. Выражение К = х<»д» ...
д» х<, ((~та<а прн т~'=(<) называется элементарной конъюнкцией. Число т называется рангом элементарной конъюнкции. По определению считаем константу 1 элементарной конъюнкцией ранга О. Определенно. Выражение з< ~/ К< (К<~К< при 1Ф1)» <-1 где К» (1 1, ..., з) — элементарная конъюнкция ранга ть называется дигъюнктиеной нормальной»рормой (д.
и. ф.). Очевидно, что д. н. ф. 9» реализует 'некоторую булеву функцию ~(х„ ..., х ). Из гл. 1 части 1 следует, что для каждой фУнкции ~(хо ..., х„) и <чь О сУществУет д. н. ф. Ю такая, что 1(х„ ...,х„) В. В качестве такой д, н. ф. можно взять, например, совершенную д. н. ф. для 1, а именно: е аэ з< ~/ х, д»...д»х, . (е ...,,е„) »(е»"-Рэ]» 293 ч.
т. нвкотогыв пгиложкнкя к кпвкгнетккв Пример 1. Рассмотрим функцию ((х„х„х,), заданную таблицей 4. Ее можно представить в ваде совершенной д. н. ф. Иа '= У~УФа Ч хюУФа ~ лФзхз ~l хюхзУе 4 хюхзха. Сдругойстороны, непосредственной проверкой убеждаемся, что эта функция может быть представлена другой д. н. ф. Из У~Уэ ~/ х,.
Данный пример показывает, что функция алгебры логики может быть представлена в виде д. н. ф., вообще говоря, не единственным образом. В связи с этим возникает возможность выбора более предпочтительной реализации. Для этого вводится индекс простоты Ь(И), характеризующий есложностьэ д. н. ф. Для функционала Ь(И) потребуем выполнения следующих аксиом. 1. Аксиома неотрицательности. Для любой д. н. ф. Ь(И) ~ О. 11. Аксиома монотонности (относительно умножения). Пусть 9) 9) ' ~/ я~'К', Тогда Е (И) > Ь (И' Ч К') .
П1. Аксиома выпуклости (относительно сложения). Пусть д.н.ф. И разбита в прямую сумму д.н.ф. И, и И„т. е. И=И, ~/И, и И„И, не имеют общих членов. Тогда Ь(И) ~ Х,(И,)+ Ь(И,). 17. Аксиома инвариантности (относительно изоморфизма). Пусть д. н. ф. В' получена иэ д. н.
ф. В путем переименования переменных (без отождествлений). Тогда Ь(В') Ь(В1. Приведем примеры встречающихся индексов простоты для д. н. ф. 1. Ьэ(В) — число букв переменных, встречающихся в записи д. и. ф. И. Если взять д. п. ф. И, и В, из примера 1, то.ьв (В,) 15 и Ьз (И,) 3, т. е. в смысле этого индекса д. н. ф. В, проще, чем д. н. ф. В,. 2. Ь„(И) — число элементарных конъюнкций, входящих в И. Для д.н.ф. И, и В„очевидно, Ь„(й~) 5 н (;(Я,) 2, т. е. в смысле этого индекса д. н. ф. И, проще, чем д. н. ф.
И,. Гл, $. Дизъюнктивные нОРМАльные ФОРмы 999 3. Ь,(И) — число символов", встречающихся в записи д, н, ф. И. Для д. н. ф. И, и И„очевидно, А»(И,) 7 и 1„(И»)-2, т. е. в смысле этого индекса д.н.ф. И, опять проще, чем д. и. ф. И,. Нетрудно проверить, что каждый из указанных индексов удовлетворяет приведенным выше аксиомам. Замечание. Пусть И=И'ЧК. Тогда в силу аксиом П1и 1 Е(И) > Ь(И').
Очевидно, что над алфавитов» переменных (х„..ч х„) мо»кпо построить 3" различных элементарных конъюнкций (»пустой» конъюнкции сопоставлена константа 1). Отсюда следует, что число д. н. ф. над этим же алфавитом из и букв равно 2»". ОпиРаЯсь на этот подсчет, введем следующее определение. Определение.
Д.н.ф. И, реализующая функцию 1(х„..., х„) и имеющая минимальный индекс Ь(И), называется минимальной относительно Ь (м. д. н. ф. относительно Ь). Поскольку дальнейшее изложение связано главным образом с индексом простоты Ьз, то минимальную д. н. ф. относительно этого индекса будем называть минимальной д. и. ф. (м. д. н. ф.). Д. н. ф., минимальную относительно индекса Ь„, будем называть кратчайшей. Вернемся теперь к примеру 1.
1. Д. н. ф. И, х,х, Ч х, является минимальной. В самом деле, функция Дхо хь х,), реализуемая этой д. н. ф., существенно зависит от переменных х„х, и х, и потому не может быть представлена д. н. ф., содержащей менее трех букв. 2. Д. н. ф. И, х»х»Чх, является кратчайшей, так как функция Дхо х„х»), реализуемая атой д.
н. ф., отлична от любой элементарной конъюнкции. 3. Д. н. ф. И, х,х, Ч х, минимальна относительно Ее так как функция ~(хь х„х»), реализуемая атой д. н. ф., по переменным х, и х, пе возрастает и они обе существенны, а поэтому не моя»ет быть представлена д. н. ф., содержащей менее двух отрицаний. Основной вопрос, который нас будет интересовать в этой главе, это как для произвольной функции алгебры логики 1(хо ..., х„) построить ее минимальную д. н. ф.
относительно Б. Эта задача называется проблемой миниАшаации булсвьш функций. Мы покажем сейчас, что дап- 300 ч. ч. неиотогыг пгнложенпя к кпввгпетпкн ная задача допускает тривиальное решение. Сначала в каком-либо порядке строят все д. н. ф. (их 2«") над переменными ло ..., х„ у)«~ а ., «) зю Затем отбирают из этого списка те д. н. ф., которые реализуют функцию )(ло ..., х„). Наконец, для выбранных д. н. ф.
вычисляют величину индекса простоты и путем сопоставлений находят минимальную (относительно Ь) . Сформулированный алгоритм весьма трудоемок с точки зрения его реализации, так как он основан на «переборе» всех д. н. ф., т. е. требует, вообще говоря, не менее 2'" более мелких операций. Им нельзя воспользоваться практически уже начиная с я=3, а для я 1 и п 2 проблема тривиальна. Таким образом, следует считать, что алгоритмы «полного перебораз, т.
е. алгоритмы, подобные по трудоемкости тривиальному алгоритму, перебирающему все д. н. ф., являются запрещенным средством в решении проблемы минимизации. Мы обращаем внимание, что развиваемая далее теория справедлива для любого индекса простоты и потому начальный этап минимизации одинаков для всех индексов прцстоты. С другой стороны, для удобства можно считать, что в этих построениях речь идет об нндексе Ьз, т. е. о построении и. д. н. ф.
Поскольку минимальная д. н. ф. относительно одного индекса может не быть минимальной д. н. ф. относительно другого индекса (см. [2, 4, раздел 3)), то теория, построенная для одного индекса, вообще говоря, не годится для другого. Однако то обстоятельство, что эти теории имеют и много общего, оправдывает рассмотрение минимизации для конкретного индекса. 5 2. Упрощение д.н.ф. и тупиковые д.н,ф. (относительно упрощения) Пусть Я вЂ” произвольная д. н. ф.и Щ Р) ЧК, И=И Ч.,а«К, где К вЂ” некоторая элементарная конъюнкция из з), з)'— д. н.
ф., образованная из остальных конъюнкций, входящих в Я, я~' — некоторый множитель из К, К' — произведение остальных множителей из К. Рассмотрим два типа преобразований д. н. ф. Гл. ь дпэъюнктивные нОРМАльные ФОРмы во1 1. Операция удаления элементарной к о н ъ ю к к ц и и. Переход от д, н. ф. И к д. н. ф. И' — преобрааование, осуществляемое путем удаления элементарной конъюнкции К. Данное преобразование определено тогда и толйко тогда, когда И' И. П. Операция удаления множителя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
