![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Из известных методов минимизации булевых функций в данной главе рассматриваются наиболее простые и распространенные в базисе {-,&, Ú }.
I Геометрический метод.
Применяется ввиду наглядности в основном для минимизации функций трех переменных, но его можно обобщить на большее количество переменных.
В геометрической интерпретации изобразим область определения произвольной булевой функции трех переменных множеством вершин трехмерного куба. Элементам куба можно поставить во взаимо-однозначное соответствие конъюнкции различного ранга: вершинам куба – конъюнкции третьего ранга, ребрам – второго, граням – первого. Ранг – число букв, образующих конъюнкцию. Каждый геометрический эквивалент меньшей размерности покрывается всеми геометрическими эквивалентами большей размерности (рис. 1-1).
|
|
Для функций и
на приведенных рис. 1-2 минимальными формами будут
,
или
Для второй функции задача решается неоднозначно.
Пример 1-1: Минимизировать функцию, заданную следующей таблицей истинности
Таблица 1-2 | ||||||||
x 1 | ||||||||
x 2 | ||||||||
x 3 | ||||||||
f (x 1, x 2, x 3) |
Ее формула в СДНФ имеет вид:
.
Отметим на рис. 1-3 вершины, соответствующие конъюнкциям, входящим в СДНФ данной функции.
|
2 Метод неопределенных коэффициентов.
Этот метод может быть применен для булевых функций от любого числа переменных, однако, для простоты его описания рассмотрим минимизацию функции, зависящей от трех переменных.
Представим функцию в виде следующей ДНФ:
Здесь представлены все возможные конъюнктивные члены, которые могут входить в . Коэффициенты
с различными индексами являются неопределенными и подбираются так, чтобы полученная форма была минимальной. Если задать наборы аргументов, подставить в формулу и приравнять полученные выражения (отбрасывая нулевые конъюнкции) значению функции на выбранных наборах, то получим систему уравнений для определения коэффициентов
. В общем случае в системе будет
уравнений,
- число аргументов функции.
(1)
Если функция задана таблицей, то в правой части соответствующих уравнений будут стоять нули и единицы. Для удовлетворения уравнения, в правой части которого стоит нуль, необходимо приравнять нулю все коэффициенты
, входящие в это уравнение (это вытекает из определения дизъюнкции).
Рассмотрев все уравнения, в правой части которых стоят нули, и приравняв все коэффициенты этих уравнений нулю, в остальных уравнениях вычеркивают вошедшие в них нулевые коэффициенты. Удобно полученную систему переписать в более сокращенной форме, оставив в ней уравнения, в правой части которых стоят единицы, убрав при этом из этих уравнений нулевые коэффициенты. Затем выбирают в системе самые короткие уравнения. В этих уравнениях приравнивают единице коэффициенты, определяющие конъюнкции наименьшего возможного ранга (это возможно, т.к. дизъюнкция равна единице при обращении в единицу хотя бы одного члена). При этом надо выбрать такие конъюнкции наименьшего ранга, которые чаще встречаются в уравнениях системы. Остальные коэффициенты можно положить равными 0 или 1. Затем рассматривают оставшиеся уравнения и в них выбирают коэффициенты, соответствующие конъюнкциям наименьшего ранга по тому же принципу, и т.д.
Найденные единичные коэффициенты определяют конъюнкции с наименьшим числом знаков, а форма, записанная с этими коэффициентами, определяет минимальную ДНФ данной функции.
Пример 1-2. Минимизировать функцию (см. пример 1-1).
Составим систему (обратите внимание на то, что она имеет стандартный вид, лишь в правой части изменяются значения в зависимости от таблицы истинности функции). Для удобства записи системы слева помещают координаты вершин (область определения функции). Верхние индексы коэффициентов комбинируют соответственно из записанных координат вершин с учетом взятых нижних индексов. Например, для второй вершины (0,0,1) верхним индексом для коэффициента будет 00; для
- 01 и т.д.
Из уравнений 2, 5, 6 в силу свойств дизъюнкции вытекает, что
Удобно вычеркнуть уравнения, в правой части которых стоят нули, а в остальных уравнениях вычеркнуть коэффициенты равные нулю.
После этого система примет вид:
(2)
В системе (2) в силу свойства дизъюнкции можно приравнять единице коэффициент
, тогда 2, 3, 4 и 5 уравнения этой системы превращаются в тождества, из первого же уравнения системы возьмем
. Все остальные коэффициенты во всех уравнениях положим равными нулю.
Обратите внимание на тот факт, что единице приравнивают коэффициенты, отвечающие конъюнкциям, содержащим наименьшее число переменных, кроме того, чаще встречающиеся в упрощенной системе уравнений.
Итак, мы нашли , остальные коэффициенты равны нулю. Отсюда минимальная форма данной функции:
Этот метод является громоздким, практически не используется, но мы рассмотрели его здесь с целью обоснования последующих методов.
3.Метод минимизирующих карт (гарвардский метод).
Этот метод по существу представляет собой тот же метод неопределенных коэффициентов, только записанный в более удобной форме.
Рассмотрим следующую таблицу
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
Эта таблица служит более компактной записью системы уравнений (1) метода неопределенных коэффициентов, где вместо коэффициентов в соответствующей клетке записываются сами конъюнкции. Каждая строка таблицы (3) заменяет собою соответственно 1-ое, 2-ое, …… 8-ое уравнения системы (1). Дизъюнкция всех элементов строки таблицы есть значение функции в вершине, определяемой соответствующими переменными. Так, первая строка есть значение функции в вершине
, четвертая в
или в переводе на координаты соответственно в (1, 1, 1), (1, 0, 0).
Можно показать, что если в СДНФ данной функции не входит какая-либо из восьми конъюнкций последнего столбца, то в минимальную форму этой функции не может входить ни одна из конъюнкций соответствующей строки таблицы.
Пусть, например, в СДНФ не входит конъюнкция , тогда в минимальную форму не входит, например, член
(аналогично и другие конъюнкции 3-ей строки):
Таким образом, если бы в минимальную форму входил член , то обязательно входил бы член
, что противоречит предположению.
Таблица (3) называется минимизирующей картой.
Минимизация функции производится по следующим правилам:
1. Все строки таблицы, которые соответствуют конъюнкциям последнего столбца, отсутствующим в СДНФ данной функции, вычеркивают.
2. В столбцах оставшихся строк вычеркивают все элементы, попавшие в вычеркнутые строки.
3. В каждой из невычеркнутых строк выбирают незачеркнутую конъюнкцию, содержащую минимальное число знаков (желательно, чтобы выбранные конъюнкции встречались чаще во всех оставшихся строках).
4. Взяв по одной конъюнкции для всех незачеркнутых строк и записав их дизъюнкцию, получают минимальную форму.
Заметим, что нахождение МДНФ неоднозначно, ибо произволен выбор минимальных конъюнкций в строках. Однако, все получаемые по этому методу МДНФ будут “одинаково минимальны”.
Пример 1-3. Минимизировать функцию (см. пример 1-1)
.
Строим для функции минимизирующую карту.
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
Отметим справа от последнего столбца те конъюнкции, которые входят в СДНФ данной функции. Вычеркнем неотмеченные строки (правило 1), затем вычеркнем в остальных строках (действуя по столбцу) те элементы, которые попали в вычеркнутые строки (правило 2). Во 2-ом столбце (с одной переменной) положим , при этом остальные элементы строк (1, 2, 5, 6 строки), где стоит элемент
, положим равными нулю. В строке 8 положим элемент
,
.
Итак, получим МДНФ данной функции в виде:
.
Сравните с результатами, полученными геометрическим методом и методом неопределенных коэффициентов.
Пример 1- 4. Минимизировать функцию
.
Согласно правилам 1, 2 вычеркиваем конъюнкции
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
Для удобства табличку оставшихся конъюнкций начертим отдельно, выбросив 1-3 столбцы, 1, 8 строки.
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | |
![]() ![]() | ![]() | ![]() |
Положим во 2-ой строке равным 1, обведем рамочкой, остальные члены положим равными нулю. Вычеркнем нулевые члены
в 6-й строке,
в 1-й строке. Выберем 1 из оставшихся строк самые короткие, 1-я и 6-я строки. Положим в них соответственно
, остальные члены равными нулю. В строках 4 и 5 будет по одному члену, равному 1. Итак, в каждой строке таблицы есть один член, равный 1, следовательно, минимальная форма функции будет
.
Возможен другой вариант минимальной формы. Рассмотрим на таблице.
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() | |
![]() | ![]() | ![]() |
Пусть в 4-й строке , а остальные члены равны нулю. Тогда в строке 5:
можно положить равными нулю. Вычеркнем
в 1-й и 6-й строках (они короче других), положим соответственно
. Тогда в строках 2 и 3 будет по одному члену, равному единице. Итак, минимальная форма функции
.
Методы неопределенных коэффициентов и минимизирующих карт приводят к громоздким записям (число строк таблицы для функции переменных равно
, а число столбцов
). Использование этих методов уже для
порядка 8-10 становится затруднительным.
Дата публикования: 2015-02-22; Прочитано: 924 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!