| Главная » Статьи » Информатика » Информатика |
Решение логических задач
| 1. Актуализация темы урока. Решать логические задачи очень увлекательно. В них вроде бы нет никакой математики - нет ни чисел, ни функций, ни треугольников, ни векторов, а есть только истина и ложь. В то же время дух математики в них чувствуется ярче всего - половина решения любой математической задачи состоит в том, чтобы как следует разобраться в условии, распутать все связи между участвующими объектами. Решать логические задачи можно разными способами, они разнообразны и каждый из них имеет свою область применения. Сегодня на занятии мы рассмотрим ряд задач, которые можно решить средствами математической логики. (Презентация на тему «Решение логических задач с помощью алгебры логики».) 2. Повторение основных понятий и логических законов алгебры логики. Давайте вспомним основные понятия, законы и обозначения математической логики. (Слайды 2-6 презентации) Использование данных законов рассмотрим на следующем примере (Слайды 7-9 презентации): Какое логическое выражение равносильно выражению A ¬(¬B C). • перепишем заданное выражение в других обозначениях: заданное выражение ; • посмотрев на заданное выражение, видим инверсию (операцию «НЕ») для сложного выражения в скобках, которую раскрываем по формуле де Моргана, ; • затем используем закон двойного отрицания по которому : • для проверки правильности преобразований построим таблицу истинности к исходному и преобразованному выражениям, сравним полученные результаты. 3. Умение строить и преобразовывать логические выражения используется и при решении логических задач. (При этом используется следующая схема решения: изучается условие задачи; вводится система обозначений для логических высказываний; конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи; определяются значения истинности этой логическая формула; из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.) Пример задачи. Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров: А) Макс победит, Билл – второй; В) Билл – третий, Ник – первый; С) Макс – последний, а первый – Джон. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс? Решение: 1) применим к этой задаче формальный аппарат математической логики 2) каждый из трех болельщиков высказал два утверждения, всего получилось 6; обозначим их так: A: М1 = «Макс – первый», Б2 = «Билл – второй» B: Н1 = «Ник – первый», Б3 = «Билл – третий» C: Д1 = «Джон – первый», М4 = «Макс – четвертый» 3) теперь как-то нужно записать, что у каждого одно высказывание верно, а второе неверно; скажем, для «A» это равносильно двум следующим условиям, которые должны выполняться одновременно: A: М1 + Б2 = 1,(по крайней мере одно из двух условий истинно) М1 • Б2 = 0 (по крайней мере одно из двух условий ложно) аналогично для остальных болельщиков B: Н1 + Б3 = 1, Н1 • Б3 = 0 С: Д1 + М4 = 1, Д1 • М4 = 0 4) перемножим первые условия из каждой пары; поскольку все эти суммы равны 1, получаем (М1 + Б2) • (Н1 + Б3) • (Д1 + М4) = 1 5) раскроем произведение первых двух скобок (М1 • Н1 + М1 • Б3 + Б2 • Н1 + Б2 • Б3) • (Д1 + М4) = 1 6) попробуем упростить «большую» скобку»; во-первых, два человека (Макс и Ник) не могут одновременно находиться на первом месте, поэтому М1 • Н1 = 0 7) во-вторых, один человек (Билл) не может одновременно находиться и на втором, и на третьем месте, поэтому Б2 • Б3 = 0, так что (М1 • Б3 + Б2 • Н1) • (Д1 + М4) = 1 8) снова перемножим скобки и получим М1 • Б3 • Д1 + М1 • Б3 • М4 + Б2 • Н1 • Д1 + Б2 • Н1 • М4 = 1 9) так же, как и в п. 6-7, находим, что М1 • Д1 = 0, М1 • М4 = 0 и Н1 • Д1 = 0, так что Б2 • Н1 • М4 = 1 10) из последнего уравнения следует, что Б2 = 1 (Билл на втором месте), Н1 = 1 (Ник – на первом) и М4 = 1 (Макс – на четвертом), а Джону осталось третье. Еще один пример задачи. Мама, прибежавшая на звон разбившейся вазы, застала всех трех своих сыновей в совершенно невинных позах: Саша, Ваня и Коля делали вид, что происшедшее к ним не относится. Однако футбольный мяч среди осколков явно говорил об обратном. – Кто это сделал? – спросила мама. – Коля не бил по мячу, – сказал Саша. – Это сделал Ваня. Ваня ответил: – Разбил Коля, Саша не играл в футбол дома. – Так я и знала, что вы друг на дружку сваливать будете, рассердилась мама. Ну, а ты что скажешь? – спросила она Колю. – Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки, – сказал Коля. Оказалось, что один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду. Кто разбил вазу? Решение: 1) применим к этой задаче формальный аппарат математической логики; введем высказывания: С: вазу разбил Саша В: вазу разбил Ваня К: вазу разбил Коля 2) запишем с помощью этих обозначений утверждения мальчиков: Саша: 1. 2. Ваня: 1. 2. Коля: 1. 3) читаем условие: «один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду»; 4) как записать «Саша два раза солгал»? в этом случае оба его утверждения неверны, поэтому и , что равносильно 5) как записать «Саша два раза сказал правду»? в этом случае оба его утверждения истинны, поэтому и , что равносильно 6) если Коля солгал, а Саша и Ваня сказали правду, то и и заменив «И» на умножение, получаем ; учитывая, что , получаем в левой части равенства ноль; так как в правой части – единица, этого не может быть (равенство ложно при любых значениях ) 7) если Ваня солгал, а Саша и Коля сказали правду, то и и заменив «И» на умножение, получаем ; учитывая, что , получаем, что это равенство ложно при любых значениях (этого не может быть) 8) остается последний возможный вариант: если Саша оба раза солгал, а Ваня и Коля сказали правду, то и и заменив «И» на умножение, получаем ; упростив это выражение с учетом равенств и , получим ; то есть, при этом предположении вазу разбил Коля, а не Ваня и не Саша; 9) таким образом, вазу разбил Коля. 4. Таким образом, для логических задач средствами математической логики мы использовали следующий алгоритм решения: • Внимательно изучить условие. • Выделить простые высказывания и обозначить их латинскими буквами. • Записать условие задачи на языке алгебры логики. • Составить логическое выражение в соответствии с условием задачи. • Упростить формулу. • Проанализировать полученный результат. | |
| Просмотров: 1302 | Комментарии: 1 | |
| Всего комментариев: 0 | |