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