- •Глава 3
- •3.1.1 Основные определения
- •3.1.2 Законы алгебры логики
- •Законы нулевого множества
- •Законы универсального множества
- •Законы двойной инверсии
- •9. Законы поглощения
- •11. Законы обобщенного склеивания
- •13. Теорема разложения
- •3.1.3 Элементарные логические функции и принцип двойственности
- •3.1.4 Классификация логических устройств и
- •Контрольные вопросы и задания
- •3.2.2 Представление логических функций (лф)
- •3.2.3 Понятие суперпозиции
- •Метод непосредственных преобразований
- •Метод Карно-Вейча
- •3.3.1 Метод непосредственных преобразований
- •3.3.2 Метод Карно-Вейча
- •Реализация логических функций
- •Особенности построения логических устройств
- •3.4.1 Реализация логических функций
- •3.4.2 Особенности построения логических устройств
3.3.1 Метод непосредственных преобразований
Одним из простейших методов минимизации является метод непосредственных преобразований, который применяется с использованием основных теорем алгебры логики.
Важные теоремы, отражающие основные соотношения алгебры логики (Табл. 3.9) |
||
1 |
x + 0 = x |
x ∙ 1 = x |
2 |
x + 1 = 1 |
x ∙ 0 = 0 |
3 |
x + x = x |
x ∙ x = x |
4 |
x + = 1 |
x ∙ = 0 |
5 |
= x |
- |
6 |
x + y = y + x |
x ∙ y = y ∙ x |
7 |
x + x ∙ y = x |
x (x + y) = x |
8 |
x + (y + z) = (x + y) + z |
x (y ∙ z) = (x ∙ y) z |
9 |
x + y ∙ z = (x + y) (x + z) |
x (y + z) = x ∙ y + x ∙ z |
10 |
= ∙ |
x ∙ y = x + y |
11 |
(x + y) ( + y) = y |
(x ∙ y) +( ∙ y) = y |
Непосредственное упрощение исходной логической функции, заданной в виде СДНФ, выполняется в следующем порядке:
1. Для каждой из возможных пар соседних конституант СДНФ применяется операция полного склеивания. При этом из них исключается по одной переменной. Потом выполняется приведение подобных членов. Этот процесс повторяется до тех пор, пока в полученном выражении не останется конъюнкций, которые отличаются друг от друга значениями одной переменной. Полученная таким способом форма называется сокращенной нормальной формой. Конъюнкции, которые входят в сокращенную нормальную форму, называются простыми импликантами. Каждой логической функции отвечает лишь одна сокращенная форма.
Применяя к сокращенной нормальной форме операцию обобщенного склеивания, исключают из нее лишние конъюнкции (импликанты). Полученная в результате последовательного ряда таких преобразований форма, не допускающая дальнейших склеиваний, называется тупиковой формой логической функции. Тупиковых форм для одной функции может быть несколько.
Полученная тупиковая форма может случайно оказаться минимальной. Минимальной формой является тупиковая форма минимальной длины. В общем случае для поиска минимальной формы необходим перебор тупиковых форм, который позволяет найти одну или несколько минимальных форм логической функции.
Метод Квайна применяется к функциям, заданным в СДНФ (возможно задание и в СКНФ), и проводится, как правило, в два этапа.
На первом этапе выполняется переход от СДНФ к сокращенной ДНФ путем проведения всех возможных склеиваний друг с другом сначала конъюнкций ранга п, затем ранга п — 1, далее п — 2 и т. д. Каждый раз в группе конъюнкций отыскиваются пары конъюнкций вида Ах и А , где А — общая часть этих конъюнкций. Эти конъюнкции склеиваются между собой по переменной х
Например, конъюнкции 1 2х3 4, и 1х2х3 4 имеют общую часть А = 1х3 4 и склеиваются по переменной х2. В результате склеивания получим из конъюнкций ранга п=4, конъюнкции 1х3 4, и 1х3 4 ранга п - 1 = 3.
При этом получается конъюнкция А ранга п-1, а конъюнкции Ах и А помечаются и сравниваются также со всеми другими конъюнкциями ранга п с целью выполнения операции склеивания.
Результатом выполнения последовательности попарного сравнения и склеивания конъюнкций ранга п является группа конъюнкций ранга п —1 и непомеченные конъюнкции ранга г. Непомеченные конъюнкции ранга п не участвовали в склеивании, следовательно, являются простыми импликантами и включаются в сокращенную ДНФ.
Конъюнкции ранга п—1 вновь подвергаются попарному сравнению и склеиванию, как это было описано выше для конъюнкций ранга п; в результате имеем группу конъюнкций ранга п—2 и непомеченные конъюнкции ранга п—1, которые являются простыми импликантами, включаемыми далее в сокращенную ДНФ.
Первый этап заканчивается тогда, когда вновь полученная группа конъюнкций не содержит склеивающихся членов, т. е. содержит только простые импликанты. После этого записывается сокращенная ДНФ, в которую включаются все полученные простые импликанты.
Рассмотрим реализацию первого этапа на примере функции ЛФ f
1 2 3 4 5
f = + + + + (3.5)
где для удобства последующего изложения над конъюнкциями записаны присвоенные им номера.
Анализируя в выражении всевозможные пары конъюнкций 1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5, находим, что операция склеивания выполняется между парами 1-3 по х1, 2-5 по х1, 3-4 по х3, 4-5 по х2.
Таким образом, все конъюнкции исходной СДНФ участвуют в склеивании и помечаются подчеркиванием. 1 2 3 4
Теперь исходная СДНФ (3.5) записывается в виде f = 2 3 + х2х3 + х1 2 + х1x3. (3.6)
Продолжая для выражения (3.6) процедуру склеивания, сравниваем попарно конъюнкции 1-2, 1-3, 1-4, 2-3, 2-4 и 3-4. Эти пары конъюнкций между собой не склеиваются. Поэтому полученная запись ЛФ (3.6) представляет собой сокращенную ДНФ исходной ЛФ (3.5), содержащей только простые импликанты.
Второй этап заключается в переходе от сокращенной ДНФ к тупиковым ДНФ и выборе среди них МДНФ.
Тупиковой называется такая ДНФ, среди простых импликант которой нет ни одной лишней. При этом под лишней понимается такая простая импликанта, удаление которой не влияет на значение истинности этой функции.
Возможны случаи, когда в сокращенной форме нет лишних простых импликант. Тогда сокращенная ДНФ является тупиковой.
Для выявления лишних простых импликант строится импликантная матрица, которая называется также матрицей (таблицей) покрытий. Каждая строка импликантной матрицы соответствует одной простой импликанте, а столбцы — конституантам единицы, которыми они и помечаются. Для рассматриваемого примера импликантная матрица приведена в табл. 3.14.
Таблица 3.14 - Импликационная матрица для выражения 3.5 |
|||||||
№ |
Простые импликанты |
Конституанты единиц |
|||||
|
|
|
|
|
|||
1 |
2 3 |
+ |
|
+ |
|
|
|
2 |
х2 х3 |
|
+ |
|
|
+ |
|
3 |
х1 2 |
|
|
+ |
+ |
|
|
4 |
х1 x3 |
|
|
+ |
+ |
+ |
Нахождение тупиковых ДНФ по импликантой матрице начинается с разметки матрицы. При этом каждая импликанта сравнивается со всеми конституантами единицы. Если импликанта является собственной частью некоторой конституанты, то на пересечении строки и столбца ставится условный знак, например – плюс (+).
Конституенты единицы, помеченные в строке с простой импликантой, поглощаются (покрываются) этой простой импликантой. Это значит, что на соответствующих наборах данная импликанта обеспечивает единичные значения ЛФ.
Например, простая импликанта 2 3 входящая в сокращенную ДНФ (3.6) рассматриваемого примера, является собственной частью конституант единиц и , и поэтому в строке с данной простой импликантой (табл. 3.13) поставлены две пометки X в соответствующих колонках. Аналогично размечены другие строки табл. 3.13.
Выявление лишних простых импликант выполняется следующим образом:
-В импликантной таблице условно вычеркивается строка с проверяемой простой импликантой вместе с соответствующими пометками в строке.
-Если при этом окажется, что в каждом столбце импликантной таблицы остается, хотя бы по одной пометке, проверяемая импликанта является лишней и ее следует удалить.
-Оставшиеся простые импликанты покрывают все единичные значения ЛФ.
-Испытание каждой последующей простой импликанты возможно лишь после удаления уже выявленных лишних простых импликант.
-Изменение последовательности испытаний и удаления лишних членов сокращенной ДНФ может привести к различным тупиковым формам ЛФ, из которых выбирается МДНФ.
Из табл. 3.13 видно, что только простая импликанта 1 обеспечивает единичное значение ЛФ на наборе 000, а импликанта 2 — на наборе 011 (соответствующие этим наборам столбцы обозначены конституантами единицы и ), поэтому эти простые импликанты обязательно войдут во все тупиковые ДНФ.
Простую импликанту 3 можно считать лишней. Однако, если ее сохранить, лишней можно считать простую импликанту 4.
Таким образом, для ЛФ возможны две тупиковые формы:
f1т = 2 3 + х2х3 + х1x3 , (3.7)
в которую не включена лишняя импликанта х1 2
и f2т = 2 3 + х2х3 + х1 2 , (3.8)
в которую не вошла лишняя импликанта x1x3.
Тупиковые формы (3.7) и (3.8) имеют одинаковое суммарное количество переменных, поэтому любую из них можно выбрать в качестве минимальной (МДНФ).
Например, можно считать fmin = f1т = 2 3 + х2х3 + х1 x3 .
Эта ЛФ реализуется схемой с ценой С = 9 (3 х 2 + 3 = 9).
Пример 4. Логическую функцию F в виде СДНФ F = х2 +х1 +х1 х3+х1х2 +x1x2x3 можно минимизировать следующим образом:
Добавим к данной функции слагаемое х1х2 , которое уже есть в данной функции, используя правило 3 (x ∙ x = x).
F = х2 + х1 + х1 х3 +х1х2 + x1x2x3 + х1х2
Применим метод склеивания (правило 11) к одинаково подчеркнутым элементарным конъюнкциям (x ∙ y + ∙ y = y):
Для х1 и х1 х3 по х3 -получим х1
Для х2 и х1х2 х1 -получим х2 ;
Для х1х2 и x1x2x3 по х3 -получим x1x2.
Результат склеивания: F = х2 + х1 + x1x2
Применим тот же метод склеивания для двух последних элементарных конъюнкций:
Для х1 и x1x2 по х2 -получим х1
Окончательный результат: Fmin =FT = х2 + x1
Полученная в результате минимизации логическая функция называется тупиковой. Логическая функция может иметь несколько тупиковых форм.
Пример5. Найти минимальную форму функции, заданной СДНФ
F(a, b,c) =а c + c + + + ab = abc.
Применяя операцию полного склеивания к сочетаниям каждой конституанты со всеми соседними и приводя подобные члены, получаем сокращенную нормальную форму:
F(a,b,c) = + c + ac + ab + b + .
П рименение операции обобщенного склеивания к импликантам можно осуществить в нескольких вариантах. Каждому из них отвечает одна из следующих тупиковых форм:
Очевидно, что анализируемой функции отвечают две минимальных нормальных формы F2(a,b,c) и F3{a,b,c).
Для исходной функции, заданной в виде СКНФ, минимизация методом непосредственного упрощения выполняется таким образом.
Сначала к членам СКНФ применяют операцию полного склеивания.
Пользуясь законом дистрибутивности, раскрывают скобки в полученном выражении.
Приводят подобные члены и применяют операцию поглощения.
Полученную таким способом ДНФ минимизируют в указанном выше порядке.