Исчисление высказываний Фрегеса - Википедия - Freges propositional calculus

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Октябрь 2019) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья возможно содержит оригинальные исследования. Пожалуйста Улучши это к проверка заявленные претензии и добавление встроенные цитаты. Заявления, содержащие только оригинальные исследования, следует удалить. (Октябрь 2019) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

В математическая логика, Исчисление высказываний Фреге был первым аксиоматизация из пропозициональное исчисление. Это было изобретено Готтлоб Фреге, который также изобрел исчисление предикатов, в 1879 г. в рамках его исчисление предикатов второго порядка (несмотря на то что Чарльз Пирс был первым, кто использовал термин «второй порядок» и разработал свою версию исчисления предикатов независимо от Фреге).

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

Исчисление высказываний Фреге эквивалентно любому другому классическому исчислению высказываний, например, «стандартному ПК» с 11 аксиомами. ПК Фреге и стандартный ПК разделяют две общие аксиомы: THEN-1 и THEN-2. Обратите внимание, что аксиомы с THEN-1 по THEN-3 используют (и определяют) только оператор импликации, тогда как аксиомы FRG-1 по FRG-3 определяют оператор отрицания.

Следующие теоремы будут стремиться найти оставшиеся девять аксиом стандартного ПК в «пространстве теорем» ПК Фреге, показывая, что теория стандартного ПК содержится в теории ПК Фреге.

(Теория, также называемая здесь в переносных целях «пространством теорем», представляет собой набор теорем, которые являются подмножеством универсального набора правильные формулы. Теоремы связаны между собой направленным образом: правила вывода, образуя своего рода дендритную сеть. В основе пространства теорем находятся аксиомы, которые «порождают» пространство теорем во многом как генераторная установка генерирует группу.)

Правила

Теоремы

Примечание: ¬ (A → ¬B) → A (TH4), ¬ (A → ¬B) → B (TH6) и A → (B → ¬ (A → ¬B)) (TH10), поэтому ¬ (A → ¬B) ведет себя так же, как A∧B (сравните с аксиомами AND-1, AND-2 и AND-3).

TH11 - это аксиома НЕ-1 стандартного ПК, называемая "сокращение до абсурда ".

Теорема TH15 - это разговаривать аксиомы ТО-2.

Сравните TH17 с теоремой TH5.

Примечание: A → ((A → B) → B) (TH8), B → ((A → B) → B) (TH9) и (A → C) → ((B → C) → (((A → B) → B) → C)) (TH19), поэтому ((A → B) → B) ведет себя так же, как A∨B. (Сравните с аксиомами OR-1, OR-2 и OR-3.)

TH20 соответствует аксиоме НЕ-3 стандартного ПК, называемой "tertium non datur ".

TH21 соответствует аксиоме НЕ-2 стандартного ПК, называемой "ex противоречие quodlibet ".

Все аксиомы стандартного ПК были заимствованы из ПК Фреге после того, как

A∧B: = ¬ (A → ¬B) и A∨B: = (A → B) → B. Эти выражения не уникальны, например A∨B также можно было определить как (B → A) → A, ¬A → B или ¬B → A. Однако обратите внимание, что определение A∨B: = (A → B) → B не содержит отрицаний. С другой стороны, A∧B нельзя определить только в терминах импликации без использования отрицания.

В некотором смысле выражения A∧B и A∨B можно рассматривать как «черные ящики». Внутри эти черные ящики содержат формулы, состоящие только из импликации и отрицания. Черные ящики могут содержать что угодно, пока они подключены к аксиомам от AND-1 до AND-3 и OR-1 до OR-3 стандартного ПК, эти аксиомы остаются верными. Эти аксиомы предоставляют полные синтаксические определения соединение и дизъюнкция операторы.

Следующий набор теорем будет направлен на поиск оставшихся четырех аксиом ПК Фреге в «пространстве теорем» стандартного ПК, показывая, что теория ПК Фреге содержится в теории стандартного ПК.

ST2 - аксиома FRG-3 ПК Фреге.

ST4 - аксиома FRG-2 ПК Фреге.

Докажите ST5: (A → (B → C)) → (B → (A → C))

ST5 - это аксиома THEN-3 ПК Фреге.

ST6 - аксиома FRG-1 ПК Фреге.

Каждую из аксиом Фреге можно вывести из стандартных аксиом, и каждую из стандартных аксиом можно вывести из аксиом Фреге. Это означает, что два набора аксиом взаимозависимы, и в одном наборе нет аксиомы, независимой от другого. Следовательно, эти два набора аксиом порождают одну и ту же теорию: ПК Фреге эквивалентен стандартному ПК.

(Поскольку, если теории должны быть разными, то одна из них должна содержать теоремы, не содержащиеся в другой теории. Эти теоремы могут быть выведены из набора аксиом их собственной теории: но, как было показано, весь этот набор аксиом может быть получен из другой теории. набор аксиом теории, что означает, что данные теоремы могут быть фактически получены исключительно из набора аксиом другой теории, так что данные теоремы также принадлежат другой теории. Противоречие: таким образом, два набора аксиом охватывают одно и то же пространство теорем. : Любая теорема, полученная из стандартных аксиом, может быть выведена из аксиом Фреге, и наоборот, сначала доказывая как теоремы аксиомы другой теории, как показано выше, а затем используя эти теоремы как леммы для вывода желаемой теоремы.)

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

• Begriffsschrift
• Хью МакКолл с Исчисление эквивалентных утверждений

Рекомендации

• Басс, Сэмюэл (1998). «Введение в теорию доказательств» (PDF). Справочник по теории доказательств. Эльзевир. С. 1–78. ISBN  0-444-89840-9.
• Детловс, Вилнис; Подниекс, Карлис (24 мая 2017 г.). «Аксиомы логики: минимальная система, конструктивная система и классическая система». Введение в математическую логику (PDF). Латвийский университет. С. 29–30.