TI05

Technische Informatik
Sommersemester 2026
[Name], [Name]
Übungsblatt 05
05.06.2026

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

2a) Schaltkreis zeichnen

Grafik ich nicht hinbekommen. Die Gatter sind:

2b) Symbolische Simulation

Wir berechnen für jeden Gatterausgang die boolesche Funktion in Abhängigkeit der Eingänge .

: (AND aus und )

: (XOR aus und )

: (AND aus und )

: (XOR aus und — entspricht einer Paritätsschaltung)

:

Die Ausgänge sind und .

realisiert eine Paritätsfunktion (1 wenn eine ungerade Anzahl Eingänge 1 ist). realisiert einen Volladdierer-ähnlichen Ausdruck: ist der Übertrag, wenn , und ist der Übertrag, wenn genau einer von 1 ist und — also der Carry eines Volladdierers.

Wir zeigen, dass die Belegung eindeutig ist, wenn der Graph azyklisch ist. Dafür beweisen wir die drei Teilaussagen.

4a) Jeder azyklische Graph hat mindestens eine Wurzel

Zu zeigen: Ein gerichteter, azyklischer Graph besitzt einen Knoten ohne eingehende Kanten (Wurzel).

Beweis durch Widerspruch:

Angenommen, hätte keine Wurzel, d.h. jeder Knoten hat mindestens eine eingehende Kante. Dann können wir durch Rückwärtsverfolgung einen unendlichen Pfad konstruieren:

Beginne bei einem beliebigen Knoten . Da er eine eingehende Kante hat, existiert ein mit . Auch hat eine eingehende Kante, also existiert mit , usw. Da endlich ist, muss sich irgendwann ein Knoten wiederholen ( mit ). Die Kanten bilden dann einen Zyklus () — Widerspruch zur Azyklizität von . Also hat mindestens eine Wurzel.

4b) Topologische Sortierung für azyklische Graphen

Zu zeigen: Für jeden azyklischen Graphen gibt es eine topologische Sortierung, d.h. eine bijektive Abbildung

mit (der Startknoten jeder Kante erhält eine kleinere Nummer als der Endknoten).

Beweis:

Wir verwenden die Aussage aus 4a).

Induktionsbasis: . Ein einzelner Knoten hat trivialerweise eine topologische Sortierung: .

Induktionsschritt: Gelte die Behauptung für alle azyklischen Graphen mit . Sei azyklisch mit .

Nach 4a) hat eine Wurzel (keine eingehenden Kanten). Entferne und alle von ausgehenden Kanten. Der resultierende Graph ist ebenfalls azyklisch (ein Zyklus in wäre auch ein Zyklus in ).

Nach Induktionsvoraussetzung hat eine topologische Sortierung . Definiere

ü

Da keine eingehenden Kanten hat, ist jede Kante mit unmöglich. Für alle anderen Kanten gilt , da die relative Ordnung aus erhalten bleibt und alle Knoten in um 1 verschoben wurden.

Also existiert eine topologische Sortierung für . Durch vollständige Induktion folgt die Behauptung für alle azyklischen Graphen.

4c) Eindeutigkeit von bei topologischer Sortierung

Zu zeigen: Mit einer topologischen Sortierung von ist die Belegung eindeutig bestimmt.

Beweis durch vollständige Induktion über :

Induktionsbasis ():

Der einzige Knoten ist entweder ein Eingang , eine Konstante 0 oder 1, oder ein Gatter ohne Eingänge (nicht sinnvoll). In allen Fällen ist durch die Definition eindeutig festgelegt:

Induktionsvoraussetzung:

Für jeden azyklischen Schaltkreis mit Knoten ist eindeutig bestimmt.

Induktionsschritt ():

Sei azyklisch. Nach 4b) existiert eine topologische Sortierung . Sei der Knoten mit , also der „letzte" Knoten in der Sortierung.

Da für alle Vorgänger von gilt, haben alle Knoten für Kanten mit eine kleinere Nummer. Diese Knoten bilden eine Menge mit .

Betrachte den induzierten Schaltkreis mit Knotenmenge . Da azyklisch ist, ist auch azyklisch. Nach Induktionsvoraussetzung ist auf eindeutig bestimmt.

Für gilt nach Definition:

wobei und . Da alle in liegen, sind deren -Werte bereits eindeutig bestimmt. Also ist auch eindeutig.

Somit ist auf ganz eindeutig bestimmt. Durch vollständige Induktion folgt die Behauptung für alle azyklischen Schaltkreise.