Logika dla informatyków/Ćwiczenia 7

Ćwiczenie 1

Rozpatrzmy system ${⊢}_h$, którego aksjomatami są formuły postaci (A1--A9), a nie dowolne generalizacje takich formuł. Regułami wnioskowania w ${⊢}_h$ niech będą (MP) oraz reguła generalizacji:

$\frac{\phi }{\mathrm{\forall }x\phi }$

Udowodnić, że twierdzenia systemów ${⊢}_h$ i ${⊢}_H$ są takie same, ale z Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \Gamma\vdash_h\var\varphi} nie wynika Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \Gamma\models\var\varphi} .

Ćwiczenie 2

Udowodnić twierdzenie o pełności dla nieprzeliczalnych sygnatur.

Ćwiczenie 3

System naturalnej dedukcji dla logiki pierwszego rzędu można otrzymać przez dodanie do systemu ${⊢}_N$ nastepujących reguł:

Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \frac{\Gamma\vdash\var\varphi(y/x)} {\Gamma\vdash\forall {x}\ciut \var\varphi}(\forall\mbox{\rm-intro}) \hspace{3cm}\frac{\Gamma\vdash\forall {x}\ciut \var\varphi} {\Gamma\vdash\var\varphi(t/x)}\using{(\forall\mbox{\rm-elim})}}

Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \frac{\Gamma\vdash\var\varphi(t/x)}{\Gamma\vdash\exists {x}\ciut \var\varphi}(\exists\mbox{\rm-intro})\frac{\Gamma\vdash\exists {x}\ciut \var\varphi\quad \Gamma,\var\varphi(y/x)\vdash\psi} {\Gamma\vdash\psi}\using{(\exists\mbox{\rm-elim})}}

przy czym regułę Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\forall\mbox{\rm-intro})} wolno stosować tylko wtedy, gdy Parser nie mógł rozpoznać (nieznana funkcja „\fv”): {\displaystyle {y}\not\in\fv{\forall {x}\ciut \var\varphi}} oraz $y$ nie jest wolne w żadnej z formuł ze zbioru $\mathrm{\Gamma }$. Natomiast reguła Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\exists\mbox{\rm-intro})} używana jest przy zastrzeżeniu Parser nie mógł rozpoznać (nieznana funkcja „\fv”): {\displaystyle {y}\not\in\fv{\Gamma\cup\{\exists {x}\ciut \var\varphi\}\cup\{\psi\}}} . Udowodnić twierdzenie o pełności dla tego systemu.

Ćwiczenie 4

Zaproponować reguły rachunku sekwentów dla logiki pierwszego rzędu.