Файл: Дроздов Е.А. Многопрограммные цифровые вычислительные машины.pdf

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

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

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

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

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

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

Совершенной дизъюнктивной нормальной формой логической функции F (х 1, Х2 , .. ; Хп ) от п различных двоичных переменных на­ зывается д. н. ф., обладающая следующими свойствами:

а) в ней нет двух одинаковых конъюнкций; б) ни одна конъюнкция не содержит двух одинаковых двоич­

ных переменных; в) никакая конъюнкция не содержит двоичной переменной вме­

сте с ее отрицанием; г) все конъюнкции имеют п-й ранг, причем каждая из них со­

держит либо переменную x jt либо ее отрицание X j ( j = 1, 2, ..., п ). Условия (свойства) а, б, в и г являются необходимыми и доста­ точными для того, чтобы дизъюнктивная нормальная форма была совершенной нормальной формой. Они же указывают путь для при­ ведения любой не тождественно ложной функции к совершенной дизъюнктивной нормальной форме. Произвольная логическая функ­ ция F (xu Х2 , ■■., х п ) приводится к совершенной д. н. ф. в такой по­

следовательности:

— функция F ( х ь х 2, ..., х п ) приводится к какой-либо дизъюнк­ тивной нормальной форме;

82

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

Q ( „ - l, = Q ( « - 1) ( Х } у - }) = X j Q ( n - V у

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

Теперь для приведения исходной логической функции к совершенной д. и. ф. достаточно исключить из последнего соотношения лишний член xix2x3:

функции от п двоичных переменных называется конъюнктивная нормальная форма, удовлетворяющая следующим условиям:

а) в ней нет двух одинаковых дизъюнкций; б) ни одна дизъюнкция не содержит двух одинаковых двоич­

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

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

переменные, которые имеют в таблице значения единицы, и инверсируются те двоичные переменные, которые имеют значения нуля.

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

Пример. Построить совершенные нормальные формы для логической функ­ ции F (.Vi, .v2, л 'з ) , заданной табл. 3.2.

1

0

1

При естественном расположении наборов двоичных переменных (000,001,010 и т. д.), как это сделано в табл. 3.2, переменные в элементарных конъюнкциях инверсируются в соответствии й двоичными эквивалентами их порядковых деся­ тичных номеров. Поэтому для рассматриваемого примера

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

§ 3.5. Минимизация логических функций и синтез логических схем

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

84

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

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

Для построения узлов ЦВМ чаще всего используются элементы, обеспечивающие реализацию таких элементарных логических опе­

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

Логические элементы именуются в соответствии с реализуемы­ ми функциями. Для реализации отрицания используется инвертор

Пирса (элемент ИЛИ—НЕ). В учебных логических схемах элемен­ ты обозначают в виде прямоугольников с записью внутри послед­ них сокращенных наименований элементов; при оформлении (вы­ черчивании) схем-документов пользуются стандартизированными условными изображениями элементов в виде прямоугольников или сегментов. Примеры условных изображений элементов приведены на рис. 3.1.

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

85

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

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

Минимизация логических функций малого числа переменных (п 5) может осуществляться по методу непосредственных преоб­ разований, являющемуся во многих случаях наиболее простым. Ми­ нимизация сложных логических функций проводится, как правило, с использованием машинных методов, т. е. путем реализации соот­ ветствующих алгоритмов на ЦВМ [3, 18].

8<з