Доказать справедливость выражения

@nas1223 · Регистрация: 08.10.2013

Доказать: A⊃(B⊃C),B⊢A⊃C, где А,В,С-формулы исчисления высказываний.

@Mysterious Light · 25.10.2013, 01:11

Есть теорема:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (A\to (B\to C))\to (B\to (A\to C))$
Она доказывается элементарно при помощи леммы о дедукции.

В принципе, её можно доказать напрямую

Cхемы аксиом
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash \alpha \to \beta \to \gamma \;\; (K)$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha \to \beta \to \gamma) \to (\alpha\to\beta) \to \alpha\to\gamma \;\; (S)$

применим Modus Ponens правил K и K (имеется в виду, здесь и далее, что вместо букв можно подставить что-то такое, чтоб MP можно было применить, в данном случае в первом K нужно сделать $https://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha$ двухаргументной функцией , чтоб она совпала со видом аксиомы K, которая является посылкой)
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash \alpha \to \beta \to \gamma \to \beta \;\; (1)$
Применим (S) к (1), получим
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha \to \beta) \to \alpha \to \beta\to\gamma \;\; (2)$
Применим (2) к (S), получим
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha \to \beta \to \gamma) \to \delta \to (\alpha \to \beta) \to \alpha \to \gamma \;\; (3)$
Применим (K) к (S), получим
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash \alpha \to (\beta \to \gamma \to \delta) \to (\beta\to\gamma) \to \beta \to \delta \;\; (4)$
Применим (S) к (4), получим
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha\to\beta\to\gamma\to\delta) \to \alpha \to (\beta\to\gamma) \to \beta \to \delta \;\; (5)$
Применим (5) к (3), получим
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha\to\beta\to\delta) \to (\gamma\to\alpha\to\beta) \to \gamma\to\alpha\to\delta \;\; (6)$
Применим (S) к (6), получим
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash ((\alpha \to \beta \to \delta) \to \gamma \to \alpha \to \beta) \to (\alpha \to \beta\to\delta) \to \gamma \to \alpha \to \delta \;\; (7)$
Наконец, применим (7) к (1) и получим
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha \to \beta\to\delta) \to \gamma \to \alpha \to \delta$
что и требовалось доказать.

Пояснение. нехватающие скобки расставляются правоассоциативно, то есть выражение $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to B\to C$ следует читать как , аналогично $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to B\to C\to D$ как

Теперь остаётся сказать, что
$https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to (B\to C),\;B\vdash A\to (B\to C)$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to (B\to C),\;B\vdash B$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to (B\to C),\;B\vdash (A\to (B\to C))\to (B\to (A\to C))$
Применяя MP сначала последнего суждения к первому, а потом то, что получится, ко второму, получим
$https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to (B\to C),\;B\vdash A\to C$

Добавлено через 1 час 49 минут
Хотя я так подумал: задание можно сделать без доказательства теоремы.

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{align*} A\to B\to C, \,B &\vdash& (A\to B\to C) \to (A\to B) \to A\to C & (S) \\ A\to B\to C, \,B &\vdash& A\to B\to C &\;\;(\Gamma1)\\ A\to B\to C, \,B &\vdash& (A\to B) \to (A\to C) &\;\; (1) \\ A\to B\to C, \,B &\vdash& B\to A\to B &\;\; (K) \\ A\to B\to C, \,B &\vdash& B &\;\; (\Gamma2) \\ A\to B\to C, \,B &\vdash& A\to B &\;\; (2) \\ A\to B\to C, \,B &\vdash& A\to C &\;\; (3) \end{align*}$
(S) и (K) являются аксиомами, Г1 и Г2 — гипотезами, (1) получается применением Modus Ponens к первым двум, (2) получается MP следующих двух, (3) является результатом MP (1) и (2).

@nas1223 1 / 1 / 0 Регистрация: 08.10.2013 Сообщений: 54
		1
	Доказать справедливость выражения 24.10.2013, 20:48. Показов 967. Ответов 1 Метки нет (Все метки) Доказать: A⊃(B⊃C),B⊢A⊃C, где А,В,С-формулы исчисления высказываний. 0

@Mysterious Light $Эксперт по математике/физике$ 4163 / 2066 / 424 Регистрация: 19.07.2009 Сообщений: 3,125 Записей в блоге: 24
	25.10.2013, 01:11	2
	Есть теорема: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (A\to (B\to C))\to (B\to (A\to C))$ Она доказывается элементарно при помощи леммы о дедукции. В принципе, её можно доказать напрямую Cхемы аксиом $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash \alpha \to \beta \to \gamma \;\; (K)$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha \to \beta \to \gamma) \to (\alpha\to\beta) \to \alpha\to\gamma \;\; (S)$ применим Modus Ponens правил K и K (имеется в виду, здесь и далее, что вместо букв можно подставить что-то такое, чтоб MP можно было применить, в данном случае в первом K нужно сделать $https://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha$ двухаргументной функцией , чтоб она совпала со видом аксиомы K, которая является посылкой) $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash \alpha \to \beta \to \gamma \to \beta \;\; (1)$ Применим (S) к (1), получим $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha \to \beta) \to \alpha \to \beta\to\gamma \;\; (2)$ Применим (2) к (S), получим $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha \to \beta \to \gamma) \to \delta \to (\alpha \to \beta) \to \alpha \to \gamma \;\; (3)$ Применим (K) к (S), получим $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash \alpha \to (\beta \to \gamma \to \delta) \to (\beta\to\gamma) \to \beta \to \delta \;\; (4)$ Применим (S) к (4), получим $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha\to\beta\to\gamma\to\delta) \to \alpha \to (\beta\to\gamma) \to \beta \to \delta \;\; (5)$ Применим (5) к (3), получим $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha\to\beta\to\delta) \to (\gamma\to\alpha\to\beta) \to \gamma\to\alpha\to\delta \;\; (6)$ Применим (S) к (6), получим $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash ((\alpha \to \beta \to \delta) \to \gamma \to \alpha \to \beta) \to (\alpha \to \beta\to\delta) \to \gamma \to \alpha \to \delta \;\; (7)$ Наконец, применим (7) к (1) и получим $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vdash (\alpha \to \beta\to\delta) \to \gamma \to \alpha \to \delta$ что и требовалось доказать. Пояснение. нехватающие скобки расставляются правоассоциативно, то есть выражение $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to B\to C$ следует читать как , аналогично $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to B\to C\to D$ как Теперь остаётся сказать, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to (B\to C),\;B\vdash A\to (B\to C)$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to (B\to C),\;B\vdash B$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to (B\to C),\;B\vdash (A\to (B\to C))\to (B\to (A\to C))$ Применяя MP сначала последнего суждения к первому, а потом то, что получится, ко второму, получим $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\to (B\to C),\;B\vdash A\to C$ Добавлено через 1 час 49 минут Хотя я так подумал: задание можно сделать без доказательства теоремы. $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{align}<br /> A\to B\to C, \,B &\vdash& (A\to B\to C) \to (A\to B) \to A\to C & (S) \\<br /> A\to B\to C, \,B &\vdash& A\to B\to C &\;\;(\Gamma1)\\<br /> A\to B\to C, \,B &\vdash& (A\to B) \to (A\to C) &\;\; (1) \\<br /> A\to B\to C, \,B &\vdash& B\to A\to B &\;\; (K) \\<br /> A\to B\to C, \,B &\vdash& B &\;\; (\Gamma2) \\<br /> A\to B\to C, \,B &\vdash& A\to B &\;\; (2) \\<br /> A\to B\to C, \,B &\vdash& A\to C &\;\; (3)<br /> \end{align}$ (S) и (K) являются аксиомами, Г1 и Г2 — гипотезами, (1) получается применением Modus Ponens к первым двум, (2) получается MP следующих двух, (3) является результатом MP (1) и (2). 0

Опции темы