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

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

Рассмотрим пример разложения функции на конституенты еди­ ницы. Пусть дана схема автомата (рис. 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

В первой фигурной скобке при принятом обозначении будем

иметь

cd\J хг.

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

cd\Jхг = (сVхг) (d V *1 )•

Подставив значения с и d, получим:

cd\Jxx = \f (0, 0, х3, . . . , хп) V Xi\Jх2] X

X [/(О, I, х3, . . . , хп) \ / х 2\ / хг].

Преобразовав аналогично вторую фигурную скобку, получим

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

122

стить равными 1 переменные, соответствующие слагаемым с от­ рицанием.

Если при какой-либо комбинации значений переменных, выбран­ ных в соответствии с изложенным правилом, функция принимает

в разложении исчезают. (Этот случай соответствует последователь­ ному включению в цепь постоянно замкнутых контактов, которые заменяются простым соединительным проводом.)

Если функция при соответствующих наборах переменных при­ нимает значение 0, то стоящий при ней конституент разложения нуля в формуле разложения функции остается (х + 0 = х), а эле­ ментарная цепь, описанная этим конституентом, в схеме необхо-

f(o,X2,...X„) -jr - f ( U 2,...x „)V [НФа ~°) \-у^(1,о,-о) I -г

дима. Формула (5.28) показывает, что схему, предназначенную для реализации любой логической связи, можно представить в виде последовательно соединенных групп элементов, каждая из которых состоит из параллельного соединения одиночных элементов.

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

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

123

§ 6. СХЕМНАЯ РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

Любое логическое выражение может быть изображено в виде схемы, построенной из логических элементов «И», «ИЛИ»—«НЕ», а преобразование логических выражений с помощью законов (1—10) отражает преобразование логических схем в другие эквивалентные им схемы. Отсюда и вытекает значение алгебры логики как мате­ матического аппарата при проектировании логических схем.

Например, тот факт, что логическая функция А \] (А /\ В) эк­ вивалентна логической функции A \J В, так как

А \ / ( А ^ В ) = ( А У А ) М Л У В ) ^ \ / \ ( А У В ) = А У В ,

делает очевидным, что схема, изображенная на рис. 28, эквива­ лентна схеме, изображенной на рис. 29. Нетрудно видеть, что вторая

схема значительно проще.

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

Символическая формула—это представление функции в виде фор­ мулы, состоящей из символов аргументов, символов операций кон­ стант «1» или «0». Применяются два способа составления логиче­

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

124

жение); 2) в произведениях знаки инверсии должны быть

Теперь по этой формуле строим схему (рис. 31), для реализа­ ции которой требуется 6 логических элементов (3 — «И», 1 — «ИЛИ», 2 — «НЕ»).

Правило составления символической формулы переключательной функции по «0»

Для составления символической формулы переключательной функции по нулям необходимо:

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

в дизьюнкциях знаки инверсии должны быть поставлены над теми аргументами, которые равны «1» на соответствующих наборах; преобразуем полученную в примере 5 символическую формулу

иполучим более экономичный вариант схемы:

П= А-В

125

— делать ничего не нужно, так как она образует один логический элемент. Для С можно добавить: АА и ВВ, которые равны «О, О»,

С = А - В + А - В + А - А + В - В = А - ( А + В ) + В ( А + В ) =

= ( А + В ) (А + В ).

Теперь по формулам для П и С строим схему (рис. 32), для реа­ лизации которой требуется 6 логических элементов (2 — «И», 2 —

«НЕ», 2 — «ИЛИ»).

щий вид:

Ск — A kBkfIk—\ + A kBkFlk—\ + A kBkFlk—\ + А кВкПк-\-

Пн —А кВкПи—1 A kBkIlk—1-{• A kBkIlk—\ + А кВкПк—1-

Тогда очевидно, что для реализации данной логической схемы необходимо иметь 12 логических элементов (7 — «И», 3 — «НЕ», 2 — «ИЛИ»).

126

Проделав преобразования, получим схему рис. 35. Для реа­ лизации данной схемы необходимо:

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

127

О— . . . abc, abc, abc, abc.

1 — . . . abc, abc, abc, abc.

В соответствии с правилами образования сложных высказыва­ ний имеем:

вилами суммирования в результате должна быть 1 и в переносе 1. Действительно:

2 = 111 + 100 + 010 + 001 = 1 + 0 + 0 + 0 = 1,

Я = 101+ 001+ 111+ 100 = 0 + 0 + 1 + 0 = 1 .

Вопросы и задачи для самопроверки

1.Исходя из табличного задания, напишите ДСНФ и КСНФ всех функций двух переменных.

2. Перепишите номера наборов, на которых функции f 1 (лц, х 2, х3) и (гОД-

х 2, х ?) равны единице, и составьте ДСНФ этих функций.

3.Сформулируйте правило, как по таблице переключательной функции по­

строить ДСНФ инверсии этой функции.

4. Запишите булеву функцию, заданную ее образующим словом «В», в СДНФ

и СКНФ:

ВI = 1111100010001000,

В4 = 1000111110001000, Вв = 0010001011110010,

В7 = 0100010011110100.

5.Для того, чтобы перейти к записи переключательной функции с помощью функции Шеффера (Пирса), можно взять двойное отрицание от каждого члена ДСНФ (КСНФ) заданной функции и применить правило де Моргана. Проверьте возможность такого преобразования на примерах и сформули­ руйте правило.

128

Глава шестая

М ИНИМ ИЗАЦИЯ БУЛ ЕВ Ы Х Ф УНКЦИ Й

§ 1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ЦЕЛИ И ЗАДАЧИ СИНТЕЗА

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

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

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

Процедура синтеза логических схем состоит из ряда этапов: 1 ) формулировки задачи, включающей полное описание зависимо­ стей «вход—выход» синтезируемой логической схемы и особых требований, предъявляемых к ней; 2 ) выбора типа логических эле­ ментов с учетом их технических характеристик; 3) выбора функ­ ционально полной системы функций алгебры логики; 4) нахождения по определенным правилам функциональных схем синтезируемого логического устройства; 5) изучения полученных решений с точки зрения их принципиального соответствия заданию и выбора опти­ мального решения; 6 ) подбора параметров элементов функциональ­ ной схемы, составления принципиальной схемы; 7) проверки ра­ боты логической схемы расчетным путем или на моделирующем устройстве.

Нужно заметить, что пункты 5 и 7 относятся к задаче анализа* но эти этапы органически слиты с синтезом, так как с инженерной точки зрения процедура последнего должна завершаться нахожде­ нием по возможности оптимального и апробированного решения.

Инженерные методы решения синтеза логических схем должны

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

Методы решения и получаемый результат преобразования и, особенно, синтеза логических схем существенно зависят от выбора той или иной полной системы элементарных функций и соответст­ вующего ей набора функциональных типов логических элементов. В некоторых случаях синтез логических схем целесообразно вы­ полнять в системе «И», «ИЛИ», «НЕ».

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

Суть процедуры синтеза логических схем в системе «И», «ИЛИ», «НЕ» можно схематически изложить следующим образом. Завер­ шающим итогом первого этапа, имеющего целью двоичное кодиро­ вание описания работы синтезируемого устройства, должно яв­ ляться: 1 ) получение конкретной функции алгебры логики, опреде­ ленной для всевозможных наборов значений аргументов, таблицы соответствия функции; 2 ) после этого легко представить получен­ ную функцию в любой из двух совершенных нормальных форм; 3) затем возможно выполнить ряд упрощений, достигаемых путем различных тождественных преобразований, с целью получения формулы, эквивалентной исходной, но содержащей меньшее число вхождений букв (как говорят, формулы меньшей длины).

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

еенахождения — минимизацией формулы.

Одна и та же булева функция может иметь несколько мини­

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

Различные аналитические, графоаналитические и табличные методы минимизации формул основаны на тождественных преобра­ зованиях совершенных нормальных форм, в соответствии с рассмот­ ренными законами (1 —1 0 ), а также законами склеивания (1 1 ) и поглощения (12), которые приводятся в главе 4. Эти преобразо­ вания позволяют получать эквивалентные формулы, отличающиеся от соответствующих исходных совершенных нормальных форм меньшим количеством членов и меньшей длиной последних и вы­ полняются до тех пор, пока дальнейшее упрощение формулы с их

130