Методы Решения логических задач

«Логика – бог мыслящих». Леон Фейхтвангер

Цель:
познакомиться с методами решения логических задач.

Слово "логика" греческого происхождения. Логика как наука основана Аристотелем (384-320 гг до н.э.), который был необыкновенной фигурой в целой плеяде блестящих греческих ученых. Он был последователем Платона и посещал его Академию в Афинах. После смерти Платона (347 г.до н.э.) Аристотель покинул Афины. Он вернулся туда 12 лет спустя и основал свою школу - Лицей. Одним из учеников Аристотеля был Александр Великий.
Логика Аристотеля является скорее частью философии, но эта часть - основа всех наук. В своем выдающемся произведении "Аналитики" Аристотель создал и проверил около 20 схем рассуждений, которые назвал силлогизмами. Процитируем самый известный силлогизм: "Сократ - человек; все люди смертны; значит Сократ смертен". После Аристотеля силлогизмы и их трансформации стали основой дедуктивных рассуждений.

Готфрид Лейбниц в начале 18 века сделал попытку создать формальную логическую систему, введя законы сочетания высказываний. Он высказал идею о том, что рассуждения могут быть сведены к механическому выполнению определенных действий по установленным правилам: "Можно придумать некий алфавит человеческих мыслей, и с помощью комбинации букв этого алфавита и анализа слов, из них составленных, все может быть открыто и разрешимо". Но эти работы не были опубликованы, и лишь в 19 веке Джордж Буль и Август де Морган основали математическую логику, независимую от философии.

Известнейшие работы Джорджа Буля (1815-1864): "Формальная логика", "Исследование законов мысли". Буль вводит в логику алгебраическую структуру, называемую сегодня кольцо Буля, две операции, свойства которых в чем-то подобны свойствам операции с числами (например, 1+0=1), и в чем-то расходятся с ними (например, 1+1=1). Это позволило описать логику высказываний как формальную алгебраическую структуру.

Огастес (Август) де Мо́рган, ввел кванторы (не называя их) и сделал попытку формального определения структур, продолжив работу, начатую Булем.

Целесообразно повторить:

Составное высказывание, образованное в результате операции логического умножения (КОНЪЮНКЦИИ), истинно тогда и только тогда, когда истинны все входящие в него простые высказывания.

Составное высказывание, образованное в результате логического сложения (ДИЗЪЮНКЦИИ), истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний.

Логическое отрицание (ИНВЕРСИЯ) делает истинное высказывание ложным и, наоборот, ложное – истинным.

Составное высказывание, образованное с помощью операции логического следования (ИМПЛИКАЦИИ), ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание)

Составное высказывание, образованное с помощью логической операции тождества(ЭКВИВАЛЕНТНОСТИ) истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны

Закон тождества A=A
Закон непротиворечия A&¬A=0
Закон исключенного третьего Av¬A=1
Закон двойного отрицания ¬¬A=A
Законы де Моргана ¬(¬Av¬B)=¬A&¬B; ¬(¬A&¬B)=¬Av¬B
Закон коммутативности


Закон ассоциативности


Закон
дистрибутивности

Целесообразно повторить:

Устные задания.

Вася забыл пароль к Windows XP, но помнил алгоритм его получения из строки подсказки «23ABN12QR8N»: если последовательности символов «AB» и «QR» поменять местами, а затем из получившейся строки удалить все символы «N», то полученная последовательность и будет паролем. Определите пароль:

23AB12QR8
23QR12AB8
23QRAB8
23QR128

Для какого имени истинно высказывание
¬(ПЕРВАЯ БУКВА СОГЛАСНАЯ  ВТОРАЯ БУКВА СОГЛАСНАЯ)  ПОСЛЕДНЯЯ БУКВА ГЛАСНАЯ?
Запишем в виде логических операций: ¬ (сс ) гл 
1). Роман
2). Юнона
3). Андрей
4). Кристина

Методы решения логических задач: 

Метод рассуждений;
Метод таблиц;
Метод графов;
Метод блок-схем;
Метод кругов Эйлера - Венна;
С помощью алгебры логики;
Итоги

Задача.
Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: «Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский. Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложно. Какой язык изучает каждый из молодых людей.
Решение.
А = « Вадим изучает китайский»;
В = «Сергей не изучает китайский»;
С = «Михаил не изучает арабский».
Если верно А, то верно и В. То есть А ложно.
Если верно В, то А и С ложные утверждения (неверно, т.к. никто не изучает китайский).
Таким образом, вено С, а А и В ложные утверждения.

Ответ: Сергей изучает китайский, Михаил – японский, а Вадим – арабский языки.

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

Задача.
Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин A, B, C. На первом месте – одна из бусин B, D, C, которой нет на третьем месте. В середине – одна из бусин А, C, E, B, не стоящая на первом месте. Какая из перечисленных цепочек создана по этому правилу?
 1) BCB 2) EAC 3) BCD 4) CBB

Решение.
У1: третья бусина – A, B или C 1) BCB не выполняется У3
У2: первая бусина – B, D или C 2) EAC не выполняется У2
У3: первая и третья бусины – разные 3) BCD не выполняется У1
У4: вторая бусина – A, B, C или E 4) CBB все условия выполняются
У5: первая и вторая бусины – разные
Ответ: 4

Задача.
На пяти железнодорожных путях стоят 5 поездов. Петров – машинист поезда, отправляющегося в 12.00, этот поезд зеленого цвета. В составе поезда, стоящего по центру, 12 вагонов. Сидоров - машинист поезда, отправляющегося в 12.45. Волков – машинист в поезде с 15 вагонами, его поезд сразу слева от поезда зеленого цвета. Сразу правее поезда, имеющего синий цвет, стоит поезд, отправляющийся в Киров. Кузьмин – машинист поезда, едущего в Саратов. Рядом с составом черного цвета – состав с 14 вагонами. Поезд на Иркутск отходит в 13.00. В 12.20 отправляется поезд с машинистом Поповым и он непосредственно справа от поезда до Кирова. Состав с 16 вагонами направляется в Харьков. Рядом с поездом, который отправляется в 12.20, поездной состав с 13 вагонами. Крайний состав окрашен в красный цвет. Состав с 12 вагонами отправляется в 12.30. Составы красного и черного цвета стоят рядом. Поезд, следующий до Харькова, отходит в12.00. Какой состав пестрый? Какой поезд едет в Петербург?

Решение:Пронумеруем условия задачи.

Петров – машинист поезда, отправляющегося в 12.00, этот поезд зеленого цвета.
В составе поезда, стоящего по центру, 12 вагонов.
Сидоров – машинист поезда, отправляющегося в 12.45.
Волков – машинист в поезде с 15 вагонами, его поезд сразу слева от поезда зеленого цвета.
Сразу правее поезда, имеющего синий цвет, стоит поезд, отправляющийся в Киров.
Кузьмин – машинист поезда, едущего в Саратов.
Рядом с составом черного цвета – состав с 14 вагонами.
Поезд на Иркутск отходит в 13.00.
В 12.20 отправляется поезд с машинистом Поповым и он непосредственно справа от поезда до Кирова.
Состав с 16 вагонами направляется в Харьков.
Рядом с поездом, который отправляется в 12.20, поездной состав с 13 вагонами.
Крайний состав окрашен в красный цвет.
Состав с 12 вагонами отправляется в 12.30.
Составы красного и черного цвета стоят рядом.
Поезд, следующий до Харькова, отходит в12.00.

Задача.
Четверо друзей Алексей, Олег, Игорь и Семен занимались в разных спортивных секциях. Один из них играл в баскетбол, второй — в волейбол, третий — в футбол, а четвертый — в теннис. У них были и различные увлечения: один из них любил кино, другой — театр, третий — эстраду, а четвертый — цирк. Известно, что Алексей не играет ни в волейбол, ни в баскетбол. Олег играет в футбол и любит театр. Семен не играет в волейбол. Тот из ребят, который играет в волейбол, любит ходить в кино, а тот, кто играет в баскетбол, не любит цирк. В какую секцию ходит и чем увлекается каждый из друзей?
Решение.
Алексей не играет ни в волейбол, ни в баскетбол.
Олег играет в футбол и любит театр.
Семен не играет в волейбол.
Тот из ребят, который играет в волейбол, любит ходить в кино.
Тот, кто играет в баскетбол, не любит цирк.

Ответ: Алексей занимается теннисом и любит ходить в цирк, Олег увлекается
театром и занимается футболом, Игорь – волейбол и кино, Семён – баскетбол и эстрада.

Метод таблиц.

Задача.
Четыре футбольных команды: итальянская команда «Милан», испанская – «Реал», российская – «Зенит», английская – «Челси» встретились в групповом этапе лиги чемпионов по футболу. Их тренировали тренеры из этих же четырех стран: итальянец Антонио, испанец Родриго, русский Николай, англичанин Марк. Известно, что национальность у всех четырех тренеров не совпадала с национальностью команд. Требуется определить тренера каждой команды, если известно: а) Зенит не тренируется у Марка и Антонио. б) Милан обещал никогда не брать Марка главным тренером.

Италия «Милан»

Испания «Реал»

Россия «Зенит»

Англия «Челси»

Италия Антонио

Испания Родриго

Россия Николай

Англия Марк

Ответ.
Российская команда «Зенит» тренируется у испанца Родриго; итальянская команда «Милан» тренируется у русского Николая; английская команда «Челси» тренируется у итальянца Антонио; испанская команда «Реал» тренируется у англичанина Марка.

Задача.
Имеются два сосуда — трехлитровый и пятилитровый. Нужно, пользуясь этими сосудами, получить 1, 2, 3, 4, 5, 6, 7 и 8 литров воды. В нашем распоряжении водопроводный кран и раковина, куда можно выливать воду.
Решение.
НБ — наполнить больший сосуд водой из-под крана;
НМ — наполнить меньший сосуд водой из-под крана;
ОБ — опорожнить больший сосуд, вылив воду в раковину;
ОМ — опорожнить меньший сосуд, вылив воду в раковину;
Б→М — перелить из большего в меньший, пока больший сосуд не опустеет или меньший сосуд не наполнится;
М→Б — перелить из меньшего в больший, пока меньший сосуд не опустеет или больший сосуд не наполнится.
Выделим три команды: НБ, Б→М, ОМ.
Две вспомогательные команды: Б = 0 ? — посмотреть, пуст ли больший сосуд;
М = З ? — посмотреть, наполнен ли малый сосуд.
Последовательность выполнения команд:
Б→М выполнять ОМ всякий раз, как меньший сосуд оказывается наполненным
НБ всякий раз, как больший сосуд будет опорожнен

Результаты выполнения команд по блок – схеме:

Ответ: из таблицы видно, как наполнить определенное количество воды. А для наполнения 8 литров необходимо наполнить оба сосуда .

Метод кругов Эйлера - Венна.

2

4

4

3

3

13

62

62

14

14

Задача.
Составить расписание занятий так, чтобы математика была первым или вторым уроком, информатика первым или третьим уроком, а физика – вторым или третьим.
В расписании всего три урока. Сколько вариантов расписания с такими условиями можно составить?
Решение.
М1 = «Математика первым уроком»
М2 = «Математика вторым уроком»
И1 = «Информатика первым уроком»
И3 = «Информатика третьим уроком»
Ф2 = «Физика вторым уроком»
Ф3 = «Физика третьим уроком»
Расписание: (М1  М2)  (И1  И3)  (Ф2  Ф3)
=(М1  М2)  (И1  И3)  (Ф2  Ф3) = (М1И1  М1И3  М2И1  М2И3)  (Ф2  Ф3) =
М1·И1·Ф2  М1·И3·Ф2  М2·И1·Ф2  М2·И3·Ф2  М1·И1·Ф3  М1·И3·Ф3  М2·И1·Ф3  М2·И3·Ф3
Ответ:
1 вариант – Математика, Физика, Информатика
2 вариант – Информатика, Математика, Физика

Задача.Следователь допрашивает Клода, Жака и Дика. Клод утверждает, что Жак лжет, Жак обвинял во лжи Дика, а Дик призывает не слушать ни того, ни другого. Кто из допрашиваемых говорил правду?

Решение:
К  ¬Ж  ¬К  Ж
Ж  ¬Д  ¬Ж  Д
Д  ¬К  ¬Ж  ¬Д  (К  Ж)

(К·¬Ж  ¬К·Ж)  (Ж·¬Д  ¬Ж·Д)  (Д·¬К·¬Ж  ¬Д·(К  Ж)) ≡
(К·¬Ж· Ж·¬Д  К·¬Ж·¬Ж·Д  ¬К·Ж·Ж·¬Д  ¬К·Ж·¬Ж·Д)  (Д·¬К·¬Ж  ¬Д·К ¬Д·Ж)≡
(К·¬Ж·¬Ж·Д  ¬К·Ж·Ж·¬Д)  (Д·¬К·¬Ж  ¬Д·К  ¬Д·Ж) ≡
К·¬Ж·¬Ж·Д·Д·¬К·¬Ж  К·¬Ж·¬Ж·Д·¬Д·К  К·¬Ж·¬Ж·Д·¬Д·Ж 
¬К·Ж·Ж·¬Д·Д·¬К·¬Ж  ¬К·Ж·Ж·¬Д·¬Д·К  ¬К·Ж·Ж·¬Д·¬Д·Ж ≡
≡ ¬К  ¬Д  Ж
Ответ: правду говорил Жак.

Идея метода рассуждений состоит в том, что мы проводим рассуждения, используя последовательно все условия задачи, и приходим к выводу, который и будет являться ответом задачи.
Идея метода таблиц состоит в том, чтобы оформлять результаты логических рассуждений с помощью таблицы.
Основой применения графов для решения логических задач служит выявление и последовательное исключение возможностей, заданных в условии. Основное преимущество – это наглядность.
Идея метода блок – схем состоит в следующем: описать последовательность выполнения операций, определить порядок их выполнения и фиксировать состояния.
Идея метода кругов Эйлера - требуется найти некоторое пересечение множеств или их объединение, соблюдая условия задачи. Метод Эйлера является незаменимым при решении некоторых задач, а также упрощает рассуждения. Но иногда с помощью арифметических действий задачу решить гораздо легче.
При решении задач с помощью алгебры логики обычно используется следующая схема решения:
изучается условие задачи;
вводится система обозначений для логических высказываний;
конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
определяются значения истинности этой логической формулы;
из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.