Математическая логика

ОСНОВНЫЕ ТАВТОЛОГИИ
1. |=A→(B→A)
2. |=(A→B)→((A→(B→C))→(A→C))
3. |=A→(B→A&B)
4А. |=A&B→A
4Б. |=A&B→B
5А. |=A→A∨B
5Б. |=B→A∨B
6. |=(A→C)→((B→C))→(A∨B→C))
7.|=(A→B)→(A→¬B)→¬A
8. ¬¬А→A

ПРАВИЛО ВЫВОДА (MODUS PONENS):
(MP).
ОПР.
ВЫВОДОМ НАЗЫВАЕТСЯ КОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ФОРМУЛ, КАЖДАЯ ИЗ КОТОРЫХ ЯВЛЯЕТСЯ АКСИОМОЙ ИЛИ ПОЛУЧАЕТСЯ ИЗ НЕКОТОРЫХ ПРЕДЫДУЩИХ ФОРМУЛ ПО ПРАВИЛУ ВЫВОДА.

ОПР.
ФОРМУЛА A НАЗЫВАЕТСЯ ВЫВОДИМОЙ В ИСЧИСЛЕНИИ ВЫСКАЗЫВАНИЙ ИЛИ ТЕОРЕМОЙ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ (ОБОЗНАЧЕНИЕ |=A), ЕСЛИ СУЩЕСТВУЕТ ВЫВОД, В КОТОРОМ ПОСЛЕДНЯЯ ФОРМУЛА ЕСТЬ A.
ПРИМЕР: |= A → A.
ДОКАЗАТЕЛЬСТВО.
1) В АКСИОМЕ 2 ВОЗЬМЁМ B = (A → A) И C = A
2) (A → ((A → A) → A)) → ((A → (A → A)) → (A → A))
3) A → (A → A) (1 АКСИОМА)
4) (A → (A → A)) → (A → A) (2,3 MP)
5)A → (A → A) (1 АКСИОМА)
6) A → A (4,5 MP )

ОПР. ФОРМУЛА A НАЗЫВАЕТСЯ ВЫВОДИМОЙ ИЗ МНОЖЕСТВА ФОРМУЛ Γ (ОБОЗНАЧЕНИЕ Γ |= A), ЕСЛИ СУЩЕСТВУЕТ ВЫВОД ИЗ Γ, В КОТОРОМ ПОСЛЕДНЯЯ ФОРМУЛА ЕСТЬ A.
ВЫВОДИМОСТЬ ИЗ ГИПОТЕЗ
ОПР.
ПУСТЬ Γ — НЕКОТОРОЕ МНОЖЕСТВО ФОРМУЛ, НАЗЫВАЕМЫХ ГИПОТЕЗАМИ. ВЫВОДОМ ИЗ Γ НАЗЫВАЕТСЯ КОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ФОРМУЛ, КАЖДАЯ ИЗ КОТОРЫХ ЛИБО ПРИНАДЛЕЖИТ МНОЖЕСТВУ Γ, ЛИБО ЯВЛЯЕТСЯ АКСИОМОЙ, ЛИБО ПОЛУЧАЕТСЯ ИЗ ПРЕДЫДУЩИХ ФОРМУЛ ПО ПРАВИЛУ ВЫВОДА.

ПРАВИЛА ВВЕДЕНИЯ И УДАЛЕНИЯ

ЕСЛИ Γ ∪ {A} ├ B, ТО Γ ├ (A → B).
ДОКАЗАТЕЛЬСТВО. ИНДУКЦИЯ ПО ДЛИНЕ ВЫВОДА ФОРМУЛЫ B ИЗ МНОЖЕСТВА ГИПОТЕЗ Γ ∪ {A}. ЕСЛИ B ЯВЛЯЕТСЯ АКСИОМОЙ ИЛИ ПРИНАДЛЕЖИТ Γ, ТО: B
B → (A → B) (1) A → B (MP) ЕСЛИ B = A, ТО ИСПОЛЬЗУЕМ ВЫВОД A → A.
ПУСТЬ B ПОЛУЧЕНА ИЗ C И C → B ПО MODUS PONENS. ИМЕЕМ Γ ├ (A → C) И Γ ├ (A → (C → B)) ПО ПРЕДПОЛОЖЕНИЮ ИНДУКЦИИ. СОЕДИНЯЕМ ЭТИ ДВА ВЫВОДА И ДОСТРАИВАЕМ ТАК:
(A → (C → B)) → ((A → C) → (A → B)) (2)
(A → C) → (A → B) (MP)
A → B (MP)
ТЕОРЕМА О ДЕДУКЦИИ ДЛЯ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

9)A→A
10)(А → В) → ((В → С)(А → С))
11)( А → (¬ А → В) А ~ В = (А → В) ∧ (В → А)
12)((А → В) → (¬ А → ¬ В)
13)( А ∧ (В ∧ С) ~ (А ∧ В) ∧ С
14)( А ∨ (В ∨ С) ~ (А ∨ В) ∨ С
15)((А ∧ В) ~ (В ∧ А)
16)((А ∨ В) ~ (В ∨ А)
17)( A ∧ (В ∨ С) ~ (А ∧ В) ∨ (А ∧ С)
18)( A ∨ (В ∧ С) ~ (А ∨ В) ∧ (А ∨ С)
19)( ¬ (А ∨ В) ~ (¬ А ∧ ¬ В)
ИСПОЛЬЗУЯ ПРИВЕДЕННЫЕ ВЫШЕ АКСИОМЫ И ТЕОРЕМЫ ПРИВЕДЕМ ДОКАЗАТЕЛЬСТВА СЛЕДУЮЩИХ ВЫСКАЗЫВАНИЙ:

20) ¬ (А ∧ В) ~ (¬ А ∨ ¬ В)
21) ¬ (А → В) ~ (¬ А ∨ В)
22) ¬ ¬ А ~ А
23) A ∨ ¬ A
24) ¬(A & ¬ A)
25) (А → В) ~ (¬ А ∧ В)
26) (А ∨ В) ~ (¬ (¬ А ∧ ¬В))
27) (А ∧ В) ~ ¬ (¬ А ∨ ¬В)
28) ( A→(B→C) ) ~ ( B→(A→C) )
29) ( A→(B→C) ) ~ ( (A&B)→C )

1. A→(A→A) СХ. 1;
2. (A→(A→A))→((A→((A→ A)→ A))→(A→A), ГДЕ B=A→A, C=A, СХ. АКС. 2;
3. (A→((A→A)→A))→(A→A) ПОЛУЧЕНО ИЗ 1 И 2;
4. A→((A→A)→A)) СХ. АКС. 1;
5. A→A ИЗ 3 И 4 ПОЛУЧИЛИ 5;
ЗАКОН ТОЖДЕСТВА
9)|=А→А

ЕСЛИ ДОКАЖЕМ ЧТО СУЩЕСТВУЮТ :
А → В, В → С, А ├ С
А → В, В → С ├ А → С
А → В ├ (В → С) →(А → С)
ТО ПРИМЕНИВ ИЗ ТАБЛИЦЫ ВВЕДЕНИЕ ИМПЛИКАЦИИ(ВВ. →) 3 РАЗА , (СВЕРХУ ВНИЗ) ПОЛУЧИМ ДОКАЗАТЕЛЬСТВО
1) А – ГИПОТЕЗА
2) А → В – ГИПОТЕЗА
3) ПРИМЕНЯЯ К ПУНКТАМ 1 И 2 ПРАВИЛО ВЫВОДА (1,2 MP) ПОЛУЧИМ В
4) В → С (ГИПОТЕЗА)
5) С (3,4 МР)
10) (А → В) → ((В → С)(А → С))

ТРЕБУЕТСЯ ДОКАЗАТЬ А ├ (¬ А → В)
1) А, ¬ А ├ В (СЛАБОЕ УДАЛЕНИЕ ¬)
2) А ├ (¬ А → В) (ВВ. →)
3) А → (¬ А → В) (ВВ. →)
11) А → (¬ А → В)

├ А & (В & С) ~ (А & В) & С
1) ├ А & (В & С) → (А & В) & С
2) ├ (А & В) & С → А & (В & С)
ДОКАЖЕМ 1-ОЕ УТВЕРЖДЕНИЕ:
ПУСТЬ А & (В & С) ├ (А & В) & С ТОГДА
1) А & (В & С) ├ А (УДАЛЕНИЕ &)
2) А & (В & С) ├ В & С (УДАЛЕНИЕ &)
3) В & С ├ В (УДАЛЕНИЕ &)
4) В & С ├ С (УДАЛЕНИЕ &)
5) А & (В & С) ├ В (СЕЧЕНИЕ 2,3)
6) А & (В & С) ├ А & В (СЕЧЕНИЕ 1,3) А, В ├ А & С
7) А & (В & С) ├ С (СЕЧЕНИЕ 2,4)
8) А & В, С ├ (А & В) & С (ВВ. &)
9) А & (В & С) ├ (А & В) & С (СЕЧЕНИЕ)
ДОКАЗАТЕЛЬСТВО 2-ОГО УТВЕРЖДЕНИЯ ПОЛУЧАЕМ В 8-ОМ ПУНКТЕ
А ~ В: (А → В) & (В → А)

1) А, А → В, ¬ В ├ В (УДАЛЕНИЕ → , МР )
2) А, А → В, ¬ В ├ ¬ В (УДАЛЕНИЕ → , МР )
3) А → В, ¬ В ├ ¬ А
4) А → В ├ (¬ В → ¬ А) (ВВ. →)
5) ├ (А → В) → (¬ В → ¬ А) (ВВ. →)
12) (А → В) → (¬ А → ¬ В)

1 ЧАСТЬ : ┣ A&(B&C) → (A&B)&C
2 ЧАСТЬ : ┣ (A&B)&C → A&(B&C)
ДОКАЗАТЕЛЬСТВО 1 ЧАСТИ:
1.A&(B&C) ┣ A (& УД.)
2.A&(B&C) ┣ B (& УД.)
3.B&C ┣ B (& УД.)
4.B&C ┣ С (& УД.)
5.A&(B&C) ┣ B (2, 3 СЕЧЕНИЕ)
6.A&(B&C) ┣ A&B (1, 5 И A, B ┣ A&B – СЕЧЕНИЕ)
7.A&(B&C) ┣ C (2,4 – СЕЧЕНИЕ)
8.A&(B&C) ┣ (A&B)&C ( 7, 6 – СЕЧЕНИЕ)
9.┣ A&(B&C) → (A&B)&C (ВВ. →)
ДОКАЗАТЕЛЬСТВО 2 ЧАСТИ: АНАЛОГИЧНО ПЕРВОЙ
13) A&(B&C) ~ (A&B)&C

А) ├ А ∨ (В ∨ С) → (А ∨ В) ∨ С
Б) ├ (А ∨ В) ∨ С → А ∨ (В ∨ С)
А ∨ (В ∨ С) ├ (А ∨ В) ∨ С
1) А├ А ∨ В (ВВ. ∨)
2) А ∨ В ├ (А ∨ В) ∨ С (ВВ. ∨)
3) А ├ (А ∨ В) ∨ С (СЕЧЕНИЕ 1,2)
4) В ├ А ∨ В (ВВ. ∨)
5) В ├ (А ∨ В) ∨ С (2,4 СЕЧЕНИЕ)
6) С├ (А ∨ В) ∨ С (ВВ. ∨)
7) В ∨ С ├ (А ∨ В) ∨ С (УДАЛЕНИЕ ∨)
8) А ∨ (В ∨ С) ├ (А ∨ В) ∨ С (УДАЛЕНИЕ ∨)
9) ВВЕДЕНИЕ →
10) А ∨ (В ∨ С) ├ (А ∨ В) ∨ С (СЕЧЕНИЕ)
14)А ∨ (В ∨ С) ~ (А ∨ В) ∨ С

├ ((А & В) → (В & А) & ├ (В & А) → (А & В))
А) ├ (А & В) → (В & А)
Б) ├ (В & А) → (А & В)
(А & В) ├ (В & А)
А & В ├ А (УД. &)
2) А & В ├ В (УД. &)
3) В,А ├ В &А (ВВ. &)
4) А & В ├ В &А (1, 2, 3 – Т.7 )
15)(А & В) ~ (В & А)

├ (А ∨ В → В ∨ А) & (В ∨ А → А ∨ В)
А) ├ А ∨ В → В ∨ А
Б) ├ В ∨ А → А ∨ В
А ∨ В ├ В ∨ А
1) А ├ В ∨ А (ВВ. ∨)
2) В ├ В ∨ А (ВВ. ∨)
3) А ∨ В ├ В ∨ А (1 & 2, УД. ∨)
16)(А ∨ В) ~ (В ∨ А)

A) A & (В ∨ С) ├ (А & В) ∨ (А & С)
Б) (А & В) ∨ (А & С) ├ A & (В ∨ С)
ДОКАЖЕМ ЧАСТЬ А:
1) А, В├ А & В
2) А & В├ (А & В) ∨ (А & С)
3) А, В├ (А & В) ∨ (А & С)
4) А, С├ А & С
5) А & С├ (А & В) ∨ (А & С)
6) А, С├ (А & В) ∨ (А & С)
7) А, В ∨ С├ (А & В) ∨ (А & С)
8) A & (В ∨ С) ├ А
9) A & (В ∨ С) ├ (В ∨ С)
10) A & (В ∨ С) ├ (А & В) ∨ (А & С)
17) A & (В ∨ С) ~ (А & В) ∨ (А & С)

ДОКАЖЕМ ЧАСТЬ Б ПО СЛЕДУЮЩЕЙ СХЕМЕ:
(А & В) ∨ (А & С) ├ A (*)
(А & В) ∨ (А & С) ├ В ∨ С (**)
А, В ∨ С├ A & (В ∨ С) (ВВ.&) ДАЛЕЕ ПРИМЕНЯЕМ Т.7.
ДОКАЖЕМ(*):
1) А & В ├ A
2) А & С├ A
3) (А & В) ∨ (А & С) ├ A
(**):
4) А & В ├ В
5) В ├ В ∨ С
6) А & В ├ В∨ С
7) А & В ├ С
8) С ├ В ∨ С
9) А & С ├ В∨ С
10) (А & В) ∨ (А & С) ├ В ∨ С
11) А, В ∨ С├ A & (В ∨ С)
12) (А & В) ∨ (А & С) ├ A & (В ∨ С)

А) ├ A ∨ (В & С) → (А ∨ В) & (А ∨ С)
Б) ├ (А ∨ В) & (А ∨ С) → A ∨ (В & С)
ДОКАЖЕМ ПО СХЕМЕ, КАК В ПРЕДЫДУЩЕМ СЛУЧАЕ:
A ∨ (В & С) ├ А ∨ В (*)
A ∨ (В & С) ├ А ∨ С (**)
А ∨ В, А ∨ С ├ (А ∨ В) & (А ∨ С) (***) (ВВ. &)
ДОКАЖЕМ(*):
1) А ├ А ∨ В
2) В & С ├ В
3) В ├ А ∨ В
4) В & С ├ А ∨ В
5) A ∨ (В & С) ├ А ∨ В
(**):
6) А ├ А ∨ С
7) В & С ├ С
8) С ├ А ∨ С
9) В & С ├ А ∨ С
10) A ∨ (В & С) ├ А ∨ С
11) А ∨ В, А ∨ С ├ (А ∨ В) & (А ∨ С)
12) A ∨ (В & С) ├ (А ∨ В) & (А ∨ С)
18) A ∨ (В & С) ~ (А ∨ В) & (А ∨ С)

ДОКАЖЕМ ЧАСТЬ Б: ├ (А ∨ В) & (А ∨ С) → A ∨ (В & С)
1) A ├ A ∨ (В & С)
2) В, С ├ В & С
3) В & С ├ A ∨ (В & С)
4) В, С ├ A ∨ (В & С)
5) А ∨ В , С ├ A ∨ (В & С)
6) А ∨ В , А ∨ С ├ A ∨ (В & С)
7) (А ∨ В) & (А ∨ С) ├ А ∨ С
8) (А ∨ В) & (А ∨ С) ├ А ∨ В
9) (А ∨ В) & (А ∨ С) ├ A ∨ (В & С)

А) ├ ¬ (А ∨ В) → (¬ А & ¬ В) Б) ├ (¬ А & ¬ В) → ¬ (А ∨ В)
ДОКАЖЕМ ЧАСТЬ А: ЧАСТЬ Б:
1) ¬ (А ∨ В) , А ├ А ∨ В 1) ¬ А & ¬ В, А ├ А
2) ¬ (А ∨ В) , А ├ ¬ (А ∨ В) 2) ¬ А & ¬ В, А ├ ¬ А
3) ¬ (А ∨ В) ├ ¬ А 2.1) А, ¬ А ├ ¬ (А ∨ В)
4) ¬ (А ∨ В) , В ├ А ∨ В 3) ¬ А & ¬ В, А ├ ¬ (А ∨ В)
5) ¬ (А ∨ В) , В ├ ¬ (А ∨ В) 4) ¬ А & ¬ В, В ├ В
6) ¬ (А ∨ В) ├ ¬ В 5) ¬ А & ¬ В, В ├ ¬ В
7) ¬ А ,¬ В ├ ¬ А & ¬ В 6) ¬ А & ¬ В, В ├ ¬ (А ∨ В)
8) 3,6,7 Т.7 → 9 7) ¬ А & ¬ В, (А ∨ В) ├ ¬ (А ∨ В)
9) ¬ (А ∨ В) ├ ¬ А & ¬ В 8) ¬ А & ¬ В, (А ∨ В) ├ А ∨ В 9) ¬ А & ¬ В ├ ¬ (А ∨ В)
19) ¬ (А ∨ В) ~ (¬ А & ¬ В)

А) ├ ¬ (А & В) → (¬ А ∨ ¬ В)
Б) ├ (¬ А ∨ ¬ В)→ ¬ (А & В)
ДОКАЖЕМ ЧАСТЬ А: ЧАСТЬ Б:
1) ¬ (А & В), А, В ├ ¬ (А & В) 1) ¬ А ├ А & В
2) ¬ (А & В), А, В ├ А & В 2) ¬ А , А & В ├ А
3) ¬ (А & В), В ├ ¬ А 3) ¬ А ├ ¬ (А & В)
4) ¬ А ├ ¬ А ∨ ¬ В 4) ¬ В, (А & В) ├ В
5) ¬ (А & В), В ├ ¬ А ∨ ¬ В 5) ¬ В, (А & В) ├ ¬ В
6) ¬ (А & В), ¬ В ├ ¬ А ∨ ¬ В 6) ¬ В ├ ¬ (А & В
7) ¬ (А & В), В∨ ¬ В ├ ¬ А ∨ ¬ В 7) (¬ А ∨ ¬ В) ├ ¬ (А & В)
8) В├ ¬ В
9) ¬ (А & В) ├ ¬ А ∨ ¬ В
20) ¬ (А & В) ~ (¬ А ∨ ¬ В)

I. |=¬¬A ~ A
II. |=A ~ ¬¬ A
ЧАСТЬ I
1. ¬¬A|=A (УДАЛЕНИЕ ¬)
2. |=¬¬A ~ A (ВВЕДЕНИЕ ¬)
ЧАСТЬ II
1. A, ¬A |=A (СВОЙСТВО ВЫВОДИМОСТИ )
2. A, ¬A |=¬A (ВВЕДЕНИЕ ¬ , ПРИВЕДЕНИЕ К НЕЛЕПОСТИ )
3. A|=¬¬A (ВВЕДЕНИЕ ¬)
4. |=A ~ ¬¬A (ВВЕДЕНИЕ ¬)
22) |= ¬¬A~ A

1. ¬A, ¬ (A∨¬A) |=¬A∨A (ВВЕДЕНИЕ ∨)
2. ¬A, ¬ (A∨¬A) |=¬(A∨¬A) (СВОЙСТВО ВЫВОДИМОСТИ )
3. ¬ (A∨¬A) |=¬¬A (ВВЕДЕНИЕ ¬)
4. ¬¬A|=A (АКСИОМА №8)
5. ¬(A∨¬A)|=A (СЕЧЕНИЕ (3,4))
5.1 A ~ A∨¬A
6. ¬(A∨¬A)|= A∨¬A
7. ¬ (A∨¬A)|= ¬ (A∨¬A)
8. |=¬¬ (A∨¬A) (ВВЕДЕНИЕ ¬)
? АКСИОМА
9.|=A∨¬A
23) A∨¬A

1.|= ¬ (A&¬A)~ ¬A∨¬A
2. |= A∨¬A (ПО ФОРМУЛЕ №23)
3. |=¬ (A&¬A)
24) |= ¬ (A&¬A)