книги из ГПНТБ / Сарингулян, Э. В. Арифметические и логические основы цифровых машин учеб. пособие

и

ванной по отношению к множеству конъюнкций того же ранга,

Аналогично понятию конституенты единицы введем поня­ тие конституенты нуля.

Логическая функция п переменных, принимающая значе­ ние, равное нулю только на одном из наборов, называется кон­ ституантой нуля, или элементарной дизъюнкцией. На осталь­ ных (2Л— 1) наборах функция равна 1. Для логических функ­ ций двух аргументов, определенных на четырех наборах, мож­

Дизъюнкция / 7(х, у) есть частный случай конституент нуля. Принимая во внимание значения переменных на наборах, когда функция равна нулю, конституенты нуля D выражают через дизъюнкцию аргументов, взятых с отрицанием или без отрицания. Отрицания расставляются так, чтобы обратить эту дизъюнкцию в нуль на заданном наборе. Для логических

функций /у, /п, f 13, / 14 можно записать

Пользуясь понятиями конституент единицы и нуля, рас­ смотрим задание логической функции в нормальной дизъюнк­ тивной и нормальной конъюнктивной формах.

Логическая функция задана нормальной дизъюнктивной формой, если она выражена через дизъюнкцию конституент единицы или через логическую сумму элементарных конъ­ юнкций.

GO

П р и м е р . Д л я ф у н к ц и и

f (Х|, Х 2, -'•3> -П) == (-Н V Х 3) V (-'■2 V -'-з) V (-VT( \J Л'Л) \J (х3V Л4)

найти ее .нормальную канътоиктвнуло 'форму.

Применим закон инверсии для логической суммы (3.12):

/(л -,, х а, х.„ х 4) = х ,х , V х ,х 3V л',х4 V х 3х 4.

Затем сгруппируем первый и .второй, третий и четвертый члены:

представляет собой нормальную конъюнктивную форму. После преобразований, основанных па законах и соответст­

вующих соотношениях алгебры логики, логическая функция может быть представлена различными нормальными дизъюнк­ тивными или конъюнктивными формами.

Задача анализа и синтеза логических схем подобна мате­ матической задаче описания заданной логической функции че­ рез элементарные логические функции выбранной функцио­ нально полной системы. Поскольку любая переключательная функция выражается через элементарные функции неодно­ значно, возникает вопрос о выборе некоторых нормальных форм для представления заданных логических функций, кото­ рые могли быть использованы в качестве исходных. Исходные формы должны быть удобны для изображения любой пере­ ключательной функции и для дальнейшего возможного упро­ щения. В качестве таких форм в теории анализа и синтеза ди­ скретных автоматов на основе первого базиса используются совершенная дизъюнктивная нормальная форма СДНФ и со­ вершенная конъюнктивная нормальная форма СКНФ.

Логическая функция часто задается таблицей истинности, которая отражает условия работы некоторой цифровой схемы. Для образования совершенной дизъюнктивной нормальной формы по таблице истинности необходимо записать элемен­ тарные конъюнкции аргументов в соответствии с 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).

Подставляя значения единицы на наборах переменных, где функция равна единице, и опуская члены логической суммы, равные нулю, получим представление переключательной функ­ ции в совершенной дизъюнктивной .нормальной форме.

принимает на наборах аргументов (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

Справедливость этого утверждения следует из формул (3.12)

и (3.13):

х \/ у — ху; х у = х V у.

Аналогично СДНФ строится совершенная конъюнктивная нормальная форма, но три условии разложения логической функции на элементарные дизъюнкции. При задании логиче­ ской функции таблицей истинности для образования совер­ шенной конъюнктивной нормальной формы необходимо запи­ сать элементарные дизъюнкции аргументов в соответствии с их значениями на тех наборах, где исходная функция равна пулю, и объединить элементарные дизъюнкции в логическое произведение. Очевидно, что аргументы, равные единице, в элементарных дизъюнкциях берутся с отрицанием.

Приведенное правило записи СКНФ называется записью переключательной функции по условиям ложности, или по нулям.

Определение. Совершенной конъюнктивной нормальной формой называется конъюнкция конституент нуля, или эле­ ментарных дизъюнкций, равных нулю на тех же наборах, что и заданная логическая функция.

Любая логическая функция, кроме константы единицы, мо­ жет быть представлена в СКНФ и единственным образом.

Если логическая функция п аргументов задана аналити­ чески, то приведение функции к СКНФ выполняется в следую­ щей последовательности:

1)путем применения законов инверсии (3.12, 3.13) к дизъюнкциям и конъюнкциям логическая функция приводится

кнормальной форме, в которой отрицания берутся к отдель­ ным переменным;

2)путем использования распределительного закона (3.11) нормальная форма приводится к конъюнктивной, представ­

ляющей собой конъюнкцию ряда членов, каждый из которых есть дизъюнкция отдельных переменных, взятых с инверсией или без нее;

3)каждый множитель конъюнктивной формы, содержащий менее п переменных, дополняется до п аргументов путем пре­ образований, тождественно равных нулю;

4)выполняется приведение подобных членов по формуле

(3.15) [1,2, 4].

Пример. Привести функцию / ( а ,. а 2, а 3) = а , V (а 2 ■ х з)

ксовершенной конъюнктивной нормальной форме.

1)Приведем функцию к нормальной форме

через операции первой функционально полной системы, напри­ мер, в форме / ]5(а , у) = а V а .

Приведем табл. 3.3 элементарных переключательных функ­ ций, имеющих СДНФ и СКНФ.

Рассмотренные выше совершенная дизъюнктивная и совер­ шенная конъюнктивная нормальные формы используются для исходного изображения логической функции, поскольку, как правило, эти формы оказываются излишне усложненными для их технической реализации. Покажем это на примере. Пере­ ключательная функция fs (а, у) для овоей реализации потребу­ ет, исходя из СДНФ, элемент НЕ, два элемента И и элемент ИЛИ (ем. табл. 3.3). При использовании СКНФ этой функ­ ции (см. табл. 3.3) ее логическая схема будет включать эле­ мент НЕ, два элемента ИЛИ и элемент И,

66

Т а б л и ц а 3.3

Представление логических функций двух аргументов в СДНФ и СКНФ

В действительности функция f5(x, у) повторяет на наборах

ских схем решать задачу о возможном упрощении переключа­ тельных функций или находить минимальные дизъюнктивные и конъюнктивные нормальные формы. Минимизация логических функций является одним из основных этапов анализа и синте­ за цифровых схем, так как решается вопрос о рациональной технической реализации заданного алгоритма.

Дизъюнктивная или конъюнктивная нормальные формы представляются минимальными, если количество знаков дво ичных переменных и их отрицаний будет наименьшее по срав­ нению с любой другой дизъюнктивной или конъюнктивной нормальной формой соответственно.

Минимальные формы логических функций могут быть оп­ ределены аналитическими или табличными методами, основан­ ными на свойствах переключательных функций, законах ал­ гебры логики и их следствиях,

Рассмотрим минимизацию логической функции, заданной или приведенной к совершенной дизъюнктивной нормальной форме методом Квайна. Алгоритм минимизации СДНФ вклю­ чает два этапа:

1) нахождение сокращенной дизъюнктивной нормальной формы аналитическим способом;

2) построение минимальной дизъюнктивной нормальной формы аналитическим или табличным способом.

Получение сокращенной дизъюнктивной нормальной фор­ мы методом Квайна основано на использовании операций склеивания и поглощения.

При выполнении операции склеивания все члены необходи­ мо оставлять в выражении, чтобы можно было использовать

В результате будет получена дизъюнктивная форма, содер­ жащая, кроме, всех констнтуент единицы, еще и другие элемен­ тарные произведения. Затем требуется провести операции по­ глощения по формуле

Процесс понижения рангов конъюнкций продолжается до об­ разования всех изолированных конъюнкций.

Вид функции, полученный после всех этапов склеивания и поглощения, является сокращенной дизъюнктивной нормаль­ ной формой. Любая переключательная функция имеет единст­ венную сокращенную дизъюнктивную нормальную форму [2].

Пример. Найти сокращенную дизъюнктивную нормальную форму логической функции / (a, b, с, d) — abc у cibd V abcd\/ V ab c d.

Прежде всего необходимо представить исходную функцию в совершенной дизъюнктивной нормальной форме. Для этого умножим первый член на d\/d~ 1, а второй член на с\/с—1.

f(a , b, с, d) — abc (d V d) V abd (с у с) \/ abed \/ abed =

—abed V abed V abed- \J abed \J abed. V abed

=- abed V abc d \/ abed, У abed \/ a b c d.

Проведем операции склеивания (3.29): _ первого члена со вторым по переменной d(abc), второго члена с третьим по переменной c(abd), второго члена с пятым по переменной b(acd).

68

Результат запишем в такой форме:

fin, b, с, d)=--abcd\fabcd\/abcdyabcd\'abcci\/abc\ abd\/acd.

Произведение abc поглощает первый и второй члены, про­

паведение abd— второй и третий члены и произведение acd— второй и пятый члены:

/ (а, b, с, d) = abc V abd \/ ас d \/ abed,

К этому выражению операции склеивания и поглощения применить нельзя и, следовательно, оно является сокращенной дизъюнктивной нормальной формой заданной переключатель­ ной функции.

Пример. Найти сокращенную дизъюнктивную нормальную

форму переключательной функции f(a., b, с) = abc \J bc\/abc. Необходимо заданную лопическую функцию привести к со­

вершенной дизъюнктивной нормальной форме:

1) abc \/ be V abc = {a v b) c \J (b \J с) (a \/ b V c) ~

= ас V be v ab \/ ас V be V be = ас V be V ab \J ax \/ bc\

2)ac(b\/b) Vbc(a\/a) V <^b(c\/c)\/ac(byb)V bc(aVa)==

~a b c\ ja b c y abc\/a b c\Jabc\,'ab c\/abc\fab c\/ abc \/ ub7=

—abc V a be V abc \J ab с V abc V abc.

Полученное выражение есть совершенная дизъюнктивная нормальная форма.

3) Проведем операции склеивания:

первого члена со вторым по переменной Ь(ас), первого члена с шестым по переменной c(ab), второго члена с третьим по переменной а(Ьс), третьего члена с четвертым по переменной c(ab), четвертого члена с пятым по переменной Ь(ас), пятого члена с шестым по переменной а(Ьс).

_ 4)_ Проведем операции поглощения произведениями ас, ab, be, ab, ас, Ьс всех конституант единицы СДНФ:

/ (а, Ь, с) = ас V ab V Ьс \/ ab V ас \/ Ьс.

К этому выражению операции склеивания и поглощения применить больше нельзя; полученная форма является сокра­ щенной дизъюнктивной нормальной формой.

6 9