Исчисление высказываний Фреге - Frege's propositional calculus

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

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

Аксиомы Правило вывода
ТО-1
А → (В → А)
ТО-2
(A → (B → C)) → ((A → B) → (A → C))
ТО-3
(A → (B → C)) → (B → (A → C))
ФРГ-1
(A → B) → (¬B → ¬A)
ФРГ-2
¬¬A → А
ФРГ-3
А → ¬¬A
Депутат
P, P → Q ⊢ Q

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

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

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

Правила

Правило   ( ТО-1 )  -  A A B → A

# wff причина
1. А посылка
2. А → (В → А) ТО-1
3. Б → А МП 1,2.

Правило   ( ТО-2 )  -  A → (B → C) ⊢ (A → B) → (A → C)

# wff причина
1. А → (В → С) посылка
2. (A → (B → C)) → ((A → B) → (A → C)) ТО-2
3. (А → В) → (А → С) МП 1,2.

Правило   ( ТО-3 )  -  A → (B → C) ⊢ B → (A → C)

# wff причина
1. А → (В → С) посылка
2. (A → (B → C)) → (B → (A → C)) ТО-3
3. В → (А → С) МП 1,2.

Правило   ( ФРГ-1 )  -  А → В ⊢ ¬B → ¬A

# wff причина
1. (A → B) → (¬B → ¬A) ФРГ-1
2. А → Б посылка
3. ¬B → ¬A МП 2,1.

Правило   ( TH1 )  -  A → B, B → C ⊢ A → C

# wff причина
1. B → C посылка
2. (B → C) → (A → (B → C)) ТО-1
3. А → (В → С) МП 1,2
4. (A → (B → C)) → ((A → B) → (A → C)) ТО-2
5. (А → В) → (А → С) MP 3,4
6. А → Б посылка
7. А → С МП 6,5.

Теоремы

Теорема   ( TH1 )  -  (A → B) → ((B → C) → (A → C))

# wff причина
1. (B → C) → (A → (B → C)) ТО-1
2. (A → (B → C)) → ((A → B) → (A → C)) ТО-2
3. (B → C) → ((A → B) → (A → C)) TH1 * 1,2
4. ((B → C) → ((A → B) → (A → C))) → ((A → B) → ((B → C) → (A → C))) ТО-3
5. (A → B) → ((B → C) → (A → C)) МП 3,4.

Теорема   ( TH2 )  -  А → (¬A → ¬B)

# wff причина
1. А → (В → А) ТО-1
2. (B → A) → (¬A → ¬B) ФРГ-1
3. А → (¬A → ¬B) TH1 * 1,2.

Теорема   ( TH3 )  -  ¬A → (A → ¬B)

# wff причина
1. А → (¬A → ¬B) TH 2
2. (A → (¬A → ¬B)) → (¬A → (A → ¬B)) ТО-3
3. ¬A → (A → ¬B) МП 1,2.

Теорема   ( TH4 )  -  ¬ (А → ¬B) → А

# wff причина
1. ¬A → (A → ¬B) TH3
2. (¬A → (A → ¬B)) → (¬ (A → ¬B) → ¬¬A) ФРГ-1
3. ¬ (А → ¬B) → ¬¬A МП 1,2
4. ¬¬A → А ФРГ-2
5. ¬ (А → ¬B) → А TH1 * 3,4.

Теорема   ( TH5 )  -  (A → ¬B) → (B → ¬A)

# wff причина
1. (А → ¬B) → (¬¬B → ¬A) ФРГ-1
2. ((A → ¬B) → (¬¬B → ¬A)) → (¬¬B → ((A → ¬B) → ¬A)) ТО-3
3. ¬¬B → ((A → ¬B) → ¬A) МП 1,2
4. B → ¬¬B ФРГ-3, с A: = B
5. B → ((A → ¬B) → ¬A) TH1 * 4,3
6. (B → ((A → ¬B) → ¬A)) → ((A → ¬B) → (B → ¬A)) ТО-3
7. (A → ¬B) → (B → ¬A) МП 5,6.

Теорема   ( TH6 )  -  ¬ (A → ¬B) → B

# wff причина
1. ¬ (B → ¬A) → B TH4, где A: = B, B: = A
2. (B → ¬A) → (A → ¬B) TH5, где A: = B, B: = A
3. ((B → ¬A) → (A → ¬B)) → (¬ (A → ¬B) → ¬ (B → ¬A)) ФРГ-1
4. ¬ (A → ¬B) → ¬ (B → ¬A) MP 2,3
5. ¬ (A → ¬B) → B TH1 * 4,1.

Теорема   ( TH7 )  -  А → А

# wff причина
1. А → ¬¬A ФРГ-3
2. ¬¬A → А ФРГ-2
3. А → А TH1 * 1,2.

Теорема   ( TH8 )  -  А → ((А → В) → В)

# wff причина
1. (А → В) → (А → В) TH7, где A: = A → B
2. ((A → B) → (A → B)) → (A → ((A → B) → B)) ТО-3
3. А → ((А → В) → Б) МП 1,2.

Теорема   ( TH9 )  -  B → ((A → B) → B)

# wff причина
1. Б → ((А → В) → Б) ТО-1, где A: = B, B: = A → B.

Теорема   ( TH10 )  -  A → (B → ¬ (A → ¬B))

# wff причина
1. (A → ¬B) → (A → ¬B) TH7
2. ((A → ¬B) → (A → ¬B)) → (A → ((A → ¬B) → ¬B) ТО-3
3. А → ((А → ¬B) → ¬B) МП 1,2
4. ((A → ¬B) → ¬B) → (B → ¬ (A → ¬B)) TH5
5. A → (B → ¬ (A → ¬B)) TH1 * 3,4.

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

Теорема   ( TH11 )  -  (A → B) → ((A → ¬B) → ¬A)

# wff причина
1. A → (B → ¬ (A → ¬B)) TH10
2. (A → (B → ¬ (A → ¬B))) → ((A → B) → (A → ¬ (A → ¬B))) ТО-2
3. (A → B) → (A → ¬ (A → ¬B)) МП 1,2
4. (A → ¬ (A → ¬B)) → ((A → ¬B) → ¬A) TH5
5. (A → B) → ((A → ¬B) → ¬A) TH1 * 3,4.

TH11 - это аксиома НЕ-1 стандартного ПК, называемая « reductio ad absurdum ».

Теорема   ( TH12 )  -  ((A → B) → C) → (A → (B → C))

# wff причина
1. В → (А → В) ТО-1
2. (B → (A → B)) → (((A → B) → C) → (B → C)) TH1
3. ((A → B) → C) → (B → C) МП 1,2
4. (B → C) → (A → (B → C)) ТО-1
5. ((A → B) → C) → (A → (B → C)) TH1 * 3,4.

Теорема   ( TH13 )  -  (B → (B → C)) → (B → C)

# wff причина
1. (B → (B → C)) → ((B → B) → (B → C)) ТО-2
2. (B → B) → ((B → (B → C)) → (B → C)) ТО-3 * 1
3. B → B TH7
4. (B → (B → C)) → (B → C) МП 3,2.

Правило   ( TH14 )  -  A → (B → P), P → Q ⊢ A → (B → Q)

# wff причина
1. P → Q посылка
2. (P → Q) → (B → (P → Q)) ТО-1
3. B → (P → Q) МП 1,2
4. (B → (P → Q)) → ((B → P) → (B → Q)) ТО-2
5. (B → P) → (B → Q) MP 3,4
6. ((B → P) → (B → Q)) → (A → ((B → P) → (B → Q))) ТО-1
7. A → ((B → P) → (B → Q)) MP 5,6
8. (A → (B → P)) → (A → (B → Q)) ТОГДА-2 * 7
9. А → (В → П) посылка
10. А → (В → Q) МП 9,8.

Теорема   ( TH15 )  -  ((A → B) → (A → C)) → (A → (B → C))

# wff причина
1. ((A → B) → (A → C)) → (((A → B) → A) → ((A → B) → C)) ТО-2
2. ((A → B) → C) → (A → (B → C)) TH12
3. ((A → B) → (A → C)) → (((A → B) → A) → (A → (B → C))) TH14 * 1,2
4. ((A → B) → A) → (((A → B) → (A → C)) → (A → (B → C))) ТО-3 * 3
5. А → ((А → В) → А) ТО-1
6. A → (((A → B) → (A → C)) → (A → (B → C))) TH1 * 5,4
7. ((A → B) → (A → C)) → (A → (A → (B → C))) ТО-3 * 6
8. (A → (A → (B → C))) → (A → (B → C)) TH13
9. ((A → B) → (A → C)) → (A → (B → C)) TH1 * 7,8.

Теорема TH15 является обратной аксиомой ТО-2.

Теорема   ( TH16 )  -  (¬A → ¬B) → (B → A)

# wff причина
1. (¬A → ¬B) → (¬¬B → ¬¬A) ФРГ-1
2. ¬¬B → ((¬A → ¬B) → ¬¬A) ТО-3 * 1
3. B → ¬¬B ФРГ-3
4. В → ((¬A → ¬B) → ¬¬A) TH1 * 3,2
5. (¬A → ¬B) → (B → ¬¬A) ТО-3 * 4
6. ¬¬A → А ФРГ-2
7. (¬¬A → A) → (B → (¬¬A → A)) ТО-1
8. Б → (¬¬A → А) МП 6,7
9. (B → (¬¬A → A)) → ((B → ¬¬A) → (B → A)) ТО-2
10. (B → ¬¬A) → (B → A) MP 8,9
11. (¬A → ¬B) → (B → A) TH1 * 5,10.

Теорема   ( TH17 )  -  (¬A → B) → (¬B → A)

# wff причина
1. (¬A → ¬¬B) → (¬B → A) TH16, с B: = ¬B
2. B → ¬¬B ФРГ-3
3. (B → ¬¬B) → (¬A → (B → ¬¬B)) ТО-1
4. ¬A → (B → ¬¬B) MP 2,3
5. (¬A → (B → ¬¬B)) → ((¬A → B) → (¬A → ¬¬B)) ТО-2
6. (¬A → B) → (¬A → ¬¬B) MP 4,5
7. (¬A → B) → (¬B → A) TH1 * 6,1.

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

Теорема   ( TH18 )  -  ((A → B) → B) → (¬A → B)

# wff причина
1. (A → B) → (¬B → (A → B)) ТО-1
2. (¬B → ¬A) → (A → B) TH16
3. (¬B → ¬A) → (¬B → (A → B)) TH1 * 2,1
4. ((¬B → ¬A) → (¬B → (A → B))) → (¬B → (¬A → (A → B))) TH15
5. ¬B → (¬A → (A → B)) MP 3,4
6. (¬A → (A → B)) → (¬ (A → B) → A) TH17
7. ¬B → (¬ (A → B) → A) TH1 * 5,6
8. (¬B → (¬ (A → B) → A)) → ((¬B → ¬ (A → B)) → (¬B → A)) ТО-2
9. (¬B → ¬ (A → B)) → (¬B → A) MP 7,8
10. ((A → B) → B) → (¬B → ¬ (A → B)) ФРГ-1
11. ((A → B) → B) → (¬B → A) TH1 * 10,9
12. (¬B → A) → (¬A → B) TH17
13. ((A → B) → B) → (¬A → B) TH1 * 11,12.

Теорема   ( TH19 )  -  (A → C) → ((B → C) → (((A → B) → B) → C))

# wff причина
1. ¬A → (¬B → ¬ (¬A → ¬¬B)) TH10
2. B → ¬¬B ФРГ-3
3. (B → ¬¬B) → (¬A → (B → ¬¬B)) ТО-1
4. ¬A → (B → ¬¬B) MP 2,3
5. (¬A → (B → ¬¬B)) → ((¬A → B) → (¬A → ¬¬B)) ТО-2
6. (¬A → B) → (¬A → ¬¬B) MP 4,5
7. ¬ (¬A → ¬¬B) → ¬ (¬A → B) ФРГ-1 * 6
8. ¬A → (¬B → ¬ (¬A → B)) TH14 * 1,7
9. ((A → B) → B) → (¬A → B) TH18
10. ¬ (¬A → B) → ¬ ((A → B) → B) ФРГ-1 * 9
11. ¬A → (¬B → ¬ ((A → B) → B)) TH14 * 8,10
12. ¬C → (¬A → (¬B → ¬ ((A → B) → B))) ТО-1 * 11
13. (¬C → ¬A) → (¬C → (¬B → ¬ ((A → B) → B))) ТО-2 * 12
14. (¬C → (¬B → ¬ ((A → B) → B))) → ((¬C → ¬B) → (¬C → ¬ ((A → B) → B))) ТО-2
15. (¬C → ¬A) → ((¬C → ¬B) → (¬C → ¬ ((A → B) → B))) TH1 * 13,14
16. (A → C) → (¬C → ¬A) ФРГ-1
17. (A → C) → ((→ C → ¬B) → (¬C → ¬ ((A → B) → B))) TH1 * 16,15
18. (¬C → ¬ ((A → B) → B)) → (((A → B) → B) → C) TH16
19. (A → C) → ((¬C → ¬B) → (((A → B) → B) → C)) TH14 * 17,18
20. (B → C) → (¬C → ¬B) ФРГ-1
21. ((B → C) → (¬C → ¬B)) →

(((¬C → ¬B) → (((A → B) → B) → C)) → ((B → C) → (((A → B) → B) → C)))

TH1
22. ((¬C → ¬B) → (((A → B) → B) → C)) → ((B → C) → (((A → B) → B) → C)) MP 20,21
23. (A → C) → ((B → C) → (((A → B) → B) → C)) TH1 * 19,22.

Примечание: 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 )  -  (А → ¬A) → ¬A

# wff причина
1. (A → A) → ((A → ¬A) → ¬A) TH11
2. А → А TH7
3. (А → ¬A) → ¬A МП 2,1.

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

Теорема   ( TH21 )  -  А → (¬A → В)

# wff причина
1. А → (¬A → ¬¬B) TH2, где B: = ~ B
2. ¬¬B → B ФРГ-2
3. А → (¬A → В) TH14 * 1,2.

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

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

Правило   ( 1 доллар )  -  2 доллара

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 стандартного ПК, эти аксиомы остаются верными. Эти аксиомы предоставляют полные синтаксические определения операторов конъюнкции и дизъюнкции .

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

Теорема   ( ST1 )  -  А → А

# wff причина
1. (A → ((A → A) → A)) → ((A → (A → A)) → (A → A)) ТО-2
2. А → ((А → А) → А) ТО-1
3. (А → (А → А)) → (А → А) MP 2,1
4. А → (А → А) ТО-1
5. А → А МП 4,3.

Теорема   ( ST2 )  -  А → ¬¬A

# wff причина
1. А гипотеза
2. А → (¬A → А) ТО-1
3. ¬A → А МП 1,2
4. ¬A → ¬A ST1
5. (¬A → A) → ((¬A → ¬A) → ¬¬A) НЕ-1
6. (¬A → ¬A) → ¬¬A MP 3,5
7. ¬¬A MP 4,6
8. А ⊢ ¬¬A резюме 1-7
9. А → ¬¬A ДТ 8.

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

Теорема   ( ST3 )  -  B∨C → (¬C → B)

# wff причина
1. С → (¬C → В) НЕ-2
2. B → (¬C → B) ТО-1
3. (B → (¬C → B)) → ((C → (¬C → B)) → ((B ∨ C) → (¬C → B))) ИЛИ-3
4. (C → (¬C → B)) → ((B ∨ C) → (¬C → B)) MP 2,3
5. B∨C → (¬C → B) МП 1,4.

Теорема   ( ST4 )  -  ¬¬A → А

# wff причина
1. A∨¬A НЕ-3
2. (A∨¬A) → (¬¬A → A) ST3
3. ¬¬A → А МП 1,2.

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

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

# wff причина
1. А → (В → С) гипотеза
2. B гипотеза
3. А гипотеза
4. B → C MP 3,1
5. C МП 2,4
6. А → (В → С), В, А ⊢ С резюме 1-5
7. А → (В → С), В ⊢ А → С DT 6
8. A → (B → C) ⊢ B → (A → C) DT 7
9. (A → (B → C)) → (B → (A → C)) ДТ 8.

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

Теорема   ( ST6 )  -  (A → B) → (¬B → ¬A)

# wff причина
1. А → Б гипотеза
2. ¬B гипотеза
3. ¬B → (A → ¬B) ТО-1
4. А → ¬B MP 2,3
5. (A → B) → ((A → ¬B) → ¬A) НЕ-1
6. (А → ¬B) → ¬A MP 1,5
7. ¬A MP 4,6
8. А → В, ¬B ⊢ ¬A резюме 1-7
9. А → В ⊢ ¬B → ¬A DT 8
10. (A → B) → (¬B → ¬A) DT 9.

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

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

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

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

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

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