Закон Пирса - Peirce's law

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

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

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

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

История

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

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

{( x → y ) → x } → x .

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

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

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

{( x → y ) → a } → x ,

где 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 → Z	1. гипотеза
( P → Q ) → Z	2. гипотеза
Z → Q	3. гипотеза
п	4. гипотеза
Z	5. modus ponens, используя шаги 4 и 1
Q	6. modus ponens, используя шаги 5 и 3
P → Q	7. сбавка с 4 до 6
Z	8. modus ponens, используя шаги 7 и 2.
( Z → Q ) → Z	9. сбавка с 3 до 8
(( Z → Q ) → Z ) → Z	10. Закон Пирса.
Z	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 содержат только «→» в качестве связки) - все тавтологии, которые используют только «→» в качестве связки.

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

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

Заметки

↑ Брент, Джозеф (1998), Чарльз Сандерс Пирс: Жизнь , 2-е издание, Блумингтон и Индианаполис: Издательство Индианского университета ( страница каталога ); также NetLibrary .
^ Тимоти Г. Гриффин, «Понятие управления формулами как типами», 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.

[1] Брент, Джозеф (1998), Чарльз Сандерс Пирс: Жизнь , 2-е издание, Блумингтон и Индианаполис: Издательство Индианского университета ( страница каталога ); также NetLibrary .

[2] Тимоти Г. Гриффин, «Понятие управления формулами как типами», 1990 г. - Гриффин определяет K на стр. 3 как эквивалент вызова / cc в Схеме, а затем обсуждает его тип, являющийся эквивалентом закона Пирса в конце раздела 5. стр.9.

Languages

In other projects