Файл: Сарингулян, Э. В. Арифметические и логические основы цифровых машин учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.10.2024
Просмотров: 60
Скачиваний: 0
П р и м е р . Д л я ф у н к ц и и
f (Х|, Х 2, -'•3> -П) == (-Н V Х 3) V (-'■2 V -'-з) V (-VT( \J Л'Л) \J (х3V Л4)
найти ее .нормальную канътоиктвнуло 'форму.
Применим закон инверсии для логической суммы (3.12):
/(л -,, х а, х.„ х 4) = х ,х , V х ,х 3V л',х4 V х 3х 4.
Затем сгруппируем первый и .второй, третий и четвертый члены:
лух., V а-,х 3 - л'о (лу — х 3); |
х ,х , \/ л 3х 4= х 4(лу V |
х я) |
и вынесем общий множитель |
|
|
/ (х, ду, х 3, х.,) — х , (х, V х 3) V |
х., (х, V х 3) = (х, V х 3) (х, \ / х„). |
|
Последнее выражение для заданной логической |
функции |
|
представляет собой нормальную конъюнктивную форму. После преобразований, основанных па законах и соответст
вующих соотношениях алгебры логики, логическая функция может быть представлена различными нормальными дизъюнк тивными или конъюнктивными формами.
Задача анализа и синтеза логических схем подобна мате матической задаче описания заданной логической функции че рез элементарные логические функции выбранной функцио нально полной системы. Поскольку любая переключательная функция выражается через элементарные функции неодно значно, возникает вопрос о выборе некоторых нормальных форм для представления заданных логических функций, кото рые могли быть использованы в качестве исходных. Исходные формы должны быть удобны для изображения любой пере ключательной функции и для дальнейшего возможного упро щения. В качестве таких форм в теории анализа и синтеза ди скретных автоматов на основе первого базиса используются совершенная дизъюнктивная нормальная форма СДНФ и со вершенная конъюнктивная нормальная форма СКНФ.
Логическая функция часто задается таблицей истинности, которая отражает условия работы некоторой цифровой схемы. Для образования совершенной дизъюнктивной нормальной формы по таблице истинности необходимо записать элемен тарные конъюнкции аргументов в соответствии с six значения ми на тех наборах, где логическая функция равна единице, и объединить элементарные конъюнкции в логическую сумму.
Очевидно, что аргументы, равные нулю, в элементарных конъюнкциях берутся с отрицанием.
Приведенное правило записи СДНФ называется записью логической функции по единицам, или по условиям истинно сти.
62
Определение. Совершенной дизъюнктивной нормальной формой называется дизъюнкция конституент единицы, или элементарных конъюнкций, равных единице на тех же набо рах, что и заданная логическая функция.
Любая логическая функция, кроме константы нуль, может быть представлена в совершенной дизъюнктивной нормальной форме и единственным образом. Это следует из разложения любой логической функции при использовании только дизъ юнкции, конъюнкции и отрицания. Члены разложения пред ставляют собой конъюнкции комбинаций аргументов с отрица ниями или без отрицаний на значения функций при данных значениях аргументов. Число членов разложения равно 2", где п —- количество аргументов, или двоичных переменных. Конъюнкции объединяются в логическую сумму. Учитывая, что число членов разложения логической функции трех аргу ментов— 23, молено записать [1]:
/ ( А , , Ао, А3) = лу X , А'з -/(0, 0, 0) V *1 -*2*8 -/(0, о, 1) V
V АТА'2л'з-/(0 , 1, 0) V AV 4>x3•/(0, 1, 1) V А1А2х з' / ( 1, 0, 0) \/
\/ х 1л'2л'з-/(1, 0, 1) V А1л,л-3-/(1 , 1, 0) V а 1а-2л:3- / ( 1, 1, 1).
Подставляя значения единицы на наборах переменных, где функция равна единице, и опуская члены логической суммы, равные нулю, получим представление переключательной функ ции в совершенной дизъюнктивной .нормальной форме.
Так, функция |
логической |
равнозначности / 9(лу у) |
(см. |
та'бл. 3.2), имеющая в разложении 22 'членов, |
|
||
/ 9(a , y) = x y - f { 0 , |
0) - f ху •f (0, |
1) - f A y - / ( I , 0) + A- у - / ( I , |
1) |
принимает на наборах аргументов (0,0) и ( 1,1) значения еди ницы /9(0,0) = 1 и /э( 1,1) = 1, а на остальных наборах (0,1) и ( 1,0) значения нуля /д(0,1) = 0 и /9( 1,0) = 0 в соответствии с ее табличным заданием.
Учитывая это, элементарная функция fg(x, у) имеет сле дующую совершенную дизъюнктивную нормальную форму, вы раженную при использовании только дизъюнкций, конъюнк ций и отрицаний к ее аргументам:
/ 9(а , у) = а у ■1 у ху -0 V a v -0 \/ д-у •i — х у \/ ху.
Совершенная дизъюнктивная нормальная форма, образо ванная по данным таблицы истинности, представляет собой запись логической функции по условиям 'истинности, или по единицам.
63
Если исходная функция задана аналитически, то приведе ние функции к совершенной дизъюнктивной нормальной фор ме выполняется в следующей последовательности:
1) логическая функция с помощью закона инверсии (3.12,
3.13) приводится к нормальной форме, в которой инверсия применяется лишь к отдельным аргументам;
2) логическая функция приводится к дизъюнктивной нор мальной форме, в которой члены объединены в логическую сумму; члены суммы представляют собой конъюнкции отдель ных аргументов, взятых с отрицанием или без него;
3)число аргументов в каждой конъюнкции увеличивается до я за счет преобразований, тождественно равных единице;
4)из полученного выражения с конъюнкциями я-го ранга удаляются конъюнкции, тождественно .южные и лишние или повторяющиеся конъюнкции [1, 2, 4].
Пример. Привести функцию }(х и х2, х3, х4) = (a'i.v2) (х3\/ л%)
ксовершенной дизъюнктивной нормальной форме.
1)Приведем функцию к нормальной форме
(Л].\"2) (л-., \ / А 4) |
( ^ 1 |
АД) |
2) Получим нормальную дизъюнктивную форму
(.V, V -V,) (Л*3Л'4) — A',A3A'4 V А-2АГ3Л'4.
3) Дополним конъюнкции, не содержащие всех аргументов, до я-го ранга за счет преобразований, тождественных единице:
x,x:ix j x 2\ /x 2) \/ х2х3х.,(х, V х,) =
== А 1Ап АДА 4 Ху* A jA 2 A 3.V4 \ / А [АД Х 2 Л 4 \ / A’ j А . АцА^ .
4) Для приведения логической функции к совершенной дизъюнктивной нормальной форме необходимо исключить из
последнего выражения лишний член х\х2х3х4:
/ ( а-,, л:2| а' :„ а .,) = л^А'оЛ'зА'., V лулл a> v4 V а:о х 3х 4.
Так как любая переключательная функция может быть представлена в совершенной дизъюнктив!ной нормальной фор ме (табл. 3.3), то, следовательно, отрицание, конъюнкция и дизъюнкция образуют базис. Константа нуля /о (а , у ) — един ственная логическая функция, не имеющая совершенной дизъ юнктивной нормальной формы, однако и эту функцию можно выразить через операции первой функционально полной систе
мы, например, в форме /о(а, у) —хх.
Базис { НЕ, |
И, ИЛИ 1 может быть уменьшен за счет |
удаления из него |
конъюнкции или дизъюнкции [3]. |
Справедливость этого утверждения следует из формул (3.12)
и (3.13):
х \/ у — ху; х у = х V у.
Аналогично СДНФ строится совершенная конъюнктивная нормальная форма, но три условии разложения логической функции на элементарные дизъюнкции. При задании логиче ской функции таблицей истинности для образования совер шенной конъюнктивной нормальной формы необходимо запи сать элементарные дизъюнкции аргументов в соответствии с их значениями на тех наборах, где исходная функция равна пулю, и объединить элементарные дизъюнкции в логическое произведение. Очевидно, что аргументы, равные единице, в элементарных дизъюнкциях берутся с отрицанием.
Приведенное правило записи СКНФ называется записью переключательной функции по условиям ложности, или по нулям.
Определение. Совершенной конъюнктивной нормальной формой называется конъюнкция конституент нуля, или эле ментарных дизъюнкций, равных нулю на тех же наборах, что и заданная логическая функция.
Любая логическая функция, кроме константы единицы, мо жет быть представлена в СКНФ и единственным образом.
Так, |
функция логической неравнозначности (см. табл. 3.2) |
|
/6(.v, у), |
принимающая значение нуля па наборах переменных |
|
(0,0) и |
( 1,1), имеет совершенную конъюнктивную нормальную |
|
форму в виде логического |
произведения двух конституент |
|
нуля, |
|
|
|
/.(*> у) = |
(-V V у) (х \/ у). |
Если логическая функция п аргументов задана аналити чески, то приведение функции к СКНФ выполняется в следую щей последовательности:
1)путем применения законов инверсии (3.12, 3.13) к дизъюнкциям и конъюнкциям логическая функция приводится
кнормальной форме, в которой отрицания берутся к отдель ным переменным;
2)путем использования распределительного закона (3.11) нормальная форма приводится к конъюнктивной, представ
ляющей собой конъюнкцию ряда членов, каждый из которых есть дизъюнкция отдельных переменных, взятых с инверсией или без нее;
3)каждый множитель конъюнктивной формы, содержащий менее п переменных, дополняется до п аргументов путем пре образований, тождественно равных нулю;
4)выполняется приведение подобных членов по формуле
(3.15) [1,2, 4].
5 |
9. В, Сарннгулян, Г. D. С м и р н о м |
65 |
|
|
Пример. Привести функцию / ( а ,. а 2, а 3) = а , V (а 2 ■ х з)
ксовершенной конъюнктивной нормальной форме.
1)Приведем функцию к нормальной форме
|
|
-И V (-Va V -V;,) |
— A t V А 2А а. |
|
|
||||
2) |
Получим |
нормальную конъюнктивную форму |
(3.11) |
||||||
|
|
A j \ / А 2А 3 :г—(Л , \ / Ап) (А , \ / А а). |
|
||||||
3) |
Дополним |
дизъюнкции |
|
недостающими |
переменными |
||||
путем добавления |
членов |
а3а3 |
и а2а2, тождественно |
равных |
|||||
нулю, |
|
|
|
|
|
|
|
|
|
(а , V А , ) (А , V А;,) = А , |
V А , |
V А аА а) А', \ / А;. \ / А оАо). |
|||||||
4) |
Путем применения формулы |
(3.11) логическая функция |
|||||||
приводится к следующему виду: |
|
|
|
|
|||||
|
(а , \ А , V А 5А - ) ( А , V А 3 V А 2А о) = |
|
|||||||
= - |
(А , V А 2 V A ;i) ( а , V А , V |
А-3) ( X , \ / A SA ,) |
(АV, А;, |
V А ,) . |
|||||
5) В результате использования формулы (3.15) исходная |
|||||||||
функция приводится к совершенной |
конъюнктивной нормаль |
||||||||
ной форме: |
|
|
|
|
|
|
|
|
|
/ ( А , , А г , А '.):— |
(А',V Ап \/ А а) |
(А , \ / А 2 \ / А 3) |
(A Vj Ао V А а). |
||||||
Константа |
единицы /15(а , |
у ) —единственная переключа |
|||||||
тельная функция, |
не имеющая совершенной |
конъюнктивной |
|||||||
нормальной формы, однако и эту функцию можно |
выразить |
||||||||
через операции первой функционально полной системы, напри мер, в форме / ]5(а , у) = а V а .
Приведем табл. 3.3 элементарных переключательных функ ций, имеющих СДНФ и СКНФ.
Рассмотренные выше совершенная дизъюнктивная и совер шенная конъюнктивная нормальные формы используются для исходного изображения логической функции, поскольку, как правило, эти формы оказываются излишне усложненными для их технической реализации. Покажем это на примере. Пере ключательная функция fs (а, у) для овоей реализации потребу ет, исходя из СДНФ, элемент НЕ, два элемента И и элемент ИЛИ (ем. табл. 3.3). При использовании СКНФ этой функ ции (см. табл. 3.3) ее логическая схема будет включать эле мент НЕ, два элемента ИЛИ и элемент И,
66