Logické spojovací - Logical connective

V logice je logická spojka (také nazývaná logický operátor , větný spojovací nebo věticí operátor ) logická konstanta používaná k propojení dvou nebo více vzorců. Například v syntaxi z výrokové logiky je binární pojivové může být použit pro spojení dvou atomové vzorce a , čímž komplexní vzorec . ${\ displaystyle \ lor}$ ${\ displaystyle P}$${\ displaystyle Q}$${\ displaystyle P \ lor Q}$

Mezi běžné spojky patří negace , disjunkce , konjunkce a implikace . Ve standardních systémech klasické logiky jsou tyto spojky interpretovány jako pravdivé funkce , i když v neklasické logice přijímají řadu alternativních interpretací . Jejich klasické interpretace jsou podobné významům výrazů přirozeného jazyka, jako je angličtina „ne“, „nebo“, „a“ a „pokud“, ale nejsou totožné. Nesrovnalosti mezi spojovacími prvky přirozeného jazyka a pojmy klasické logiky motivovaly neklasické přístupy k významu přirozeného jazyka i přístupy, které spojují klasickou kompoziční sémantiku s robustní pragmatikou .

Logické spojení je podobné, ale není ekvivalentní syntaxi běžně používané v programovacích jazycích, které se nazývá podmíněný operátor .

Přehled

Ve formálních jazycích jsou funkce pravdy reprezentovány jednoznačnými symboly. To umožňuje, aby logická prohlášení nebyla chápána nejednoznačným způsobem. Tyto symboly se nazývají logické spojky , logické operátory , výrokové operátoři nebo v klasické logiky , pravdivostní funkční spojky . Pravidla, která umožňují konstrukci nových dobře formulovaných formulí spojením dalších dobře formulovaných formulí pomocí pravdivě funkčních spojek, najdete v dobře formulované formuli .

Logické spojky lze použít k propojení více než dvou příkazů, takže lze hovořit o n -árním logickém spojivu .

Běžné logické spojky

Symbol, jméno		Pravdivá tabulka					Vennův diagram
Nulové spojky (konstanty)
⊤	Pravda / tautologie				1
⊥	Falešnost / rozpor				0
Unární spojky
		P  =	0		1
	Návrh P		0		1
¬	Negace		1		0
Binární spojky
		P  =	0		1
		Q  =	0	1	0	1
	Návrh P		0	0	1	1
	Návrh Q		0	1	0	1
∧	Spojení		0	0	0	1
↑	Alternativní odmítnutí		1	1	1	0
∨	Disjunkce		0	1	1	1
↓	Společné odmítnutí		1	0	0	0
→	Materiál podmíněný		1	1	0	1
${\ Displaystyle \ nleva doprava šipka$	Exkluzivní nebo		0	1	1	0
↔	Dvoupodmínečné		1	0	0	1
←	Konverze implikace		1	0	1	1
Více informací

Seznam běžných logických spojek

Mezi běžně používané logické spojky patří:

• Negace (ne) : ¬, N (předpona), ~
• Spojka (a) : ∧, K (předpona), &, ∙
• Disjunkce (nebo) : ∨, A (předpona)
• Věcná implikace (pokud ... pak) : →, C (předpona), ⇒, ⊃
• Biconditional (if and only if) : ↔, E (prefix), ≡, =

Alternativní názvy pro biconditional jsou iff , xnor a bi-implication .

Například význam prohlášení, že prší (označeno P ) a já uvnitř (označeno Q), se transformuje, když jsou tyto dva kombinovány s logickými spojkami:

• Je to prší ( P )${\ Displaystyle \ neg}$
• Prší a já jsem uvnitř ( )${\ displaystyle P \ wedge Q}$
• Prší nebo jsem uvnitř ( )${\ displaystyle P \ lor Q}$
• Pokud prší, pak jsem uvnitř ( )${\ displaystyle P \ rightarrow Q}$
• Pokud jsem uvnitř, pak prší ( )${\ displaystyle Q \ rightarrow P}$
• Jsem uvnitř, jen když prší ( )${\ Displaystyle P \ leftrightarrow Q}$

Je také běžné považovat vždy pravdivý vzorec a vždy falešný vzorec za spojovací:

• Skutečný vzorec (⊤, 1, V [předpona] nebo T)
• Falešný vzorec (⊥, 0, O [předpona] nebo F)

Historie notací

• Negace: symbol ¬ objevil v Heyting v roce 1929 (ve srovnání s Frege ‚s symbol ⫟ v jeho Begriffsschrift ); symbol ~ se objevil v Russellu v roce 1908; alternativní notace je přidat vodorovnou čáru na začátek vzorce, jako v ; další alternativní notace je použít primární symbol jako v P '.${\ displaystyle {\ overline {P}}}$
• Konjunkce: symbol ∧ se objevil v Heytingu v roce 1929 (ve srovnání s Peanovým používáním set-teoretické notace křižovatky ∩); symbol & objevil se alespoň v Schönfinkel v roce 1924; symbol . pochází z Booleho výkladu logiky jako elementární algebry .
• Disjunkce: symbol ∨ se objevil v Russellu v roce 1908 (ve srovnání s Peanovým používáním set-teoretické notace spojení ∪); symbol + se také používá, a to navzdory nejednoznačnosti vyplývající ze skutečnosti, že + obyčejné elementární algebry je exkluzivní nebo je- li logicky interpretována ve dvouprvkovém kruhu ; přesně v historii použil Peirce a + společně s tečkou v pravém dolním rohu ,
• Důsledek: symbol → lze vidět u Hilberta v roce 1917; ⊃ použil Russell v roce 1908 (ve srovnání s převrácenou C notací Peana); ⇒ byl použit ve Vaxu.
• Biconditional: symbol ≡ použil alespoň Russell v roce 1908; ↔ používal alespoň Tarski v roce 1940; ⇔ byl použit ve Vaxu; další symboly se objevily včas v historii, jako je ⊃⊂ v Gentzen , ~ v Schönfinkel nebo ⊂⊃ v Chazal.
• Pravda: symbol 1 pochází z Booleovy interpretace logiky jako elementární algebry nad dvouprvkovou booleovskou algebrou ; další notace zahrnují (k nalezení v Peanu).${\ displaystyle \ bigwedge}$
• Nepravda: symbol 0 pochází také z Booleovy interpretace logiky jako prstenu; další notace zahrnují (k nalezení v Peanu).${\ displaystyle \ bigvee}$

Někteří autoři někdy v historii používali písmena pro spojky: u. pro spojení (němčina „und“ pro „a“) ​​a o. pro disjunkci (německý „oder“ pro „nebo“) v dřívějších dílech Hilberta (1904); N p pro negaci, K pq pro konjunkci, D pq pro alternativní popření, A pq pro disjunkci, X pq pro společné popření, C pq pro implikaci, E pq pro bikondicionální u Łukasiewicze (1929); srov. Polská notace .

Nadbytek

Takové logické pojivo, jako je opačná implikace „←“, je ve skutečnosti stejné jako materiální podmíněné se zaměněnými argumenty; symbol pro opačnou implikaci je tedy nadbytečný. V některých logických kalkulích (zejména v klasické logice ) jsou určité v zásadě odlišné složené příkazy logicky ekvivalentní . Méně triviální příklad redundance je klasický ekvivalence mezi ¬ P  ∨  Q a P  →  Q . Klasický logický systém proto nepotřebuje podmíněný operátor „→“, pokud se již používají „¬“ (ne) a „∨“ (nebo), nebo může použít „→“ pouze jako syntaktický cukr pro sloučenina mající jednu negaci a jednu disjunkci.

Existuje šestnáct booleovských funkcí, které spojují vstupní pravdivostní hodnoty P a Q se čtyřcifernými binárními výstupy. Ty odpovídají možným volbám binárních logických spojek pro klasickou logiku . Různé implementace klasické logiky mohou zvolit různé funkčně úplné podmnožiny spojovacích prvků.

Jedním z přístupů je vybrat minimální množinu a definovat další spojky nějakou logickou formou, jako v příkladu s výše uvedeným podmíněným materiálem. Níže jsou uvedeny minimální funkčně úplné sady operátorů v klasické logice, jejichž arity nepřesahují 2:

Jeden prvek

{↑}, {↓}.

Dva prvky

${\ displaystyle \ {\ vee, \ neg \}}$, , , , , , , , , , , , , , , , , .${\ Displaystyle \ {\ klín, \ neg \}}$${\ displaystyle \ {\ to, \ neg \}}$${\ displaystyle \ {\ gets, \ neg \}}$${\ displaystyle \ {\ to, \ bot \}}$${\ displaystyle \ {\ gets, \ bot \}}$${\ displaystyle \ {\ to, \ nleva dopravaarrow \}}$${\ displaystyle \ {\ gets, \ nlevá pravá šipka \}}$${\ displaystyle \ {\ to, \ nrightarrow \}}$${\ displaystyle \ {\ to, \ nleftarrow \}}$${\ displaystyle \ {\ gets, \ nrightarrow \}}$${\ displaystyle \ {\ gets, \ nleftarrow \}}$${\ displaystyle \ {\ nrightarrow, \ neg \}}$${\ Displaystyle \ {\ nlevá šipka, \ neg \}}$${\ displaystyle \ {\ nrightarrow, \ top \}}$${\ Displaystyle \ {\ nlevá šipka, \ top \}}$${\ displaystyle \ {\ nrightarrow, \ leftrightarrow \}}$${\ displaystyle \ {\ nlevá šipka, \ leftrightarrow \}}$

Tři prvky

${\ displaystyle \ {\ lor, \ leftrightarrow, \ bot \}}$, , , , , .${\ displaystyle \ {\ lor, \ leftrightarrow, \ nleftrightarrow \}}$${\ Displaystyle \ {\ lor, \ nlevá pravá šipka, \ nahoru \}}$${\ displaystyle \ {\ land, \ leftrightarrow, \ bot \}}$${\ displaystyle \ {\ land, \ leftrightarrow, \ nleftrightarrow \}}$${\ displaystyle \ {\ land, \ nleva doprava, \ top \}}$

Dalším přístupem je použít s rovnými právy spojky určité pohodlné a funkčně úplné, ale ne minimální sady. Tento přístup vyžaduje více výrokových axiomů a každá ekvivalence mezi logickými formami musí být buď axiom, nebo prokazatelná jako věta.

V intuitistické logice je však situace komplikovanější . Z jejích pěti spojek, {∧, ∨, →, ¬, ⊥}, lze pouze negaci „¬“ redukovat na další spojky (více viz Falešná (logika) § Falešná, negace a rozpor ). Ani konjunkce, disjunkce, ani materiální podmíněné nemají ekvivalentní formu vytvořenou z ostatních čtyř logických spojek.

Přirozený jazyk

Standardní logické spojky klasické logiky mají hrubé ekvivalenty v gramatikách přirozených jazyků. V angličtině , jako v mnoha jazycích, jsou takové výrazy obvykle gramatickými spojkami . Mohou však mít také formu komplementizátorů , přípon sloves a částic . Mezi významů přirozeného jazyka spojek je hlavním předmětem výzkumu v formální sémantiky , pole, které studuje logickou strukturu přirozené jazyky.

Významy přirozených jazykových spojek nejsou přesně totožné s jejich nejbližšími ekvivalenty v klasické logice. Zejména disjunkce může být exkluzivně interpretována v mnoha jazycích. Někteří vědci vzali tuto skutečnost jako důkaz, že sémantika přirozeného jazyka je neklasická . Jiní však udržují klasickou sémantiku tím, že navrhují pragmatické popisy exkluzivity, které vytvářejí iluzi neklasicismu. V takových účtech je exkluzivita obvykle považována za skalární implikaci . Související hádanky zahrnující disjunkci zahrnují závěry o svobodné volbě , Hurfordovo omezení a přínos disjunkce v alternativních otázkách .

Mezi další zjevné nesrovnalosti mezi přirozeným jazykem a klasickou logikou patří paradoxy materiální implikace , oslí anafora a problém kontrafaktuálních podmíněností . Tyto jevy byly brány jako motivace pro identifikaci denotací přirozených jazykových kondicionálů s logickými operátory včetně přísných podmíněných , proměnně přísných podmíněných a různých dynamických operátorů.

Následující tabulka ukazuje standardní klasicky definovatelné aproximace pro anglická spojovací zařízení.

Anglické slovo	Spojovací	Symbol	Logická brána
ne	negace	"¬"	NE
a	spojení	"∧"	A
nebo	disjunkce	"∨"	NEBO
kdyby ... tak	materiální implikace	"→"	IMPLY
...li	opačná implikace	"←"
kdyby a jen kdyby	dvoupodmínečné	"↔"	XNOR
ne obojí	alternativní odmítnutí	"↑"	NAND
ani ... ani	společné popření	"↓"	ANI
ale ne	materiální neimplikace	"↛"	NIMPLY

Vlastnosti

Některé logické spojky mají vlastnosti, které mohou být vyjádřeny ve větách obsahujících pojivo. Některé z těchto vlastností, které může mít logické spojení, jsou:

Asociativita

V rámci výrazu obsahujícího dvě nebo více stejných asociativních spojek za sebou nezáleží na pořadí operací, pokud se nezmění posloupnost operandů.

Komutativita

Operandy pojiva mohou být prohozeny, čímž se zachová logická ekvivalence původního výrazu.

Distribuce

Spojka označená · se distribuuje přes jinou spojku označenou +, pokud a · ( b + c ) = ( a · b ) + ( a · c ) pro všechny operandy a , b , c .

Idempotence

Kdykoli jsou operandy operace stejné, sloučenina je logicky ekvivalentní operandu.

Vstřebávání

Dvojice spojek ∧, ∨ splňuje absorpční zákon, pokud pro všechny operandy a , b .${\ Displaystyle a \ land (a \ lor b) = a}$

Monotónnost

Pokud f ( a ₁ , ..., a _n ) ≤ f ( b ₁ , ..., b _n ) pro všechny a ₁ , ..., a _n , b ₁ , ..., b _n ∈ {0 , 1} tak, že a ₁ ≤ b ₁ , a ₂ ≤ b ₂ , ..., a _n ≤ b _n . Např. ∨, ∧, ⊤, ⊥.

Afinita

Každá proměnná vždy ovlivňuje pravdivostní hodnotu operace, nebo nikdy nezmění. Např. ¬, ↔ ,, ⊤, ⊥.${\ Displaystyle \ nleva doprava šipka$

Dualita

Číst přiřazení pravdivostní hodnoty pro operaci shora dolů v její tabulce pravdivosti je stejné jako brát doplněk čtení tabulky stejného nebo jiného spojovacího prvku zdola nahoru. Aniž by se uchýlili k pravdivostním tabulkám, mohou být formulovány jako g̃ (¬ a ₁ , ..., ¬ a _n ) = ¬ g ( a ₁ , ..., a _n ) . Např. ¬.

Zachování pravdy

Sloučenina všech těchto argumentů je tautologie je tautologie sama. Např. ∨, ∧, ⊤, →, ↔, ⊂ (viz platnost ).

Zachování falešnosti

Sloučenina, kterou všechny tyto argumenty představují protiklady, je sama o sobě rozporem. Např. ∨, ∧ ,, ⊥, ⊄, ⊅ (viz platnost ).${\ Displaystyle \ nleva doprava šipka$

Involutivita (pro unární spojky)

f ( f ( a )) = a . Např. Negace v klasické logice.

Pro klasickou a intuicionistickou logiku znamená symbol "=", že odpovídající implikace "... → ..." a "... ← ..." pro logické sloučeniny lze dokázat jak jako věty, tak jako symbol "≤" znamená, že „... → ...“ pro logické sloučeniny je důsledkem odpovídajících spojek „... → ...“ pro výrokové proměnné. Některé logiky s mnoha hodnotami mohou mít nekompatibilní definice ekvivalence a řádu (implikace).

Konjunkce i disjunkce jsou v klasické logice asociativní, komutativní a idempotentní, většina druhů mnohocenné logiky a intuitionistické logiky. Totéž platí o distribučnosti spojky nad disjunkcí a disjunkcí nad konjunkcí, stejně jako o absorpčním zákonu.

V klasické logice a některých variantách mnohocenné logiky jsou konjunkce a disjunkce dvojí a negace je duální, druhá je také duální v intuitistické logice.

Pořadí přednosti

Jako způsob, jak snížit počet nezbytných závorek, lze zavést pravidla přednosti : ¬ má vyšší prioritu než ∧, ∧ vyšší než ∨ a ∨ vyšší než →. Například je zkratka pro . ${\ Displaystyle P \ vee Q \ wedge {\ neg R} \ rightarrow S}$${\ Displaystyle (P \ vee (Q \ wedge (\ neg R))) \ rightarrow S}$

Zde je tabulka, která ukazuje běžně používanou přednost logických operátorů.

${\ displaystyle {\ begin {array} {c | c} {\ text {Operator}} & {\ text {Precedence}} \\\ hline \ neg & 1 \\\ land & 2 \\\ vee & 3 \\\ to & 4 \\\ šipka vlevo & 5 \ end {array}}}$

Ne všichni kompilátoři však používají stejné pořadí; například bylo také použito uspořádání, ve kterém má disjunkce nižší prioritu než implikace nebo bi-implikace. Někdy je přednost mezi spojkou a disjunkcí nespecifikovaná a vyžaduje, aby byla výslovně uvedena v daném vzorci v závorkách. Pořadí priority určuje, které pojivo je „hlavní pojivem“ při interpretaci neatomového vzorce.

Počítačová věda

Pravdivě funkční přístup k logickým operátorům je implementován jako logická hradla v digitálních obvodech . Prakticky všechny digitální obvody (hlavní výjimkou je DRAM ) jsou vytvořeny z NAND , NOR , NOT a přenosových bran ; viz další podrobnosti ve funkci Pravda v informatice . Logické operátory přes bitové vektory (odpovídající konečným booleovským algebrám ) jsou bitové operace .

Ale ne každé použití logického pojiva v počítačovém programování má booleovskou sémantiku. Například pro P  ∧  Q a P  ∨  Q je někdy implementováno líné hodnocení , takže tyto spojky nejsou komutativní, pokud jeden nebo oba výrazy P , Q mají vedlejší účinky . Také podmiňovací způsob , který v jistém smyslu odpovídá hmotnému podmíněnému pojivu, je v zásadě neboleanský, protože pro , následný Q se neprovede, pokud předchůdce  P je falešný (ačkoli sloučenina jako celek je úspěšná ≈ „true“ v takový případ). To se blíží spíše intuicionistickým a konstruktivistickým pohledům na materiální podmíněné - než pohledům klasické logiky. if (P) then Q;

Viz také

Poznámky

Reference

Prameny

• Bocheński, Józef Maria (1959), A Précis of Mathematical Logic , přeložil z francouzského a německého vydání Otto Bird, D. Reidel, Dordrecht, Jižní Holandsko.
• Enderton, Herbert (2001), Matematický úvod do logiky (2. vydání), Boston, MA: Academic Press, ISBN 978-0-12-238452-3
• Gamut, LTF (1991), „Kapitola 2“, Logika, jazyk a význam , 1 , University of Chicago Press, s. 54–64, OCLC  21372380
• Rautenberg, W. (2010), Stručný úvod do matematické logiky (3. vydání), New York : Springer Science+Business Media , doi : 10.1007/978-1-4419-1221-3 , ISBN 978-1-4419-1220-6.
• Humberstone, Lloyd (2011). The Connectives . Stiskněte MIT. ISBN 978-0-262-01654-4.

externí odkazy

• „Propositional Connective“ , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Lloyd Humberstone (2010), „ Sentence Connectives in Formal Logic “, Stanford Encyclopedia of Philosophy ( Abstrakt algebraický logický přístup k spojkám.)
• John MacFarlane (2005), „ Logické konstanty “, Stanfordská encyklopedie filozofie .