ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.06.2025
Просмотров: 4504
Скачиваний: 2
Глава 3. Переключательная алгебра
функции F путем замены AND на OR и О на 1, как функцию, ду альную по отношению к F,
Важно также установить, что NAND и NOR не являются ассо циативными. И так, справедливо:
{xo^Xl) /\Х2 ^ XQA (Ж1ЛЯ;2) |
(3.18) |
(3.19) |
3.4.Каноническая дизъюнктивная нормальная форма (KDNF).
Любую двоичную функцию можно представить с использованием только логических элементов AND, OR или NOT. Это может быть выполнено на основе систематического подхода, как в примере с функциями, приведенными в табл. 3.7. Можно действовать двумя различными способами. Мы начнем с канонической нормальной дизъ юнктивной формы (KDNF).
Таблица 3.7. Таблица истинности А^ЛЯ примера с KDNF.
Х2 |
XI |
XQ |
Десятичный |
У |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
2 |
1 |
0 |
1 |
1 |
3 |
1 |
1 |
0 |
0 |
4 |
0 |
1 |
0 |
1 |
5 |
1 |
1 |
1 |
0 |
6 |
1 |
1 |
1 |
1 |
7 |
0 |
Для этого рассмотрим сначала входные векторы Хг, р,ля которых функция у ~ f{x) принимает значение 1. Следовательно, д,ля этих входных векторов справедливо f{xi) — 1. В нашем случае это х^^ ^27 ^35 ^5 и а^б- Проведем J\ля каждого подобного входного вектора операцию конъюнкции (логического умножения, И) с элементом Хг, который как раз J\ля этого входного вектора принимает значение 1. Для х^ было бы:
т^ — Х2 f\^x\ f\X{) |
(3.20) |
77i5 называют также «минтермом». Минтермы содержат всегда все входные переменные, поэтому их называют полной конъюнкцией.
3.5.Каноническая конъюнктивная нормальная форма (KKNF)
Вслучае минтерма, входные переменные могут быть инвертиро ванными либо не инвертированными, в зависимости от того, что представляет собой переменная 1 или О, В этом примере входные минтермы имеют вид:
т о |
= -> ^2 Л -• ^1 Л -I жо |
(3.21) |
т 2 |
= -> Ж2 Л rci Л -> хо |
(3.22) |
шз = -> ^2 Л a:i Л жо |
(3.23) |
|
Шб — Х2 /\xi f\-^XQ |
(3.24) |
|
Следовательно, при определенном варианте входных переменных минтерм имеет значение 1.
Вся функция может быть представлена на основе дизъюнкции (логическое сложение) минтермов. Функция получает значение 1, когда, по крайней мере, один из минтермов равен 1. Этот способ представления называется «канонической дизъюнктивной нормаль ной формой» (KDNF). В нашем случае функция может быть пред ставлена следующим образом:
У= (-П Х2 Л -1 Ж1 Л -1 Жо) V (-П Ж2 Л Ж1 Л -п Жо) V
V (-> Х2 Л ^1 Л жо) V {х2 Л -1 a;i Л х^) V (ж2 Л xi Л -п х^) (о.25)
3.5.Каноническая конъюнктивная нормальная форма (KKNF)
вкачестве альтернативы ^\ля представления функции могут быть применены входные векторы ж^, при которых функция принимает
значение О, то есть когда будет справедливо равенство f{xi) = 0. Для функции показанной в табл. 3.7, такими векторами будут xi, Х4
и xj.
Сформируем так называемые макстермы. Это дизъюнкции, ко торые равны О, когда приложен соответствующий входной вектор xf,
М1=Х2У xiW -^XQ |
(3.26) |
||
М4 = ^Х2У |
хгУ |
XQ |
(3.27) |
М7 = ^Х2\/ |
^хгУ |
-^XQ |
(3.28) |
Итак, входные переменные, которые в входом векторе равны 1, выступают в макстерме инвертировано. Входные переменные, ко торые в входном векторе равны О, появляются в макстерме в неинвертированном виде. Таким образом, макстерм равен О только д^ля Ж2 — О, Ж1 = О и Жо = 0.
Глава 3. Переключательная |
алгебра |
Вся функция может быть представлена теперь на основе конъ юнкции макстермов, так как значение функции только тогда рав но О, когда, по крайней мере, один из макстермов равен 0. Форма представления, называемая как «каноническая конъюнктивная нор мальная форма» (KKNF), представлена в следующем примере:
у = (ж2 V Ж1 V -1 жо) л (-> ^2 V Ж1 V хо) л (-«д:2 V -> д;1 V -1 XQ) (3.29)
3.6.Представление функций с помощью KKNF и KDNF.
На практике часто возникает вопрос, как от конкретной проблемы перейти к необходимым для ее решения переключательным функ циям. В связи с этим рассмотрим в качестве примера функцию «чет ность» (parity) /р, представленную в табл. 3.8. Должна быть реализо вана схема с тремя входами, которая на выходе у выдает 1 тогда, ко гда четное число входных сигналов равно 1. В качестве первой опе рации установим таблицу истинности для функции у — fp{x2^ XI^XQ). Затем рассмотрим все комбинации входных сигналов, для которых входной сигнал должен быть равен 1. В данном конкретном слу чае этому соответствуют варианты комбинаций входных сигналов, в которых содержатся две 1 или ни одной. Этим исчерпываются все возможные случаи. В табл. 3.8 даны дополнительно все десятичные эквиваленты входных векторов.
Таблица 3.8. Таблица истинности для |
приведенной |
в качестве примера |
||
функции «четность» у = |
fp{x2^xi,xo). |
|||
Десятичные |
У |
|||
Х2 |
XI |
Хо |
||
эквиваленты |
||||
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
2 |
0 |
0 |
1 |
1 |
3 |
1 |
1 |
0 |
0 |
4 |
0 |
1 |
0 |
1 |
5 |
1 |
1 |
1 |
0 |
6 |
1 |
1 |
1 |
1 |
7 |
0 |
Затем формируем KDNF. Нам потребуются минтермы тг, соот ветствующие входным векторам с десятичными эквивалентами 6,
3.6. Представление функций с помощью KKNF и KDNF.
5, 3, 0. Эти минтермы связываются через логическое ИЛИ. В этом примере KDNF имеет вид:
у — {х2 Л ^1 Л -1 Х{^) V {х2 Л -«a;i Л жо) V
(3.30)
V (-1 а;2 Л Ж1 Л XQ) V (-1ГГ2 Л -• a:i Л -> жо)
Соответствующая логическая схема содержит 4 вентиля И, со единенные с четырехвходовым вентилем ИЛИ.
Хо
^ |
8L |
^1 Vf\ |
& |
>1 |
|
l b |
& |
•^2 |
Vf\ |
& |
Рис. 3.2. Логическая схема реализации KDNF, соответствующей функции «четность».
KKNF образуют макстермы с десятичными эквивалентами 1, 2, 4, 7. Их связывают логические вентили И. Соответствующая KKNF имеет следующий вид:
У = (^2 V XI V -1 хо) Л {х2 V -1 ^1 V хо) Л
(3.31)
Л (-1Ж2 V Ж1 V Хо) Л (-П Ж2 V -1 a;i V -I жо)
л:о |
W\ |
>1 |
||
>1 |
||||
^1 |
Tm |
& |
||
>1 |
||||
Х2 |
Tni |
>1 |
Рис. 3.3. Логическая схема реализации KKNF, соответствующей функции «четность».
KKNF и КВМРявляются равнозначными формами представле ния функции. Но зачастую они имеют различную сложность, так как число минтермов обуславливается числом входных векторов, при которых функция принимает значение 1, в то время как число