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

Основоположником математической логики является английский математик XIX века Джордж Буль (George Boole), создавший алгебру логики (булеву алгебру), в которой переменные принимают не числовые значения, а логические: 1 (Истина, True) или 0 (Ложь, False).

Логическое высказывание — это повествовательное предложение на естественном языке, о содержании которого можно однозначно и объективно сказать, истинно оно или ложно в текущий момент.

Примеры высказываний:

• «Астана — столица Республики Казахстан» (Истинное высказывание, = 1);

• «Число 12 делится на 5 без остатка» (Ложное высказывание, = 0);

• «В байте ровно 8 бит» (Истинное высказывание, = 1).

НЕ являются высказываниями: вопросительные предложения («Который час?»), побудительные просьбы («Закрой окно!») и субъективные оценки («Этот фильм очень красивый»), так как для них нельзя однозначно определить истинность.

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

1. Логическое отрицание (Инверсия / НЕ / NOT, обозначается $\neg A$ или $\overline{A}$):

Меняет значение высказывания на противоположное: $\overline{0} = 1$, $\overline{1} = 0$;

2. Логическое умножение (Конъюнкция / И / AND, обозначается $A \land B$ или $A \cdot B$ или $A \& B$):

Истинно тогда и только тогда, когда оба высказывания истинны одновременно:

$0 \land 0 = 0, \;\quad 0 \land 1 = 0, \;\quad 1 \land 0 = 0, \;\quad 1 \land 1 = 1$;

3. Логическое сложение (Дизъюнкция / ИЛИ / OR, обозначается $A \lor B$ или $A + B$):

Истинно, если истинно хотя бы одно из высказываний (или оба):

$0 \lor 0 = 0, \;\quad 0 \lor 1 = 1, \;\quad 1 \lor 0 = 1, \;\quad 1 \lor 1 = 1$.

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

Шаги построения таблицы истинности:

1. Подсчитать количество переменных n в формуле;

2. Определить число строк таблицы по формуле $M = 2^n$ (для 2 переменных $M = 2^2 = 4$ строки, для 3 переменных $M = 2^3 = 8$ строк);

3. Подсчитать количество логических операций в формуле (число столбцов = переменные + операции);

4. Расставить приоритет действий: скобки → инверсия (¬) → конъюнкция (∧) → дизъюнкция (∨);

5. Заполнить входные наборы переменных перебором всех двоичных комбинаций (00, 01, 10, 11);

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

Для упрощения сложных логических выражений и оптимизации логических схем применяют законы де Моргана:

1. Отрицание конъюнкции: $\overline{A \land B} = \overline{A} \lor \overline{B}$

(«Неправда, что идет дождь И дует ветер» означает «Или дождь не идет, ИЛИ ветер не дует»);

2. Отрицание дизъюнкции: $\overline{A \lor B} = \overline{A} \land \overline{B}$

(«Неправда, что яблоко красное ИЛИ сладкое» означает «Яблоко НЕ красное И НЕ сладкое»).

Закон двойного отрицания: $\overline{\overline{A}} = A$.

Законы поглощения: $A \lor (A \land B) = A, \quad A \land (A \lor B) = A$.