Парадокс парикмахерской - Barbershop paradox

Эта статья посвящена логической проблеме Льюиса Кэрролла, связанной с условными операторами. Для несвязанной версии парадокса Бертрана Рассела о самоотнесении см. Парадокс парикмахера.

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

Парадокс

По сюжету дядя Джо и дядя Джим идут в парикмахерскую. Они объясняют, что в магазине живут и работают три парикмахера - Аллен, Браун и Карр - и некоторые или все из них могут быть там. Нам даются две части информации, из которых мы можем сделать выводы. Во-первых, магазин определенно открыт, поэтому должен быть хотя бы один из парикмахеров. Во-вторых, говорят, что Аллен очень нервничает, поэтому он никогда не выходит из магазина, если с ним не пойдет Браун.

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

Дядя Джо приводит следующие аргументы:

Предположим, что Карр отсутствует. Покажем, что это предположение приводит к противоречию. Если Карра нет, то мы это знаем: «Если Аллен отсутствует, значит, Браун в игре», потому что «в магазине» должен быть кто-то. Но мы также знаем, что когда Аллен выходит из дома, он берет с собой Брауна, так что, как правило, "Если Аллен отсутствует, значит, нет Брауна". Два утверждения, к которым мы пришли, несовместимы, потому что, если Аллен отсутствует, Браун не может быть одновременно входом (согласно одному) и выходом (согласно другому). Есть противоречие. Таким образом, мы должны отказаться от нашей гипотезы о том, что Карр отсутствует, и заключить, что Карр должен быть в игре.

Дядя Джим отвечает, что такой вывод необоснован. Правильный вывод, который можно сделать из несовместимости двух «гипотетических» гипотез, состоит в том, что то, что предполагается в них (что Аллен отсутствует), должно быть ложным при нашем предположении, что Карр отсутствует. Тогда наша логика просто позволяет нам прийти к выводу: «Если Карр отсутствует, то обязательно должен быть Аллен».

Исторический спор

Парадокс возник из-за разногласий между Кэрроллом и его коллегой из Оксфорда, профессором логики Уайкхема. Джон Кук Уилсон, у двух из которых был давний антагонизм. Проблема также обсуждалась другими, с которыми Кэрролл переписывался, и рассматривалась в более поздних статьях, опубликованных Джон Венн, Альфред Сиджвик и Бертран Рассел среди прочего. Взгляд Кука Уилсона представлен в рассказе персонажем дядюшки Джо, который пытается доказать, что Карр всегда должен оставаться в магазине. Другие придерживались того же мнения, когда Кэрролл распространял свои частные печатные версии проблемы. Как заметил Кэрролл, «Я переписываюсь примерно с дюжиной логиков по этому любопытному вопросу; и до сих пор мнения относительно свободы С. разделились поровну».[2]:445-448

Упрощение

Обозначение

При чтении оригинала полезно иметь в виду следующее:

  • То, что Кэрролл называл «гипотетическими», современные логики называют »логические условия ".
  • Дядя Джо завершает свое доказательство сокращение до абсурда, что означает на английском языке "доказательство от противного ".
  • То, что Кэрролл называет протазисом условного, теперь известно как антецедент, и аналогично аподозис теперь называется следствием.

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

Оператор (Имя)РазговорныйСимволический
ОтрицаниеНЕТне X¬¬X
СоединениеИX и Y∧X ∧ Y
ДизъюнкцияИЛИ ЖЕX или Y∨X ∨ Y
УсловныйЕСЛИ ... ТОесли X, то Y⇒X ⇒ Y

Примечание. X ⇒ Y (также известное как «Импликация») можно читать много способов на английском, от «X достаточно для Y» до «Y следует из X ". (См. Также Таблица математических символов.)

Пересмотр

Чтобы упростить пересказ истории Кэрролла, мы воспользуемся следующим атомарные заявления:

  • A = Аллен в магазин
  • B = коричневый в
  • C = Карр в

Так, например, (¬A ∧ B) означает «Аллен отсутствует, а Браун входит».

Дядя Джим дает нам две аксиомы:

  1. Сейчас в магазине есть как минимум один парикмахер (A ∨ B ∨ C)
  2. Аллен никогда не выходит из магазина без Брауна (¬A ⇒ ¬B)

Дядя Джо представляет доказательства:

Сокращенный английский с логическими маркерамиВ основном символические
Предположим, Карра НЕТ.H0: ¬C
Дано НЕ С, ЕСЛИ Аллен НЕ в ТО, ТОГДА должен быть Браун, чтобы удовлетворить Аксиому 1 (А1).Согласно H0 и A1, ¬A ⇒ B
Но из аксиомы 2 (A2) следует, что универсально верно, что IF Allen
не в ТО Браун не в (всегда верно, что если ¬A, то ¬B)		По A2, ¬A ⇒ ¬B
Пока у нас есть, что NOT C дает оба (НЕ ТО, ТОГДА B) И (НЕ ТОГО, НЕ B).Таким образом, ¬C ⇒ ((¬A ⇒ B) ∧ (¬A ⇒ ¬B))
Дядя Джо утверждает, что это противоречие.⊥
Следовательно, Карр должен быть внутри.∴C

Дядя Джо в основном утверждает, что (¬A ⇒ B) и (¬A ⇒ ¬B) противоречат друг другу, говоря, что один и тот же антецедент не может привести к двум различным консеквентам.

Это предполагаемое противоречие составляет суть «доказательства» Джо. Кэрролл представляет этот бросающий вызов интуиции результат как парадокс, надеясь, что современная двусмысленность будет разрешена.

Обсуждение

В современной теории логики этот сценарий не является парадоксом. В закон следствия согласовывает то, что утверждает дядя Джо, - несовместимые гипотезы. Этот закон гласит, что «если X, то Y» логически идентично «X ложно или Y истинно» (¬X ∨ Y). Например, учитывая утверждение «если вы нажмете кнопку, загорится свет», оно должно быть истинным в любой момент, что либо у вас есть нет нажал кнопку или горит лампочка.

Короче говоря, получается не то, что ¬C порождает противоречие, а только то, что он требует A, потому что ¬A на самом деле порождает противоречие.

В этом сценарии это означает, что Карр не должен быть внутри, но если его нет, то должен быть Аллен.

Упрощение до Аксиомы 1

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

Чтобы убедиться в этом, давайте атакуем большой «противоречивый» результат Джима, главным образом, многократно применяя закон импликации. Сначала давайте разберем одно из двух оскорбительных условий:

"Если Аллен отсутствует, значит, нет Брауна"
"Аллен в игре или Браун отсутствует"
(¬A ⇒ ¬B)
(A ∨ ¬B)

Подставив это в

«ЕСЛИ Карр отсутствует, ТО, если Аллен тоже отсутствует, значит, Браун играет, И если Аллен отсутствует, то Браун отсутствует».
¬C ⇒ ((¬A ⇒ B) ∧ (¬A ⇒ ¬B))

Что дает, при продолжении применения закона импликации,

«ЕСЛИ Карр отсутствует, ТО, если Аллен тоже отсутствует, Браун входит И либо Аллен входит, ИЛИ Браун отсутствует».
«ЕСЛИ Карр отсутствует, ТО оба из них верны: Аллен в ИЛИ, Браун в ИЛИ Аллен в ИЛИ, Браун в отключке».
«Карр в ИЛИ. Оба эти утверждения верны: Аллен в ИЛИ. Браун в ИЛИ Аллен в ИЛИ. Браун отсутствует».
¬C ⇒ ((¬A ⇒ B) ∧ (A ∨ ¬B))
¬C ⇒ ((A ∨ B) ∧ (A ∨ ¬B))
C ∨ ((A ∨ B) ∧ (A ∨ ¬B))
    • обратите внимание, что: C ∨ ((A ∨ B) ∧ (A ∨ ¬B)) можно упростить до C ∨ A
    • поскольку ((A ∨ B) ∧ (A ∨ ¬B)) просто A

И напоследок (справа разводим по скобкам)

«Карр в ИЛИ Либо Аллен в ИЛИ, ИЛИ Браун в ИЛИ, И Карр в ИЛИ, Либо Аллен в ИЛИ, ИЛИ Браун отсутствует».
«Включительно Карр находится в ИЛИ. Аллен входит в ИЛИ. Браун находится в ИЛИ. Включительно Карр входит в ИЛИ. Аллен входит в ИЛИ. Браун отсутствует».
C ∨ (A ∨ B) ∧ C ∨ (A ∨ ¬B)
(C ∨ A ∨ B) ∧ (C ∨ A ∨ ¬B)

Таким образом, сразу становятся правдивыми два утверждения: «Один или несколько из Аллена, Брауна или Карра входят», что является просто Аксиомой 1, и «Карр входит, или Аллен входит, или Браун отсутствует». Очевидно, что одним из способов одновременного выполнения обоих этих утверждений является случай, когда Аллен находится внутри (потому что дом Аллена - это парикмахерская, и в какой-то момент Браун покинул ее).

Другой способ описать, как (X ⇒ Y) ⇔ (¬X ∨ Y) превращает это в действительный набор утверждений, - это перефразировать утверждение Джима, что «Если Аллен также out ... "into" Если Карр отсутствует, а Аллен отсутствует, значит, Браун играет "((¬C ∧ ¬A) ⇒ B).

Отображение совместимых условных операторов

Эти два условия не являются логическими противоположностями: чтобы доказать от противного, Джиму нужно было показать ¬C ⇒ (Z ∧ ¬Z), где Z является условным условием.

Противоположностью (A ⇒ B) является ¬ (A ⇒ B), что, используя Закон де Моргана, преобразуется в (A ∧ ¬B), что совсем не то же самое, что (¬A ∨ ¬B), к чему сводится A ⇒ ¬B.

Эта путаница в отношении «совместимости» этих двух условных выражений была предвидена Кэрроллом, который включает упоминание об этом в конце рассказа. Он пытается прояснить этот вопрос, утверждая, что протазис и аподозис импликации «Если Карр в ...» «неправильно разделены». Однако применение Закона Импликации полностью удаляет «Если ...» (сводится к дизъюнкциям), поэтому не существует протазиса и аподозиса, и не требуется никаких контраргументов.

Смотрите также

Примечания

  1. ^ Кэрролл, Льюис (июль 1894 г.). «Логический парадокс». Разум. 3 (11): 436–438.
  2. ^ а б Кэрролл, Льюис (1977). Бартли, Уильям Уоррен (ред.). Символическая логика, части I и II. Пресс-комбайн. ISBN  0855279842.

дальнейшее чтение

  • Рассел, Бертран (1903). «Глава II. Символическая логика». Принципы математики. п. § 19 п. 1. ISBN  0-415-48741-2. Рассел предлагает функциональное понятие истинности логические условия, что (среди прочего) влечет за собой, что ложное предложение будет подразумевать все предложения. В примечании он упоминает, что его теория импликации разрешит парадокс Кэрролла, поскольку она не только позволяет, но фактически требует, чтобы обе "п подразумевает q" и "п подразумевает не-q"быть правдой, пока п не правда.