Самая сложная логическая задача

Задача:
Есть три бога: A, B и C, которые являются богами истины, лжи и случая в произвольном порядке.
Бог истины всегда говорит правду, бог лжи — всегда обманывает, бог случая может говорить и правду, и ложь в произвольном порядке.
Требуется определить богов, задав 3 вопроса, на которые можно ответить «да» или «нет».
Каждый вопрос задаётся только одному богу.
Боги понимают язык, но отвечают на своём языке, в котором есть 2 слова «da» и «ja»,
причём неизвестно, какое слово обозначает «да», а какое «нет».

Опубликовал задачу и предложил её решение — Булос.

Американский философ и логик Джордж Булос (4 сентября 1940 – 27 мая 1996), Массачусетский технологический институт.

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

Вопрос Булоса:
«Означает ли «da» «да», только если ты бог правды, а бог B — бог случая?».
Другой вариант вопроса:
«Является ли нечётным числом количество правдивых утверждений в следующем списке:
ты — бог лжи, «ja» обозначает «да», B — бог случая?»

Решение задачи может быть упрощено, если использовать условные высказывания, противоречащие фактам.
Идея этого решения состоит в том, что на любой вопрос Q, требующий ответа «да» либо «нет», заданный богу правды или богу лжи:

  • Если я спрошу тебя Q, ты ответишь «ja»?

результат будет «ja», если верный ответ на вопрос Q это «да», и «da», если верный ответ «нет».
Для доказательства этого можно рассмотреть восемь возможных вариантов, предложенных самим Булосом:

  • Предположим, что «ja» обозначает «да», а «da» обозначает «нет»:
    • Мы спрашивали у бога правды, и он ответил «ja».

      Поскольку он говорит правду и верный ответ на вопрос Q — «ja»,
      оно обозначает «да».

    • Мы спрашивали у бога правды, и он ответил «da». Поскольку он говорит правду и верный ответ на вопрос Q — «da»,
      оно обозначает «нет».
    • Мы спрашивали у бога лжи, и он ответил «ja». Поскольку он всегда лжёт, поэтому на вопрос Q он ответит «da».
      То есть правильный ответ на вопрос «ja», который обозначает «да».
    • Мы спрашивали у бога лжи, и он ответил «da».

      Поскольку он всегда лжёт, поэтому на вопрос Q он ответит «ja».
      То есть правильный ответ на вопрос «da», который обозначает «нет».

  • Предположим, что «ja» обозначает «нет», а «da» обозначает «да»:
    • Мы спрашивали у бога правды, и он ответил «ja». Поскольку он говорит правду и верный ответ на вопрос Q — «da»,
      оно обозначает «да».
    • Мы спрашивали у бога правды, и он ответил «da». Поскольку он говорит правду и верный ответ на вопрос Q — «ja»,
      оно обозначает «нет».
    • Мы спрашивали у бога лжи, и он ответил «ja». Поскольку он всегда лжёт, поэтому на вопрос Q он отвечает «ja».
      Но, так как он лжёт, верный ответ на вопрос Q — «da», что означает «да».
    • Мы спрашивали у бога лжи, и он ответил «da». Поскольку он всегда лжёт, поэтому на вопрос Q он отвечает «da».
      Но, так как он лжёт, верный ответ на вопрос Q — «ja», что означает «нет».

Используя этот факт, можно задавать вопросы:

  • Спросим бога B: «Если я спрошу у тебя «Бог А — бог случая?», ты ответишь «ja»?».
    Если бог B отвечает «ja», значит, либо он бог случая (и отвечает случайным образом), либо он не бог случая,
    а на самом деле бог A — бог случая.
    В любом варианте, бог C — это не бог случая.
    Если же B отвечает «da», то либо он бог случая (и отвечает случайным образом),
    либо B не бог случая, что означает, что бог А — тоже не бог случая.
    В любом варианте, бог A — это не бог случая.
  • Спросим у бога, который не является богом случая (по результатам предыдущего вопроса, либо A, либо C):
    «Если я спрошу у тебя: «ты бог случая?», ты ответишь «ja»?».
    Поскольку он не бог случая, ответ «ja» обозначает, что он бог правды, а ответ «da» обозначает, что он бог лжи.
  • Спросим у этого же бога «Если я у тебя спрошу: «Бог B — бог случая?», ответишь ли ты «ja»?».
    Если ответ «ja» — бог B является богом случая, если ответ «da», то бог, с которым ещё не говорили, является богом случая.

Оставшийся бог определяется методом исключения.

Сложная логическая задача:

                                                             < назад          .................             вперед >

Самая сложная логическая задача (итал. L’indovinello più difficile del mondo) — название логической задачи, предложенной американским философом и логиком Джорджем Булосом в итальянской газете «la Repubblica»:
Есть три бога: A, B и C, которые являются богами истины, лжи и случая в произвольном порядке. Бог истины всегда говорит правду, бог лжи — всегда обманывает, бог случая может говорить и правду, и ложь в произвольном порядке. Требуется определить богов, задав 3 вопроса, на которые можно ответить «да» или «нет». Каждый вопрос задаётся только одному богу. Боги понимают язык, но отвечают на своём языке, в котором есть 2 слова «da» и «ja», причём неизвестно, какое слово обозначает «да», а какое «нет».

Булос также разъясняет некоторые моменты задачи:
• Можно задавать одному богу более чем один вопрос (поэтому другим богам может быть не задано ни одного вопроса вообще).
• Каков будет следующий вопрос и кому он будет задан, может зависеть от ответа на предыдущий вопрос.
• Бог случая отвечает случайным образом, зависящим от подбрасываний монетки, спрятанной в его голове: если выпадет аверс, то отвечает правдиво, если реверс — то врёт.
• Бог случая отвечает «da» или «ja» на любой вопрос, на который можно ответить «да» либо «нет».

История

Булос указывает логика Рэймонда Смаллиана как автора задачи и Джона Маккарти за увеличение сложности задачи из-за неясных трактовок «da» и «ja». Похожие задачи есть в книгах Смаллиана, например, он описывает остров, где половина жителей зомби (они постоянно лгут), а другая половина — люди (они постоянно говорят правду). Ситуацию усложняет факт, что жители острова прекрасно нас понимают, но древнее табу запрещает им использовать неродные слова. Поэтому они используют ответы «bal» или «da», которые означают «да» и «нет», причём неясно, какое из них что обозначает. Есть ещё ряд подобных головоломок в книге «The Riddle of Scheherazade». Всё это разновидности широко известных задач о рыцарях и лжецах Смаллиана.
Одна из таких задач была освещена в фильме «Лабиринт»: есть 2 двери и 2 стражника, один всегда говорит правду, второй всегда лжёт. Одна дверь ведёт к замку, вторая — к гибели. Смысл головоломки состоит в том, чтобы узнать, какая дверь ведёт к замку задав один вопрос одному стражнику. В фильме Сара спрашивала: «Он [другой стражник] скажет мне, что его дверь ведёт к замку?»

Решение задачи

Булос предложил решение задачи в той же статье, где он и опубликовал саму задачу. Он заявил, что первым вопросом мы должны найти бога, который не является богом случая, то есть является либо богом правды, либо богом лжи. Есть множество вопросов, которые могут быть заданы для достижения этой цели. Одна из стратегий — использование сложных логических связей в самом вопросе.
Вопрос Булоса: «Означает ли „da“ „да“, только если ты бог правды, а бог B — бог случая?». Другой вариант вопроса: «Правдивы ли нечётные утверждения в следующем списке: ты — бог лжи, „ja“ обозначает „да“, B — бог случая?»
Решение задачи может быть упрощено, если использовать условные высказывания, противоречащие фактам. Идея этого решения состоит в том, что на любой вопрос Q, требующий ответа «да» либо «нет», заданный богу правды или богу лжи:
• Если я спрошу тебя Q, ты ответишь «ja»?
результат будет «ja», если верный ответ на вопрос Q это «да» и «da», если верный ответ «нет». Для доказательства этого

можно рассмотреть восемь возможных вариантов:
• Предположим, что «ja» обозначает «да», а «da» обозначает «нет»: 
o Мы спрашивали у бога правды, и он ответил «ja». Поскольку он говорит правду и верный ответ на вопрос Q — «ja», оно обозначает «да».
o Мы спрашивали у бога правды, и он ответил «da». Поскольку он говорит правду и верный ответ на вопрос Q — «da», оно обозначает «нет».
o Мы спрашивали у бога лжи, и он ответил «ja». Поскольку он всегда лжёт, поэтому на вопрос Q он ответит «da». То есть правильный ответ на вопрос «ja», который обозначает «да».
o Мы спрашивали у бога лжи, и он ответил «da». Поскольку он всегда лжёт, поэтому на вопрос Q он ответит «ja». То есть правильный ответ на вопрос «da», который обозначает «нет».
• Предположим, что «ja» обозначает «нет», а «da» обозначает «да»: 
o Мы спрашивали у бога правды, и он ответил «ja». Поскольку он говорит правду и верный ответ на вопрос Q — «da», оно обозначает «да».
o Мы спрашивали у бога правды, и он ответил «da». Поскольку он говорит правду и верный ответ на вопрос Q — «ja», оно обозначает «нет».
o Мы спрашивали у бога лжи, и он ответил «ja». Поскольку он всегда лжёт, поэтому на вопрос Q он отвечает «ja». Но, так как он лжёт, верный ответ на вопрос Q — «da», что означает «да».
o Мы спрашивали у бога лжи, и он ответил «da». Поскольку он всегда лжёт, поэтому на вопрос Q он отвечает «da».

Но, так как он лжёт, верный ответ на вопрос Q — «ja», что означает «нет».

Используя этот факт можно задавать вопросы:
• Спросим бога B: «Если я спрошу у тебя „Бог А — бог случая?“, ты ответишь „ja“?». Если бог B отвечает «ja», значит, либо он бог случая (и отвечает случайным образом), либо он не бог случая, а на самом деле бог A — бог случая. В любом варианте, бог C — это не бог случая. Если же B отвечает «da», то либо он бог случая (и отвечает случайным образом), либо B не бог случая, что означает, что бог А — тоже не бог случая. В любом варианте, бог A — это не бог случая.
• Спросим у бога, который не является богом случая (по результатам предыдущего вопроса, либо A, либо C): «Если я спрошу у тебя: „ты бог правды?“, ты ответишь „ja“?». Поскольку он не бог случая, ответ «ja» обозначает, что он бог правды, а ответ «da» обозначает, что он бог лжи.
• Спросим у этого же бога «Если я у тебя спрошу: „Бог B — бог случая?“, ответишь ли ты „ja“?». Если ответ «ja» — бог B является богом случая, если ответ «da», то бог, с которым ещё не говорили, является богом случая.
Оставшийся бог определяется методом исключения.

Морфологический разбор слова онлайн

Введите слово или предложение и получите морфологический разбор с указанием части речи, падежа, рода, времени и т.д.

Начальная форма: РЕШИТЬ
Часть речи: причастие
Грамматика: единственное число, женский род, именительный падеж, неодушевленное, одушевленное, непереходный, прошедшее время, совершенный вид, страдательный залог
Формы: решить, решил, решила, решило, решили, решу, решим, решишь, решите, решит, решат, решив, решивши, решимте, реши, решивший, решившего, решившему, решившим, решившем, решившая, решившей, решившую, решившею, решившее, решившие, решивших, решившими, решённый, решённого, решённому, решённым, решённом, решён, решённая, решённой, решённую, решённою, решена, решённое, решено, решённые, решённых, решёнными, решены


Начальная форма: ДРУГ
Часть речи: существительное
Грамматика: единственное число, мужской род, одушевленное, творительный падеж
Формы: друг, друга, другу, другом, друге, друзья, друзей, друзьям, друзьями, друзьях

Начальная форма: ДРУГОЙ
Часть речи: местоименное прилагательное
Грамматика: единственное число, мужской род, неодушевленное, одушевленное, предложный падеж
Формы: другой, другого, другому, другим, другом, другая, другую, другою, другое, другие, других, другими


Начальная форма: ЗАДАЧА
Часть речи: существительное
Грамматика: единственное число, женский род, именительный падеж, неодушевленное
Формы: задача, задачи, задаче, задачу, задачей, задачею, задач, задачам, задачами, задачах


Слайд 1

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

Слайд 2

Известно несколько различных способов решения логических задач. Метод рассуждений Табличный С помощью графов Упрощение логических выражений Составление таблиц истинности Метод кругов Эйлера

Слайд 3

Рассмотрим четыре типа логических задач. Задачи 1-го типа В условии приводится несколько двойных или одинарных утверждений и дается оценка их истинности, т.е. сообщается, сколько участников говорят только правду, сколько лгут и сколько говорят то правду, то ложь .

Слайд 4

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

Слайд 5

Задача №2. Три друга играли во дворе в футбол и разбили мячом окно. Ваня сказал: «Это я разбил окно, Коля окно не разбивал». Коля сказал «Это сделал не я и не Саша». Саша сказал: «Это сделал не я и не Ваня». А Бабушка сидела на лавочке и все видела. Она сказала, что только один мальчик оба раза сказал правду , но не назвала того, кто разбил окно. Кто же это? В К С Слова В Слова К Слова С В ┐ К ┐ К ┐ С ┐ С ┐ В 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 Ответ: разбил Коля

Слайд 6

Задачи 2-го типа В условии приводится несколько двойных утверждений, в которых одно утверждение истинно, а другое ложно. Результат – расстановка участников по местам. Пример: Перед началом турнира болельщики высказали следующие предположения по поводу своих кумиров: А. Макс победит, Билл – второй. Б. Билл – третий, Ник – первый. В. Макс – последний, а первый – Джон. Когда соревнования закончились, оказалось, что каждый болельщик был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Билл, Ник, Макс?

Слайд 7

Пример: Перед началом турнира болельщики высказали следующие предположения по поводу своих кумиров: А. Макс победит, Билл – второй. Б. Билл – третий, Ник – первый. В. Макс – последний, а первый – Джон.

Когда соревнования закончились, оказалось, что каждый болельщик был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Билл, Ник, Макс? А В С Билл — 2 Макс — 1 Билл — 3 Ник — 1 Макс — 4 Джон -1 И Л И Л Л И Противоречие!!! Два первых места Ответ: Ник -1, Билл 2, Джон 3, Макс — 4 И Л Л И И Л

Слайд 8

М Б Н Д 1 3 2 4 1-ый эксперт: Предположим, что Макс – победит, следовательно М4 — ложно Противоречие- в вершину 1 приходит Д1 Значит М1 – убрать , а М4 – оставить Убираем Д1 Убираем Б3 Решение с применением графа Вершины графа – имена участников и места, которые они могут занять . Для каждого эксперта используются линии разных цветов. В результате решения на графе должна остаться только одна линия определенного цвета , и из каждой вершины должна выходить одна линия. Ответ: Ник – первый Билл – второй Джон – третий Макс — четвертый

Слайд 9

Задачи 3-го типа В условии приводятся несколько (обычно три) двойных утверждений, в которых одно утверждение истинно, а другое ложно. Пример: Трое свидетелей рассказали о машине, которую они видели: Это была Хонда черного цвета. Это был Форд синего цвета. Это был Мерседес, но не синий. Каждый из них был прав только в одном из своих утверждений. Какая это была машина? Первый Второй Третий Хонда Черная Форд Синий Мерседес не синий И Л Л И Л И Л И И Л Л И Ответ: Форд, черный

Слайд 10

Задачи 4- типа. Даны несколько логических высказываний, являющихся истинными. Задача 1. На вопрос, кто из десятиклассников, присутствующих на олимпиаде по физике решит самую трудную задачу, учитель ответил: «Если задачу может решить Виктор, то ее может решить и Степан, но неверно, что если задачу может решить Антон, то может решить ее и Степан» и оказался прав, когда результаты стали известны. Кто из трех десятиклассников решил самую трудную задачу? Обозначения; А = «Задачу решил Антон» В = «Задачу решил Виктор» С = «Задачу решил Степан» ( В — > C) /\ (¬( А — > C)) = 1

Слайд 11

Составим таблицу истинности логического выражения А В С В — > C А- > C ¬(А- > C ) ( В — > C) /\ (¬( А — > C)) 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 1 1 0 0 Ответ: задачу решил Антон

Слайд 12

Задача №1 . В одном королевстве король всякому узнику, приговоренному к смерти, давал последний шанс спастись. Ему предлагалось угадать, в какой из двух комнат находится тигр, а в какой — принцесса. Хотя вполне могло быть, что король в обеих комнатах разместил принцесс или, что хуже, в обеих — тигров. Выбор надо сделать на основании табличек на дверях комнат. Причем узнику известно, что утверждения на табличках одновременно либо истины, либо ложны. Надписи были таковы. Первая комната: «По крайней мере, в одной из этих комнат находится принцесса». Вторая комната: «В другой комнате – тигр». Какую дверь должен выбрать узник? ? Решение логических задач методом преобразования логических выражений.

Слайд 13

P 1 = В первой комнате принцесса . P 2 = Во второй комнате принцесса. P 1 = В первой комнате тигр. P 2 = Во второй комнате тигр.

Слайд 14

А = Р 1 \/ Р 2 В = Р 1 А & B \/ A & B = 1

Слайд 15

А & B \/ A & B = 1 (P 1 \/ P 2 ) & P 1 \/ (P 1 \/ P 2 ) & P 1 А = Р 1 \/ Р 2 В = Р 1 = (P 1 & P 1 \/ P 2 & P 1 ) \/ (P 1 & P 2 ) & P 1 = = 0 \/ P 2 & P 1 \/ (P 1 & P 2 & P 1 ) = P 2 & P 1 = 1 Ответ: А = Р 1 \/ Р 2 В = Р 1 А = Р 1 \/ Р 2 Дистрибутивность Закон де Моргана

Слайд 16

P 1 = В первой комнате принцесса . P 2 = Во второй комнате принцесса. P 1 = В первой комнате тигр. P 2 = Во второй комнате тигр. P 2 & P 1 = 1 P 2 & P 1 = 1 P 2 & P 1 = 1 P 2 & P 1 = 1

Слайд 17

Задача №4 (на однозначное соответствие) В бюро переводов приняли на работу троих сотрудников: Диму, Сашу и Юру. Каждый из них знает ровно два иностранных языка из следующего набора: немецкий, японский, шведский, японский, китайский, французский и греческий. Известно, что (1) Ни Дима, ни Юра не знают японского (2) Переводчик со шведского старше переводчика с немецкого (3) Переводчик с китайского, переводчик с французского и Саша родом из одного города (4) Переводчик с греческого, переводчик с немецкого и Юра учились втроем в одном институте (5) Дима – самый молодой из всех троих, и он не знает греческого (6) Юра знает два европейских языка В ответе запишите первую букву имени переводчика со шведского языка и, через запятую, первую букву имени переводчика с китайского языка.

Слайд 18

Немецкий Шведский Японский Китайский Французский Греческий Дима + — — + — — Юра — + — — + — Саша — — + — — + Дима — Немецкий и китайский Юра – шведский и французский Саша – японский и греческий Рассуждение с использованием таблицы

Слайд 19

При решении подобных задач нужно выбрать наиболее рациональный метод.

Добавить комментарий

Закрыть меню