+1 Daumen
727 Aufrufe

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

Avatar von

Ich habe das selbe Problem, die d) e) und f) vorallem. Es wäre nett wenn einer evtl die Hornformel verständlich erklären könnte, vorallem im Zusammenhang mit der Aufgabe, und eventuell einen Lösungsansatz geben könnte.

1 Antwort

0 Daumen

Für die a) würde ich sagen ist die Lösung: V₃(M) = {P ^ P ^ P ^ P), für die b): |Vi(M)| = i + 1 = m

bei der c) Beweist du das ganze einfach per Induktion.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community