информатика и логика - Лекция 12. Методы решения логических задач.

Форма входа

Поиск

Календарь

Статистика

Онлайн всего: 1

Гостей: 1

Пользователей: 0

	Четверг, 19.09.2024, 03:56
	Приветствую Вас Гость \| RSS
	Алгебра логики
	Главная \| Регистрация \| Вход

Лекция 12. Методы решения логических задач.

5. Решение задач с логическими выражениями

Построение таблиц истинности логических выражений.

Пример:

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

Решение (способ 1):

1) нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данных;

2) если для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F;

3) перепишем ответы в других обозначениях:

4) первое выражение,

равно 1 только при

, поэтому это неверный ответ (первая строка таблицы не подходит);

5) второе выражение,

, равно 1 только при

, поэтому это неверный ответ (первая и вторая строки таблицы не подходят);

6) третье выражение,

равно нулю при

поэтому это неверный ответ (вторая строка таблицы не подходит);

7) наконец, четвертое выражение,

равно нулю только тогда, когда

, а в остальных случаях равно 1, что совпадает с приведенной частью таблицы истинности;

8) таким образом, правильный ответ – 4; частичная таблица истинности для всех выражений имеет следующий вид:

(крестик показывает, что значение функции не совпадает с F, а знак «–» означает, что вычислять оставшиеся значения не обязательно).

Решение (способ 2):

1) часто правильный ответ – это самая простая функция, удовлетворяющая частичной таблице истинности, то есть, имеющая единственный нуль или единственную единицу в полной таблице истинности;

2) в этом случае можно найти такую функцию и проверить, есть ли она среди данных ответов;

3) в приведенной задаче в столбце F есть единственный нуль для комбинации

;

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 = 2³ всевозможных комбинаций этих логических значений;

5) выражение X₁ = 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) область, где X₂=1 , включает в себя всю область, где X₁=1 и еще один вариант, поэтому «поисковик» выдаст больше запросов, чем для первого случая;

12) аналогично делаем вывод, что область X₃=1 включает всю область X₂=1 и расширяет ее, а область X₄=1 – это расширение области X₃=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 .

информатика и логика 2024

Создать бесплатный сайт с uCoz