XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 68
Текст из файла (страница 68)
После этого применяют тождество поглощения'. Как только сокращеннвл ДНФ тем или иным способом найдена, приступают к нахождению ядра. Ядро можно определить (без использования карты Карно) с помощью так называемой таблицы Квабна. Столбцы этой таблицы соответствуют элементарным конъюнкциям исходной СДНФ, а строки — простым импликантам сокращенной ДНФ. На пересечении строки и столбца проставляется знак „+" (плюс), если простая импликанта данной строки покрывает элементарную конъюнкцию данного столбца. Ядро вычисляется так: отмечаем столбцы с 'Смс Гаериеое Г.П., Саионсенко А.А.
426 б. БУЛЕВЫ ФУНКЦИИ единственным знаком „+", тогда простые импликанты тех и только тех строк, в которые попал этот знак, образуют ядро. Для примера 6.13.б (см. рис. 6.14) получим таблицу Квайна, изображенную на рис. 6.16. Рис. 8.16 (В целях экономии места элементарные конъюнкции в таблице заменены цифровыми обозначениями соответствующих вершин и граней булеза куба — точно так же как при обозначении прямоугольников на картах Карно. Ядровые импликанты выделены жирным шрифтом.) По таблице Квайна можно составить и функцию Патрика для перечисления тупиковых ДНФ.
Для этого нужно отметить все столбцы таблицы, в которых на пересечении со строками, соответствующими ядровым импликантам, не стоит знак „+". Для разбираемого примера таковым является только последний столбец. Чтобы покрыть соответствующую элементарную конъюнкцию СДНФ, можно выбрать одну из двух простых импликант: х1хгхя или хгхзх4. В заключение рассмотрим очень кратко применение карт Карно к построению минимальных ДНФ часпгпчмых булевых фу44к44пб, т.е. частичных отпображений из множесгва (О, 1~" в множество 10, Ц. 6.6.
Построение ияяямальиых ДНФ 427 Частичная булева функция может быть задана посредством карты Карно, в которой кроме клеток с единицами и пустых клеток будут клетки, заполненные прочерками (-). Такой прочерк означает, что на соответствующем наборе функция не определена. Склейка для частичной функции (заданной картой Карно) проводится таким образом, что выделяются прямоугольники максимальной площади (содержащие 2~ клеток, для некоторого я), каждая клетка которых содержит либо единицу, либо прочерк, причем существует по крайней мере одна единичная клетка. Пример 6.15.
Пусть частичная функция Дхмхз,яз) задана картой Карно, приведенной на рис. 6.17. Прямоугольник макси- . ' ' о6 61 И ~О мальной площади (равной 4), состоюций из единицы и прочерков, записывается как Ох х. Следовательно, минимальная ДНФ для заданной функции будет У~. ф Охх По поводу рассмотренного при- Рис. 6.17 мера возникает такой вопрос почему не принят во внимание другой прямоугольник (площади 2), содержащий клетку с единицей и клетку с прочерком: х007 Связано зто вот с чем. Перед тем как выделять упомянутые вьппе прямоугольники, мы на самом деле доопределяем исходную частичную функцию (получая обычную булеву функцию) так, чтобы в максимальном числе клеток, в которых стоят прочерки (но не нули!), появились единицы.
Точнее говоря, среди прямоугольников (с прочерками), содержащих данную единицу, выбирают для замены прочерков единицами такой, который имеет максимальную площадь. Прочерки же в остальных прямоугольниках заменяют нулями. В примере 6.15 мы доопределяем исходную функцию так, что получается функция ~м задаваемая картой Карно, приве- 6. ВУЛЕВЫ ФУНКЦИИ хОО Охх Рис.
О.19 Рис. 6.18 денной на рис. 6.18. Эта функция имеет минимальную ДНФ х4. Следовательно, и частичная исходная функция может быть представлена такой ДНФ, поскольку на всех наборах, на которых она определена, она принимает такое же значение, как и функция У4. Конечно, мы могли бы доопределить функцию у по-другому, так, чтобы получилась функция у2, заданная картой Карно, приведенной на рис.
6.19. Ясно, что Ь = Изхз, поэтому и ча стичная функция у может быть определена такой ДНФ. Но эта ДНФ не минимальна для данной частичной (именно частичной!) функции, поскольку первый способ доопределения дал ДНФ, содержащую лишь один литерал.
Таким образом, в отличие от минимизации булевых функций при минимизации частичных булевых функций не следует выделять все максимальные прямоугольники с прочерками, содержащие данную единичную клетку карты Карно, достаточно выбрать произвольно любой иэ таких прямоугольников. Но, конечно, не нужно забывать о том, что каждая единица на карте должна быть покрыта некоторой склейкой. Пример 6.16. Для карты на рис.
6.20 следует взять обе склейки на четыре позиции: 00 х х и х х00, получив для заданной этой картой частичной функции минимальную ДНФ в виде Х1Х2 Ч хзх4. Заметим, что без использования склеек с прочерками мы вообще не могли бы минимизировать данную функцию. Нуж- 429 6.7. Теорема Поста но также отметить, что не всегда использование „частичности" функции позволяет получить минимальную ДНФ для нее. Так, на представленной на рис. 6.20 карте в случае, если мы переместим нижнюю единицу на строку вьппе, обычная склейка на две позиции дает лучший результат: хтхзхе, а записанная вьппе ДНФ уже не будет минимальной (и даже кратчайшей). 00хх хх00 Рис.
6.20 6.7. Теорема Поста В силу теоремы о предстпавлекии любой булевой утуккции диэъюнктпивной или конъюнктивной нормальной Яормой стпандартный базис (тт',, ) является полным множеством. Поскольку, согласно законам де Моргана, можно выразить кокьюнкцию через диэъюккцию и отрицание, равно как и дизъюнкцию можно выразить через конъюнкцию и отрицание, то при удалении из стандартного базиса одной функции, дизъюнкции или конъюнкции, при сохранении отрицания, получим снова полное множество.
Прежде чем рассматривать другие примеры полных множеств, установим один важный факт. ч Из условия теоремы следует, что каждая функция т Е Р может быть представлена некоторой формулой тр над С, т.е. у(хт,...,х„) = тр(хм...,х„). (6.17) Теорема 6.3. Пусть г' и С вЂ” некоторые множества булевых функций, причем г' — полное множество. Тогда, если каждая функция из г' может быть представлена некоторой в ормулой кад мкожестпвом Ст, то С вЂ” полное множество. 430 б.
БУЛЕВЫ ФУНКЦИИ Докажем, что всякая формула над Р эквивалентна некоторой формуле над С, т.е. всякая функция у, представляемая формулой над г', может быть представлена также и некоторой формулой над С. Доказательство проведем по такой схеме: сначала убедимся в справедливости утверждения для „базисных" формул, т.е. для переменных и констант из Р, а затем в предположении, что оно уже доказано для формул Фм ..., Ф„, где п > 1, докажем его для любой формулы вида ДФм...,Ф„), где у" е г'. Такой метод доказательства называют доказательством индукцией по построению формулы.
Пусть р — какая-то формула над г'. Если ~р= х, где х — булево переменное из множества Х, то, поскольку каждое переменное есть, по определению, и формула над С, функция у представляется формулой над С. Если ~р есть константа из Р, то представляющэл <р формула над С существует ввиду (6.17). Рассмотрим формулу над Р вида ДФы...,Ф„), где п ) О, у Е Р, а Фм ..., Ԅ— формулы над Р.
Согласно предположению индукции, каждая формула Ф;, 1 = 1, п, может быть заменена эквивалентной ей формулой 9; над 0 (т.е. имеет место тиохедесп~во Ф, = 9; над РОС). Тогда, используя правила эквивалентных преобразований формул (см. теорему 6.1), получим тождество а в соответствии с (6.17) будем иметь у(9ы...,9 ) = Ф(йм...,6„). (6.18) Правая часть тождества (6.18) и есть формула над С, эквивалентная исходной формуле над Р. Поскольку в силу полноты множества Р любая булева функция может быть представлена некоторой формулой над Г, а любая такал формула, как мы только что доказали, эквивалентна некоторой формуле над С, то любая булеза функция 431 6.7.
Теорема Поете может быть представлена некоторой формулой над С, что и доказывает полноту множества С. ~ Пример 6.1Т. Рассмотрим базис Жегалнина (Ю,, Ц. Чтобы доказать полноту этого множества, заметим, что хЧу=х.у®хЮ9, х=х®1, т.е. каждый элемент стандартного базиса может быть представлен формулой над базисом Жегалкина. Отсюда и следует (ввиду полноты стандартного базиса и теоремы 6.3) полнота базиса Жегалкина. з(1 Любую формулу над базисом Жегалкина называют поли- номом 2Кееалкина. Полинам Жегалкина от и переменных может быть записан в виде Р(хм...,х„) = ~~З (шой2)а;„,„з х;,х;,...х; (О,'„...,,„)С(нг,,е> где коэффициенты полинома а;„,; е (О, Ц индексированы всеми возможными подмножествами множества (1, 2, ..., и) (коэффициент ае соответствует пустому множеству).
В частности, при и = 3 будем иметь: азгзхзхгхз е9 аггхзхг Ю аззхзхзЮ Вагзхгхз®абаз®агхгевазхзВао (619) (общий вид полинома Жегзлкина от трех переменных). Формула вида и ','~ (шоа2)а;х; Юае (6.20) называется полиномом 2Кееалкина первой спзепени от переменных. В таком полиноме отсутствуют „нелинейные" слагаемые, т.е. все коэффициенты, индексированные более чем одноэлементными подмножествами, равны 0 (и вместе с ними равны 0 все слагаемые, содержащие конъюнкции переменных). 432 В. БУЛЕВЫ ФУНКЦИИ Можно доказать следующее достаточно простое, но важное утверждение. Теорема 6.4. Полипом Жегзлкина для любой булевой функции определен однозначно.
Для функций от небольшого числа переменных (не превьппающего 4) можно использовать мепзод иеопределекмыи моэффициемпзов, позволяющий получить полипом Жегалкина данной функции. Проиллюстрируем этот метод на примере. Пример 6.18. Пусть вектиор эвачевиб булевой функции у равен 11001011. Найдем полипом Жегалкина, представляющий у. Поскольку размерность вектора значений у равна 2з = 8, то у задана как функция от трех переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
