28
Logik Logik Vorkurs Informatik Theoretischer Teil WS 2013/14 30. September 2013 Vorkurs Informatik - Theorie - WS2013/14

Logik - Benutzer-Homepages · PDF fileLogik > Logik > logische Aussagen Motivation Logik spielt in der Informatik eine wichtige Rolle. Anwendungen sind z.B. Modellierung von Wissen

  • Upload
    ledieu

  • View
    216

  • Download
    0

Embed Size (px)

Citation preview

Logik

Logik

Vorkurs InformatikTheoretischer Teil

WS 2013/14

30. September 2013

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > logische Aussagen

Logik

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > logische Aussagen

Motivation

Logik spielt in der Informatik eine wichtige Rolle. Anwendungen sindz.B.

Modellierung von Wissen (z.B. kunstliche Intelligenz

Auswertung von Datenbankanfragen

Kontrollfluss von Computerprogrammen(if-then-else-Konstrukte)

Logikbauteile in der technischen Informatik (Hardware)

Automatische Verifikation (automatisches Testen eines Systemsauf dessen Funktionstuchtigkeit)

Mathematische Beweise

Korrektes Argumentieren

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > logische Aussagen

logische Aussagen

Die Logik behandelt die allgemeinen Prinzipien des korrektenArgumentierens. Diese Prinzipien gelten auch unabhangig vomkonkreten Inhalt. Eine logische Aussage (kurz Aussage) ist ein Satzoder Ausdruck, der entweder wahr (1) oder falsch (0) sein kann.

Beispiel 1: Folgende Satze und Ausdrucke sind Aussagen:

”Die Sonne scheint.“

”Es ist hell.“

”Der Tisch ist blau.“

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > logische Aussagen

Beispiel 2

Beispiel 2: Folgende Satze und Ausdrucke sind keine Aussagen:

“5 + 5”, “3 · 2”, “ 57 ” usw., da sie keine vollstandige Ausdrucke

sind, denen man die Werte wahr oder falsch zuordnen kann.

“15 ist eine schone Zahl” (“schon” ist fur Zahlen nicht definiert.)

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > logische Aussagen

Beispiel 2 Fortsetzung

Aufforderungen (“Lach mal!”)

und Fragen (“Wie spat ist es?”)

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > Aussagenlogik

Aussagenlogik

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > Aussagenlogik

Syntax und Semantik

Definition (Syntax)

Mit der Syntax legen wir fest, welche Zeichenreihen gultige Formelnsind und welche nicht.

So soll etwa (A→ B) eine gultige Zeichenreihe sein, wohingegen dieZeichenreihe (→ A)B nicht erlaubt sein soll.

Definition (Semantik)

Die Semantik legt die Bedeutung einer Formel fest; also, ob eineFormel wahr oder falsch ist. Dies ist immer abhangig davon, ob dieeinzelnen atomaren Aussagen, aus denen eine Formel besteht, wahroder falsch sind. Der Einfachheit halber belegen wir die Atome nur mit“wahr”(1) oder “falsch”(0), den sogenannten Wahrheitswerten.

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > Syntax und Semantik der Aussagenlogik

Syntax und Semantik der Aussagenlogik

Wir nehmen an, dass wir eine unendliche Menge A, . . ., Z , A1, . . . vonAtomen (auch aussagenlogische Variablen genannt) gegeben haben.Aussagenlogische Formeln bestehen aus den Atomen, den Junktoren∧,∨,¬,→, ↔ und Klammern. Sie werden nach den folgenden Regelnaufgebaut:

Definition

Sowohl aussagenlogische Variablen, als auch 0 und 1, sind gultigeFormeln.

Beispiele:

V Der Vorhang ist rot.

K Der Koffer ist blau.

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > Syntax und Semantik der Aussagenlogik

Negation

Definition (Negation)

Ist A eine Formel, dann ist auch ¬A (nicht A) eine Formel. DieAussage ¬A ist nur dann wahr, wenn die Aussage A falsch ist.

Beispiel:

A Alle Kinder spielen gern.

¬A Nicht alle Kinder spielen gern.

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > Syntax und Semantik der Aussagenlogik

Negation

Definition (Negation)

Ist A eine Formel, dann ist auch ¬A (nicht A) eine Formel. DieAussage ¬A ist nur dann wahr, wenn die Aussage A falsch ist.

Wahrheitstafel:

A ¬A0 11 0

Vorkurs Informatik - Theorie - WS2013/14

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 Die Sonne scheint.

B Der Wind weht stark.

(A ∧ B) Die Sonne scheint und der Wind weht stark.

Vorkurs Informatik - Theorie - WS2013/14

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

Vorkurs Informatik - Theorie - WS2013/14

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:

V Der Vorhang ist rot.

K Der Koffer ist blau.

(V ∨ K ) Der Vorhang ist rot oder der Koffer ist blau.

Vorkurs Informatik - Theorie - WS2013/14

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

Vorkurs Informatik - Theorie - WS2013/14

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 Es regnet.

B Die Straße ist nass.

(A→ B) Wenn es regnet, dann ist die Straße nass.

Vorkurs Informatik - Theorie - WS2013/14

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

Faustregel: Aus Wahrem kann man nur Wahres folgern - ausFalschem kann man alles folgern.

Vorkurs Informatik - Theorie - WS2013/14

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 Der Schornstein raucht.

B Die Heizung ist an.

(A↔ B) Der Schornstein raucht genau dann, wenn die Heizungan ist.

Vorkurs Informatik - Theorie - WS2013/14

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

Vorkurs Informatik - Theorie - WS2013/14

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 Ich liege Montags um 10 Uhr im Bett und schlafe.

L Ich besuche Montags um 10 Uhr die Vorlesung”Lineare

Algebra“.

(D∨L) Entweder liege ich Montags um 10 Uhr im Bett undschlafe oder besuche die Vorlesung

”Lineare Algebra“.

Vorkurs Informatik - Theorie - WS2013/14

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

Vorkurs Informatik - Theorie - WS2013/14

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

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > Noch mehr Definitionen

Tautologie

Definition (Tautologie)

Eine aussagenlogische Formel, deren Wahrheitswert bei jeder Belegungder Variablen wahr ist, heißt Tautologie (oder allgemeingultig).

Beispiel:

A ¬A (A ∨ ¬A)

0 1 11 0 1

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > Noch mehr Definitionen

Kontradiktion

Definition (Kontradiktion)

Eine aussagenlogische Formel, deren Wahrheitswert bei jeder Belegungder Variablen 0 (falsch) ist, heißt Kontradiktion (oder unerfullbar).

Beispiel:

A ¬A (A ∧ ¬A)

0 1 01 0 0

Vorkurs Informatik - Theorie - WS2013/14

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

Vorkurs Informatik - Theorie - WS2013/14

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

Vorkurs Informatik - Theorie - WS2013/14

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

Vorkurs Informatik - Theorie - WS2013/14

Logik > Logik > Rechenregeln

noch Fragen???

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

Vorkurs Informatik - Theorie - WS2013/14