Теория недели 10.09 - 15.09.2012

Логика и графы. Высказывания. Логические операции. Кванторы общности. Описание графов. Пути в графах. Деревья. Множества

Решение логических задач с помощью рассуждений

Этим способом обычно решают несложные логические задачи.

Задача №1. Три девочки – Роза, Маргарита и Анюта представили на конкурсе корзины из выращенных ими роз, маргариток и анютиных глазок. Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием любимых цветов. Какие цветы вырастила каждая из девочек?

Решение.

  1. Девочка, вырастившая маргаритки, обратила внимание на то, что ни у одной из девочек имя не совпадает с названием выращенных цветов, поэтому можно записать следующие условия:
    а) Аня вырастила не анютины глазки.
    б) Маргарита вырастила не маргаритки.
    в) Роза вырастила не розы.
  2. Из диалога Розы и девочки, вырастившей маргаритки, следует, что Роза вырастила не маргаритки. Поэтому она могла вырастить либо розы, либо анютины глазки. Учитывая условие в), получаем, что Роза вырастила анютины глазки.
  3. В связи с условием б) и предыдущим выводом очевидно, что Маргарита вырастила розы.
  4. Следовательно, Аня вырастила маргаритки.

Ответ. Роза вырастила анютины глазки, Маргарита – розы, Аня – маргаритки.

Задача №2. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: «Вадим изучает китайский, Сергей не изучает китайский, Михаил не изучает арабский». Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?

Решение.

  1. Имеются три утверждения:
    а) Вадим изучает китайский;
    б) Сергей не изучает китайский;
    в) Михаил не изучает арабский.
  2. Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.
  3. Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно.
  4. Остается считать верным третье утверждение, а первое и второе – ложными. Следовательно, Вадим не изучает китайский, изучает китайский Сергей.
  5. Так как Михаил не изучает арабский, то он может изучать лишь японский. Тогда Вадим изучает арабский.

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

Решение логических задач средствами алгебры логики

Обычно используется следующая схема решения:

  1. изучается условие задачи;
  2. вводится система обозначений для логических высказываний;
  3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
  4. определяются значения истинности этой логической формулы;
  5. из полученных значений истинности формулы определяются значения истинности введенных логических высказываний, на основании которых делается заключение о решении.

Задача №3. Виновник ночного дорожно-транспортного происшествия скрылся с места аварии. Первый из опрошенных свидетелей сказал работникам ГИБДД, что это были «Жигули», первая цифра номера машины – единица. Второй свидетель сказал, что машина была марки «Москвич», а номер начинался с семерки. Третий свидетель заявил, что машина была иностранная, номер начинался не с единицы. При дальнейшем расследовании выяснилось, что каждый из свидетелей правильно указал либо только марку машины, либо только первую цифру номера. Какой марки была машина и с какой цифры начинался номер?

Решение.

Введем обозначения для логических высказываний: Ж – это «Жигули»; М – это «Москвич»; И – это иностранная машина; Е – номер машины начинается с единицы; С – номер машины начинается с семерки.


Для решения задачи нужно определить, при каких значениях логических переменных Ж, М, И, Е, С это высказывание истинно.

Упростим выражение, учитывая те обстоятельства, что машина не может быть одновременно и марки «Жигули», и марки «Москвич», и иностранного происхождения, а также то, что номер машины не может одновременно начинаться с единицы и с семерки:


При выводе мы также использовали закон противоречия и закон исключения констант.Высказывание истинно только при Ж=1, М=0, И=0, Е=0, С=1. Таким образом, мы установили, что виновником дорожно-транспортного происшествия была машина марки «Жигули», номер которой начинался с цифры семь.

Ответ. Машина марки «Жигули», номер которой начинался с цифры семь.

Задача №4. В клуб служебного собаководства на очередную тренировку пришли со своими собаками Антон, Борис, Петр, Виктор и Олег. Желая подшутить над новым инструктором, на вопрос: «Кто же хозяин каждой из собак?» каждый юноша дал один правильный и один неправильный ответ. Антон сказал: «Моя собака – Рекс, а собака Петра – Лайма». Борис сказал: «Рекс – моя собака, а собака Виктора – Джек». Петр сказал: «Собака Виктора – Зевс, а моя собака – Рекс». Виктор сказал: «Моя собака – Джек, а собака Олега – Бичо». Олег сказал: «Да, моя собака – Бичо, а собака Бориса – Зевс». Кто же на самом деле хозяин каждой собаки?

Решение.

Обозначим высказывательную форму «Юноша X – хозяин собаки Y» как и запишем получившиеся логические выражения. Из высказываний молодых людей и того факта, что одно из высказываний истинно, а другое ложно, следуют истинные составные высказывания:

Если все эти истинные высказывания логически перемножить, то получим следующее истинное высказывание:


Выполните преобразование этого высказывания с учетом того, что у каждого хозяина только одна собака и у каждой собаки только один хозяин.

В результате преобразований получим следующее равносильное высказывание:


которое истинно только при .

Ответ. Петр – хозяин Лаймы, Борис – Рекса, Виктор – Зевса, Олег – Бичо, Антон – Джека.

Решение логических задач с помощью таблиц

При использовании табличного способа условия, которые содержит задача, и результаты рассуждений фиксируются с помощью специально составленных таблиц.

Задача №1. Пятеро одноклассников – Ирена, Тимур, Камилла, Эльдар и Залим стали победителями олимпиад школьников по физике, математике, информатике, литературе и географии. Известно, что победитель олимпиады по информатике учит Ирену и Тимура работе на компьютере; Камилла и Эльдар тоже заинтересовались информатикой; Тимур всегда побаивался физики; Камилла, Тимур и победитель олимпиады по литературе занимаются плаванием; Тимур и Камилла поздравили победителя олимпиады по математике; Ирена сожалеет о том, что у нее остается мало времени на литературу. Победителем какой олимпиады стал каждый из этих ребят?

Решение.

1. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание. Так как одноклассников, участвующих в олимпиадах по различным предметам, пятеро, а предметов, по которым проводится олимпиада, тоже пять, то каждый из ребят может победить в олимпиаде только по одному предмету.

2. Из условий 1 и 2 следует, что Ирена, Тимур, Камилла и Эльдар не могут победить в олимпиаде по информатике. Следовательно, в олимпиаде по информатике победил Залим. Занесем это в таблицу, а оставшиеся клетки столбца «Информатика», а также оставшиеся клетки строки «Залим» заполним нулями. Занесем сведения, содержащиеся в высказываниях 3, 4 и 5 в таблицу.

Физика

Информатика

Математика

Литература

География

Ирена

 

0

 

 

 

Тимур

0

0

0

0

 

Камилла

 

0

0

0

 

Эльдар

 

0

 

 

 

Залим

0

1

0

0

0

3. Из таблицы видно, что Тимур – победитель олимпиады по географии.

Физика

Информатика

Математика

Литература

География

Ирена

 

0

 

 

0

Тимур

0

0

0

0

1

Камилла

 

0

0

0

0

Эльдар

 

0

 

 

0

Залим

0

1

0

0

0

4. Из таблицы видим, что Камилла является победителем по физике.

Физика

Информатика

Математика

Литература

География

Ирена

0

0

 

 

0

Тимур

0

0

0

0

1

Камилла

1

0

0

0

0

Эльдар

0

0

 

 

0

Залим

0

1

0

0

0

5. Из условия 6 следует, что Ирена не может победить в олимпиаде по литературе.

Физика

Информатика

Математика

Литература

География

Ирена

0

0

 

0

0

Тимур

0

0

0

0

1

Камилла

1

0

0

0

0

Эльдар

0

0

 

 

0

Залим

0

1

0

0

0

6. Из таблицы видно, что победителем олимпиады по математике является Ирена. Поэтому оставшиеся клетки столбца «Математика», а также оставшиеся клетки строки «Ирена» можно заполнить нулями. Также из таблицы видно, что Эльдар – победитель олимпиады по литературе. Итак, окончательно получим таблицу:

Физика

Информатика

Математика

Литература

География

Ирена

0

0

1

0

0

Тимур

0

0

0

0

1

Камилла

1

0

0

0

0

Эльдар

0

0

0

1

0

Залим

0

1

0

0

0

Ответ. Ирена – победитель олимпиады по математике; Тимур – победитель олимпиады по географии; Камилла – победитель олимпиады по физике; Эльдар – победитель олимпиады по литературе; Залим – победитель олимпиады по информатике.

Задача №2. Три дочери писательницы Дорис Кей – Джуди, Айрис и Линда тоже очень талантливы. Они приобрели известность в разных видах искусств – песни, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго. Известно, что:

1. Джуди живет не в Париже, а Линда – не в Риме;

2. Парижанка не снимается в кино;

3. Та, кто живет в Риме, певица;

4. Линда равнодушна к балету.

Где живет Айрис и какова ее профессия?

Решение.

1. Составим таблицу и отразим в ней условия 1 и 4, заполнив клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.

Париж

Рим

Чикаго

Пение

Балет

Кино

0

Джуди

Айрис

0

Линда

0

2. Далее рассуждаем следующим образом: так как Линда живет не в Риме, то, согласно условию 3, она не певица. Из таблицы сразу видно, что Линда киноактриса.

Париж

Рим

Чикаго

Пение

Балет

Кино

0

Джуди

0

Айрис

0

0

Линда

0

0

1

3. Согласно условию 2, парижанка не снимается в кино, значит, Линда живет не в Париже, но она живет и не в Риме. Следовательно, Линда живет в Чикаго. Так как Линда и Джуди живут не в Париже, там живет Айрис. Джуди живет в Риме и, согласно усло­вию 3, певица. А так как Линда киноактриса, то Айрис балерина. В результате постепенного заполнения получаем следующую таблицу.

Париж

Рим

Чикаго

Пение

Балет

Кино

0

1

0

Джуди

1

0

0

1

0

0

Айрис

0

1

0

0

0

1

Линда

0

0

1

Ответ. Айрис балерина. Она живет в Париже.

Решение логических задач с помощью графов

Многие логические задачи связаны с рассмотрением нескольких конечных множеств с одинаковым числом элементов. Между элементами множеств имеются некоторые зависимости, которые требуется установить. Для решения таких задач можно использовать графы.

Решим задачу №1 с помощью графов.

Решение.

1. Рассмотрим множество школьников (И, Т, К, Э, З) и множество предметов, по которым проводятся олимпиады (Ф, И, М, Л, Г). По условию задачи между элементами множеств существует взаимно-однозначное соответствие. Если в ходе задачи выясняется, что X выиграл  олимпиаду по предмету Y, то точки X и Y соединяются сплошным отрезком, в противном случае – пунктирным.

2. Согласно условиям 1, 2 и 3 ни Ирена, ни Камилла, ни Тимур, ни Эльдар не могут быть победителем олимпиады по информатике. Следовательно, Залим – победитель олимпиады по информатике. Соединим вершины графа «З» и «И» сплошным отрезком, а все остальные вершины, обозначающие название предметов, соединяем с вершиной «З» пунктиром.

 

3. Отобразим сведения, содержащиеся в высказываниях 3, 4 и 5 на графе.

 

4. Из графа видно, что Тимур – победитель олимпиады по географии. Следовательно, соединим вершины графа «Т» и «Г» сплошным отрезком, а все остальные вершины, обозначающие имена ребят, соединяем с вершиной «Г» пунктиром.

 

5. Из графа видно, что Камилла является победителем олимпиады по физике. Соединим вершины графа «К» и «Ф» сплошным отрезком, а все остальные вершины, обозначающие имена школьников, соединяем с вершиной «Ф» пунктиром. По условию 6 выясняется, что Ирена не является победителем олимпиады по литературе.

 

6. Из графа видно, что победителем олимпиады по математике является Ирена, то есть соединим вершины графа «И» и «М» сплошным отрезком.

 

7. Тогда Эльдар – победитель олимпиады по литературе. Имеем  конечный граф.

 

Ответ. Ирена – победитель олимпиады по математике; Тимур – победитель олимпиады по географии; Камилла – победитель олимпиады по физике; Эльдар – победитель олимпиады по литературе; Залим – победитель олимпиады по информатике.

Домашнее задание:

 

 

1. В поездке пятеро друзей – Антон, Борис, Вадим, Дима и Гриша познакомились с попутчицей. Они предложили ей отгадать их фамилии, причем каждый из них высказал одно истинное и одно ложное утверждение. Дима сказал: «Моя фамилия – Мишин, а фамилия Бориса – Хохлов». Антон сказал: «Мишин – это моя фамилия, а фамилия Вадима – Белкин». Борис сказал: «Фамилия Вадима – Тихонов, а моя фамилия – Мишин». Вадим сказал: «Моя фамилия – Белкин, а фамилия Гриши – Чехов». Гриша сказал: «Да, моя фамилия – Чехов, а фамилия Антона – Тихонов». Какую фамилию носит каждый из друзей?

2. На заводе работают три друга: слесарь, токарь, шлифовщик. Их фамилии: Борисов, Иванов, Семенов. У слесаря нет ни братьев, ни сестер, он самый младший из друзей. Семенов женат на сестре Борисова и старше токаря. У кого какая специальность?