Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



Цели:

  1. Обучающие:
    1. Научить решать логические задачи
  2. Развивающие:
    1. Развивать логическое мышление
    2. Развивать внимание
  3. Воспитывающие:
    1. Воспитывать дисциплинированность

Теоретическая часть

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

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

Пример. Трое друзей, болельщиков автогонок " Формула-1", спорили о результатах предстоящего этапа гонок.

— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

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

Решение. Введем обозначения для логических высказываний:

Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

Реплика Ника " Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывания каждого из друзей:

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

Высказывание истинно только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.


УРОК №19-20

Тема: Решение логических задач табличным способом.

Цели:

1. Обучающие:

1.Научить решать логические задачи

    1. Закрепить навыки решения логических задач

2. Развивающие:

1.Развивать внимание

3. Воспитывающие:

2. Воспитывать аккуратность ведения тетради

Теоретическая часть.

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

Пример 1. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.

Известно, что:

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

На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 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; Просмотров: 1733; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.092 с.)
Главная | Случайная страница | Обратная связь