Logische Verbindung - Logical connective

In der Logik ist ein logisches Konnektor (auch als logischer Operator , Satzverbindung oder Satzoperator bezeichnet ) eine logische Konstante, die verwendet wird, um zwei oder mehr Formeln zu verbinden. Zum Beispiel kann in der Syntax der Aussagenlogik das binäre Konnektor verwendet werden, um die beiden atomaren Formeln zu verbinden und die komplexe Formel wiederzugeben . ${\displaystyle \lor}$ ${\displaystyle P}$${\displaystyle Q}$${\displaystyle P\lor Q}$

Übliche Konnektoren sind Negation , Disjunktion , Konjunktion und Implikation . In Standardsystemen der klassischen Logik werden diese Konnektoren als Wahrheitsfunktionen interpretiert , obwohl sie in der nichtklassischen Logik eine Vielzahl alternativer Interpretationen erhalten . Ihre klassischen Interpretationen ähneln den Bedeutungen natürlicher Sprachausdrücke wie Englisch „not“, „or“, „and“ und „if“, aber nicht identisch. Diskrepanzen zwischen natürlichsprachlichen Konnektoren und denen der klassischen Logik haben sowohl nichtklassische Ansätze zur Bedeutung natürlicher Sprache als auch Ansätze motiviert, die eine klassische kompositorische Semantik mit einer robusten Pragmatik verbinden .

Ein logisches Konnektor ist einer Syntax ähnlich, die häufig in Programmiersprachen verwendet wird und als Bedingungsoperator bezeichnet wird , jedoch nicht äquivalent zu dieser .

Überblick

In formalen Sprachen werden Wahrheitsfunktionen durch eindeutige Symbole dargestellt. Dadurch können logische Aussagen nicht mehrdeutig verstanden werden. Diese Symbole werden als logische Verknüpfungen , logische Operatoren , propositionaler Betreiber oder in der klassischen Logik , wahrheitsfunktionale Konnektive . Für die Regeln, die die Konstruktion neuer wohlgeformter Formeln durch Verbinden anderer wohlgeformter Formeln unter Verwendung von Wahrheitsfunktionskonnektoren ermöglichen, siehe wohlgeformte Formeln .

Logische Verknüpfungen können verwendet werden, um mehr als zwei Aussagen zu verknüpfen, so dass man von n- ären logischen Verknüpfungen sprechen kann .

Gemeinsame logische Verknüpfungen

Symbol, Name		Wahrheitstabelle					Venn- Diagramm
Nulläre Konnektoren (Konstanten)
⊤	Wahrheit / Tautologie				1
⊥	Falschheit / Widerspruch				0
Unäre Verbindungen
		P  =	0		1
	Satz P		0		1
¬	Negation		1		0
Binäre Konnektoren
		P  =	0		1
		Q  =	0	1	0	1
	Satz P		0	0	1	1
	Satz Q		0	1	0	1
∧	Verbindung		0	0	0	1
↑	Alternative Ablehnung		1	1	1	0
∨	Disjunktion		0	1	1	1
↓	Gemeinsame Ablehnung		1	0	0	0
→	Materialbedingt		1	1	0	1
${\displaystyle \nleftrightarrow }$	Exklusiv oder		0	1	1	0
↔	Biconditional		1	0	0	1
←	Umgekehrte Implikation		1	0	1	1
Mehr Informationen

Liste gängiger logischer Verknüpfungen

Häufig verwendete logische Verknüpfungen sind:

• Negation (nicht) : ¬ , N (Präfix), ~
• Konjunktion (und) : ∧ , K (Präfix), & , ∙
• Disjunktion (oder) : ∨, A (Präfix)
• Materielle Implikation (wenn...dann) : → , C (Präfix), ⇒ , ⊃
• Biconditional (wenn und nur wenn) : ↔ , E (Präfix), ≡ , =

Alternative Namen für biconditional sind iff , xnor und bi-implication .

Zum Beispiel wird die Bedeutung der Aussagen es regnet (bezeichnet mit P ) und Ich bin drinnen (bezeichnet mit Q) transformiert, wenn die beiden mit logischen Verknüpfungen kombiniert werden:

• Es regnet nicht ( P )${\displaystyle \neg}$
• Es regnet und ich bin drinnen ( )${\displaystyle P\keil Q}$
• Es regnet oder ich bin drinnen ( )${\displaystyle P\lor Q}$
• Wenn es regnet, dann bin ich drinnen ( )${\displaystyle P\rightarrow Q}$
• Wenn ich drinnen bin, dann regnet es ( )${\displaystyle Q\rightarrow P}$
• Ich bin drinnen, wenn es regnet ( )${\displaystyle P\leftrightarrow Q}$

Es ist auch üblich, die immer wahre Formel und die immer falsche Formel als zusammenhängend zu betrachten:

• Wahre Formel (⊤, 1, V [Präfix] oder T)
• Falsche Formel (⊥, 0, O [Präfix] oder F)

Geschichte der Notationen

• Negation: das Symbol ¬ erschien 1929 bei Heyting (vgl. Freges Symbol ⫟ in seiner Begriffsschrift ); das Symbol ~ erschien 1908 in Russell ; eine alternative Schreibweise besteht darin, eine horizontale Linie über der Formel hinzuzufügen, wie in ; eine andere alternative Notation besteht darin, ein Primsymbol wie in P' zu verwenden.${\displaystyle {\overline {P}}}$
• Konjunktion: das Symbol ∧ erschien 1929 in Heyting (vergleiche Peanos Verwendung der mengentheoretischen Schreibweise des Schnitts ∩); das Symbol & tauchte zumindest 1924 in Schönfinkel auf; das Symbol . stammt aus Booles Interpretation der Logik als elementare Algebra .
• Disjunktion: Das Symbol ∨ erschien 1908 bei Russell (vergleiche Peanos Verwendung der mengentheoretischen Notation von Vereinigung ∪); das Symbol + wird auch verwendet, trotz der Mehrdeutigkeit, die sich aus der Tatsache ergibt , dass das + der gewöhnlichen elementaren Algebra ein exklusives oder , logisch interpretiert, in einem Zweielementring ist ; Pünktlich in der Historie wurde ein + zusammen mit einem Punkt in der unteren rechten Ecke von Peirce verwendet ,
• Implikation: das Symbol → ist 1917 bei Hilbert zu sehen ; ⊃ wurde 1908 von Russell verwendet (vergleiche Peanos umgekehrte C-Notation); ⇒ wurde in Vax verwendet.
• Biconditional: das Symbol ≡ wurde zumindest von Russell 1908 verwendet; ↔ wurde zumindest von Tarski 1940 verwendet; ⇔ wurde in Vax verwendet; andere Symbole tauchten pünktlich in der Geschichte auf, wie in Gentzen , ~ in Schönfinkel oder ⊂⊃ in Chazal.
• Richtig: Das Symbol 1 stammt aus Booles Interpretation der Logik als elementare Algebra über der zweielementigen Booleschen Algebra ; andere Notationen sind (zu finden in Peano).${\displaystyle \bigwedge}$
• Falsch: Das Symbol 0 stammt auch aus Booles Interpretation der Logik als Ring; andere Notationen sind (zu finden in Peano).${\displaystyle \bigvee}$

Einige Autoren verwendeten zu irgendeinem Zeitpunkt der Geschichte Buchstaben für Bindeglieder: u. für Konjunktion (deutsch "und" für "und") und o. für Disjunktion (deutsch "oder" für "oder") in früheren Werken von Hilbert (1904); N p für Negation, K pq für Konjunktion, D pq für alternative Verweigerung, A pq für Disjunktion, X pq für gemeinsame Verneinung, C pq für Implikation, E pq für bikonditional in Łukasiewicz (1929); vgl. Polnische Notation .

Redundanz

Ein solches logisches Konnektiv wie die umgekehrte Implikation "←" ist tatsächlich dasselbe wie eine Materialbedingung mit vertauschten Argumenten; daher ist das Symbol für die umgekehrte Implikation überflüssig. In einigen logischen Kalkülen (insbesondere in der klassischen Logik ) sind bestimmte im Wesentlichen unterschiedliche zusammengesetzte Aussagen logisch äquivalent . Ein weniger triviales Beispiel für eine Redundanz ist die klassische Äquivalenz zwischen ¬ P  ∨  Q und P  →  Q . Daher braucht ein klassisch-basiertes logisches System den Bedingungsoperator "→" nicht, wenn "¬" (not) und "∨" (or) bereits verwendet werden, oder kann "→" nur als syntaktischen Zucker für a . verwenden Verbindung mit einer Negation und einer Disjunktion.

Es gibt sechzehn Booleschen Funktionen der Eingangs Assoziieren Wahrheitswerte P und Q mit vierstelligen binären Ausgänge. Diese entsprechen möglichen Wahlmöglichkeiten von binären logischen Verknüpfungen für die klassische Logik . Verschiedene Implementierungen der klassischen Logik können verschiedene funktional vollständige Teilmengen von Konnektoren wählen .

Ein Ansatz besteht darin, eine minimale Menge zu wählen und andere Verknüpfungen durch eine logische Form zu definieren, wie im obigen Beispiel mit der Materialbedingung. Im Folgenden sind die minimalen funktional vollständigen Operatorensätze in der klassischen Logik aufgeführt, deren Stelligkeit 2 nicht überschreitet:

Ein Element

{↑}, {↓}.

Zwei Elemente

${\displaystyle \{\vee,\neg\}}$, , , , , , , , , , , , , , , , , .${\displaystyle \{\wedge ,\neg\}}$${\displaystyle \{\to ,\neg\}}$${\displaystyle \{\gets,\neg\}}$${\displaystyle \{\to ,\bot\}}$${\displaystyle \{\gets,\bot\}}$${\displaystyle \{\to ,\nleftrightarrow \}}$${\displaystyle \{\gets ,\nleftrightarrow \}}$${\displaystyle \{\to ,\nrightarrow \}}$${\displaystyle \{\to ,\nleftarrow \}}$${\displaystyle \{\gets ,\nrightarrow \}}$${\displaystyle \{\gets ,\nleftarrow \}}$${\displaystyle \{\nrightarrow ,\neg \}}$${\displaystyle \{\nleftarrow ,\neg \}}$${\displaystyle \{\nrightarrow ,\top \}}$${\displaystyle \{\nleftarrow ,\top \}}$${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$${\displaystyle \{\nleftarrow ,\leftrightarrow \}}$

Drei Elemente

${\displaystyle \{\lor,\leftrightarrow,\bot\}}$, , , , , .${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$${\displaystyle \{\land,\leftrightarrow,\bot\}}$${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$${\displaystyle \{\land ,\nleftrightarrow ,\top \}}$

Ein anderer Ansatz besteht darin, gleichberechtigte Konnektoren eines bestimmten praktischen und funktionell vollständigen, aber nicht minimalen Satzes zu verwenden. Dieser Ansatz erfordert mehr propositionale Axiome , und jede Äquivalenz zwischen logischen Formen muss entweder ein Axiom oder als Theorem beweisbar sein.

In der intuitionistischen Logik ist die Situation jedoch komplizierter . Von seinen fünf Verknüpfungen {∧, ∨, →, ¬, ⊥} kann nur die Negation "¬" auf andere Verknüpfungen reduziert werden (siehe Falsch (Logik) § Falsch, Negation und Widerspruch für mehr). Weder Konjunktion, Disjunktion noch Materialbedingung haben eine äquivalente Form, die aus den anderen vier logischen Verknüpfungen aufgebaut ist.

Natürliche Sprache

Die üblichen logischen Konnektoren der klassischen Logik haben grobe Entsprechungen in den Grammatiken natürlicher Sprachen. Im Englischen , wie in vielen anderen Sprachen, sind solche Ausdrücke typischerweise grammatikalische Konjunktionen . Sie können aber auch die Form von Complementizer , Verb Suffixe und Partikel . Die Denotationen natürlicher Sprachkonnektoren sind ein wichtiges Forschungsthema in der formalen Semantik , einem Feld, das die logische Struktur natürlicher Sprachen untersucht.

Die Bedeutungen natürlicher Sprachkonnektoren sind nicht genau identisch mit ihren nächsten Äquivalenten in der klassischen Logik. Insbesondere die Disjunktion kann in vielen Sprachen exklusiv interpretiert werden. Einige Forscher haben diese Tatsache als Beweis genommen , dass die natürliche Sprache Semantik ist nicht klassische . Andere behalten jedoch die klassische Semantik bei, indem sie pragmatische Darstellungen von Exklusivität postulieren, die die Illusion von Nicht- Klassizität erzeugen. In solchen Konten wird Exklusivität typischerweise als skalare Implikatur behandelt . Zu verwandten Rätseln mit Disjunktion gehören Schlussfolgerungen aus freier Wahl , Hurford's Constraint und der Beitrag der Disjunktion in alternativen Fragen .

Andere offensichtliche Diskrepanzen zwischen natürlicher Sprache und klassischer Logik sind die Paradoxien der materiellen Implikation , der Eselanaphora und das Problem der kontrafaktischen Bedingungen . Diese Phänomene wurden als Motivation zum Identifizieren der Bezeichnungen von Bedingungen in natürlicher Sprache mit logischen Operatoren genommen, einschließlich der strengen Bedingung , der variabel strengen Bedingung sowie verschiedener dynamischer Operatoren.

Die folgende Tabelle zeigt die klassisch definierbaren Standard-Approximationen für die englischen Konnektoren.

englisches Wort	Konnektivität	Symbol	Logisches Tor
nicht	Negation	"¬"	NICHT
und	Verbindung	"∧"	UND
oder	Disjunktion	"∨"	ODER
wenn, dann	materielle Implikationen	"→"	IMPLIZIEREN
...wenn	umgekehrte Implikation	"←"
dann und nur dann, wenn	bikonditionell	"↔"	XNOR
nicht beide	alternative Ablehnung	"↑"	NAND
weder noch	gemeinsame Verleugnung	"↓"	NOCH
aber nicht	materielle Nichtimplikation	"↛"	SCHNELL

Eigenschaften

Einige logische Konnektoren besitzen Eigenschaften, die in den Sätzen ausgedrückt werden können, die das Konnektor enthalten. Einige dieser Eigenschaften, die ein logisches Konnektiv haben kann, sind:

Assoziativität

Innerhalb eines Ausdrucks, der zwei oder mehr gleiche assoziative Verknüpfungen hintereinander enthält, spielt die Reihenfolge der Operationen keine Rolle, solange die Reihenfolge der Operanden nicht geändert wird.

Kommutativität

Die Operanden des Konnektors können vertauscht werden, wobei die logische Äquivalenz zum ursprünglichen Ausdruck erhalten bleibt.

Verteilung

Ein mit · bezeichnetes Konnektor verteilt sich über ein anderes mit + bezeichnetes Konnektor, wenn a · ( b + c ) = ( a · b ) + ( a · c ) für alle Operanden a , b , c gilt .

Idempotenz

Immer wenn die Operanden der Operation gleich sind, ist die Verbindung logisch äquivalent zum Operanden.

Absorption

Ein Konnektorpaar ∧, ∨ erfüllt das Absorptionsgesetz, wenn für alle Operanden a , b .${\displaystyle a\land (a\lor b)=a}$

Monotonie

Wenn f ( a ₁ , ..., a _n ) f ( b ₁ , ..., b _n ) für alle a ₁ , ..., a _n , b ₁ , ..., b _n ∈ {0 , 1} , so dass a ₁ ≤ b ₁ , a ₂ ≤ b ₂ , ..., a _n ≤ b _n . ZB ∨, ∧, ⊤, ⊥.

Affinität

Jede Variable macht immer einen Unterschied im Wahrheitswert der Operation oder sie macht nie einen Unterschied. B. ¬, ↔, , ⊤, ⊥.${\displaystyle \nleftrightarrow }$

Dualität

Die Wahrheitswert-Zuordnungen für die Operation von oben nach unten in ihrer Wahrheitstabelle zu lesen, ist dasselbe, als würde man das Komplement des Lesens der Tabelle derselben oder einer anderen Verknüpfung von unten nach oben nehmen. Ohne auf Wahrheitstabellen zurückzugreifen, kann man sie als g̃ (¬ a ₁ , ..., ¬ a _n ) = ¬ g ( a ₁ , ..., a _n ) formulieren . ZB ¬.

Wahrheitserhaltend

Die Verbindung all dieser Argumente, die Tautologien sind, ist eine Tautologie selbst. ZB ∨, ∧, ⊤, →, ↔, ⊂ (siehe Gültigkeit ).

Falschheitserhaltend

Die Verbindung all dieser Argumente sind Widersprüche, ist selbst ein Widerspruch. ZB ∨, ∧, , ⊥, ⊄, ⊅ (siehe Gültigkeit ).${\displaystyle \nleftrightarrow }$

Involutivität (für unäre Konnektive)

f ( f ( a )) = a . ZB Negation in der klassischen Logik.

Für die klassische und intuitionistische Logik bedeutet das "="-Symbol, dass entsprechende Implikationen "...→..." und "...←..." für logische Verbindungen sowohl als Theoreme bewiesen werden können, als auch das "≤"-Symbol bedeutet, dass "...→..." für logische Verbindungen eine Folge entsprechender "...→..."-Konnektoren für Aussagenvariablen ist. Einige mehrwertige Logiken können inkompatible Definitionen von Äquivalenz und Ordnung (Entailment) haben.

Sowohl Konjunktion als auch Disjunktion sind in der klassischen Logik, den meisten Varianten der vielwertigen Logik und der intuitiven Logik, assoziativ, kommutativ und idempotent. Das gleiche gilt für die Distributivität von Konjunktion über Disjunktion und Disjunktion über Konjunktion sowie für das Absorptionsgesetz.

In der klassischen Logik und einigen Varianten der vielwertigen Logik sind Konjunktion und Disjunktion dual, und die Negation ist selbst-dual, letztere ist auch in der intuitionistischen Logik selbst-dual.

Rangfolge

Um die Anzahl der notwendigen Klammern zu reduzieren, kann man Vorrangregeln einführen : ¬ hat Vorrang vor ∧, ∧ höher als ∨ und ∨ höher als →. So ist zum Beispiel die Abkürzung für . ${\displaystyle P\vee Q\wedge {\neg R}\rightarrow S}$${\displaystyle (P\vee (Q\wedge (\neg R)))\rightarrow S}$

Hier ist eine Tabelle, die eine häufig verwendete Rangfolge logischer Operatoren zeigt.

${\displaystyle {\begin{array}{c|c}{\text{Operator}}&{\text{Precedence}}\\\hline \neg &1\\\land &2\\\vee &3\\\to &4\\\Pfeil nach links und rechts &5\end{array}}}$

Allerdings verwenden nicht alle Compiler dieselbe Reihenfolge; zum Beispiel wurde auch eine Reihenfolge verwendet, bei der Disjunktion niedrigere Priorität hat als Implikation oder Doppelimplikation. Manchmal ist der Vorrang zwischen Konjunktion und Disjunktion nicht spezifiziert, sodass er in einer gegebenen Formel in Klammern explizit angegeben werden muss. Die Rangfolge bestimmt, welches Konnektiv das "Hauptkonnektiv" bei der Interpretation einer nicht-atomaren Formel ist.

Informatik

Ein wahrheitsfunktionaler Ansatz für logische Operatoren wird als logische Gatter in digitalen Schaltungen implementiert . Praktisch alle digitalen Schaltungen (die Hauptausnahme ist DRAM ) sind aus NAND- , NOR- , NOT- und Übertragungsgattern aufgebaut ; Weitere Details finden Sie unter Wahrheitsfunktion in der Informatik . Logische Operatoren über Bitvektoren (entsprechend endlichen Booleschen Algebren ) sind bitweise Operationen .

Aber nicht jede Verwendung eines logischen Konnektors in der Computerprogrammierung hat eine boolesche Semantik. Zum Beispiel lazy evaluation wird manchmal für implementiert P  ∧  Q und P  ∨  Q , so dass diese Konnektive nicht kommutativ ist , wenn eine oder beide der Ausdrücke P , Q haben Nebenwirkungen . Außerdem ist eine Bedingung , die in gewisser Weise dem materiellen bedingten Konnektor entspricht, im Wesentlichen nicht boolesch, da für if (P) then Q;die Folge Q nicht ausgeführt wird, wenn der Antezedens  P falsch ist (obwohl eine Verbindung als Ganzes erfolgreich ist ≈ "wahr" in solchen Fall). Dies ist näher an intuitionistischen und konstruktivistischen Ansichten über das materielle Bedingte als an den Ansichten der klassischen Logik.

Siehe auch

Anmerkungen

Verweise

Quellen

• Bocheński, Józef Maria (1959), A Précis of Mathematical Logic , übersetzt aus der französischen und deutschen Ausgabe von Otto Bird, D. Reidel, Dordrecht, Südholland.
• Enderton, Herbert (2001), A Mathematical Introduction to Logic (2. Aufl.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3
• Gamut, LTF (1991), "Kapitel 2", Logik, Sprache und Bedeutung , 1 , University of Chicago Press, S. 54–64, OCLC  21372380
• Rautenberg, W. (2010), A Concise Introduction to Mathematical Logic (3. Aufl.), New York : Springer Science+Business Media , doi : 10.1007/978-1-4419-1221-3 , ISBN 978-1-4419-1220-6.
• Humberstone, Lloyd (2011). Die Verbindungen . MIT-Presse. ISBN 978-0-262-01654-4.

Externe Links

• "Propositional Connective" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Lloyd Humberstone (2010), " Sentence Connectives in Formal Logic ", Stanford Encyclopedia of Philosophy (Ein abstrakter algebraischer Logikansatz für Konnektoren.)
• John MacFarlane (2005), „ Logische Konstanten “, Stanford Encyclopedia of Philosophy .