Закон Пирса

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

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

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

Согласно изоморфизму Карри – Ховарда, закон Пирса является типом операторов продолжения, например call / cc в Scheme.

• 1 История
• 2 Другие доказательства
• 3 Использование закона Пирса с теоремой дедукции
• 4 Полнота импликативного исчисления высказываний
• 5 См. Также
• 6 Примечания
• 7 Дальнейшее чтение

Вот собственное утверждение закона Пирса:

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

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

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

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

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

Внимание: (( х → у) →) → х это не тавтология. Однако [ a → x ] → [(( x → y) → a) → x ] - тавтология.

Вот простое доказательство закона Пирса, предполагающего двойное отрицание и выводящего стандартную дизъюнкцию из импликации: ${\ displaystyle (\ neg \ neg P \ iff P)}$${\ Displaystyle ((P \ rightarrow Q) \ Rightarrow (\ neg P \ vee Q))}$

${\ Displaystyle {\ begin {выровнен} (п \ rightarrow q) \ rightarrow p \\\ neg (p \ rightarrow q) \ lor p \\\ neg (\ neg p \ lor q) \ lor p \\ (p \ land \ neg q) \ lor p \\ p \ lor p \\ p. \\\ конец {выровнено}}}$

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

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

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

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

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

1. ↑ Брент, Джозеф (1998), Чарльз Сандерс Пирс: Жизнь, 2-е издание, Блумингтон и Индианаполис: Издательство Индианского университета ( страница каталога ); также NetLibrary.
2. ^ Тимоти Г. Гриффин, «Понятие управления формулами как типами», 1990 г. - Гриффин определяет K на стр. 3 как эквивалент вызова / cc в Схеме, а затем обсуждает его тип, являющийся эквивалентом закона Пирса в конце раздела 5. стр.9.

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