Pisemka Gregor 8.12.2011

Výroková logika, normální tvary formulí, predikátová logika, věty o úplnosti výrokové a predikátové logiky, prenexní tvary formulí, modely teorií 1. řádu. Meze formální metody, Gödelovy věty.
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Pisemka Gregor 8.12.2011

Příspěvek od mathemage »

1) Uvedte platna tvrzeni:
a) \Theta_\mathbb{P}(T) = \Theta_\mathbb{P}(\Theta_\mathbb{P}(T))
b) \Theta_\mathbb{P}(T\cap S) = \Theta_\mathbb{P}(T)\cap\Theta_\mathbb{P}(S)
b) T\subseteq S \Rightarrow \Theta_\mathbb{P}(T)\subseteq\Theta_\mathbb{P}(S)
(Plati a), c) )

2) Budte \mathbb{P} = \{p, q, r\} a teorie ve vyrokove logice T = {q}. Kolik je jednoduchych extenzi teorie T?
(M(T) = 2^2 = 4, S je jednoducha extenze T prave tehdy kdyz M(S) \subseteq M(T), tedy extensi je celkem jako podmnozin tridy modelu: 2^{M(T)} = 2^4 = 16)

3) Necht mame |\mathbb{P}|\geq\omega, tridu modelu K = \;^{\mathbb{P}}2 - \{v\}. Je K axiomatizovatelne?
(Sporem: K axiomatizovatelne, -K tez axiomatizovatelne skrze teorii \{p^{v(p)}| p\in\mathbb{P}\}, tedy dle vety z prednasky je -K konecne axiomatizovatelne. Muzeme techto konecne axiomu spojit konjunkci do jedne formule, neboli \exists\varphi: M(\varphi) = -K. To, zda-li je nejake pravdivostni ohodnoceni modelem teto teorie zalezi jen a pouze na prvovyrocich vyskytujicich se ve formuli \varphi, zbytek lze volit libovolne. Ovsem zbyvajicicich prvovyroku je |\mathbb{P}|, tedy vsech moznych modelu teto teorie je |M(\varphi)| = 2^{\mathbb{|P|}}. Zaroven ovsem |M(\varphi)| = |-K| = |\{v\}| = 1, coz je spor!)
Carpe Diem!
Odpovědět

Zpět na „AIL062 Výroková a predikátová logika“