Menschliche Logik AND Boolsche Logik = NOT Logisch

Menschliche Logik AND Boolsche Logik = NOT Logisch

Der Satz vom Widerspruch

z.B.: „Zürich ist ein Kontinent.“ und „Zürich ist kein Kontinent.“ kann nicht gleichzeitig wahr sein.

Axiom (Vorannahme) der Logik, d.h. weder beweis- noch widerlegbar

Aristoteles, Begründer der Logik* 384 v. Chr. in Stageira† 322 v. Chr. in Chalkis

Eine Aussage kann nicht gleichzeitig mit ihrem Gegenteil wahr sein.

Logische Folgerung Aussage 1: „Wenn es regnet, wird die Straße nass.“

Aussage 2: „Es regnet.“

Folgerung: „Die Straße wird nass.“

Aus den zwei Aussagen “wenn A, dann B“ und „A“ kann die Aussage „B“ hergeleitet

werden.

Auf diese Weise können wir argumentieren und mittels gemeinsam anerkannten „Regeln“ und wahren Aussagen neue Aussagen als wahr herleiten.

Was sind Aussagen?

2 + 4 = 6 1 Zürich ist die Hauptstadt der Schweiz. 0 Peter (23) ist älter als Paul (17). 1

Aussagen sind Sätze, die entweder wahr (1) oder falsch (0) sind.

Keine Aussagen:• Wo ist der Bahnhof?• Ruhe jetzt!

• Bern ist eine schöne Stadt.• Dieses Wasser (20°) ist kalt.

unklar!

AussagenlogikAussagen…

…werden durch Variablen repräsentiert

…haben Wahrheitswert (wahr/falsch, resp. 0/1) A = „Zürich ist die Hauptstadt der Schweiz.“ 0 B = „2+4=6“ 1

Aussagenlogische Formeln sind zusammengesetzte Aussagen (*Beispiele mit obigen Werten für A und B):

A UND B 0 A ODER B 1 (NICHT A) UND B 1

… sind ebenfalls Aussagen, also auch entweder wahr oder falsch – je nach Wahrheitsgehalt ihrer Teile. Peter ist älter als Paul und 4+4=8. ?

... werden oft als Wahrheitstabellen dargestellt, z.B.

Zusammengesetzte Aussagen…

A B A UND B

0 0 0

0 1 0

1 0 0

1 1 1

Die Idee ist, für alle Kombinationen der einfliessenden Teilaussagen (= Inputs) den Wert der zusammengesetzten Aussage (= Output) darzustellen

George BooleBegründer der Aussagenlogik

englischer Mathematiker* 1815 in Lincoln† 1864 in Ballintemple (Irland)

Boolesche Variablen Können immer nur einen von zwei Werten annehmen

true/false, wahr/falsch, 1/0 In vielen Programmiersprachen ein „Datentyp“

Oft gebraucht für bedingte Anweisungen z.B. in Java, C, PHP, Pascal oder VisualBasic

Logische Operatoren Logische Operatoren verbinden Aussagen zu

neuen (zusammengesetzten) Aussagen Die drei grundlegenden Operatoren sind:

UND ODER NICHT

(fast alle anderen lassen sich aus diesen drei Operatoren zusammensetzen)

AND

Deutsch: UND „sowohl A als auch B“ mathematisches Symbol: ∧ in Java: && (z.B. true && false -> false)

OR

Deutsch: ODER „entweder A oder B oder beides“ mathematisches Symbol: V in Java: ||

NOT

Deutsch: NICHT, Negation „nicht A, also das Gegenteil“

mathematisches Symbol: ¬ in Java: !

XOR

Deutsch: ausschliessendes ODER „entweder A oder B, aber nicht beides“ mathematisches Symbol: ⊻ in Java: ^

Wahrheitstabellen: Wer hat genascht? Boris: „Karsten oder ich waren es.“ Karsten: „Entweder war es Ulf oder ich.“ Ulf: „Entweder hat Boris oder ich nicht genascht.“

B K U

Beispiel: Wer hat genascht? Boris: „Karsten oder ich waren es.“ Karsten: „Entweder war es Ulf oder ich.“ Ulf: „Entweder hat Boris oder ich nicht genascht.“

B K U

0 0 0

1 0 0

0 1 0

1 1 0

0 0 1

1 0 1

0 1 1

1 1 1

Wer hat genascht? Boris: „Karsten oder ich waren es.“ Karsten: „Entweder war es Ulf oder ich.“ Ulf: „Entweder hat Boris oder ich nicht genascht.“

B K U K OR B U XOR K NOT (U XOR B) gleich U XOR

B

(K OR B) AND (U XOR K) AND (U XOR B)

0 0 0

1 0 0

0 1 0

1 1 0

0 0 1

1 0 1

0 1 1

1 1 1

Wer hat genascht? Boris: „Karsten oder ich waren es.“ Karsten: „Entweder war es Ulf oder ich.“ Ulf: „Entweder hat Boris oder ich nicht genascht.“

B K U K OR B U XOR K NOT (U XOR B) gleich U XOR

B

(K OR B) AND (U XOR K) AND (U XOR B)

0 0 0 0 0 0

1 0 0 1 0 1

0 1 0 1 1 0

1 1 0 1 1 1

0 0 1 0 1 1

1 0 1 1 1 0

0 1 1 1 0 1

1 1 1 1 0 0

Wer hat genascht? Boris: „Karsten oder ich waren es.“ Karsten: „Entweder war es Ulf oder ich.“ Ulf: „Entweder hat Boris oder ich nicht genascht.“

B K U K OR B U XOR K NOT (U XOR B) gleich U XOR

B

(K OR B) AND (U XOR K) AND (U XOR B)

0 0 0 0 0 0 0

1 0 0 1 0 1 0

0 1 0 1 1 0 0

1 1 0 1 1 1 1

0 0 1 0 1 1 0

1 0 1 1 1 0 0

0 1 1 1 0 1 0

1 1 1 1 0 0 0

Wer kommt zur Party? Ute: „Entweder kommt Ingrid oder Sonja.“ Sonja: „Entweder kommt Ingrid oder Ute.“ Ingrid: „Es kommen Sonja oder Ute.“

Lösung: Ingrid kommt nicht, Sonja und Ute schon

U S I

Umformungsregeln Assoziativgesetz

(A Λ B) Λ C = A Λ (B Λ C) = A Λ B Λ C(A V B) V C = A V (B V C) = A V B V C

DistributivgesetzA Λ (B V C) = (A Λ B) V (A Λ C)A V (B Λ C) = (A V B) Λ (A V C)

De Morgansche’s Gesetz¬(A V B) = ¬A Λ ¬B¬(A Λ B) = ¬A V ¬B

Doppelte Negation ¬¬A = A

Bsp.:

¬(A V ¬B) = ¬A Λ ¬¬B = ¬A Λ B

Tipp:

Λ =

ΛND

de Morgan'sche Regel

„Morgen abend gibt‘s Pizza und Bier.“

Negation?

Formal:A: es gibt Pizza, B: es gibt BierNegation von A Λ B:

¬(A Λ B) = ¬A V ¬B

A B ¬(A Λ B)

¬A V ¬B

0 0

0 1

1 0

1 1

De Morgan:Das NOT ist wie ein Minus, und Vorzeichen umkehren macht aus einem AND ein OR – oder umgekehrt

de Morgan'sche Regel

„Morgen abend gibt‘s Pizza und Bier.“

Negation?

Formal:A: es gibt Pizza, B: es gibt BierNegation von A Λ B:

¬(A Λ B) = ¬A V ¬B

„Morgen gibt‘s nicht Pizza UND Bier“, bzw.

„Morgen gibt‘s keine Pizza oder kein Bier“

„Morgen gibt‘s nicht Pizza UND Bier“, bzw.

„Morgen gibt‘s keine Pizza oder kein Bier“

A B ¬(A Λ B)

¬A V ¬B

0 0 1 1

0 1 1 1

1 0 1 1

1 1 0 0

Logik in Java

Logische Operationen: AND: && OR: || NOT: !

Boolean: Variable, die entweder wahr oder falsch ist (engl.: true oder false)

z.B.: true && false -> false logischer Vergleich: ==

Achtung! Zuweisung: =