논리 추론 : $\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $ 진리표를 사용하지 않고

Aug 18 2020

다음 추론의 타당성을 입증하십시오 (진리표를 사용하지 마십시오).

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $$ 나는 명제를 보여주는 진리표를 그렸습니다. $((p\implies q) \land (q\implies r)) \implies (p\implies r)$타우 톨 로지이지만 논리 추론 규칙을 사용하여 결과를 표시하는 전제를 조작하는 데 성공하지 못했습니다.
몇 가지 조언을 해주세요.

답변

7 GrahamKemp Aug 19 2020 at 01:51

교묘 한 다른 표기법 (순차 미적분)을 사용하여 다음과 같은 자연 추론 증명 트리를 구성 할 수 있습니다.

$$\dfrac{\dfrac{\dfrac{\dfrac{}{p\vdash p}{\tiny\textsf{ID}}~\dfrac{}{p\to q\vdash p\to q}{\tiny\textsf{ID}}}{p,p\to q\vdash q}{\tiny{\to}\mathsf E}~\dfrac{}{q\to r\vdash q\to r}{\tiny\textsf{ID}}}{p,p\to q,q\to r\vdash r}{\tiny{\to}\mathsf E}}{p\to q,q\to r\vdash p\to r}{\tiny{\to}\mathsf I}$$

따라서 우리는 추론이 유효하다는 결론을 내립니다. $$\left\lvert\!\begin{split} &p\to q\\&q\to r\\\hline &p\to r\end{split}\right.$$

사용 된 규칙-장소 $\Gamma, \Delta$있는 목록 문, 그리고$\varphi, \psi$ 단일 문입니다.

$\textsf{ID}$: 정체성 (또는 가정) $\qquad\begin{split}~\\\hline\Gamma,\varphi&\vdash\varphi\end{split}$

간단하게 : 가정의 추가 (비어있을 수 있음) 목록과 함께 가정되는 경우 명령문을 유도 할 수 있습니다.
${\to}\mathsf E$: 조건부 제거 : $\qquad\begin{split}\Gamma&\vdash\varphi\\\Delta&\vdash \varphi\to \psi\\\hline\Gamma\cup\Delta&\vdash \psi\end{split}$

조건문이 하나의 명령문 목록에서 파생 될 수 있고 그 선행 항목이 다른 목록에서 파생 될 수 있다면 결과는 목록의 결합에서 파생 될 수 있다고 추론 할 수 있습니다.
${\to}\mathsf I$: 조건부 소개 : $\qquad\begin{split}\Gamma,\varphi&\vdash \psi\\\hline\Gamma&\vdash\varphi\to\psi\end{split}$

결과가 선행을 포함하는 진술 목록에서 파생 될 수있는 경우 해당 조건이 목록에서 파생 될 수 있다고 추론 할 수 있습니다.

이 추론의 예입니다 방전 가정을. 증명이 끝나면 전제를 제외하고는 모든 가정이 적절하게 해제되어야합니다.

여기서 우리는 결론의 선행을 추가 한 두 가지 전제 인 세 가지 진술 을 가정했습니다 . 우리는 결과를 성공적으로 도출 한 후 세 번째 가정을 해제합니다.

6 rain1 Aug 18 2020 at 20:11

우리는 증명하고 싶다

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{p\implies r}$$

컨텍스트에 p를 소개합니다.

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \end{matrix}}{r}$$

합치다 $p\implies q$ 과 $p$ 추론하다 $q$:

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \\ q \end{matrix}}{r}$$

합치다 $q\implies r$ 과 $q$ 추론하다 $r$:

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \\ q \\ r \end{matrix}}{r}$$

QED

4 mrtaurho Aug 18 2020 at 20:16

tautology 사용 $$(p\implies q)\implies((q\implies r)\implies(p\implies r))$$대신 주어진 건물에 Modus Ponens를 두 번 적용하십시오. 또는 tautology를 사용하십시오.$$\varphi\implies(\psi\implies (\varphi\land\psi))$$ 결론적으로 $$\frac{\begin{matrix} \varphi \\ \psi\end{matrix}}{(\varphi\land\psi)} $$ 그리고 증명하기 위해 당신이 준 팽팽하게 $$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{ p\implies r} $$

완전성을 위해 : 전제에 위의 팽팽한 결론을 추가하십시오.

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ (p\implies q)\implies((q\implies r)\implies(p\implies r)) \end{matrix}}{(q\implies r)\implies(p\implies r)}$$

그리고

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ (p\implies q)\implies((q\implies r)\implies(p\implies r))\\ (q\implies r)\implies(p\implies r) \end{matrix}}{p\implies r}$$

증거를 완성합니다. 대안을 위해 먼저 주어진 규칙을 사용하여

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{( p\implies q)\land(q\implies r)}$$

다른 팽팽함을 사용하여

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\( p\implies q)\land(q\implies r)\\ (( p\implies q)\land(q\implies r))\implies (p\implies r) \end{matrix}}{p\implies r}$$

2 fleablood Aug 18 2020 at 20:40

modus ponens를 두 번 사용하고 조건 소개 :

$p\implies q$ 과 $p$ 방법 $q$ 사실입니다 (처음 사용). $q\implies r$ 과 $q$ 진정한 의미이다 $r$사실이다. (두 번째 사용). 그래서 주어진$p \implies q$ 과 $q\implies r$ 그런 다음 조건부 소개로 $p$ 진정한 의미 $r$사실이다. 그래서$p\implies r$.

좋아, 내가 얻은 것 같아.

표기법을 취하면 $\phi\vdash \psi$ "우리가 $\phi$ 우리는 파생 할 수 있습니다 $\psi$ 그때:

$p\implies q$ (주어진)

$p \implies r$ (키벤)

$p\vdash p$ (무언가는 무언가를 가정하는 것이라고 가정합니다. $\mu\vdash \mu$ 왜냐하면 우리가 가정한다면 $\mu$ 우리는 파생 할 수 있습니다 $\mu$... 우리는 그것이 사실이라고 가정하기 때문입니다. 이것은 우리가 주장하고 말할 수 없습니다 입니다 ( "초기 건물에 머물고"에 대한 코멘트에있는 당신의 요구로 당신이 믿는 것을 의미)가 true; 이것은 가설 아래서 그것이 사실이라면 우리가 도출 할 수 있다고 말하는 것입니다. 물론 그것이 사실 이 아니라면 우리가 도출 한 것은 관련이 없을 것입니다.)

$p\vdash p\implies q$ ($p\implies q$ 우리가 가정하는지 여부는 주어진 진실입니다 $p$또는 아닙니다. 모든 진실한 진술에 대해$T$ 그때 $\mu\vdash T$항상 사실입니다. 그리고 나는 추측한다$\mu\vdash F$ 항상 거짓입니다.)

$p\vdash q$ (modus ponens)

$p\vdash q\to r$ ($q\implies r$ 우리가 가정하는지 여부는 주어진 진실입니다 $p$ 여부)

$p\vdash r$ (modus ponens)

$p\implies r$ (조건부 소개;)

(이것은 기본 규칙입니다. 영어로 가정하면 $\mu$ 우리는 파생 할 수 있습니다 $\psi$ 그때 $\mu \implies \psi$ 사실이어야합니다.)