Лекциите на ФМИ: Математическа Логика

Математическа Логика

ФМИ за начинаещи » Математическа Логика

Съдържание

Нека $Y \vDash A$ и $X$ е множество от съждения. Ако за всяко $B \in Y$ имаме $X \vDash B$ . Тогава $X \vDash A$ - транзитивност

Да изберем произволен модел $v$ на $X$ . Тогава $v(B) = 1 \forall B \in Y$ . От тук получаваме, че $v(Y) = 1$ , т.е $v(A) = 1$ .

Ако $X \vDash A$ то съществува крайно $X_0 \subseteq X : X_0 \vDash A$ . компактност - Ще докажем по-късно!:)

Аксиоматика на съждителното смятане

$A, B, C$ са произволни формули.
Аксиома 1: $A \Rightarrow (B \Rightarrow A)$
Аксиома 2: $(A \Rightarrow (B \Rightarrow C)) \Rightarrow ((A \Rightarrow B) \Rightarrow (A \Rightarrow C))$
Аксиома 3: $A \land B \Rightarrow A$
Аксиома 4: $A \land B \Rightarrow B$
Аксиома 5: $(C \Rightarrow A) \Rightarrow ((C \Rightarrow B) \Rightarrow (C \Rightarrow A \land B))$
Аксиома 6: $A \Rightarrow A \lor B$
Аксиома 7: $B \Rightarrow A \lor B$
Аксиома 8: $(A \Rightarrow C) \Rightarrow ((B \Rightarrow C) \Rightarrow (A \lor B \Rightarrow C))$
Аксиома 9: $(A \Rightarrow B) \Rightarrow ((A \Rightarrow \not B) \Rightarrow \lnot A)$
Аксиома 10: $\lnot\lnot A \Rightarrow A$

Правила за извод
$\frac{A, A \Rightarrow B}{B}$ - MP - модус поненс или правило за отделяне

Дефиниция(Доказателство):
Всяка крайна редица $A_1, A_2, \cdots, A_n$ от формули, такава че всеки нейн член е или аксиома на съждителното смятане, или се получава от 2 члена с по-малки номера по правилото MP.

Дефиниция(Теорема):
Теорема на съждителното смятане е всяка формула, която е последен член на някое доказателство. Самата редица се нарича доказателство на нейния последен член.

Мета теорема: За всяка формула $A$ , формулата $A \Rightarrow A$ е теорема на съждителното смятане (с.с.)

от А2 заместваме със $C = A$ : $\underbrace{(A \Rightarrow (B \Rightarrow A))}_{A1} \Rightarrow ((A \Rightarrow B) \Rightarrow (A \Rightarrow A))$
сега отново заместваме $B = A \Rightarrow B$ : $(A \Rightarrow ((A \Rightarrow B) \Rightarrow A)) \Rightarrow ((A \Rightarrow (A \Rightarrow (B \Rightarrow A))) \Rightarrow (A \Rightarrow A))$

формално:
$(A \Rightarrow ((A \Rightarrow B) \Rightarrow A)) \Rightarrow ((A \Rightarrow (B \Rightarrow A)) \Rightarrow (A \Rightarrow A))$ — Аксиома 2
$A \Rightarrow ((A \Rightarrow B) \Rightarrow A)$ — Аксиома 1
$A \Rightarrow (A \Rightarrow B)$ — А1
$(A \Rightarrow (A \Rightarrow B)) \Rightarrow (A \Rightarrow A)$ — MP 1,2
$A \Rightarrow A$ — MP 3, 4

Метатеорема за коректност: Всяка теорема на с.с е логически закон.
Лема 1: Всички аксиоми на с.с са закони.
Лема 2: Правилото MP запазва истинността. Т.е ако $A$ и $A \Rightarrow B$ са логически закони, то $B$ е логически закон.
Доказателство на Лема 2: Нека $A, A \Rightarrow B$ са логически закони и нека $v$ е произволна оценка. Ще докажем, че $v(B) = 1$ . $v(A) = 1 \land v(A \Rightarrow B) = 1$ . От семантиката следва, че $v(B) = 1$
Доказателство на Лема 1: Трябва да проверим всички формули със таблицата.
Пример за А5: $(C \Rightarrow A) \Rightarrow ((C \Rightarrow B) \Rightarrow (C \Rightarrow A \land B))$ използваме съкратената проверка.

Доказателство на теоремата (за коректност):
Нека $A$ е теорема на с.с. Тогава съществува доказателство в с.с. : $A_1, A_2, \cdots, A_n = A$ .
Лема 3: За всяко $i = 1..n$ имаме, че $A_i$ е логически закон.
Доказателство (по индукция):
1. за $i = 1$ $A_1$ е аксиома, и от лема 1 получаваме, че $A_1$ е логически закон.
2. Нека за i = 1..k твърдението е вярно
3. Ще докажем за k+1
3.1. $A_{k+1}$ е аксиома. По лема 1 полчаваме, че е логически закон.
3.2. $A_{k+1}$ се получава от някои 2 предходни $A_n, A_m$ по правилото MP. Така получаваме, че $A_n = A_m \Rightarrow A_{k+1}$ . От индукционната стъпка имамме, че $A_n, A_m$ са логически закони. По Лема 2 получаваме, че $A_{k+1}$ е логически закон.

Синтактично следване

Дефиниция(синтактично следване):
$X$ e множество от формули, $A$ е формула $X \vdash A$ : от $X$ синтактично следва $A$ .
$X \vdash A$ ако съществува крайна редица формули $A_1, A_2, \cdots, A_n$ , такава че
1. $A_n = A$
2. Всяко $A$ e или аксиома на с.с. или $\in X$ или се получава от 2 формули с по-малки номера по MP. Редицата $A_1, \cdots, A_n$ се нарича доказателство на $A$

Лема: $\varnothing \vdash A$ тг.с.т. $A$ е теорема на с.с. — доказва се очевидно
Свойства на $\vdash$ :
$A \in X$ , то $X \vdash A$
Док: взимаме редицата от единствен член $A$ . Тя е доказателство на $A$ от $X$ .
$X \vdash A$ и $X \subseteq Y$ , то $Y \vdash A$
Док: Нека $X \vdash A$ и $X \subseteq Y$ , тогава съшествува доказателство $A_1, A_2, \cdots, A_n$ на $A$ от $X$ . Тогава това доказателство е и доказателство на $A$ от $Y$ .
$Y \vdash A$ и за всяко $B \in Y$ имаме $X \vdash B$ . Тогава $X \vdash A$ .
Док: Имаме $Y \vdash A$ , т.е редицата $A_1, \cdots, A_n = A$ е доказателство на $A$ от $Y$ , като $A_{i_1}, A_{i_2}, \cdots, A_{i_k} \in Y$ .
$X \vdash A_{i_1}$ със доказателство $B_1^{i_1}, B_2^{i_1}, \cdots, B_m^{i_1} = A_{i_1}$
…
$X \vdash A_{i_k}$ със доказателство $B_1^{i_k}, B_2^{i_k}, \cdots, B_m^{i_k} = A_{i_k}$

на местата на $A_{i_1}, \cdots A_{i_k}$ вмъкваме техните доказателства.

$A_1, \cdots, B_1^{i_1}, B_2^{i_1}, \cdots, B_m^{i_1} = A_{i_1}, \cdots$ — получената редица е доказателство на $A$ от $X$ .

$X \vdash A$ то съшествува крайно $X_0 \subseteq X$ , такова че $X_0 \vdash A$ .
$X \vdash A$ то съществува $A_1, \cdots, A_{i_1}, \cdots A_{i_k} A_n = A$
$A_{i_1}, \cdots Ð�_{i_k}$ са елементи на $X$ и точно от тях образуваме $X_0$ . Сега очевидно $X_0 \vdash A$ със същото доказателство.

page_revision: 4, last_edited: 1257079261|%e %b %Y, %H:%M %Z (%O ago)

Edit Rate (0)Tags discuss (0) History Files Print Site tools + Options

Лекциите на ФМИ

За да изглеждаме умни пред другите

Начало

За автори

Лекции

Аксиоматика на съждителното смятане

Синтактично следване