Файл: Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие.pdf

Действительно,

Nf — Л ^ + Лг-Ь • • • + А т.

Логической сумме функций Лг соответствует подмножество Nf* Следовательно, каждой функции алгебры логики А с можно поста'

будет равна числу букв в исходной ДНФ.

Для нахождения более простой формы булевой функции необ­ ходимо найти такую ДНФ или такое покрытие подмножества Nf интервалами N A a Nf, чтобы (5.22) было минимальным. Для на­

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

§ 5. РАЗЛОЖЕНИЕ ФУНКЦИЙ НА КОНСТИТУЕНТЫ (ЗАКОН РАЗЛОЖЕНИЯ ФУНКЦИЙ)

Пусть задана некоторая функция алгебры логики f (х), которую

118

х f (х) = ахх V Ьхх = Ьх,

или

xf(x) = f(l)x, x f { x ) ~ f (0) x.

Рассмотрим теперь разложение двух переменных / (х, у). Вна­ чале разложим функцию по л: при фиксированном значении у. Оче­ видно, можно записать:

fix, у) = ф(х).

На основании (5.24):

ср(х) = ф(1)х\/ф(0)х.

При этом Ф (1) = / (1, у); ф (0) = / (0, у).

Тогда

Разложив функции / (1, у) и f (0, у) как функции одной перемен­ ной, пользуясь (5.24), получим:

Подставив полученные разложения в (5.25), получим оконча­ тельно:

и поэтому не зависит от порядка, в котором выполняется разложе­ ние.

схему, где xt — контакты элементов схемы. Поступив с этой функ­ цией, как и ранее, получим разложение вначале относительно пере­ менной х х:

f ( x x, х2, х3, . . . , * „ ) = / ( 1, х2, х3, . . . , х„)ххV V / (0, х2, Х3, . . . , хп) хх.

119

Из этой формулы, в частности, следует, что при преобразовании релейно-контактной схемы число контактов одного из ее элементов может быть всегда сведено к одному переключающему контакту х х.

Выполнив разложение последовательно относительно каждой переменной, получим

Полученное разложение представляет собой сумму членов, каж­ дый из которых является конституентом единицы, умноженным на коэффициент, значение которого равно значению исходной функции, если в ней принять равными единице те переменные, которые вхо­ дят в конституент в виде простых сомножителей, и равными нулю те переменные, которые в конституент входят с отрицанием. Схема, эквивалентная разложению (5-27), приведена на рис. 25.

f(1,x2,...x„)\-xf

Ф и * г , * з )

~jW,x2t-Xn)\Xl

Рис. 25

В реальной релейно-контактной схеме разложение (5.27) озна­ чает следующее. Для каждого простого сомножителя конституента нужно соединить накоротко имеющиеся в схеме замыкающие кон­ такты соответствующего элемента и разомкнуть цепи, содержащие размыкающие контакты. Для каждого сомножителя, входящего

вконституент с отрицанием, нужно разомкнуть все замыкающие

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

Полученный результат следует толковать так: любая функция алгебры логики может быть представлена в виде суммы некоторых конституентов единицы, а схема, реализующая эту функцию,—

120

в виде ряда параллельных цепей, каждая из которых состоит только из последовательно соединенных элементов.

Рассмотрим пример разложения функции на конституенты еди­ ницы. Пусть дана схема автомата (рис. 26), которую можно описать функцией алгебры логики:

/(*. У> z) = x (y\fz)\l~x{y\Jz).

Для определения конституентов 1, на которые разлагается данная функция, найдем значения коэффициентов при конституентах и результат сведем в таблицу 5-6.

Согласно (5.27):

/ (х, у, z) = x(y\Jz)\J х (у\/z) — xyz\J xyz\] xyz\J xyz\J xyz\J xyz.

Любая функция алгебры логики может быть разложена на кон-

ституенпгы нуля. Пусть задана некоторая дизъюнкция алгебры

121