Maria Oelinger. Schaltungen und Boolesche Algebra (11)

http://www.oelinger.de

Home Maria Oelinger
zurück zur Übersicht     Teil I Teil II Teil III Teil IV

1.4 Schaltnetze – Teil IV

Satz zu DAG
Ein nichtleerer azyklischer gerichteter Graph (ADG) G = (V, E) mit | V | = n > 1 hat mindestens einen Input und einen Output.

Beweis: Dirichletscher Schubfachschluss
Beginne in einer Ecke und nimm an, dies sein kein Input.
Also existiert eine Vorgängerecke. Ist sie Input, dann Ende, sonst wiederhole.
Nach maximal n Versuchen hat man Input oder Kreis.
Azyklischer Graph vorausgesetzt, also Input.

Output analog mit Nachfolger statt Vorgänger.

Partielle Ableitung f: BⁿB sei Boolesche Funktion. Dann ist die partielle Ableitung gebildet gemäß:

f (x_i | a) := f (x₁, …, x_i-1, a, …, x_n)

f_{x_i}: B^n-1B     mit     f_{x_i} := f (x_i | 0)  f (x_i | 1)

Es gilt:

f_{x_i} = 0    für alle x_i, von denen f nicht abhängt

(f  g)_{x_i} = f_{x_i}  g_{x_i}

Ableitungen konstanter Funktionen sind immer Null

f_{x_i|x_j} = f_{x_j|x_i}

(f • g)_{x_i} = f g_{x_i} f_{x_i} g  f_{x_i} g_{x_i}

weiter...

zurück zur Übersicht
Feel free to send me email: maria@oelinger.de

© 2000 Maria Oelinger
cand. math. Schaltungen und Boolesche Algebra (11) Letzte Änderung: 19.11.2000
address: http://www.oelinger.de/maria/schalt/schalt11.htm