|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Тема: Решение логических задач средствами алгебры логики.
Цели:
Теоретическая часть Обычно используется следующая схема решения:
Пример. Трое друзей, болельщиков автогонок " Формула-1", спорили о результатах предстоящего этапа гонок. — Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл. — Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым. Питер, к которому обратился Ник, возмутился: — Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину. По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки? Решение. Введем обозначения для логических высказываний: Ш — победит Шумахер; Х — победит Хилл; А — победит Алези. Реплика Ника " Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается. Зафиксируем высказывания каждого из друзей:
Учитывая то, что предположения двух друзей подтвердились, а предположения третьего неверны, запишем и упростим истинное высказывание
Высказывание Ответ. Победителем этапа гонок стал Шумахер. УРОК №19-20 Тема: Решение логических задач табличным способом. Цели: 1. Обучающие: 1.Научить решать логические задачи
2. Развивающие: 1.Развивать внимание 3. Воспитывающие: 2. Воспитывать аккуратность ведения тетради Теоретическая часть. При использовании этого способа условия, которые содержит задача, и результаты рассуждений фиксируются с помощью специально составленных таблиц. Пример 1. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе. Известно, что:
На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами? Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание. Так как музыкантов трoе, инструментов шесть и каждый владеет только двумя инструментами, получается, что каждый музыкант играет на инструментах, которыми остальные не владеют. Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна — альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов " альт" и " кларнет" заполним нулями: скрипка флейта альт кларнет гобой труба Браун 0 0 1 1 0 0 Смит 0 0 0 Вессон 0 0 Из таблицы видно, что на трубе может играть только Вессон. Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки " Вессон" можно заполнить нулями: скрипка флейта альт кларнет гобой труба Браун 0 0 1 1 0 0 Смит 0 0 0 0 Вессон 1 0 0 0 0 1 Из таблицы видно, что играть на флейте и на гобое может только Смит. скрипка флейта альт кларнет гобой труба Браун 0 0 1 1 0 0 Смит 0 1 0 0 1 0 Вессон 1 0 0 0 0 1 Ответ: Браун играет на альте и кларнете, Смит — на флейте и гобое, Вессон — на скрипке и трубе. Практическая часть. Пример 2. Три одноклассника — Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего — регби. Юра сказал, что на туризм ему не хватает времени, хотя его сестра — единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги. Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен. Определите, кто чем любит заниматься в свободное время и у кого какая профессия. Решение. Здесь исходные данные разбиваются на тройки (имя — профессия — увлечение). Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист. Имя Юра Профессия врач Увлечение туризм Буква " а", присутствующая в слове " врач", указывает на то, что Влад тоже не врач, следовательно врач — Тимур. В его имени есть буквы " т" и " р", встречающиеся в слове " туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени — Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы " ю" и " р". Следовательно, окончательно имеем:
Имя Юра Тимур Влад Профессия физик врач юрист Увлечение бег туризм регби Ответ. Влад — юрист и регбист, Тимур — врач и турист, Юра — физик и бегун. Пример 3. Три дочери писательницы Дорис Кей — Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств — пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго. Известно, что: Джуди живет не в Париже, а Линда — не в Риме; парижанка не снимается в кино; та, кто живет в Риме, певица; Линда равнодушна к балету. Где живет Айрис, и какова ее профессия? Решение. Составим таблицу и отразим в ней условия 1 и 4, заполнив клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание: Париж Рим Чикаго Пение Балет Кино 0 Джуди Айрис 0 Линда 0 Далее рассуждаем следующим образом. Так как Линда живет не в Риме, то, согласно условию 3, она не певица. В клетку, соответствующую строке " Линда" и столбцу " Пение", ставим 0. Из таблицы сразу видно, что Линда киноактриса, а Джуди и Айрис не снимаются в кино. Париж Рим Чикаго Пение Балет Кино 0 Джуди 0 Айрис 0 0 Линда 0 0 1 Согласно условию 2, парижанка не снимается в кино, следовательно, Линда живет не в Париже. Но она живет и не в Риме. Следовательно, Линда живет в Чикаго. Так как Линда и Джуди живут не в Париже, там живет Айрис. Джуди живет в Риме и, согласно условию 3, является певицей. А так как Линда киноактриса, то Айрис балерина. В результате постепенного заполнения получаем следующую таблицу: Париж Рим Чикаго Пение Балет Кино 0 0 1 Джуди 1 0 0 1 0 0 Айрис 0 1 0 0 0 1 Линда 0 0 1 Ответ. Айрис балерина. Она живет в Париже. Пример 4. Один из четырех мальчиков испортил выключатель. На вопрос «Кто это сделал? » были получены такие ответы: (1) «Это сделал или Миша, или Коля»; (2) «Это сделал или Витя, или Коля»; (3) «Это не могли сделать ни Толя, ни Миша»; (4) «Это сделал или Витя, или Миша». Можно ли по этим данным установить, кто виновен в поломке выключателя, если известно, что из четырех высказываний три истинны? Решение. Обозначим через М высказывание «Виноват Миша», В — «Виноват Витя», К — «Виноват Коля», Т — «Виноват Толя». Тогда ответы на вопрос о виновнике поломки описываются следующими формулами алгебры высказываний:
В первые четыре столбца таблицы поместим значения высказываний М, В, К и Т, в столбцы с 5-го по 8-й поместим значения высказываний (1) — (4). Так как виноват только один из четырех мальчиков, количество строк в таблице равно 4, причем первые четыре столбца таблицы содержат только по одному значению «истина» (единицу), а остальные — «ложь» (нуль). Значения в столбцах с 5-го по 8-й вычисляем в соответствии с записанными формулами. М в к т (1)(2)(3)(4) 1 0 0 0 1 0 0 1 0 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 Из таблицы видно, что возможны два варианта одновременной истинности трех ответов: из четырех строк таблицы две (2-я и 3-я) содержат по три единицы. Но эти строки соответствуют значениям истинности для высказываний В и К. Следовательно, виноват или Витя, или Коля, т. е. однозначно ответить на вопрос «Кто виноват? » при заданных условиях нельзя. Ответ. По ответам, данным мальчиками, определить виновника нельзя. Пример 5. Один из трех братьев — Витя, Толя или Коля — разбил окно. В разговоре участвуют еще два брата — Андрей и Дима. (1) — Это мог сделать только или Витя, или Толя, — сказал Андрей. (2) — Я окно не разбивал, — возразил Витя, — и Коля тоже. (3) — Вы оба говорите неправду, — заявил Толя. (4) — Нет, Толя, один из них сказал правду, а другой сказал неправду, — возразил Дима. (5) — Ты, Дима, не прав, — вмешался Коля. Их отец, которому, конечно, можно доверять, уверен, что трое из пяти братьев сказали правду. Кто же разбил окно? Решение. Обозначим через В высказывание «Окно разбил Витя», Т — «Окно разбил Толя», К — «Окно разбил Коля». Тогда высказывания участников разговора опишутся формулами:
Составим таблицу, поместив в первые три столбца значения высказываний В, Т, К, as столбцы с 4-го по 8-й — значения высказываний (1) — (5). Так как только один из братьев может быть виновником неприятного события, то возможны только три варианта значений для В, Т, К, поэтому таблица содержит три строки, в каждой из которых в первых трех столбцах одна единица и два нуля. Значения в остальных столбцах таблицы вычисляем в соответствии с записанными формулами. В Т к (1) (2) (3) (4) (5) 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1
Теперь воспользуемся истинностью утверждения отца о том, что правду сказали трое из пяти братьев. В соответствии с таблицей это возможно, только если окно разбил Толя (2-я строка). Ответ. Окно разбил Толя. Пример 6. Ключ от замка спрятан в одной из трех шкатулок — черной, белой или красной, — на крышках которых сделаны надписи: (1) на черной шкатулке: «Ключ не в белой шкатулке»; (2) на белой шкатулке: «Ключ не в этой шкатулке»; (3) на красной шкатулке: «Ключ в этой шкатулке». В какой шкатулке спрятан ключ, если известно, что из трех надписей на крышках по крайней мере одна истинна и по крайней мере одна ложна? Решение. Обозначим через Ч высказывание «Ключ в черной шкатулке», Б — «Ключ в белой шкатулке», К — «Ключ в красной шкатулке». Тогда надписи на шкатулках опишутся формулами: (1) Б; (2) Б; (3) К. Составим таблицу из шести столбцов, в первых трех из которых опишем все возможности нахождения ключа в одной из шкатулок, а в остальных — соответствующие значения надписей. Ч Б К (1)(2)(3) 1 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 1 Теперь, пользуясь дополнительной информацией о том, что по крайней мере одна надпись истинна и по крайней мере одна ложна, проанализируем 4-й, 5-й и 6-й столбцы таблицы. Условиям задачи удовлетворяет только первая строка таблицы. Следовательно, ключ спрятан в черной шкатулке. Ответ. Ключ спрятан в черной шкатулке.
Рассмотрим два подхода применения табличного метода к решению задач из серии «Кто где живет? » («Кто кем работает? », «Как составить расписание? » и т. д.). В задачах такого рода надо найти только одно истинное сложное конъюнктивное высказывание из всех подобных высказываний, описывающих возможные варианты. Первый подход основан на так называемом «тупом» переборе, второй — на переборе со стратегией (этот подход достаточно подробно описан в [2]). Пример 7. Три друга — Антонов, Вехов и Сомов — решили провести свой отпуск в трех различных городах — Москве, Санкт-Петербурге и Киеве. Можно ли определить, в какой город должен поехать каждый из них, если имеются следующие ограничения: (1) или Антонов не едет в Москву, или Сомов едет в Санкт-Петербург; (2) или Антонов едет в Москву и Вехов не едет в Киев, или Сомов едет в Санкт-Петербург; (3) если Антонов едет в Киев, то Сомов едет в Москву. При этом Вехов не едет в Санкт-Петербург; (4) если Вехов едет в Москву, то Антонов едет в Санкт-Петербург? Рассмотреть варианты, когда из этих ограничений: а) верны все; б) верны только два; в) верны только три. Решение. Обозначим через am, An и ак высказывания «Антонов едет в Москву», «Антонов едет в Санкт-Петербург» и «Антонов едет в Киев» соответственно. Аналогично определим высказывания Бм, Бп, Бк, См, Сп, Ск. В этих обозначениях ограничения из условия задачи опишутся формулами: Составим таблицу, содержащую 13 столбцов: в первые девять поместим значения am, Вм, См, An, Вп, Сп, ак, Вк, Ск, а в столбцы с 10-го по 13-й — значения, вычисленные по формулам (1) — (4). Единицы и нули в первых девяти столбцах расставляем так, чтобы перебрать все возможные варианты поездок друзей в города с учетом того, что каждый едет в какой-нибудь город и в один город едет только один из друзей. Получим шесть вариантов. Ам Вм См Аи Вп Сп Ак Вк Ск (1) (2) (3) (4) 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0 1 Анализируя таблицу, получаем ответ на вопрос задачи. Ответ. а) Можно, так как в случае, когда Антонов едет в Москву, Сомов — в Санкт-Петербург, а Вехов — в Киев, верны все ограничения (2-я строка таблицы); б) нельзя, так как ровно два ограничения верны в трех случаях (1-я, 4-я и 6-я строки); в) нельзя, так как ровно три ограничения верны в двух случаях (3-я и 5-я строки). Приведем решение этой задачи перебором со стратегией , используя табличный метод. Составим таблицу размера 3x3, столбцы которой обозначим фамилиями друзей, а строки — названиями городов: Города Фамилии
Антонов Вехов Сомов Москва Киев Санкт-Петербург Для решения задачи в случае а) надо так расставить единицы в этой таблице, чтобы в каждой ее строке и каждом столбце было ровно по одной единице и при этом формулы (1) — (4) были бы одновременно истинны. Из (1) выбираем истинность дизъюнкта Сп, который дает однозначный ответ о Сомове, и ставим единицу в соответствующую ячейку таблицы. Так как Сомов едет только в один город и в Санкт-Петербург едет только один из друзей, то заполняем нулями остальные строки 3-го столбца и столбцы 3-й строки. Города Фамилии
Антонов Вехов Сомов Москва 0 Киев 0 Санкт-Петербург 0 0 1 Формула (2) будет истинна в силу истинности Сп- В формуле (3) конъюнкт Bn истинен, а для истинности импликации Ак ® См мы должны выбрать вариант, при котором Ак ложно, так как См ложно. Таким образом, истинно должно быть am, т. е. Антонов должен ехать в Москву. Ставим единицу в соответствующую ячейку таблицы и нули в остальные ячейки по Москве и Антонову. Получаем единственную незаполненную ячейку, соответствующую поездке Вехова в Киев, в которую и ставим единицу. Города Фамилии
Антонов Вехов Сомов Москва 1 0 0 Киев 0 1 0 Санкт-Петербург 0 0 1 Проверяем истинность формулы (4). Она следует из ложности Вм. Таким образом, получили такой вариант ответа: Антонов едет в Москву, Вехов едет в Киев, Сомов едет в Санкт-Петербург. Чтобы убедиться в однозначности этого ответа, рассмотрим другие варианты истинности формулы (1). Города Фамилии
Антонов Вехов Сомов Москва 0 0 1 Киев 1 0 0 Санкт-Петербург 0 1 0 В представленном варианте получаем истинность формул (1) и (4) и ложность формул (2) и (3). Еще один вариант: Города Фамилии
Антонов Вехов Сомов Москва 0 1 0 Киев 0 0 1 Санкт-Петербург 1 0. 0 В этом варианте получаем истинность формул (1), (3) и (4) и ложность (2). Перебрав таким образом все варианты, мы получим однозначность ответа в случае а) и невозможность однозначного решения в случаях б) и в). Мы видим, что в этой задаче первоначальный «тупой» перебор оказался более эффективным и кратким в оформлении. Пример 8. При составлении расписания уроков на один день учителя математики, истории и литературы высказали следующие пожелания: (1) учитель математики просил поставить его урок в расписании или первым, или вторым; (2) учитель истории — или первым, или третьим; (3) учитель литературы — или вторым, или третьим. Как составить расписание уроков, чтобы учесть пожелания учителей? Решение. Обозначим через M1, M2 и Мз высказывания «Математика поставлена в расписании первым уроком», «Математика — второй урок», «Математика — третий урок» соответственно. Аналогично определим И1, И2, И3, Л1, Л2, Л3. В этих обозначениях пожелания учителей опишутся следующими формулами:
Так как каждый предмет должен стоять в расписании данного дня ровно один раз и можно считать, что в этот день первые три урока должны быть обязательно заняты этими предметами, то таблицу можно составить по аналогии с предыдущей задачей. Mi Hi Лг М2И2 Л2 МзИз Лз (1) (2) (3) 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1. 1. 1. 0 1 0 1 0 0 0 0 1 1! _ I 0 1 0 'о 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 В таблице во 2-й и 3-й строках в столбцах для (1) — (3) стоят все единицы. Следовательно, для удовлетворения всех пожеланий расписание можно составить двумя способами: первый урок — математика, второй — литература, третий — история или первый урок — история, второй — математика, третий — литература. Ответ . Расписание можно составить двумя способами: 1) первый урок —• математика, второй — литература, третий — история; 2) первый урок — история, второй — математика, третий — литература. Перебор со стратегией выбора варианта истинности формулы (1), аналогичный решению задачи 4, приводит к составлению двух таблиц размера 3x3, дающих оба варианта составления расписания. УРОК 21-22 Тема: Решение логических задач с помощью рассуждений. Цели: учить решать задачи с помощью рассуждений; сформулировать правила преобразования логических задач; |
Последнее изменение этой страницы: 2019-05-18; Просмотров: 2107; Нарушение авторского права страницы
истинно только при Ш=1, А=0, Х=0. 
