Студентам > Рефераты > Вычислительные машины и системы
Вычислительные машины и системыСтраница: 9/12
i=0
- 5 -
4) Два неодинаковых минтерма или макстерма имеют
хотя бы од-
ну переменную, входящую в один из них в прямой, а в
другой - в
инверсной форме, следовательно
m 4i 5. 0m 4j 0
= 0, если i 7- 0 j;
M 4i 0 V
M 4j 0 = 1, если i 7- 0 j.
2Основная теорема
алгебры логики 0: любую булеву функцию от n
переменных можно выразить логической суммой минтермов,
которая
называется 2 совершенной нормальной дизъюнктивной
формой 0, или логи-
ческим произведением макстермов, которое
называется 2 совершенной
2нормальной конъюнктивной формой 0.
Логические функции отражают не только принцип работы
некото-
рых частей ЭВМ, но и их состав, если каждой элементарной
функции
соответствует реальный физический элемент. Любая сложная
логичес-
кая функция может быть реализована некоторой частью ЭВМ,
если эта
часть построена с помощью такого набора элементов,
который реали-
зует все функции одной из функционально полных систем.
Такой на-
бор называется функционально полным набором логических
элементов
Поскольку каждая функция может быть представлена в
виде раз-
личных логических уравнений, каждая функция может быть
реализова-
на при помощи различных логических схем. Очевидно,
что более
простому логическому уравнению соответствует более
простая схема.
Упрощение (минимизация) функции сводится к получению ее
минималь-
ной дизъюнктивной или конъюнктивной нормальной формы,
т.е. такой
формы, при которой функция содержит наименьшее число
переменных и
знаков логических операций.
Существует несколько методов минимизации. В
дальнейшем мы
рассмотрим метод непосредственных преобразований и метод
диаграмм
Вейча.
ПЕРВЫЙ СЕМЕСТР
ЛЕКЦИЯ N 7
2МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ
2Метод непосредственных
преобразований
Суть данного метода заключается в том, что
минимизация ис-
ходной логической функции производится путем применения к
отдель-
ным членам или группам членов формулы, выражающей данную
логичес-
кую функцию, основных законов алгебры логики с целью
получения
минимальной формы функции, т.е. такой, которая не
содержит лишних
переменных или членов.
Лишними переменными или членами являются те, которые
не вли-
яют на значение преобразуемой формулы.
Пример:
4_ 5
4_
x 41 5. 0x 42 5. 0x 43 0 V
x 41 5. 0x 42 5. 0x 43 0 =
x 42 5. 0x 43 5. 0(x 41 5
0V 5 0x 41 0) =
x 42 5. 0x 43 5. 01 =
x 42 5. 0x 43
т.е. в исходной формуле лишней являлась двоичная
переменная x 41 0.
Примечание: произведенная операция называется
"склеиванием"
членов формулы.
Действия, отвечающие методу непосредственных
преобразований,
обычно проводятся в следующем порядке:
1) Выявляются группы двоичных переменных исходной
формулы, к
которым можно применить операцию склеивания или другие
законы ал-
гебры логики, приводящие выражение к более простой форме.
2) Упрощение исходной формулы путем применения к
выявленным
группам соответствующих законов.
3) Преобразование промежуточной логической формулы
с целью
образования таких групп переменных, к которым можно
применить уп-
рощающие законы алгебры логики. Здесь могут проводиться:
- группирование членов;
- действия по раскрытию скобок и выносу за скобки;
- добавление фиктивных членов, т.е. таких,
совокупность ко-
торых тождественно равна нулю;
- логическое умножение одного или нескольких членов
на логи-
ческую сумму переменной и ее отрицания.
4) Упрощение преобразованной промежуточной
логической форму-
лы с получением формы, близкой к минимальной, в виде
некоторой
ДНФ.
5) Выявление и удаление из полученной
предварительной формы
лишних членов, что дает минимальную форму исходной
логической
функции.
В качестве примера рассмотрим минимизацию следующей
функции:
4_ _ _ _
f(a,b,c) = ab V bc V bc V ab =
- 2
-
(используем метод умножения всех членов формулы на сумму
тех пе-
ременных и их отрицаний, которые отсутствуют в данном
члене;)
4_ _ _ _ _
_ _ _
= ab(cVc) V bc(aVa) V bc(aVa) V
ab(cVc) =
(в результате, отбросив повторяющиеся члены, получаем
СДНФ функ-
ции;)
4_ 0 4 __ 0
4_ 0 4 _ _ 0 4 _ 0 4 __ 0
4 _ 0 4 _ _
= abc V abc V abc V abc V abc V abc V abc V abc =
└─┘
╚═╝ └─┘
╚═╝
4_ __ _ _ _ __ _
= abc V abc V abc V abc V abc V abc =
(перегруппировываем члены с целью их упрощения)
4_ 9 4 _
_ _ _ _
= b 9c 0(aVa) V ab(cVc) V
ac(bVb) =
(окончательно получим)
4_ _ _
= bc V ab V ac.
Однако группирование членов после умножения можно
провести и
несколько иначе:
4_ _ _ _ _ _
_ _ _
f(a,b,c) = ab(cVc) V bc(aVa) V ac(bVb) = ab V bc V
ac.
Следовательно, данная функция имеет две минимальные
формы.
Недостатком метода непосредственной минимизации
является
трудность получения всех минимальных форм, если их
несколько.
Кроме того, метод в целом весьма трудоемок, результат
минимизации
в сильной степени зависит от квалификации и интуиции
человека,
проводящего минимизацию. Поэтому данный метод
применяется лишь
для минимизации простых логических формул.
2Метод минимизации с помощью карт
Вейча
Данный метод наиболее применим в инженерной
практике благо-
даря своей простоте и легкости использования. Однако
метод удобен
для упрощения функций, зависящих от небольшого числа
переменных
(до 8). Преимущество этого метода состоит в том, что нет
необхо-
димости приводить функцию к СДНФ.
Рассмотрим изображение на карте Вейча функции
4__ _
_ _ __ _ __ _
f(a,b,c,d) = cd V abd V abc V
abcd V abcd V bcd
- 3
-
При нанесении заданной функции на карту никаких
предвари-
тельных преобразований не проводится. Каждый
дизъюнктивный член
| 
Главная
Документация
Файлы
Информация
