Aufgabe:
1. Sei v(A) die Anzahl der Variablen, die in der Satzformel A vorkommen, k(A) die Anzahl der Klammerpaare in A, op(A) die Anzahl der Operatoren in A und bop(A) die Anzahl der binären Operatoren in A.
Diese Funktionen können rekursiv über die Struktur der Formeln definiert werden, wobei * einen beliebigen binären Operator aus der Menge {∧, ∨, →, ↔} bezeichnet.
v(pi) = 1 ; v(¬A) = v(A) ; v(A*B) = v(A) + v(B)
k(pi) = 0 ; k(¬A) = 1 + k(A) ; k(A*B) = 1 + k(A) + k(B)
op(pi) = 0 ; op(¬A) = 1 + op(A) ; op(A*B) = 1 + op(A) + op(B)
bop(pi) = 0 ; bop(¬A) = bop(A) ; bop(A*B) = 1 + bop(A) + bop(B)
Sei F die Menge aller Aussagenformeln. Beweisen Sie die folgenden Aussagen mit Hilfe struktureller Induktion über die Struktur von Aussagenformeln:
Jede Aussagenformel A ∈ PROP enthält die gleiche Anzahl von Klammerpaaren und Operatoren: k(A) = op(A)
2. Zeigen Sie unter Verwendung der Definitionen aus der vorherigen Übung Folgendes:
a) Sei n die Anzahl der Variablenvorkommen in A ∈ F. Dann ist die Anzahl der Operatoren in A mindestens n - 2:
op(A) ≥ v(A) - 2
b) In einer Formel gibt es immer eine Variable mehr als binäre Operatoren: v(A) = 1 + bop(A)
Problem/Ansatz:
Leider fehlt mir hier der Ansatz, wie ich die Aufgaben mit struktureller Induktion lösen kann. Ich würde mich sehr über jegliche Hilfe freuen.
