РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ X1X1 X2X2 X3X3 F2F2 0001 0010 0100 0110 1000 1010 1101 1111 © Учитель информатики Краснополянской школы 1 Домнин К.М. 2005 год. - презентация

1 РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ X1X1 X2X2 X3X3 F2F © Учитель информатики Краснополянской школы 1 Домнин К.М год

2 Логических задач существует великое множество, огромно и число способов их решения. Невозможно составить один алгоритм для решения всех творческих задач, но выделить из них наиболее распространенные методы можно. Рассмотрим следующие распространенные способы решения логических задач: 1. С помощью алгебры логики 2. С помощью таблиц 3. С помощью графов 4. С помощью рассуждений

3 РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ С ПОМОЩЬЮ С ПОМОЩЬЮ АЛГЕБРЫ ЛОГИКИ

4 1. Решение задач с помощью алгебры логики При решении задач этим способом необходимо: изучить условие задачи ввести систему обозначений для логических высказываний (формализация задачи) сконструировать логическую формулу, описывающую связи между всеми высказываниями определить значения истинности этой формулы упростить формулу и сделать выводы об истинности входящих в нее высказываний В соревнованиях по гимнастике участвуют: Аня, Валя, Таня и Даша. Болельщики строят прогнозы: 1) Таня займет I место, Валя - II; 2) Таня займет II место, Даша - III; 3) Аня займет II место, Даша - IV. По окончании соревнований оказалось, что в каждом предположении только одно из высказываний каждого болельщика истинно, другое - ложно. Каковы результаты соревнований, если на каждом месте по одной девушке? Задача 1

5 1. Решение задач с помощью алгебры логики Введем систему обозначений для задачи (формализация задачи): А = Таня займет I местоВ = Валя займет 2 место С = Таня займет 2 местоD = Даша займет 3 место Е = Аня займет 2 местоF = Даша займет 4 место Исходя из того, что только одно из высказываний любого болельщика верно, можно записать конъюнкцию(которая будет ложной) и дизъюнкцию(которая будет истинной). Составим логические выражения для каждого болельщика: 1) 2) 3) 1) 2) 3) AB = 0 CD = 0 EF = 0 По условию каждая девочка может занять только одно место, поэтому можно записать дополнительные выражения: A+B = 1 C+D = 1 E+F = 1 4) 5) 6) 7)BC = 0 8)8)AC = 0 9)9)DF = 0 10)CE = 0 11)BE = 0

6 1. Решение задач с помощью алгебры логики Умножим 4) на 5): (A+B)(C+D) = 1 раскроем скобки:AC+BC+AD+BD = 1 Посмотрим, какие из слагаемых по условию ложны: Из 8) АС = 0, из 7) ВС = 0 Тогда AD+BD = 1 или D(A+B) = 1, но (А+В) = 1 (из 4) D = 1 из 2): CD = 0 C = 0 Аналогично умножим 5) на 6): (C+D)(E+F) = 1 раскроем скобки:CE+DE+CF+DF = 1 Посмотрим, какие из слагаемых ложны: 13) 12) CE = 0, т.к. из 13) С = 0 CF = 0, т.к. из 13) С = 0 DF = 0, из условия 9) DE = 1 но D = 1 из 12) Это означает, что Е = 1 14) Но по 3) EF = 0 F = 0 15)

7 1. Решение задач с помощью алгебры логики Аналогично умножим 4) на 6): (A+B)(E+F) = 1 раскроем скобки:AE + AF + BE + BF = 1 Посмотрим, какие из слагаемых ложны: Из 15), что слагаемые с F равны 0: AF = 0BF = 0 Из 11), что : BE = 0 ОстаетсяAE = 1 но из 14) Е = 1 А = 1 Осталось оценить истинность В: Из 11), что : BE = 0 из 14) Е = 1 Это значит, что В = 0 Итак, мы определили, что: А = 1 В = 0 C = 0 D = 1 Е = 1 F = 0 Вернемся к условию (формализации задачи)

8 1. Решение задач с помощью алгебры логики А = Таня займет I местоВ = Валя займет 2 место С = Таня займет 2 местоD = Даша займет 3 место Е = Аня займет 2 местоF = Даша займет 4 место 1) 2) 3) А = 1 В = 0C = 0D = 1 Е = 1F = 0 Мы получили: Из обозначений для выражений следует ОТВЕТ: 1) Таня займет I место (А = 1) 2) Даша займет 3 место (D = 1) 3) Аня займет 2 место (E = 1) 4) Вале остается только 4 место В начале мы приняли следующие обозначения:

9 РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ С ПОМОЩЬЮ С ПОМОЩЬЮТАБЛИЦ

10 2. Решение задач с помощью таблиц Три девочки Роза, Маргарита и Анюта представили на конкурс цветоводов корзины выращенных ими роз, маргариток и анютиных глазок. Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием любимых цветов. Какие цветы вырастила каждая из девочек? Для решения задачи составим таблицу, в которой в строках – множество имен девочек, в столбцах – множество названий цветов розы маргаритки Анютины глазки Роза Маргарита Анюта Из условия задачи: «Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием любимых цветов.» следует, что это сказала Анюта, значит она вырастила маргаритки Значит Роза могла вырастить только Анютины глазки Маргарите остаются Розы Ответ виден из таблицы

11 2. Решение задач с помощью таблиц Решите задачу самостоятельно с помощью таблиц: Владимир, Игорь и Сергей преподают математику, физику и литературу, а живут они в Рязани, Туле и Ярославле. Известно также, что Владимир живет не в Рязани, Игорь живет не в Туле, рязанец – не физик, Игорь – не математик, туляк преподает литературу. Кто где живет и что преподает? Рязань ТулаЯрославль Владимир Игорь Сергей

12 РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ С ПОМОЩЬЮ С ПОМОЩЬЮГРАФОВ

13 3. Решение задач с помощью графов

14 РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ МЕТОДОМ РАССУЖДЕНИЙ РАССУЖДЕНИЙ

15 4. Решение задач с помощью рассуждений Два солдата подошли к реке, по которой на лодке катаются двое мальчиков. Как солдатам переправиться на другой берег, если лодка вмещает только одного солдата либо двух мальчиков, а солдата и мальчика уже не вмещает? ММ СС

16 ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ: ЗАДАЧА 1: Есть 2 кувшина емкостью 3 и 8 литров. Как с помощью только этих кувшинов набрать из реки 7 литров воды. ЗАДАЧА 2 Пятеро одноклассников: Ирена, Тимур, Камилла, Эльдар и Залим стали победителями олимпиад школьников по физике, математике, информатике, литературе и географии. Известно, что: 1) победитель олимпиады по информатике учит Ирену и Тимура работе на компьютере; 2) Камилла и Эльдар тоже заинтересовались информатикой; 3) Тимур всегда побаивался физики; 4) Камилла, Тимур и победитель олимпиады по литературе занимаются плаванием; 5) Тимур и Камилла поздравили победителя олимпиады по математике; 6) Ирена сожалеет о том, что у нее остается мало времени на литературу.