Краткое содержание: Параграф § 18 / Информатика 10 класс

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

Алгебра логики, или булева алгебра, является разделом математики, который исследует высказывания с точки зрения их логических значений – истинности или ложности – и логических операций, выполняемых над ними. Основоположником этой дисциплины считается Джордж Буль (1815–1864), английский математик. В 1938 году Клод Шеннон применил алгебру логики для описания функционирования релейно-контактных и электронно-ламповых схем.

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

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

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

Логическая переменная – это переменная, которая обозначает высказывание и может принимать только два логических значения: «истина» (1) или «ложь» (0). В различных обозначениях также используются: И (Истина) / Л (Ложь) или true / false.

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

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

Основные логические операции и их обозначения:

• Отрицание (Инверсия, НЕ): Обозначается \( \neg A \), \( \bar{A} \), \( \text{H}E \ A \). Истинно, когда исходное высказывание ложно.
• Конъюнкция (Логическое умножение, И): Обозначается \( A \land B \), \( A \cdot B \), \( A \ \& \ B \). Истинна тогда и только тогда, когда оба исходных высказывания истинны.
• Дизъюнкция (Логическое сложение, ИЛИ): Обозначается \( A \lor B \), \( A + B \). Ложна тогда и только тогда, когда оба исходных высказывания ложны.
• Строгая дизъюнкция (Исключающее ИЛИ): Обозначается \( A \oplus B \). Истинна тогда и только тогда, когда истинно ровно одно из исходных высказываний.
• Импликация (Логическое следование): Обозначается \( A \to B \), \( A \subset B \). Ложна только в одном случае: когда посылка \( A \) истинна, а следствие \( B \) ложно.
• Эквиваленция (Эквивалентность, Равнозначность): Обозначается \( A \leftrightarrow B \), \( A \equiv B \), \( A = B \). Истинна тогда и только тогда, когда логические значения обоих исходных высказываний совпадают.

Логические выражения

Составное логическое высказывание может быть записано в виде логического выражения (формулы). Логическое выражение состоит из логических констант (0, 1), логических переменных, знаков логических операций и скобок.

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

При вычислении логического выражения операции выполняются в следующем порядке приоритета (от высшего к низшему):

1. Отрицание.
2. Конъюнкция.
3. Дизъюнкция, строгая дизъюнкция.
4. Импликация, эквиваленция.

Операции одинакового приоритета выполняются слева направо. Скобки могут изменять порядок выполнения операций.

Логические уравнения и предикаты

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

Предикат – это утверждение, содержащее одну или несколько переменных. При замене переменной каким-либо конкретным значением, предикат превращается в высказывание.

Множество истинности предиката \( P(x) \) – это множество всех объектов, для которых предикат становится истинным высказыванием. Предикаты позволяют задавать множества.

Из имеющихся предикатов можно строить новые, используя логические операции. Если \( A \) и \( B \) – множества истинности предикатов \( A(x) \) и \( B(x) \), то:

• Пересечение \( A \cap B \) является множеством истинности для предиката \( A(x) \land B(x) \).
• Объединение \( A \cup B \) является множеством истинности для предиката \( A(x) \lor B(x) \).