- •Глава 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.2.2 Представление логических функций (лф)
СДНФ переключательной функции записывается по таблице истинности.
Для того чтобы по таблице истинности построить СДНФ, надо каждому набору переменных, на котором ЛФ принимает единичное значение, поставить в соответствие элементарную конъюнкцию ранга п и все эти конъюнкции соединить дизъюнктивно; в каждой конъюнкции СДНФ с отрицанием берутся те переменные, которые на соответствующем этой конъюнкции наборе имеют нулевое значение.
Используя это правило, запишем в СДНФ функции f1 и f2 трех переменных, заданных таблице 3.13.
Таблица 3.13
№ |
x1 |
x2 |
x3 |
f1 |
f2 |
1 |
0 |
0 |
0 |
0 |
1 |
2 |
0 |
0 |
1 |
1 |
0 |
3 |
0 |
1 |
0 |
0 |
1 |
4 |
0 |
1 |
1 |
1 |
0 |
5 |
1 |
0 |
0 |
0 |
0 |
6 |
1 |
0 |
1 |
1 |
0 |
7 |
1 |
1 |
0 |
0 |
1 |
8 |
1 |
1 |
1 |
0 |
1 |
Для получения f1 используем 2, 4 и 6 строки
f1 = + х2 (3.1)
Для получения f2 используем 1, 7 и 8 строки.
f2 = + х2 + х1 х2 х3 (3.2)
Элементарные конъюнкции СДНФ называют конституантами (составляющими) единицы, так как они соответствуют наборам, при которых ЛФ принимает значения 1.
После составления выражения для f1 можно построить из логических элементов И, ИЛИ, НЕ функциональную схему, которая будет вычислять значение ЛФ f1.
Чтобы построить функциональную схему для ЛФ, записанной в СДНФ, надо взять k ЛЭ И на n входов каждая, где k — число конъюнкций СДНФ, и объединить выходы схем И с помощью элемента ИЛИ на k входов.
Для ЛФ f1 функциональная (или логическая) схема приведена на рис. 3.6 (на схеме не показаны лишь элементы НЕ, с помощью которых получаются инверсные значения переменных х1 и x2).
Рисунок 3.6 Рисунок 3.7
Для каждой функциональной схемы можно сделать оценку ее сложности, которая выражается ценой схемы С (по Квайну).
Цена С определяется суммарным числом входов логических элементов.
Чем меньше величина С, тем проще функциональная схема. Если ЛФ задана в СДНФ, ее цену можно выразить формулой:
С = kn + k.
Для ЛФ f1 - k = 3 -число конъюнкций, а n = 3 –число входов (х1 х2 х3).
Тогда С = 3 х 3 + 3 = 12
Используя правило склеивания (ПРАВИЛО 11), можно упростить ЛФ, заданную в СДНФ.
Для этого в СДНФ сначала склеиваются между собой конъюнкции ранга п, затем полученные конъюнкции ранга (n — 1), (n — 2), и так до тех пор, пока в выражении для ПФ не останется ни одной пары склеиваемых между собой конъюнкций. Операция склеивания позволяет понизить ранг конъюнкций и сократить их число. В результате уменьшается цена функциональной схемы.
Например, в выражении f1 = + х2 выполним склеивание:
-конъюнкций и х2 по переменной х2 , получим: ;
-и конъюнкций и по переменной х1 , получим : .
В результате функция f1 преобразуется к виду f1 = + (3.3)
Функциональная схема, реализующая ЛФ f1 по выражению (3.3), изображена на рис. 3.7.
Цена этой схемы С = 6, т. е. по сравнению с эквивалентной схемой на рис. 3.8 цена уменьшилась в 2 раза.
В результате попарного склеивания конъюнкций ранга п, а далее (п — 1), (п — 2) и т. д., в выражении для ЛФ остаются конъюнкции, которые между собой не склеиваются.
Конъюнкция, которая не склеивается ни с какой другой конъюнкцией ДНФ, называется простой импликантой.
В выражении (3.3) конъюнкции не склеиваются между собой, т. е. они являются простыми импликантами.
ДНФ, представляющая собой дизъюнкцию простых импликант, называется сокращенной ДНФ.