В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 12
Текст из файла (страница 12)
Если а- <аь..., аз,>, Р = <Рь..., Рзг> и очР, то )т(аь ..., щз)<)т(Рг,..., Ра,). Отсюда Д(аь ° ° ., агчь Д(е,.... аа,)„щ+ь ° ° ., щ,)<)г(Рг, ". Р' — ь!«(Рь "., Ра ), Рг+ь..., Ра), так как <еь..., щ — ь )з(аг,..., аа,). аг+ь. °, ,>(<Р . Р'- )з(Р' ' Ра,). Р+ .", Р,>. Классы Ть Ть Ть Д М неполные и попарно разливные, поскольку можно привести врнмеры булевых функций, не принадлежащих ни одному из этих классов, и примеры функций, принадлежащих одному из любык двух классов, ио ие принадлежащих другому. Кроме иеречислсниых можно указать н много других функционально замкнутых классов.
Оказывается, что для проверкд полноты системы булевых фуннций можно ограничиться рассмотренными пятью функционально замкнутыми классами. Теорема 1.1й (теорема Поста). Для гого аобы система булеемх функций ()„..., ) ) била полной, необкодимо и достаточно, чтобы длл каждого нз классов Ть Ть Д М и 5 аошлесь функция Д из системы, не лринадлгжощаа етому классу. Докажем только необходимость этого условии. Классы Ть Ть Д М и Я попарно различны и не соввадают с классом Кг всех булевых функций.
Если бы все функции )ь..,, ) принадлежали какому-либо из этих классов, то, ьан следует из утвержденна 1.б, в силу его замкнутости система ()ь..., ) ) не была бы полной. Пример 1.18. Доказать полноту системы (+. т/, 1). Сосга. вим таблицу Поста. В плетках табл. 1.13 будем писать знак «+» илн « — ь в зависимости от того, принадлежит рассматриваемая фуниция данному фунициоиальио замкнутому классу или иет. В силу теоремы Поста для полноты системы необходимо и достаточно, чтобы а каждом столбце был хотя бы одпп минус.
Таблица гза Т Тг к+У !— Принадлежность функции Х ф У илассам Т„ 1. и непринаддежность классу Т, очевидна. Эта функция несамодвойствеицэя, так как (Х + У)*= -1(-1Х + -1 У) ((Х + Ц + (У + Ц) + + 1 = Х + У + 1. Функция Х+У нсмонотонная, так «ак <1. 0>ъ,<1. 1>.. а1+0=1в!-1-1=0. Функция Хтг'У, очевидно, принадлежит классам Т, и Ть Она несамодвойственная, так как двойственная ей функции есть ХЬ У. Она нелинейная, так как многочлен Жегалкинэ этой функции имеет вид Кт/ У = ХУ+Х+ У. Монотонность функции Х тг' у легко проверяетсв по се таблице истинности.
Пля функции, тождественно-равной 1, таблица Поста заполняется тривиально. Так как каждый столбец таблицы Паста содержит по меныпсй мере один знак « — », то система (+, Ч/, Ц— полная. Система фуниций 0 называется независимой, если никакая функция (ш 0 не представлена супсрпозициями функций из Оч()). Независимая система фунютий называется базисом функционально замкнутого класса К, если всякая фуниция из К есть суиераоаиция функций из О. Пр р 1.10. 1.
Сисчема функций (Ь,-)) независимая, так как ЬшТь -1ейть Ьшй,цспс 2 Система функций (Ь, )/, -1) ие является независимой, так иакХт/У= т(-)ХЬ 1У). 3. Система функций (+,, Ц независимая, так как +сйуь ° Ть 1 ТП +Шб, ° шб, 1ш(Л1 + Т. епт 1шт 4. Системы функций (Ь, П ), (+г ъ Ц вЂ” базисы класса А, всех булевык функций. 5. Система функций (О, ) — базис функционально замк-- нутого класса Е линейных функций. Это независимая система, так как Ошуь -Н(Ть Ош Ть -шТь С другой стороны, каждая линейная функция выражается суперпозициями функций +, -\, поскольку -1Х = Х + 1. Но эти функции в свою очередь- выражаются через 0 и —:-)Х=Х-О, К+ У=-1 (К-У).
1.2.3. Минимизация в классе дизъюнктивнмх нарзпшьных форм Выше было доказано, что произвольная булеза функция может быть представлена формулой в днзъюнкткшюй и копъюнктнвкой нормальной форме Равносильными преобразованиями можно получить формулу, содержащую меньшее, чем исходная, число переменных. Например: а) (Х~ ЬХз) )/ (Х~0-1Хз)=ХП и) (Х,ЬХ))ТХ вЂ” Х; в) (Х~ ЬХз) ~I (Х~ Ь Хз) звХ~ Ь (Хз )Г Хз).
ав Заметим, чта последнее преобразование выводит формулу из класса днзьюиктниных нормальных форм. Ьупем минимизировать формулм в плассс ДНФ. Дизъювктнвиая нормальная форма иазывается ипнииальной, если опа содержит наименьшее общее число вхождений выскззмазтельных перемеипык по сравнению со всеми равноснльиымн ей дизъюиктивными нормальными формами. Следователыю,минимальную ДКФ данной формулы можно найти, перебрав кояечяое число равнасцльиых ей ДНФ п выбрав среди них ту, «оторви содержит минимальное число переменных. Однако при большом числе переменных такой перебор праптцчеснн невыполним. Существуют эффективные способы нахогкаепия мнпимальпоп ДНФ (см., например,(1Ц).
Рассмотрим только один пз них — метод минимизирующих карт. Хоти этот метод и нс отличается большой эффективностью, зато он прост для изложения и не требует введения дополнительных понятий. Пусть булеза функпвя ааиана таблицей истинности нли СДНФ. Прп записи формуа будем опускать символ б я вместо -)Х, писать У„ напричер КгХзйз'Ч/ КгХз вместо (Хг Ь )Хз б д Хз) г/ (Х Ь-ГХз).
Состзвпи следующую карту (см. табл. 1.14). Утзерншенне 1.8. Если конъюнкция Хгп ... Х е", жш(0, 1), ! = 1,..., л, принадлежащая 1-й строке гибл. 1.14, не входит е СЙНФ, оырожающую функцию ЦХг,..., Х ), то любая «онъюнкция /-й строки не входит ни е какую ДЙФ. емражающую шходную функцию. Действительно, если канышп<ция Х,"... К ""нс входит в СДНФ, выражающую функцию /(Хь..., Х ), то па алгоритму построения СДНФ (см. теорему 1.8) /(м, ..., з )=О. Если бы. какая-то конъюнкция г-й строки вошла в некоторую ДНФ функции /.
то /(зь.-.. е ) 1. Опиигем способ построения минимальной ДНФ: 1. Огметим в табл. 1.14 строки, в которых соответствующая им конъюнкция'ХР.... Хешие принадлежит СДНФ, выражающей функцию /(Хь,, К ). Вычеркнем все конъюнкции в зтич строках. В Вычеркнутые в этих строках конъюнкции вычеркнем также но всех остальных строках таблицы. 3. В каждой строке выберем из оставшихся коньюнкций лишь конъюнкции с наименьшим числом сомножителей, а ос. тальнме вычеркнем. 4. В кажлой строке выберем иа одночу оставшемуся элементу и составим из них ДНФ. 5.
Из всех.ДНФ, полученных в н. 4, выберем минимальную. Заметим, что в. 5 предусматривает перебор различных ДНФ лля нахождения минимальной из них. Однако при этом число . 66 "вариантов перебора, «ак правнло, меньше, чем в случае, «огда перебвраются все равнссплы~ые ДНФ. Действу» в ссответсгв«н с еп. 1 — 5, получим мяннмалгную ДНФ, выражающую функвдю )(Х,..., Х„], Пусть Р— формула в ДЙФ, полученная в п.
5. Тогда, сслп ((зь ., м,) = 1, то Р(еь ° ., е ) 1. действительно, если «онъю«кц«я К~зц.. ...Кйм соответствует 1-5 стропе табл. !Д4, то этв строка осталась мевычер«нугой; лкба» «онъюнкция в этой строке на оценке <м,..., е > принимает зна юнпе 1. Слепопательна:, н формуле Р, содержащая одну нз тек«х каньюнкцнй в качестве лазьюнкткююго члена, прн««мает па опенке <аь ° ., е > значение 1, т.
е. Р(вь.. ! = 1. Если ((еь-...в ) О, то нв оценке <аь. ° ., е > все невычсрквугы» з табл. 1.14 конъюнкця«принимают значение О, так как все кояъюнющя, коюрые аа этой оценке прннкмают зиачсяяс 1, вычеркнуты. Слсдовачсльно, составленная пэ втп««онъюпкцнй дйф принимает на этой опек«е значение О, т.
* Р(еь ., е ) = О. Пример 1.йп. Пусп )(Хь Хъ Хз] Хгу Хат(ХХХ т! )/ Х~Х Х ьг Х~ХгХ Октав«м табл. !.!5. Отметим знаком вычеркнутые строк«. После прныенення лп. 1 — 3 в табл. 1.15 останутся конъюнкцнн, приведенные в табл. 1Лб. После при«сне«на пп. 4 н 5 «олучвм мнннмальную ДНФ Х,Хз)( Х,хь Поскольку алгорнтыы на«сждсняя мпв«нальной ДНФ лот а аа 136 таалпиа 1.1З вольно сложны, иногда примеанют алгоритмы упрощеяия, получая некоторме приечленые Лля лзльнейщего пспольюванн» ДНФ, среди которых содержатся и минимальные. К таким тяпам ДНФ относятся н соиращепные ДНФ, поторые мм будем испопьзонать в гл. 4. Сокрмлениая ДНФ формулы может быть получена, например, по следующему алюритму. Рассмотрим произвольную копъюпктивную иорызльную форму исходной формулы.
Воспользуемсн законом обобщеняой лис рибутнвнсс н (Л,'ьг'... ~'А„) й (В, уу ... Ьу В,) (А, й бй)Ч'...Ч(А~ййг)тг'..'ьт(Ааййг) и «раскроем» сиобкн. Затем произведем упрощения полученной формулы, пользуясь раиносильностямн (АЬВ)тгА Л, Лттл А и улаляя тожлсстпснно-лажные дизыонктнвные члены. В результате получим ДПФ, которая называется сокреп(вялой. 1.2А. Кщпвггтные жмене Рассмотрим одно из приложений логики высказываний — применение ее к тсорин электрических Налей, а именно к ионтактяым скемам. Пусть «ь..., х„— набор контактов в злектрнческой схеме. Контактн могут быть размыкзющнми и замыкающими. Ксмгант называется рпзммхаюи(пл, если он размыкается прн подаче напряжения на обмоигу реле, к иотораму ои подключен, а когда напряжение ие подается, контакт замкяут. Контакт назыдеегсн ьо замыкающим, если он замыкается прн подаче напряжения на обмотку реле, к которому он подключен.
а когда напряженно .не подастся, контакт разомкнут. В схеме одни и тат же контакт может неолнокрвтно быть как размыкающим, так н замыкающим. Булем считать, что х, 1, если на обмотку контаита кг подается напряжении н х, = Π— в противном случае. Каждой последовательно-паратлслыюй схеме с конгактзми кг,..., х, поставим я соответствие ее функцию проводимости 1, если схема проводит ток; гххг ° . х") = ( О, если схема не ировадпг ток. Тогда функция проводимости схемы, состоящей из одного контакта кь есть ХР, где ег = 1, если «онтакт замыкающий, и ы = = О, есле контакт разминающий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
