Boolesche Algebra: Unterschied zwischen den Versionen
(→De Morgansche Gesetze) |
|||
| (37 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| − | Die '''boolesche Algebra''' ist eine algebraische Struktur und beschreibt die Operationen '''UND''', '''ODER''' und '''NICHT''', | + | Die '''boolesche Algebra''' ist eine algebraische Struktur und beschreibt die Operationen '''UND''', '''ODER''' und '''NICHT''', die auf logische Aussagen angewendet werden können. Die Kenntnis dieser Struktur ist hilfreich für den Umgang mit dem [[Datentyp]] [[boolean]]. |
==Die booleschen Operatoren== | ==Die booleschen Operatoren== | ||
| Zeile 23: | Zeile 23: | ||
Die '''Disjunktion''' ist eine der grundlegenden logischen Verknüpfungen der Aussagenlogik. Die Disjunktion zweier Aussagen ''A'' und ''B'' ist genau dann wahr, wenn mindestens eine der Aussagen ''A'' '''oder''' ''B'' wahr ist. Das mathematische Symbol ist '''∨'''. In [[Java]] wird das '''OR''' durch '''||''' repräsentiert. | Die '''Disjunktion''' ist eine der grundlegenden logischen Verknüpfungen der Aussagenlogik. Die Disjunktion zweier Aussagen ''A'' und ''B'' ist genau dann wahr, wenn mindestens eine der Aussagen ''A'' '''oder''' ''B'' wahr ist. Das mathematische Symbol ist '''∨'''. In [[Java]] wird das '''OR''' durch '''||''' repräsentiert. | ||
| + | [[Datei:venn_or.png|220x160px|right]] | ||
{| class = "wikitable" width=50% align="center" | {| class = "wikitable" width=50% align="center" | ||
| Zeile 35: | Zeile 36: | ||
| ''true'' ||''true'' || ''true'' | | ''true'' ||''true'' || ''true'' | ||
|} | |} | ||
| − | |||
| − | |||
===Negation (NOT)=== | ===Negation (NOT)=== | ||
| − | Die '''Negation''' ist eine wichtige Operation in der Aussagenlogik. Die Negation einer Aussage ''A'' führt zur ihrer Verneinung | + | Die '''Negation''' ist eine wichtige Operation in der Aussagenlogik. Die Negation einer Aussage ''A'' führt zur ihrer Verneinung. Das heißt aus einer wahren Aussage wird eine falsche Aussage und umgekehrt. Das mathematische Symbol ist '''¬'''. In [[Java]] wird das '''NOT''' durch '''!''' repräsentiert. |
{| class = "wikitable" width=50% align="center" | {| class = "wikitable" width=50% align="center" | ||
| Zeile 53: | Zeile 52: | ||
Die '''Kontravalenz''' ist eine erweiterte logische Verknüpfung in der Aussagenlogik. Die Kontravalenz zweier Aussagen ''A'' und ''B'' ist genau dann wahr, wenn '''entweder''' ''A'' '''oder''' ''B'', aber nicht beide wahr sind. Das mathematische Symbol ist '''⊕'''. In [[Java]] wird das '''XOR''' durch '''^''' repräsentiert. | Die '''Kontravalenz''' ist eine erweiterte logische Verknüpfung in der Aussagenlogik. Die Kontravalenz zweier Aussagen ''A'' und ''B'' ist genau dann wahr, wenn '''entweder''' ''A'' '''oder''' ''B'', aber nicht beide wahr sind. Das mathematische Symbol ist '''⊕'''. In [[Java]] wird das '''XOR''' durch '''^''' repräsentiert. | ||
| + | [[Datei:venn_xor.png|220x160px|right]] | ||
{| class = "wikitable" width=50% align="center" | {| class = "wikitable" width=50% align="center" | ||
| Zeile 65: | Zeile 65: | ||
| ''true'' ||''true'' || ''false'' | | ''true'' ||''true'' || ''false'' | ||
|} | |} | ||
| − | |||
| − | |||
===Implikation=== | ===Implikation=== | ||
| − | Die '''Implikation''' ist eine erweiterte logische Verknüpfung in der Aussagenlogik. Die Implikation zweier Aussagen ''A'' und ''B'' ist genau dann wahr, wenn ''A'' falsch oder ''B'' wahr ist. Das mathematische Symbol ist '''⇒'''. Die Implikation ist | + | Die '''Implikation''' ist eine erweiterte logische Verknüpfung in der Aussagenlogik. Die Implikation zweier Aussagen ''A'' und ''B'' ist genau dann wahr, wenn ''A'' falsch oder ''B'' wahr ist. Das mathematische Symbol ist '''⇒'''. Die Implikation ist semantisch äquivalent zu ¬A ∨ B. In [[Java]] gibt es keinen Implikationsoperator. |
| + | |||
| + | Eine Implikation wird im Deutschen meistens durch "'''wenn''' ''A'', '''dann''' ''B''" ausgedrückt. Es handelt sich hierbei um eine einfache Folgerung. Aus einer falschen Ausgangsaussage '''A''' lässt sich alles folgern, daher kann die Gesamtaussage nicht falsch werden. | ||
| + | [[Datei:venn_implikation.png|220x160px|right]] | ||
{| class = "wikitable" width=50% align="center" | {| class = "wikitable" width=50% align="center" | ||
| Zeile 83: | Zeile 84: | ||
| ''true'' ||''true'' || ''true'' | | ''true'' ||''true'' || ''true'' | ||
|} | |} | ||
| − | |||
| − | |||
===Äquivalenz (XNOR)=== | ===Äquivalenz (XNOR)=== | ||
| − | Die '''Äquivalenz''' ist eine erweiterte logische Verknüpfung in der Aussagenlogik. Die Äquivalenz zweier Aussagen ''A'' und ''B'' ist genau dann wahr, wenn ''A'' und ''B'' wahr oder ''A'' und ''B'' falsch sind. Das mathematische Symbol ist '''⇔'''. Die Äquivalenz ist | + | Die '''Äquivalenz''' ist eine erweiterte logische Verknüpfung in der Aussagenlogik. Die Äquivalenz zweier Aussagen ''A'' und ''B'' ist genau dann wahr, wenn ''A'' und ''B'' wahr oder ''A'' und ''B'' falsch sind. Das mathematische Symbol ist '''⇔'''. Die Äquivalenz ist semantisch äquivalent zu A ∧ B ∨ ¬A ∧ ¬B. In [[Java]] gibt es keinen Operator hierfür. |
| + | |||
| + | Die Äquivalenz wird im Deutschen meistens durch "'''genau dann''' ''A'', '''wenn''' ''B''" ausgedrückt. "Genau" heißt immer und nur unter dieser Bedingung. '''A''' gilt genau dann, wenn '''B''' gilt. '''A''' und '''B''' sind äquivalent, also austauschbar. Das heißt die vorherige Aussage gilt auch anders herum: '''B''' gilt genau dann, wenn '''A''' gilt. | ||
| + | [[Datei:venn_äquivalenz.png|right]] | ||
{| class = "wikitable" width=50% align="center" | {| class = "wikitable" width=50% align="center" | ||
| Zeile 101: | Zeile 103: | ||
| ''true'' ||''true'' || ''true'' | | ''true'' ||''true'' || ''true'' | ||
|} | |} | ||
| − | |||
| − | |||
==Peano-Axiome (erweitertes Wissen)== | ==Peano-Axiome (erweitertes Wissen)== | ||
| + | |||
| + | Wenn keine Klammern vorhanden sind, gilt folgende Reihenfolge: Am stärksten bindet Negation, danach Konjunktion und danach Disjunktion. | ||
===Kommutativgesetze=== | ===Kommutativgesetze=== | ||
| Zeile 112: | Zeile 114: | ||
(1') ''A'' ∨ ''B'' ≡ ''B'' ∨ ''A'' | (1') ''A'' ∨ ''B'' ≡ ''B'' ∨ ''A'' | ||
| + | Das Vertauschen der Argumente ''A'' und ''B'' ist hier möglich, ohne dass sich das Ergebnis der Operation ändert. | ||
===Assoziativgesetze=== | ===Assoziativgesetze=== | ||
| Zeile 119: | Zeile 122: | ||
(2') (''A'' ∨ ''B'') ∨ ''C'' ≡ ''A'' ∨ (''B'' ∨ ''C'') | (2') (''A'' ∨ ''B'') ∨ ''C'' ≡ ''A'' ∨ (''B'' ∨ ''C'') | ||
| + | Die Klammerung der oben durchgeführten Operationen hat keinen Einfluss auf das Ergebnis. | ||
===Idempotenzgesetze=== | ===Idempotenzgesetze=== | ||
| Zeile 126: | Zeile 130: | ||
(3') ''A'' ∨ ''A'' ≡ ''A'' | (3') ''A'' ∨ ''A'' ≡ ''A'' | ||
| + | Die Eigenschaften des Arguments ''A'' bleiben bestehen, auch wenn dieses mit sich selbst verknüpft wird. | ||
===Distributivgesetze=== | ===Distributivgesetze=== | ||
| + | |||
(4) ''A'' ∧ (''B'' ∨ ''C'') ≡ (''A'' ∧ ''B'') ∨ (''A'' ∧ ''C'') | (4) ''A'' ∧ (''B'' ∨ ''C'') ≡ (''A'' ∧ ''B'') ∨ (''A'' ∧ ''C'') | ||
(4') ''A'' ∨ (''B'' ∧ ''C'') ≡ (''A'' ∨ ''B'') ∧ (''A'' ∨ ''C'') | (4') ''A'' ∨ (''B'' ∧ ''C'') ≡ (''A'' ∨ ''B'') ∧ (''A'' ∨ ''C'') | ||
| + | Auswirkung des Auflösens von Klammern um Verknüpfungen von Operationen; ähnlich dem "Ausmultiplizieren" in der Schulmathematik. | ||
===Neutralitätsgesetze=== | ===Neutralitätsgesetze=== | ||
| Zeile 139: | Zeile 146: | ||
(5') ''A'' ∨ ''false'' ≡ ''A'' | (5') ''A'' ∨ ''false'' ≡ ''A'' | ||
| + | Der Wert des Argumentes ''A'' wird durch die oben ausgeführten Operationen nicht verändert. | ||
===Extremalgesetze=== | ===Extremalgesetze=== | ||
| Zeile 146: | Zeile 154: | ||
(6') ''A'' ∨ ''true'' ≡ ''true'' | (6') ''A'' ∨ ''true'' ≡ ''true'' | ||
| + | Das Ergebnis der oben beschriebenen Operationen ist unabhängig vom Wert des Arguments ''A''. | ||
===Doppelnegationsgesetz=== | ===Doppelnegationsgesetz=== | ||
| − | (7) ¬¬''A'' ≡ ''A'' | + | (7) ¬(¬''A'') ≡ ''A'' |
| + | "Doppelte Verneinung": Der Wert von ''A'' wird durch zweimaliges Ausführen des ¬ -Operators nicht beeinflusst. | ||
===De Morgansche Gesetze=== | ===De Morgansche Gesetze=== | ||
| − | |||
| − | (8')¬(''A'' ∨ ''B'') ≡ ¬''A'' ∧ ¬''B'' | + | (8) ¬(''A'' ∧ ''B'') ≡ ¬''A'' ∨ ¬''B'' |
| + | |||
| + | (8') ¬(''A'' ∨ ''B'') ≡ ¬''A'' ∧ ¬''B'' | ||
| + | |||
| + | Alltagsbeispiele: | ||
| + | |||
| + | (8) Peter hat sich einen Tee zubereitet, in dem nicht Zitronensaft und Zucker enthalten sind. | ||
| + | Beschreibe die Boolesche Variable '''A''' den Zustand, dass Zucker im Tee ist und '''B''' den Zustand, dass sich Zitronensaft im Tee befindet. Dann lautet die Antwort auf die Frage, ob Peters Tee Zucker und Zitronensaft (beides auf einmal) beinhaltet (also '''A''' = '''true''' und '''B''' = '''true''': | ||
| + | |||
| + | ¬(''A'' ∧ ''B'') = ¬(''true'' ∧ ''true'') = ¬''true'' =''false''. In Peters Tee ist kein Zitronensaft und Zucker. | ||
| + | |||
| + | Diese Aussage ist äquivalent zu der Aussage "In Peters Tee ist kein Zitronensaft oder kein Zucker" (also mindestens eins von beiden ist nicht enthalten). Das heißt bei gleicher Belegung der Variablen erhält man das gleiche Ergebnis: | ||
| + | |||
| + | ¬''A'' ∨ ¬''B'' = ¬''true'' ∨ ¬''true'' = ''false'' ∨ ''false'' = false. | ||
| + | |||
| + | Damit die jeweilige Aussage wahr ist, muss mindestens eine der beiden Zutaten nicht in Peters Tee enthalten sein. | ||
| + | |||
| + | |||
| + | (8') Petras Kaffee enthält nicht Milch oder Zucker. Die Variable '''A''' beschreibe den Zustand, dass der Kaffee Milch enthält und '''B''', dass Zucker enthalten ist. Die Antwort auf die Frage, ob der Kaffee Milch aber keinen Zucker enthält (also '''A''' = '''true''' und '''B''' = '''false''') lautet dementsprechend: | ||
| + | |||
| + | ¬(''A'' ∨ ''B'') =¬(''true'' ∨ ''false'') = ¬''true'' = ''false''. In Petras Kaffee ist weder Milch noch Zucker. | ||
| + | |||
| + | Diese Aussage ist äquivalent zu "Petras Kaffee enthält keine Milch und keinen Zucker." Das heißt bei gleicher Belegung der Variablen kommt das gleiche Ergebnis heraus: | ||
| + | |||
| + | ¬''A'' ∧ ¬''B'' = ¬''true'' ∧ ¬''false'' = ''false'' ∧ ''true'' = ''false''. | ||
===Komplementärgesetze=== | ===Komplementärgesetze=== | ||
| + | |||
(9) ''A'' ∧ ¬''A'' ≡ ''false'' | (9) ''A'' ∧ ¬''A'' ≡ ''false'' | ||
(9') ''A'' ∨ ¬''A'' ≡ ''true'' | (9') ''A'' ∨ ¬''A'' ≡ ''true'' | ||
| + | |||
| + | Es können nicht gleichzeitig ''A'' und die Negation von ''A'' gelten: Beispielsweise kann der Himmel nicht gleichzeitig blau und nicht-blau sein (9). | ||
| + | Allerdings ist der Himmel entweder blau oder nicht-blau gefärbt (9'). | ||
===Dualitätsgesetze=== | ===Dualitätsgesetze=== | ||
| − | |||
| − | (10')¬ | + | (10) ¬false ≡ true |
| + | |||
| + | (10') ¬true ≡ false | ||
| + | |||
| + | Der Wert '''true''' ist das Komplement zu '''false'''. Ist eine Aussage nicht-wahr, so ist sie falsch. Umgekehrt gilt für eine nicht-falsche Aussage, dass sie wahr sein muss. | ||
Aktuelle Version vom 9. November 2016, 14:57 Uhr
Die boolesche Algebra ist eine algebraische Struktur und beschreibt die Operationen UND, ODER und NICHT, die auf logische Aussagen angewendet werden können. Die Kenntnis dieser Struktur ist hilfreich für den Umgang mit dem Datentyp boolean.
Inhaltsverzeichnis
Die booleschen Operatoren
Konjunktion (AND)
Die Konjunktion ist eine der grundlegenden logischen Verknüpfungen der Aussagenlogik. Die Konjunktion zweier Aussagen A und B ist genau dann wahr, wenn A und B (sowohl als auch) wahr sind. Das mathematische Symbol ist ∧. In Java wird das AND durch && repräsentiert.
| A | B | A ∧ B |
|---|---|---|
| false | false | false |
| false | true | false |
| true | false | false |
| true | true | true |
Disjunktion (OR)
Die Disjunktion ist eine der grundlegenden logischen Verknüpfungen der Aussagenlogik. Die Disjunktion zweier Aussagen A und B ist genau dann wahr, wenn mindestens eine der Aussagen A oder B wahr ist. Das mathematische Symbol ist ∨. In Java wird das OR durch || repräsentiert.
| A | B | A ∨ B |
|---|---|---|
| false | false | false |
| false | true | true |
| true | false | true |
| true | true | true |
Negation (NOT)
Die Negation ist eine wichtige Operation in der Aussagenlogik. Die Negation einer Aussage A führt zur ihrer Verneinung. Das heißt aus einer wahren Aussage wird eine falsche Aussage und umgekehrt. Das mathematische Symbol ist ¬. In Java wird das NOT durch ! repräsentiert.
| A | ¬A |
|---|---|
| false | true |
| true | false |
Kontravalenz (XOR)
Die Kontravalenz ist eine erweiterte logische Verknüpfung in der Aussagenlogik. Die Kontravalenz zweier Aussagen A und B ist genau dann wahr, wenn entweder A oder B, aber nicht beide wahr sind. Das mathematische Symbol ist ⊕. In Java wird das XOR durch ^ repräsentiert.
| A | B | A ⊕ B |
|---|---|---|
| false | false | false |
| false | true | true |
| true | false | true |
| true | true | false |
Implikation
Die Implikation ist eine erweiterte logische Verknüpfung in der Aussagenlogik. Die Implikation zweier Aussagen A und B ist genau dann wahr, wenn A falsch oder B wahr ist. Das mathematische Symbol ist ⇒. Die Implikation ist semantisch äquivalent zu ¬A ∨ B. In Java gibt es keinen Implikationsoperator.
Eine Implikation wird im Deutschen meistens durch "wenn A, dann B" ausgedrückt. Es handelt sich hierbei um eine einfache Folgerung. Aus einer falschen Ausgangsaussage A lässt sich alles folgern, daher kann die Gesamtaussage nicht falsch werden.
| A | B | A ⇒ B |
|---|---|---|
| false | false | true |
| false | true | true |
| true | false | false |
| true | true | true |
Äquivalenz (XNOR)
Die Äquivalenz ist eine erweiterte logische Verknüpfung in der Aussagenlogik. Die Äquivalenz zweier Aussagen A und B ist genau dann wahr, wenn A und B wahr oder A und B falsch sind. Das mathematische Symbol ist ⇔. Die Äquivalenz ist semantisch äquivalent zu A ∧ B ∨ ¬A ∧ ¬B. In Java gibt es keinen Operator hierfür.
Die Äquivalenz wird im Deutschen meistens durch "genau dann A, wenn B" ausgedrückt. "Genau" heißt immer und nur unter dieser Bedingung. A gilt genau dann, wenn B gilt. A und B sind äquivalent, also austauschbar. Das heißt die vorherige Aussage gilt auch anders herum: B gilt genau dann, wenn A gilt.
| A | B | A ⇔ B |
|---|---|---|
| false | false | true |
| false | true | false |
| true | false | false |
| true | true | true |
Peano-Axiome (erweitertes Wissen)
Wenn keine Klammern vorhanden sind, gilt folgende Reihenfolge: Am stärksten bindet Negation, danach Konjunktion und danach Disjunktion.
Kommutativgesetze
(1) A ∧ B ≡ B ∧ A
(1') A ∨ B ≡ B ∨ A
Das Vertauschen der Argumente A und B ist hier möglich, ohne dass sich das Ergebnis der Operation ändert.
Assoziativgesetze
(2) (A ∧ B) ∧ C ≡ A ∧ (B ∧ C)
(2') (A ∨ B) ∨ C ≡ A ∨ (B ∨ C)
Die Klammerung der oben durchgeführten Operationen hat keinen Einfluss auf das Ergebnis.
Idempotenzgesetze
(3) A ∧ A ≡ A
(3') A ∨ A ≡ A
Die Eigenschaften des Arguments A bleiben bestehen, auch wenn dieses mit sich selbst verknüpft wird.
Distributivgesetze
(4) A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)
(4') A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)
Auswirkung des Auflösens von Klammern um Verknüpfungen von Operationen; ähnlich dem "Ausmultiplizieren" in der Schulmathematik.
Neutralitätsgesetze
(5) A ∧ true ≡ A
(5') A ∨ false ≡ A
Der Wert des Argumentes A wird durch die oben ausgeführten Operationen nicht verändert.
Extremalgesetze
(6) A ∧ false ≡ false
(6') A ∨ true ≡ true
Das Ergebnis der oben beschriebenen Operationen ist unabhängig vom Wert des Arguments A.
Doppelnegationsgesetz
(7) ¬(¬A) ≡ A
"Doppelte Verneinung": Der Wert von A wird durch zweimaliges Ausführen des ¬ -Operators nicht beeinflusst.
De Morgansche Gesetze
(8) ¬(A ∧ B) ≡ ¬A ∨ ¬B
(8') ¬(A ∨ B) ≡ ¬A ∧ ¬B
Alltagsbeispiele:
(8) Peter hat sich einen Tee zubereitet, in dem nicht Zitronensaft und Zucker enthalten sind. Beschreibe die Boolesche Variable A den Zustand, dass Zucker im Tee ist und B den Zustand, dass sich Zitronensaft im Tee befindet. Dann lautet die Antwort auf die Frage, ob Peters Tee Zucker und Zitronensaft (beides auf einmal) beinhaltet (also A = true und B = true:
¬(A ∧ B) = ¬(true ∧ true) = ¬true =false. In Peters Tee ist kein Zitronensaft und Zucker.
Diese Aussage ist äquivalent zu der Aussage "In Peters Tee ist kein Zitronensaft oder kein Zucker" (also mindestens eins von beiden ist nicht enthalten). Das heißt bei gleicher Belegung der Variablen erhält man das gleiche Ergebnis:
¬A ∨ ¬B = ¬true ∨ ¬true = false ∨ false = false.
Damit die jeweilige Aussage wahr ist, muss mindestens eine der beiden Zutaten nicht in Peters Tee enthalten sein.
(8') Petras Kaffee enthält nicht Milch oder Zucker. Die Variable A beschreibe den Zustand, dass der Kaffee Milch enthält und B, dass Zucker enthalten ist. Die Antwort auf die Frage, ob der Kaffee Milch aber keinen Zucker enthält (also A = true und B = false) lautet dementsprechend:
¬(A ∨ B) =¬(true ∨ false) = ¬true = false. In Petras Kaffee ist weder Milch noch Zucker.
Diese Aussage ist äquivalent zu "Petras Kaffee enthält keine Milch und keinen Zucker." Das heißt bei gleicher Belegung der Variablen kommt das gleiche Ergebnis heraus:
¬A ∧ ¬B = ¬true ∧ ¬false = false ∧ true = false.
Komplementärgesetze
(9) A ∧ ¬A ≡ false
(9') A ∨ ¬A ≡ true
Es können nicht gleichzeitig A und die Negation von A gelten: Beispielsweise kann der Himmel nicht gleichzeitig blau und nicht-blau sein (9). Allerdings ist der Himmel entweder blau oder nicht-blau gefärbt (9').
Dualitätsgesetze
(10) ¬false ≡ true
(10') ¬true ≡ false
Der Wert true ist das Komplement zu false. Ist eine Aussage nicht-wahr, so ist sie falsch. Umgekehrt gilt für eine nicht-falsche Aussage, dass sie wahr sein muss.
