Schachtelungstiefe von Formeln als rekursive Funktion definieren

Question

Aufgabe:

Hinweis:

Die Schachtelungstiefe ist die maximale Anzahl ineinander verschachtelter Klammern in
einer Formel. Z.B. hat die Formel ((A ∨ (B ∧ ¬C)) ∨ (D → A)) eine Schachtelungstiefe von 3.

Definieren Sie die Schachtelungstiefe als rekursive Funktion

Problem/Ansatz:

hallo,

ich weiß nicht genau wie ich die Aufgabe lösen soll. Meine Angehensweise war das ich für beliebige Formel Fm folgendes definiert hab:

0(Fm) .= # öffnende Klammern in Fm

S(Fm) .= # schließende Klammer in Fm

Dann wollte ich durch die Anzahl der öffnenden und schließenden Klammern diie Verschachtelung bestimmen bin aber leider nicht meher weiter gekommen.

Wäre euch über jede Hilfe dankbar:)

LG

Answer 1

Definieren Sie die Schachtelungstiefe als rekursive Funktion

Die Syntax der Aussagenlogik wurde auch rekursiv definiert, ungefähr so:

1. Jede Variable ist eine aussagenlogische Formel.
2. Sind F und G aussagenlogische Formeln, dann sind auch
   • (F ∨ G)
     
   • (F ∧ G)
     
   • (F → G)
     
   • ¬F
   aussagenlogische Formeln.
3. Keine weiteren Ausdrücke sind aussagenlgische Formeln.

Für die Verschachtelungstiefe \(t(F)\) einer aussagenlogischen Formel \(F\) gilt dann

        \(t(F)=\begin{cases} 0 & \text{falls } F \text{ eine Variable ist}\\ 1+\max\left(t(G)+t(H)\right) & \text{falls }F=\left(G\circ H\right) \text{mit }\circ\in\{\vee,\wedge,\to\} \text{ ist}\\ t(G) & \text{falls }F=\neg G \text{ ist} \end{cases}\)