Решение логических задач средствами алгебры логики
Обычно используется следующая схема решения:
1. Изучается условие задачи;
2. Вводится система обозначений для логических высказываний;
3. Конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
4. Определяются значения истинности этой логической формулы;
5. Из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.
Рассмотрим этот способ на примерах.
Задача 1.
Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?
Решение.
Запишем условие кратко
Чёрточка сверху означает отрицание.
Имеется три утверждения:
- Вадим изучает китайский;
- Сергей не изучает китайский;
-Михаил не изучает арабский.
Рассмотрим перебор всех случаев.
|
1 случай. Верно первое утверждение.
Два других ложны
Получили противоречие
. Двое изучают китайский язык.
2 случай. Верно второе утверждение.
Два других ложны
Получили противоречие.
Никто не изучает китайский язык
.
 |
3 случай. Верно третье утверждение.
Два других ложны
Ответ: Сергей изучает китайский язык,
Михаил — японский,
Вадим — арабский.
Задача 2.
На концерт пошли три девочки нашего класса Аня, Валя и Люда. Одна из них была в красном платье, другая – в белом, третья – в синем. На вопрос, какое на каждой из девушек было платье, они ответили:
- Аня была в красном.
- Валя – не в красном.
- Люда – не в синем.
В этом ответе из трёх частей одна верна, две неверны.
В каком платье была каждая из девочек?
Решение.
Условие.Запишем условие кратко.
(Чёрточка сверху означает отрицание)
Рассмотрим перебор всех случаев
|
1) Если только первое
высказывание
верно. Получили противоречие.
2) Если только
второе
высказывание Получили противоречие.
Верно
| |
3) Если только Аня К С, Б
третье
высказывание Валя К К
верно
ЛюдаС К, Б
Ответ. Валя была в красномплатье,
Люда в белом платье,
Аня в синемплатье.
Истинностные задачи
Истинностные задачи – это задачи, в которых требуется
Установить истинность или ложность высказываний.
Рассмотрим этот способ на примерах.
Задача 1.
Василиса Прекрасная
Украли у Ивана Царевича Василису Прекрасную. Поехал он выручать ее. Поймал Змея Горыныча, Бабу Ягу, Кощея Бессмертного и Лешего – Иван Царевич знал, что один из них украл ее.
И спрашивает: «Кто украл Василису?» Змей Горыныч, Баба Яга и Кощей Бессмертный ответили: «Не я», а Леший – «Не знаю».
Потом оказалось, что двое из них сказали правду, а двое – неправду.
Знает ли Леший, кто украл Василису?
Решение
Начнем рассуждать с ответов Змея Горыныча, Бабы Яги, Кощея Бессмертного.
Так как украл Василису Прекрасную кто-то один, то среди ответов Змея Горыныча, Бабы Яги, Кощея Бессмертного может быть лишь один ложный, иначе при двух ложных ответах получается, что украли ее двое.
Тогда вторым ложным ответом будет ответ Лешего, так как всего ложных ответов два.
Поэтому Леший знал, кто украл Василису Прекрасную.