VarAL ⊆{Pi |i ∈N0} sei ein Alphabet aussagenlogischer Variablen. Für eine Menge M ⊆ForAL von aussagenlogischen Formeln sowie i ∈N0 möge Vi(M) wie folgt induktiv definiert sein: V0(M) = M und Vi+1(M) = {f > g| f ∈Vi(M),g∈ M} Außerdem sei V(M) =Si∈N0 Vi(M).
a) Geben Sie V3(M) für M = {P} explizit an.
b) Es sei m ∈ N0 und M = {Pj | j ∈ Zm}. Geben Sie einen arithmetischen Ausdruck für |Vi(M)|in Abhängigkeit von i ∈N0 und m an. Erinnerung. Zm = {j∈N0 | j < m}
c) Beweisen Sie Ihre Behauptung aus b) mittels vollständiger Induktion über i ∈N0. Es sei jetzt VarAL = {P,Q,R,S}. Ferner bezeichne ⊥die unerfüllbare Formel P > P sowie >die Tautologie P < P. Eine Horn-Klausel ist ein Element der Menge K = {> v|v∈VarAL}∪{f g| f ∈V(VarAL),g∈VarAL∪{⊥}} und eine Horn-Formel ein Element der Menge V(K).
d) Geben Sie eine Horn-Formel F ∈ V(K) mit mindestens 6 Horn-Klauseln an und so, dass diese Klauseln alle paarweise nicht äquivalent sind (d.h., sind k1 und k2 Klauseln von F und k1 6= k2, so gilt k1 6≡ k2). Kennzeichen Sie anschließend, was die Horn-Klauseln von F sind.
e) Gibt es eine unerfüllbare Horn-Formel G ∈ V(K), in der ⊥ als Teilwort nicht vorkommt? Wenn ja, geben Sie eine solche Formel an; andernfalls begründen Sie, warum dies nicht der Fall sein kann.
f) Betrachten Sie folgende Horn-Formel:
H =(P > R Q) > (> Q) > (P > Q > S ⊥) > (Q S)
Geben Sie eine Interpretation I: VarAL →B an, die Modell von H ist und so, dass die Anzahl Variablen, die von I mit f belegt werden (d.h. |{v∈VarAL | I(v) = f}|), minimal ist. Begründen Sie anschließend, warum Ihre Interpretation I tatsächlich minimal ist. Hinweis. Ihre Begründung soll möglichst prägnant sein. Insbesondere sollen Sie keine Wahrheitstabelle o.Ä. angeben.
Kann jemand die Aufgabenstellung erklären und lösen?
Danke im Vorraus :D
