TI01-2

Technische Informatik
Sommersemester 2026
[Name], [Name]
Übungsblatt 01
30.04.2026

Ich habe die Aufgaben selbst versucht zu lösen und möchte ein Korrektur.

a) Prinzip der Dualität

Da alle Gesetze der Boolschen Algebra laut Definition zu und symmetrisch sind, z.B.:

sind Fälle ohne 0 und 1 trivialerweise korrekt.

Da und sind Aussagen mit 0 und 1 dann korrekt, wenn 0 und 1 getauscht werden, da eine Anwendung der Dualitätsregel der Definitionen in der jeweils anderen resultiert.

ä

b)

Es gilt zu zeigen, dass für die Absorption & Komplementregel der in der Vorlesung vorgestellten Axiome von boolschen Algebren erfüllt.

i) Absorption

:

Fall 1 :

Fall 2 :

:

Fall 1 :

Fall 2 :

ii) Komplementregel

:

Fall 1 :

Fall 2 :

Fall 3 :

Fall 4 :

a) Es gilt zu zeigen, dass

b) Es gilt zu zeigen, dass

a)

Ich definiere für einen Binärbaum der Höhe die Anzahl der Knoten des Baumes als .

Zu beweisende Aussage:

Basisfall (): Ein Binärbaum der Höhe besteht aus genau einem Knoten (einem Blatt).

Induktionsvoraussetzung (IV): Für einen beliebigen aber festen Binärbaum der Höhe gelte:

Induktionsschritt ():

Sei ein Binärbaum der Höhe . Nach der rekursiven Definition besteht er aus einer Wurzel mit einem oder zwei Kindteilbäumen. Jeder Kindteilbaum hat Höhe höchstens , also gilt nach IV für jeden Kindteilbaum: .

Da die Wurzel maximal zwei Kinder hat, ergibt sich:

Schlussfolgerung: Da die Aussage für gilt und der Induktionsschritt zeigt, dass sie für gilt wenn sie für gilt, folgt durch strukturelle Induktion über die Baumstruktur:

b)

Bei der Vorlesungsdefinition würde man über die Anzahl der Knoten induzieren.