Теперь доходит очередь до элемента 00101, обладающего тремя соседями по переменным x1, x2, и x4. Мы находим элемент 11111, ортогональный ему по этим трем переменным, и убеждаемся, что он также принадлежит множеству М1 и имеет соседей по перечисленным переменным. Последнее выясняется простым сравнением соответствующих булевых векторов, выбираемых из таблицы и представляющих собой перечни соседей у рассматриваемых элементов. Отсюда следует, что в множестве М1 существует максимальный интервал - - 1 - 1 и что этот интервал обязателен.
 |
Полученное таким образом решение имеет следующий вид:
Итак, в рассматриваемом примере процесс редуцирования благополучно завершился получением кратчайшей ДНФ. Конечно, могут встретиться и менее удачные в этом смысле булевы функции, при минимизации которых данным методом будут возникать критические ситуации, когда приходится или выбирать один из возможных путей продолжения процесса конструирования ДНФ, довольствуясь приближенным решением, или организовывать перебор вариантов, достаточный для гарантированного нахождения оптимального решения.
Следует, однако, заметить, что при рассмотрении различных булевых функций с числом переменных не свыше 15 критические ситуации будут встречаться относительно редко. А именно на такие функции и ориентирован данный метод — произвольные функции с большим числом переменных практически трудно даже задать, поскольку для этого необходимо перечислить все 2n значения функции.
Представление булевой функции на гиперкубе и его двумерной развертке. Булево пространство М можно представить в виде n-мерного куба (гиперкуба), 2n вершин которого задают элементы множества М, а n2n-1 ребер связывают соседние элементы.
Графическое изображение гиперкуба получается итерационным методом удвоения размерности, при котором 0-мерный куб представляется одной точкой, а изображение (n + 1) -мерного куба получается из изображения n-мерного куба смещением его в некотором направлении, условно ортогональном ранее использованным, и включением в новое изображение как исходного, так и смещенного изображения вместе с трассами вершин, проходимыми при смещении. Примеры такого построения до значения n =5 включительно показаны на рис. 41 и 42. Там же показано, какие конкретно элементы булева пространства представлены различными вершинами (при n = 4 и n = 5 показаны лишь некоторые из них).
Булева функция может быть задана выделением ее характеристического множества М1 — соответствующие вершины зачерняются. Так, на рис. 42 задана булева функция, рассмотренная в предыдущем примере.
При таком представлении интервалы характеристического множества М1 получают некоторую наглядность, поскольку они соответствуют подкубам рассматриваемого гиперкуба и их можно распознавать визуально, глядя на графическое изображение булевой функции. Однако уже при n = 5 такое изображение представляет собой довольно запутанную картину, распутать которую можно, перейдя к двумерной развертке гиперкуба.
Естественный способ получения двумерной развертки гиперкуба продемонстрирован на рис. 43, где показанный на предыдущем рисунке пятимерный куб последовательно разворачивается путем «разрезания» некоторых ребер и соответствующего «выпрямления» в пространство меньшей размерности.
В результате получается двумерная матричная сеть, изображенная на рис. 44. Ее узлам соответствуют элементы булева пространства М, получаемые соединением вектора, отмечающего горизонтальную линию, с вектором, отмечающим вертикальную линию. При этом левый верхний узел представляет набор 00000, соседний с ним справа — набор 00100, соседний снизу — набор 01000 и т. д. Интересно отметить, что последовательность булевых векторов, которыми оказываются пронумерованы линии как горизонтальные, так и вертикальные, представляют код Грея для натуральных чисел, известный также под названием симметричного кода и нашедший применение в технике благодаря тому, что
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.