Пример 1. 1.1.5 Оценка сообщений с позиций алгебры логики

Алгебра логики – это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания. Создателем алгебры логики (ХIХ век) считается английский математик Джордж Буль, в честь которого эта алгебра названа булевой.

Логическим высказыванием называют любое сообщение, в отношении которого однозначно известно, истинно оно или ложно. Так, например, о сообщении «Белый гриб съедобен» можно сказать, что оно истинное высказывание. Сообщение «Все грибы съедобны» – пример ложного высказывания. Таким образом, алгебра логики по существу двузначна.

Высказывания, образованные из других высказываний с помощью логических связок («и», «или», и др.), называются сложными или составными. Высказывания, не являющиеся составными, называются элементарными. Например, высказывания «Три – число нечетное» и «Три – число простое» являются элементарными, тогда как высказывание «Три – число нечетное и простое» – составное. В последнем высказывании союз «и» употребляется как логическая связка

Если сложное высказывание истинно для всех значений входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией. Тавтологиями являются все математические законы, например: истинно для любых a и b.

Если сложное высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным.

Если значения сложных высказываний совпадают при всех возможных значениях входящих в них переменных, то такие высказывания называют равносильными, тождественными или эквивалентными.

Упрощение сложных высказываний – это замена высказывания на равносильное ему на основе законов алгебры высказываний.

В информатике вместо термина «логическая связка» принято употреблять термин «логическая операция» или «булева операция». Логическая (булева) операция, как и логическая связка выражает истинность или ложность информации в составном сообщении.

Рассмотрим действие основных логических операций, принимая в булевом контексте, что 0 – представляет значение «ложь», а 1 – логическое значение «истина».

1) Операция AND - конъюнкция (лат. conjunctio – соединение), логическое умножение. Обозначается символом Ù.

Она реализует следующую конструкцию логического высказывания: «результат операции будет истинным только в том случае, если оба входных сообщения истины»:

1Ù1=1;

1Ù0=0;

0Ù1=0;

0Ù0=0.

2) Операция OR – дизъюнкция (лат. disjunctio – разделение). Обозначается символом Ú.

Реализует словесную конструкцию: «результат будет истинным, если истинно хотя бы одно из входных сообщений»:

1Ú1=1;

1Ú0=1;

0Ú1=1;

0Ú0=0.

3) Операция NOT – логическое отрицание. Обозначается символом Ø.

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

.

4) Операция XOR – исключающее ИЛИ. Обозначается символом Ä.

Реализует конструкцию «результат будет истинным, если истинно либо то, либо другое из входных значений, но не оба одновременно», например:

1Ä1=0;

1Ä0=1;

0Ä1=1;

0Ä0=0.

5) Импликация (лат. implico – тесно связаны). Обозначается символом ®.

Выражается в конструкциях: “ если..., то ”, “ из... следует ”, “ ... влечет... ”. Например, «из A следует B», «если верно сообщение А, то верно и В», «наступление события А влечет наступление события В»:

A ® B.

Импликация двух высказываний ложна тогда и только тогда, когда из истинного высказывания следует ложное (истинная предпосылка ведет к ложному выводу):

1®1=1;

1®0=0;

0®1=1;

0®0=1.

6) Эквиваленция (или двойная импликация). Обозначается символом «или ~.

Выражается высказываниями типа “ тогда и только тогда ”, " необходимо и достаточно ”, “ равносильно ”. Например, «A равносильно B», «сообщение А, верно тогда и только тогда, когда верно В (и наоборот)», «для наступления события А необходимо и достаточно наступления события В»:

A«B.

Эквивалентность двух высказываний истинна, тогда и только тогда, когда оба эти высказывания истинны, или оба ложны:

1«1=1;

1«0=0;

0«1=0;

0«0=1.

Из приведенных шести операций основными считаются три: конъюнкция, дизъюнкция и отрицание. Через них в принципе можно выразить остальные три, например операция импликации выражается через отрицание и дизъюнкцию:

A ® B =Ø А Ú В.

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

A«B=(A ÙB) Ú(A ÙB);

A «B =(A ÚB) Ù(A ÚB).

Порядок выполнения логических операций задается круглыми скобками. Иначе порядок действий следующий: сначала выполняется операция отрицания (NOT), затем конъюнкция (AND), после конъюнкции – дизъюнкция (OR или XOR) и в последнюю очередь – импликация и эквиваленция.

Рассмотрим пример сложного логического высказывания: АÚ(B→C) ÙD «Ø(A)

Порядок выполнения:

1) Ø(А) – инверсия;

2) В → С – импликация;

3) (В → С) ÙD – конъюнкция;

4) А Ú(B → C) ÙD – дизъюнкция;

5) А Ú(B → C) ÙD = не(A) – эквивалентность.

1.1.6 Основные законы равносильности алгебры логики