Главная Обратная связь

Дисциплины:






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



 

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

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

Таким образом, функция, представленная табл.2.4, запишется в виде , (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, если осуществить конъюнкцию составленных дизъюнкций:

. (2.10)

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

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

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

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

 

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

 

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

Пример 2.9. Упростить выражение (2.9).

Решение. Используя закон склеивания для первого и третьего членов, и для второго и четвертого, а также одно из тождеств алгебры логики получим:

=

= .

Полученное выражение равносильно исходному, но намного проще его.

Пример 2.10. Пусть имеется логическая функция . Требуется минимизировать ее.

Решение. Добавим дважды к правой части функции уже имеющийся член х321 (отчего функция не изменится); тогда

=

= .

Это выражение значительно проще исходного.

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

 

 





sdamzavas.net - 2018 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...