Gesetze von Morgan

Die Morgan-Augen sind in der Aussagenlogik verwendete Schlußregeln, die festlegen, was das Ergebnis der Ablehnung einer Disjunktion und einer Konjunktion von Aussagen oder Aussagenvariablen ist. Diese Gesetze wurden vom Mathematiker Augustus De Morgan definiert.

Die Gesetze von Morgan stellen ein sehr nützliches Werkzeug dar, um die Gültigkeit eines mathematischen Denkens zu demonstrieren. Später wurden sie vom Mathematiker George Boole im Rahmen des Mengenbegriffs verallgemeinert.

Diese von Boole gemachte Verallgemeinerung entspricht vollständig Morgans Anfangsgesetzen, wurde jedoch speziell für Mengen und nicht für Sätze entwickelt. Diese Verallgemeinerung ist auch als Morgans Gesetze bekannt.

Überprüfung der Aussagenlogik

Bevor wir uns ansehen, was Morgans Gesetze genau sind und wie sie angewendet werden, sollten wir uns einige Grundbegriffe der Aussagenlogik merken. (Weitere Einzelheiten finden Sie im Artikel über Aussagenlogik).

Auf dem Gebiet der mathematischen (oder aussagenlogischen) Logik ist eine Folgerung eine Schlussfolgerung, die aus einer Reihe von Prämissen oder Hypothesen hervorgeht. Diese Schlussfolgerung führt zusammen mit den oben genannten Prämissen zu einer so genannten mathematischen Argumentation.

Diese Argumentation muss nachgewiesen oder geleugnet werden können. das heißt, dass nicht alle Schlussfolgerungen oder Schlussfolgerungen in einer mathematischen Argumentation gültig sind.

Irrtum

Eine falsche Folgerung, die von bestimmten Annahmen ausgeht, von denen angenommen wird, dass sie wahr sind, wird als Irrtum bezeichnet. Irrtümer haben die Besonderheit, Argumente zu sein, die richtig erscheinen, aber mathematisch gesehen nicht.

Die Aussagenlogik ist verantwortlich für die präzise Entwicklung und Bereitstellung von Methoden, mit denen man eine mathematische Argumentation ohne Mehrdeutigkeit validieren oder widerlegen kann. das heißt, eine gültige Schlussfolgerung aus den Räumlichkeiten ziehen. Diese Methoden sind als Inferenzregeln bekannt, zu denen Morgans Gesetze gehören.

Vorschläge

Die wesentlichen Elemente der Aussagenlogik sind Aussagen. Aussagen sind Aussagen, über die man sagen kann, ob sie gültig sind oder nicht, aber dass sie nicht gleichzeitig wahr oder falsch sein können. In dieser Angelegenheit sollte es keine Mehrdeutigkeit geben.

So wie Zahlen durch Addition, Subtraktion, Multiplikation und Division kombiniert werden können, können die Sätze mit Hilfe der bekannten logischen Konnektivität (oder Konnektoren) bedient werden: Negation (, "no"), Disjunktion (V, "O"), Konjunktion (Ʌ, "und"), bedingt (→, "wenn ..., dann ...") und bikonditional (↔, "ja und nur wenn").

Um allgemeiner zu arbeiten, betrachten wir anstelle spezifischer Sätze Satzvariablen, die beliebige Sätze darstellen und normalerweise durch Kleinbuchstaben p, q, r, s usw. bezeichnet werden.

Eine Aussagenformel ist eine Kombination von Aussagenvariablen über einige der logischen Zusammenhänge. Mit anderen Worten, es ist eine Zusammensetzung von Aussagenvariablen. Sie werden normalerweise mit griechischen Buchstaben bezeichnet.

Es wird gesagt, dass eine Satzformel logisch eine andere impliziert, wenn die letztere jedes Mal wahr ist, wenn die erste wahr ist. Dies wird bezeichnet durch:

Wenn die logische Implikation zwischen zwei Aussagenformeln wechselseitig ist - das heißt, wenn die vorherige Implikation auch in der entgegengesetzten Richtung gültig ist -, werden die Formeln als logisch äquivalent bezeichnet und mit bezeichnet

Logische Äquivalenz ist eine Art Gleichheit zwischen Aussagenformeln und ermöglicht es, diese bei Bedarf durch die anderen zu ersetzen.

Gesetze von Morgan

Morgans Gesetze bestehen aus zwei logischen Äquivalenzen zwischen zwei Satzformen, nämlich:

Diese Gesetze erlauben es, die Negation einer Disjunktion oder Konjunktion als Negation der beteiligten Variablen zu trennen.

Der erste kann wie folgt gelesen werden: Die Verneinung einer Disjunktion ist gleich der Konjunktion der Verneinungen. Und der zweite lautet so: Die Verneinung einer Konjunktion ist die Disjunktion der Verneinungen.

Mit anderen Worten, die Disjunktion zweier Aussagenvariablen zu leugnen, ist gleichbedeutend mit der Konjunktion der Negationen beider Variablen. Ebenso ist das Leugnen der Konjunktion zweier Satzvariablen gleichbedeutend mit der Disjunktion der Negationen beider Variablen.

Wie bereits erwähnt, hilft die Substitution dieser logischen Äquivalenz, wichtige Ergebnisse zusammen mit den anderen bestehenden Inferenzregeln zu demonstrieren. Mit diesen können Sie viele Aussagenformeln vereinfachen, so dass die Arbeit mit ihnen nützlicher ist.

Das Folgende ist ein Beispiel eines mathematischen Beweises unter Verwendung von Inferenzregeln unter diesen Morgans Gesetzen. Insbesondere wird gezeigt, dass die Formel:

ist gleichbedeutend mit:

Letzteres ist einfacher zu verstehen und zu entwickeln.

Vorführung

Erwähnenswert ist, dass die Gültigkeit von Morgans Gesetzen mathematisch nachgewiesen werden kann. Eine Möglichkeit besteht darin, Ihre Wahrheitstabellen zu vergleichen.

Setzt

Dieselben Folgerungsregeln und Logikbegriffe, die auf Sätze angewendet werden, können auch unter Berücksichtigung von Mengen entwickelt werden. Dies ist die sogenannte Boolesche Algebra nach dem Mathematiker George Boole.

Um die Fälle zu differenzieren, ist es notwendig, die Notation zu ändern und in Mengen zu übertragen, alle Begriffe, die bereits von der Aussagenlogik gesehen wurden.

Ein Set ist eine Sammlung von Objekten. Die Mengen werden mit Großbuchstaben A, B, C, X, ... und die Elemente einer Menge mit Kleinbuchstaben a, b, c, x usw. bezeichnet. Wenn ein Element a zu einer Menge X gehört, wird es bezeichnet durch:

Wenn es nicht zu X gehört, lautet die Notation:

Die Art der Darstellung der Mengen besteht darin, ihre Elemente in Tasten zu platzieren. Zum Beispiel wird die Menge der natürlichen Zahlen dargestellt durch:

Mengen können auch dargestellt werden, ohne eine explizite Liste ihrer Elemente zu schreiben. Sie können in der Form {:} ausgedrückt werden. Die beiden Punkte lauten "so dass". Eine Variable, die die Elemente der Menge darstellt, wird links von den beiden Punkten platziert, und die Eigenschaft oder Bedingung, die sie erfüllen, wird rechts davon platziert. Das ist:

Zum Beispiel kann die Menge von ganzen Zahlen größer als -4 ausgedrückt werden als:

Oder gleichwertig und abgekürzt:

In ähnlicher Weise stellen die folgenden Ausdrücke die Mengen von geraden bzw. ungeraden Zahlen dar:

Vereinigung, Schnittmenge und Ergänzungen von Mengen

Als nächstes werden wir die Analoga des logischen Zusammenhangs im Fall von Mengen sehen, die Teil der Grundoperationen zwischen Mengen sind.

Union und Kreuzung

Die Vereinigung und der Schnittpunkt von Mengen werden folgendermaßen definiert:

Betrachten Sie zum Beispiel die Mengen:

Dann müssen Sie:

Komplement

Das Komplement einer Menge wird durch die Elemente gebildet, die nicht zu dieser Menge gehören (vom gleichen Typ wie das Original). Das Komplement einer Menge A wird bezeichnet durch:

Zum Beispiel ist innerhalb der natürlichen Zahlen das Komplement der Menge der geraden Zahlen das der ungeraden Zahlen und umgekehrt.

Um das Komplement einer Menge zu bestimmen, muss von Anfang an klar sein, welche universellen oder Hauptelemente berücksichtigt werden. Zum Beispiel ist es nicht gleichbedeutend, das Komplement einer Menge auf den natürlichen Zahlen als auf den rationalen zu betrachten.

Die folgende Tabelle zeigt die Beziehung oder Analogie, die zwischen den Operationen für zuvor definierte Mengen und den konnektiven Operationen der Aussagenlogik besteht:

Gesetze von Morgan für Mengen

Schließlich sind Morgans Gesetze zu Mengen:

In Worten: Das Komplement einer Vereinigung ist die Schnittmenge der Komplemente, und das Komplement einer Vereinigung ist die Vereinigung der Komplemente.

Ein mathematischer Beweis für die erste Gleichheit wäre: