Logika dla informatyków/Ćwiczenia 5: Różnice pomiędzy wersjami

Wersja z 21:39, 21 wrz 2006

Ćwiczenie 1.

Niech $⊢_{H_{1}}$ oznacza system dowodzenia otrzymany z systemu $⊢_{H}$ przez zamianę aksjomatu (A3) na następujący aksjomat:

(A3') $(\neg φ \to \neg ψ) \to ((\neg φ \to ψ) \to φ) .$

Dowieść, że obydwa systemy są równoważne, tzn., że dla dowolnego sekwentu $Δ ⊢ φ$ , zachodzi $Δ ⊢_{H} φ$ , gdy $Δ ⊢_{H_{1}} φ$ .

Ćwiczenie 2.

Niech $⊢_{H_{2}}$ oznacza system dowodzenia otrzymany z systemu $⊢_{H}$ przez zamianę aksjomatu (A3) na $⊢_{H}$ , następujący aksjomat:

(A3") $(\neg φ \to \neg ψ) \to (ψ \to φ) .$

Dowieść, że obydwa systemy są równoważne, tzn., że dla dowolnego sekwentu $Δ ⊢ φ$ , zachodzi $Δ ⊢_{H} φ$ , gdy $Δ ⊢_{H_{2}} φ$ .

Ćwiczenie 3.

Dowieść, że aksjomatu (A3) nie da się wyprowadzić z aksjomatów (A0-2) przy pomocy reguły odrywania.

Ćwiczenie 4.

Dowieść $⊢_{H} \neg p \to (p \to q)$ używając twierdzenia o dedukcji oraz bez użycia tego twierdzenia.

Ćwiczenie 5.

Pokazać, że w systemie $⊢_{H}$ dopuszczalna jest następująca reguła:

\frac{φ \to ψ \neg ψ}{\neg φ}

tzn. pokazać, że jeśli $Δ ⊢_{H} φ \to ψ$ oraz $Δ ⊢_{H} \neg ψ$ , to również mamy $Δ ⊢_{H} \neg φ$ .

Ćwiczenie 6.

Dowieść, że dla każdej formuły $φ$ , nie będącej tautologią, istnieje maksymalny zbiór formuł $Δ$ (nad daną sygnaturą) o tej własności, że $Δ ⊢_{H} φ$ .

Ćwiczenie 7.

Każdy z poniższych sekwentów wyprowadzić w systemie $⊢_{H^{+}}$ , $⊢_{N}$ , $⊢_{G}$ .

(a) ⊢ ⊥ \to p

;

(b) p \to q, q \to r ⊢ p \to r

;

(c) ⊢ (\neg p \to p) \to p

;

(d) p, \neg p ⊢ q

;

(e) p \to (q \to r) ⊢ q \to (p \to r)

;

(f) ⊢ (\neg p \to \neg q) \to (q \to p)

;

(g) ⊢ \neg (p \land q) \to (\neg p \lor \neg q)

.

Ćwiczenie 8.

Dowieść, że jeśli $Δ ⊢_{N} φ$ , to dla dowolnej formuły $ψ$ zachodzi $Δ, ψ ⊢_{N} φ$ .

Ćwiczenie 9.

Dowieść, że jeśli $Δ ⊢_{N} ⊥$ , to dla dowolnej formuły $φ$ zachodzi $Δ ⊢_{N} φ$ .

Ćwiczenie 10.

Dla każdego z systemów $⊢_{H^{+}}$ , $⊢_{N}$ , $⊢_{G}$ dowieść, że jeśli sekwent $Δ ⊢ φ$ jest wyprowadzalny w tym systemie oraz $S$ jest podstawieniem formuł na zmienne zdaniowe, to sekwent $\vec{S} (Δ) ⊢ S (φ)$ powstający w wyniku podstawienia jest też wyprowadzalny w tym systemie.

Ćwiczenie 11.

Udowodnić, że w rachunku sekwentów zamiana reguły $(\lor$ -prawa $)$ na dwie reguły:

Parser nie mógł rozpoznać (nieznana funkcja „\prooftree”): {\displaystyle \displaystyle \prooftree{\Delta\vdash\Gamma,\varphi} \justifies{\Delta\vdash\Gamma,\varphi\vee\psi} \endprooftree \hspace{3cm} \prooftree{\Delta\vdash\Gamma,\psi} \justifies{\Delta\vdash\Gamma,\varphi\vee\psi} \endprooftree}

daje w wyniku równoważny system dowodzenia (wyprowadzalne s± te same sekwenty).

Udowodnić, że następuj±ce reguły osłabiania s± dopuszczalne w rachunku sekwentów:

Parser nie mógł rozpoznać (nieznana funkcja „\prooftree”): {\displaystyle \displaystyle \prooftree{\Delta\vdash\Gamma}\justifies{\Delta,\varphi\vdash\Gamma} \endprooftree \hspace{3cm} \prooftree{\Delta\vdash\Gamma}\justifies{\Delta\vdash\Gamma,\varphi} \endprooftree}

Wyprowadzić w rachunku sekwentów:
1. $⊢ p \lor \neg p$ ;
2. $⊢ ((p \to q) \to p) \to p$ .

Czy można to zrobić używaj±c tylko sekwentów postaci $Δ ⊢ φ$ (z jedn± formuł± po prawej)?

@@ Linia 63: / Linia 63: @@
 :<math>(a)\ \displaystyle \vdash \bot\to p</math>;
-:(b)\ <math>\displaystyle p\to q,q\to r\vdash p\to r</math>;
+:<math>(b)\ \displaystyle p\to q,q\to r\vdash p\to r</math>;
-:(c)\ <math>\displaystyle \vdash(\neg p\to p)\to p</math>;
+:<math>(c)\ \displaystyle \vdash(\neg p\to p)\to p</math>;
-:(d)\ <math>\displaystyle p,\neg p\vdash q</math>;
+:<math>(d)\ \displaystyle p,\neg p\vdash q</math>;
-:(e)\ <math>\displaystyle p\to(q\to r)\vdash q\to(p\to r)</math>;
+:<math>(e)\ \displaystyle p\to(q\to r)\vdash q\to(p\to r)</math>;
-:(f)\ <math>\displaystyle \vdash (\neg p\to \neg q)\to (q\to p)</math>;
+:<math>(f)\ \displaystyle \vdash (\neg p\to \neg q)\to (q\to p)</math>;
-:(g)\ <math>\displaystyle \vdash \neg(p\wedge q)\to(\neg p\vee\neg q)</math>.
+:<math>(g)\ \displaystyle \vdash \neg(p\wedge q)\to(\neg p\vee\neg q)</math>.
@@ Linia 79: / Linia 79: @@
 Ćwiczenie 9.
-Dowieść, że je¶li <math>\displaystyle \Delta\vdash_{N}\bot</math>, to dla dowolnej
+Dowieść, że jeśli <math>\displaystyle \Delta\vdash_{N}\bot</math>, to dla dowolnej
 formuły <math>\displaystyle \varphi</math> zachodzi <math>\displaystyle \Delta\vdash_{N}\varphi</math>.
-# Dla każdego z sytemów <math>\displaystyle \vdash_{H^+}</math>, <math>\displaystyle \vdash_{N}</math>,
-<math>\displaystyle \vdash_G</math> dowie¶ć, że je¶li sekwent <math>\displaystyle \Delta\vdash\varphi</math> jest
+Ćwiczenie 10.
+Dla każdego z systemów <math>\displaystyle \vdash_{H^+}</math>, <math>\displaystyle \vdash_{N}</math>,
+<math>\displaystyle \vdash_G</math> dowieść, że jeśli sekwent <math>\displaystyle \Delta\vdash\varphi</math> jest
 wyprowadzalny w&nbsp;tym systemie oraz <math>\displaystyle S</math> jest podstawieniem formuł na
 zmienne zdaniowe, to sekwent <math>\displaystyle \vec{S}(\Delta)\vdash S(\varphi)</math>
-powstaj±cy w  wyniku podstawienia  jest też wyprowadzalny w tym systemie.
+powstający w  wyniku podstawienia  jest też wyprowadzalny w tym systemie.
-#
-  Udowodnić, że w rachunku sekwentów zamiana reguły <math>\displaystyle (\vee </math> -prawa <math>\displaystyle  )</math>
+Ćwiczenie 11.
+Udowodnić, że w rachunku sekwentów zamiana reguły <math>\displaystyle (\vee </math> -prawa <math>\displaystyle  )</math>
 na dwie reguły:

Logika dla informatyków/Ćwiczenia 5: Różnice pomiędzy wersjami

Wersja z 21:39, 21 wrz 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia