Пятница, 24.11.2017, 05:01
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Главная » Статьи » Информатика » Информатика

Решение логических задач
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. Таким образом, для логических задач средствами математической логики мы
использовали следующий алгоритм решения:
• Внимательно изучить условие.
• Выделить простые высказывания и обозначить их латинскими буквами.
• Записать условие задачи на языке алгебры логики.
• Составить логическое выражение в соответствии с условием задачи.
• Упростить формулу.
• Проанализировать полученный результат.
Категория: Информатика | Добавил: july1971 (09.07.2012) | Автор: Пахомова Юлия Владиславовна E
Просмотров: 755 | Комментарии: 1 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]