5. Решение задач с логическими
выражениями
Построение
таблиц истинности логических выражений.
Пример:
Символом F обозначено
одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан
фрагмент таблицы истинности выражения F:
Какое выражение
соответствует F?
Решение (способ 1):
1) нужно для каждой строчки подставить
заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить
результаты с соответствующими значениями F для этих данных;
2) если для какой-нибудь комбинации X, Y и
Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не
рассматривать, поскольку для правильного ответа все три результата должны
совпасть со значениями функции F;
3) перепишем ответы в других обозначениях:
4) первое выражение, 
равно
1 только при
, поэтому это неверный ответ (первая строка таблицы не подходит);
равно
1 только при, поэтому это неверный ответ (первая строка таблицы не подходит);5) второе выражение, 
, равно 1 только при 
, поэтому это неверный ответ (первая и вторая строки таблицы не подходят);
, равно 1 только при , поэтому это неверный ответ (первая и вторая строки таблицы не подходят);6) третье выражение,
равно нулю при 
поэтому это неверный ответ (вторая строка таблицы не подходит);
равно нулю при поэтому это неверный ответ (вторая строка таблицы не подходит);7) наконец, четвертое выражение, 
равно нулю только тогда, когда 
, а в остальных случаях равно 1, что совпадает с приведенной частью таблицы истинности;
равно нулю только тогда, когда , а в остальных случаях равно 1, что совпадает с приведенной частью таблицы истинности;8) таким образом, правильный ответ – 4; частичная таблица истинности для всех выражений имеет следующий вид:
(крестик показывает, что значение функции не совпадает с F, а знак «–» означает, что вычислять оставшиеся значения не обязательно).
Решение (способ 2):
1) часто правильный ответ – это самая простая функция, удовлетворяющая частичной таблице истинности, то есть, имеющая единственный нуль или единственную единицу в полной таблице истинности;
2) в этом случае можно найти такую функцию и проверить, есть ли она среди данных ответов;
3) в приведенной задаче в столбце F есть единственный нуль для комбинации 
;
;4) выражение, которое имеет единственный нуль для этой комбинации, это 
, оно есть среди приведенных ответов (ответ 4);
, оно есть среди приведенных ответов (ответ 4);5) таким образом, правильный ответ – 4.
Пример:
Какое из приведённых имен удовлетворяет логическому условию:
(первая буква согласная → вторая буква согласная) ∩ (предпоследняя буква гласная → последняя буква гласная)?
1) КРИСТИНА;
2) МАКСИМ;
3) СТЕПАН;
4) МАРИЯ.
Решение:
1) два условия связаны с помощью операции ∩ («И»), поэтому должны выполняться одновременно;
2) импликация ложна, если ее первая часть («посылка») истинна, а вторая («следствие») – ложна;
3) первое условие «первая буква согласная → вторая буква согласная» ложно тогда, когда первая буква согласная, а вторая – гласная, то есть для ответов 2 и 4;
4) второе условие «предпоследняя буква гласная → последняя буква гласная» ложно тогда, когда предпоследняя буква гласная, а последняя – согласная, то есть, для ответа 3;
5) таким образом, для варианта 1 (КРИСТИНА) оба промежуточных условия и исходное условие в целом истинны;
6) ответ: 1.
Пример:
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.
1) принтеры & сканеры & продажа;
2) принтеры & сканеры;
3) принтеры | сканеры;
4) принтеры | сканеры | продажа.
Решение (способ 1, рассуждение с использованием свойств операций «И» и «ИЛИ»):
1) меньше всего результатов выдаст запрос с наибольшими ограничениями – первый (нужны одновременно принтеры, сканеры и продажа);
2) на втором месте – второй запрос (одновременно принтеры и сканеры);
3) далее – третий запрос (принтеры или сканеры);
4) четвертый запрос дает наибольшее количество результатов (принтеры или сканеры или продажа);
5) таким образом, верный ответ – 1234 .
Решение (способ 2, через таблицы истинности):
1) каждое из условий можно рассматривать как сложное высказывание;
2) обозначим отдельные простые высказывания буквами:
A: принтеры;
B: сканеры;
C: продажа;
3) запишем все выражения-запросы через логические операции
X1=A*B*C, X2=A*B, X3=A+B, X4=A+B+C;
4) здесь присутствуют три переменные, А, B и C (хотя второе и третье выражения от С не зависят!), поэтому для составления таблицы истинности нужно рассмотреть 8 = 23 всевозможных комбинаций этих логических значений;
5) выражение X1 = A*B*C равно 1 (истинно) только при A=B=C=1 , в остальных случаях – равно 0 (ложно);
6) выражение X2=A*B равно 1 только при A=B=1 , в остальных случаях – равно 0;
7) выражение X3=A+B равно 0 только при A=B=0 , в остальных случаях – равно 1;
8) выражение X4=A+B+C равно 0 только при A=B=C= 0, в остальных случаях – 1;
9) запишем результаты пунктов 5-8 в виде таблицы истинности
10) по таблице видим, что наименьшая «область действия» у первого выражения, поисковый сервер выдаст наименьшее число запросов;
11) область, где X2=1 , включает в себя всю область, где X1=1 и еще один вариант, поэтому «поисковик» выдаст больше запросов, чем для первого случая;
12) аналогично делаем вывод, что область X3=1 включает всю область X2=1 и расширяет ее, а область X4=1 – это расширение области X3=1;
13) таким образом, верный ответ – 1234 .
Решение (способ 3, через диаграммы):
1) запишем все ответы через логические операции
X1=A*B*C, X2=A*B, X3=A+B, X4=A+B+C;
2) покажем области, определяемые этими выражениями, на диаграмме с тремя областями
3) сравнивая диаграммы, находим последовательность областей в порядке увеличения: (1,2,3,4), причем каждая следующая область в этом ряду охватывает целиком предыдущую (как и предполагается в задании, это важно!);
4) таким образом, верный ответ – 1234 .