MGMIT - Zusammenfassung PDF

Preview

Summary

Download MGMIT - Zusammenfassung PDF

Description

MGMIT Quantoren Der erste Quantor kommt auch in der Aussage zu erst.

Zusammenfassung Logik 1.

hat die stärkste Bindung

2.

bindet stärker als

3.

bindet stärker als

4.

bindet stärker als

Gesetze Absorption bei Konjunktion und Disjunktion

Kommutativität bei Konjunktion und Disjunktion

Assoziativität bei Konjunktion und Disjunktion

Distributivität

Doppelte Verneinung Identitätsgesetz und und Ausgeschlossene Dritte

Regeln von de Morgan bei der Negation einer Konjuktion bzw. Disjunktion

Kontraposition Weitere Regeln

Formen der Aussagen Negations Normalform (NNF) Wenn alle Negationen in Literalen (vor Aussagenvariabelen) vorkommen und keine Implikationen (

) oder Äquivalenzen (

) vorkommen.

Disjunktiver Normalform (DNF) Darf Literalen beinhalten Konjuktiver Normalform (KNF)

Darf Literalen beinhalten Achtung: Wenn DNF oder KNF, ist es automatisch NNF ist beides, da man die Klammern verschieden setzen kann. Für jede aussagenlogische Formel gibt es logisch äquivalente Formeln in NNF, KNF und DNF. 1. Eleminieren von Äquivalenzen (

) durch Regel

2. Eleminieren von Implikationen (

) durch Regel

3. Eliminieren der Negationen, die nicht zu einem Literal gehören. (De Morgan oder doppelte Negation Regel)

Prädikate und Quantoren Quantoren ist wahr für alle (mindestens) ein

aus der Grundmenge

aus der Grund Menge

:

Es existiert

, so dass

wahr ist:

Vertauschregel Sei

ein Prädikat. Dann gelten die Äquivalenzen:

Achtung: Sind die Quantoren ungleich, dann ist die Reihenfolge der Quantoren wichtig. Di folgende Äquivalenz gilt im Allgemeinen nicht. Beispiel:mit bedeutet: für alle

gibt es ein

so dass

bedeutet: Es gibt ein , so dass für all

gilt:

Die beiden Aussagen sind nich logisch äquivalent.

Negationsregel

Ausklammerungsregel

Achtung:

Beweistechniken Direkte Beweise Bei einem direkten Beweis einer mathematischen Aussage

wird das Problem direkt und ohne

Umwege angegangen.

Vorlage Aussage: Wenn Beweis:

und

ungerade natürliche Zahlen sind, dann ist die Differenz

gerade

& ist gerade.

Beweis durch Widerspruch Um

zu zeigen, nimmt man die negierte Aussage

als wahr an. Wenn die negierte Aussage

wahr ist, ist dies ein Widerspruch. Somit wäre die Aussage ist wahr

ist falsch Wenn

wahr ist

falsch.

Widerspruch.

Beweis durch Kontraposition Um

zu zeigen, kann man durch die Regeln auch

beweisen.

Beweis einer Äquivalenz Hier wollen wir eine Aussage von der Form der Formel

zeigen. Diese Aussage ist logisch äquivalen zu

. Dabei können verschieden Techniken für die jeweilige

Seite verwendet werden.

Vorlage Aussage:

Beweis: direkt beweisen

durch Kontraposition beweisen ist ungerade

Mengenlehre : Menge der natürliche Zahlen : Menge der ganzen Zalen : Menge der rationalen Zahlen. Das heisst, die Menge der Brüche mit : Menge der reelen Zahlen. Beinhalten Zahlen welche nicht als Bruch dargestellt werden können z.B. oder

: leere Menge

Notation für Mengen

Mächtigkeit / Kardinalität

Definition Teilmenge (

Teilmenge von

)

Dies bedeutet also, dass jedes Element von (

echte Teilmenge von

auch in

enthalten ist.

)

Hier betont man, dass die Menge von

nicht identisch zu

ist, aber

in

ist. Für alle Mengen gilt:

und

Potenzmenge Die Potenzmenge einer Menge mit

Elemente enthält

Elemente (Mächtigkeit der

Potenzmenge).

Operationen mit Mengen Schnittmenge

Vereinigungsmenge

Rechenregeln der Vereinigung und des Durchschnittes

enthalten

Kommutativität

Assoziativität

Distributivität

Idempotenzgesetz

Einschliessungseigenschaft Charakterisierung der Teilmengenbeziehung

Differenzmenge Die Differenzmenge in

aber nicht in

oder

der beiden Mengen

ist die Menge der Elemente, die

enthalten sind.

Symmetrische Differenz Es handelt sich um die Menge aller Elemente, die jeweils in einer, aber nicht in beiden Mengen liegen, also ohne Schnittmenge.

Eigenschaften der Mengendifferenzen 1. 2. 3.

Komplement Ist

eine Teilmenge von

, so nennt man die Differenzmenge

(oder die Ergänzungsmenge) von

in

auch das Komplement

und schreibt dafür

Eigenschaften des Komplements Es sei

eine Grundmenge. Für alle Teilmenge

und

von

gelten:

Komplementgesetze

Regel von de Morgan:

Partitionen Sei

eine Menge. Dann heisst Die Teilmenge in

eine Partition oder Zerlegung von

, wenn gilt:

sind nicht leer:

Die Vereinigung der Teilmengen in

ist

:

Die Elemente einer Partition werden Blöcke der Partition genannt. Beispiel:

Kartesisches Produkt gelesen: A kreuzt B.

Mächtigkeit des Produkts

, somit ergibt sich die Mächtigkeit das kartesischen Produkts von

:

Grössenvergleiche von unendlichen Mengen Eine Menge einer in

heisst abzählbar, wenn zu

existiert, also kann zu jeder Zahl von

zu

zuweisen.

Eine abzählbare nicht endliche Menge heisst abzählbar unendlich. Ist eine unendliche Menge nicht abzählbar, dann heisst sie überzählbar. Eine Menge wenn

gleich mächtig sind d.h.

Relationen Definitionen auf die Menge

ist genau dann abzählbar unendlich

Das offene Interval ]0,1[={0...