Logik:Klausuren/08.02.2003/2.2 Aufgabe

1. Aufgabenstellung

a) Definieren Sie eine rekursive Funktion $ h\; $, die die Anzahl der in einer aussagenlogischen Formel enthaltenen binären Junktoren bestimmt.

b) Bezeichne $ r(F)\; $ den Rang einer aussagenlogischen Formel $ F\; $ und $ h(F)\; $ die Anzahl der binären Junktoren in $ F\; $. Beweisen Sie mit struktureller Induktion, dass für jede aussagenlogische Formel F in Negationsnormalform, die nur die Junktoren $ \and ,\or ,\neg\; $ enthält, die Gleichung $ r(F) = h(F)\; $ gilt.

2. Lösung

a)

$ h(F)=\begin{cases} 0 & \mbox{wenn F atomar} \\ h(G) & \mbox{wenn F der Form } \neg\mbox{G} \\ h(G) + h(H) +1 & \mbox{wenn F der Form (G}\circ\mbox{H)} \end{cases} $

b)

Zu zeigen: $ r(F) = h(F)\; $

1. Induktionsanfang

$ F\; $ ist ein Atom
$ r(F)\; $ für Atome explizit definiert mit 0
$ h(F)\; $ für Atome explizit definiert mit 0
es gilt: $ r(F) = h(F) = 0\; $

2. Induktionsschritt

Voraussetzung:
$ r(F) = h(F)\; $ und
$ r(G) = h(G)\; $ gilt.
$ F\; $ und $ G\; $ aussagenlogisch Formeln in Negationsnormalform.

a) Gilt auch $ r(\neg F) = h(\neg F)\; $) ?
$ r(\neg F) = r(F) $, nach Definition, und weil $ F\; $ in Negationsnormalform
$ h(\neg F) = h(F $), nach Definition
Nach Vorraussetzung gilt also:
$ r(\neg F) = r(F) = h(F) = h(\neg F) $

b) Gilt auch $ r(F \circ G) = h(F \circ G) $ ?
$ r(F \circ G) = r(F) + r(G) + 1 $, nach Definition
$ h(F \circ G) = h(F) + h(G) + 1 $, nach Definition
Nach Vorraussetzung gilt also:
$ r(F \circ G) = r(F) + r(G) + 1 = h(F) + h(F) + 1 = h(F \circ G) $

4. Alternativen/Diskussion/Hinweise etc.

---

zur Klausur 08.02.2003
Aufgaben-Kategorie InduktionAufgaben-Kategorie Rekursion