Auswahl logischer Verknüpfungen {¬,∨,∧,⇒,⇔} in der Mengenlehre?

Ist auch nicht vollständig, da tatsächlich 16 mögliche zusammengesetzte Aussagen (und entsprechende logische Verknüpfungen) zur Auswahl stehen. (Da {¬,∨,∧,⇒,⇔} bereits überflüssig ist, warum nicht die anderen 11 Konnektoren einwerfen, von denen einige SEHR hilfreich sind, wie "nand" ⊼ , "nor" ⊽ und "exclusive or" ⊻?)

Einige der "16 möglichen zusammengesetzten Aussagen" sind tatsächlich triviale Fälle (und auch das ¬ kommt zweimal vor). Tatsächlich können nur fünf der sechzehn nicht mit einem der fünf Standardoperatoren hergestellt werden. Siehe folgende Tabelle:

Table   Name                       Value for x..y
------------------------------------------------------
0000    Contradiction              False
0001    Conjunction                x ∧ y
0010    Nonimplication                      ¬(x ⇒ y)
0011    Left projection            x
0100    Converse nonimplication             ¬(y ⇒ x)
0101    Right projection           y
0110    Exclusive disjunction               ¬(x ⇔ y)
0111    Inclusive disjunction      x ∨ y
1000    Nondisjunction                      ¬(x ∨ y)
1001    Equivalence                x ⇔ y
1010    Right complementation      ¬y
1011    Converse implication       y ⇒ x
1100    Left complementation       ¬x
1101    Implication                x ⇒ y
1110    Nonconjunction                      ¬(x ∧ y)
1111    Affirmation                True

Wie Sie sehen können, sind nur fünf (Nichtimplikation, umgekehrte Nichtimplikation, exklusive Disjunktion, Nichtdisjunktion, Nichtkonjunktion) nicht in diesem „Standardsatz“. Es gibt jedoch Bücher, die auch ⊻, exklusive Disjunktion, als Standardoperator einführen.

Ich helfe in einem Informatikkurs über grundlegende Mathematik, und letzte Woche hat mich jemand gefragt:

Warum haben wir ein Symbol für ⊆ (Teilmenge), wenn wir bereits ⊂ (echte Teilmenge) und = (Gleichheit) haben? "a ⊆ b ≡ a ⊂ b ∨ a = b", also ist der Operator redundant.

Mir fiel keine bessere Antwort ein als "Weil Mathematiker faul sind und Dinge so kurz wie möglich schreiben wollen ". Das ist natürlich eine voreilige Schlussfolgerung – aber tatsächlich denke ich, dass es ziemlich wahrscheinlich ist, dass etwas Wahres darin ist. Man könnte fragen, „warum wurde × (Multiplikation) definiert?“, denn bei den natürlichen Zahlen kann man einfach addieren: 5 × 3 = 5 + 5 + 5 = 3 + 3 + 3 + 3 + 3. Weiter geht es fragen: "Warum wurden 2 und 3 definiert, wenn man auch 1+1 und 1+1+1 schreiben kann?" Irgendwann ist es wirklich zu viel Arbeit, alles aufzuschreiben, daher wurde mehr Notation eingeführt.

Natürlich dürfen Sie Ihre eigene Notation definieren. Indem Sie Nichtimplikation, exklusive Disjunktion, Nichtdisjunktion und Nichtkonjunktion definieren, haben Sie einen erschöpfenden Satz. Definieren Sie diejenigen, die Sie häufig benötigen, am Anfang Ihres Schreibens.

Wie sind wir also zu diesem Standardsatz logischer Operatoren gekommen? Indem wir sie verwenden und herausfinden, welche wir oft brauchen. Beachten Sie auch, dass die fünf nicht existierenden Anweisungen alle durch Negieren eines anderen Operators gebildet werden können (siehe vierte Spalte in der obigen Tabelle) und dass dies nicht möglich ist, wenn Sie eine der fünf „Standard“-Anweisungen weglassen.

Die Menge {¬,∨,∧,⇒,⇔} wird normalerweise verwendet, weil sie die "natürlichsten" enthält.

Wenn wir mit einer minimalen Menge beginnen, wie {¬,⇒}, werden die anderen normalerweise als Abkürzungen eingeführt.

Es gibt keinen "tiefen" Grund: hauptsächlich Tradition, und ein "angemessener" Kompromiss zwischen Einsparungen (Minimum) und Lesbarkeit ( p ∧ q als ¬(p ⇒ ¬q auszudrücken) ist nicht so "natürlich".

gnasher729 hat einen wichtigen Punkt angesprochen, der eine Erweiterung verdient: "In der formalen Logik sind Implikation x ⇒ y und Äquivalenz x ⇔ y sehr offensichtlich nützlich - sie drücken direkt die möglicherweise wichtigsten Konzepte der formalen Logik aus."

Der Hauptpunkt, den ich ansprechen möchte, ist folgender: Die naive Mengenlehre ist nicht die einzige wichtige Mengenlehre, und die klassische Logik ist nicht die einzige wichtige Logik. In den meisten Logiken stimmt es nicht, dass P⇒Q dasselbe ist wie ¬P∨Q. Wenn Sie sich mehr mit Logik befassen, werden Sie allmählich erkennen, dass Implikation (in einem sehr tiefen Sinne) „fundamentaler“ ist als sogar Konjunktion oder Disjunktion.

Aber einen Vorgeschmack kann ich euch jetzt schon geben. Sie brauchen die anderen Konnektoren nicht, wenn Sie Quantifizierung über Aussagen und Implikationen haben. Wir werden die übliche Konvention verwenden, die die Implikation mit rechts verbindet (d. h. A⇒B⇒C bedeutet A⇒(B⇒C); Sie können dies begründen, indem Sie feststellen, dass A⇒B⇒C äquivalent zu (A∧B )⇒C). Dann können Sie sie in Bezug auf Gentzen-Regeln definieren:

• P∧Q ist äquivalent zu ∀S.(P⇒Q⇒S)⇒S
• P∨Q ist äquivalent zu ∀S.(P⇒S)⇒(Q⇒S)⇒S
• ¬P ist äquivalent zu ∀SP⇒S

Letzteres erkennen Sie vielleicht als ex falso quodlibet .

Quantifizierung über Aussagen scheint etwas "Neues" zu sein, ist es aber eigentlich nicht. Als Sie sagten, dass „P⇒Q auch ¬P∨Q geschrieben werden könnte“, behaupten Sie tatsächlich, dass eine Aussage für alle Aussagen P und Q wahr ist, was eine universelle Quantifizierung von Aussagen ist. Wir neigen dazu, dieses Detail vor Studenten zu verbergen, damit sie sich mit der Aussagenlogik vertraut machen können, ohne über Quantifizierung nachdenken zu müssen.

Abschließender Gedanke: Der „tiefe Sinn“, auf den ich zuvor angespielt habe, ist, dass die logische Folgerung ein Morphismus in der Kategorientheorie ist und die Implikation ein exponentielles Objekt. Ich erwarte nicht, dass Sie diesen Satz verstehen, aber ein Beispiel kann helfen.

Betrachten Sie Modus Ponens . Wenn wir P⇒Q und P haben, dann können wir auf Q schließen. Wenn wir jedoch in der Mengenlehre eine Funktion f : A → B und einen Wert x : A haben, dann können wir die Funktion auf den Wert anwenden und geben f(x) : B.

Es stellt sich heraus, dass dies nicht nur ein Notationstrick oder ein Zufall ist. Es ist eine Verbindung, die sehr tief geht.

Es gibt zwei mögliche logische Funktionen ohne Eingänge, "wahr" und "falsch". Wir verwenden keine Symbole für sie, nur Namen.

Es gibt vier mögliche logische Funktionen mit einer Eingabe: „Wahr“ und „Falsch“ (was auch immer die Eingabe ist, die Ausgabe ist „wahr“ oder was auch immer die Eingabe ist, die Ausgabe ist „falsch“), Identität (Ausgabe = Eingabe) und Negation (Ausgang = Gegenteil von Eingang). Drei davon benötigen kein Symbol. Für das vierte verwenden wir das Symbol ¬. Das ist eines Ihrer fünf Symbole, und wir würden wirklich ein Symbol für diese Funktion brauchen.

Es gibt 16 mögliche logische Funktionen mit zwei Eingängen. Sechs davon "verwenden" nicht beide Eingänge; wenn wir die Eingänge x und y nennen, dann sind diese sechs Funktionen „falsch“, „wahr“, x, y, ¬x und ¬y. Es bleiben also noch 10 Funktionen übrig.

In der formalen Logik sind Implikation x ⇒ y und Äquivalenz x ⇔ y sehr offensichtlich nützlich - sie drücken direkt die möglicherweise wichtigsten Konzepte der formalen Logik aus. In anderen Bereichen, die mit Logik zu tun haben, sind sie viel weniger wichtig, aber in der formalen Logik sind sie äußerst wichtig. Wenn wir ein Symbol für "a impliziert b" haben, brauchen wir nicht wirklich eines für "a wird durch b impliziert", wir können einfach schreiben "b impliziert a". (Sie könnten einen Pfeil von rechts nach links verwenden; einige würden sagen, dass dies eigentlich kein anderes Symbol ist). Wenn wir die Negationen hinzufügen (kein zusätzliches Symbol für "a ist nicht äquivalent zu b" und "a impliziert nicht b"), dann werden weitere sechs Funktionen abgedeckt, vier bleiben übrig.

Für die letzten vier gibt es mehrere vernünftige Möglichkeiten, sie mit Symbolen darzustellen. Wir haben ein Symbol für logisch und ("beide") und logisch oder ("mindestens eins", oder "eins oder beide") und zusammen mit ihren Negationen ist alles abgedeckt. Wir hätten "keine", "höchstens eine" verwenden können, aber logisch und und logisch oder den Wettbewerb gewonnen. Fügen Sie ihre Negationen hinzu, und alles ist abgedeckt.

Das ist formale Logik; andere Bereiche, die Logik verwenden, haben andere Anforderungen. Bei der Entscheidungsfindung (häufig in der Softwareentwicklung verwendet) werden logisches Und, logisches Oder und Negation am häufigsten verwendet. Implikation und Äquivalenz werden selten verwendet. In der Computerhardware werden nand (nicht (a und b)) und nor (nicht (a oder b)) ganz selbstverständlich von einfachster Computerhardware implementiert, und alles basiert auf diesen beiden Funktionen. Dies ist jedoch ein Bereich, der im Gegensatz zur formalen Logik nicht für den menschlichen Konsum bestimmt ist.

Außerhalb sehr grundlegender logischer Kontexte gibt es wirklich nicht viel zu gewinnen, wenn man mit einem minimalen angemessenen Satz von Konnektoren beginnt und den Rest definiert. Alles, was es tut, ist, die Dinge unnötig zu verkomplizieren. Sogar in der Logik könnten wir mit dem Sheffer-Strich anstelle von {~, ->} beginnen, ziehen es aber vor, unsere Studenten nicht übermäßig zu verwirren.

Erlauben Sie mir, Ihnen einen ganz anderen Grund zu nennen, warum zumindest die separate Einführung von ∨,∧,⇒ ihre Vorzüge haben könnte.

Klassische Logik ist nett und alles, aber einige Leute interessieren sich tatsächlich für intuitionistische Logik. In der intuitionistischen Logik kann man keines der Konnektoren ¬,∨,∧,⇒ durch zwei beliebige andere definieren. Dies liegt daran, dass viele bekannte Gesetze wie (eines der) DeMorgan-Gesetze oder ¬A∨B ⇔ (A ⇒ B) nicht gelten. Es gibt tatsächlich eine Art von Semantik für intuitionistische (Aussagen-)Logik, die durch bikartesische geschlossene Kategorien gegeben ist . Aus dieser Sicht ist dieses "Problem" völlig natürlich:

In diesen bikartesischen geschlossenen Kategorien haben wir binäre Produkte von Aussagen, die durch "∧" gegeben sind, binäre Koprodukte , die durch "∨" gegeben sind, und Exponentialegegeben durch "⇒". Man könnte meinen, mir fehlen noch die €. Bikartesische geschlossene Kategorien haben ein Anfangsobjekt. Es entspricht dem Symbol ⊥ für „Falschheit“ oder „Widerspruch“. Die Negation eines Satzes A ist dann einfach A ⇒ ⊥ (das funktioniert auch in der klassischen Logik). Es gibt keinen Grund zu glauben (und wir wissen, dass es nicht möglich ist), dass diese Konstruktionen aufeinander reduziert werden können (es funktioniert auch nicht in vertrauten Kategorien, wie den Kategorien von Mengen und Funktionen). Wenn Sie sich also für Kategorientheorie oder intuitionistische Logik interessieren, würden Sie natürlich ⊥, ∧, ∨ und ⇒ separat einführen (eigentlich fehlt mir das Terminalobjekt ⊤, das "Wahrheit" bedeutet, aber es ist hier nicht wirklich wichtig).

Vor diesem Hintergrund macht es auch keinen Sinn, "alle möglichen binären Konnektoren" zu definieren, da es in der intuitionistischen Logik keine Wahrheitswerte gibt und es somit unendlich viele mögliche Konnektoren gibt (und nicht nur 16). Allerdings sind die Konnektoren ∧, ∨ und ⇒ sozusagen etwas Besonderes, da jeder eine ziemlich grundlegende universelle Abbildungseigenschaft erfüllt (dies ist teilweise an den bekannten „Eliminations“- und „Einführungs“-Regeln in „Natürliche Deduktion“ zu erkennen). .

Mathematiker sind faul ... So faul, als manche Computer benutzen ... Aber Computer müssen einfach sein, um elektronisch implementiert und miniaturisiert zu werden ... Dann, wie CISC .vs. RISC, nur Negation, Konjunktion (und) und Disjonktion (einschließlich-oder) oder besser NAND (nicht-und) und NOR (nicht-oder) sind erforderlich, um logische Mengen auszudrücken (siehe Karnaugh-Lösung, Church-Turing-Theorem, ASIC Programmierung)

Dann,

Verwenden Sie hochrangige Präsentationen mit vielen Operatoren, damit es kurz und dann scheinbar einfach aussieht ...

Verwenden Sie einen reduzierten Satz von Operatoren, um es einfach und schnell auszuführen

Es gibt viele 'Compiler' zum Konvertieren ...