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

 

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

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

Таблица 14

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

b а	0	1
0	0	0
1	0	1	с=аÙb

 

Таким образом, конъюнкция – это операция В²aВ, где В – двухэлементное множество {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) видно, что столбец функции является инверсным столбецу х₃, т.е. , от х₂, х₃ – z не зависит!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

Решить логическое уравнение– значит, определить значения переменных, при которых соответствующая ПФ=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

 

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₂).