Составление логических функций.

 

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

Запись логической функции в виде суммы произведений переменных называют дизъюнктивной нормальной формой (ДНФ):

а запись функции в виде произведения сумм — конъюнктивной нормальной формой (КНФ):

Инверсия любой функции, записанной в дизъюнктивной (конъюнктивной) нормальной форме, по правилу (1.5) дает замену записи на конъюнктивную (дизъюнктивную) нормальную форму. Например, инверсия функции

имеет вид

.

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

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

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

Пусть в качестве примера функция F задана в виде табл.2.3. Для комбинаций переменных 2, 7, 8 функция F истинна (т. е. F=1), что означает для указанных комбинаций равенство единице следующих произведений: хуz=1.

Таблица 2.3

Таблица истинности

Номер комбинации	X	Y	Z	F

 

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

Функция, определяемая таблицей истинности, может быть представлена не только ее единичными, но и нулевыми значениями. Так, на основании табл.2.3 рассматриваемая функция ложна (F =0 или F=1), если истинно каждое из произведений

Воспользовавшись законом инверсии, приходим к записи функции в СКНФ:

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

 

Примеры составления логических функций.

Простую логическую функцию иногда можно записать в аналитической форме непосредственно из словесного определения. Покажем это на примере составления функций «Равнозначность» и «Неравнозначность», которые будем использовать в дальнейшем. Функция «Равнозначность» принимает значение 1, если две ее входные переменные имеют одинаковые логические потенциалы: x₁=x₂=1 ИЛИ x1=x2=0. Поэтому ее представляют как . Условное изображение элемента «Равнозначность» приведено на рис.2.3,а.

Функция «Неравнозначность» принимает значение 1, если две ее входные переменные имеют разные логические потенциалы: x₁=1, x₂=0 ИЛИ x₁=0, x₂=1. Поэтому ее представляют в следующем виде:

,

где значок - символизирует функцию «Неравнозначность».

Рис.2.3 Условные изображения элементов «Равнозначность» (а) и «Неравнозначность» (б).

 

Функцию «Неравнозначность» иначе называют «Исключающее ИЛИ». Ей присуще интересное свойство: если на один ее вход подать лог.1, то логический потенциал, поданный на второй вход, будет на выходе инвертирован; если же вместо лог.1 на один вход подать лог.0, то функция будет вести себя как повторитель логического потенциала, поданного на другой вход. Это легко проверит это самостоятельно. Условное изображение элемента «Неравнозначность» дано на рис. 2.3,б. Вместо приведенного значка (=1) используется значок m2, указывающий на то, что «Исключающее ИЛИ» функционирует по правилам сложения одноразрядных двоичных чисел (сложение по модулю 2): 1+0=1; 0+1=1; 0+0=0; 1+1=0 (при арифметическом сложении единица переносится в соседний более старший разряд).

В общем случае для получения аналитической формы функции используют таблицы истинности.

Пример 2.8. Пусть на выходе некоторого устройства должен появиться сигнал высокого уровня (лог.1, у=1), если на входах устройства действует комбинация сигналов х₁х₂х₃ из набора №1 ИЛИ из набора №2 ИЛИ из набора №3 ИЛИ из набора №6, приведенные в табл.2.4. Если на каждом перечисленном наборе конъюнкция сигналов будет равна лог.1, то на выходе устройства будет сигнал высокого уровня (U¹).

Таким образом, функция, представленная табл.2.4, запишется в виде , (2.9)

где сигналы х₁,х₂,х₃, инвертированы, если они в соответствующих наборах равны лог.0 (иначе конъюнкция не будет равна 1).

Таблица 2.4

Таблица истинности функции y

Номер набора	х3	х2	х1	y	Номер набора	х3	х2	х1	y

 

Такая форма логической функции, как указывалось ранее, называется совершенной дизъюнктивной нормальной формой ( СДНФ). Она представляется логической суммой простых конъюнкций, каждая из которых содержит все переменные в прямом или инверсном виде не более одного раза; в такие конъюнкции не входят суммы переменных, а также отрицания произведений двух или более переменных. Входящие в СДНФ конъюнкции называются минтермами или конституентами единиц. Логическая сумма конъюнкций, отличающаяся от (2.9) тем, что все конъюнкции или некоторые из них не содержат всех переменных (в прямом или инверсном виде), представляет собой дизъюнктивную нормальную форму (ДНФ) функции.

Логическую функцию можно составить не только по единичным, но и по нулевым значениям. Из табл.2.4 следует, что на наборах №№0, 4, 5, 7 у =0. Чтобы на каждом указанном наборе имело место у=0, нулю должна равняться дизъюнкция переменных из этого Набора, т.е. каждое слагаемое дизъюнкции; если в данном наборе переменная равна единице, то в дизъюнкцию должна входить ее инверсия. На всех указанных наборах функция из табл.2.4 будет равна 0, если осуществить конъюнкцию составленных дизъюнкций:

. (2.10)

Здесь у =0 обеспечивают: первый сомножитель при (при х₃=x₂=х₁=1, т. е. на наборе № 0), второй сомножитель при (при х₃=0; x₂=х₁=1, т. е. на наборе № 4), третий сомножитель при (при х₃=х₁=0; х₂ =1, т. е. на наборе № 5), четвертый сомножитель при х₃=х₂=х₁=0, т.е. на наборе № 7.

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

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

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