Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Цели:

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) учитель литературы — или вторым, или третьим.

Как составить расписание уроков, чтобы учесть пожелания учителей?

Решение.

Обозначим через M₁, M₂ и Мз высказывания «Математика поставлена в расписании первым уроком», «Математика — второй урок», «Математика — третий урок» соответственно. Аналогично определим И1, И2, И3,Л1, Л2, Л3.

В этих обозначениях пожелания учителей опишутся следующими форму­лами:

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

Mi Hi Лг М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

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

Цели:  учить решать задачи с помощью рассуждений;

сформулировать правила преобразования логических задач;