ZF - Zusammenfassung Logik und Diskrete Strukturen PDF

Preview

Summary

Warning: TT: undefined function: 32 Logik und Diskrete Strukturen Zusammenfassung:I Aussagenlogik Teil 1:Abzählbare Menge: - Wenn es eine Surjektion N --> S gibt - S können also durchnummeriert werdenAufzählbare Menge: - Wenn ein Alg. „aufS“ existiert der: - aufS hat nat. Zahl als Argument - ...

Description

Logik und Diskrete Strukturen Zusammenfassung: I Aussagenlogik Teil 1: Abzählbare Menge: - Wenn es eine Surjektion N --> S gibt - S können also durchnummeriert werden Aufzählbare Menge: - Wenn ein Alg. „aufS“ existiert der: - aufS hat nat. Zahl als Argument - aufS (i) terminiert für jedes i - aufS (i) liefert als Erg. Ein Element aus S - für s e S gibt es mind. Ein i e N, so dass aufSS (i) das Element s als Erg. Liefert Junktoren:

Signatur einer Sprache L

Aussagenvariablen => nullstellige Relationssymbole oder nullstellige Prädikatssymbole => Atom (kann nicht weiter aufgespalten)

1

Strukturelle Induktion:

II Aussagenlogik Teil 2: Eindeutigkeitssatz:

Wahrheitstabelle:

2

-

die Semantik der aussagenlog. Formel F"="((a"∧"b)"⇒"c)"" Eine Zeile der WT, in der F wahr ist => Modell von F Wenn F immer W ist in allen Interpretationen => Allgemeingültig

Zeilenanzahl: (n=Anzahl der Aussagevariablen) 2n (+1) = Zeilen in der WT Obere => 23 +1 = 9 F = ((a ∧ b) ⇒ (c ∨ d)) ð 24 + 1 = 17 Spaltenanzahl: ð Anzahl der Aussagenvariablen ð Anzahl der Teilformeln F = ((a ∧ b) ⇒ (c ∨ d)) ð 7 F = (a ∧ b) => erfüllbar wenn eine Interpretation in F wahr ist F = (a ∧ b) => falsifizierbar wenn eine Interpretation in F falsch ist F = (a ∧ ¬a) => ist in ALLEN Interpretationen falsch => unerfüllbar (F ⇒ ⊥) ist genau dann wahr, wenn ¬F wahr ist. (logisch äquivalent)

Folgerung. Aus F folgt G: F |="G wenn jede Interpretation, die F erfüllt, ebenfalls G erfüllt

a |="(b ⇒"a)" " " " " "

"

3

Ersetzungssatz:

è strukturelle Induktion

III Prädikatenlogik Teil 1: è Gleiche Junktoren wie Sprache der Aussagenlogik è ABER bietet sprachliche Mittel zur Darstellung der inneren Struktur Elementare Aussagen: (neben ⊥ und ⊤) Terme: Repräsentation von Objekten Relationssymbole: Eigenschaften/Beziehungen von Objekten Quantoren: ∀ „für alle“ und ∃ „es gibt“

4

Signatur einer Sprache: 1. RelnL"von n-stelligen Relationssymbolen (0-stellige => Aussagevariablen) => Verben 2. FunnL"von n-stelligen Funktionssymbolen (0-stellige => Konstanten) è Terme aus Konstanten, Variablen und Fktsymbolen => Subjekten und Objekten einer nat. Sprache

Freie/gebundene Variablen

=> x kommt frei vor

=> x kommt gebunden vor

5

Term ohne Variable => Grundterm oder geschlossener Term Formel ohne Variable => Grundformel (s(a) ∨ t(b)) (Atomare Grundformeln => Grundatome) ∃x (s(x) ∨ t(x)) Formel ohne FREIE Variable => geschlossene Formel Interpretation einer Sprache L: ð Interpretiert die Signatur von L - Terme und Variablen => nicht leere Menge (Universum) int. - 1-stellige Relsymbole => 1-stellige Relsymbole (Teilmenge des Universums) int. - n-stellige Relsymbole => n-stellige Telsymbole über das Universum interpretiert

BSP:

a,b,cM => Variable; sM => Konstante

6

Umgebung: D-Umgebung (D-Belegung) nicht leere Menge D in einer Fkt U, die jeder Variablen x einen Wert U(x) e D zuordnet. U : Var → D

Modellbezeichnung:

-

M erfüllt L-Formel F (oder M (Modell von F)) gdw. M |= F => sonnst M falsifiziert |≠ F L-Formel allgemeingültig gdw. sie jeder von L-Interpret. erfüllt wird L-Formel erfüllbar gdw. sie von einer L-Interpret. erfüllt wird L-Formel falsifizierbar gdw. sie von einer L-Interpret. falsifiziert wird L-Formel unerfüllbar gdw. sie von jeder L-Interpret. falsifiziert wird F und G logisch äquivalent F|=|G gdw. F|= G und G|= F Aus F folg G (Folgerung) gdw. F erfüllt ebenfalls G erfüllt

IV Prädikatenlogik Teil 2: Normalform: Rektifizierte Formel, Pränexform, Skolemform, Konjunktive Normalform, Klauselnormalform. - Wichtige Eigenschaften (Äquivalenz (Un-)Erfüllbarkeiten) Erhalten - Das Schließen/sonstige Aufgaben erleichtern Rektifiziert - Wenn Var. Die unmittelbar hinter einem Quantor steht - paarweise verschieden sind - verschieden von allen freien Var. sind

7

Pränexform - Formel, wenn sie die Gestalt Q1x1 … Qnxn G hat Qi Quantoren sind und G Quantorenfrei ist. (Alle Quantoren vor der Formel)

Voraussetzungen: - Kein Äquivalenzjunktor ó - Rektifiziert (siehe letzte Sei

BSP

-

-

alle x kommt mit neg. Polarität vor (Rechte Seite der linken Implikation = 0) aber (linke Seite der rechten Implikation = 1) 0 + 1 ungerade => Ex existiert y => zwei mal rechte Seite der Implikation => Positiv ABER es ist negiert => Neg. Polarität => wird zum A existiert z => zwei mal rechte Seite der Implikation => Positiv => bleibt E

alle x kommt mit neg. Polarität vor (Rechte Seite der linken Implikation = 0) aber (linke Seite der rechten Implikation = 1) 0 + 1 Negation => bleibt Existenz doppelte Negation => bleibt Existenz => negiert => wird zu allem

8

Polarität: - F Formel in der ⇔ NICHT vor kommt - G eine Teilformel von F Positive Polarität: Negative Polarität: - G in F geraden Anzahl von ¬ - G in F ungeraden Anzahl von ¬ - Linke Seite des ⇒ - Linke Seite des ⇒ ) è Zählt Negationen und Vorkommen in linken Teilen è Gerade (Positive); Ungerade (Negative)

p im linken Teil einer Implikation => negativ p im rechten Teil einer Implikation => keine neg und kein „linker Teil“ => 0 => positiv

9

Elementare Substitution è Skolemform - s und t L-Terme, F L-Formel und x eine Var [s/x] => elementare Sub. „s für x“

Term frei für eine Var. in einer Formel: Nur wenn s frei für x in F vorkommt => innerhalb der Quantifikation von x darf kein s vor kommen BSP

BSP

è Analog mit 2-stelligem Fktsymbol

10

Skolemform (nur Allquantoren)

Literale: - pos. Literal => Atom - neg. Literal => negiertes Atom Komplement: - L w eines positiven Literals L = A negative Literal ¬A. - L w eines negativen Literals L = ¬A positive Literal A. Kausel: - Disjunktion „v“ von Literalen

11

Konjunktive Normalform - In Pränexform (alle Quantoren vorne) - Quantorfreie Teil => Konjunktion „∧“)von Klauseln

1. Rektifiziert (keine doppelte Var. belegung) 2. Pränexform (Quantoren nach vorne)

BSP Nicht konj. Normalform da 2. x nicht hätte ersetzt werden müssen => E Quantor bezieht sich nur aus 1. x

Regeln:

Klauselnormalform - Konjunktion „∧“ von Klauseln (=> konj Normalform ohne Quantoren)

12

V Resolution Beweis: Feststellung davon, dass eine Aussage aus einer Menge von Axiomen folgt. è Beweismethoden Resolution: Technik des automatischen Beweisens. Eine Widerlegungsmethode ð Um zu beweisen, dass aus F, G folgt: (F ∧ ¬G ) F und nicht G ist ein Wiederspruch Disjunktion „v“ è , :

ð Reihenfolge der Literale in einer Klausel ist irrelevant è Klausel (Disjunktion „v“ von Lit) kann ohne Klammerung da gestellt werden

Klausel als Menge von Lit:

Konjunktion „∧“)è){}):) ) ) Klauselnormalform als Menge von Klauseln.

(a ∧ ¬a) => {{a}, {¬a}} => ⊥)

13

Klausur Formel F unerfüllbar

Resolution verlangt: - Geschlossene Form (keine freie Variablen) => Alle an einen Allquantor gebunden - In Klauselnormalform => in Skolemform (nur Allquantoren) - Rektifikation => Var. werden ersetzt die in der anderen Klausel nicht vor kommen

14

Unifikationsalg.:

BSP

15

VI Natürliches Schließen 1.Einführungsregel für die Disjunktion:

-

2.Einführungsregel für die Konjunktion:

”E“ für ”Einführung“ ”r“ für ”rechts“ ”l“ für ”links“

3.Einführungsregel für die Implikation:

16

4.Einführung in die Negation:

5.Einführung der doppelten Negation:

6.Einführungsregeln für ⊤ und ¬⊥:

7.Einführungsregeln für ⊥:

1.Beseitigungsregeln für die Konjunktion:

-

2.Beseitigungsregel für die Disjunktion:

”B“ für ”Beseitigung“ ”r“ für ”rechts“ ”l“ für ”links“

3.Beseitigungsregl für die Implikation:

4.Beseitigungsregl für die Negation Regeln ¬B"und ⊥E"sind identisch

5.Beseitigungsregel für die doppelte Negation:

6.Beseitigungsregl für ⊥:

17

Beide Annahmen sind beseitigt:

In einer Herleitung in der alle Annahmen beseitigt sind => gilt in allen Welten

Anders herum:

Gleiches Prinzip

GEHT NICHT!!! Verum => nVerum NEIN!!

18

Herleitung von ((A ⇒ B) ⇒ (¬B ⇒ ¬A))

(A ⇔ B) Notation für ((A ⇒ B) ∧ (B ⇒ A))

Einführungsregel für ∀:

Einführungsregel für ∃:

Beseitigungsregel für ∀:

19

Beseitigungsregel für ∃:)

BSP

VII Natürliche Zahlen: N = {0,1,2,…} => Nachfolgefkt S

è N enthält jedes der Elemente 0, S(0), S(S(0)), S(S(S(0))), ... 0 8∈"Bild(s)"=>"0"ist"kein"Nachfolger"einer"nat."Zahl" -

Für alle n e N \ {0} gilt:

20

Induktion:

Die Addition über N: - Assoziativ (m+n)+p=m+(n+p) - Kommutativ m+n=n+m Vollständige Induktion:

entspricht Prinzip 21

Ordnungsrelationen: „≤“ - Reflexiv n ≤ n - Antisymmetrisch ((n≤m ∧ m≤n) => n=m) - Transitiv ((n≤m ∧)m≤k) => n≤k) !! < (Wohlordnung über N) ist nicht antisymmetrisch è KEINE Ordnungsrelation !! VIII Ganze Zahlen: Idee: n -m durch Paar (n,m) è Subtraktion und negative ganze Zahlen -2 = (0,2), (1,3), (2,4),…, (n,n+2) Sinnäquivalent wenn: - n + m = n‘ + m‘ - n – m = n‘ – n‘ Relation ∼ def: Für alle n, m, n‘, m‘ in N: (n,m) ∼)(nʹ,mʹ )gdw. n+mʹ = nʹ+m ) Äquivalenzrelation von ∼:)

è Äquivalenzklassen

BSP:

22

Fundamentalsatz der Arithmetik:

IX Modulararithmetik Kongruenz modulo a, b e Z (ganze Zahlen) und m e N m ≥ 2 a ist kongruent zu b modulo m (mod => Rest einer Division) gdw. a – b durch m teilbar ist => „b zieht mod m von a ab“ oder „a = (k x m) + b“ k e Z Notiert: „. ≡ . (mod m)“ (z.B. a ≡ b (mod m) ) -

Für jedes m e N mit m ≥ 2

23

z.B.: 6 e 0—3 => 6 e (k x 3) + 0 => stimmt da 6 Vielfaches von 3. k = 2 -6 e 0—3 => -6 e (k x 3) + 0 => stimmt da k e Z => k = -2 -1 e 1—3 => -1 e (k x 3) + 1 => für k = -2/3 !! kein e von Z !!

Lemma 1:

Lemma 2:

24

Lemma 3:

Lemma 4:

Lemma 5:

Lemma 6:

X Kombinatorik: k Objekte aus n: - Ziehen mit zurück legen? - Reihenfolge relevant?

25

Ziehen von k Objekten aus n (mit 1 ≤ k ≤ n)

Ziehen mit zurück legen, geordnet: - Da Objekt mehrmals gezogen werden kann => n Möglichkeiten - Mit k Ziehungen => nk Ziehen ohne zurücklegen, geordnet: - Objekt kann nicht mehrmals gezogen werden => 1. n 2. n-1 … - Möglichkeiten: n x n(n-1) x … x (n-k+1) - Permutation => n! Ziehen ohne zurücklegen, ungeordnet: - Objekt kann nicht mehrmals gezogen werden => in k! versch. Reihenfolge - Da Reihenfolge verschieden => „Ziehen ohne zurücklegen, geordnet“ x k! è Binomialkoeffizient Ziehen mit zurück legen, ungeordnet: - Objekt kann mehrmals gezogen werden - „Ziehen ohne zurücklegen, ungeordnet“ => Zahl der Multimengen Kodierung einer Multimenge als Liste:

26

Verallgemein.

27...