Закон Пирса

В логике назван закон Пирса в честь философа и логика Чарльза Сандерса Пирса . Это было принято как аксиома в его первой аксиоматизации логики высказываний . Его можно рассматривать как закон исключенного третьего, записанный в форме, которая включает только один вид связки, а именно импликацию.

В высказываний исчислении закон Пирса гласит, что (( P → Q )→ P )→ P . Вкратце это означает, что P должно быть истинным, если существует предложение Q такое, что истинность P следует из истины «если P, то Q ».

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

При изоморфизме Карри-Говарда закон Пирса является типом операторов продолжения , например call/cc в Scheme .

История

Вот формулировка закона самим Пирсом:

Пятая икона необходима для принципа исключенного среднего и других связанных с ним пропозиций. Одна из простейших формул такого рода:

{( Икс ⤙ y ) ⤙ Икс } ⤙ Икс .

Вряд ли это аксиома. То, что это правда, проявляется в следующем. Оно может быть ложным только в том случае, если конечный консеквент x ложен, в то время как его антецедент ( x ⤙ y ) ⤙ x истинен. Если это правда, то либо ее консеквент x является истинным, хотя вся формула была бы истинной, либо ее антецедент x ⤙ y является ложным. Но в последнем случае антецедент x ⤙ y , то есть x , должен быть истинным. (Пирс, Сборник статей 3.384).

Пирс далее указывает на немедленное применение закона:

Из только что приведенной формулы сразу получаем:

{( Икс ⤙ у ) ⤙ а } ⤙ Икс ,

где a используется в таком смысле, что ( x ⤙ y ) ⤙ a означает, что из ( x ⤙ y ) следует каждое предложение. При таком понимании формула утверждает принцип исключенного третьего, согласно которому из ложности отрицания x следует истинность x . (Пирс, Сборник статей 3.384).

Предупреждение : как поясняется в тексте, « а » здесь обозначает не пропозициональный атом, а что-то вроде квантифицированной пропозициональной формулы. $\forall p\,p$. Формула (( x → y ) → a ) → x не было бы тавтологией , если бы a интерпретировалось как атом.

Отношения между принципами

В интуиционистской логике, если $P$ доказано или отвергнуто, или если $Q$ доказана справедливость, то справедлив закон Писа для двух предложений. Но особый случай закона, когда $Q$ отвергается, называется Conceconcia mirabilis , эквивалентно исключенному среднему уже по минимальной логике . Это также означает, что закон Писа влечет за собой классическую логику, а не интуиционистскую логику, как также показано ниже. Интуиционистски, даже ограничение $\neg Q\to P$ подразумевает закон для двух предложений. Постулирование истинности последнего приводит к промежуточной логике Сметанича .

Полезно рассмотреть закон Пирса в эквивалентной форме $((P\to Q)\to (P\land Q))\to P$. Действительно, из $P\to Q$ следует $P\leftrightarrow (P\land Q)$, и так $(P\to Q)\to P$ эквивалентно $(P\to Q)\to (P\land Q)$. Дело $Q=\bot$ теперь напрямую показывает, как устранение двойного отрицания $\neg \neg P\to P$ полный чудесных следствий по сравнению с минимальной логикой.

В интуиционистской логике взрыв можно использовать для $\bot \to (P\land \bot )$, и поэтому здесь особый случай последствия закона также подразумевает устранение двойного отрицания. Поскольку двойное отрицание исключенного третьего всегда уже действительно, даже в минимальной логике, это также интуиционистски доказывает исключенное среднее. В другом направлении можно также интуитивно показать, что исключенное среднее напрямую подразумевает закон Писа. С этой целью заметим, что, используя принцип взрыва , исключенную середину можно выразить как $P\lor (P\to Q)$. Словами это можно выразить так: «Каждое предложение $P$ либо содержит, либо подразумевает любое другое предложение». Теперь, чтобы доказать закон, заметим, что $(P\lor R)\to ((R\to P)\to P)$ выводится из простого введения импликации, с одной стороны, и modus ponens , с другой. Наконец, вместо $R$ учитывать $P\to Q$.

Другое доказательство закона классической логики основано на дважды проходе через классически действительный обратный дизъюнктивный силлогизм : Сначала обратите внимание, что $\neg \neg P$ подразумевается $(\neg \neg P\land \neg Q)\lor P$, что интуитивно эквивалентно $\neg (\neg P\lor Q)\lor P$. Теперь взрыв влечет за собой это $\neg A\lor B$ подразумевает $A\to B$и используя исключенное среднее для $A$ означает, что эти два понятия фактически эквивалентны. В совокупности это означает, что в классической логике $P$ эквивалентно $(P\to Q)\to P$.

Использование закона Пирса с теоремой о дедукции

Закон Пирса позволяет усовершенствовать технику использования теоремы дедукции для доказательства теорем. Предположим, что вам дан набор посылок Γ и вы хотите вывести предложение Z. из них С помощью закона Пирса можно добавить (бесплатно) дополнительные посылки вида Z → P к Γ. Например, предположим, что нам даны P → Z и ( P → Q ) → Z , и мы хотим вывести Z , чтобы мы могли использовать теорему о дедукции, чтобы заключить, что ( P → Z ) → ((( P → Q ) → Z )→ Z ) — теорема. мы можем добавить еще одну посылку Z → Q. Тогда Отсюда P → Z получаем P → Q. и Затем мы применяем modus ponens с ( P → Q )→ Z в качестве основной предпосылки для Z. получения Применяя теорему дедукции, получаем, что ( Z → Q )→ Z следует из исходных посылок. Затем мы используем закон Пирса в форме (( Z → Q ) → Z ) → Z и modus ponens, чтобы вывести Z из исходных посылок. Тогда мы сможем завершить доказательство теоремы так, как планировали изначально.

P → Z	1. гипотеза
( P → Q )→ Z	2. гипотеза
Z → Q	3. гипотеза
П	4. гипотеза
С	5. modus ponens, используя шаги 4 и 1.
вопрос	6. modus ponens, используя шаги 5 и 3.
P → Q	7. вычет от 4 до 6
С	8. modus ponens, используя шаги 7 и 2.
( Z → Q )→ Z	9. вычет от 3 до 8
(( Z → Q )→ Z )→ Z	10. Закон Пирса
С	11. modus ponens, используя шаги 9 и 10.
(( P → Q )→ Z )→ Z	12. вычет от 2 до 11
( P → Z )→((( P → Q )→ Z )→ Z )	13. вычет от 1 до 12 QED

Полнота импликативного исчисления высказываний

Основная статья: Импликативное исчисление высказываний

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

• P →( Q → P )
• ( P →( Q → R ))→(( P → Q )→( P → R ))
• (( P → Q )→ P )→ P
• из P и P → Q вывести Q

(где P , Q , R содержат только «→» в качестве связки) — это все тавтологии , в которых в качестве связки используется только «→».

Неудача неклассических моделей интуиционистской логики

Поскольку закон Пирса подразумевает закон исключенного третьего, он всегда должен ошибаться в неклассической интуиционистской логике. Простой явный контрпример — это многозначная логика Гёделя , которая представляет собой нечеткую логику , в которой истинностные значения представляют собой действительные числа от 0 до 1, с материальной импликацией, определяемой следующим образом:

${\begin{aligned}u\mathrel {\xrightarrow[{G}]{}} v&={\begin{cases}1,&{\text{if }}u\leq v\\v,&{\text{if }}u>v\end{cases}}\end{aligned}}$

и где закон Пирса как формулу можно упростить до:

${\begin{aligned}((u\mathrel {\xrightarrow[{G}]{}} v)\mathrel {\xrightarrow[{G}]{}} u)\mathrel {\xrightarrow[{G}]{}} u&={\begin{cases}1,&{\text{if }}u\leq v\\u,&{\text{if }}u>v\end{cases}}\end{aligned}}$

где это всегда верно, было бы эквивалентно утверждению, что u > v подразумевает u = 1, что верно только в том случае, если 0 и 1 являются единственными разрешенными значениями. Однако в то же время выражение никогда не может быть равно нижнему значению истинности логики, и его двойное отрицание всегда истинно.

См. также

• Библиография Чарльза Сандерса Пирса

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

• Пирс, К.С., «Об алгебре логики: вклад в философию обозначений», American Journal of Mathematics 7, 180–202 (1885). Перепечатано: Сборник статей Чарльза Сандерса Пирса 3.359–403 и Сочинения Чарльза С. Пирса: хронологическое издание 5, 162–190.
• Пирс, CS, Сборник статей Чарльза Сандерса Пирса , Vols. 1–6, Чарльз Хартшорн и Пол Вайс (ред.), Vols. 7–8, Артур В. Беркс (редактор), издательство Гарвардского университета, Кембридж, Массачусетс, 1931–1935, 1958.