0 Daumen
395 Aufrufe

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:

Avatar von

1 Antwort

0 Daumen

\(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}\)

Avatar von 5,6 k

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community