Logika dla informatyków/Ćwiczenia 6

Ćwiczenie 1

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

<span id="wtomigraj}

Ćwiczenie 2

Udowodnić, że jeśli w systemie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \vdash_{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)] </math>(\var\varphi\to \vartheta)\wedge(\psi\to \vartheta)

\to(\var\varphi\vee \psi \to \vartheta)</math>;

• [(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)] </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.

Ć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.