1.Aussagenlogik

1.1 Gleichwertiges Kalkül

Diskrete Mathematik-LMLPHP

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

Diskrete Mathematik-LMLPHP

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:

Diskrete Mathematik-LMLPHP

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

Diskrete Mathematik-LMLPHP

Beispiel

Diskrete Mathematik-LMLPHP

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

Diskrete Mathematik-LMLPHP

Wir setzen Graph G=<V,E> als gerichtete Graph voraus,V={v1,v2,...,Vn},|E| = m

Diskrete Mathematik-LMLPHP

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

Diskrete Mathematik-LMLPHP

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

Diskrete Mathematik-LMLPHP

4.3 Martrix des Graph

4.3.1 Assoziationsmatrix

Beispiel

Bei ungerichtetem Graph

Diskrete Mathematik-LMLPHP

Diskrete Mathematik-LMLPHP

Bei gerichtetem Graph

Diskrete Mathematik-LMLPHP

Diskrete Mathematik-LMLPHP

4.3.2 Adjazenzmatrix

Bei gerichtetem Graph

Diskrete Mathematik-LMLPHP

Diskrete Mathematik-LMLPHP

4.4 Kürzester Pfad

4.4.1 dijkstra Algorithmus

Diskrete Mathematik-LMLPHP

Wir verwenden Menge S als aktuell kürzester Pfad,Menge U als Pfadmöglichkeiten

Diskrete Mathematik-LMLPHP

5.Baum

5.1 Huffman Algorithmus

W(Baum) = Die Summe des Verzweigungspunkt

Diskrete Mathematik-LMLPHP

W(Baum) = 42

05-11 12:50