Logik: Anzahl Formeln...

[icarus2]

Im Buch "Logik fuer Informatiker" von Uwe Schoenig lautet die Uebung 6:

Wie viele verschiedene Formlen mit den atomaren Formeln $A\_1, A\_2,\ldots, A_n$ und verschiedenen Wahrheitsverlaeufen gibt es?

Die Antwort lautet $2^{2^n}$.

Das Problem ist, dass ich mir nicht sicher bin ob ich verstehe warum das so ist. Meine Erklaerung ist:
Es gibt gesamthaft $2^n$ Belegungen fuer n atomare Variabeln. Nun kann man fuer jede dieser Belegungen entscheiden, ob sie in der Formel enthalten sein soll, oder nicht. Das gibt dann $2^{2^n}$ Moeglichkeiten.

Zur eigentlichen Frage:
Stimmt meine Begruendung? Ich finde sie zu ungenau (fall sie ueberhaupt richtig ist). Kann mir jemand sagen ob meien Antwort stimmt oder gegebenenfalls die Loesung richtige erklaren?

[SG1]

Wie kann eine Belegung in einer Formel enthalten sein? Ersetze "ob sie in der Formel enthalten sein soll" durch "ob diese Belegung die Formel wahr machen soll", dann passts.

[Bashar]

icarus2 schrieb:

Im Buch "Logik fuer Informatiker" von Uwe Schoenig lautet die Uebung 6:

Wie viele verschiedene Formlen mit den atomaren Formeln $A\_1, A\_2,\ldots, A_n$ und verschiedenen Wahrheitsverlaeufen gibt es?

Die Antwort lautet $2^{2^n}$.

Das ist normalerweise falsch. Es gibt jeweils $2^{2^n}$ boolesche Funktionen, aber die Formeldarstellung einer Funktion ist ja nicht eindeutig. Es sei denn, man hätte hier Formel und Funktion gleich definiert, was ich komisch fände, oder man lässt nur Formeln in einer kanonischen Normalform zu.

Das Problem ist, dass ich mir nicht sicher bin ob ich verstehe warum das so ist. Meine Erklaerung ist:
Es gibt gesamthaft $2^n$ Belegungen fuer n atomare Variabeln. Nun kann man fuer jede dieser Belegungen entscheiden, ob sie in der Formel enthalten sein soll, oder nicht. Das gibt dann $2^{2^n}$ Moeglichkeiten.

Für Funktionen: Eine boolesche Funktion mit n Argumenten hat, da jedes einen von zwei Werten annehmen kann, einen Definitionsbereich von $2^n$ Elementen. Jedem davon kann man einen von zwei Funktionswerten zuordnen, also bekommt man $2^{2^n}$ verschiedene Funktionen.

[SG1]

Bashar schrieb:

icarus2 schrieb:

Im Buch "Logik fuer Informatiker" von Uwe Schoenig lautet die Uebung 6:

Wie viele verschiedene Formlen mit den atomaren Formeln $A\_1, A\_2,\ldots, A_n$ und verschiedenen Wahrheitsverlaeufen gibt es?

Die Antwort lautet $2^{2^n}$.

Das ist normalerweise falsch. Es gibt jeweils $2^{2^n}$ boolesche Funktionen, aber die Formeldarstellung einer Funktion ist ja nicht eindeutig.

Deshalb steht da ja auch auch "und verschiedenen Wahrheitsverlaeufen".

[Bashar]

Ahja. Komische Ausdrucksweise, das sollte man sich IMHO nicht angewöhnen.

Mein Punkt bleibt aber bestehen. Man zeigt das sinnvollerweise nicht über die Anzahl der Möglichkeiten, eine Formel zu konstruieren, sondern über die Anzahl der "Wahrheitsverläufe", normalerweise "Funktionen" genannt.

[icarus2]

SG1 schrieb:

Wie kann eine Belegung in einer Formel enthalten sein? Ersetze "ob sie in der Formel enthalten sein soll" durch "ob diese Belegung die Formel wahr machen soll", dann passts.

Stimmt, eine Belegung kann nicht in einer Formel enthalten sein ^^

Bashar schrieb:

Das ist normalerweise falsch. Es gibt jeweils $2^{2^n}$ boolesche Funktionen, aber die Formeldarstellung einer Funktion ist ja nicht eindeutig. Es sei denn, man hätte hier Formel und Funktion gleich definiert, was ich komisch fände, oder man lässt nur Formeln in einer kanonischen Normalform zu.

Das hatte ich verwirrt, weil man eine Formel im Prinzip auf beliebig viele Arten schreiben kann. Aber mit den boolschen Funktionen macht das Sinn. Formel und Funktion sind im Buch nicht gleich definiert.
Vielleicht hat der Autor das auch so gemeint sich aber etwas unklar ausgedrueckt.

Bashar schrieb:

Für Funktionen: Eine boolesche Funktion mit n Argumenten hat, da jedes einen von zwei Werten annehmen kann, einen Definitionsbereich von 2n Elementen. Jedem davon kann man einen von zwei Funktionswerten zuordnen, also bekommt man 22n verschiedene Funktionen.

Gute Erklaerung, jetzt versteh ichs

Vielen Dank fuer eure Antworten.

[Jockelx]

Ist das wirklich so leicht gemeint?
Ich hätte das so gelesen/gemacht:

Es gibt die atomaren Formeln A1, A2,..., die wahr oder falsch sein können, also
A1(0), A1(1), A2(0), A2(1),... atomare Formeln

Formeln bildet man aus atomaren Fomeln mittels

- Alle atomaren Formeln sind Formeln
- Für alle Formeln F und G sind F | G und F & G Formeln
- Für jede Formel F ist !F eine Formel
- Für alle Formeln F und G ist (F → G) eine Formel
- Für alle Formeln F und G ist (F G) eine Formel

~~
Für n=2 haben wir die Formeln
- A1(0), A1(1), A2(0), A2(1)
- A1(0) & A2(0), A1(0) & A2(1), A1(1) & A2(0), A1(1) & A2(1)
- A1(0) | A2(0), A1(0) | A2(1), A1(1) | A2(0), A1(1) | A2(1)
- A1(0) A2(0), A1(0) A2(1), A1(1) A2(0), A1(1) A2(1)
~~
Die Negationen und Implikatinen fallen wegen z.B. A1(1) & A2(0) = ! A1(0) & A2(0) und A1(0) → A2(0) = A1(1) | A2(0) alle raus.

Ob das so gemeint ist, bzw. ob das überhaupt eine richtige Aussage ist, weiß ich aber leider nicht.

Edit:
Die Formeln waren schrott. Richtig ist:
A, B, !A, !B
A & B, !A & B, A & !B, !A & !B
A | B, !A | B, A | !B, !A | !B
A B, !A B, A !B, !A !B

Das sind die 16 Formeln, für die es immer eine Belegung gibt, die unterschiedliche Wahrheitswerte zu jeder anderen Formel hat.
Aber weiterhin: weiß weder ob das gemeint war, noch ob das für alle n gilt.

[SG1]

Jockelx schrieb:

Ist das wirklich so leicht gemeint?

Ich pack mal die Glaskugel aus und sage: Ja. Aber Bashar hat schon recht, die Formulierung könnte besser sein. Und wenn mans ganz genau nimmt, ist die Rechnung, die alle hier angestellt haben auch nur eine obere Abschätzung. Dass diese Abschätzung auch exakt ist sieht man dann, indem man sich überlegt, dass es zu jedem Wahrheitswertverlauf eine passende KNF gibt.