Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 20
Текст из файла (страница 20)
Например, у (х1, хт, хз))1 — — '44(О, 1, 2, 3, 7) (табл. 2.11). Зададим булеву функцию 1(х1, х2, ..., Х„) с помощью гиперкуба, каждой вершине которого взаимно однозначно соответствует двоичный набор (а1, ат, ..., 47„); вершины упорядочены по ярусам (в 6-й ярус входят (".) вершин, которым соответствуют двоичные наборы, содержащие 6 единиц); вершины соединены ребром, 12.3.
Минимизация брлееых 04рикциа е классе ДНФ 103 если соответствующие им двоичные наборы отличаются в одном и только одном разряде. Вершины, в которых у'(х1, хз, ..., Х„) = 1 и которые образуют гиперкуб, порождают единичный интервал втой функции. Единичный интервал те булевой функции 1 называется максимальным, если не найдется единичный интервал уы строго включающий 1,. В данном примере единичными интервалами являются множества вершин (О), (1), (2)> (3)4 (7)1 (О, Ц, (О, 2), (1, 3), (2, 3)4 (3, 7), (О, 1, 2, 3); максимальными интервалами — (О, 1, 2, 3), (3, 7) Конъюнкция, соответствующая максимальному единичному интервалу функции 1, называется нросотоб имяликанатоб этой (О, 1, 2, 3) н х(, (3, 7) и *2хз. Будем задавать единичный интервал перечислением вершин, а также с помощью последовательности символов О, 1, —, где прочерк означает отсутствие в конъюнкции соответствующей перемен- (О, 1, 2, 3) ++ О-, (3, 7) ++ -11.
Дизъюнкция всех простых импликант булевой функции называется сокраи(ениад ДНФ втой функции. Переход от совершенней ДНФ к сокращенной однозначен и осуществляется с помощью непарного сравнения конституент соседних ярусов (номера которых отличаются на единицу). Пример 2.4. нейдем сокрвшениую ДнФ булевой Функпин у(х1, хт, хз, х4) (рис.
2.2): У(х1, хт, х6, х4))1 = и(0, 1, 2, 3, б, 7, З, Ю, 12, 14, 15). Сравнивая точку 0000 нулевого ярусе с точпвми яервого яруса 1000, 0010 и 0001, получаем три ребра, -000, 00-0 и 000- соответственно, которые обрвзу1от Гл. 2. Математическая яозико 104 12.3. Минимизация булевых функций а классе ДНФ 105 нулевой реберный ярус. действуя аналогично, полу~вен: ребра первого яруса (8, 12) -+ 1-00, (8, 10) -+ 10-0, (2, 10) -+ -010, (2, 6) -+ 0- 10, (2, 3) + 001-, (1, 3) -+ 00 — 1; ребра второго круса (12, 14) -+ 11-0, (10, 14) -+ 1-10, (6, 14) -+ -110, (6, 7) -+ 011-, .
(3, 7) -+ О- 11; ребра третьего яруса (14, 15) -+ 111-, (7, 15) -+ -111. Все гочки включены э ребра, следовзгелыю, ни одна нз точек не образует максимальный интервал. Сравнивал ребра соседних прусов, йормируем ярусы граней: нулевой— (-000, -010) = (00-0, 10 — О] -+ -0-0, (аао-, 001-) = (Оо-о, 00-1) -+ оо — —; первый— (1-00, 1-10) = (10-0, 11-0) -+ 1--41, (-010, -110) = (0-10, 1 — 10) -+ — — 10, (0-10, О-1Ц ю (001 —, 011-) -+ О- 1-," эгорой— (оп-, ш-) = (001, — ш) -+ -и- . Все шестнадцать ребер включены в грани, следовательно, ни одна нз пих не образует максимальный интервал. Сравнивал грани соседних ярусов, замечаем, что ни одна из пар сравниваемых граней ие образует куб.
Следовательно, все шесзь граней лвллэнсл максимальными ннгервзламн, и соогвегстэуюшие нм коньюнккнп представляют собой простые импликангы. В результате сокрашениал ПНФ рассматриваемой булевой функции имеет вид У(хн хз, хз, хз) = Узле Ч Узпз Ч хзпз Ч хзУз Ч Узхз У хзхз, и слоиносгь ее 12. Слоиносгь умеиьшигсл до 6 в результате определения мпнималыюго покрытии столбцов строками в импликзнгной таблице (табл. 2.12) Таблица 2.12 В столбцах, соответствующих вонсгптуеигам 1, 12 и 15, нюсоднгся одна 1, следовательно, соответсгвуюшие строки (00- —, 1 — -О, -11-) образуют вдро покрытия.
Эго ядро явлнегсл покрьпяем столбцов сгрокзмн, следовательно, оно миипмалыюе (рис. 2.2): Г (хз, зз, хз, хз) = Уз из Ч хзпа Чхзхз. Большое значение имеют слобоонредсяенные буяевы функции 1(хг, хт, ..., х„) которые обладают следующими свойствамн: 1) число переменных н велико; 2) мощность объединения единичной Уг И НуЛЕВОй Уо областей намного меньше, чем 2", где единичную и нулевую области образуют вершины, в которых функция равна соответственно 1 и 0; 3) единичная и нулецая области задаются соответствующими интервалами.
Множество вершин гиперкуба, на которых функция равна 0 и которые образуют гиперкуб, называется нулевым интервалом. Сокращенную ДНФ слабоопределенных функций строят с помощью таблицы различий, Таблицей различий называется двумерная таблица размера н х Щ, каждой строке которой взаимно однозначно соответствует разряд рассматриваемого единичного интервала, столбцу — нулевой интервал, а на пересечении з-й строки с 7'-м столбцом находится результат операции: О 9 О = О, 1 (В О ес 1, — 9 О сс О, 091 сп1, 191ееО, — 91=0, 09-= О, 19-= О, — 9-= О, причем в качестве первого аргумента берется значение з-го разряда единичного интервала, в качестве второго — значение з-го разряда нулевого интервала, соответствующего у'-му столбцу. Выделение максимальных интервалов сводится к покрытию столбцов строками таблицы различий.
В самом деле, максимальные интервалы в слабоопределенных функциях состоят из вершин единичной и неопределенной областей. Единица в клетке (з, т) таблицы различий показывает, что если оставить з-й разряд в конъюнкции, то 7-й нулевой интервал не входит в гиперкуб, соответствующий втой конъюнкции. Следовательно, покрытие столбцов строками порождает максимальный интервал полностью определенной булевой функции 7 (хг, хт, ..., х„), единичная и нулевая области которой включают соответственно единичную и нулевую области заданной функции у(х1, хт, ..., и„).
Функция у (хг, хт,..., х„) называется мазкорирующей функцию у (х1, хт,... х ) у(хь хт ° ° ° х ) э )(хь хт~ ° ° ° х ) ° Пример 2.5. Найдем минимальную ДНФ булевой йункцни / 1 ив интервалах 0-0-0-0, 11-0-01, 0 †001-, 1 0 на интервалах 10-0-01, 00--10-, 1101 †0- Гл. 2.
Мащемащическав логика 106 у(хм*э, "., хт) =УсУэ Чхэус Чкэхв Тупиковые ДНФ фувкцвк ус»э»т, ..., х„) Рис. 2.3 этой функции (рнс. 2.3). пню~,~З~. или функнни, водкиной с помощью десятичных эквяввлентов минимальных и максимальных элементов соответствующих интервалов, которые получаются в реаультате подстановки нулевого (00...0) и еднничного (11...1) кода вместо прочерков: [ 1 на интервалах [О, 42], [97, 117], [2, 51], ], О на интервалах [65, 85], [4, 29], [104, 109]. Выделим мщокество максимальных иитеРвалов (Уос„,), содеРиащих единичный интервал [О, 42] во таблице равлнчий (табл.
2.13), у которой строки идентифицированы буквамн а, Ь, с,а, е, у, 6. Таблица 2.13 Испольауя метод Петрика, найдем все покрытия этой таблнпы (аЧА)еа ю ае. Имеем адно поврытие, соответствующее максималыюму интервалу 0 — -Π— ~ Э [О, 59], которому соответствует простая импликанта УсУэ. Аналогично находим миоиества максимелынах интервалов, содериащих остальные единичные интервалы: (тасос Э [97, 117]) = ([32, 119]) е+ хэпс, ( Уоссс Э [2 51]) ([О 59]~ [2 123]) ее УсУь Уэ»е, В реаультете полученасокращеннаяДНФ булевойфункпнну(хы хт, ..., »т), являющейся уие полностью определенной. Единичная область К функции у содержит единичную область 91 функиин у: К Э К, нулевая область | фунвцни у— нулевую область 12 функции у: ь~ э ~ы Выделение максимальных интервалов, построение сокращенной ДНФ функции у — первый этап минимизации в классе ДНФ, при этом нулевой столбец в таблице различий указывает на противоречивость заданной функции.
Вторым этапом является переход ат сокращенной ДНФ функции у' к тупиковой ДНФ Функция 7 мажорирует заданную функ- 52.3. Микимизацил булевых функций в классе ДНФ 107 Тупиковой ДИФ булевой функции у (х1, хэ,..., х„) называется ДНФ, не определяющая функцию у с точностью до неопределенной области при вычеркивании хотя бы одного произвольнога первичнаго герма х '. Тупиковая ДНФ булевой функции получается в результате покрытия столбцов строками импликакпткой пгаблицы (двумерной таблицы, каждой строке которой взаимно однозначно соответствует максимальный интервал, столбцу — единичный интервал, а на пересечении э-й строки с у'-м столбцом находится 1, если у-й единичный интервал входит в э-й максимальный интервал, в противном случае на пересечении находится 0).
Построим для рассматриваемого примера нмплнкантную таблицу (табл. 2.14) . Таблица 2.14 Таблица имеет одно покрытие, его обраауют первая н вторая строки. Это докрытяе пороидает тупиковую ДНФ функции У(хы»э, ..., хт) = УсУэ Ч»»Ус. Теоретически числа тупиковых ДНФ булевой функции у(х1, хз,..., х„) при и -> со растет как число всех различных булевых функций от п переменных'22".
Практически же количество 2" тупиковых ДНФ увеличивается значительно медленнее, чем 2 из-за большого количества недоопределенных вершин гиперкуба. Перебор всех тупиковых ДНФ булевой функции определяет выбор минимальной ДНФ этой функции. В рассматриваемом примере тупиковая ДНФ одна; следовательно, она является минимальной ДНФ функции 1(х1, х2, ...
1 х7 ) у(а, 6, с, б) = ас( Ч 6с, где а = х1, 6 = хэ, с = хе, Ы = хь. При таком доопределении функция зависит от четырех переменных. Булева функция, полученная из функции у (х1, хэ,..., х„) фиксированием э'-й переменной, т' й (1, 2, ..., пу, как уже было определено, называется осптапточкой. Если х; = 1, то остаточная функция называется единичной, если х; = 0 — нулевой.
Булева функция У(х1, хт, ..., х„) квсуи1вспгвекка зависит от (-й переменной, если ее остаточные функции па этой переменной равны. Гл, 2. Аэатематическая логика 108 12.4. Лолната. Ластраекие суперпагиций булевых функций 109 $2.4. Полнота. Построение суиериозиций булевых функций Любое сложное высказывание можно представить в виде выражения, в которое входят простые высказывания (переменные) х(, операции дизъюнкции, конъюнкции, отрицания и, быть может, скобки. Рассмотрим, каким свойствам должны удовлетворять оцерации, с помощью которых можно выражать любое сложное высказывание. Будем моделировать конъюнкцию и дизъюнкцию соответственно последовательным и параллельным соединением ключевых элементов (для определенности — полупроводниковых), отрицание — включением нагрузки в коллекторную цепь транзистора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
