Logik - lz_inf/Vorkurs/WiSe11/uploads/files/tag... · A Orlando di Lasso lebte im 16. Jahrhundert B Orlando di Lasso leitete die bayerische Hofkapelle (A ^B)Orlando di Lasso lebte

Logik

Logik

Quick Start InformatikTheoretischer Teil

WS2011/12

7. Oktober 2011

QSI - Theorie - WS2011/12

Logik > Logik > logische Aussagen

Logik



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



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.”



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.



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.


Logik > Logik > Aussagenlogik

Aussagenlogik


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”.


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



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



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



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



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



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.



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



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



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



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.



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



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.



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


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



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



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



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”α ≡ β“.


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 ))



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



noch Fragen???

Quelle Bild: http://www.citycampus.eu/cms/images/comic fragezeichen.png


Documents

Logik - lz_inf/Vorkurs/WiSe11/uploads/files/tag... · A Orlando di Lasso lebte im 16. Jahrhundert B Orlando di Lasso leitete die bayerische Hofkapelle (A ^B)Orlando di Lasso lebte