§25. Логические задачи | Использование алгебры логики. Задачи 5 - 6 (курс pol 136 ч.)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углубленный курс, 4 часа в неделю)


Уроки 27 - 30
Предикаты и кванторы. Логические элементы компьютера. Логические задачи
§23. Предикаты и кванторы. §24. Логические элементы компьютера. §25. Логические задачи



Содержание урока

§23. Предикаты и кванторы
§24. Логические элементы компьютера
§25. Логические задачи

Метод рассуждений. Задача 1

Табличный метод. Задача 2

Табличный метод. Задача 3

Табличный метод. Задача 4

Использование алгебры логики. Задачи 5 - 6

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

Задачи


§25. Логические задачи


Использование алгебры логики
Задачи 5 - 6


Когда в условии задачи встречаются сложные логические высказывания, удобно использовать методы алгебры логики. Покажем этот подход на примерах.

Задача 5. Следующие два высказывания истинны:

1. Неверно, что если корабль А вышел в море, то корабль С — нет.

2. В море вышел корабль В или корабль С, но не оба вместе.

Определить, какие корабли вышли в море.

Введём три высказывания: А — «Корабль А вышел в море»; В — «Корабль В вышел в море»; С — «Корабль С вышел в море». Вспомним, что связка «если..., то» в логических выражениях заменяется импликацией, поэтому фразу «Если корабль А вышел в море, то корабль С — нет» можно записать как А —> C = 1. Но в условии сказано, что это утверждение неверно, поэтому:

А —> C = О, или А —> C = 1.

Второе условие — это операция «исключающее ИЛИ», т. е. В ⊕ С = 1. Оба условия истинны одновременно, т. е. их логическое произведение (И) тоже истинно:

(А —> C) • (В ⊕ С) = 1.

Нам нужно решить это уравнение и найти неизвестные А, В и С. Для этого выразим импликацию и операцию «исключающее ИЛИ» через базовый набор логических операций (НЕ, И, ИЛИ), а затем раскроем инверсию сложного выражения с помощью закона де Моргана:

(А —> C) • (В ⊕ С) = (A + C) • (В • C + B • C) = A • C • (В • C + B • C) = 1

В последнем выражении раскроем скобки и учтём, что С • C = 0 и С • С = С. Получим:

А • B • С = 1.

Это уравнение имеет единственное решение: А = 1, В = 0 и С = 1. Это значит, что в море вышли корабли А и С.

Выше был показан общий подход к решению подобных задач, однако эту конкретную задачу можно решить намного проще. Как вы знаете, импликация А —> В ложна только при А = 1 и В = 0. Поэтому из условия А —> C = 0 сразу следует, что А = С = 1. Теперь остаётся только применить второе условие В ⊕ С = 1, которое при С = 1 даёт В = 0, и получаем тот же ответ, что и раньше.

Задача 6. На вопрос «Кто из твоих учеников изучал логику?» учитель ответил: «Если логику изучал Андрей, то изучал и Борис. Однако неверно, что если изучал Семён, то изучал и Борис». Кто же изучал логику?

Обозначим переменными высказывания: А — «Логику изучал Андрей»; В — «Логику изучал Борис» и С — «Логику изучал Семён». Оба высказывания учителя можно записать в виде импликаций:

«Если логику изучал Андрей, то изучал и Борис».   А —> В = 1

«Неверно, что если изучал Семён, то изучал и Борис».   С —> В = 0

Дальше есть два варианта решения. Во-первых, можно поступить так же, как и в предыдущей задаче: применить операцию «НЕ» ко второму высказыванию и составить уравнение с помощью логического произведения:

(А —> В) • (C —> В) = 1.

Теперь представляем импликацию через базовые операции и применяем закон де Моргана

(А + В) • (C + В) = (А + В) • С • B = А • C • B = 1.

Это уравнение имеет единственное решение: А = 0, В = 0 и С = 1. Значит, логику изучал только Семён.

Можно поступить иначе, вспомнив, что импликация ложна только в том случае, когда первое высказывание истинно, а второе ложно. Поэтому из условия C —> B = 0 сразу следует, что В = 0 и С = 1. Тогда первое условие, А —> В = А —> 0 = 1 сразу даёт А = 0.

Следующая страница Вопросы и задания



Cкачать материалы урока







Наверх