ВУЗ:
Составители:
21
Согласно приведенному выше алгоритму, используя минтермы из табл. 2.6 и
основные аксиомы (тождества) алгебры-логики (табл. 2.3), получим:
()
()()
()()()()
()()
012012012012012012
012012012012
012012776655
4433221100012
11
1010
00
,,
xxxxxxxxxxxxxxxxxx
xxxxxxxxxxxx
xxxxxxmymymy
mymymymymyxxxy
+++=⋅+⋅+
+⋅+⋅+⋅+⋅+
+⋅+⋅=+++
+
+
+++
=
Дизъюнктивную нормальную форму, полученную суммированием
конституент единицы (минтермов), называют совершенной дизъюнктивной
нормальной формой
(СДНФ). В общем случае СДНФ любой логической
функции можно представить в следующей форме:
∑
−
=
=
1
0
q
i
ii
mfF
(2.12)
где f
i
– значение функции (0 или 1), m
i
– минтерм, соответствующие i-ому
набору переменных;
q = 2
n
– количество различных значений ФАЛ при n
заданных переменных.
2. Конъюнктивная нормальная форма (КНФ). КНФ называется логическое
произведение элементарных логических сумм, в каждую из которых
аргумент или его инверсия входят один раз.
Получена КНФ может быть из таблицы истинности с использованием
следующего алгоритма:
а) для каждого набора переменных, на котором ФАЛ равна нулю, записывают
элементарные логические суммы входных переменных, причем
переменные, значения которых равны единице, записывают с
инверсией. Полученные суммы называют конституентой нуля, или
макстермами.
б) логически перемножают все конституенты нуля (макстермы).
Пример 2.4. Записать КНФ для ФАЛ, заданной в примере 2.2.
Решение. Составим таблицу конституент нуля (макстермов) для ФАЛ, заданной
в примере 2.2.
Таблица 2.7
Макстермы ФАЛ y(x
2
,x
1
,x
0
)
x
2
x
1
x
0
Макстермы
(M)
Значение
функции
0 0 0
0120
xxxM
+
+
=
y
0
=0
0 0 1
0121
xxxM
+
+
=
y
1
=0
0 1 0
0122
xxxM
+
+
=
y
2
=0
0 1 1
0123
xxxM
+
+
=
y
3
=1
1 0 0
0124
xxxM
+
+
=
y
4
=0
1 0 1
0125
xxxM
+
+
=
y
5
=1
1 1 0
0126
xxxM
+
+
=
y
6
=1
1 1 1
0127
xxxM
+
+
=
y
7
=1
22
Согласно приведенному выше алгоритму, используя макстермы из табл. 2.7 и
основные аксиомы (тождества) алгебры-логики (табл. 2.3), получим:
(
)
(
)
(
)
(
)
(
)
(
)
()()()( )
()
()()
012012
012012776655
4433221100012
,,
xxxxxx
xxxxxxMyMyMy
MyMyMyMyMyxxxy
++⋅++×
×++⋅++=+⋅+⋅+×
×
+
⋅
+
⋅
+
⋅
+
⋅
+
=
Конъюнктивную нормальную форму, полученную суммированием
конституент нуля (макстермов), также называют совершенной конъюнктивной
нормальной формой
(СКНФ). В общем случае СКНФ любой логической
функции можно представить в следующей форме:
()
∏
−
=
+=
1
0
q
i
ii
MfF
(2.13)
где
f
i
– значение функции (0 или 1), M
i
– макстерм, соответствующие i-ому
набору переменных;
Рассмотренные методики позволяют получить математическую форму записи
для самой функции. Иногда удобнее применять не саму ФАЛ, а ее инверсию. В этом
случае при использовании вышеописанных методик для записи СДНФ необходимо
выбирать нулевые, а для записи СКНФ – единичные значения функции.
Пример 2.5. Для ФАЛ из примера 2.2 записать СДНФ и
СКНФ инверсной функцией.
Решение. Воспользовавшись таблицей 2.5, запишем
СДНФ:
(
)
012012012012012
,, xxxxxxxxxxxxxxxy
+
+
+
=
СКНФ:
(
)
(
)
(
)
(
) ()
012012012012012
,, xxxxxxxxxxxxxxxy ++
⋅
+
+
⋅
+
+
⋅
+
+
=
Описание ФАЛ в виде последовательности десятичных чисел. Иногда для
сокращения записи ФАЛ представляют в виде последовательности десятичных чисел.
При этом последовательно записывают десятичные эквиваленты двоичных кодов
соответствующих конституент еденицы и нуля (минтермов и макстермов).
Пример 2.6. Записать в виде последовательности десятичных чисел ФАЛ из
примеров 2.3 и 2.4.
Решение. В СДНФ из примера 2.3 первая конституента единицы (минтерм -
012
xxx
)
соответствует двоичному коду 011 (табл. 2.6). Десятичный эквивалент
этого кода равен 3. Аналогично записываются все остальные
конституенты:
(
)
(
)
∑
= 7,6,5,3
012
xxxy
.
В СКНФ из примера 2.4 первая конституента нуля (макстерм
012
xxx ++
)
соответствует двоичному коду 000 (табл. 2.7). Десятичный эквивалент
этого кода равен 0. Аналогично записывают все остальные конституенты:
(
)
∏
= )4,2,1,0(
012
xxxy
.
Кубические комплексы. В последнее время широкое распространение получило так
называемое кубическое представление ФАЛ. Такое представление использует
ограниченное число символов и поэтому применяется при автоматизации процессов
логического проектирования цифровых интегральных схем (ИС).
Согласно приведенному выше алгоритму, используя минтермы из табл. 2.6 и Согласно приведенному выше алгоритму, используя макстермы из табл. 2.7 и
основные аксиомы (тождества) алгебры-логики (табл. 2.3), получим: основные аксиомы (тождества) алгебры-логики (табл. 2.3), получим:
y ( x2 , x1 , x0 ) = y0 m0 + y1m1 + y2 m2 + y3 m3 + y4 m4 + y (x2 , x1 , x0 ) = ( y0 + M 0 ) ⋅ ( y1 + M 1 ) ⋅ ( y2 + M 2 ) ⋅ ( y3 + M 3 ) ⋅ ( y4 + M 4 ) ×
+ y5 m5 + y6 m6 + y7 m7 = 0 ⋅ (x2 x1 x0 ) + 0 ⋅ ( x2 x1 x0 ) + × ( y5 + M 5 ) ⋅ ( y6 + M 6 ) ⋅ ( y7 + M 7 ) = (x2 + x1 + x0 ) ⋅ ( x2 + x1 + x0 ) ×
+ 0 ⋅ ( x2 x1 x0 ) + 1 ⋅ ( x2 x1 x0 ) + 0 ⋅ (x2 x1 x0 ) + 1 ⋅ ( x2 x1 x0 ) + × ( x2 + x1 + x0 ) ⋅ (x2 + x1 + x0 )
+ 1 ⋅ ( x2 x1 x0 ) + 1 ⋅ ( x2 x1 x0 ) = x2 x1 x0 + x2 x1 x0 + x2 x1 x0 + x2 x1 x0 Конъюнктивную нормальную форму, полученную суммированием
Дизъюнктивную нормальную форму, полученную суммированием конституент нуля (макстермов), также называют совершенной конъюнктивной
конституент единицы (минтермов), называют совершенной дизъюнктивной нормальной формой (СКНФ). В общем случае СКНФ любой логической
нормальной формой (СДНФ). В общем случае СДНФ любой логической функции можно представить в следующей форме:
q −1
функции можно представить в следующей форме: F = ∏ ( fi + M i ) (2.13)
q −1
F = ∑ f i mi
i =0
(2.12)
где fi – значение функции (0 или 1), Mi – макстерм, соответствующие i-ому
i =0
набору переменных;
где fi – значение функции (0 или 1), mi – минтерм, соответствующие i-ому
набору переменных; q = 2n – количество различных значений ФАЛ при n Рассмотренные методики позволяют получить математическую форму записи
заданных переменных. для самой функции. Иногда удобнее применять не саму ФАЛ, а ее инверсию. В этом
случае при использовании вышеописанных методик для записи СДНФ необходимо
2. Конъюнктивная нормальная форма (КНФ). КНФ называется логическое выбирать нулевые, а для записи СКНФ – единичные значения функции.
произведение элементарных логических сумм, в каждую из которых
аргумент или его инверсия входят один раз. Пример 2.5. Для ФАЛ из примера 2.2 записать СДНФ и СКНФ инверсной функцией.
Получена КНФ может быть из таблицы истинности с использованием Решение. Воспользовавшись таблицей 2.5, запишем
следующего алгоритма: СДНФ: y (x2 , x1 , x0 ) = x2 x1 x0 + x2 x1 x0 + x2 x1 x0 + x2 x1 x0
y (x2 , x1 , x0 ) = (x2 + x1 + x0 ) ⋅ ( x2 + x1 + x0 ) ⋅ (x2 + x1 + x0 ) ⋅ ( x2 + x1 + x0 )
а) для каждого набора переменных, на котором ФАЛ равна нулю, записывают
СКНФ:
элементарные логические суммы входных переменных, причем
переменные, значения которых равны единице, записывают с Описание ФАЛ в виде последовательности десятичных чисел. Иногда для
инверсией. Полученные суммы называют конституентой нуля, или сокращения записи ФАЛ представляют в виде последовательности десятичных чисел.
макстермами. При этом последовательно записывают десятичные эквиваленты двоичных кодов
б) логически перемножают все конституенты нуля (макстермы). соответствующих конституент еденицы и нуля (минтермов и макстермов).
Пример 2.4. Записать КНФ для ФАЛ, заданной в примере 2.2.
Решение. Составим таблицу конституент нуля (макстермов) для ФАЛ, заданной Пример 2.6. Записать в виде последовательности десятичных чисел ФАЛ из
в примере 2.2. примеров 2.3 и 2.4.
Таблица 2.7 Решение. В СДНФ из примера 2.3 первая конституента единицы (минтерм - x2 x1 x0 )
Макстермы ФАЛ y(x2,x1,x0) соответствует двоичному коду 011 (табл. 2.6). Десятичный эквивалент
Макстермы Значение этого кода равен 3. Аналогично записываются все остальные
x2 x1 x0
(M) функции конституенты:
0 0 0 M 0 = x2 + x1 + x0 y0=0 y (x2 x1 x0 ) = ∑ (3,5,6,7 ) .
0 0 1 M 1 = x2 + x1 + x0 y1=0 В СКНФ из примера 2.4 первая конституента нуля (макстерм x2 + x1 + x0 )
0 1 0 M 2 = x2 + x1 + x0 y2=0 соответствует двоичному коду 000 (табл. 2.7). Десятичный эквивалент
0 1 1 M 3 = x2 + x1 + x0 y3=1 этого кода равен 0. Аналогично записывают все остальные конституенты:
1 0 0 M 4 = x2 + x1 + x0 y4=0 y ( x2 x1 x0 ) = ∏ (0,1,2,4) .
1 0 1 M 5 = x2 + x1 + x0 y5=1 Кубические комплексы. В последнее время широкое распространение получило так
1 1 0 M 6 = x2 + x1 + x0 y6=1 называемое кубическое представление ФАЛ. Такое представление использует
M 7 = x2 + x1 + x0 ограниченное число символов и поэтому применяется при автоматизации процессов
1 1 1 y7=1
логического проектирования цифровых интегральных схем (ИС).
21 22
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
