Файл: Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.07.2024
Просмотров: 83
Скачиваний: 1
Эта функция обращается в нуль на наборах значений аргумен
тов, |
имеющих номера j — 3, |
6, |
7, 11, 15, поэтому F 4 = |
V / при |
||
/ = |
3, |
6, 7, 11, 15, откуда |
|
|
|
|
|
|
Fx = fx = |
V * ? = M /- |
|
(611) |
|
Подставляя правую часть |
тождества (6.9) |
в формулу |
(6.11), |
|||
получаем СКНФ функции |
|
|
|
|
||
|
|
Л = Л 4 в-1 )-/= Л<4 |
при т = 28, 25, |
24, 20, 16, |
|
|
где |
m |
- (2n— l) — j. Итак, |
|
|
|
|
|
|
F 4== (Х4 V -^3 V *^2 V "^1 V *^о) Л (*^4 V *^3 V Х2У *^1V ^о)Л |
|
|||
|
|
A ^ V ^ a V ^ V ^ i V ^ A ^ V ^ s V ^ V ^ i V ^ A |
|
|||
• |
|
A ta V ^ V ^ V -^ V ^ o )- |
|
|
||
Склеивая I h IV, II и III, III и V члены СКНФ, получим конъюнк тивную нормальную форму
К = ( х 4 V * 2 V * 1 V Хо ) А (* 4 У Х 3 V * 2 V * l ) Л (* 4 У * 2 V Х 1 V * о ) •
Склеив I и III члены этой формулы, получим
Л = (хл УххV *о) Л (*4 V - ^ s V ^ V хд ■
Раскрыв скобки согласно распределительному закону, получим
F4 = x4 у х4х3 У х4х2 у х4хх у х4х4 У х4х3 У х 4х2 у
У х4 У х0х4 у х0х3 У XqX2 у XqX4.
Проведя операцию поглощения, найдем сокращенную дизъюнк тивную нормальную форму функции
^ l = *4V*lV*0*sV*0*2-
Нахождение минимальных конъюнктивных нормальных форм
Минимальные КНФ находятся с помощью правила де Моргана и методов минимизации СДНФ. Этот прием характеризуется тремя
шагами: |
й шаг. Записываем отрицание заданной функции как дизъюнк |
1- |
|
цию элементарных конъюнкций максимальной длины, имеющих |
|
номера тех наборов аргументов, на которых функция обращается |
|
в нуль. |
й шаг. Полученное выражение минимизируется с помощью |
2- |
|
любого из методов минимизации СДНФ, в результате чего прихо
150
дим к минимальным дизъюнктивным формам отрицания заданной функции.
3-й шаг. От минимальных ДНФ отрицания заданной функции с помощью правила де Моргана переходим к КНФ, которые и яв ляются минимальными КНФ заданной функции.
Пример 8. Найти минимальную КНФ функции
F t = \ / ^ при / = 3, 6, 7, 11, 15. |
(6.12) |
В соответствии с первым шагом имеем
К1=--\Д / |
при / = |
3, 6, 7, 11, |
15. |
(6.13) |
Х,Х0 |
x , x D |
Х,Хд |
X, Х„ |
|
0 |
0 |
1 |
0 |
|
* з * г |
|
|
|
|
0 |
0 |
1 |
0 |
|
х з хг |
|
|
|
|
1 |
1 |
1 |
0 |
|
* 3 * 2 |
|
|
|
|
1 |
1 |
0 |
0 |
|
Х з*2 |
|
|
|
|
Рис. 40
Второй шаг —-минимизация формулы (6.13). Проведем миними зацию методом «усовершенствованного алгоритма Куайна». После первого склеивания членов выражения (6.13) и устранения элемен тарных поглощений получаем члены
ksk2, kgkn, kek7, k7ki5, kukig,
после склеивания которых и устранения элементарных поглощений находим два члена:
и k6k7.
Дальнейшее склеивание и поглощение невозможны, поэтому вы ражение
(6.14)
является сокращенной ДНФ функции и имеет вид
F = х4хгх0V х4х3х2х4. |
(6.15) |
В результате выполнения 3-го шага получаем
F1 = F1 = (x4\/x 1\/x о) {x4\J x3\J х2\/ хi). |
(6.16) |
151
Пример 9. Найти минимальную КНФ функции при пом сщи карты Карно (рис. 40).
В данном случае необходимо накрыть совокупность всех нуле вых квадратов карты минимальным количеством правильных пря моугольников (рис. 40).
Из карты видно, что других равноценных накрытий нет. Следо вательно, отрицание функции имеет единственную минимальную
ДНФ
F = Х3ХхV * 1 * 0 V * 3 * 2 * 1 .
а функция — единственную минимальную КНФ
F = (* 8 V X l ) (х 1 V * о ) (* 8 V * 2 V * l ) •
Минимизирующие карты
Минимизирующие карты составляются по правилу, которое можно сформулировать, пользуясь функцией трех переменных
(табл. 6-7).
Т а б л и ц а 6-7
|
ч |
но |
|
Д в о и |
ный мер |
0 0 0
001
0 1 0
011
100
101
п о
111
X |
У |
Z |
х + у |
X + Z |
||
X |
У |
г |
х + у |
X + |
Z |
|
X |
У |
г |
х + |
У |
X + |
Z |
X |
У |
Z |
Х + |
У |
X + |
Z |
X |
У |
Z |
х + |
У |
X + |
Z |
X |
У |
Z |
Х + |
У |
х + |
г |
X |
У |
Z |
х + |
у |
X —}- Z |
|
X |
У |
Z |
х + |
у |
X + |
Z |
X |
у |
Z |
х + |
У |
Х + |
Z |
У + |
2 |
|
X + |
У + |
2 |
и |
У + г - |
х + У + г |
/ о |
||||
У + |
г |
х |
+ |
У + |
z |
h |
У + |
г |
х |
+ |
У + |
г |
/ 2 |
У + |
г |
х |
+ |
У + |
2 |
/з |
У + |
г |
x |
+ |
y + |
z |
/4 |
У + |
г |
х |
+ |
У + |
г |
/б |
У + |
г |
x |
+ |
y + |
z |
/в |
У + |
г |
х + |
У + |
г |
fi |
|
Составляем Таблицу конституентов нуля, причем каждый пе ременной ставим в соответствие разряд двоичного номера строки: нулевому значению цифры разряда соответствует переменная без отрицания, а единице — переменная с отрицанием.
Определяем значения функции Д при kx = 0. Строки таблицы
(карты), содержащие Д = |
1, вычеркиваем, поскольку они соответст |
||
вуют конституентам нуля, |
не входящим в минимальную форму. Ком |
||
бинации переменных, соответствующие Д = |
1, нужно |
вычеркнуть |
|
не только "в г-й строке, но и в любой другой, |
так как |
они будут в |
|
разложении лишними. |
|
|
|
Незачеркнутые комбинации переменных будут встречаться толь |
|||
ко в тех_строках, где Д = |
0. В карте может оказаться несколько |
||
152
строк, в каждой из которых будет только одна незачеркнутая ком бинация (конституент), содержащая минимальное число перемен
ных. Такие комбинации условимся |
называть с у щ е с т в е н |
н ы м и и будем обводить их в карте |
рамками. Существенные ком |
бинации обязательно должны входить в окончательное выражение. В некоторых строках, где /) — 0, могут оказаться комбинации переменных, которые не зачеркнуты и не обведены рамкой. Такие комбинации назовем с в о б о д н ы м и . Одна из свободных ком бинаций, содержащая наименьшее число переменных, должна, войти в окончательное выражение функции. Все сводные комбина ции обводим общей рамкой, внутри которой могут оказаться и за
черкнутые, последние принимать во внимание не будем. |
p l>t |
|||||||||
Составляем |
минимальную форму |
функции f (х, |
у, z) |
|||||||
р 2, ■■• рп, |
где |
рп — обведенные |
рамкой различные |
комбинации |
||||||
переменных (конституенты). |
|
|
|
|
|
|||||
Пример 10. |
Пусть задана функция |
|
|
|
|
|||||
|
|
|
f (х, |
у, |
z) = xyz-\- xyz-f-xyz, |
|
|
|||
которая принимает значения f0 — /3 — f5 = |
1, а / х — f 2 = U — |
|||||||||
= /в -= U = |
0. Найдем минимальную КНФ функции при помощи |
|||||||||
минимизирующей карты (см. табл. 6-8). |
|
|
|
|||||||
|
|
|
|
|
|
|
|
Т а б л и ц а |
6-8 |
|
Двоичный. |
|
|
|
|
х + у |
|
y + z |
х + у + z |
|
|
номер |
|
|
|
|
|
|
|
|||
xyz |
|
|
|
|
|
|
|
|
|
|
Д М - |
|
|
- у — |
|
-х±у— x+z |
|
X +y+-Z- |
-f<r+- |
|
|
00/ |
|
|
-Г |
лг |
Л^'У' |
et+Z' |
|
\ x + y + ZI |
f , 0 |
|
0/0 |
|
|
Дг |
|
Л+f- |
ЛНгХГ [y+z |
z + y + z |
fz 0 |
|
|
-Ш4— |
|
|
|
|
|
X+Z— -y+-z— |
|
|
|
|
100 |
|
|
¥ |
-г |
|
|
|
x + y + z |
f, 0 |
|
дав |
|
|
|
|
- х + у - |
-x+z -у+1 |
X+y+Z— |
&■ |
|
|
но |
J r |
-г |
■ъ- |
х + у |
X + Z |
y + z |
z+y+z |
r,0 |
|
|
/н |
ДОг |
-г |
Дгг |
х + у |
JZ+ZT Jf+TT |
x + y + z |
f7 0 |
|
||
Согласно карте |
и сформулированному правилу пользования ею |
f(x, у |
, z) = (x + y)(x + z) (y + z) ( x + y + z ) . |
11 З а к а з N° 2437 |
153 |