Sebuah inferensi logika: $\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $ tanpa menggunakan tabel kebenaran

Aug 18 2020

Buktikan validitas dari inferensi berikut (JANGAN gunakan tabel kebenaran):

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $$ Saya telah menggambar tabel kebenaran yang menunjukkan bahwa proposisi: $((p\implies q) \land (q\implies r)) \implies (p\implies r)$adalah tautologi, tetapi tidak berhasil memanipulasi tempat menggunakan aturan inferensi logika untuk menampilkan hasilnya.
Tolong beri beberapa saran.

Jawaban

7 GrahamKemp Aug 19 2020 at 01:51

Dengan menggunakan notasi yang sedikit berbeda — Kalkulus Berurutan — kita dapat menyusun pohon bukti deduksi alami berikut:

$$\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}$$

Dengan demikian kami menyimpulkan bahwa inferensi itu valid: $$\left\lvert\!\begin{split} &p\to q\\&q\to r\\\hline &p\to r\end{split}\right.$$

Aturan yang digunakan — di mana $\Gamma, \Delta$adalah daftar pernyataan, dan$\varphi, \psi$ adalah pernyataan tunggal — adalah:

$\textsf{ID}$: Identitas (atau asumsi) $\qquad\begin{split}~\\\hline\Gamma,\varphi&\vdash\varphi\end{split}$

Sepele: Anda dapat memperoleh pernyataan jika diasumsikan bersama dengan daftar asumsi tambahan (mungkin kosong).
${\to}\mathsf E$: Eliminasi Bersyarat: $\qquad\begin{split}\Gamma&\vdash\varphi\\\Delta&\vdash \varphi\to \psi\\\hline\Gamma\cup\Delta&\vdash \psi\end{split}$

Jika kondisional dapat diturunkan dari satu daftar pernyataan, dan antesedennya dapat diturunkan dari daftar lain, maka kita dapat menyimpulkan bahwa akibatnya dapat diturunkan dari gabungan daftar.
${\to}\mathsf I$: Pengantar Bersyarat: $\qquad\begin{split}\Gamma,\varphi&\vdash \psi\\\hline\Gamma&\vdash\varphi\to\psi\end{split}$

Jika konsekuensi dapat diturunkan dari daftar pernyataan termasuk antesedan, maka kita dapat menyimpulkan bahwa kondisi masing-masing dapat diturunkan dari daftar.

Inferensi ini adalah contoh penerapan asumsi. Di akhir pembuktian, semua asumsi, kecuali tempat, harus digunakan dengan benar.

Di sini kita telah mengasumsikan tiga pernyataan, dua premis dengan tambahan anteseden dari kesimpulan kita. Kami melepaskan asumsi ketiga itu setelah berhasil menurunkan konsekuensinya.

6 rain1 Aug 18 2020 at 20:11

Kami ingin membuktikan

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

Perkenalkan p ke dalam konteks:

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

Mengumpulkan $p\implies q$ dan $p$ untuk menyimpulkan $q$:

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

Mengumpulkan $q\implies r$ dan $q$ untuk menyimpulkan $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

Gunakan tautologi $$(p\implies q)\implies((q\implies r)\implies(p\implies r))$$sebagai gantinya dan terapkan Modus Ponens dua kali dengan tempat yang diberikan. Cara lainnya, gunakan tautologi$$\varphi\implies(\psi\implies (\varphi\land\psi))$$ untuk menyimpulkan $$\frac{\begin{matrix} \varphi \\ \psi\end{matrix}}{(\varphi\land\psi)} $$ dan kemudian gunakan tautologi yang Anda berikan untuk membuktikan $$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{ p\implies r} $$

Demi kelengkapan: mengingat premis tambahkan kesimpulan tautologi di atas

$$\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)}$$

lalu

$$\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}$$

yang melengkapi buktinya. Untuk alternatif pertama gunakan aturan yang diberikan untuk mendapatkan

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

dan kemudian dengan menggunakan tautologi lain yang kami miliki

$$\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

Gunakan modus ponens dua kali dan pengenalan kondisi:

$p\implies q$ dan $p$ cara $q$ benar. (penggunaan pertama). $q\implies r$ dan $q$ adalah cara yang benar $r$adalah benar. (penggunaan kedua). Jadi diberikan$p \implies q$ dan $q\implies r$ kemudian dengan pengantar bersyarat $p$ menjadi benar berarti $r$adalah benar. Begitu$p\implies r$.

Oke saya pikir saya mengerti:

Jika kita mengambil notasi $\phi\vdash \psi$ yang berarti "apakah kita akan berasumsi $\phi$ kita bisa mendapatkan $\psi$ kemudian:

$p\implies q$ (diberikan)

$p \implies r$ (qiven)

$p\vdash p$ (mengasumsikan sesuatu adalah mengasumsikan sesuatu. $\mu\vdash \mu$ selalu benar karena jika kita berasumsi $\mu$ kita bisa mendapatkan $\mu$... karena kami menganggap itu benar. Ini bukan untuk mengatakan kita mengklaim itu adalah benar (seperti klaim Anda dalam komentar tentang "tinggal di tempat awal" berarti Anda percaya); ini untuk mengatakan di bawah hipotesis jika itu benar kita bisa menurunkannya. Tentu saja jika tidak benar apa yang kita peroleh tidak akan relevan.)

$p\vdash p\implies q$ ($p\implies q$ adalah kebenaran yang diberikan apakah kita berasumsi $p$atau tidak. Untuk setiap pernyataan yang benar$T$ kemudian $\mu\vdash T$akan selalu benar. Dan saya rasa$\mu\vdash F$ akan selalu salah.)