การอนุมานเชิงตรรกะ: $\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)$เป็น tautology แต่ไม่ประสบความสำเร็จในการจัดการสถานที่โดยใช้กฎการอนุมานเชิงตรรกะเพื่อแสดงผลลัพธ์
ช่วยให้คำแนะนำหน่อย

คำตอบ

7 GrahamKemp Aug 19 2020 at 01:51

การใช้สัญกรณ์ที่แตกต่างกันอย่างไม่ซับซ้อน - Sequent Calculus - เราอาจสร้างโครงสร้างหลักฐานการหักตามธรรมชาติต่อไปนี้:

$$\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)} $$ จากนั้นใช้ tautology ที่คุณให้มาเพื่อพิสูจน์ $$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{ p\implies r} $$


เพื่อความสมบูรณ์: ให้สถานที่เพิ่ม tautology ข้างต้นสรุป

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

แล้วใช้ tautology อื่น ๆ ที่เรามี

$$\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$ (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$ จะเป็นเท็จเสมอ)

$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$ ต้องเป็นจริง)

2 Maurocurto Aug 18 2020 at 21:19

นี่คือหลักฐานโดยใช้กฎการหักตามธรรมชาติ:

$\vdash((p\implies q)\land(q\implies r))\implies (p\implies r)$

  1. $((p\implies q)\land(q\implies r))$ - สมมติฐาน
  2. $\mid\underline{\quad p}$ - สมมติฐาน
  3. $\mid\quad p\implies q$ - กฎการกำจัด $\land$ ใน $1.$
  4. $\mid\quad q$ - กฎการกำจัด $\implies$ ใน $2.,\,3.$
  5. $\mid\quad q\implies r$ - กฎการกำจัด $\land$ ใน $1.$
  6. $\mid\quad r$ - กฎการกำจัด $\implies$ ใน $4.,\,5.$
  7. $p\implies r$ - กฎการแนะนำของ $\implies$ ใน $2.,\,6.$ (สมมติฐานปิด 2. )
  8. $((p\implies q)\land(q\implies r))\implies (p\implies r)$ - กฎการแนะนำของ $\implies$ ใน $1.,\,7.$ (สมมติฐานปิด $1.$)