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

Алгебра логики — раздел математики, в котором изучаются логические операции, осуществляемые над доступными объектами высказываниями. 

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

Основателем алгебры логики был английский математик XIX века Джордж Буль. В 1854 году он опубликовал научную работу «исследование законов мышления». Как раз эта работа положила начало новому разделу математики и теперь алгебру логики часто называют булевой алгеброй. 

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

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

Определение

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

Рассмотрим конъюнкцию подробно.

Пусть аргументы обозначенные как А и B. Так как каждый аргумент может принимать только два значения — ложь (ноль) или истина (единица), то всего возможно 4 комбинации:

•       оба высказывания ложны;
•       одно высказывание ложно, а второе истина;
•       оба высказывания истинны.

Эти комбинации удобно представить в виде таблицы, которая называется таблицей истинности. Каждой комбинации соответствует свое значение произведения высказывания А и B в согласии с определением.

Для обозначения конъюнкции используется различные символы — ∧, &, русская буква И.

Определение

Дизъюнкция (логическое сложение) — выражение истинно, когда хотя бы одно из высказываний истина.

Обозначение V, английский союз or, русское ИЛИ

Определение

Инверсия (отрицание) — меняющая ложь на истину и истину на ложь.

По определению инверсия 0 есть единица, а инверсия единицы есть ноль.

 = 1 и  = 0

Обозначение —

Приоритет логических операций

При выполнении действия со сложными логическими выражениями большую роль играет их порядок:

1.       действие в скобках;
2.       инверсия;
3.       конъюнкция;
4.       дизъюнкция.

Построение таблиц истинности сложных логических выражений

Пример 1

Постройте таблицу истинности для выражения

 ^A

Данное выражение содержит два высказывания, две логические переменные, обозначенные как A и B.  Каждое из высказываний может принимать лишь два значения 0 или 1.

Существуют только 4 комбинации значений A и B. Эти комбинации перечисляем в первых двух столбиках таблицы истинности. Каждый следующий столбик таблицы — это результат одного из действий, одной из операций, порядок которых определяется правилами приведенными ранее. Каждая операция подписана в верхней ячейке столбика. Сначала выполняется дизъюнкция переменных A и B, затем результат дизъюнкции инвертируется далее выполняется конъюнкция результатов инверсии и переменной А. Так как это действие завершающее, то результат конъюнкции и будет ответом.

Пример 2

Постройте таблицу истинности для выражения

A^BV

В представленном выражении 3 логические переменные A, B и C. Каждая из них может принимать два значения — ложь (ноль) или истина (единица). Тогда возможно всего 8 комбинаций значений логических переменных. Все они приведены в первых трех столбцах таблицы истинности. Порядок действий будет следующий:

•       Сначала выполняется конъюнкция переменных A и B.
•       Далее выполняется инверсия значений переменной C. Все нули из третьего столбца поменялись на единицы и все единицы на нули.
•       Третьим действием выполняется дизъюнкция результатов двух предыдущих логических действий.