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

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

Конъюнкция может быть представлена таблицей, подобной таблице Кэли для абстрактных алгебраических операций, называемой двухмерной таблицей истинности:

Таблица 14

Бинарная конъюнкция

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

Таблица 15

Бинарная конъюнкция

Конъюнкция n переменных истинна тогда и только тогда, когда все составляющие ее переменные истинны (равны 1).

Логическая операция, соответствующая союзу «или» в неразделительном смысле, называется дизъюнкцией (disjunctio – «разделение»). Пример дизъюнкции: «На экзамене по дискретной математике я получу 5 или 4».

Дизъюнкцией называется логическая операция, соединяющая две переменные а и b в такую переключательную функцию с, которая равна 0 (ложна) только тогда, когда ложны обе переменные (равны 0).

Дизъюнкция обозначается символом Ú.

В латыни союзу «или» в неразделительном смысле соответствует слово vel. Символ Ú происходит от первой буквы этого слова.

Таблица истинности дизъюнкции (одномерная) имеет вид табл. 16.

Таблица 16

Бинарная дизъюнкция

Дизъюнкция n переменных ложна тогда и только тогда, когда все составляющие ее переменные ложны.

Логическая операция, соответствующая частице «не», словосочетанию «неверно, что», называется инверсией. Пример инверсии: «Студент Петров не отличник», «Неверно, что студент Иванов является спортсменом».

Инверсией называется переключательная функция, полученная отрицанием данной ПФ.

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

Таблица истинности унарной операции инверсии ВaВ имеет вид табл. 17.

Таблица 17

Бинарная инверсия

Логическая операция, соответствующая союзу «если...то», называется импликацией.

Примеры импликации: «Если вы будете хорошо заниматься в семестре, то сдадите экзамен по дискретной математике».

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

Импликация обозначается символом ®.

Таблица истинности импликации имеет вид табл. 18.

Таблица 18

Импликация

Приведенное выше высказывание преподавателя будет расценено студентами как ложь, если они действительно хорошо занимались в семестре, а на экзамене получили неудовлетворительные оценки.

Логическая операция, соответствующая союзу «тогда и только тогда, когда», называется эквиваленцией (эквивалентностью).

Пример эквиваленции (эквивалентности): «Я поеду к морю тогда и только тогда, когда сдам экзамен по дискретной математике».

Эквиваленцией (эквивалентностью) называется логическая операция, соединяющая две переменных в такую ПФ, которая истинна тогда, когда обе образующих ее переменных одновременно истинны или одновременно ложны. Эквиваленция обозначается символом «.

Таблица истинности эквиваленции имеет вид табл. 19.

Таблица 19

Эквиваленция

Далее мы познакомимся с другими логическими операциями, которым нет простого эквивалента в разговорной речи, например, суммой по модулю 2 (исключающее ИЛИ).

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

Область определения ПФ n переменных – множество всех возможных наборов длины n при матричном задании ПФ, а при геометрическом способе задания – множество всех вершин n-мерного куба.

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

Например, для бинарной ПФ: вырожденная ПФ (табл. 20) – такая функция, которая зависит не от всех n переменных.

Таблица 20

Вырожденная ПФ

Из таблицы (см. табл. 20) видно, что столбец функции является инверсным столбецу х₃, т.е. , от х₂, х₃ – z не зависит!

Двоичные ПФ описывают элементную базу электронной вычислительной техники и устройств автоматики и телемеханики – комбинационные и последовательностные автоматы, которые будут рассмотрены в дальнейшем.

Итак, основные двоичные логические операции:

1) дизъюнкция  («ИЛИ»);

2) конъюнкция & («И»);

3) инверсия или отрицание («НЕ»);

4) импликация  («ЕСЛИ, ТО»);

5) эквиваленция  («ТОГДА И ТОЛЬКО ТОГДА, КОГДА»).

Кроме того, имеется операция:

6) сумма по модулю 2  («НЕВЕРНО, ЧТО ТОГДА И ТОЛЬКО ТОГДА, КОГДА» «ИЛИ-ИЛИ»).

Имеются также специальные операции:

7) стрелка Пирса  («ИЛИ-НЕ»);

8) штрих Шеффера(«И-НЕ») и др.

Алгебра, несущим множеством которой является множество ПФ, а операциями – дизъюнкция, конъюнкция и инверсия, называется булевой алгеброй ПФ.

ПФ можно описать некоторые условия, например, равенства (неравенства) некоторых битов, значения отдельных битов 0 или 1, например:

,

означает, что бит a₁ должен быть равен нулю и при этом биты a₂ и a₃ равны.

Решить логическое уравнение – значит, определить значения переменных, при которых соответствующая ПФ=1 (истинна), где 1 – константа.

Решить систему логических уравнений – значит определить значения переменных, при которых соответствующая ПФ=1.

Пример. Дана таблица истинности для трех ПФ (табл. 21).

Таблица 21

Таблица истинности трех ПФ

z₁=0,6[1,2,3,4,5,7],

z₂=1,2,4,7[0,3,5,6]=a₁a₂a₃=1,

z₃=0,3,5,6[1,2,4,7].

Здесь указаны номера наборов, на которых ПФ равны единице. Это так называемая символическая форма задания ПФ (СФ ПФ).

Видно, что общих решений нет.

Если же взять:

,

то получим:

z₂=0,3,5,6[1,2,4,7], т.е.

решение системы z₁,z₂,z₃=0,6.

Если же в уравнении указывается равенство с другой переменной или функцией, то, как мы уже знаем из теории множеств:

a₁a₂a₃=a₃, a₁a₂a₃a₃=0, a₁a₂=0.

Решение: 01,10 (a₁a₂).