Mantıksal bir çıkarım: $\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $ doğruluk tablolarını kullanmadan

Aug 18 2020

Aşağıdaki çıkarımın geçerliliğini kanıtlayın (doğruluk tablolarını KULLANMAYIN):

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $$ Öneriyi gösteren bir doğruluk tablosu çizdim: $((p\implies q) \land (q\implies r)) \implies (p\implies r)$bir totolojidir, ancak sonucu göstermek için mantık çıkarım kurallarını kullanarak öncülleri manipüle etmede başarılı olamamıştır.
Lütfen biraz tavsiye verin.

Yanıtlar

7 GrahamKemp Aug 19 2020 at 01:51

Biraz farklı bir gösterim kullanarak - Sıralı Hesap - aşağıdaki doğal kesinti kanıtlama ağacını oluşturabiliriz:

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

Böylece çıkarımın geçerli olduğu sonucuna varıyoruz: $$\left\lvert\!\begin{split} &p\to q\\&q\to r\\\hline &p\to r\end{split}\right.$$

Kullanılan kurallar - nerede $\Gamma, \Delta$ifadelerin listeleridir ve$\varphi, \psi$ tek ifadelerdir — şunlardır:

$\textsf{ID}$: Kimlik (veya varsayım) $\qquad\begin{split}~\\\hline\Gamma,\varphi&\vdash\varphi\end{split}$

Önemsiz bir şekilde: Ek (muhtemelen boş) bir varsayım listesiyle birlikte varsayılırsa bir ifade türetebilirsiniz.
${\to}\mathsf E$: Koşullu Eliminasyon: $\qquad\begin{split}\Gamma&\vdash\varphi\\\Delta&\vdash \varphi\to \psi\\\hline\Gamma\cup\Delta&\vdash \psi\end{split}$

Bir koşul, bir ifade listesinden türetilebiliyorsa ve onun öncülü başka bir listeden türetilebiliyorsa, sonucun listelerin birleşiminden türetilebileceği sonucuna varabiliriz.
${\to}\mathsf I$: Koşullu Giriş: $\qquad\begin{split}\Gamma,\varphi&\vdash \psi\\\hline\Gamma&\vdash\varphi\to\psi\end{split}$

Bir sonuç, bir öncülü içeren bir ifadeler listesinden türetilebiliyorsa, ilgili koşulun listeden türetilebileceği sonucuna varabiliriz.

Bu çıkarım örneğidir boşaltma bir varsayım. Bir kanıtın sonunda, tesisler hariç tüm varsayımların uygun şekilde yerine getirilmiş olması gerekir.

Burada , sonucumuzun öncülünün eklenmesiyle birlikte iki öncül olmak üzere üç ifade varsaydık . Sonuçtan başarıyla türetildikten sonra bu üçüncü varsayımı geçersiz kılıyoruz.

6 rain1 Aug 18 2020 at 20:11

Kanıtlamak istiyoruz

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

P'yi bağlama tanıtın:

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

Bir araya koymak $p\implies q$ ve $p$ çıkarmak $q$:

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

Bir araya koymak $q\implies r$ ve $q$ çıkarmak $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

Totolojiyi kullanın $$(p\implies q)\implies((q\implies r)\implies(p\implies r))$$bunun yerine ve verilen öncüllerle Modus Ponens'i iki kez uygulayın. Alternatif olarak, totolojiyi kullanın$$\varphi\implies(\psi\implies (\varphi\land\psi))$$ sonuçlandırmak $$\frac{\begin{matrix} \varphi \\ \psi\end{matrix}}{(\varphi\land\psi)} $$ ve sonra verdiğiniz totolojiyi kanıtlamak için kullanın $$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{ p\implies r} $$

Eksiksizlik adına: öncüller verildiğinde, yukarıdaki totolojiyi ekleyin.

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

ve sonra

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

kanıtı tamamlar. Alternatif için ilk önce verilen kuralı kullanarak

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

ve sonra sahip olduğumuz diğer totolojiyi kullanarak

$$\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'i iki kez kullanın ve durum tanıtımı:

$p\implies q$ ve $p$ anlamına geliyor $q$ doğrudur. (ilk kullanım). $q\implies r$ ve $q$ doğru demektir $r$doğru. (ikinci kullanım). Yani verilen$p \implies q$ ve $q\implies r$ sonra şartlı giriş ile $p$ doğru olmak demek $r$doğru. Yani$p\implies r$.

Tamam sanırım anladım:

Notasyonu alırsak $\phi\vdash \psi$ "varsayacak mıydık $\phi$ türetebiliriz $\psi$ sonra:

$p\implies q$ (verilen)

$p \implies r$ (verilen)

$p\vdash p$ (bir şeyi varsaymak, bir şeyi varsaymaktır. $\mu\vdash \mu$ her zaman doğrudur çünkü varsayarsak $\mu$ türetebiliriz $\mu$... çünkü doğru olduğunu varsayıyoruz. Bu biz iddia ediyorlar söylemek değildir olduğunu ( "başlangıç tesislerinde kalan" hakkında yorumda, iddia ettiği gibi iman ima) true; bu, eğer doğru olsaydı, bir varsayım altında türetebilirdik. Elbette doğru değilse , türettiklerimiz alakalı olmayacak.)

$p\vdash p\implies q$ ($p\implies q$ varsayarsak da verilmiş bir gerçektir $p$ya da değil. Her gerçek ifade için$T$ sonra $\mu\vdash T$her zaman doğru olacak. Ve sanırım$\mu\vdash F$ her zaman yanlış olacaktır.)