Парадокс парикмахерской был предложен Льюисом Кэрроллом в трехстраничном эссе под названием «Логический парадокс», опубликованный в июльском 1894 году журнала Mind. Название происходит от «декоративного» рассказа, который Кэрролл использует в статье, чтобы проиллюстрировать парадокс. Раньше он существовал в нескольких альтернативных формах в его письмах и переписке, не всегда с участием парикмахерской. Кэрролл описал это как иллюстрацию «очень реальной трудности в теории гипотетических предположений». С точки зрения современной логики это рассматривается не столько как парадокс, сколько как простая логическая ошибка. Сейчас он представляет интерес главным образом как эпизод в развитии алгебраико-логических методов, когда они не были так широко поняты (даже среди логиков), хотя проблема продолжает обсуждаться в связи с теориями импликация и модальная логика.
По сюжету дядя Джо и дядя Джим пешком до парикмахерской. Они объясняют, что в магазине живут и работают три парикмахера - Аллен, Браун и Карр - и некоторые или все из них могут быть там. Нам даются две части информации, из которых мы можем сделать выводы. Во-первых, магазин определенно открыт, поэтому должен быть хотя бы один из парикмахеров. Во-вторых, говорят, что Аллен очень нервничает, поэтому он никогда не выходит из магазина, если с ним не пойдет Браун.
Итак, по словам дяди Джима, Карр очень хороший парикмахер, и он хочет знать, будет ли Карр там, чтобы побрить его. Дядя Джо настаивает на том, что Карр обязательно присутствует, и утверждает, что может доказать это логически. Дядя Джим требует доказательства.
Дядя Джо приводит следующие аргументы:
Предположим, Карра нет. Мы покажем, что это предположение приводит к противоречию. Если Карра нет, то мы знаем следующее: «Если Аллена нет, значит Браун в игре», потому что должен быть кто-то, чтобы «следить за магазином». Но мы также знаем, что всякий раз, когда Аллен выходит, он берет с собой Брауна, поэтому, как правило, «если Аллен отсутствует, то и Браун отсутствует». Два утверждения, к которым мы пришли, несовместимы, потому что, если Аллен отсутствует, Браун не может быть одновременно входом (согласно одному) и выходом (согласно другому). Есть противоречие. Таким образом, мы должны отказаться от нашей гипотезы о том, что Карр отсутствует, и заключить, что Карр должен быть в игре.
Дядя Джим отвечает, что такой вывод необоснован. Правильный вывод, который можно сделать из несовместимости двух «гипотетических» гипотез, состоит в том, что то, что предполагается в них (что Аллен отсутствует), должно быть ложным при нашем предположении, что Карр отсутствует. Тогда наша логика просто позволяет нам прийти к выводу: «Если Карр отсутствует, то обязательно должен быть Аллен».
Парадокс возник из-за разногласий между Кэрроллом и его коллегой из Оксфорда, профессором логики Уайкхема Джоном Куком Уилсоном, двое из которых долгое время имели Бегущий антагонизм. Проблема также обсуждалась другими людьми, с которыми Кэрролл переписывался, и рассматривалась в более поздних статьях, опубликованных, среди прочих, Джоном Венном, Альфредом Сиджвиком и Бертраном Расселом. Взгляд Кука Уилсона представлен в рассказе персонажем дяди Джо, который пытается доказать, что Карр всегда должен оставаться в магазине. Другие придерживались того же мнения, когда Кэрролл распространял свои частные печатные версии проблемы. Как заметил Кэрролл: «Я переписываюсь с дюжиной логиков по этому любопытному вопросу; и до сих пор мнения относительно свободы С разделились поровну».
При чтении оригинала полезно иметь в виду следующее:
Символы могут использоваться в значительной степени упростите логические утверждения, такие как те, которые присущи этой истории:
Оператор (Имя) | Разговорный | Символический | ||
---|---|---|---|---|
Отрицание | НЕ | не X | ¬ | ¬X |
Соединение | И | X и Y | ∧ | X ∧ Y |
Дизъюнкция | OR | X или Y | ∨ | X ∨ Y |
Условное | ЕСЛИ... ТО | если X, то Y | ⇒ | X ⇒ Y |
Примечание: X ⇒ Y (также известное как «Implication») может быть прочитано по-разному в английском языке, от «X достаточно для Y» до «Y следует из X». (См. Также Таблица математических символов.)
Чтобы упростить переформулирование истории Кэрролла, мы возьмем следующие атомарные утверждения :
Так, например, (¬A ∧ B) означает «Аллен отсутствует, а Браун в "
дядя Джим дает нам две аксиомы:
Дядя Джо представляет доказательство:
Сокращенный английский с логическими маркерами | В основном символический |
---|---|
Предположим, что Карра НЕТ. | H0: ¬C |
Дано НЕ С, ЕСЛИ Аллен НЕ в ТО, ТОГДА должен быть Браун, чтобы удовлетворить Аксиому 1 (А1). | Согласно H0 и A1, ¬A ⇒ B |
Но аксиома 2 (A2) утверждает, что универсально верно, что ЕСЛИ Аллен. не в, ТО Браун не в (всегда верно, что если ¬A, то ¬B) | По A2, ¬A ⇒ ¬B |
Итак, мы имеем, что NOT C дает оба (не A THEN B) AND (не A THEN Not B). | Таким образом, ¬C ⇒ ((¬A ⇒ B) ∧ (¬A ⇒ ¬B)) |
Дядя Джо утверждает, что они противоречат друг другу. | ⊥ |
Следовательно, Карр должен быть внутри. | ∴C |
Дядя Джо в основном утверждает, что (¬A ⇒ B) и (¬A ⇒ ¬B) противоречат друг другу, говоря, что одно и то же не может привести к двум различным консеквентам.
Это предполагаемое противоречие составляет суть «доказательства» Джо. Кэрролл представляет этот бросающий вызов интуиции результат как парадокс, надеясь, что современная двусмысленность будет разрешена.
В современной теории логики этот сценарий не является парадоксом. закон импликации согласовывает то, что дядя Джо утверждает, что гипотетические гипотезы несовместимы. Этот закон гласит, что «если X, то Y» логически идентично «X ложно или Y истинно» (¬X ∨ Y). Например, учитывая утверждение «если вы нажмете кнопку, то загорится свет», должно быть верно в любой момент, что либо вы не нажимали кнопку, либо свет горит.
Короче говоря, получается не то, что ¬C порождает противоречие, а только то, что он требует A, потому что ¬A на самом деле порождает противоречие.
В этом сценарии это означает, что Карр не должен быть внутри, но если его нет, то должен быть Аллен.
Применение закона следствия к оскорбительным условным выражениям показывает, что вместо того, чтобы противоречить друг другу, просто повторяется тот факт, что, поскольку магазин открыт, один или несколько из Аллена, Брауна или Карра находятся внутри, а другой накладывает очень мало ограничений на то, кто может или не может быть в магазине.
Чтобы увидеть это, давайте атакуем большой «противоречивый» результат Джима, в основном применяя многократно закон импликации. Сначала давайте разберем одно из двух оскорбительных условий:
|
|
Подставляя это в
|
|
Что дает, при продолжении применения закона импликации,
|
|
И, наконец, (справа мы dist в скобках)
|
|
Итак, два утверждения, которые становятся истинными одновременно: «Один или несколько из Аллена, Брауна или Карра находятся внутри», что является просто Аксиомой 1, и «Карр в игре, или Аллен, или Браун вне игры». Очевидно, что одним из способов одновременного осуществления обоих этих утверждений является случай, когда Аллен находится внутри (потому что дом Аллена - это парикмахерская, и в какой-то момент Браун покинул ее).
Другой способ описать, как (X ⇒ Y) ⇔ (¬X ∨ Y) превращает это в действительный набор утверждений, - это перефразировать утверждение Джима о том, что «Если Аллена тоже нет...» в «Если Карр отсутствует, а Аллен отсутствует, значит, Браун играет "((¬C ∧ ¬A) ⇒ B).
Эти два условных оператора не являются логическими противоположностями: чтобы доказать противоречие, Джиму нужно было показать ¬C ⇒ (Z ∧ ¬Z), где Z является условным.
Противоположностью (A ⇒ B) является ¬ (A ⇒ B), которое, используя закон Де Моргана, преобразуется в (A ∧ ¬B), что вовсе не является то же самое, что и (¬A ∨ ¬B), к чему сводится A ⇒ ¬B.
Эта путаница в отношении «совместимости» этих двух условных выражений была предвидена Кэрроллом, который включает упоминание об этом в конце рассказа. Он пытается прояснить этот вопрос, утверждая, что протазис и аподозис импликации «Если Карр в...» «неправильно разделены». Однако применение Закона Импликации полностью удаляет «Если...» (сводится к дизъюнкциям), поэтому не существует протазиса и аподозиса, и не требуется никаких контраргументов.