Логические выражения и логические операции над высказываниями

1 2 3 4 5 6 7

Лекция 4. Булевая алгебра. Алгебра логики

План лекции

4.1. Понятие высказывания. Простое и составное высказывание

4.2. Логические выражения и логические операции над высказываниями

4.3. Равносильность логических операций.

4.4. Формулы алгебры логики. Функции алгебры логики

4.5. Формы представления высказываний

4.6. Полнота системы булевых функций

4.7. Минимизация высказываний методом Квайна

Понятие высказывания. Простое и составное высказывание

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

Основным объектом логики высказываний служат простые высказывания.

Определение. Высказывание — это повествовательное предложение, выражающее суждение. Если суждение, составляющее содержание (смысл) некоторого высказывания, истинно, то и о данном высказывании говорят, что оно истинно. В противном случае, если суждение, составляющее содержание некоторого высказывания, ложно, то и о данном высказывании говорят, что оно ложно.

Истинность и ложность называются логическими, или истинностными, значениями высказываний.

ПРИМЕРЫ.

1. Число 100 делится на 5. (Истина)

2. Число 3 больше числа 5. (Ложь)

3. Сегодня светит солнце. (Не является высказыванием)

4. Вечером мы пойдем в кино. (Не является высказыванием)

5. Я лгу. (Не является высказыванием)

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

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

Логические выражения и логические операции над высказываниями

Определение. Логическое выражение – это символическая запись, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками).

В булевой алгебре простым высказываниям ставятся в соответствие логические переменные, значение которых равно 1, если высказывание истинно, и 0, если высказывание ложно. Обозначаются логические переменные буквами латинского алфавита A, B, C, …, X, Y,Z. Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение. Действия логических операций будем представлять в виде таблиц истинности.

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

Логические операции:

1. Операция «НЕ»: Операция, выражаемая словом «не», называется инверсией (отрицанием) и обозначается чертой над высказыванием (знаком Ø, либо ¢).

Высказывание истинно, когда A ложно, и ложно, когда A истинно.

ПРИМЕР.

А: 7 делится на 5 без остатка.

Ø А: Неверно, что 7 делится на 5 без остатка.

А	Ø А
0	1
1	0

Эта таблица и принимается в качестве определения операции отрицания.

2. Операция «И»: Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой «^.» (может также обозначаться знаками или &).

Высказывание А × В истинно тогда и только тогда, когда оба высказывания А и В истинны.

ПРИМЕРЫ:

A. 6 делится на 3 без остатка (1);

B. 10 больше 5 (1);

C. 7 делится на 3 без остатка (0);

D. 3 больше 7 (0);

A&B =1

A&C =0

C&D =0

А	В	А&В
0	0	0
0	1	0
1	0	0
1	1	1

Эта таблица и принимается в качестве определения операции конъюнкции

3. Операция «ИЛИ» Операция, выражаемая связкой «или» (в не исключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком .

Высказывание А В ложно тогда и только тогда, когда оба высказывания А и В ложны.

ПРИМЕРЫ:

A. 6 делится на 3 без остатка (1);

B. 10 больше 5 (1);

C. 7 делится на 3 без остатка (0);

D. 3 больше 7 (0);

A B=1

A D=1

C D=0

А	В	А В
0	0	0
0	1	1
1	0	1
1	1	1

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

4. Операция «Исключающее ИЛИ» (Операция неравнозначности (равноименности) «строгая дизъюнкция», «сумма по модулю два»,). Строгой дизъюнкцией высказываний А и В называется высказывание, которое истинно тогда и только тогда, когда истинно только одно из этих высказываний. Обозначается знаком .

А	В	А В
0	0	0
0	1	1
1	0	1
1	1	0

5. Операция «ЕСЛИ-ТО»: Операция, выражаемая связками «если..., то», «из... следует», «... влечет...», называется импликацией (лат. implico — тесно связаны) или логическим следованием и обозначается знаком . Высказывание ложно тогда и только тогда, когда А истинно, а В ложно. Высказывание А называется антецедентом, а В – консеквентом.

А	В	А В
0	0	1
0	1	1
1	0	0
1	1	1

6. Операция «РАВНОСИЛЬНО»: Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «... равносильно...», называется эквиваленцией или двойной импликацией, или логическим тождеством и обозначается знаком или ~,или .

Высказывание истинно тогда и только тогда, когда значения А и В совпадают.

А	В	А~В
0	0	1
0	1	0
1	0	0
1	1	1

7. Обратная конъюнкция И – НЕ (Штрих Шеффера ê )

А	В	А ê В
0	0	1
0	1	1
1	0	1
1	1	0

8. Обратная дизъюнкция ИЛИ – НЕ (Стрелка Пирса , функция Вебба)

А	В	А В
0	0	1
0	1	0
1	0	0
1	1	0

Используя эти логические операции можно строить сколь угодно сложные высказывания. Приоритет выполнения операций: ⌐ & Ú ~ ê

ПРИМЕР. Сложное высказывание: «Если вы не пропускаете занятия и успешно занимаетесь, то Вы сдадите экзамен хорошо» можно записать следующим образом. Обозначим:

П – пропускаете занятия;

Y – успешно занимаетесь;

Х – сдадите экзамен хорошо,

тогда все высказывание запишется:

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

ПРИМЕР.

Пусть A=1, B=0, C=0, D=1. Подставим эти значения в высказывание и получим:

Символы ⌐ & Ú ~ ê называются пропозициональными связками,

А, В, С, … и т.д. – пропозициональными переменными.

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

ПРИМЕР.

Определить значение истинности составного высказывания

D=А&(А&В ) &В