論理的推論： $\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}$

条件文をステートメントの1つのリストから導出でき、その先行詞を別のリストから導出できる場合、後件部はリストの結合から導出できると推測できます。
${\to}\mathsf I$：条件付き紹介： $\qquad\begin{split}\Gamma,\varphi&\vdash \psi\\\hline\Gamma&\vdash\varphi\to\psi\end{split}$

先行詞を含むステートメントのリストから後件を導出できる場合は、それぞれの条件文をリストから導出できると推測できます。

この推論は、一例である放電仮定します。証明の終わりに、前提を除いて、すべての仮定は適切に実行されている必要があります。

ここでは、3つのステートメントを想定しています。2つの前提には、結論の先行詞が追加されています。後件の導出に成功した後、その3番目の仮定を解除します。

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

トートロジーを使用する $$(p\implies q)\implies((q\implies r)\implies(p\implies r))$$代わりに、指定された前提でModusPonensを2回適用します。または、トートロジーを使用します$$\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

モーダスポネンスを2回使用し、導入を条件付けます。

$p\implies q$ そして $p$ 手段 $q$ 本当です。（最初の使用）。 $q\implies r$ そして $q$ 本当の意味 $r$本当です。（2回目の使用）。与えられた$p \implies q$ そして $q\implies r$ その後、条件付き導入によって $p$ 真であることは $r$本当です。そう$p\implies r$。

さて、私はそれを手に入れたと思います：

表記を取る場合 $\phi\vdash \psi$ 「私たちが想定したのは $\phi$ 導き出すことができます $\psi$ その後：

$p\implies q$ （与えられた）

$p \implies r$ （qiven）

$p\vdash p$ （何かを仮定することは何かを仮定することです。 $\mu\vdash \mu$ 私たちが仮定すると $\mu$ 導き出すことができます $\mu$...それが真実であると仮定しているからです。これは、私たちがそれが真実であると主張していると言っているのではありません（「最初の敷地にとどまる」についてのコメントでのあなたの主張はあなたが信じていることを意味します）。これは、それが真実である場合、私たちが導き出すことができるという仮説の下で言うことです。もちろん、それが真実でなければ、私たちが導き出したものは関係ありません。）

$p\vdash p\implies q$ （（$p\implies q$ 私たちが仮定するかどうかは与えられた真実です $p$か否か。すべての真のステートメントに対して$T$ その後 $\mu\vdash T$常に真実になります。そして、私は推測します$\mu\vdash F$ 常にfalseになります。）

$p\vdash q$ （モーダスポネンス）

$p\vdash q\to r$ （（$q\implies r$ 私たちが仮定するかどうかは与えられた真実です $p$ か否か）

$p\vdash r$ （モーダスポネンス）

$p\implies r$ （条件付き紹介;）

（これは基本的なルールです。英語では、 $\mu$ 導き出すことができます $\psi$ その後 $\mu \implies \psi$ 真でなければなりません。）