Logik
Logik
Quick Start InformatikTheoretischer Teil
WS2011/12
7. Oktober 2011
QSI - Theorie - WS2011/12
Logik > Logik > logische Aussagen
Motivation
Logik spielt in der Informatik eine wichtige Rolle. Anwendungen sindz.B.
Modellierung von Wissen, etwa in der kunstlichen Intelligenz
Automatische Verifikation (automatisches Testen, ob ein Systemdie Spezifikationen erfullt)
Kontrollfluss von Computerprogrammen
Logikbauteile in der Hardware
Datenbanken: Auswerten von Anfragen
Mathematische Beweise
Korrektes Argumentieren
QSI - Theorie - WS2011/12
Logik > Logik > logische Aussagen
logische Aussagen
Die Logik behandelt die allgemeinen Prinzipien des korrektenArgumentierens. Diese Prinzipien gelten allein aufgrund der Form derAussagen und sind unabhangig vom konkreten Inhalt. Eine logischeAussage (kurz Aussage) ist ein Satz oder Ausdruck, der entwederwahr oder falsch sein kann auch wenn wir diese gegebenenfalls nichtkennen.
Beispiel 1: Folgende Satze und Ausdrucke sind Aussagen:
“2 ist gerade.”
“2 < 1”, “2 > 1”
“Dieser Ball ist rot.”
QSI - Theorie - WS2011/12
Logik > Logik > logische Aussagen
Beispiel 2
Beispiel 2: Folgende Satze und Ausdrucke sind keine Aussagen:
“1 + 2”, “1− 2” usw., da sie keine vollstandige Ausdrucke sind,denen man die Werte wahr oder falsch zuordnen kann.
“2 ist eine kleine Zahl” ist keine Aussage, da “klein” fur Zahlennicht definiert ist.
QSI - Theorie - WS2011/12
Logik > Logik > logische Aussagen
Beispiel 2 Fortsetzung
Aufforderungen (“Komm her!”) und Fragen (“Was machen wir?”)
“Dieser Satz ist falsch!”, da dieser Satz weder wahr noch falschsein kann. Denn wenn der Satz wahr ware, dann trifft derbehauptete Sachverhalt zu und demnach ist der Satz falsch. Erkann aber auch nicht falsch sein; denn dann trifft der Sachverhaltnicht zu und so ist der Satz wahr.
QSI - Theorie - WS2011/12
Logik > Logik > Aussagenlogik
Syntax und Semantik
Definition (Syntax)
Mit der Syntax legen wir fest, welche Zeichenreihen gultige Formelnsind.
So soll etwa (A ∧ B) eine gultige Zeichenreihe sein, wohingegen dieZeichenreihe ∧()AB nicht erlaubt sein soll.
Definition (Semantik)
Die Semantik legt fest, ob die Formeln wahr oder falsch sind - jeweilsin Abhangigkeit davon, ob die einzelne atomaren Aussagen von denensie bestehen wahr oder falsch sind. Wir werden von konkreten Inhaltender atomaren Aussagen absehen und belegen die Atome einfachentweder mit “wahr” oder “falsch”, den sogenanntenWahrheitswerten. Wir verwenden 1 fur “wahr” und 0 fur “falsch”.
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Syntax und Semantik der Aussagenlogik
Wir nehmen an, dass wir eine unendliche Menge A, B, A1, A2, A3, . . . ,B1,B2,B3,. . . von Atomen (auch aussagenlogische Variablengenannt) gegeben haben. Aussagenlogische Formeln sindZeichenreihen, die aus den Atomen, den Junktoren ∧,∨,¬,→ und ↔und den beiden Klammern ( und ) nach den folgenden Regelnaufgebaut werden.
Definition
Atome sind Formeln.
Beispiele:
L Lucy spielt Gitarre
A 9 geteilt durch 3 ist 2
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Negation
Definition (Negation)
Wenn A eine Formel ist, dann ist auch ¬A (nicht A) eine Formel (DasZeichen
”¬“ heißt Negation.) Die Aussage ¬A ist nur dann wahr,
wenn die Aussage A falsch ist.
Beispiel:
A Deutschland ist Fußballweltmeister
¬A Deutschland ist nicht Fusßballweltmeister
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Negation
Definition (Negation)
Wenn A eine Formel ist, dann ist auch ¬A (nicht A) eine Formel (DasZeichen
”¬“ heißt Negation.) Die Aussage ¬A ist nur dann wahr,
wenn die Aussage A falsch ist.
Wahrheitstafel:
A ¬A
0 11 0
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Konjunktion
Definition (Konjunktion)
Seien A und B zwei Formeln, dann ist (A ∧ B) (sprich: A und B)ebenfalls eine Formel. Die Aussage (A ∧ B) ist wahr, wenn sowohl dieAussage A als auch die Aussage B wahr sind.
Beispiel:
A Orlando di Lasso lebte im 16. Jahrhundert
B Orlando di Lasso leitete die bayerische Hofkapelle
(A ∧ B) Orlando di Lasso lebte im 16. Jahrhundert und leitete diebayerische Hofkapelle
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Konjunktion
Definition (Konjunktion)
Seien A und B zwei Formeln, dann ist (A ∧ B) (sprich: A und B)ebenfalls eine Formel. Die Aussage (A ∧ B) ist wahr, wenn sowohl dieAussage A als auch die Aussage B wahr sind.
Wahrheitstafel:
A B (A ∧ B)
0 0 00 1 01 0 01 1 1
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Disjunktion
Definition (Disjunktion)
Seien A und B zwei Formeln, dann ist (A ∨ B) (sprich: A oder B)ebenfalls eine Formel. Die Aussage (A ∨ B) ist wahr, wenn mindestenseine der beide Aussagen A oder B wahr ist.
Beispiel:
D Im WS wird die Vorlesung “Logik und Datenbanken”angeboten
L Im WS wird die Vorlesung “Logik in der Informatik”angeboten
(D ∨ L) Im Wintersemester wird die Vorlesung “Logik undDatenbanken” oder die Vorlesung “Logik in derInformatik” angeboten.
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Disjunktion
Definition (Disjunktion)
Seien A und B zwei Formeln, dann ist (A ∨ B) (sprich: A oder B)ebenfalls eine Formel. Die Aussage (A ∨ B) ist wahr, wenn mindestenseine der beide Aussagen A oder B wahr ist.
Wahrheitstafel:
A B (A ∨ B)
0 0 00 1 11 0 11 1 1
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Implikation
Definition (Implikation)
Seien A und B zwei Formeln, dann ist (A→ B) (sprich: Wenn A dannB) ebenfalls eine Formel. Die Aussage (A→ B) ist wahr, wenn A falschist oder wenn sowohl die Aussage A als auch die Aussage B wahr sind.
Beispiel:
A Wir nehmen die Express-Fahre ab Hirtshals
B Wir gelangen nach Bergen
(A→ B) Wenn wir die Express-Fahre ab Hirtshals nehmen, dannwerden wir nach Bergen gelangen
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Implikation
Definition (Implikation)
Seien A und B zwei Formeln, dann ist (A→ B) (sprich: Wenn A dannB) ebenfalls eine Formel. Die Aussage (A→ B) ist wahr, wenn A falschist oder wenn sowohl die Aussage A als auch die Aussage B wahr sind.
Wahrheitstafel:
A B (A→ B)
0 0 10 1 11 0 01 1 1
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Biimplikation
Definition (Biimplikation)
Seien A und B zwei Formeln, dann ist (A↔ B) (sprich: A genau dannwenn B) ebenfalls eine Formel. Die Aussage (A↔ B) ist wahr, wenn Aund B beide falsch oder beide wahr sind.
Beispiel:
A Deutschland schneidet bei der PISA-Studie besser ab
B Der Staat investiert mehr Geld in die Bildung
(A↔ B) Deutschland schneidet bei der PISA-Studie besser abgenau dann wenn der Staat mehr Geld in die Bildunginvestiert.
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
Biimplikation
Definition (Biimplikation)
Seien A und B zwei Formeln, dann ist (A↔ B) (sprich: A genau dannwenn B) ebenfalls eine Formel. Die Aussage (A↔ B) ist wahr, wenn Aund B beide falsch oder beide wahr sind.
Wahrheitstafel:
A B (A↔ B)
0 0 10 1 01 0 01 1 1
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
ausschließende Disjunktion
Definition (ausschließende Disjunktion)
Seien A und B zwei Formeln, dann ist (A∨B) (sprich: Entweder Aoder B) ebenfalls eine Formel. Die Aussage (A∨B) ist wahr, wenngenau eine der beide Aussagen A oder B wahr ist.
Beispiel:
D Im WS kann man Dienstags von 10:00 bis 12:00 dieVorlesung “Einfuhrung in die Numerik” besuchen.
L Im WS kann man Dienstags von 10:00 bis 12:00 dieVorlesung “Einfuhrung in Adaptive Systeme” besuchen.
(D∨L) Im Wintersemester kann man Dienstags von 10:00 bis12:00 entweder die Vorlesung “Einfuhrung in dieNumerik” oder die Vorlesung “Einfuhrung in AdaptiveSysteme” besuchen.
QSI - Theorie - WS2011/12
Logik > Logik > Syntax und Semantik der Aussagenlogik
ausschließende Disjunktion
Definition (ausschließende Disjunktion)
Seien A und B zwei Formeln, dann ist (A∨B) (sprich: Entweder Aoder B) ebenfalls eine Formel. Die Aussage (A∨B) ist wahr, wenngenau eine der beide Aussagen A oder B wahr ist.
A B (A∨B)
0 0 00 1 11 0 11 1 0
QSI - Theorie - WS2011/12
Logik > Logik > Noch mehr Definitionen
Tautologie
Definition (Tautologie)
Eine aussagenlogische Formel, deren Wahrheitswert bei jeder Belegungder Variablen 1 (wahr) ist, heißt Tautologie.
Beispiel:
A ¬A (A ∨ ¬A)
0 1 11 0 1
QSI - Theorie - WS2011/12
Logik > Logik > Noch mehr Definitionen
Kontradiktion
Definition (Kontradiktion)
Eine aussagenlogische Formel, deren Wahrheitswert bei jeder Belegungder Variablen 0 (falsch) ist, heißt Kontradiktion.
Beispiel:
A ¬A (A ∧ ¬A)
0 1 01 0 0
QSI - Theorie - WS2011/12
Logik > Logik > Noch mehr Definitionen
Erfullbare Formeln
Definition (Erfullbar)
Eine aussagenlogische Formel, heißt erfullbar, wenn es eine Belegungder Variablen gibt, bei der die Formel den Wahrheitswert 1 hat.
Beispiel:
A B (A ∧ B)
0 0 00 1 01 0 01 1 1
QSI - Theorie - WS2011/12
Logik > Logik > Noch mehr Definitionen
Aquivalente Formeln
Definition
Seien α und β aussagenlogische Formeln.
Sei M die Menge der Variablen, die in α vorkommen, und N dieMenge der Variablen, die in β vorkommen.
Die Formeln α und β heißen aquivalent, wenn fur jede Belegungder Variablen in M ∪ N die Wahrheitswerte von α und βubereinstimmen.
Wir schreiben dann auch”α ≡ β“.
QSI - Theorie - WS2011/12
Logik > Logik > Rechenregeln
Rechenregeln
Seien A, B und C aussagenlogischen Formeln. Dann gilt:
1) ¬¬A ≡ A
2) Kommutativgesetze:
(A ∧ B) ≡ (B ∧ A)(A ∨ B) ≡ (B ∨ A)
3) Assoziativgesetze:
((A ∧ B) ∧ C ) ≡ (A ∧ (B ∧ C ))((A ∨ B) ∨ C ) ≡ (A ∨ (B ∨ C ))
4) Distributivgesetze:
((A ∧ B) ∨ C ) ≡ ((A ∨ C ) ∧ (B ∨ C ))((A ∨ B) ∧ C ) ≡ ((A ∧ C ) ∨ (B ∧ C ))
QSI - Theorie - WS2011/12
Logik > Logik > Rechenregeln
Rechenregeln 2
5) De Morgan’sche Gesetze:
¬(A ∧ B) ≡ (¬A ∨ ¬B)¬(A ∨ B) ≡ (¬A ∧ ¬B)
6)
(A ∧ 1) ≡ A (A ∧ 0) ≡ 0 (A ∧ A) ≡ A(A ∨ 1) ≡ 1 (A ∨ 0) ≡ A (A ∨ A) ≡ A
7) Absorptionsgesetze:
(A ∨ (A ∧ B)) ≡ A(A ∧ (A ∨ B)) ≡ A
QSI - Theorie - WS2011/12