Таблицы истинности

Информатика. 10 класса. Босова Л.Л. Оглавление

§ 19. Таблицы истинности

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

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

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

1) определить число строк таблицы m = 2ⁿ, где n — число переменных в логическом выражении;
2) определить число столбцов таблицы как сумму чисел логических переменных и логических операций в логическом выражении;
3) установить последовательность выполнения логических операций с учётом скобок и приоритетов операций;
4) заполнить строку с заголовками столбцов таблицы истинности, занеся в неё имена логических переменных и номера выполняемых логических операций;
5) выписать наборы входных переменных с учётом того, что они представляют собой ряд целых n-разрядных двоичных чисел от 0 до 2ⁿ — 1;
6) провести заполнение таблицы истинности по столбцам, выполняя логические операции.

Пример 1. Построим таблицу истинности для логического выражения

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

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

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

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

Таблица истинности, построенная в предыдущем примере, доказывает равносильность выражений

Можно записать:

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

Функцию от n переменных, аргументы которой и сама функция принимают только два значения — 0 и 1, называют логической функцией. Таблица истинности может рассматриваться как способ задания логической функции.

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

Рассмотрим несколько примеров.

Пример 2. Известен фрагмент таблицы истинности для логического выражения F, содержащего логические переменные А, В и С.

Сколько из приведённых ниже логических выражений соответствуют этому фрагменту?

1) (A v С) & B;
2) (A v B) & (С ? А);
3) (А & B v С) & (B ? А & С);
4) (А ? B) v (С v А ? B).

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

1) Логическое выражение (A v С) & В соответствует данному фрагменту таблицы истинности:

2) Логическое выражение (A v В) & (С ? А) не соответствует данному фрагменту таблицы истинности, т. к. уже на первом наборе значение рассматриваемого логического выражения не совпадает со значением F. Проведение дальнейших вычислений не имеет смысла.

3) Логическое выражение (А & В v С) & (В ? А & С) не соответствует данному фрагменту таблицы истинности:

4) Логическое выражение (А ? В) v (С v А ? В) соответствует данному фрагменту таблицы истинности:

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

Можно ли утверждать, что в результате решения задачи мы нашли логическое выражение F?

Пример 3. Логическая функция F задаётся выражением:

Ниже приведён фрагмент таблицы истинности, содержащий все наборы переменных, на которых F истинна.

Определим, какому столбцу таблицы истинности функции F соответствует каждая из переменных х, y > z.

В исходном логическом выражении задействовано три логические переменные. Полная таблица истинности для этого выражения должна состоять из 8 (2³) строк.

Наборам переменных, на которых логическое выражение истинно, соответствуют десятичные числа 0, 2, 3, 4 и 7.

Следовательно, наборам переменных, на которых логическое выражение ложно, должны соответствовать десятичные числа 1, 5 и 6 (их двоичные коды 001, 101 и 110). Построим по этим данным вторую часть таблицы истинности:

Теперь выясним, при каких значениях х, у, z логическое выражение ложно:

Логическое произведение ложно, если хотя бы один из операндов равен нулю. Таким образом, мы имеем две дизъюнкции, каждая из которых должна быть ложной. Это возможно только в случае равенства нулю каждого из операндов, входящих в дизъюнкцию. Подберём подходящие значения х, у и z, заполняя следующую таблицу:

Первая дизъюнкция равна нулю на наборе 011. Для равенства нулю второй дизъюнкции требуется, чтобы х = 1, у = 0, а z может быть и 0, и 1.

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

Переменная у принимает единичное значение только один раз. Следовательно, ей соответствует второй столбец исходной таблицы. Из таблицы со значениями х, у и z следует, что при у = 1: х = 0, а z = 1. Следовательно, переменной z соответствует первый столбец, а переменной х — третий столбец исходной таблицы.

Убедиться в правильности полученного ответа можно, полностью заполнив следующую таблицу:

САМОЕ ГЛАВНОЕ

Истинность логического выражения можно доказать путём построения его таблицы истинности.

Функцию от п переменных, аргументы которой и сама функция принимают только два значения — 0 и 1, называют логической функцией. Таблица истинности может рассматриваться как способ задания логической функции.

Вопросы и задания

1. Что представляет собой таблица истинности?

2. Составлена таблица истинности для логического выражения, содержащего n переменных. Известно m — количество строк, в которых выражение принимает значение 0. Требуется выяснить, в скольких случаях логическое выражение примет значение 1 при следующих значениях n и m:

3. Постройте таблицы истинности для следующих логических выражений:

4. Рассмотрите два составных высказывания

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

6. Какое из приведённых логических выражений равносильно выражению (А ? С) & (B ? С)?

7. Известен фрагмент таблицы истинности для логического выражения F, содержащего логические переменные А, В и С.

8. Логическая функция F задаётся выражением