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

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

Ćwiczenie 1

Dowieść, że "silne" twierdzenie o pełności (Twierdzenie 6.7) pociąga twierdzenie o zwartości.

Ćwiczenie 2

Udowodnić, że jeśli w systemie $⊢_{H +}$ zamienimy aksjomaty (B1--B4) na aksjomaty

(D1) Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\to\var\varphi\vee \psi} ;
(D2) Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \psi\to\var\varphi\vee \psi} ;
(D3] Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle (\var\varphi\to \vartheta)\wedge(\psi\to \vartheta) \to(\var\varphi\vee \psi \to \vartheta)} ;
(C1) Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\wedge \psi\to \var\varphi} ;
(C2) Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\wedge \psi\to \psi} ;
(C3) Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle (\vartheta\to \var\varphi)\wedge(\vartheta\to \psi)\to (\vartheta\to\var\varphi\wedge \psi)} .

to twierdzenie o pełności pozostanie prawdziwe.

Ćwiczenie 3

Dany jest nieskończony zbiór chłopców, z których każdy ma skończoną liczbę narzeczonych. Ponadto dla każdego $k \in N$ ,

dowolnych

k

chłopców ma co najmniej

k

narzeczonych. Dowieść, że każdy chłopiec może się ożenić z jedną ze swoich narzeczonych bez popełnienia bigamii.

@@ Linia 1: / Linia 1: @@
-{{cwiczenie|2|b|
+{{cwiczenie|1||
-}}
+Dowieść, że "silne" twierdzenie o pełności (Twierdzenie&nbsp;[[#tw-zda-4|6.7]]) pociąga twierdzenie o zwartości.}}
+<span id="wtomigraj">
+{{cwiczenie|2||
+Udowodnić, że jeśli w systemie <math>\vdash_{H+}</math>
+zamienimy aksjomaty (B1--B4) na aksjomaty
+*(D1) <math>\var\varphi\to\var\varphi\vee \psi</math>;
+*(D2) <math>\psi\to\var\varphi\vee \psi</math>;
+*(D3] <math>(\var\varphi\to \vartheta)\wedge(\psi\to \vartheta)
+\to(\var\varphi\vee \psi \to \vartheta)</math>;
+*(C1) <math>\var\varphi\wedge \psi\to \var\varphi</math>;
+*(C2) <math>\var\varphi\wedge \psi\to \psi</math>;
+*(C3) <math>(\vartheta\to \var\varphi)\wedge(\vartheta\to \psi)\to
+(\vartheta\to\var\varphi\wedge \psi)</math>.
+to twierdzenie o pełności pozostanie prawdziwe.}}
+{{cwiczenie|3||
+Dany jest nieskończony zbiór chłopców, z których każdy ma
+skończoną liczbę narzeczonych. Ponadto dla każdego <math>k\in N</math>,
+dowolnych <math>k</math> chłopców ma co najmniej <math>k</math> narzeczonych. Dowieść, że każdy chłopiec może się ożenić z jedną ze swoich narzeczonych bez popełnienia bigamii.}}