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

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

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

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

где значок Примеры составления логических функций. - student2.ru - символизирует функцию «Неравнозначность».

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

Рис.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 из набора №1 ИЛИ из набора №2 ИЛИ из набора №3 ИЛИ из набора №6, приведенные в табл.2.4. Если на каждом перечисленном наборе конъюнкция сигналов будет равна лог.1, то на выходе устройства будет сигнал высокого уровня (U1).

Таким образом, функция, представленная табл.2.4, запишется в виде Примеры составления логических функций. - student2.ru , (2.9)

где сигналы х123, инвертированы, если они в соответствующих наборах равны лог.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, если осуществить конъюнкцию составленных дизъюнкций:

Примеры составления логических функций. - student2.ru . (2.10)

Здесь у =0 обеспечивают: первый сомножитель при Примеры составления логических функций. - student2.ru (при х3=x21=1, т. е. на наборе № 0), второй сомножитель при Примеры составления логических функций. - student2.ru (при х3=0; x21=1, т. е. на наборе № 4), третий сомножитель при Примеры составления логических функций. - student2.ru (при х31=0; х2 =1, т. е. на наборе № 5), четвертый сомножитель при х321=0, т.е. на наборе № 7.

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

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

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

Наши рекомендации