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

Определение и назначение таблиц истинности

Таблица истинности представляет собой набор значений, которые принимает логическое выражение для всех возможных комбинаций (наборов) значений входящих в него логических переменных. Она является одним из основных инструментов в алгебре логики и информатике, используемым для определения истинности логической функции и доказательства эквивалентности логических выражений. Истинность логического выражения, то есть его значение (0 или 1), может быть доказана путем построения его полной таблицы истинности. Логическая функция от \( n \) переменных — это функция, аргументы и сама функция которой могут принимать только два значения: 0 (ложь) и 1 (истина).

Построение таблицы истинности

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

• Определить количество строк \( m \). Оно рассчитывается по формуле \( m = 2^n \), где \( n \) — это количество логических переменных в выражении. К этому количеству добавляется одна строка для заголовков.
• Определить количество столбцов. Оно равно сумме числа логических переменных и числа всех логических операций в выражении.
• Установить последовательность выполнения логических операций, учитывая скобки и приоритет операций. Основные приоритеты (по убыванию): отрицание (инверсия, NOT), конъюнкция (логическое умножение, AND), дизъюнкция (логическое сложение, OR), импликация (следование), эквивалентность (равнозначность).
• Заполнить строку заголовков, внеся в нее переменные и логические операции в порядке их выполнения.
• Заполнить столбцы входных переменных. Наборы входных переменных (значений 0 и 1) представляют собой последовательность \( n \)-разрядных двоичных чисел от 0 до \( 2^n - 1 \).
• Поочередно заполнить столбцы, выполняя логические операции в установленном порядке.

Анализ таблиц истинности

Анализ таблиц истинности позволяет решать обратную задачу: по известному фрагменту или полному виду таблицы истинности определить логическое выражение (функцию), которое ей соответствует. Также таблицы истинности используются для доказательства равносильности (или эквивалентности) логических выражений. Два логических выражения, зависящие от одних и тех же логических переменных, называются равносильными, если для всех наборов входящих в них переменных значения выражений совпадают. Например, равносильность выражений \( A \land \bar{B} \lor \bar{A} \land B \) и \( A \leftrightarrow B \) может быть доказана сравнением их столбцов в таблице истинности.

Примеры решения задач

Пример 1. Построение таблицы истинности для выражения \( A \land \bar{B} \lor \bar{A} \land B \). Выражение имеет 2 переменные (\( n=2 \)), значит, строк с наборами будет \( 2^2 = 4 \). Операций 5: 2 отрицания, 2 конъюнкции и 1 дизъюнкция. Всего 7 столбцов (2 переменные + 5 операций).

Пример 3. Восстановление логического выражения \( F \) по фрагменту таблицы истинности. Дано выражение \( (x \lor \bar{y} \lor \bar{z}) \land (\bar{x} \lor y) \). Полная таблица истинности для трех переменных (\( x, y, z \)) должна иметь \( 2^3 = 8 \) строк. На первом фрагменте показаны наборы, на которых функция \( F \) истинна (1). На втором фрагменте показаны наборы, на которых \( F \) ложна (0). Для восстановления неизвестного столбца переменных необходимо для каждого набора, где \( F=0 \) (например, 0, 1, 0) найти, при каких значениях \( x, y, z \) выражение \( (x \lor \bar{y} \lor \bar{z}) \land (\bar{x} \lor y) \) принимает 0. Это происходит, когда хотя бы одна из двух конъюнкций равна 0. Если \( \bar{x} \lor y = 0 \), то \( \bar{x} = 0 \) и \( y = 0 \), то есть \( x=1 \) и \( y=0 \). Если \( x \lor \bar{y} \lor \bar{z} = 0 \), то \( x=0 \), \( \bar{y}=0 \), \( \bar{z}=0 \), то есть \( x=0, y=1, z=1 \). Сравнение этих наборов со строками таблицы позволяет установить соответствие столбцов переменным.