3.1.1. Основные логические операции

Наиболее употребительными логическими операциями является логические операции отрицание, сложение и умножение. Они позволяют составить любую логическую функцию. Рассмотрим операцию отрицание. Если для множеством истинности является . То через обозначается высказывание с множеством истинности, заштрихованным на рисунке 3.1.а., функция (читается «не ») называется функцией НЕ, или инверсией. Из таблицы истинности, представленной на рисунке 3.1.б следует что и = 0. Изображается функция в виде логического элемента, называемого элементом НЕ, или инвертором представленного на рисунке 3.2 в.

Л огическое сложение обозначается знаком + или логическим символом V. Функция , имеет множество истинности и получила название функции ИЛИ (дизъюнкции). Диаграмма, соответствующая функции х+у, и таблица истинности приведены на рисунках 3.2, а, б.

С помощью диаграммы можно убедиться в справедливости следующего тождеств:

1) x+1=1, (x I=I),

2) x+0=x, (x =x),

3) + =1, ( I),

4) x+x=x (x x=x).

Из последнего тождества следует , что в функциях логического сложения отсутствуют коэффициенты.

Логический элемент (рисунок 3.2 в) называет элементом ИЛИ (лизъюнктором).

Логическое умножение соответствует операция пересечения множеств. Функция

.

Следующий - символ логического умножения, называется функцией И, или конъюнкцией. Множество истинности Х У и таблица истинности показаны на рисунках 3.3 а, б.

Для функции ху определены тождества:

1) x1=x (x I=x),

2) x0=0 (x ),

3) , (x x= ),

4) xx=x (x x=x).

Последнее тождество показывает, что в алгебре логики отсутствует возведение в степень.

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

Операции логического сложения и логического умножения возможны для трех и более переменных.

3.1.2. Законы и тождества алгебры логики

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

Приведем основные законы и тождества алгебры логики.

1) П ер е м е с т и т е л ь н ы й (коммутативный) закон:

ху = ух; х + у = у + х.

2) Со ч е та т е л ь н ы й (ассоциативный) закон:

xyz=x(yz)=(xy)z;

x+y+z=x+(y+z)=(x+y)+z.

3) Р а с п р е д е л и т е л ь н ы й ( дистрибутивный) закон:

конъюнкции относительно дизъюнкции –

x(y+z)=xy+xz;

дизъюнкции относительно конъюнкции –

x+yz=(x+y)(x+z).

4) Законы ин в е р с и и (законы де Моргана):

а) инверсия конъюнкций есть дизъюнкция инверсий-

б) инверсия дизъюнкций есть конъюнкция инверсий –

в) обобщение законов де Моргана, предложенное Шенноном -

т.е. инверсия любой функции получается заменой каждой переменной на инверсную с одновременной взаимной заменой символов конъюнкции.

5. формула (двойную инверсию можно снять).

6) При конъюнкции и некоторой функции соответствующие переменные в функции заменяются на 1, а инверсные – на 0, а при дизъюнкции – наоборот:

Из этих тождеств вытекает следующие равносильности, называемые законом поглощения:

a+ab=a; a+ab+ac+…+az=a;

a(a+b)=a; a(a+b)(a+c)…(a+z)=a.

7) Законы склеивания:

а) полного склеивания

б) неполного склеивания

в) обобщенного склеивания

8)

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

Пример 3.1 Преобразование логической функции:

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

В логических преобразованиях установлен следующий порядок выполнения операций:

1) инверсия;

2) конъюнкция;

3) дизъюнкция;

4) другие операции, соответствующие логическим функциям, которые будут рассмотрены ниже.

Скобки в логических выражениях проставляется для выделения отдельных сочетаний или для изменения установленного порядка преобразований.

Контрольные вопросы

1) Дайте определение логической функции, логической переменной

2) Как выполняется операция инверсии?

3) Как выполняется операция логического умножения или конъюнкция?

4) Как выполняется операция логического сложения или дизъюнкция?

5) Дайте определение основных законов алгебры логики?