Mathematische Logik

De…nitionEine Aussage ist ein sprachliches oder formelmäßiges Gebilde, von dem es sinnvoll ist zu sagen, essei wahr oder falsch.Einer Aussage kann man einen Wahrheitswert 1 (wahr) oder 0 (falsch) zuordnen.Beispiel

Abkürzung Aussage WahrheitswertP ”7 < 10" 1 (wahr)Q ”1 + 1 = 3" 0 (falsch)

De…nitionEine Aussageform enthält Variable. Durch die Belegung der Variablen ergeben sich Aussagen.BeispielAussageform: P(x) : ”x ist eine gerade Zahl”

Belegung=) P (1) : ”1 ist eine gerade Zahl” (falsch)Belegung=) P (4) : ”4 ist eine gerade Zahl” (wahr)

Aussagen können durch logische Operationen zu neuen Aussagen verknüpft werden.Beispiele

² ”Wenn jemand mit stark überhöhter Geschwindigkeit fährt und in eine Radarmessung geratenist, dann erhält er Punkte in Flensburg.” (o¤ensichtlich wahr)

² ”Wenn der Hahn kräht auf dem Mist, dann ändert sich das Wetter oder es bleibt wie es ist”(wahre ’Bauernregel’)

Logische OperationenSeien P und Q Aussagen:

Bezeichnung: symbolisch gelesen:Negation: P ”nicht P ”Konjunktion: P ^ Q "Pund Q"

"und” im Sinne von ”sowohl als auch”Disjunktion: P _ Q "Poder Q"

”oder” nicht im Sinne von ”entweder oder”Implikation: P ) Q "aus P folgt Q" ; " wenn P; so Q"

oder ”wenn P; dann Q"Äquivalenz: P , Q ” P genau dann, wenn Q”

oder ” P dann und nur dann, wenn Q”

Logischen Operationen kann man mittels einer Wahrheitstabelle de…nieren.(Versuchen Sie dieseDe…nitionen nachzuvollziehen!)

P Q P P ^ Q P _ Q P ) Q P , Q0 0 1 0 0 1 10 1 1 0 1 1 01 0 0 0 1 0 01 1 0 1 1 1 1

Beispiele

² Sei P = "7 < 10" (wahr), so P = "7 ¸ 10" (falsch)

1

² Seien P = "7 < 10" (wahr)Q = "7 = 10" (falsch)

¾, dann gilt: P ^ Q = "7 < 10 und 7 = 10" ist falsch.

² Seien P = "7 < 10" (wahr)Q = "7 = 10" (falsch)

¾, dann gilt: P _ Q = "7 < 10 oder 7 = 10" ist wahr.

² Seien a;b 2 R : a = b ) a2 = b2 für jede Belegung wahr!z.B. fürBelegung: ¡1 = 1| {z }

falsch

) (¡1)2 = 12| {z }wahr

wahr

1 = 2| {z }falsch

) 12 = 22| {z }falsch

wahr

Man beachte: Aus Falschem kann Wahres oder Falsches gefolgert werden.Wenn man aus einer Aussage mit unbekannten Wahrheitswert eine wahre Aussage folgert,folgt nicht, daß die ursprüngliche Aussage auch wahr ist,d.h. die häu…g anzutre¤endeSchlußweise((P ) Q) ^ Q) ) P ist falsch

² Wir betrachten die Aussagen P = ”Dreieck ist gleichseitig”, Q = ”Dreieck ist gleichwinklig”.Dann gilt die wahre Aussage:P , Q = ”Ein Dreieck ist gleichseitig genau dann, wenn es gleichwinklig ist.”

Sprechweise:Es gelte P ) Q. Man sagt dann auchP ist eine hinreichende Bedingung für QQ ist eine notwendige Bedingung für P

Beispiele

² Notwendig dafür, daß eine Zahl n 2 N durch 6 teilbar ist, ist ihre Teilbarkeit durch 2:(P = ”n 2 N durch 6 teilbar”; Q = ”n 2 N durch 2 teilbar”: Es gilt P ) Q).

² Sei y = f(x) di¤erenzierbar in (a;b) : Dann ist f0(x0) = 0 eine notwendige Bedingung dafür,daß in x0 2 (a; b) ein lokales Extremum vorliegt.

SchlußregelnBeim logischen Schließen werden Schlußregeln angewendet (hier eine kleine Auswahl).

((P ) Q) ^ P ) ) Q (Abtrennregel)¡P _ Q

¢,

¡P ^ Q

¢(De Morgansche Regel)¡

P ^ Q¢

,¡P _ Q

¢(De Morgansche Regel)

(P ) Q) ,¡Q ) P

¢(Kontraposition)

(P ) Q) ,¡P ^ Q

¢(Negation der Implikation)

Es handelt sich um sogenannte Tautologien, (Tautologien haben für jede Belegung von P; Q denWahrheitswert 1). Bei der Negation von Aussagen werden häu…g Fehler begangen, so daß dieformale Anwendung dieser Schlußregeln sehr nützlich und empfehlenswert ist.Beispiele

² Die Regel ((P ) Q) ^ P) ) Q benutzt intuitiv jedes Kind.Wenn die Mutter z.B. sagt: ”Wenn du noch einen Lö¤el von der Suppe ißt, dann darfst dudein Kompott essen”, so wird der Sprößling mit Bewältigung dieses einen Lö¤els voll Suppesofort auf der Freigabe das angekündigten Kompotts bestehen.

² Betrachten wir die logische Struktur der ’Bauernregel’: ”Wenn der Hahn kräht auf dem Mist,dann ändert sich das Wetter oder es bleibt wie es ist”.Wir setzen: H¡ ”Hahn kräht auf Mist”, W¡ ”Wetter ändert sich”’Bauernregel’: H )W _ W| {z }

wahr

ist somit unabhängig von H immer wahr

2

² Betrachten wir weiter die obige wahre Aussage:”Wenn jemand mit stark überhöhter Geschwindigkeit fährt und in eine Radarmessung ger-aten ist, dann erhält er Punkte in Flensburg.”Welche Aussage kann man ableiten, wenn jemand keine Punkte in Flensburg hat? Gehen wirformal an die Fragestellung heran.

Wir setzen: G¡ ”mit stark überhöhter Geschwindikeit fahren”R¡ ”in Radarmessung geraten”, P¡ ”Punkte in Flensburg”

Aussage:Fragestellung:

(G ^ R) ) PP ) ???

Es gilt: (G^ R) ) P Kontraposition() P ) (G ^ R)(G^ R) De Morgansche Regel() G _ R

)=)

¡P ) G_ R

¢

Man kann also ableiten (sinngemäß formuliert):”Wenn jemand keine Punkte in Flensburg hat, dann ist er nichtzu schnell gefahren oder nicht geblitzt worden”

² In einer Datenbank sollen alle Personen gefunden werden, die gleichzeitig folgenden Bedin-gungen genügen:A = ”Person ist männlich”, B = ”Körpergröße der Person ¸ 180 cm”Gesucht wird also mit der Bedingung A^B = ”Person ist männlich und hat eine Körpergröße¸ 180 cm”.Ignoriert werden dann alle Personen mit A ^ B

De Morgansche Regel() A_B = ”Person ist weiblichoder Person hat eine Körpergröße < 180 cm”

Quanti…katoren erzeugen aus Aussageformen Aussagen:8x : P (x) - für alle x (einer Grundgesamtheit) ist P(x) wahr9x : P (x) - es existiert (mindestens) ein x für das P(x) wahr ist

Beispiele

² 8x 2 R : x2 ¸ 0 (wahre Aussage)

² 9x 2 R : x2 = 2 (wahre Aussage, z.B. x =p

2)

² 9x 2 R : x2 +1 = 0 (falsche Aussage)

Die Negation von diesem Aussagentyp wird von vielen Studenten immer wieder gern falsch gemacht.Man verwende dieDe Morganschen Regeln8x : P(x) () 9x : P(x)9x : P(x) () 8x : P(x)

Beispiele

² 8x 2 R : x2 ¸ 0 , 9x 2 R : x2 ¸ 0 , 9x 2 R : x2 < 0 (falsche Aussage)

² Man negieren die Aussage:”Alle Bundestagsabgeordneten stimmen für eine Diätenerhöhung”Das Ergebnis lautet: ”Es gibt mindestens einen Bundestagsabgeordneten, der nicht für eineDiätenerhöhung stimmt.”

3