Logische Binde

Im Logik, a Logische Binde (auch a genannt logical operator, Sentential Connective, oder Sential Operator) ist ein Logische Konstante. Sie können verwendet werden, um logische Formeln zu verbinden. Zum Beispiel in der Syntax von Aussagelogik, das binär Bindektion ${\ displayStyle \ lor}$ Kann verwendet werden, um den beiden zu verbinden Atomformeln ${\ displayStyle p}$ und ${\ displayStyle q}$die komplexe Formel rendern ${\ displayStyle p \ lor q}$.

Zu den gemeinsamen Konnektiven gehören Negation, disjunktion, Verbindung, und Implikation. In Standardsystemen von klassische Logik, diese Konnektiven sind interpretiert wie Wahrheit Funktionen, obwohl sie eine Vielzahl von alternativen Interpretationen in erhalten nicht klassische Logik. Ihre klassischen Interpretationen ähneln den Bedeutungen natürlicher Sprachausdrücke wie z. Englisch "Nicht", "oder", "und" und "wenn", aber nicht identisch. Diskrepanzen zwischen natürlichen Sprachkonnektiven und denen klassischer Logik haben nichtklassische Ansätze zur Bedeutung der natürlichen Sprache sowie Ansätze motiviert, die ein Klassiker kombinieren Kompositionssemantik mit einem robusten Pragmatik.

Ein logisches Verbindungsbetrieb ähnelt, aber nicht gleichwertig einer Syntax, die häufig in Programmiersprachen verwendet wird, die als a Bedingender Bediener.^[1]

Überblick

Im formelle SprachenWahrheitsfunktionen werden durch eindeutige Symbole dargestellt. Auf diese Weise können logische Aussagen nicht mehrdeutig verstanden werden. Diese Symbole werden genannt Logische Verbindungen, logische Operatoren, Aussagener Operatorenoder, in klassische Logik, Wahrheitsfunktional Verbindungen. Damit die Regeln, die es ermöglichen, neue gut geformte Formeln zu konstruieren, indem andere wohlgeformte Formeln mithilfe von Wahrheitsfunktionen verbinden, siehe siehe gut geformte Formel.

Logische Verbindungen können verwendet werden, um Null oder mehr Anweisungen zu verknüpfen, damit man darüber sprechen kann n-ary Logische Verbindungen. Das Boolesche Konstanten WAHR und FALSCH kann als Null-Ary-Operatoren betrachtet werden. Negation ist ein 1-Ary-Bindeffekt und so weiter.

Gemeinsame logische Verbindungen

Symbol, Name		Wahrheit Tisch					Venn Diagramm
Zeroary Connectives (Konstanten)
⊤	Wahrheit/Tautologie				1
⊥	Falschheit/Widerspruch				0
Unary Connectives
		P=	0		1
	Vorschlag P		0		1
¬	Negation		1		0
Binärverbindungen
		P=	0		1
		Q=	0	1	0	1
	Vorschlag P		0	0	1	1
	Vorschlag 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
→	Material bedingt		1	1	0	1
${\ displayStyle \ nleftrightarrow}$	Exklusiv oder		0	1	1	0
↔	Zweikonditionell		1	0	0	1
←	Konverse Implikation		1	0	1	1
Mehr Informationen

Liste der gängigen logischen Verbindungen

Zu den häufig verwendeten logischen Konnektiven gehören:^[2]

• Negation (nicht): ¬, n (Präfix), ~^[3]
• 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-Implikation.

Zum Beispiel die Bedeutung der Aussagen es regnet (bezeichnet durch P) und Ich bin drinnen (Mit q bezeichnet) wird transformiert, wenn die beiden mit logischen Konnektiven kombiniert werden:

• es ist nicht Regen (${\ displayStyle \ neg}$P)
• Es regnet und Ich bin drinnen (${\ displayStyle p \ Wedge q}$)
• Es regnet oder Ich bin drinnen (${\ displayStyle p \ lor q}$)
• Wenn es regnet, dann Ich bin drinnen (${\ displayStyle p \ rightarrow q}$)
• Wenn Ich bin drinnen, dann es regnet (${\ displayStyle q \ rightarrow p}$)
• Ich bin drinnen dann und nur dann, wenn es regnet (${\ displayStyle p \ leftrightarrow q}$)

Es ist auch üblich, die zu berücksichtigen immer wahr Formel und die Immer falsch Formel, um Binde zu sein:

• WAHR Formel (⊤, 1, v [Präfix] oder t)
• FALSCH Formel (⊥, 0, o [Präfix] oder f)

Geschichte der Notationen

• Negation: Das Symbol erschien in Heying 1929^[4][5] (vergleichen mit FregeSymbol ⫟ in seinem BEGRIFFSSCHRIFT); Das Symbol ~ erschien in Russell im Jahr 1908;^[6] Eine alternative Notation besteht darin, eine horizontale Linie über die Formel hinzuzufügen, wie in ${\ displayStyle {\ overline {p}}}$; Eine andere alternative Notation ist die Verwendung a Hauptsymbol wie in p '.
• Konjunktion: Das Symbol ∧ erschien 1929 in Heyting^[4] (vergleichen mit PeanoDie Verwendung der set-theoretischen Notation von Überschneidung ∩^[7]); das Symbol und erschien mindestens in Schönfinkel im Jahr 1924;^[8] das Symbol . kommt von Boole''s Interpretation der Logik als Elementaralgebra.
• Disjunktion: Das Symbol ∨ erschien in Russell im Jahr 1908^[6] (vergleichen mit PeanoDie Verwendung der set-theoretischen Notation von Union ∪); Das Symbol + wird auch verwendet, obwohl die Unklarheit aus der Tatsache kommt, dass das + gewöhnliche Elementaralgebra ist ein Exklusiv oder bei logisch in einem Zweielement interpretiert Ring; pünktlich in der Geschichte A + zusammen mit einem Punkt in der unteren rechten Ecke wurde von verwendet Peirce,^[9]
• Implikation: Das Symbol → kann in gesehen werden Hilbert 1917;^[10] ⊃ wurde 1908 von Russell verwendet^[6] (Vergleiche mit Peanos umgekehrter C -Notation); ⇒ wurde in vax verwendet.^[11]
• Biconditional: Das Symbol ≡ wurde 1908 zumindest von Russell verwendet;^[6] ↔ wurde zumindest von verwendet Tarski 1940;^[12] ⇔ wurde in Vax verwendet; Andere Symbole erschienen pünktlich in der Geschichte, wie ⊃⊂ in Gentzen,^[13] ~ In Schönfinkel^[8] oder ⊂⊃ in Chazal.^[14]
• Richtig: Das Symbol 1 kommt von Boole''s Interpretation der Logik als Elementaralgebra über dem Zwei-Element-Boolesche Algebra; Andere Notationen sind ${\ textstyle \ bigwedge}$ (in Peano gefunden werden).
• Falsch: Das Symbol 0 kommt auch aus Booles Interpretation der Logik als Ring; Andere Notationen sind ${\ textstyle \ bigvee}$ (in Peano gefunden werden).

Einige Autoren verwendeten Buchstaben für Connectives zu einer bestimmten Zeit der Geschichte: u. für die Konjunktion (Deutschs "und" für "und") und Ö. für die Disjunktion (Deutschs "Oder" für "oder") in früheren Werken von Hilbert (1904); Np zur Negation, Kpq für die Konjunktion, Dpq Für alternative Ablehnung, Apq für die Disjunktion, Xpq für gemeinsame Ablehnung, Cpq zur Implikation, Epq für biconditionale in ŁukaSiewicz (1929);^[15] vgl. Polnische Notation.

Redundanz

Solch ein logischer Verbindungsbetrieb als Konverse Implikation "←" ist eigentlich gleich wie Material bedingt mit ausgetauschten Argumenten; Somit ist das Symbol für die Konversesimplikation überflüssig. In einigen logischen Berechnungen (insbesondere in klassische Logik) bestimmte im Wesentlichen unterschiedliche zusammengesetzte Aussagen sind logisch äquivalent. A weniger trivial Beispiel für eine Redundanz ist die klassische Äquivalenz zwischen ¬P∨Q und P→Q. Daher benötigt ein klassisches logisches System den bedingten Operator "→" Wenn "¬" (nicht) und "∨" (oder) bereits verwendet werden oder kann das "→" nur als a verwenden syntethischer Zucker für eine Verbindung mit einer Negation und einer Disjunktion.

Es gibt sechzehn Boolesche Funktionen assoziieren Sie die Eingabe Wahrheitswerte P und Q mit vierstellig binär Ausgänge.^[16] Diese entsprechen mögliche Auswahlmöglichkeiten von binären logischen Konnektiven für klassische Logik. Verschiedene Implementierungen der klassischen Logik können unterschiedlich wählen funktionell vollständig Teilmengen von Konnektiven.

Ein Ansatz besteht darin, a zu wählen minimal Stellen Sie andere Konnektiven nach einer logischen Form fest und definieren Sie sie, wie im Beispiel mit dem oben bedingten Material. Das Folgende sind die Minimal funktionell vollständige Betreibersätze in klassischer Logik, deren Arities 2 nicht überschreiten:

Ein Element

{↑}, {↓}.

Zwei Elemente

${\ displaystyle \ {\ vee, \ neg \}}$, ${\ displayStyle \ {\ Wedge, \ neg \}}$, ${\ displayStyle \ {\ to, \ neg \}}$, ${\ displayStyle \ {\ get, \ neg \}}$, ${\ displayStyle \ {\ to, \ bot \}}$, ${\ displayStyle \ {\ get, \ bot \}}$, ${\ displayStyle \ {\ to, \ nleftrightarrow \}}$, ${\ displayStyle \ {\ get, \ nleftrightarrow \}}$, ${\ displayStyle \ {\ to, \ nrightarrow \}}$, ${\ displaystyle \ {\ to, \ nleftarrow \}}$, ${\ displayStyle \ {\ get, \ nrightarrow \}}$, ${\ displayStyle \ {\ get, \ 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 ist die Verwendung mit gleichen Rechtenkonnektiven eines bestimmten bequemen und funktional vollständigen, aber nicht minimal einstellen. Dieser Ansatz erfordert mehr Aussagen Axiomeund jede Äquivalenz zwischen logischen Formen muss entweder ein sein Axiom oder als Theorem nachweisbar.

Die Situation ist jedoch komplizierter in intuitionistische Logik. Seiner fünf Konnektiven, {∧, ∨, →, ¬, ⊥}, nur Negation "¬" kann auf andere Konnektiven reduziert werden (siehe Falsch (Logik) § Falsch, Negation und Widerspruch für mehr). Weder Konjunktion, Disjunktion noch materielles Bedingungen haben eine äquivalente Form, die aus den anderen vier logischen Konnektiven erstellt wurde.

Natürliche Sprache

Die standardmäßigen logischen Konnektiven der klassischen Logik haben grobe Äquivalente in den Grammatiken natürlicher Sprachen. Im Englischwie in vielen Sprachen sind solche Ausdrücke normalerweise grammatikalische Konjunktionen. Sie können jedoch auch die Form von annehmen Komplementizer, Verb Suffixe, und Partikel. Das Bezeichnungen of Natural Language Connectives ist ein wichtiges Thema der Forschung in formelle Semantik, ein Feld, das die logische Struktur natürlicher Sprachen untersucht.

Die Bedeutungen der natürlichen Sprachverbindungen sind nicht genau mit ihren nächsten Äquivalenten in der klassischen Logik identisch. Insbesondere kann eine Disjunktion eine erhalten Exklusive Interpretation in vielen Sprachen. Einige Forscher haben diese Tatsache als Beweis für die natürliche Sprache angesehen Semantik ist nicht klassisch. Andere behalten jedoch die klassische Semantik durch Plätze bei pragmatisch Berichte über Exklusivität, die die Illusion der Nichtklassiker schaffen. In solchen Konten wird Exklusivität typischerweise als behandelt Skalare Implikatur. Verwandte Rätsel, die eine Disjunktion betreffen freie Wahl schließen, Hurfords Einschränkungund der Beitrag der Disjunktion in alternative Fragen.

Andere offensichtliche Diskrepanzen zwischen natürlicher Sprache und klassischer Logik sind die Paradoxien der materiellen Implikation, Eselanaphora und das Problem von kontrafaktische Bedingungen. Diese Phänomene wurden als Motivation zur Identifizierung der Bezeichnungen natürlicher Sprache mit logischen Operatoren angesehen, einschließlich der streng bedingt, das variabel streng bedingtsowie verschiedene verschiedene dynamisch Betreiber.

Die folgende Tabelle zeigt die standardmäßig klassisch definierbaren Annäherungen für die englischen Konnektiven.

englisches Wort	Bindektion	Symbol	Logisches Tor
nicht	Negation	"¬"	NICHT
und	Verbindung	"∧"	UND
oder	disjunktion	"∨"	ODER
wenn, dann	materielle Implikation	"→"	IMPLIZIEREN
...wenn	Konverse Implikation	"←"
dann und nur dann, wenn	zweikonditionell	"↔"	Xnor
nicht beide	Alternative Ablehnung	"↑"	NAND
weder noch	gemeinsame Ablehnung	"↓"	NOCH
aber nicht	Material Nichtimplikation	"↛"	Flüssig

Eigenschaften

Einige logische Verbindungen besitzen Eigenschaften, die in den Theoreme, die den Bindeffekt enthalten, ausgedrückt werden. Einige dieser Eigenschaften, die ein logischer Bindewesen haben kann, sind:

Assoziativität

Innerhalb eines Ausdrucks, der zwei oder mehr der gleichen assoziativen Konnektive in Folge enthält, spielt die Reihenfolge der Operationen keine Rolle, solange die Abfolge der Operanden nicht geändert wird.

Amtativität

Die Operanden des Bindeffekts können ausgetauscht werden, was die logische Äquivalenz zum ursprünglichen Ausdruck bewahrt.

Verbreitung

Ein durch · verteiltes Binde a · (b + c) = ((a · b) + (a · c) Für alle Operanden a, b, c.

Idempotenz

Immer wenn die Operanden der Operation gleich sind, entspricht die Verbindung logisch dem Operanden.

Absorption

Ein Paar Konnektiven ∧ ∨ erfüllt das Absorptionsgesetz, wenn ${\ displayStyle a \ Land (a \ lor b) = a}$ Für alle Operanden a, b.

Monotizität

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. Z. B. ∨, ∧, ⊤, ⊥.

Affinität

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

Dualität

Lesen Sie die Wahrheitswertsaufgaben für den Betrieb von oben nach unten in seiner Wahrheitstabelle ist das gleiche wie das Ergänzung zum Lesen der Tabelle derselben oder eines anderen Bindezeit von unten nach oben. Ohne auf Wahrheitstabellen zurückzugreifen, kann es als formuliert werden g(¬a₁, ..., ¬a_n) = ¬g(a₁, ..., a_n). Z. B. ¬.

Wahrheitsvorverdauer

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

Falschheitpräparation

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

Involutivität (für Unary Connectives)

f(f(a)) = a. Z.B. 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 als auch als "≤" -Symbol erwiesen werden können, und das "≤" -Symbol bedeutet, dass "... → ..." für logische Verbindungen eine Folge der entsprechenden "... → ..." -Konnectives für Aussagenvariablen ist. Etwas Viele bewertete Logik Kann inkompatible Definitionen von Äquivalenz und Ordnung (mit sich bringen) aufweisen.

Sowohl Konjunktion als auch Disjunktion sind in der klassischen Logik assoziativ, kommutativ und idempotent, die meisten Sorten der vielen bewerteten Logik und intuitionistischen Logik. Gleiches gilt für die Verteilung der Konjunktion über Disjunktion und Disjunktion über die Konjunktion sowie für das Absorptionsgesetz.

In der klassischen Logik und einigen Arten mit vieler bewerteter Logik, Konjunktion und Disjunktion sind doppelt, und die Negation ist selbst-duisch, letzteres ist auch in der intuitionistischen Logik selbst-Dual.

Rangfolge

Um die Anzahl der notwendigen Klammern zu verringern, kann man einführen Vorrangregeln: ¬ hat höhere Vorrang als ∧, ∧ höher als ∨ und ∨ höher als →. Also zum Beispiel, ${\ displayStyle p \ vee q \ wedge {\ neg r} \ rightarrow s}$ ist kurz für ${\ displayStyle (p \ vee (q \ wedge (\ neg r)) \ rightarrow s}$.

Hier ist eine Tabelle, die einen häufig verwendeten Vorrang der logischen Operatoren zeigt.^[17]

Operator	Vorrang
${\ displayStyle \ neg}$	1
${\ displayStyle \ Land}$	2
${\ displayStyle \ lor}$	3
${\ displayStyle \ bis}$	4
${\ displayStyle \ leftrightarrow}$	5

Allerdings verwenden nicht alle Compiler dieselbe Reihenfolge; Beispielsweise wurde auch eine Reihenfolge verwendet, in der eine Disjunktion ein geringer Vorrang als Implikation oder Bi-Implikation ist.^[18] Manchmal ist Vorrang zwischen Konjunktion und Disjunktion nicht spezifiziert, um sie in bestimmten Formel mit Klammern ausdrücklich bereitzustellen. Die Vorrangreihenfolge bestimmt, welches Bindevektiv die "Hauptbettzu" bei der Interpretation einer nichtatomaren Formel ist.

Informatik

Ein Wahrheitsfunktionalansatz für logische Operatoren wird als implementiert als Logik -Tore in Digitale Schaltungen. Praktisch alle digitalen Schaltungen (die Hauptausnahme ist Dram) sind ausgebaut von NAND, NOCH, NICHT, und Übertragungsdates; Weitere Informationen finden Sie in Wahrheitsfunktion in der Informatik. Logische Operatoren über Bitvektoren (entsprechend endlich Boolesche Algebren) sind Bitgewise Operations.

Aber nicht jede Verwendung eines logischen Binde Computerprogrammierung Hat eine Boolesche Semantik. Zum Beispiel, faule Bewertung wird manchmal implementiert für P∧Q und P∨QDaher sind diese Konnektiven nicht kommutativ, wenn eine oder beide Ausdrücke P, Q haben Nebenwirkungen. Auch eine bedingt, was in gewissem Sinne dem entspricht Material bedingt Connective ist im Wesentlichen nicht-im-an-Boolen, weil if (p) dann q;, das konsequente q wird nicht ausgeführt, wenn die vorgezogenP ist falsch (obwohl eine Verbindung insgesamt in diesem Fall erfolgreich ist ≈ "wahr"). Dies ist näher am Intuitionisten und Konstruktivist Ansichten zum materiellen bedingten - und nicht zu den Ansichten der klassischen Logik.

Siehe auch

Verweise

Quellen

• Bocheński, Józef Maria (1959), Eine Précis mathematischer Logik, übersetzt aus den französischen und deutschen Ausgaben von Otto Bird, D. Reidel, Dordrecht, Südholland.
• Enderton, Herbert (2001), Eine mathematische Einführung in die Logik (2. Aufl.), Boston, MA: Akademische Presse, ISBN 978-0-12-238452-3
• Gamut, L.T.F (1991), "Kapitel 2", Logik, Sprache und Bedeutung, vol. 1, University of Chicago Press, S. 54–64, OCLC 21372380
• Rautenberg, W. (2010), Eine kurze Einführung in die mathematische Logik (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 Connectives. MIT Press. ISBN 978-0-262-01654-4.

Externe Links

• "Propositional Connective", Enzyklopädie der Mathematik, EMS Press, 2001 [1994]
• Lloyd Humberstone (2010), "Satzverbindungen in formaler Logik",", Stanford Encyclopedia of Philosophy (Ein Abstrakte algebraische Logik Ansatz zu Konnektiven.)
• John MacFarlane (2005), ","Logische Konstanten",", Stanford Encyclopedia of Philosophy.