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

Aktualna wersja na dzień 10:35, 5 wrz 2023

Ć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 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 $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ć (błąd składni): {\displaystyle \frac{\Delta\vdash\Gamma,\varphi} {\Delta\vdash\Gamma,\varphi\vee\psi} \hspace{3cm} \frac{\Delta\vdash\Gamma,\psi} {\Delta\vdash\Gamma,\varphi\vee\psi} }

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

Ćwiczenie 12

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{\Delta\vdash\Gamma}{\Delta,\varphi\vdash\Gamma} \hspace{3cm} \frac{\Delta\vdash\Gamma}{\Delta\vdash\Gamma,\varphi} }

Ćwiczenie 13

Wyprowadzić w rachunku sekwentów:

(a) ⊢ p \lor \neg p

;

(b) ⊢ ((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 1: / Linia 1: @@
-{{Cwiczenie|1|}}
+{{Cwiczenie|1||
-Niech <math>\displaystyle \vdash_{H_1}</math> oznacza system dowodzenia otrzymany
+Niech <math>\vdash_{H_1}</math> oznacza system dowodzenia otrzymany
-z systemu <math>\displaystyle \vdash_H</math> przez zamianę aksjomatu (A3) na
+z systemu <math>\vdash_H</math> przez zamianę aksjomatu (A3) na
 następujący aksjomat:
-*(A3')&nbsp; <math>\displaystyle (\neg\varphi\to\neg\psi)\to((\neg\varphi\to
+*(A3')&nbsp; <math>(\neg\varphi\to\neg\psi)\to((\neg\varphi\to
-\psi)\to\varphi).</math>
+\psi)\to\varphi)</math>.
-Dowieść, że obydwa systemy są równoważne, tzn., że dla
+Dowieść, że obydwa systemy są równoważne, tzn. że dla
-dowolnego sekwentu <math>\displaystyle \Delta\vdash\varphi</math>, zachodzi
+dowolnego sekwentu <math>\Delta\vdash\varphi</math> zachodzi
-<math>\displaystyle \Delta\vdash_H\varphi</math> , gdy <math>\displaystyle \Delta\vdash_{H_1}\varphi</math>.
+<math>\Delta\vdash_H\varphi</math>, gdy <math>\Delta\vdash_{H_1}\varphi</math>.
+}}
-Ćwiczenie 2.
+{{Cwiczenie|2||
+Niech <math>\vdash_{H_2}</math> oznacza system dowodzenia otrzymany
+z systemu <math>\vdash_H</math> przez zamianę aksjomatu (A3) na następujący aksjomat:
-Niech <math>\displaystyle \vdash_{H_2}</math> oznacza system dowodzenia otrzymany
+*(A3")&nbsp; <math>(\neg\varphi\to\neg\psi)\to(\psi\to\varphi)</math>.
-z systemu <math>\displaystyle \vdash_H</math> przez zamianę aksjomatu (A3) na <math>\displaystyle \vdash_H</math>, następujący aksjomat:
-*(A3")&nbsp; <math>\displaystyle (\neg\varphi\to\neg\psi)\to(\psi\to\varphi).</math>
+Dowieść, że obydwa systemy są równoważne, tzn. że dla
+dowolnego sekwentu <math>\Delta\vdash\varphi</math> zachodzi
-Dowieść, że obydwa systemy są równoważne, tzn., że dla
+<math>\Delta\vdash_H\varphi</math>, gdy <math>\Delta\vdash_{H_2}\varphi</math>.
-dowolnego sekwentu <math>\displaystyle \Delta\vdash\varphi</math>, zachodzi
+}}
-<math>\displaystyle \Delta\vdash_H\varphi</math> , gdy <math>\displaystyle \Delta\vdash_{H_2}\varphi</math>.
-Ćwiczenie 3.
+{{Cwiczenie|3||
 Dowieść, że aksjomatu (A3) nie da się wyprowadzić z
 aksjomatów (A0-2) przy pomocy reguły odrywania.
+}}
+{{Cwiczenie|4||
-Ćwiczenie 4.
+Dowieść <math>\vdash_H\neg p \to(p\to q)</math> używając twierdzenia o
-Dowieść <math>\displaystyle \vdash_H\neg p \to(p\to q)</math> używając twierdzenia o
 dedukcji oraz bez użycia tego twierdzenia.
+}}
+{{Cwiczenie|5|e|
-Ćwiczenie 5.
+Pokazać, że w systemie <math>\vdash_H</math> dopuszczalna jest
-Pokazać, że w systemie <math>\displaystyle \vdash_H</math> dopuszczalna jest
 następująca reguła:
-<center><math>\displaystyle \frac{\varphi\to\psi\ \ \
+<center><math>\frac{\varphi\to\psi\ \ \
 \neg\psi}{\neg\varphi}</math></center>
-tzn.&nbsp;pokazać, że jeśli <math>\displaystyle \Delta\vdash_H\varphi\to\psi</math> oraz
+tzn.&nbsp;pokazać, że jeśli <math>\Delta\vdash_H\varphi\to\psi</math> oraz
-<math>\displaystyle \Delta\vdash_H\neg\psi</math>, to również mamy <math>\displaystyle  \Delta\vdash_H\neg\varphi</math>.
+<math>\Delta\vdash_H\neg\psi</math>, to również mamy <math>\Delta\vdash_H\neg\varphi</math>.
+}}
+{{Cwiczenie|6||
-Ćwiczenie 6.
+Dowieść, że dla każdej formuły <math>\varphi</math>, nie będącej
+tautologią, istnieje maksymalny zbiór formuł&nbsp;<math>\Delta</math> (nad daną sygnaturą)
-Dowieść, że dla każdej formuły <math>\displaystyle \varphi</math>, nie będącej
-tautologią, istnieje maksymalny zbiór formuł&nbsp;<math>\displaystyle \Delta</math> (nad daną sygnaturą)
 o&nbsp;tej własności, że
-<math>\displaystyle \Delta\not\vdash_H\varphi</math>.
+<math>\Delta\not\vdash_H\varphi</math>.
+}}
+{{Cwiczenie|7||
-Ćwiczenie 7.
 Każdy z poniższych sekwentów wyprowadzić w  systemie
-<math>\displaystyle \vdash_{H^+}</math>, <math>\displaystyle \vdash_{N}</math>, <math>\displaystyle \vdash_G</math>.
+<math>\vdash_{H^+}</math>, <math>\vdash_{N}</math>, <math>\vdash_G</math>.
-:<math>(a)\ \displaystyle \vdash \bot\to p</math>;
+:<math>(a)\ \vdash \bot\to p</math>;
-:<math>(b)\ \displaystyle p\to q,q\to r\vdash p\to r</math>;
+:<math>(b)\ p\to q,q\to r\vdash p\to r</math>;
-:<math>(c)\ \displaystyle \vdash(\neg p\to p)\to p</math>;
+:<math>(c)\ \vdash(\neg p\to p)\to p</math>;
-:<math>(d)\ \displaystyle p,\neg p\vdash q</math>;
+:<math>(d)\ p,\neg p\vdash q</math>;
-:<math>(e)\ \displaystyle p\to(q\to r)\vdash q\to(p\to r)</math>;
+:<math>(e)\ p\to(q\to r)\vdash q\to(p\to r)</math>;
-:<math>(f)\ \displaystyle \vdash (\neg p\to \neg q)\to (q\to p)</math>;
+:<math>(f)\ \vdash (\neg p\to \neg q)\to (q\to p)</math>;
-:<math>(g)\ \displaystyle \vdash \neg(p\wedge q)\to(\neg p\vee\neg q)</math>.
+:<math>(g)\ \vdash \neg(p\wedge q)\to(\neg p\vee\neg q)</math>.
+}}
+{{Cwiczenie|8||
-Ćwiczenie 8.
+Dowieść, że jeśli <math>\Delta\vdash_{N}\varphi</math>, to dla dowolnej
+formuły <math>\psi</math> zachodzi <math>\Delta,\psi\vdash_{N}\varphi</math>.
+}}
-Dowieść, że jeśli <math>\displaystyle \Delta\vdash_{N}\varphi</math>, to dla dowolnej
+{{Cwiczenie|9||
-formuły <math>\displaystyle \psi</math> zachodzi <math>\displaystyle \Delta,\psi\vdash_{N}\varphi</math>.
+Dowieść, że jeśli <math>\Delta\vdash_{N}\bot</math>, to dla dowolnej
+formuły <math>\varphi</math> zachodzi <math>\Delta\vdash_{N}\varphi</math>.
+}}
-Ćwiczenie 9.
+{{Cwiczenie|10||
-Dowieść, że jeśli <math>\displaystyle \Delta\vdash_{N}\bot</math>, to dla dowolnej
+Dla każdego z systemów <math>\vdash_{H^+}</math>, <math>\vdash_{N}</math>,
-formuły <math>\displaystyle \varphi</math> zachodzi <math>\displaystyle \Delta\vdash_{N}\varphi</math>.
+<math>\vdash_G</math> dowieść, że jeśli sekwent <math>\Delta\vdash\varphi</math> jest
+wyprowadzalny w&nbsp;tym systemie oraz <math>S</math> jest podstawieniem formuł na
+zmienne zdaniowe, to sekwent <math>S(\Delta)\vdash S(\varphi)</math>
-Ć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.
+}}
+{{Cwiczenie|11|k|
-Ćwiczenie 11.
-Udowodnić, że w rachunku sekwentów zamiana reguły <math>\displaystyle (\vee </math> -prawa <math>\displaystyle  )</math>
+Udowodnić, że w rachunku sekwentów zamiana reguły <math>(\vee</math> -prawa <math>)</math>
 na dwie reguły:
-<center><math>\displaystyle \frac{\Delta\vdash\Gamma,\varphi}
+<center><math>\frac{\Delta\vdash\Gamma,\varphi}
 {\Delta\vdash\Gamma,\varphi\vee\psi}
 \hspace{3cm} \frac{\Delta\vdash\Gamma,\psi}
@@ Linia 103: / Linia 102: @@
 daje w wyniku równoważny system dowodzenia(wyprowadzalne są te same sekwenty).
+}}
+{{Cwiczenie|12|weakening|
-Ćwiczenie 12.{{kotwica|weakening|}}
 Udowodnić, że następujące reguły ''osłabiania'' są dopuszczalne
 w rachunku sekwentów:
-<center><math>\displaystyle \frac{\Delta\vdash\Gamma}{\Delta,\varphi\vdash\Gamma}
+<center><math>\frac{\Delta\vdash\Gamma}{\Delta,\varphi\vdash\Gamma}
 \hspace{3cm}
 \frac{\Delta\vdash\Gamma}{\Delta\vdash\Gamma,\varphi}
 </math></center>
+}}
+{{Cwiczenie|13||
-Ćwiczenie 13.
 Wyprowadzić w rachunku sekwentów:
-:<math>(a)\ \displaystyle \vdash p\vee \neg p</math>;
+:<math>(a)\ \vdash p\vee \neg p</math>;
-:<math>(b)\ \displaystyle \vdash ((p\to q)\to p)\to p</math>.
+:<math>(b)\ \vdash ((p\to q)\to p)\to p</math>.
-Czy można to zrobić używając tylko sekwentów postaci <math>\displaystyle \Delta\vdash\varphi</math>
+Czy można to zrobić używając tylko sekwentów postaci <math>\Delta\vdash\varphi</math>
 (z jedną formułą po prawej)?
+}}

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

Aktualna wersja na dzień 10:35, 5 wrz 2023

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia