Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Решение логических задач

С ПОМОЩЬЮ ТАБЛИЧНОГО МЕТОДА

1) В школе разбито окно. Один свидетель говорит: «Если виновен Борис, то виновен и Дмитрий», другой: «Если виновен Дмитрий, то виновен и Борис», а третий – «Виновен только один из них: либо Борис, либо Дмитрий». Могут ли они все трое лгать? Могут ли они все трое говорить правду? Для решения этой задачи достаточно построить совместную таблицу для показаний трех свидетелей. Пусть Pозначает, что виновен Борис, а Q– что виновен Дмитрий.

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

2) Три ученика, Саша, Коля и Вова, прогуляли информатику. Когда их спросили, кому пришла в голову эта идея, они ответили следующее:

Саша: «Я никогда не призывал к прогулу, это была идея Коли».

Коля: «Я никогда не предложил бы это первым, во всем виноват Вова».

Вова: «Эта идея пришла в голову Коле. Я просто пошел за компанию».

Учитель почувствовал, что двое учеников говорят правду наполовину, а один – лжет. Кто из учеников был инициатором прогула?

Решение: У каждого мальчика два высказывания, запишем их в более формальном виде:

Саша: 1. Это не Саша. 2. Это Коля.

Коля:1. Это не Коля. 2. Это Вова.

Вова: 1. Это Коля. 2. Это не Вова.

Теперь предположим, что зачинщик – Саша; составим таблицу, где отметим истинность каждого высказывания единицей, а ложность – нулем:

Этот вариант уже подходит, потому что Саша оба раза солгал, а остальные сказали один раз правду, а второй – нет;

На всякий случай проверяем остальные варианты

Таким образом, Саша первым предложил прогулять урок, ответ – С.

№3 Накануне олимпиады по математике ученики разных классов высказали следующие предположения по поводу победы своих представителей:

10 «А» Максим победит, Борис – займет второе место;

10 «Б» Борис – третий, Николай – первый;

10 «В» Максим – последний, а первый – Дмитрий.

Когда олимпиада закончилась, оказалось, что каждый из классов был прав только в одном из своих прогнозов. Какое место на олимпиаде заняли Дмитрий, Николай, Борис, Максим?

Решение: Запишем высказывания трех классов в форме таблицы (заголовок строки обозначает место на олимпиаде):

Считая, что два человека не могут оказаться на одном месте, начнем «раскручивать» эту таблицу с той строчки, где больше всего информации (в данном случае – с первой). Предположим, что Максим действительно занял первое место, как и сказал 10 «A»; в этом случае 10 «В» ошибся, поставив на первое место Дмитрия. Учитывая, что каждый один раз угадал, а второй ошибся, получается, что 10 «В» угадал, что Максим будет на четвертом месте. Но мы предположили, что Максим – на первом месте (а не на четвертом), следовательно, получили противоречие; это значит, что Максим все-таки не на первом месте. Таким образом, в первом прогнозе 10 «А» ошибся, это значит, что во втором он угадал, и Борис действительно занял второе место:

Так как Борис – второй, он не может быть на третьем месте, поэтому из прогноза 10 «Б» следует, что Николай – первый:

Если Николай на первом месте, там не может быть Дмитрий, поэтому из ответов 10 «В» (среди которых должен быть один верный, и один неверный), сразу находим, что Максим занял четвертое место:

Осталось только определиться с Дмитрием – ему досталось единственное «свободное» третье место; окончательный список победителей:

1. Николай 2. Борис 3. Дмитрий 4. Максим

С ПОМОЩЬЮ РАССУЖДЕНИЙ

1) Классный руководитель пожаловался директору, что у него в классе появилась компания из 3-х учеников, один из которых всегда говорит правду, другой всегда лжет, а третий говорит через раз то ложь, то правду. Директор знает, что их зовут Коля, Саша и Миша, но не знает, кто из них правдив, а кто – нет. Однажды все трое прогуляли урок астрономии. Директор знает, что никогда раньше никто из них не прогуливал астрономию. Он вызвал всех троих в кабинет и поговорил с мальчиками. Коля сказал: «Я всегда прогуливаю астрономию. Не верьте тому, что скажет Саша». Саша сказал: «Это был мой первый прогул этого предмета». Миша сказал: «Все, что говорит Коля, – правда». Директор понял, кто из них кто.Определите кто «говорит всегда правду», «всегда лжет», «говорит правду через раз».

Решение:

Во-первых, есть «точная» информация, которая не подвергается сомнению: все трое прогуляли урок астрономии в первый раз(*).

Запишем высказывания мальчиков:

Коля: 1. Я всегда прогуливаю астрономию, 2. Саша врет.

Саша: 1. Я в первый раз прогулял астрономию.

Миша: 1. Коля говорит правду.

Известно, что один из них все время лжет, второй – говорит правду, а третий говорит правду через раз (то есть, из двух его высказываний одно истинно, а второе – ложно; если у нас есть только одно высказывание «полу-лжеца», оно может быть как истинным, так и ложным). Сопоставив первое высказывание Коли и высказывание Саши с «точной» информацией (*), сразу определяем, то тут Коля соврал, а Саша сказал правду; это значит, что второе высказывание Коли – тоже неверно, поэтому мальчик Коля всегда лжет. Тогда один из оставшихся, Саша или Миша, говорит правду всегда, а второй – через раз

Мишино высказывание неверно, поскольку мы уже определили, что Коля лжет; это значит, что Миша не всегда говорит правду, он – «полу-лжец». Тогда получается, что Саша всегда правдив, и действительно, его высказывание верно, таким образом, верный ответ – Саша – правдив, Коля – лжец, Миша – «полу-лжец».

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

Решение: Запишем высказывания:

Сразу заметим, что высказывание 3 (Виктор – редактор) неверно, потому что иначе оказывается верным и высказывание 4, чего не может быть по условию (верно только одно высказывание)

Если Рома – староста (высказывание 1 верно), то остальные высказывания – неверны; поэтому Сергей – заместитель (из 2) и Виктор – не редактор (из 3), а староста; но тогда получается, что некому быть редактором и в классе 2 старосты; значит, это предположение неверно

Теперь предположим, что Сергей – не заместитель; отсюда следует, что Рома – не староста (из 1), а Виктор – староста (из 4) и не редактор (из 3); это может быть, если Рома – заместитель, а Сергей – редактор.

На всякий случай проверим последний вариант – предположим, что Виктор – не староста (высказывание 4 истинно, а остальные – ложны); сразу получаем, что Виктор – не редактор (из 3), Сергей – заместитель (из 2), а Рома – не староста (из 1); в этом случае два претендента на должность заместителя (Сергей и Виктор), а старосты нет вообще, поэтому это неверный вариант. Таким образом, правильный ответ – Виктор – староста, Рома – заместитель, а Сергей – редактор.

3) Преподаватель проверил работы трех учащихся, но не взял их с собой на занятия. Учащимся он сказал: вы все получили разные оценки:3, 4, 5. У Васильева не 4, у Сергеева не 5, а вот у Алексеева, по-моему 4. Впоследствии оказалось, что преподаватель, верно, высказался об оценке только одного учащегося. У кого какая оценка?

Решение:

Таким образом,Васильев — 4, Сергеев — 3, Алексеев — 5.

С ПОМОЩЬЮ СРЕДСТВ АЛГЕБРЫ ЛОГИКИ

1) При составлении расписания на понедельник преподаватели просили, чтобы уроки проходили в следующем порядке:

а) математика первым или третьим уроком;

б) история - первым или вторым;

в) литература - вторым или третьим.

Можно ли удовлетворить просьбы всех трех преподавателей и каким образом, если это возможно?

Введем следующие элементарные высказывания:

А - математика – I урок

В - математика - III урок

С - история - II урок

D - история - I урок

E - литература - II урок

F - литература - III урок

Просьбы всех преподавателей выражены высказываниями:

S₁=А∨В, S₂=C∨D, S₃=E∨D.

Высказывание, удовлетворяющее просьбы всех трех преподавателей, очевидно, есть конъюнкция S₁, S₂, S₃, т.е. S = S₁ & S₂ & S₃ и оно должно быть истинным, т.е. S=1. Применим дистрибутивный закон в преобразованиях S:

S=(A∨B) & (C∨D) & (E∨F)=(A&C∨B&C∨A&D∨B&D) & (E∨F)

В данном случае конъюнкция A&D=0, т.к. первым уроком математика и история одновременно быть не могут.

S=A&C&Е∨B&C&Е∨B&D&Е∨A&C&F∨B&C&F∨B&D&F

Очевидно А&С&Е=0, т.к. С&Е=0: второй урок не может быть одновременно уроком истории и литературы. Аналогично: В&С&Е=0, B&C&F=0, B&D&F=0, т.е. S= B&D&Е∨A&C&F=1.

Дизъюнкция истинна, если одно из слагаемых истинно: B&D&Е=1; A&C&F=1.

Конъюнкция высказываний истинна, если истинны все входящие в нее сомножители. В результате получаем два возможных варианта ответа:

а) B&D&Е=1, т.е. история – I урок,

литература – II урок,

математика – III урок.

б) A&C&F=1, т.е. математика – I урок

история - II урок,

литература - III урок.

2) Мама, прибежавшая на звон разбившейся вазы, застала всех трех своих сыновей в совершенно невинных позах: Саша, Ваня и Коля делали вид, что происшедшее к ним не относится. Однако футбольный мяч среди осколков явно говорил об обратном.

– Кто это сделал? – спросила мама.

– Коля не бил по мячу, – сказал Саша. – Это сделал Ваня.

Ваня ответил: – Разбил Коля, Саша не играл в футбол дома.

– Так я и знала, что вы друг на дружку сваливать будете, рассердилась мама. Ну, а ты что скажешь? – спросила она Колю.

– Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки, – сказал Коля.

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

Решение: Введем простые высказывания:

С - вазу разбил Саша

В - вазу разбил Ваня

К - вазу разбил Коля

Запишем с помощью этих обозначений утверждения мальчиков:

Саша: 1. К 2. В

Ваня: 1. К 2. С

Коля: 1. В

Читаем условие: «один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду»;

Как записать «Саша два раза солгал»? В этом случае оба его утверждения неверны, поэтому К=0 и В=0, что равносильно К & В=1.

«Саша два раза сказал правду»? в этом случае оба его утверждения неверны, поэтому К=1 и В=1, что равносильно К &В=1.

Если Коля солгал, а Саша и Ваня сказали правду, то К &В=1 и К & С=1 и В=1.

Заменив «И» на умножение, получаем К&В&К&С&В=1, учитывая, что К&К=0, получаем в левой части равенства ноль; так как в правой части – единица, этого не может быть (равенство ложно при любых значениях К, С, В).

Если Ваня солгал, а Саша и Коля сказали правду, то К&В=1 и К &С=1 и В=1, заменив «И» на умножение, получаем К&В&К&С&В=1, учитывая, что В&В=0, получаем, что это равенство ложно при любых значениях К, С, В (этого не может быть).

Остается последний возможный вариант: если Саша оба раза солгал, а Ваня и Коля сказали правду, то К&В=1 и К&С=1 и В=1, заменив «И» на умножение, получаем К&В&К&С&В=1, упростив это выражение с учетом равенств К&К=К и В&В=В, получим К&В&С=1, то есть, при этом предположении вазу разбил Коля, а не Ваня и не Саша. Таким образом, вазу разбил Коля.

3) Пытаясь вспомнить победителей прошлогоднего турнира, пять бывших зрителей турнира заявили:

1. Антон был вторым, а Борис пятым.

2. Виктор был вторым, а Денис третьим.

3. Григорий был первым, а Борис третьим.

4. Антон был третьим, а Евгений шестым.

5. Виктор был третьим, а Евгений четвертым.

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

Решение: Обозначим высказывания зрителей символом Ху, где Х- первая буква имени участника турнира, а у - номер места, которое он занял в турнире. Так как в паре высказываний каждого зрителя одно истинно, а второе ложно, то будут истинными дизъюнкции этих высказываний: А₂ v Б₅; В₂ v Д₃; Г₁ v Б₃; А₃ v Е₆; В₃ v Е₄. Но тогда будет истинной и формула

F = (А₂vБ₅)&(В₂vД₃)&(Г₁vБ₃)&(А₃vЕ₆)&(В₃vЕ₄).

Путем простых равносильных преобразований легко показать, что F=Б₅ & В₂ & Г₁ & А₃ &Е₄=1, и значит Б₅=1; В₂=1; Г₁=1; А₃=1; Е₄=1, что и дает ответ на вопрос задачи. Автоматически получаем, что Денис был шестым.