Закон Пирса - Peirces law - Wikipedia

Чарльз Сандерс Пирс
Общий
Философский
Биографический

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

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

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

Под Изоморфизм Карри – Ховарда, Закон Пирса - это тип продолжение операторы, например вызов / cc в Схема.[2]

История

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

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

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

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

Предупреждение: ((Икс→у)→а)→Икс является нет а тавтология. Тем не мение, [а→Икс]→[((Икс→у)→а)→Икс] - тавтология.

Прочие доказательства

Вот простое доказательство закона Пирса, предполагающего двойное отрицание и вывод стандартной дизъюнкции из импликации :

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

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

  • п→Z
1. гипотеза
    • (п→Q)→Z
2. гипотеза
      • Z→Q
3. гипотеза
        • п
4. гипотеза
        • Z
5. modus ponens, используя шаги 4 и 1
        • Q
6. modus ponens, используя шаги 5 и 3
        • п→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
  • ((п→Q)→Z)→Z
12. сбавка от 2 до 11

(п→Z)→(((п→Q)→Z)→Z)

13. удержание от 1 до 12 QED

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

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

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

  • п→(Q→п)
  • (п→(Q→р))→((п→Q)→(п→р))
  • ((п→Q)→п)→п
  • из п и п→Q сделать вывод Q

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

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

Примечания

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

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

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