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.

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