Урок №10. Таблицы истинности.
Вы уже знакомы с таблицами истинности логических операций. В них установлено соответствие между всеми возможными наборами операндов и результатами выполнения соответствующих операций.
Таблица истинности логического выражения показывает, какие значения принимает выражение при всех наборах значений входящих в него переменных.
Для построения таблицы истинности следует:
1) подсчитать n — число переменных в выражении;
2) установить последовательность выполнения логических операций с учётом скобок и приоритетов;
3) подсчитать общее число логических операций в выражении;
4) определить число столбцов в таблице: число переменных + число операций;
5) заполнить шапку таблицы, включив в неё переменные и операции в соответствии с последовательностью, установленной в п. 2;
6) определить число строк в таблице (не считая шапки таблицы): m = 2n;
7) выписать наборы входных переменных с учётом того, что они представляют собой ряд целых /г-разрядных двоичных чисел от 0 до 2п — 1;
8) провести заполнение таблицы по столбцам, выполняя логические операции в соответствии с установленной последовательностью.
Пример 1
Построим таблицу истинности для логического выражения A v А ∧ В.
В нём две переменные, две операции, причём сначала выполняется конъюнкция, а затем — дизъюнкция. Всего в таблице будет четыре столбца:
Наборы переменных — это целые числа от 0 до 3, представленные в двухразрядном двоичном коде: 00, 01, 10, 11. Заполненная таблица истинности имеет вид:
Обратите внимание, что последний столбец (результат) совпал со столбцом А. В этом случае можно сказать, что логическое выражение A v А ∧ В равносильно логической переменной А.
Таблицу истинности можно построить для логического выражения с любым числом переменных n, главное — правильно записать все 2n комбинаций 0 и 1, являющихся значениями переменных. Сделать это можно так: в столбце для последней переменной чередуйте 0 и 1, для предпоследней — 00 и 11, затем — 0000 и 1111 и т. д.
С помощью таблиц истинности можно доказывать различные свойства логических операций, называемые также законами алгебры логики.
Пример 2
Докажем распределительный закон для логического сложения: A v (В ∧ С) = (A v В) ∧ (A v С).
Совпадение значений в выделенных столбцах, соответствующих логическим выражениям в левой и правой частях равенства, доказывает справедливость распределительного закона для логического сложения.
Вы уже знаете, что решать логические задачи можно, составляя, упрощая и анализируя логические выражения. Рассмотрим ещё один способ решения логических задач — с помощью таблиц истинности.
Задача
Коля, Вася и Серёжа гостили летом у бабушки. Однажды один из мальчиков нечаянно разбил любимую бабушкину вазу. На вопрос, кто разбил вазу, они дали такие ответы:
Серёжа: 1) я не разбивал; 2) Вася не разбивал.
Вася: 3) Серёжа не разбивал; 4) вазу разбил Коля.
Коля: 5) я не разбивал; 6) вазу разбил Серёжа.
Бабушка знала, что один из её внуков, назовём его правдивым, оба раза сказал правду; второй, назовём его шутником, оба раза сказал неправду; третий, назовём его хитрецом, один раз сказал правду, а другой раз — неправду.
Назовите имена правдивого, шутника и хитреца. Кто из внуков разбил вазу?
Решение
Пусть К = «Коля разбил вазу», В= «Вася разбил вазу», С = «Серёжа разбил вазу». Для решения задачи можно составить таблицу истинности, в которой представить все возможные варианты значений высказываний каждого мальчика. Но так как ваза разбита одним внуком, то достаточно фрагмента таблицы истинности, содержащего наборы значений переменных: 001, 010, 100.
Исходя из того, что знает о внуках бабушка, следует искать в таблице строку, содержащую в каком-либо порядке три комбинации значений: 00 (слова шутника), 11 (слова правдивого внука), 01 или 10 (слова хитреца). Такая строка выделена жирной рамкой. Согласно этой строке, вазу разбил Серёжа, он же оказался хитрецом. Шутником оказался Вася. Имя правдивого внука — Коля.
Содержимое спойлера