Способы решения логических задач

1. Способы решения логических задач

СПОСОБЫ
РЕШЕНИЯ
ЛОГИЧЕСКИХ
ЗАДАЧ

2.

Существует три способа
решения логических задач:
•С
помощью рассуждений.
•Табличный.
•Средствами алгебры логики.

3.

Способ рассуждений
Самый примитивный способ.
Им решаются самые простые логические задачи.
Его идея состоит в том, что мы проводим
рассуждения, используя последовательно
все условия задачи, и приходим к выводу,
который и будет являться ответом задачи.

4.

ЗАДАНИЕ
Вадим, Сергей и Михаил изучают различные
иностранные языки: китайский, японский и арабский.
На вопрос, какой язык изучает каждый из них, один
ответил: "Вадим изучает китайский, Сергей не изучает
китайский, а Михаил не изучает арабский".
Впоследствии выяснилось, что в этом ответе только одно
утверждение верно, а два других ложны. Какой язык
изучает каждый из молодых людей?

5.

Решение. Имеется три утверждения. Если верно первое утверждение, то верно
и второе, так как юноши изучают разные языки. Это противоречит условию
задачи, поэтому первое утверждение ложно. Если верно второе утверждение, то
первое и третье должны быть ложны. При этом получается, что никто не изучает
китайский. Это противоречит условию, поэтому второе утверждение тоже
ложно. Остается считать верным третье утверждение, а первое и второе —
ложными. Следовательно, Вадим не изучает китайский, китайский изучает
Сергей.
Ответ: Сергей изучает китайский язык, Михаил — японский, Вадим —
арабский.

6.

Способ построения таблиц
Основной прием - построение таблиц.
Табличный способ нагляден, но используется
только для определенного класса задач и требует
умения сравнивать и сопоставлять.

7. Задание

ЗАДАНИЕ
Три клоуна Бим, Бам и Бом вышли на арену в
красной, зеленой и синей рубашках. Их туфли были
тех же цветов. У Бима цвета рубашки и туфель
совпадали. У Бома ни туфли, ни рубашка не были
красными. Бам был в зеленых туфлях, а в рубашке
другого цвета. Как были одеты клоуны?
рубашки
К
З
туфли
С
К
З
С
Бим
Бам
Бом
Таблица

8.

Решение. Составим таблицу, в столбцах которой отметим
возможные цвета рубашек и туфель клоунов (буквами К, З и С
обозначены красный, зеленый и синий цвета). Будем заполнять
таблицу, используя условия задачи. Туфли Бама зеленые, а
рубашка не является зеленой. Ставим знак + в клетку 2-й строки и 5го столбца, и знак - в клетку 2-й строки и 2-го столбца.
Следовательно, у Бима и Бома туфли уже не могут быть зелеными,
так же как не могут быть туфли Бама синими или красными.
Отметим все это в таблице (см. табл. 1).
рубашки
К
З
Бим
Бам
Бом
-
туфли
С
К
З
С
+
-
+
-
-
-
+
Таблица 1

9.

Далее, туфли и рубашка Бома не являются красными, отметим эти ячейки
таблицы знаком – . На этом этапе, видим, что красные туфли могут быть
только у Бима, а, следовательно, туфли Бома - синие. Правая часть
таблицы заполнена, мы установили цвета обуви клоунов (табл.1). Цвет
рубашки Бима совпадает с цветом его туфель и является красным.
Теперь легко устанавливается владелец зеленой рубашки - Бом. Бам, в
таком случае, одет в рубашку синего цвета.
Мы полностью заполнили таблицу, в которой однозначно
устанавливаются цвета туфель и рубашек клоунов (см. табл. 2):
рубашки
туфли
К
З
С
К
З
С
Бам
+
-
-
+
+
-
+
-
Бом
-
+
-
-
-
+
Бим
Таблица 2
Ответ: Бим одет в красную рубашку и красные туфли, Бам в синей рубашке
и зеленых туфлях, Бом в зеленой рубашке и туфлях синего цвета.

10.

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

11.

В школьном первенстве по настольному теннису в четверку лучших
вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие
болельщики высказали свои предположения о распределении мест в
дальнейших состязаниях.
Один считает, что первой будет Наташа, а Маша будет второй.
Другой болельщик на второе место прочит Люду, а Рита, по его
мнению, займет четвертое место.
Третий любитель тенниса с ними не согласился. Он считает, что
Рита займет третье место, а Наташа будет второй.
Когда соревнования закончились, оказалось, что каждый из
болельщиков был прав только в одном из своих прогнозов.
Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?
(В ответе перечислите подряд без пробелов числа,
соответствующие местам девочек в указанном порядке имен.)

12.

Решение:
Обозначим высказывания:
Н1 = “первой будет Наташа”;
М2 = “второй будет Маша”;
Л2 = “второй будет Люда”;
Р4 = “четвертой будет Рита”;
Р3 = “третьей будет Рита”;
Н2 = “второй будет Наташа”.
Согласно условию:
из высказываний 1 болельщика следует, что Н1VМ2 истинно;
из высказываний2 болельщика следует, что Л2VР4 истинно;
из высказываний 3 болельщика следует, что Р3VН2 истинно.
Следовательно, истинна и конъюнкция
(Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = 1.
Раскрыв скобки получим:
(Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = (Н1/\Л2V Н1/\Р4 V М2/\Л2 V М2/\Р4) /\
(Р3VН2)=
Н1/\ Л2/\Р3 V Н1/\Р4/\Р3 V М2/\Л2/\Р3 V М2/\Р4/\Р3 V Н1/\Л2/\Н2 V Н1/\Р4/\
Н2 V М2/\Л2/\Н2 V М2/\Р4/\Н2 = Н1/\ Л2/\Р3 V 0 V 0 V 0 V 0 V 0 V 0 V= Н1/\
Л2/\Р3
Наташа-1, Люда-2, Рита-3, а Маша-4.
Ответ: 1423

13.

ЗАДАНИЕ
Три дочери писательницы Дорис Кей — Джуди, Айрис и Линда —тоже очень
талантливы. Они приобрели известность в разных видах искусств —пении, балете
и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в
Париж,Рим и Чикаго. Известно, что:
Джуди живет не в Париже, а Линда — не в Риме;
парижанка не снимается в кино; та, кто живет в Риме, — певица;
Линда равнодушна к балету.
Где живет Айрис и какова ее профессия?

14.

Решение:
Париж
+
-
Рим
+
-
Чикаго
Джуди
Айрис
+
Линда
Пение Балет
+
+
-
Ответ: Айрис — балерина. Она живет в Париже.
Кино
+

15.

ЗАДАНИЕ
На перекрестке произошло дорожно-транспортное происшествие, в котором
участвовали автобус (А), грузовик (Г), легковой автомобиль (Л) и
маршрутное такси (М). Свидетели происшествия дали показания инспектору
ГИБДД. Первый свидетель считал, что первым на перекресток выехал
автобус, а маршрутное такси было вторым. Другой свидетель полагал, что
последним на перекресток выехал легковой автомобиль, а вторым был
грузовик. Третий свидетель уверял, что автобус выехал на перекресток
вторым, а следом за ним – легковой автомобиль. В результате оказалось,
что каждый из свидетелей был прав только в одном из своих утверждений. В
каком порядке выехали машины на перекресток? В ответе перечислите
подряд без пробелов первые буквы названий транспортных средств в
порядке их выезда на перекресток, например
Ответ: АГЛМ.

16.

ЗАДАНИЕ
Ответ:

17.

РЕШЕНИ
Е
Ответ:

18.

Андрей, Аня и Маша решили пойти в кино. Каждый из них
высказал свои пожелания по поводу выбора фильма.
Андрей сказал: “Я хочу посмотреть французский боевик”.
Маша сказала: “Я не хочу смотреть французскую комедию”.
Аня сказала: “Я хочу посмотреть американскую мелодраму”.
Каждый из них слукавил в одном из двух пожеланий. На какой
фильм пошли ребята?
Ответ: американский боевик.

19.

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

20.

Три молодые мамы Анна, Ирина и Ольга, гуляя в парке со своими
малышами, встретили свою четвертую подругу. На вопрос, как
зовут малышей, желая подшутить над подружкой, они ответили:
Анна: моего малыша зовут Денис, а Кирилл – сын Ирины.
Ирина: моего сыночка зовут Максим, а Кирилл – сын Анны.
Ольга: мой мальчик – Кирилл, а сына Анны зовут Максим.
Каждая из них один раз сказала правду и один раз солгала. Как
зовут мальчиков Анны, Ирины и Ольги? В ответе перечислите
подряд без пробелов буквы, соответствующие именам мальчиков в
указанном порядке имен их мам, например КМД.
Ответ: ДМК.

21.

Коля, Боря, Вова и Юра заняли первые четыре места в
спортивном соревновании. На вопрос, какие места они
заняли, они ответили:
1) "Коля не занял ни первое, ни четвертое места".
2) «Боря занял второе место».
3) «Вова не был последним». Какое место занял каждый
мальчик?
Ответ:
первое - Вова,
второе - Боря,
третье-Коля,
четвертое - Юра.

22.

За круглым столом сидели 4 студента.
Филолог сидел против Козина, рядом с историком.
Математик сидел рядом с Волковым.
Соседи Шатрова – Егоркин и физик.
Какая профессия у Козина?
Ответ:
Козин - математик,
Шатров - филолог (сидел против Козина), рядом с историком - Егоркиным.
Математик сидел рядом с Волковым (физик) .
Соседи Шатрова - Егоркин и физик.

23.

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

24.

Три товарища — Иван, Дмитрий, Степан преподают раз­
личные предметы (химию, биологию, физику) в школах
Москвы, Ленинграда и Киева. Известно:
1) Иван работает не в Москве, а Дмитрий не в Ленинграде;
2) москвич преподает не физику;
3) тот, кто работает в Ленинграде, преподает химию;
4) Дмитрий преподает не биологию.
Какой предмет и в каком городе преподает каждый из това­
рищей?
Ответ:
Иван живет в Ленинграде, преподает химию;
Дмитрий – в Киеве, физику;
Степан – в Москве, биологию.

25.

Алеша, Боря и Гриша нашли в земле сосуд. Рассматривая удивитель­
ную находку, каждый высказал по два предположения:
Алеша. Это сосуд греческий и изготовлен в V веке.
Боря. Это сосуд финикийский и изготовлен в III веке.
Гриша. Это сосуд не греческий и изготовлен в IV веке.
Учитель истории сказал ребятам, что каждый из них прав только в
одном из двух предположений.
Где и в каком веке изготовлен сосуд?
Ответ: финикийский и изготовлен в V веке

26.

Из поврежденной книги выпала часть сшитых вместе листов.
Номер первой выпавшей страницы 143, а номер последней
записан теми же цифрами, но в ином порядке. Сколько листов
выпало из книги?
Ответ: Для иного порядка страница
должна быть четной, раз начало
нечетное, и ее номер должен быть
больше, чем 143. Получается: 314. 314143+1=172 страниц.
172:2=86 листов выпало

27.

Определить участника преступления, исходя из двух посылок:
1) "Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал";
2) "Если Иванов не участвовал, то Сидоров не участвовал".
Ответ:

28.

Рассмотрим решение этой несложной задачи двумя способами:
1) с помощью алгебраических преобразований.
Решение
Составим выражения:
I - "Иванов участвовал в преступлении";
P - "Петров участвовал в преступлении";
S - "Сидоров участвовал в преступлении".
Запишем посылки в виде формул:
¬I˅P→S и ¬I→¬S
Применим преобразования с помощью законов алгебры логики:
F(I,P,S) = ( ¬I˅P→S) &( ¬I→¬S)=(¬(¬I˅P)˅S) & (I˅¬S) = (I & ¬P ˅S) & (I ˅¬S)
= I&¬P˅ I & S˅ I &¬P &¬S ˅0 = I&¬P ˅ I & S = I & (¬P˅S)
Из последнего выражения видно, что выражение верно, если I=1, значит
преступник - Иванов.
Ответ: Иванов

29.

Рассмотрим решение этой несложной задачи двумя способами:
2) с помощью таблиц истинности
Решение
Составим выражения:
I - "Иванов участвовал в преступлении";
P - "Петров участвовал в преступлении";
S - "Сидоров участвовал в преступлении".
Запишем посылки в виде формул:
Ответ: Иванов
¬I˅P→S и ¬I→¬S

30. Задача о синоптике

ЗАДАЧА О СИНОПТИКЕ
На вопрос, какая завтра будет погода, синоптик ответил:
1. Если не будет ветра, то будет пасмурная погода без дождя.
2. Если будет дождь, то будет пасмурно и без ветра.
3. Если будет пасмурная погода, то будет дождь и не будет ветра.
Так какая же погода будет завтра?

31. Задача о синоптике

ЗАДАЧА О СИНОПТИКЕ
Выделим простые высказывания и запишем их через переменные:
A – «Ветра нет»
B – «Пасмурно»
С – «Дождь»
Запишем логические функции (сложные высказывания) через введенные переменные:
Если не будет ветра, то будет пасмурная погода без дождя:
Если будет дождь, то будет пасмурно и без ветра:
Если будет пасмурная погода, то будет дождь и не будет ветра:
Запишем произведение указанных функций:
F=(A→ B & C) & (C→B & A) & (B→ C & A)
A→B&C
С→B&A
B→C&А
Упростим формулу (используются законы де Моргана, переместительный закон, закон
противоречия):
F=(A→ B & ¬C) & (C→B & A) & (B→ C & A) = (¬A v B & ¬C) & (¬C v B&A) & (¬B v C&A) =
= (¬A v B & ¬C) & (¬B v C&A) & (¬C v B&A) = (¬A &¬ B v B&¬C&¬B v ¬A&C&A v B&¬C&C&A)
& (C v B&A)= ¬A & ¬B &(C v B&¬A) =A&¬B&C v¬ A&¬B&B&¬A == ¬A&¬B&¬C
Приравняем результат единице, т.е. наше выражение должно быть истинным:F = ¬A &¬ B & ¬C =
1 и проанализируем результат: Логическое произведение равно 1, если каждый множитель равен 1.
¬A = 1; ¬B = 1; ¬C = 1.значит: A = 0; B = 0; C = 0;
Ответ: погода будет ясная, без дождя, но ветреная.

32. Задача

ЗАДАЧА
Аня, Вика и Сергей решили пойти в кино.
Учитель хорошо знавший этих ребят, высказал следующие
предположения:
Аня пойдет в кино только тогда, когда пойдут Вика и Сергей;
Аня и Сергей пойдут в кино вместе или же оба останутся дома;
чтобы Сергей пошел в кино, необходимо, чтобы пошла Вика.
Когда ребята пошли в кино, оказалось, что учитель немного
ошибался, из трех его утверждений истинными оказались
только два.
Кто из названных ребят пошел в кино?
Ответ: Аня и Сергей не пойдут в кино, а пойдет Вика.

33. Задача Эйнштейна который считал, что ее может решить только 2% населения:

ЗАДАЧА ЭЙНШТЕЙНА
КОТОРЫЙ СЧИТАЛ,
ЧТО ЕЕ МОЖЕТ
РЕШИТЬ ТОЛЬКО
2% НАСЕЛЕНИЯ:

34. Альберт Эйнштейн Albert Einstein 1879 - 1955

АЛЬБЕРТ ЭЙНШТЕЙН
ALBERT EINSTEIN
1879 - 1955
Физик-теоретик, один из
основоположников современной
физики. Известен прежде всего
как автор теории
относительности. Эйнштейн внес
также значительный вклад в
создание квантовой механики,
развитие статистической физики
и космологии. Лауреат
Нобелевской премии по физике
1921 («за объяснение
фотоэлектрического эффекта»)

35. Условие задачи Эйнштейна,

УСЛОВИЕ ЗАДАЧИ ЭЙНШТЕЙНА,
На одной улице подряд стоят пять домов, каждый — своего цвета. В каждом живёт человек, все
пять — разных национальностей. Каждый человек предпочитает уникальную марку сигарет,
напиток и домашнее животное. Кроме того:
Норвежец
живёт в первом доме.
Англичанин
Зелёный
живёт в красном доме.
дом находится слева от белого, рядом с ним.
Датчанин
пьет чай.
Тот,
кто курит Marlboro, живёт рядом с тем, кто выращивает кошек.
Тот,
кто живёт в жёлтом доме, курит Dunhill.
Немец
Тот,
кто живёт в центре, пьет молоко.
Сосед
Тот,
курит Rothmans.
того, кто курит Marlboro, пьет воду.
кто курит Pall Mall, выращивает птиц.
Швед
выращивает собак.
Норвежец
живёт рядом с синим домом.
Тот,
кто выращивает лошадей, живёт в синем доме.
Тот,
кто курит Winfield, пьет пиво.
В
зелёном доме пьют кофе.
Вопрос: Кто разводит рыбок?