Hallo!

Ich hatte heute mit meinem Übungsleiter im Fach "Automatentheorie und formale Sprachen" einen netten Diskurs über die Berechenbarkeit der Anzahl möglicher Klammerungen innerhalb eines Ausruckes in einer Prädikatenlogik.

Der Test-Ausdruck sieht so aus:
~p & q -> r
Legende:
~ = negiert, einstelliger Junktor
& v -> = zweistellige Junktoren, sind gleichwertig
() = Klammern

Wieviele Klammerungsmöglichkeiten gibt es nun?
Meines Wissens diese hier:
~(p) & (q -> r)
~(p & q) -> r
~(q & q -> r)
~(q & (q -> r))
~((q & p) -> r)

Habe ich welche vergessen / was falsch gemacht?
Bitte korrigieren!
Jedenfalls will ich darauf hinaus, dass es 5 Möglichkeiten der Klammerung gibt.

Jetzt suchen wir nach der Formel zur Berechnung der Anzahl möglicher Klammerungen.

Mein Vorschlag:
Die Anzahl Möglichkeiten ergibt sich aus
a) allen Kombinationsmöglichkeiten der 2stelligen Junktoren innerhalb des gegebenen Ausdrucks (wie lautet der mathemantische Ausdruck dafür?)
b) zuzüglich (ergo +) der Anzahl der Prädikate (p,q,r) rechts vom Einstelligen Junktor
c) zuzüglich b) für alle weiteren einstelligen kunktoren, wobei immer nur die Prädikate rechts vom und ab dem aktuellen einstelligen Junktor gezählt werden.

Bei unseren Testläufen hat sich diese Vorgehensweise als zuverlässig erwiesen (hatten nur Zeit für 3 Läufe).
Wie aber kann man das mathematisch ausdrücken?
Weil, so wie oben ausgedrückt erweist sich das für eine Formelsammlung als ziemlich unpraktisch und fehl am Patz.

mfg pktm

EDIT:Typo\n\n

<!--EDIT|pktm|1105654889-->