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

Конъюнкцией называется бинарная логическая операция, соединяю-щая две двоичных переменных а и b, принадлежащих множеству {0,1}, в такую переключательную функцию с, которая равна 1 (истинна) только тогда, когда равны 1 (истинны) обе переменных. Операция конъюнкции обозначается символом  (&) или просто «×». В ряде случаев точку также опускают.
Конъюнкция может быть представлена таблицей, подобной таблице Кэли для абстрактных алгебраических операций, называемой двухмерной таблицей истинности:
Таблица 14
Бинарная конъюнкция
   b
а 0 1
0 0 0
1 0 1 с=аÙb

Таким образом, конъюнкция – это операция В2aВ, где В – двухэле-ментное множество {0,1}, где 0,1 – значения истинности переменных. Известна также другая форма таблицы истинности – одномерная:
Таблица 15
Бинарная конъюнкция
а b с=аÙb
0 0 0
0 1 0
1 0 0
1 1 1

Конъюнкция n переменных истинна тогда и только тогда, когда все составляющие ее переменные истинны (равны 1).
Логическая операция, соответствующая союзу «или» в неразделительном смысле, называется дизъюнкцией (disjunctio – «разделение»). Пример дизъюнкции: «На экзамене по дискретной ма-тематике я получу 5 или 4».
Дизъюнкцией называется логическая операция, соединяющая две пе-ременные а и b в такую переключательную функцию с, которая равна 0 (ложна) только тогда, когда ложны обе переменные (равны 0).
Дизъюнкция обозначается символом Ú.
В латыни союзу «или» в неразделительном смысле соответствует слово vel. Символ Ú происходит от первой буквы этого слова.
Таблица истинности дизъюнкции (одномерная) имеет вид табл. 16.
Таблица 16
Бинарная дизъюнкция
а b с=аÚb
0 0 0
0 1 1
1 0 1
1 1 1

Дизъюнкция n переменных ложна тогда и только тогда, когда все со-ставляющие ее переменные ложны.
Логическая операция, соответствующая частице «не», словосочетанию «неверно, что», называется инверсией. Пример инверсии: «Студент Петров не отличник», «Неверно, что студент Иванов является спортсменом».
Инверсией называется переключательная функция, полученная отри-цанием данной ПФ.
Инверсию а обозначают  , используя знак дополнения множеств.
Таблица истинности унарной операции инверсии ВaВ имеет вид табл. 17.
Таблица 17
Бинарная инверсия
а

0 1
1 0

Логическая операция, соответствующая союзу «если...то», называется импликацией.
Примеры импликации: «Если вы будете хорошо заниматься в семестре, то сдадите экзамен по дискретной математике».
Импликацией называется логическая операция, соединяющая две переменных а и b в такую переключательную функцию с, которая равна 0 (ложна) только тогда, когда а истинно, а b ложно.
Импликация обозначается символом ®.
Таблица истинности импликации имеет вид табл. 18.
Таблица 18
Импликация
а b с=а®b
0 0 1
0 1 1
1 0 0
1 1 1

Приведенное выше высказывание преподавателя будет расценено студентами как ложь, если они действительно хорошо занимались в семестре, а на экзамене получили неудовлетворительные оценки.
Логическая операция, соответствующая союзу «тогда и только тогда, когда», называется эквиваленцией (эквивалентностью).
Пример эквиваленции (эквивалентности): «Я поеду к морю тогда и только тогда, когда сдам экзамен по дискретной математике».
Эквиваленцией (эквивалентностью) называется логическая операция, соединяющая две переменных в такую ПФ, которая истинна тогда, когда обе образующих ее переменных одновременно истинны или одновременно ложны. Эквиваленция обозначается символом «.
Таблица истинности эквиваленции имеет вид табл. 19.
Таблица 19
Эквиваленция
а b с=а«b
0 0 1
0 1 0
1 0 0
1 1 1

Далее мы познакомимся с другими логическими операциями, которым нет простого эквивалента в разговорной речи, например, суммой по модулю 2 (исключающее ИЛИ).
Заметим, что операции могут быть выражены через другие операции, например, импликация а®b может быть представлена в виде  , что может быть доказано построением соответствующих таблиц истинности.
Область определения ПФ n переменных – множество всех возможных наборов длины n при матричном задании ПФ, а при геометрическом способе задания – множество всех вершин n-мерного куба.
Переключательную функцию, определенную на всех своих наборах, называют полностью определенной. Вырожденные функции зависят не от всех переменных.
Например, для бинарной ПФ: вырожденная ПФ (табл. 20) – такая функция, которая зависит не от всех n переменных.
                Таблица 20
Вырожденная ПФ
BC z
x3 х2 x1   
0 0 0 0 1
0 0 1 1 1
0 1 0 2 1
0 1 1 3 1
1 0 0 4 0
1 0 1 5 0
1 1 0 6 0
1 1 1 7 0

Из таблицы (см. табл. 20) видно, что столбец функции является ин-версным столбецу х3, т.е.  , от х2, х3 – z не зависит!
Двоичные ПФ описывают элементную базу электронной вычислительной техники и устройств автоматики и телемеханики – комбинационные и последовательностные автоматы, которые будут рассмотрены в дальнейшем.
Итак, основные двоичные логические операции:
1) дизъюнкция  («ИЛИ»);
2) конъюнкция & («И»);
3) инверсия или отрицание  («НЕ»);
4) импликация  («ЕСЛИ, ТО»);
5) эквиваленция  («ТОГДА И ТОЛЬКО ТОГДА, КОГДА»).
Кроме того, имеется операция:
6) сумма по модулю 2  («НЕВЕРНО, ЧТО ТОГДА И ТОЛЬКО ТО-ГДА, КОГДА» «ИЛИ-ИЛИ»).
Имеются также специальные операции:
7) стрелка Пирса  («ИЛИ-НЕ»);
8) штрих Шеффера(«И-НЕ») и др.
Алгебра, несущим множеством которой является множество ПФ, а операциями – дизъюнкция, конъюнкция и инверсия, называется булевой алгеброй ПФ.
ПФ можно описать некоторые условия, например, равенства (неравенства) некоторых битов, значения отдельных битов 0 или 1, например:
,
означает, что бит a1 должен быть равен нулю и при этом биты a2 и a3 равны.
Решить логическое уравнение – значит, определить значения переменных, при которых соответствующая ПФ=1 (истинна), где 1 – константа.
Решить систему логических уравнений – значит определить значения переменных, при которых соответствующая ПФ=1.
Пример. Дана таблица истинности для трех ПФ (табл. 21).
Таблица 21
Таблица истинности трех ПФ

ВС z1 z2 z3
a3 a2 a1       
0 0 0 0 1 0 1
0 0 1 1 0 1 0
0 1 0 2 0 1 0
0 1 1 3 0 0 1
1 0 0 4 0 1 0
1 0 1 5 0 0 1
1 1 0 6 1 0 1
1 1 1 7 0 1 0

z1=0,6[1,2,3,4,5,7],
z2=1,2,4,7[0,3,5,6]=a1a2a3=1,
z3=0,3,5,6[1,2,4,7].
Здесь указаны номера наборов, на которых ПФ равны единице. Это так называемая символическая форма задания ПФ (СФ ПФ).
Видно, что общих решений нет.
Если же взять:
,
то получим:
z2=0,3,5,6[1,2,4,7], т.е.
решение системы z1,z2,z3=0,6.
Если же в уравнении указывается равенство с другой переменной или функцией, то, как мы уже знаем из теории множеств:
a1a2a3=a3, a1a2a3a3=0, a1a2=0.
Решение: 01,10 (a1a2).