1.Aussagenlogik
1.1 Gleichwertiges Kalkül
1.2 Normalform
Einfache Disjunktion besteht aus Disjunktion endlicher Aussagensvariable order deren Negation
Einfache Konjunktion besteht aus Konjunktion endlicher Aussagensvariable oder deren Negation
Disjunktive Normalform besteht aus Disjunktion endlicher einfache Konjunktion
Konjunktive Normalform besteht aus Konjunktion endlicher einfache Disjunktion
Als Minimale Aritikel bezeichnen wir einfache Konjunktion
2.Menge
2.1 Das Begriff der Menge
Eine Menge ist ein Verbund, eine Zusammenfassung von einzelnen Elementen
N Tupel Menge hat 2 Teilmenge
2.2 Grundlegend Rechnung der Menge
Menge Berechnungsformel:
3.Binäre Beziehung
3.1 Kartesisches Produkt
Kartesisches Produkt:Wir setzen A,B als Menge voraus,wir benutzen A als erstes Element,B als zweites Element,dann sie setzen geordenetes Paar zusammen.Als A×B werden wir verzeichnen
A×B = {<x,y>|x∈A∩y∈B}
Beispiel:A={a,b},B={0,1,2}
Ergebnis der A×B ist
A×B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}
Ergebnis der B×A ist
B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}
Eigenschaften:
Kartesisches Produkt kann Kommutativgesetz und Assoziativgesetz nicht entsprechen,aber Distributivgesetz entsprechen
3.2 Berechnung der Menge
Difinitionsmenge:domR = {x|∃y(<x,y>∈R)}
Wertebereich:ranR= {y|∃x(<x,y>∈R)}
Gebiete:fldR = domR∪ranR
Beispiel
4.Graph
4.1 Ungerichtete Graph und gerichtete Graph
Graph G ist eine zwei Tupel <V,E>
V ist eine nicht leer endliche Menge,deren Teilmenge bezeichnen wir als Knoten
E ist eine Kantenmenge,deren Teilmenge bezeichnen wir als Kante
Es gibt nur eine Knoten,ohne Kante,bezeichnen wir es als trivial Graph
Bei ungerichtetem Graph,bezeichnen wir Knoten v,der als Endpunkt besetzt,als Grad
Bei gerichtetem Graph,bezeichnen wir Knoten,der als Startpunkt besetzt,Ausgangsgrad,als d(v);
bezeichnen wir Knoten,der als Endpunkt besetzt,als Eingangsgrad,als d(v)
Händeschüttelngesetz:Wir setzen Graph G=<V,E> als ungerichtete order gerichtete Graph voraus,V={v1,v2,...,Vn},|E| = m
Wir setzen Graph G=<V,E> als gerichtete Graph voraus,V={v1,v2,...,Vn},|E| = m
Beim ungerichtete Graph,der ungerichtete Kanten,der hängt mit ein Paar Knoten,großer als eins,bezeichnen wir ihn als parallel Kante
Beim gerichtete Graph,der Kanten,deren Startpunkt und Endpunkt gleich sind,bezeichnen wir sie gerichteten als parallel Kante
Einfaches Graph,ohne parallel und Kreis
G'⊆G und V'=V,bezeichnen wir G' spanning Teilgraph des G
4.2 Weg,Kreis und Anschlussmöglichkeit des Graphs
Wenn jede Kante nur ein Mal vorbeigegangen ist,bezeichnen wir es als einfachen Weg;Wenn v= v,bezeichnen wir es als einfachen Kreis
Wenn jeder Knoten nur ein Mal vorbeigegangen ist,bezeichnen wir es als primär Weg;Wenn v= v,bezeichnen wir es als primär Kreis
Beispiel
Bei einem ungerichtete Graph G,es besteht aus Weg zwischen u und v,bezeichnen es wir als "u und v ist zusammenhängend"
Bei einem ungerichtete Graph G oder trivial Graph G sind beliebig zwei Knoten zusammenhängend,bezeichnen wir es als verbundenes Graph,sonst als nicht verbundenes Graph
Bei einem gerichtete Graph D ignorieren wir alle Richtung der Kanten,bekommen wir gerichtete Graph,das zusammenhängend ist,bezeichnen wir es als schwach verbundenes Graph
Wenn beliebige Knoten des D am mindestens von einem Knoten nach anderem erreichen kann,bezeichnen wir es als einseitig verbundenes Graph
Wenn beliebige Knoten des D von einem Knoten nach anderm erreichen kann,bezeichnen wir es als stark verbundenes Graph
4.3 Martrix des Graph
4.3.1 Assoziationsmatrix
Beispiel
Bei ungerichtetem Graph
Bei gerichtetem Graph
4.3.2 Adjazenzmatrix
Bei gerichtetem Graph
4.4 Kürzester Pfad
4.4.1 dijkstra Algorithmus
Wir verwenden Menge S als aktuell kürzester Pfad,Menge U als Pfadmöglichkeiten
5.Baum
5.1 Huffman Algorithmus
W(Baum) = Die Summe des Verzweigungspunkt
W(Baum) = 42