Изменения
→Теорема о дедукции
[[Категория: Математическая логика]] [[Лекция 2 | <<]][[Матлогика Лекция 4 | На главную>>]][[Лекция ==Теорема о дедукции== Будем обозначать буквами <tex>\Gamma, \Delta, \Sigma</tex> списки формул (возможно, пустые). {{Определение |definition=Пусть <tex>\Gamma</tex> - некоторый список высказываний, <tex>\alpha</tex> - некоторое высказывание в исчислении <tex>\langle L, A, R \rangle</tex>. Тогда будем говорить, что <tex>\alpha</tex> '''выводится''' из <tex>\Gamma</tex> (запись: <tex>\Gamma \vdash \alpha</tex>), если существует доказательство <tex>\alpha</tex> в исчислении <tex>\langle L, A_1, R \rangle</tex>, где <tex>A_1</tex> - это <tex>A</tex> с добавленными формулами из <tex>\Gamma</tex>. Элементы <tex>\Gamma</tex> называются допущениями, предположениями, или гипотезами.}} Замечание: в этом определении появляются дополнительные предположения, поэтому речь идет именно о ''выводе'', а не о ''доказательстве''. Очевидно, что, если <tex>\Gamma = \varnothing</tex>, то <tex>\Gamma \vdash \alpha</tex> соответствует <tex>\vdash \alpha</tex>. {{Теорема|statement=Пусть справедливо <tex>\Gamma \vdash \alpha \rightarrow \beta</tex>. Тогда справедливо <tex>\Gamma \cup \{\alpha\} \vdash \beta</tex>|proof=Возьмем <tex>\delta_1, ..., \delta_m</tex> --- вывод формулы <tex>\alpha \rightarrow \beta</tex>. В ней <tex>\delta_m = \alpha \rightarrow \beta</tex>. Добавим <tex>\delta_{m+1} = \alpha</tex> --- это добавленная аксиома, и <tex>\delta_{m+2} = \beta</tex>, получим вывод <tex>\beta</tex> как М.Р. <tex>\delta_m</tex> и <tex>\delta_{m+1}</tex>. }} {{Лемма|statement=<tex>\vdash \alpha \rightarrow \alpha</tex>|proof=#<tex>\alpha \rightarrow (\alpha \rightarrow \alpha)</tex> (Сх. акс. 1)#<tex>(\alpha \rightarrow (\alpha \rightarrow \alpha)) \rightarrow (\alpha \rightarrow ((\alpha \rightarrow \alpha) \rightarrow \alpha)) \rightarrow (\alpha \rightarrow \alpha)</tex> (Сх. акс. 2)#<tex>(\alpha \rightarrow ((\alpha \rightarrow \alpha) \rightarrow \alpha)) \rightarrow (\alpha \rightarrow \alpha)</tex> (М.Р. 1, 2)#<tex>(\alpha \rightarrow ((\alpha \rightarrow \alpha) \rightarrow \alpha))</tex> (Сх. акс. 1)#<tex>\alpha \rightarrow \alpha</tex> (М.Р. 4 , 3)}} {{Теорема|about= о дедукции|statement=Пусть справедливо <tex>\Gamma \cup \{\alpha\} \vdash \beta</tex>. Тогда справедливо <tex>\Gamma \vdash \alpha \rightarrow \beta</tex>.| proof=Имеется вывод <tex>\delta_1, ..., \delta_{m-1}, \beta</tex>. Набросаем план вывода, формулы в нем занумеруем через 10 ('''<s>Ну да, логика же</s>'''): <tex>(10)</tex> <tex>\Gamma \vdash \alpha \rightarrow \delta_1</tex> ... <tex>(10m - 10)</tex> <tex>\Gamma \vdash \alpha \rightarrow \delta_{m-1}</tex> <tex>(10m)</tex> <tex>\Gamma \vdash \alpha \rightarrow \beta</tex> Дополним план до полноценного вывода. Рассмотрим формулу номер <tex>i</tex>. Возможны следующие варианты:# <tex>\delta_i</tex> --- аксиома или предположение, входящее в <tex>\Gamma</tex>. Тогда вставим перед этой формулой <tex>\delta_i</tex> и <tex>\delta_i \rightarrow (\alpha \rightarrow \delta_i)</tex>, формула верна по M.P.# <tex>]]\delta_i = \alpha</tex>. Тогда вставляем перед формулой 4 формулы из леммы.# <tex>\delta_i</tex> выводится по M.P. из <tex>\delta_j</tex> и <tex>\delta_k</tex>, где <tex>j, k < i</tex>. Выведем <tex>\alpha \rightarrow \delta_i</tex>, добавив <tex>(\alpha \rightarrow \delta_j) \rightarrow ((\alpha \rightarrow (\delta_j \rightarrow \delta_i)) \rightarrow (\alpha \rightarrow \delta_i))</tex> (сх. акс. 2) и <tex>(\alpha \rightarrow (\delta_j \rightarrow \delta_i)) \rightarrow (\alpha \rightarrow \delta_i)</tex> (M.P. из <tex>j</tex> и предыдущей)}} {{Определение|definition=Высказывание <tex>\alpha</tex> следует из высказываний <tex>\Gamma</tex>, если при любой оценке пропозициональных переменных, входящих в высказывания, на которых все высказывания из <tex>\Gamma</tex> истинны, <tex>\alpha</tex> также истинно. Запись: <tex>\Gamma \models \alpha</tex>.}} ==Теорема о полноте исчисления высказываний== {{Лемма|statement= Если <tex>\Gamma \vdash \alpha</tex>, то <tex>\Gamma, \gamma \vdash \alpha</tex>. Если <tex>\Gamma_1, \Gamma_2 \vdash \alpha</tex>, то <tex>\Gamma_2, \Gamma_1 \vdash \alpha</tex>. Аналогично для следствия.|proof= '''КТО МОЖЕТ НАПИСАТЬ ЭТО ФОРМАЛЬНО?'''}}
