Transcript
3
Aussagenlogik • Rechnen mit Wahrheitswerten: true ( wahr“) und false ( falsch“). ” ” • Die Objekte, mit denen wir hantieren, sind Aussagen, also Dinge, denen wir eindeutig einen Wahrheitswert zuordnen k¨onnen. Zur Bezeichnung f¨ ur Aussagen nehmen wir Großbuchstaben A, B, C, . . . • Die Verkn¨ upfungen von Aussagen liefern neue Aussagen. Art der Verkn¨ upfungen im Folgenden. • Die Negation ist der einfachste Operator, da er nur einen Operanden hat: A ¬A false true true false • Andere Operationen auf {0, 1}. Rechnen ”modulo”: Wenn bei einer Operation der zul¨assige Zahlbereich verlassen wird, dann verschiebt man das Ergebnis wieder in den zul¨assigen Bereich. + 0 1 0 0 1 1 1 0 F¨ ur {0, 1} rechnet man praktisch ”modulo 2”. 1 + 1 = 2 = 0 modulo 2. Diese Art zu rechnen ist f¨ ur praktische Probleme meist nicht sehr hilfreich, aber mathematisch sehr n¨ utzlich! • Maximum und Minimum als Operator auf {0, 1}. max 0 1 0 0 1 1 1 1 und min 0 1 0 0 0 1 0 1 • Konjunktion – Die Und-Verkn¨ upfung“: ” A B A∧B false false false false true false true false false true true true • Oder-Verkn¨ upfung“ – Disjunktion. ” A B A∨B false false false false true true true false true true true true
• Die Implikation ( Aus A folgt B’”): ” A B A⇒B false false true false true true true false false true true true 4 • Eine weitere Verkn¨ upfung (von den 2 = 16 m¨oglichen Verkn¨ upfungen zweier ¨ Aussagen) ist die Aquivalenz : A B A⇔B false false true false true false true false false true true true • Einfachere Gesetzm¨aßigkeiten lassen sich einfach durch Aufstellen der Wahrheitstafeln f¨ ur die vorkommenden Teilausdr¨ ucke zeigen. Z.B. ist f¨ ur beliebige A und B der Ausdruck A ⇔ B gleichwertig mit (A ⇒ B) ∧ (B ⇒ A): A B A ⇒ B B ⇒ A (A ⇒ B) ∧ (B ⇒ A) A ⇔ B false false true true true true true false false false false true true false false true false false true true true true true true Eine Implikation A ⇒ B l¨asst sich auch ausdr¨ ucken als (¬A) ∨ B: A B ¬A (¬A) ∨ B A ⇒ B false false true true true true true false true true true false false false false true true false true true • Rechenregln f¨ ur Wahrheitswerte: – Zwei Kommutativgesetze (kennen wir von + und ·): A∧B = B∧A A∨B = B∨A
(3.1) (3.2)
– Zwei Assoziativgesetze (auch wie bei + und ·): (A ∧ B) ∧ C = A ∧ (B ∧ C) (A ∨ B) ∨ C = A ∨ (B ∨ C)
(3.3) (3.4)
– Zwei (!) Distributivgesetze: (A ∧ B) ∨ C = (A ∨ C) ∧ (B ∨ C) (A ∨ B) ∧ C = (A ∧ C) ∨ (B ∧ C)
(3.5) (3.6)
– Die de morganschen Regeln: ¬(A ∧ B) = (¬A) ∨ (¬B) ¬(A ∨ B) = (¬A) ∧ (¬B)
(3.7) (3.8)
– Weitere Regeln: ¬(¬A) = A A∧A = A A∨A = A
(3.9) (3.10) (3.11)
• Mehrwertige Logik (Fuzzy Logic): Betrachte nicht nur true und false, sondern z.B: true, undetermined und false. Dreiwertige Logik. Allgemeiner: Wahrheitswert a mit 0 ≤ a ≤ 1. Definiere dann die Operatoren allgemeiner: a ∧ b := a · b, ¬a := 1 − a, a ∨ b := a + b − a · b oder a ∧ b := min(a, b), a ∨ b := max(a, b).
Aufgaben 3.1 Best¨atige durch Wahrheitstafeln das erste Distributivgesetz (3.5) und die erste de morgansche Regel (3.7). ¨ 3.2 Zeige die Aquivalenz von A ⇒ B und (¬B) ⇒ (¬A) a) Mittels Wahrheitstafeln b) Durch Umformen (zweckm¨aßig ist hier, die zweite Form in die erste umzuformen, aber andersrum geht’s nat¨ urlich auch). 3.3 Zeige noch einmal, dass A ⇔ B gleichwertig ist zu (B ⇒ A) ∧ (A ⇒ B), diesmal aber mit den Rechenregeln: Setze f¨ ur ⇒ die Formulierung mit ¬ und ∨ ein, und wende die Rechenregeln an, um eine zu A ⇔ B ¨aquivalente Formel zu bekommen, die wieder nur ¬, ∧ und ∨ verwendet. 3.4 Ein logischer Ausdruck, der (unabh¨angig von den Werten der darin vorkommenden Variablen) immer den Wert true hat, heißt Tautologie — z.B. der Ausdruck A ∨ (¬A). Welche der folgenden Aussagen sind Tautologien? a) (A ∧ C) ∨ (A ∧ ¬C) b) ¬(A ∧ ¬A) ∨ (B ∧ C) c) ((A ∨ B) ∧ ¬(¬A ∧ ¬B)) ∧ ((A ∨ ¬B) ∧ ¬(¬A ∧ B)) d) (A ∨ B) ∧ (¬A ∨ B) ∧ (A ∨ ¬B) ∧ (¬A ∨ ¬B) e) (A ∧ B) ∨ (A ∧ C) ∨ (B ∧ C) 3.5 Bei einem Verstoß gegen ein mathematisches Gesetz (welches, ist hier egal) kommen drei stadtbekannte Gauner A, B und C als T¨ater infrage — einer alleine oder mehrere zusammen. Der Polizei liegen zwei Aussagen vor:
• Wenn A unschuldig ist, ist B schuldig. • Wenn B unschuldig ist, sind sowohl A als auch C schuldig. Da die Polizei ihre Informanten kennt, weiß sie, dass die erste Aussage wahr, die zweite Aussage aber falsch ist. Wer ist’s gewesen? Hier gibt es mal wieder verschiedene L¨osungswege – man kann z.B. logische Ausdr¨ ucke f¨ ur die Aussagen aufstellen und umformen, man kann die Aufgabe aber auch graphisch l¨osen, indem man sich ein Venn-Diagramm f¨ ur drei Mengen A, B, C aufmalt:
Nun legt man fest, dass der Bereich innerhalb von z.B. A bedeutet, dass A schuldig ist etc., hat so alle m¨oglichen Kombinationen von Schuld/Unschuld der drei Kandidaten vor sich und kann mittels der Aussagen solange Bereiche ausschließen, bis nur noch ein Feld u ¨brig ist. 3.6 Wenn man im Ganovenr¨atsel den L¨osungsweg mit dem Venn-Diagramm r¨ uckw¨arts geht, kann man recht einfach ein eigenes Logikr¨atsel erfinden. Man beginnt mit einem Venn-Diagramm f¨ ur drei Mengen A, B und C und w¨ahlt dann einen beliebigen Bereich aus. Jetzt muss man nach nicht zu einfachen Aussagen suchen, die daf¨ ur sorgen, das alle Bereiche außerhalb des gew¨ahlten Bereichs nicht mehr in Frage kommen. Sobald man die logischen Ausdr¨ ucke zusammengestellt hat, l¨asst man sich eine nette Geschichte dazu einfallen, indem man jeder Menge eine Bedeutung gibt (z.B. A = Der FC Bayern ” wird Meister.“). Design your Logikr¨atsel!
