<< Пред. стр. 6 (из 7) След. >>
Список литературы по разделу
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
f =
Полиномиальные представления позволяют зачастую записать функции, зависящие более чем от двух аргументов, проще, чем в ДНФ или КНФ.
Задачи минимизации могут также решаться в монофункциональных базисах функций Вебба или Шиффера. Здесь существуют два подхода к проблеме минимизации: либо по аналогии с минимизацией в классе ДНФ применяется специальный метод минимизации для монофункционального базиса, либо минимизация производится в классе ДНФ, а затем строится специальный метод перехода от базиса конъюнкция, дизъюнкция, отрицание к монофункциональному базису [5].
Геометрический метод многомерного куба
При небольшом числе переменных более наглядным является метод минимизации, основанный на геометрическом представлении булевых функций. Для каждого сложного высказывания в соответствии с его формулой можно построить геометрическую модель. Область определения булевой функции у = f( ) можно рассматривать как совокупность n-мерных векторов (рис. 2.2). В общем случае совокупность векторов ( ) отображается на множество вершин n — мерного куба. Все такие вершины образуют логическое пространство. Подмножество отмеченных вершин является отображением на n-мерном кубе булевой функции от n — переменных в СДНФ.
Рисунок 2.2 — Геометрическая модель булевой функции
Рассмотрим пример геометрической интерпретации области определения функции трех переменных. Куб помещают в начало пространственной системы координат. Оси называют теми же буквами, которыми обозначены независимые переменные (аргументы) функции. Пусть дана функция:
На кубе (рис.2.3) вершины, соответствующие конституентам единицы СДНФ заданной функции, обозначены затемненными кружочками. Восемь
вершин куба отражают все минитермы третьего ранга булевой функции от трех переменных в СДНФ.
Как же использовать для целей минимизации геометрические модели формул? Для отображения функции от и переменных, представленной в любой ДНФ, установлено соответствие между минитермами функции и элементами и мерного куба. Минитерм (n-1)-го ранга можно рассматривать как результат "склеивания" двух минитермов n — го ранга (18).
Рисунок 2.3 — Отображение булевой функции на трехмерном кубе
На n -мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координаты хi, соединяющим эти вершины ребром. Говорят, что ребро покрывает инцидентные ему вершины. Таким образом, минитермам (n-1)-го ранга соответствуют ребра и-мерного куба. Аналогично установлено соответствие минитермов (и-2)-го ранга граням и -мерного куба, каждая из которых покрывает четыре вершины и четыре ребра.
Для рассматриваемой функции на кубе (рис. 2.3) отмечены затемненными кружочками четыре вершины. Используя обозначения ребер, покрывающих эти вершины, можно записать сокращенную на кубе формулу
Эти же четыре вершины можно покрыть не тремя, а двумя ребрами:
Если удается использовать не все названия ребер так, что все вершины, заданные исходной функцией, оказываются покрытыми ребрами, то приходят к одной из минимальных форм записи формул. Минимальных форм может быть несколько. Если отмеченные вершины принадлежат одной грани, то можно дизъюнкцию из четырех конъюнкций заменить одной буквой — названием грани.
Рассмотрим отображение на кубе следующей функции трех переменных:
(2.44)
Здесь и — минитермы второго ранга отражают ребра, покрывающие вершины соответственно: и (склеивание по хз), и (склеивание по хз); а хз — минитерм первого ранга — отражается на кубе гранью, покрывающей вершины: и ребра: .
Элементы n -мерного куба, характеризующиеся s измерениями, называются s-кубами. Так, вершины являются 0 -кубами, ребра — 1-кубами, грани— 2-кубами и т.д. Таким образом, можно считать, что минитерм (n -— s)-гo ранга в ДНФ для функции н переменных отображается s-кубом, причем каждый s- куб покрывает все те s-кубы низшей размерности, которые связаны только с его вершинами. В функции (2.44) минитермы х,х~ и х,х~ соответствуют 1- кубам (s =3-2=1), а минитерм х3 отображается 2-кубом (s =3-1=2).
Итак, любая ДНФ отображается на и-мерном кубе совокупностью s- кубов, которые покрывают все вершины, соответствующие конституентам единицы. Справедливо и обратное утверждение: если некоторая совокупность s-кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим s-кубам минитермов является выражением данной функции в ДНФ. Такая совокупность s-кубов образует покрытие функции. Покрытие, соответствующее минимальной форме, называют минимальным покрытием.
Если булева функция содержит не три, а четыре независимых переменных, то используется четырехмерный куб, где три направления обычных и одно новое — направление "вовнутрь". В четырехмерном кубе имеются вершины, ребра, грани и подкубы. Методика построения многомерных кубов изложена в литературе [5], [6]. Однако использование кубов для целей минимизации при n > 4 требует настолько сложных построений, что теряются все преимущества этого метода перед аналитическими способами.
При числе переменных больше трех можно рекомендовать минимизировать булевы функции с помощью карт Карно.
Карты Карно
Карты Карно представляют собой графическое изображение логических функций. Карта разделена на квадратики, каждому из которых соответствует определенная комбинация значений всех входных переменных (таблица 2.7). Каждая сторона квадратика представляет собой границу между значениями переменных. Обозначения входных переменных ставятся сбоку или сверху карты и относятся ко всему столбцу или строке следующих за ними квадратиков. Значения входных переменных на карте не пишутся (таблица 2.8). Считается, что значения входных переменных в этих квадратиках равны "1". В квадратиках записывают значения функций "0" или "1" при данных комбинациях значений переменных (таблицы 2.9 и 2.10).
Таблица 2.7
X2
X1
Таблица 2.8
X2
X1
Из заданной карты Карно аналитическое выражение логической функции можно выписать несколькими способами. При этом получаются выражения различной формы и сложности, которые, однако, определяют одну и ту же функцию. Важно научиться получать сразу наиболее простые и удобные по форме аналитические выражения. Если задана карта какой-либо функции, то можно записать эту функцию в ДНФ. Например, для карты таблицы 2.10 аналитическое выражение функции равно дизъюнкции конъюнкций всех квадратиков, содержащих единицы:
f = .
Эту функцию можно записать в более простой форме, если выбирать комбинации переменных не для каждого квадратика, а сразу для пар соседнихквадратиков, содержащих "1". Для карты таблицы 2.11 функция f = , для карты таблицы 2.12 f= ,для таблицы 2.13: f = , так как контур, объединяющий два квадратика, определяется только одной переменной и не зависит от другой переменной.
Таблица 2.9
X2
0 0
0 1
X1
Таблица 2.10
X2
0 1
1 1
X1
Таблица 2.11
X2
0 1
1 1
X1
f =
Таблица 2.12
X2
0 1
1 1
X1
f =
Таблица 2.13
X2
0 1
1 1
X1
f =
Очевидно, что самое простое выражение получается тогда, когда контуры содержат максимально возможное число квадратиков.
Карта Карно обладает тем достоинством, что она содержит столько клеток, сколько таблица истинности логической функции строк. Это делает карту менее громоздкой, наглядной и позволяет использовать ее лдя синтеза, анализа и минимизации логических функций.
Карты Карно для трех и четырех переменных приведены в рис. 2.4 и рис.2.5. Области переменных в картах распределяются таким образом, что при переходе от одного квадратика к другому (соседнему) всегда меняется значение только одной переменной х,. от прямого значения к инверсии и обратно. Крайние квадратики карты (верхние, нижние и боковые) так же отличаются друг от друга значением только одной переменной, так как являются тоже "соседними" между собой в этом смысле.
Рисунок 2.4 — Карта Карно трех переменных
X3
X1
X2
Рисунок 2.5 — Карта Карно четырех переменных
X3
X2
X1
X4
Каким же образом составить карту Карно и как ей пользоваться'? Рассмотрим это на примере.
Пусть, например, задана булева функция f ( ) в ДНФ, зависящая от четырех переменных:
f =
Представив функцию в СДНФ (18) и исключив повторяющиеся слагаемые (19), получим:
f =
Заполним карту Карно для четырех переменных, проставляя в карте таблицы 2.14 единицы для каждого члена дизъюнкции функции f. Оставшиеся клетки оставляем пустыми. Объединяем все «1» и могут накладываться один на другой. При этом для получения более простого выражения функции нужно составить сначала контуры с возможно максимальной площадью, затем контуры с меньшей площадью. Это исключает возможность получения «лишних контуров».
Таблица 2.14 – Пример заполнения Карты Карно
Рисунок 2.5 — Карта Карно четырех переменных
X3
1
1 1
1
1 1
1 1
1 1
1
X2
X1
X4
Рассмотрим свойства контура. При переходе от одной клетки карты к другой, одна из переменных меняет свое значение, поэтому выражение контура из двух клеток не зависит от этой переменной, а определяется всеми остальными переменными. Это правило справедливо и для контуров, ограничивающих число клеток, больше двух.
Отсюда вытекает, что для n = 4 контур из восьми клеток представляет собой минитерм первого ранга (n-3) ДНФ функции; из четырех клеток – минитерм второго ранга (n-2) ; из двух клеток – минитерм третьего ранга (n-1). Следствием этого является правило «считывания» минимизированной функции с карты Карно.
Для рассматриваемого примера из таблицы 2.14:
f = .
Здесь каждый аргумент минитерма функции представляет собой переменную, которая в пределах контура не изменяет своего значения, причем «1» соответствует прямое значение аргумента, «0» - его отрицание (инверсия).
Для минимизации функции пяти переменных (рис. 2.6) используется две таких карты, как для четырех переменны; для логических функций шести переменных (рис. 2.7) – четыре такие карты. Карты для числа переменных больше шести применяются редко, так как они становятся громоздкими и лишены наглядности.
X5 X5
X4
X2
X1
X3
Рисунок 2.6 — Карта Карно для пяти переменных
X5
X4
X3
X2
<< Пред. стр. 6 (из 7) След. >>
Список литературы по разделу