Aufgabe:
Wenn wir in eine Menge von aussagenlogischen Formeln Ψ immer mehr Formeln hineintun, so wird Ψ
intuitiv früher oder später notgedrungen zwei äquivalente Formeln enthalten. In dieser Aufgabe wollen wir untersuchen, wie viele nicht äquivalente Formeln eine Formelmenge unter bestimmten Bedingungen beinhalten kann.
Die Formelmenge Ψ
soll nun aber nicht beliebig sein, sondern nur Formeln enthalten, die aus einer Formel φ folgen und auch nur die Variablen enthalten, die φ enthält. Beispielsweise könnte für φ=a∧b die Menge Ψ gleich {a,b,¬a∨b} sein, denn alle diese Formeln folgen aus φ und sie sind paarweise nicht äquivalent und es kommen nur a und b darin vor. Dies ist aber nicht die größtmögliche Menge Ψ mit dieser Eigenschaft.
1.Geben Sie nun eine größtmögliche Menge Ψ an für φ=a∧b wie oben.
2.Gegeben ist nun die Formel φ=a1∧a2∧⋯∧an für ein beliebiges n. Wie groß ist nun ein größtmögliches Ψ? Beweisen Sie die Korrektheit Ihrer Antwort.
Die Aufgabe ist sehr wichtig. Ich Bitte um Hilfe
