Logik at TU Kaiserslautern

Rekursive Datentypen sind Mengen von Objekten, welche mittels Rekursion definiert sind.

Beispiele: Strings, nichtnegative Zahlen, Bäume, logische Formeln

1. Es gibt Basisfälle, z.B. bei Strings gilt:

ε ∈ Σ* (leeres Wort ist ein String)

2. Hinzu kommt ein induktiver Fall / eine induktive Regel, z.B. bei Strings:

a ∈ Σ und s ∈ Σ* ⇒ <a,s> ∈ Σ* (Buchstabe a aus Alphabet Σ kann als Präfix an beliebigen String s ∈ Σ* angehängt werden und das Ergebnis ist wieder ein String)

Implizit: Ein rekursiver Datentyp ist eine Menge an Objekten, die aus einem Basisfall und allen mittels induktiver Regel daraus ableitbaren Objekten besteht.

Basisfall: ε • ε = ε

Induktiv:

Lassen wir nun o.B.d.A die Aussage für ein beliebiges, aber festes s ∈ Σ* gelten.

Betrachte nun

z • ε  = z ∈ Σ*  mit z := <a,s> , a ∈ Σ.

Es gilt mit der Definition von String-Konkatenation

<a,s> • ε = <a, s • ε >

Mit der Induktionsvoraussetzung gilt nun

<a, s • ε > = <a, s> = z

und somit gilt insgesamt

z • ε = z.

Da die Eigenschaft für alle Basisfälle gilt und induktiv weiter gilt, wenn wir einen Buchstaben hinzufügen, gilt sie für alle Strings und somit auch für jede mögliche String-Konkatenation, also

s • ε = s,∀ s∈Σ*

Eine aussagenlogische Formel φ ist eines der folgenden Dinge:

1. Eine Variable x
2. Eine Konstante, also ⊤ oder⊥.
3. Einer der folgenden Ausdrücke:

¬φ1 oder (φ1 ∧ φ2)  oder (φ1∨ φ2)

für aussagenlogische Formeln φ1, φ2.

Wahrheitswertetabelle

• Implikation: (φ → ψ) := (¬ φ ∨ ψ)
• Äquivalenz: (φ ↔ ψ) := (φ → ψ) ∧ (ψ → φ)

Eine Formel φ nennen wir erfüllbar, wenn es eine Belegung/Interpretation I(φ) gibt, sodass gilt

I(φ) = 1.

Eine Formel φ nennen wir unerfüllbar, wenn es keine Belegung/Interpretation I(φ) gibt, sodass gilt

I(φ) = 1,

bzw wenn für jede Belegung/Interpretation I(φ) gilt

I(φ) = 0.

Ja, eine Formel φ und ihre Negation ¬φ können beide erfüllbar sein.

Beweis: Es reicht zu zeigen, dass wir für eine beliebige Formel φ und ihre Negation ¬φ  Belegungen/Interpretationen finden, welche diese erfüllen:

• Betrachte φ = p
• Es gilt also: ¬φ = ¬p

Wir wissen nun, dass für I(p) = 1 gilt I(φ) = 1 und dass für I(p) = 0 gilt I(¬φ) = 1.

q.e.d.