Aussagenlogik: Syntax und Semantik

Question

Frage:

Definieren Sie mittels einer rekursiven Definition eine Funktion l : LAL → ℕ, die die Länge einer Formel zum Ergebnis hat. Z.B. soll l((A∧¬B)) = 6 sein. Es soll also jedes vorkommende Symbol gezählt werden. (Dabei sind Klammerersparnisregeln nicht erlaubt. Wir schreiben also stets (A ∧ B) und nicht A ∧B.) Beweisen Sie dann mittels struktureller Induktion, dass für alle Formeln F der Aussagenlogik gilt

1+ tiefe (F) ≤ L(F)
Code:

Answer 1

\(l(F) = \begin{cases}1 & \text{falls $F$ eine Variable ist}\\1 + l(F') & \text{falls $F$ von der Form $\neg F'$ ist}\\\dots & \text{falls $F$ von der Form $(F'\wedge F'')$ ist}\\\vdots & \vdots\end{cases}\)

Comments

Können Sie bitte Ihre Lösung erklären, hab nicht verstanden, wie Sie gemacht haben

---

Es gibt nur endlich viele Möglichkeiten, eine Formel aus anderen Formeln zusammenzubauen:

1. Die Formel ist überhaupt nicht zusammengebaut, sondern besteht aus einer einzigen Variable
2. Indem man der Formel ein \(\neg\) voranstellt
   
3. Indem man zwei Formeln mit einem \(\wedge\) oder \(\vee\) verbindet
4. Weitere Möglichkeiten findest du gegebenenfalls in deiner Definition Syntax der Aussagenlogik
   

Für jede dieser Möglichkeiten musst du angeben, wie man die Länge der Formel aus den Längen der Teilformen berechnet.

Ich habe das in meiner Antwort exemplarisch für 1. und 2. gemacht. Du musst das noch für 3. und gegebenfalls weitere Möglichkeiten machen.

---

Wir sieht der Beweis aus?

Beweisen Sie dann mittels struktureller Induktion, dass für alle Formeln F der Aussagenlogik gilt
1+ tiefe (F) ≤ L(F)

---

Bestimme die Funktion

        \(d(F) = L(F) - \operatorname{tiefe}(F)\).

Zeige dass \(d(F)\geq 1\) für jede Formel \(F\) gilt.

---

Wir sieht der Beweis aus?

Beweisen Sie dann mittels struktureller Induktion, dass für alle Formeln F der Aussagenlogik gilt
1+ tiefe (F) ≤ L(F)

Was bedeutet tiefe hier?

---

Was tiefe bedeutet, steht in deinen Unterlagen.