Файл: Сарингулян, Э. В. Арифметические и логические основы цифровых машин учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.10.2024
Просмотров: 61
Скачиваний: 0
Распространяя закон инверсии на логические функции с п переменными, связанными операцией конъюнкции, молено записать
ПП
П•*/= 2
i~i с-=1
Закон инверсии не имеет аналога в обычной алгебре.
Рассмотрим теперь ряд простых, но весьма важных соот ношений при эквивалентных преобразованиях сложных логи ческих функций к более простому виду:
а \ / а = |
а ; |
(3.14) |
а а = |
а ; |
(3.15) |
a v 1= |
1; |
(3.16) |
а * 1= а ; |
(3.17) |
|
а . О = |
а: |
(3.18) |
д--0 — 0; |
(3.19) |
|
а V а = |
1; |
(3.20) |
А •А = |
0. |
(3.21) |
II как следствие из приведенных соотношений получаем:
А V А V А V а V ... V А = а;
А Л А Д А Л а Л ... Л А = а ;
А V У V Z у7А 2= 1:
x - y - z - y = 0.
Часто для упрощения сложных логических функций исполь зуются следующие зависимости:
а V ху — х — операция поглощения; (3.22)
х у \/х у = |
х —операция склеивания; |
(3.23) |
|
а V Ау \/ А2 = |
а ; |
(3.24) |
|
а (а V у) = а ; |
|
(3.25) |
|
а (а V у) (а V |
2 ) = а ; |
(3.26) |
|
A v Ay = |
а V .у; |
(3.27) |
|
А V AV = |
А V у. |
(3.28) |
|
58
§ 3.2. Формы логических функций и их минимизация
Любая логическая функция может быть выражена различ ными формами в зависимости от способов применения элемен тарных логических операций к переменным и их группам.
При задании переключательных функций таблицами истин ности переход к аналитической записи с помощью операций первой функционально полной системы наиболее удобно для практического применения выполнять в нормальной дизъюнк тивной или нормальной конъюнктивной формах. Для образо вания этих форм введем некоторые понятия.
Логическая функция и переменных, принимающая значение единицы только на одном из наборов, называется конституентой единицы, или элементарной конъюнкцией. На остальных
(2" = 1) |
наборах функция равна 0. |
При |
количестве наборов 2П число конституент единицы |
равно также 2п. Котиституенту единицы Q выражают через ло гическое произведение переменных и их отрицаний. Для логи
ческих |
функций двух аргументов число элементарных конъ |
||
юнкций |
равно четырем |
(табл. 3.2). Ими являются |
функции |
f1(х, у ), / 2(х, y ) , f а{х, у ) , |
h (х, у ) . Конъюнкция /] (х, у) |
есть ча |
|
стный случай конституент единицы. Учитывая значения пере менных на соответствующих наборах, конституенты единицы можно представить через логические произведения аргументов следующим образом:
/, (х, у) = х - у; |
/ 2{х, у) = х -у; |
/а(х , У) = х-у, |
/ 8(х, у) = х •у. |
Отрицания берутся над теми переменными, которые на на борах, на которых функция равна значению 1, имеют код 0.
Число переменных, составляющих элементарную конъюнк цию, называется ее рангом. Для приведенных конституент ранг
т= 2:
fi (х, у) = Q P ; / 2(х, у) = Q<2>; / 4(х, у) = QW .
При выполнении преобразований логических функций ис пользуются понятия соседних и изолированных [конъюнк ций [1].
Элементарные конъюнкции Q(m) и Qt%m) т-го ранта являют ся соседними, если возможно последующее их преобразование:
Q‘m>= |
x t |
= х, |
и |
|
_ |
0%п) = |
xtQ2m_1) = х,- Q("'~ ]> |
|
или |
|
|
59
и
Qim)= z x , Q ? ‘ - ]) = |
X i Q l" ' - [). |
|
Например, элементарные конъюнкции 5-го ранга |
||
QiS) = ayy2x ,ayv5 и |
QaS) — -V, a 2a 3a 4a 6 |
|
называются соседними, поскольку |
|
|
Q\S) = |
|
Q(4’ |
и |
|
|
0$5) = -Д (''V 'Y V o) |
= -И Q(4). |
|
Элементарная конъюнкция |
ранга т называется изолиро |
|
ванной по отношению к множеству конъюнкций того же ранга,
если она не |
является |
соседней ни |
с_одной конъюнкцией |
-из |
|
этого множества. Например, |
Q l3)— a^.y-iAj изолирована по |
от |
|||
ношению к |
множеству |
|
|
|
|
/•ч(З) |
~ Л‘ ,Л‘2А'3, |
/~ПЗ) |
Aj-VjA'a |
/л(3) |
|
Q i |
Q 3 ” |
И Q4 ----- Л^Л’оЛ';}- |
|
||
Аналогично понятию конституенты единицы введем поня тие конституенты нуля.
Логическая функция п переменных, принимающая значе ние, равное нулю только на одном из наборов, называется кон ституантой нуля, или элементарной дизъюнкцией. На осталь ных (2Л— 1) наборах функция равна 1. Для логических функ ций двух аргументов, определенных на четырех наборах, мож
но выделить |
следующие |
конституенты |
нуля |
(табл. 3.2): |
/?(-*> |
У), / „ ( а , |
у), / 13(а , у), |
х, |
у). |
Дизъюнкция / 7(х, у) есть частный случай конституент нуля. Принимая во внимание значения переменных на наборах, когда функция равна нулю, конституенты нуля D выражают через дизъюнкцию аргументов, взятых с отрицанием или без отрицания. Отрицания расставляются так, чтобы обратить эту дизъюнкцию в нуль на заданном наборе. Для логических
функций /у, /п, f 13, / 14 можно записать
/т (х, У) = х V у; |
/ , , (а , у) = а V у; |
/ы ( х , у) = A v у; |
/ и ( А , у) = А V у. |
Пользуясь понятиями конституент единицы и нуля, рас смотрим задание логической функции в нормальной дизъюнк тивной и нормальной конъюнктивной формах.
Логическая функция задана нормальной дизъюнктивной формой, если она выражена через дизъюнкцию конституент единицы или через логическую сумму элементарных конъ юнкций.
GO
Применяя основные законы алгебры логики, операция от рицания может быть применена лишь к аргументам функции, а последующие необходимые преобразования сведут заданную логическую функцию к виду логической суммы конституепт единицы. Таким образом, любая логическая функция сможет быть выражена через отрицание, конъюнкцию и дизъюнкцию, т. е. выражена в нормальной дизъюнктивной форме-
Пример. Для функции
f ( x u лу, лу, Л'.,) ==л-1л-3Л'Л,(-'-']а-2\/^1л'з) Х/лъл'дД^ (х, v
найти ее нормальную конъюнктивную форму.
1) Применяя закон инверсии к логическому сложению
(3.12) и к логическому умножению (3.13), получим:
X jX2\ / Л,А3 — Лj Л2 * А ,А”3
Л j Л з - A j Л3 — (Xj \ / Л 2) ("И \ / лу).
Раскроем скобки:
(лу V лу) (лу\/ лу) =■ лулу Х/лул3V лулу,
так как согласно (3.21) лулу= 0,
2) Преобразуем член л2л3л4( л* у7лух2лу):
Аулулу (Ay V лулулу) — A,Ay,AyAy V ЛулулуАу = Х3ЛуЛ4(А', V ЛУ) =
-— :
так как лу \/ х, = 1 (3.20).
3) Подставляя преобразованные выралсения в исходную форму, получим нормальную дизъюнктивную форму:
/(л у , лу, лу, лу) = лух3лу V л,лу V лулу V а 2ау V АУА£А-4.
4) Применяя операцию поглощения (3.22) к первому и третьему, к четвертому и пятому конъюнктивным членам, по лучим упрощенное выражение для заданной логической функции, представленное конъюнкциями переменных с отрица ниями и без отрицаний в форме логической суммы:
/(.ту, лу, лу, А'.,) =лулух4V лулу V лух3V лулу V лулух, =
:= лулу (лу V 1) V луло V лух,, (1 \/ лу) = лулу, V лулу V лулу.
Если логическая функция задана в виде логического про изведения элементарных дизъюнкций, то такая форма опреде ляется как конъюнктивная нормальная форма. Конъюнктив ная нормальная форма аналогично дизъюнктивной нормаль ной форме устанавливается для любой логической функции.
б!