ГДЗ: Параграф § 19 / Информатика 10 класс

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

Количество строк \( m \) для наборов значений переменных вычисляется по формуле \( m = 2^n \), где \( n \) — это количество логических переменных в выражении. К этому добавляется одна строка для заголовков.

• Сначала определяется количество строк \( m = 2^n \).
• Затем вычисляется общее число столбцов (число переменных плюс число логических операций).
• Устанавливается правильный порядок выполнения логических операций.
• Заполняются столбцы входных переменных всеми возможными наборами значений.
• Поочередно заполняются столбцы, выполняя логические операции в установленном порядке.

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

Для всех выражений необходимо следовать алгоритму: определить число строк \( (2^n) \), определить число столбцов (переменные + операции), установить приоритет операций и заполнить таблицу по столбцам. Например, для \( A \to \bar{B} \): \( n=2 \), 4 строки. Порядок: 1) \( \bar{B} \), 2) \( A \to \bar{B} \).

Необходимо построить таблицу истинности для обеих формул. Если столбцы, соответствующие \( \bar{A} \to B \) и \( A \lor B \), полностью совпадают для всех 4 наборов значений \( A \) и \( B \), то равносильность доказана.

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

• 1) Выражение \( (A \to B) \leftrightarrow (A \land \bar{B}) \) имеет 2 переменные, 4 строки.
• 2) Выражение \( (A \to B) \to (\bar{A} \to \bar{B}) \) имеет 2 переменные, 4 строки.
• 3) Выражение \( (A \leftrightarrow B) \to (\bar{B} \lor C) \) имеет 3 переменные, 8 строк.

Необходимо строго соблюдать порядок операций: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

Пусть \( A \) — 'одно слагаемое делится на 3', \( B \) — 'другое слагаемое делится на 3', \( C \) — 'сумма делится на 3'.

• Высказывание \( F_1 \) можно представить как импликацию \( A \to B \).
• Высказывание \( F_2 \) можно представить как \( \bar{A} \to \bar{C} \) (хотя формулировка не строгая, можно интерпретировать как \( \bar{A} \to \bar{C} \)).

Для \( F_1 \) строится таблица истинности для \( A \to B \). Для \( F_2 \) (в интерпретации с \( A \) и \( C \)) строится таблица для \( \bar{A} \to \bar{C} \). Сравнение столбцов покажет, совпадают ли значения. (Примечание: Смысл высказываний в задаче избыточен для чисто логической задачи, где нужно просто построить таблицу для формулы).

• 1) Построить таблицу истинности для \( A \to (\bar{A} \to A) \). Все значения в результирующем столбце должны быть 1.
• 2) Построить таблицу истинности для \( (A \to B) \to (\bar{B} \to \bar{A}) \). Все значения в результирующем столбце должны быть 1. Это закон контрапозиции.
• 3) Построить таблицу истинности для \( (A \land \bar{C}) \lor (C \to (A \lor \bar{B})) \land B \land C \). Все значения в результирующем столбце должны быть 1. Выражение имеет 3 переменные, 8 строк.

Необходимо построить таблицу истинности для исходного выражения \( F = (A \to \bar{C}) \land (\bar{B} \to C) \) и для каждого из вариантов. Выражение, чей результирующий столбец совпадет со столбцом \( F \), является равносильным.

Равносильное выражение — 4) \( A \leftrightarrow B \to C \). (Предполагаемое решение из учебника: 4. \( A \leftrightarrow B \to C \) соответствует \( F \)).

Для каждого набора из фрагмента (например, \( A=1, B=0, C=0 \) при \( F=0 \)) необходимо вычислить значение каждого из пяти логических выражений. Если значение выражения совпадает со значением \( F \) для всех четырех наборов, то это выражение является искомым.

Проверка показывает, что ни одно из приведенных выражений не соответствует данному фрагменту. (Ответ 5).

Дано логическое выражение \( F = (A \land \bar{B} \land \bar{C}) \lor (\bar{A} \land B \land C) \lor (\bar{A} \lor \bar{B} \lor \bar{C}) \). Необходимо найти наборы \( A, B, C \), при которых \( F=0 \). Для этого все три дизъюнктивные части должны быть равны 0. Сначала рассмотрим \( (\bar{A} \lor \bar{B} \lor \bar{C}) = 0 \). Это возможно, только если \( \bar{A}=0, \bar{B}=0, \bar{C}=0 \), т.е. \( A=1, B=1, C=1 \). При этом наборе: 1-я часть \( (1 \land \bar{1} \land \bar{1}) = 0 \), 2-я часть \( (\bar{1} \land 1 \land 1) = 0 \), 3-я часть \( (\bar{1} \lor \bar{1} \lor \bar{1}) = 0 \). Таким образом, на наборе (1, 1, 1) функция \( F=0 \).

Второй набор, на котором \( F=0 \), — это (0, 1, 0). (Проверка из учебника). Теперь нужно сравнить найденные наборы с данным фрагментом. В таблице фрагмента, где \( F=0 \):

• Набор (0, 0, 0) соответствует (0, 1, 0) в одной из строк, где \( F=1 \).
• Набор (0, 1, 0) соответствует набору (1, 1, 1) (из решения).

Сравнение наборов истинности, где \( F=0 \), с фрагментом позволяет установить, что переменная \( A \) соответствует третьему столбцу, \( B \) — первому, \( C \) — второму.