Э Логические задачи Е Г Школа 58 Иванцова С.А., МОУ СОШ 58, г.Н.Новгород

В этой презентации приводятся тренировочные задания из нескольких источников: открытого сегмента федерального банка тестовых заданий, демонстрационных вариантов ЕГЭ прошлых лет, материалов К. Ю. Полякова, учебного пособия «ЕГЭ Информатика» (Крылов С.С., Лещинер В.Р., Якушкин П.А. - М.: Интеллект-Центр, 2007). Презентация содержит систематизированную информацию из различных источников, а также разработки автора в виде необходимых для исследования темы курса рекомендаций и решения ряда задач. Цель данной работы помочь вам «набить руку» в решении тестов ЕГЭ, разобраться с наиболее сложными заданиями и узнать объективный уровень своих знаний.

Что нужно прежде всего знать: 1. условные обозначения логических операций ¬А, не А, отрицание (инверсия) A B, A и B, A B логическое умножение (конъюнкция) A B, A или B, A + B логическое сложение (дизъюнкция) A B импликация (следование) А В, А В, А~В логическое равенство (эквивалентность) 2. таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквивалентность» 3. операцию «импликация» можно выразить через «ИЛИ» и «НЕ»: A B = ¬ A B или в других обозначениях A B = 4. приоритеты логических операций: 1. Скобки 2. Инверсия 3. Конъюнкция 4. Дизъюнкция 5. Импликация 6.Эквивалентность

Правила, законы алгебры логики

Что нужно прежде всего знать: Можно выделить несколько основных способов решения логических задач: 1. Алгебраический – с применением законов алгебры логики, таблиц истинности – способ технологичный, универсальный, но бывает порой громоздким, сложным. Решение начинается с задания логических переменных, получению логических выражений, соответствующих условию задачи и дальнейшему упрощению данных логических выражений с целью достижения определённых выводов. 2. Метод устных логических рассуждений – начинается с поиска неоспоримого факта (или, наоборот, самого спорного предположения) из условия задачи, сопровождается возникающими по ходу рассуждений противоречиями, что приводит к определённым выводам. Это наиболее популярный, простой способ, но имеет фактор риска, т.к. устные логические рассуждения не всегда корректны и порой приводят к неправильным выводам. Этого можно избежать, если применять наглядные, графические методы решения задач. 3. С применением наглядного, графического представления информации, что ускоряет и облегчает процесс решения задач: метод таблиц; метод графов. метод диаграмм (основан на применении теории множеств).

Метод таблиц, технология решения: Из условия задачи определяем: - из скольких строк и столбцов будет состоять таблица; - какую смысловую нагрузку будут иметь эти строки и столбцы; На основе возможных предположений (обычно в строках таблицы) рассуждаем об истинности и ложности утверждений из условия задачи (обычно в столбцах таблицы); Если предположение истинно, то ставим «+», «1», а если ложное, то «-», «0». В результате должен получится ответ, соответствующий условию задачи. Способ таблиц удобен, нагляден, но не обладает универсальностью, т. к. предназначен для решения только определенного класса задач.

Метод графов, возможная технология решения: Метод графов применяется тогда, когда между объектами существует много связей. Граф позволяет наглядно представить эти связи и определить, какие из них не противоречат условиям задачи. Иногда определённое предположение является «вершиной» графа, от которой отходят «ветки» - возможные выводы. Часть направлений, возможно, ведут в тупик из-за возникающих противоречий. Часть направлений приводит к искомым решениям. Метод графов позволяет увидеть различные подходы к решению задачи, что позволяет найти несколько вариантов решения и выбрать из них наиболее оптимальный. 1. Исходные данные записывают в разные столбцы (строки). 2. Рассуждают и об истинности ложности предположений. 3. Если предположение истинно, то значение столбиков соединяется стрелочкой, а если ложное, то пунктирной стрелочкой. 4. В результате должен получиться правильный ответ, соответствующий условию задачи

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

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

Пример 2:

Правильный ответ: Миша(М), т.к. только первая строка таблицы соответствует условию задачи о правдивости утверждений мальчиков, т.е. Миша соврал наполовину (01), Коля оба факта исказил (00), Сергей сказал чистую правду (11). Ответ М: Ответ К: Ответ С: Если разбил М Если разбил К10 Если разбил С11 00 Решение - методом таблиц: В таблице каждая строка отражает положение дел в случае предположения факта: пусть стекло разбил Миша, Коля или Сергей соответственно, а каждый столбец соответствует высказыванию Миши, Коли и Сергея (1 – истина, 0 – ложь). Пример 2:

Пример 3: Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров: А) Макс победит, Билл – второй; В) Билл – третий, Ник – первый; С) Макс – последний, а первый – Джон. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс? (В ответе перечислите подряд без пробелов места участников в указанном порядке имен.) Решение (метод таблиц - предложен К.Ю. Поляковым) 1. Запишем высказывания трех болельщиков в форме таблицы (номер строки обозначает место в турнирной таблице): ABC 1Макс НикДжон 2Билл 3 4Макс 1.Считая, что два человека не могут оказаться на одном месте, начнем «раскручивать» эту таблицу с той строчки, где больше всего информации (в данном случае – с первой)

Предположим, что Макс действительно занял первое место, как и сказал «A»; в этом случае «C» ошибся, поставив на первое место Джона. Учитывая, что каждый один раз угадал, а второй ошибся, получается, что «C» угадал, что Макс будет на четвертом месте. ABC 1Макс НикДжон 2Билл 3 4Макс Но мы предположили, что Макс – на первом месте (а не на четвертом), следовательно, получили противоречие; это значит, что Макс все-таки не на первом месте. Таким образом, в первом прогнозе «А» ошибся, это значит, что во втором он угадал, и Билл действительно занял второе место. Так как Билл – второй, он не может быть на третьем месте, поэтому из прогноза «Б» следует, что Ник – первый. Если Ник на первом месте, там не может быть Джон, поэтому из ответов «С» (среди которых должен быть один верный, и один неверный), сразу находим, что Макс занял четвертое место. Осталось только определиться с Джоном – ему досталось единственное «свободное» третье место; окончательный список победителей: 1. Ник 2. Билл 3. Джон 4. Макс Места победителей в порядке их перечисления в тексте вопроса: Джон – 3, Ник – 1, Билл – 2, Макс - 4 Таким образом, правильный ответ 3124

Пример 3: Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров: А) Макс победит, Билл – второй; В) Билл – третий, Ник – первый; С) Макс – последний, а первый – Джон. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс? (В ответе перечислите подряд без пробелов места участников в указанном порядке имен.) Решение (метод графов) 1. Запишем высказывания трех болельщиков в форме таблицы (номер строки обозначает имя участника турнира Джон, Ник, Билл, Макс): ABC Д1 Н1 Б23 М14 Считая, что одно место в турнире не может быть занято несколькими участниками, начинаем «раскручивать» эту таблицу с первого места как наиболее «критичного». Пусть Джон – первый:

Противоречие, следовательно Если Джон не первый, тогда пусть Ник первый: Пример 3: ABC Д1 Н1 Б23 М14 Д1Б3 Б2 Н1 М4 Б2 Д3 Джону досталось единственное «свободное» третье место. Места победителей в порядке их перечисления в тексте вопроса: Джон – 3, Ник – 1, Билл – 2, Макс – 4 Таким образом, правильный ответ 3124 Итак, пусть Джон – первый: Решение (метод графов)

Мама, прибежавшая на звон разбившейся вазы, застала всех трех своих сыновей в совершенно невинных позах: Саша, Ваня и Коля делали вид, что происшедшее к ним не относится. Однако футбольный мяч среди осколков явно говорил об обратном. – Кто это сделал? – спросила мама. – Коля не бил по мячу, – сказал Саша. – Это сделал Ваня. Ваня ответил: – Разбил Коля, Саша не играл в футбол дома. – Так я и знала, что вы друг на дружку сваливать будете, рассердилась мама. Ну, а ты что скажешь? – спросила она Колю. – Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки, – сказал Коля. Оказалось, что один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду. Кто разбил вазу? Пример 4: Решение (метод логических рассуждений): Запишем высказывания трех мальчиков в краткой форме: Саша: 1. это не Коля 2. это Ваня Ваня: 1. это Коля 2. это не Саша Коля: 1. это не Ваня

Решение (метод логических рассуждений - предложен К.Ю. Поляковым) Запишем высказывания трех мальчиков в краткой форме: Саша: 1. это не Коля 2. это Ваня Ваня: 1. это Коля 2. это не Саша Коля: 1. это не Ваня У Коли всего одно высказывание, которое «относится к делу» и то, что он сделал или не сделал уроки, никак не проясняет ситуацию с разбитой вазой. Итак, двое мальчиков сказали правду: это не могут быть Саша и Ваня, потому что их первые высказывания противоречат одно другому. Это не могут быть Саша и Коля, поскольку высказывание Коли противоречит второму высказыванию Саши, поэтому правду сказали Ваня и Коля, а Саша – соврал. Таким образом, вазу разбил Коля Пример 4:

Решение (метод таблиц): Запишем высказывания трех мальчиков в краткой форме: Саша: 1. это не Коля 2. это Ваня Ваня: 1. это Коля 2. это не Саша Коля: 1. это не Ваня Каждая строка таблицы соответствует предположению: пусть кто-то из мальчиков разбил вазу: СВК Саш а Ваня Коля По условию задачи «один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду» соответствует третья строка, следовательно вазу разбил Коля Пример 4:

Пример 5: Три свидетеля дорожного происшествия сообщили сведения о скрывшемся нарушителе. Боб утверждает, что тот был на синем "Рено", Джон сказал, что нарушитель уехал на черной "Тойоте", а Сэм показал, что машина была точно не синяя и, по всей видимости, это был "Форд". Когда удалось отыскать машину, выяснилось, что каждый из свидетелей точно определил только один из параметров автомобиля, а в другом ошибся. Какая и ка­кого цвета была машина у нарушителя? Ответ запишите в виде двух слов, разделенных пробелом: МАРКА ЦВЕТ. Например: ЖИГУЛИ БЕЛЫЙ. Решение (с применением законов логики) Обозначим высказывания: А - "машина синего цвета"; В - "машина была "Рено"; С ="машина черного цвета"; D = "машина была "Тойота"; Е ="машина была "Форд".

Решение (1 способ: с применением законов логики) Согласно условию: Раскрывая скобки, получим: Из полученных восьми слагаемых семь (согласно условию задачи) являются ложными, остается единственное истинное слагаемое (подчеркнуто): B C A=1 Значит, нарушитель скрылся на автомобиле «Рено» черного цвета. Ответ: Рено черный Пример 5: Обозначим высказывания: А - "машина синего цвета"; В - "машина была "Рено"; С ="машина черного цвета"; D = "машина была "Тойота"; Е ="машина была "Форд".

Решение (2 способ: методом логических рассуждений) Боб ДжонСэм Боб Джон Сэм Удобнее начать с противоречивых утверждений о том, что машина синяя. Если Боб прав, что машина синего цвета, то это не «Рено», а Сэм врёт, что она не синяя, то тогда это «Форд». Но тогда получается, что Джон врёт во всём, что не соответствует условию задачи. Значит, Боб не прав, что машина синяя, но тогда это «Рено». Поэтому утверждение Джона, марка машины – «Тайота» – ложь, значит, машина чёрная. Пример 5: Боб: 1. машина синяя 2. это «Рено» Джон: 3. машина чёрная 4. это «Тайота» Сэм: 5. машина не синяя 6. это «Форд» Таблица осталась незаполненной, т.к. несложные логические рассуждения в верном направлении быстро привели к результату.

Три друга: Алеша, Сережа и Денис купили щенков разной породы (колли, ротвейлер и овчарку) и дали им клички (Лесси, Джек и Гриф). Известно, что 1. щенок Алеши темнее по окраске, чем овчарка, Лесси и Джек; 2. щенок Сережи старше Джека, ротвейлера и овчарки. Какой породы щенок и с какой кличкой у каждого из ребят? Пример 6: Решение (метод графов):

1. щенок Алеши темнее по окраске, чем овчарка, Лесси и Джек; 2. щенок Сережи старше Джека, ротвейлера и овчарки. Колли Ротвейлер Денис Сережа Лесси Джек Гриф Овчарка Алеша Из условия задачи мы видим: у Алеши не овчарка,не Лесси,и не Джек. У Сережи не Джек,не ротвейлер, и не овчарка. Если у Алеши не Лесси и не Джек, то у него Гриф. У Сережи не ротвейлер и не овчарка, значит у него колли. У Сережи колли, а у Алеши не овчарка, значит у него ротвейлер. Следовательно у Дениса овчарка. У Алеши Гриф, а у Сережи не Джек, значит у него Лесси. У Дениса Джек. Ответ: У Алеши ротвейлер по кличке Гриф. У Сережи колли по кличке Лесси. У Дениса овчарка по кличке Джек.

Пример 7: В понедельник в одном из классов должно быть проведено 4 урока - по математике, физике, информатике и биологии. Учителя высказали свои пожелания для составления расписания. Учитель математики хочет иметь первый или второй урок, учитель физики - второй или третий урок, учитель информатики - первый или четвертый, учитель биологии - третий или четвертый. Какой вариант расписания устроит всех учителей школы? (Обозначения: М - математика, Ф - физика, И- информатика, Б - биология) 1) ИМБФ 2) МФБИ 3) МИФБ 4) МБФИ Пожелания учителей: М (1, 2)Ф (2,3)И (1,4)Б (3,4) ИМБФ +-++ МФБИ ++++ МИФБ ++-+ МБФИ +++- Решение (метод таблиц): Структурируем исходные данные в виде таблицы и проверим различные варианты расписания уроков на их соответствие пожеланиям учителей: Правильный ответ - 2

Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин A, B, C. На первом месте – одна из бусин B, D, C, которой нет на третьем месте. В середине – одна из бусин А, C, E, B, не стоящая на первом месте. Какая из перечисленных цепочек создана по этому правилу? 1)CBB 2) EAC 3)BCD 4) BCB Решение (метод таблиц): Правило содержит три условия, обозначим их так: У1: третья бусина – A, B или C У2-3: первая бусина – B, D или C, не совпадающая с третьей У4-5: вторая бусина – A, B, C или E, не совпадающая с первой Фактически условия У2-3 и У4-5 сложные, их можно разбить на два, так что получится всего пять условий: У1: третья бусина – A, B или C У2: первая бусина – B, D или C У3: первая и третья бусины – разные У4: вторая бусина – A, B, C или E У5: первая и вторая бусины – разные Пример 8:

Решение (метод таблиц): У1: третья бусина – A, B или C У2: первая бусина – B, D или C У3: первая и третья бусины – разные У4: вторая бусина – A, B, C или E У5: первая и вторая бусины – разные Теперь для каждого из ответов проверим выполнение всех условий. В таблице красный крестик обозначает, что условие не выполняется для данного варианта. Серым цветом выделена строка, где нет ни одного крестика, то есть все условия выполняются: Таким образом, правильный ответ – 1. Пример 8: У1У2У3У4У5 1) CBB 2) EAC 3) BCD 4) BCB

Цепочка из трех бусин формируется по следующему правилу: На первом месте в цепочке стоит одна из бусин А, Б, В. На втором - одна из бусин Б, В, Г. На третьем месте - одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте. Какая из следующих цепочек создана по этому правилу: 1)АГБ 2) ВАГ 3) БГГ 4) ББГ Решение (метод таблиц): Правило содержит три условия: У1: На первом месте в цепочке стоит одна из бусин А, Б, В. У2: На втором - одна из бусин Б, В, Г. У3: На третьем месте - одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте. Пример 9: У1У2У3 1) АГБ х 2) ВАГ х 3) БГГ х 4) ББГ В цепочке «АГБ» нарушено правило третьей буквы. В цепочке «ВАГ» нарушено правило второй буквы В цепочке «БГГ» нарушено правило третьей буквы. В цепочке «ББГ» всё правильно. Правильный ответ - 4

Пример 10: Для составления цепочек используются бусины, помеченные буквами: М, N, О, Р, S. В середине цепочки стоит одна из бусин М, О, S. На третьем - любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На первом месте - одна из бусин О, Р, S, не стоящая в цепочке в середине. Какая из перечисленных цепочек создана по этому правилу? 1) SMP 2) MSO 3) SNO 4) OSN Решение (метод таблиц): Правило содержит три условия: У1: В середине цепочки стоит одна из бусин М, О, S. У2: На третьем - любая гласная, если первая буква согласная, и любая согласная, если первая гласная. У3: На первом месте - одна из бусин О, Р, S, не стоящая в цепочке в середине. У1У2У3 1) SMP x 2) MSO x 3) SNO x 4) OSN Правильный ответ - 4

Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке стоит одна из бусин A, C, E. На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте – одна из бусин C, D, E, не стоящая в цепочке на первом месте. Какая из перечисленных цепочек создана по этому правилу? 1) CBE 2) ADD 3) ECE 4) EAD Решение (метод таблиц): Можно составить по условию задачи несколько утверждений: У1: На первом месте в цепочке стоит одна из бусин A, C, E. У2: На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. У3: На третьем месте – одна из бусин C, D, E, не стоящая в цепочке на первом месте. Пример 11: 1) CBE 2) ADD 3) ECE 4) EAD У1: У2:хх У3:х х – утверждение ложно. Свободен от «х» только второй столбец. Ответ: 2) ADD

На одной улице стоят в ряд 4 дома, в которых живут 4 человека: Алексей, Егор, Виктор и Михаил. Известно, что каждый из них владеет ровно одной из следующих профессий: Токарь, Столяр, Хирург и Окулист, но неизвестно, кто какой и неизвестно, кто в каком доме живет. Однако, известно, что: 1) Токарь живет левее Столяра 2) Хирург живет правее Окулиста 3) Окулист живет рядом со Столяром 4) Токарь живет не рядом со Столяром 5) Виктор живет правее Окулиста 6) Михаил не Токарь 7) Егор живет рядом со Столяром 8) Виктор живет левее Егора Выясните, кто какой профессии, и кто где живет, и дайте ответ в виде заглавных букв имени людей, в порядке слева направо. Например, если бы в домах жили (слева направо) Константин, Николай, Роман и Олег, ответ был бы: КНРО Решение (метод логических рассуждений): Из п.3) следует одно из ОС или СО. Из п.1), п. 4) следует ТОС (ТСО невозможно из-за п. 4) ) Из п.2) следует ТОСХ Из п.5) следует, что В=С или В=Х Из п.8) следует, что В не может быть последним (т.е. ВХ), тогда В=С, а Е=Х Из п.6) следует, что М=¬Т, следовательно М=О, следовательно А=Т Итак, ТОСХ и А=Т, М=О, В=С, Е=Х, следовательно, ответ - АМВЕ Пример 12:

На одной улице стоят в ряд 4 дома, в которых живут 4 человека: Алексей, Егор, Виктор и Михаил. Известно, что каждый из них владеет ровно одной из следующих профессий: Токарь, Столяр, Хирург и Окулист, но неизвестно, кто какой и неизвестно, кто в каком доме живет. Однако, известно, что: 1) Токарь живет левее Столяра 2) Хирург живет правее Окулиста 3) Окулист живет рядом со Столяром 4) Токарь живет не рядом со Столяром 5) Виктор живет правее Окулиста 6) Михаил не Токарь 7) Егор живет рядом со Столяром 8) Виктор живет левее Егора Решение (метод графов): Токарь Столяр Хирург Окулист Токарь Столяр Окулист Хирург Токарь Окулист Столяр Хирург Алексей Егор Виктор Михаил Пример 12: Выясните, кто какой профессии, и кто где живет, и дайте ответ в виде заглавных букв имени людей, в порядке слева направо. Например, если бы в домах жили (слева направо) Константин, Николай, Роман и Олег, ответ был бы: КНРО На одной улице стоят в ряд 4 дома, в которых живут 4 человека: Алексей, Егор, Виктор и Михаил. Известно, что каждый из них владеет ровно одной из следующих профессий: Токарь, Столяр, Хирург и Окулист, но неизвестно, кто какой и неизвестно, кто в каком доме живет. Однако, известно, что: 1) Токарь живет левее Столяра 2) Хирург живет правее Окулиста 3) Окулист живет рядом со Столяром 4) Токарь живет не рядом со Столяром 5) Виктор живет правее Окулиста 6) Михаил не Токарь 7) Егор живет рядом со Столяром 8) Виктор живет левее Егора Решение : Токарь Столяр Хирург Окулист Токарь Столяр Окулист Хирург Токарь Окулист Столяр Хирург Алексей Егор Виктор Михаил Алексей Виктор Егор Михаил Алексей Михаил Виктор Егор ответ - АМВЕ Выясните, кто какой профессии, и кто где живет, и дайте ответ в виде заглавных букв имени людей, в порядке слева направо. Например, если бы в домах жили (слева направо) Константин, Николай, Роман и Олег, ответ был бы: КНРО

Спасибо за внимание!