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

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

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

• Переместительные (коммутативные) законы: \( 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) \).
• Законы идемпотентности: \( A \& A = A \) и \( A \lor A = A \).
• Закон противоречия: \( A \& \overline{A} = 0 \) (ложь).
• Закон исключённого третьего: \( A \lor \overline{A} = 1 \) (истина).
• Закон двойного отрицания: \( \overline{\overline{A}} = A \).
• Законы работы с константами: \( A \lor 1 = 1 \), \( A \lor 0 = A \), \( A \& 1 = A \), \( A \& 0 = 0 \).
• Законы де Моргана: \( \overline{A \& B} = \overline{A} \lor \overline{B} \) и \( \overline{A \lor B} = \overline{A} \& \overline{B} \).
• Законы поглощения: \( A \& (A \lor B) = A \) и \( A \lor (A \& B) = A \).

Аналогичные законы справедливы и для операций над множествами: объединения \( (\cup) \), пересечения \( (\cap) \) и дополнения \( (\overline{A}) \). Законы алгебры логики могут быть доказаны с помощью таблиц истинности.

Примеры применения законов и решение задач

На страницах учебника представлены примеры, демонстрирующие, как использовать эти законы для упрощения сложных логических выражений. Например, импликация \( A \to B \) может быть заменена на эквивалентное выражение \( \overline{A} \lor B \). Это преобразование часто используется для упрощения выражений, включающих импликацию, прежде чем применять другие законы, такие как законы де Моргана. При работе с битовыми операциями (поразрядная конъюнкция \(\& \)) введены обозначения предикатов, и логическое выражение преобразуется, чтобы найти наименьшее число, удовлетворяющее условию тождественной истинности.

Составление логического выражения по таблице истинности

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

1. Отметить в таблице истинности те наборы значений переменных, при которых логическая функция \( F \) принимает значение 1 (истина).
2. Для каждого такого набора составить конъюнкцию (логическое «И») всех переменных. При этом переменная включается в конъюнкцию в прямом виде, если её значение в наборе равно 1, и в инверсном (с отрицанием \( \overline{A} \)), если её значение равно 0.
3. Все полученные конъюнкции связываются операцией дизъюнкции (логическое «ИЛИ»).

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

Решение систем логических уравнений

В учебнике также рассматривается решение систем логических уравнений. Решение такой системы — это набор значений переменных, при подстановке которого все уравнения системы становятся истинными. Для первого уравнения \( (x_1 \to x_2) \& (x_2 \to x_3) \& (x_3 \to x_4) = 1 \) строится «дерево решений», которое позволяет найти все наборы значений, удовлетворяющие уравнению. Для системы из двух уравнений, каждое из которых имеет 5 решений, общее количество решений равно произведению числа решений каждого уравнения (5 * 5 = 25).

Логические функции

Логическое выражение представляет собой логическую функцию. Совокупность значений \( n \) аргументов (переменных) удобно представлять в виде двоичной строки длиной \( n \). Общее количество различных булевых функций от \( n \) аргументов равно \( 2^{2^n} \). Например, для \( n=2 \) существует \( 2^{2^2} = 16 \) различных логических функций, которые подробно перечислены в тексте (например, \( F_0 \) — константа «ложь», \( F_7 \) — дизъюнкция, \( F_{15} \) — штрих Шеффера, \( F_{16} \) — константа «истина»).