Лемма о дедукции, полнота исчисления высказываний — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: « << На главную >>»)
 
Строка 1: Строка 1:
 
[[Лекция 2 | <<]][[Матлогика | На главную]][[Лекция 4 | >>]]
 
[[Лекция 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, \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>.
 +
}}

Версия 21:32, 12 января 2012

<< На главную >>

Теорема о дедукции

Будем обозначать буквами [math]\Gamma, \Delta, \Sigma[/math] списки формул (возможно, пустые).


Определение:
Пусть [math]\Gamma[/math] - некоторые список высказываний, [math]\alpha[/math] - некоторое высказывание в исчислении [math]\langle L, A, R \rangle[/math]. Тогда будем говорить, что [math]\alpha[/math] выводится из [math]\Gamma[/math] (запись: [math]\Gamma \vdash \alpha[/math]), если существует доказательство [math]\alpha[/math] в исчислении [math]\langle L, A_1, R \rangle[/math], где [math]A_1[/math] - это [math]A[/math] с добавленными формулами из [math]\Gamma[/math]. Элементы [math]\Gamma[/math] называются допущениями, предположениями, или гипотезами.


Замечание: в этом определении появляются дополнительные предположения, поэтому речь идет именно о выводе, а не о доказательстве. Очевидно, что, если [math]\Gamma = \varnothing[/math], то [math]\Gamma \vdash \alpha[/math] соответствует [math]\vdash \alpha[/math].

Теорема:
Пусть справедливо [math]\Gamma \vdash \alpha \rightarrow \beta[/math]. Тогда справедливо [math]\Gamma, \alpha \vdash \beta[/math]
Доказательство:
[math]\triangleright[/math]
Возьмем [math]\delta_1, ..., \delta_m[/math] --- вывод формулы [math]\alpha \rightarrow \beta[/math]. В ней [math]\delta_m = \alpha \rightarrow \beta[/math]. Добавим [math]\delta_{m+1} = \alpha[/math] --- это добавленная аксиома, и [math]\delta_{m+2} = \beta[/math], получим вывод [math]\beta[/math].
[math]\triangleleft[/math]