Die Regeln der Logik bilden die Grundlage mathematischen Argumentierens
Anwendungen
- Schaltkreiseentwurf
- Programmiersprachen
- Verifikation
- …
Definition: Aussagen
Eine Aussage ist ein sprachliches Gebilde, dem genau einer der Wahrheitswerte wahr (w) oder falsch (f) zugeordnet ist.
Bsp.
- 2 ist eine gerade Zahl – wahre Aussage
- Bananen sind blau – falsche Aussage
- nachts ist es kälter als draußen – keine Aussage
Definition: Verknüpfung von Aussagen
Mit Hilfe logischer Operatoren erhält man neue Aussage aus vorhandenen. Sind A und B Aussagen, so erhält man folgende Aussagen:
„nicht A“ – A ist falsch = nicht A
„Negation“ ¬A ↔‾A
„A und B “ – A und B sind beide wahr
„Konjunktion“ A ∧ B ↔ A ⋅ B
„A oder B“ – A oder B oder beide sind wahr
„Disjunktion“ A ∨ B ↔ A + B
„A xor B“ – entweder A oder B sind wahr
„Exklusives Oder“ A ∨ B ↔ A ⊕ B
„A impliziert B“ – aus A folgt B
„Implikation“ – A ⇒ A ↔ A → B
ist immer wahr, falls A falsch ist
ist nur falsch, falls A wahr und B falsch ist
„A ist äquivalent zu B“ „A genau dann wenn B“
„Äquivalenz“ – A ⇔ B
A und B verhalten sich genau gleich
Wahrheitstafeln – überprüfen der Wahrheitswerte von verknüpften Aussagen mit 0 für falsch und 1 für wahr („positive Logik“)
A – B – ¬A – A ∧ B – A ∨ B – A ⊕ B – A ⇒ B – A ⇔ B
0 0 1 0 0 0 1 1
0 1 1 0 1 1 1 0
1 0 0 0 1 1 0 0
1 1 0 1 1 0 1 1
Reihenfolge der Ausführung logischer Operatoren wird festgelegt über Prioritäten und Klammern
Operatoren nach absteigender Prio:
¬ , ∧ , (∨ , ⊕), (⇒, ⇔)
Bsp. A ∧ B ⇒ ¬A ∨ B ⇔ (A ∧ B) ⇒ ((¬A) ∨ B)
A, B, C – Aussagevariablen
w und f – logische Konstanten
logische Formel: Verknüpfung von log. Konstanten und Variablen
durch Einsetzen konkreter Aussagen ergibt sich eine zusammengesetze Aussage
Definition: Tautologie
Beim Einsetzen konkreter Aussagen ergibt sich unabhängig von den konkreten Wahrheitswerten immer eine wahre Aussage!
Definition: Widerspruch
Beim Einsetzen konkreter Aussagen ergibt sich unabhängig von den konkreten Wahrheitswerten immer eine falsche Aussage!
Folgende Formeln sind Tautologien:
Assoziativgesetz – Klammern verschieben
(A ∨ B) ∨ C ⇔ A ∨ (B ∨ C)
(A ∧ B) ∧ C ⇔ A ∧ (B ∧ C)
Kommutativgesetz – vertauschen von Elementen
A ∧ B ⇔ B ∧ A
A ∨ B ⇔ B ∨ A
Distributivgesetz – Klammern ausmultiplizieren
A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C)
A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C)
Identitätsgesetz – nur für Aussagen
A ∨ f ⇔ A – A oder f / A plus 0
A ∧ w ⇔ A – A und w / A * 1
Komplementgesetz
A ∨ ¬A ⇔ w
Satz vom ausgeschlosennen Dritten („Sein oder nicht sein“)
A ∧ ¬A ⇔ f
Satz vom Widerspruch („etwas kann ncith glz. wahr und flasch sein“)
De Morgan’sche Gesetze
¬(A ∨ B) ¬A ∧ ¬B
wenn ich A oder B nicht will, will ich beide nicht
¬(A ∧ B) ¬A ∨ ¬B
wenn ich A und B nicht will, will A nicht oder B nicht
Indempotenz
A ∨ A ⇔ A (ein A „wegkürzen“)
A ∧ A ⇔ A
Doppelte Verneinung
¬(¬A) ⇔ A (nicht nicht A = A)
Kontraposition („Verneinen und Umdrehen“)
A ⇒ B ⇔ (¬B ¬A)