Элементы алгебры логики

Учебное пособие: Элементы алгебры логики

1. Основные понятия и теоретические основы

1.1. Высказывание и логические переменные

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

• Высказывание — это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.
• Примеры истинных высказываний: «Na — металл», «3 + 5 = 2 · 4», «Великий русский учёный М.В. Ломоносов родился в 1711 году».
• Примеры ложных высказываний: «Зимой воробьи впадают в спячку», «II + VI > VIII».

Что НЕ является высказыванием:

1. Побудительные и вопросительные предложения: («Запишите домашнее задание», «Как пройти в библиотеку?»).
2. Субъективные суждения и оценки: («Компьютерная графика — самая интересная тема в курсе школьной информатики»).
3. Парадоксы: («Это предложение является ложным» — принятие его истинности или ложности приводит к противоречию).
4. Числовые выражения без знаков равенства/неравенства: (например, $4X + 3$).
5. Предложения с переменными (уравнения, неравенства с переменной): Равенства или неравенства вида $X < 12$ становятся высказываниями только при подстановке конкретного значения переменной. Множество значений переменной, при которых получаются истинные высказывания, называется областью истинности предложения с переменной.

Обозначения и значения:

Алгебра логики отвлекается от смысловой содержательности высказываний и рассматривает только их истинность или ложность.

• Высказывания обозначаются буквами и называются логическими переменными ($A, B, C...$).
• Истинному высказыванию соответствует логическое значение $1$ ($A = 1$).
• Ложному высказыванию соответствует логическое значение $0$ ($B = 0$).

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

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

Название логической операции · Алгебраическое название · Логическая связка в естественном языке · Используемые знаки и обозначения

• Инверсия — Логическое отрицание; «не», «неверно, что»; $\overline{A}$, $\neg A$, $-A$, $НЕ\ A$
• Конъюнкция — Логическое умножение; «и», «а», «но», «хотя»; $A \& B$, $A \wedge B$, $A \cdot B$, $A \times B$, $A\ И\ B$
• Дизъюнкция — Логическое сложение; «или»; $A \lor B$, $A \mid B$, $A + B$, $A\ ИЛИ\ B$

Определения и таблицы истинности базовых операций:

• Инверсия — логическая операция, которая высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному.
• При построении отрицания используется оборот «неверно, что...» либо частица «не» при сказуемом.

$A$ · $\overline{A}$

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

$A$ · $B$ · $A \& B$

• 0 — 0; 0
• 0 — 1; 0
• 1 — 0; 0
• 1 — 1; 1
• Дизъюнкция — логическая операция, которая двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны.

$A$ · $B$ · $A \lor B$

• 0 — 0; 0
• 0 — 1; 1
• 1 — 0; 1
• 1 — 1; 1

1.3. Логические выражения и приоритет операций

Логическое выражение — выражение, содержащее логические переменные, знаки логических операций и скобки.

При отсутствии скобок операции выполняются в соответствии с их приоритетом:

1. Инверсия ($\overline{A}$)
2. Конъюнкция ($\&$)
3. Дизъюнкция ($\lor$)

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

1.4. Правила построения таблиц истинности

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

Алгоритм построения:

1. Подсчитать $n$ — число переменных в выражении.
2. Подсчитать общее число логических операций в выражении.
3. Установить последовательность выполнения операций с учётом скобок и приоритетов.
4. Определить число столбцов: $\text{число столбцов} = \text{число переменных} + \text{число операций}$.
5. Заполнить шапку таблицы (переменные и операции в установленном порядке).
6. Определить число строк в таблице (без шапки): $m = 2^n$.
7. Выписать наборы входных переменных (целые $n$-разрядные двоичные числа от $0$ до $2^n - 1$ в порядке возрастания).
8. Заполнить таблицу по столбцам, выполняя логические операции по шагам.

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

1.5. Законы алгебры логики (Свойства логических операций)

Название закона · Для логического умножения (конъюнкции) · Для логического сложения (дизъюнкции)

• Переместительный (коммутативный) — $A \& B = B \& A$; $A \lor B = B \lor A$
• Сочетательный (ассоциативный) — $(A \& B) \& C = A \& (B \& C)$; $(A \lor B) \lor C = A \lor (B \lor C)$
• Распределительный (дистрибутивный) — $A \& (B \lor C) = (A \& B) \lor (A \& C)$; $A \lor (B \& C) = (A \lor B) \& (A \lor C)$
• Двойного отрицания — $\overline{\overline{A}} = A$; $\overline{\overline{A}} = A$
• Исключённого третьего — $A \& \overline{A} = 0$; $A \lor \overline{A} = 1$
• Повторения — $A \& A = A$; $A \lor A = A$
• Операций с 0 и 1 — $A \& 0 = 0$; $A \& 1 = A$; $A \lor 0 = A$; $A \lor 1 = 1$
• Общей инверсии (законы де Моргана) — $\overline{A \& B} = \overline{A} \lor \overline{B}$; $\overline{A \lor B} = \overline{A} \& \overline{B}$

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

1.6. Логические элементы

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

1. Конъюнктор (элемент И): реализует операцию логического умножения ($\&$). Единица на выходе появляется только тогда, когда на всех входах действуют единицы.
2. Дизъюнктор (элемент ИЛИ): реализует операцию логического сложения ($1$). Единица на выходе появляется, если хотя бы на одном входе присутствует единица.
3. Инвертор (элемент НЕ): реализует операцию отрицания. Инвертирует сигнал ($0 \to 1$, $1 \to 0$).

2. Вопросы для проверки знаний (Quiz)

Вопросы

1. Что такое высказывание в алгебре логики?
2. Какие типы предложений естественного языка не могут являться высказываниями?
3. Что такое область истинности предложения с переменной?
4. При каких значениях операндов конъюнкция двух высказываний дает результат «истина» ($1$)?
5. В каком случае дизъюнкция двух высказываний ложна ($0$)?
6. Укажите стандартный порядок (приоритет) выполнения логических операций при отсутствии скобок.
7. Какая формула используется для расчета количества строк в таблице истинности для выражения, содержащего $n$ переменных?
8. Сформулируйте закон исключённого третьего для логического сложения и для логического умножения.
9. Чему равны значения выражений $A \lor 1$ и $A \& 0$?
10. Какие логические элементы являются базовыми для построения электронных схем?

Ответы для самопроверки

1. Высказывание — это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.
2. Вопросительные предложения, побудительные предложения, предложения с субъективными оценками/мнениями, а также логические парадоксы.
3. Область истинности — это множество всех тех значений переменной, при подстановке которых предложение с переменной превращается в истинное высказывание.
4. Конъюнкция истинна ($1$) тогда и только тогда, когда оба исходных высказывания истинны ($1$).
5. Дизъюнкция ложна ($0$) тогда и только тогда, когда оба исходных высказывания ложны ($0$).
6. 1) Инверсия, 2) Конъюнкция, 3) Дизъюнкция.
7. $m = 2^n$ (не считая строки с шапкой таблицы).
8. Для логического сложения: $A \lor \overline{A} = 1$. Для логического умножения: $A \& \overline{A} = 0$.
9. $A \lor 1 = 1$; $A \& 0 = 0$.
10. Конъюнктор (логический элемент И), дизъюнктор (логический элемент ИЛИ) и инвертор (логический элемент НЕ).

3. Вопросы для размышления и эссе

1. Фундаментальное значение алгебры логики в вычислительной технике.

• Направление анализа: Рассмотрите, каким образом абстрагирование от смыслового содержания высказываний и сведение логических значений к двоичным кодам ($0$ и $1$) позволило применить аппарат алгебры логики к разработке электронных схем, хранению и обработке информации в компьютерах.

2. Проблема определения истинности высказываний в формальных и естественных языках.

• Направление анализа: Объясните, почему естественный язык допускает создание предложений, не являющихся высказываниями (вопросы, призывы, парадоксы), и как формализация языка (математическая, химическая, физическая символика) позволяет однозначно разграничивать истинные и ложные утверждения.

3. Сравнительный анализ способов решения логических задач.

• Направление анализа: Сопоставьте метод построения таблиц истинности, алгебраические преобразования (с использованием законов логики) и использование диаграмм (кругов Эйлера). Проанализируйте преимущества и ограничения каждого метода при решении практических задач.

4. Глоссарий терминов

• Алгебра логики — Раздел математики, изучающий высказывания и правила выполнения над ними операций, аналогичных сложению и умножению.
• Высказывание — Предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.
• Дизъюнктор — Логический элемент (схема ИЛИ), реализующий операцию логического сложения.
• Дизъюнкция — Логическая операция (логическое сложение), связывающая два высказывания с помощью союза «или» и дающая значение «ложь» только тогда, когда оба операнда ложны.
• Инвертор — Логический элемент (схема НЕ), реализующий операцию логического отрицания.
• Инверсия — Логическая операция (логическое отрицание), меняющая значение высказывания на противоположное.
• Конъюнктор — Логический элемент (схема И), реализующий операцию логического умножения.
• Конъюнкция — Логическая операция (логическое умножение), связывающая высказывания союзом «и» и дающая значение «истина» только тогда, когда оба операнда истинны.
• Логический элемент — Дискретный преобразователь, выдающий после обработки двоичных сигналов значение одной из логических операций.
• Логическое выражение — Выражение, содержащее логические переменные, знаки логических операций и скобки.
• Логическая переменная — Переменная, обозначающая высказывание и принимающая только два значения: $0$ или $1$.
• Логическое значение — Обозначение истинности ($1$) или ложности ($0$) логической переменной.
• Область истинности — Множество значений переменной, при которых предложение с переменной становится истинным высказыванием.
• Простое высказывание — Высказывание, ни одна часть которого не является самостоятельным высказыванием.
• Равносильность логических выражений — Свойство двух логических выражений принимать одинаковые значения на всех возможных наборах входных переменных.
• Составное высказывание — Высказывание, образованное из простых высказываний с помощью логических операций.
• Таблица истинности — Таблица, показывающая, какие значения принимает логическое выражение при всех возможных наборах входящих в него переменных.