Logické pojivo - Logical connective

tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Dubna 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Hasseův diagram logických spojek.

v logika, a logické pojivo (také nazývaný a logický operátor, sentenciální spojovacínebo sentenciální operátor) je symbol nebo slovo slouží k připojení dvou nebo více věty (buď a formální nebo a přirozený jazyk ) v gramaticky platné takovým způsobem, že hodnota vytvořené složené věty závisí pouze na hodnotě původních vět a na významu spojovacího výrazu.

Nejběžnější logické spojky jsou binární spojky (také zvaný dyadické spojky), které spojují dvě věty a které lze považovat za funkci operandy. Další běžné logické pojivo, negace, je považován za a unární spojovací.^[1]

Logické spojky spolu s kvantifikátory, jsou dva hlavní typy logické konstanty použito v formální systémy (jako výroková logika a predikátová logika ). Sémantika logické spojky je často (ale ne vždy) prezentována jako a funkce pravdy.

Logická spojka je podobná, ale ne ekvivalentní syntaxi běžně používané v programovacích jazycích zvané a podmíněný operátor.^[2]

V jazyce

Přirozený jazyk

V gramatice přirozených jazyků mohou být dvě věty spojeny a gramatická spojka vytvořit a gramaticky složená věta. Některé, ale ne všechny takové gramatické spojky jsou pravda funkční. Zvažte například následující věty:

Ve výše uvedeném seznamu vět si všimněte, že slova označená C a D používají slova a a tak. Tato slova se nazývají gramatické spojky protože spojují dvě věty (A) a (B), tvoří složené věty (C) a (D). Slovo a ve větě (C) je a logický spojovací. Všimněte si, že pravda (C) jako sloučeniny je pravdivá nebo nepravdivá. Ale (C) je zcela určeno tím, jaká pravda je nalezena pro jednodušší větu (A), jednodušší větu (B) a logickou definici a. Nemělo by to smysl a bylo by v rozporu s pravidly logiky tvrdit, že (A) je pravda a (B) je pravda, ale popírá to, že (C) je pravda. Nicméně slovo tak v (D) není logické pojivo, protože by bylo docela rozumné potvrdit (A) a (B), ale popřít (D): možná koneckonců Jill šla do kopce, aby přinesla vodu, ne proto Jack vůbec šel do kopce.

Různá anglická slova a slovní páry vyjadřují logická spojka a některá jsou synonyma. Mezi ně patří mimo jiné:

Formální jazyky

Ve formálních (logických) jazycích jsou pravdivostní funkce reprezentovány jednoznačnými symboly. To umožňuje, aby logické příkazy nebyly chápány nejednoznačně. Tyto symboly se nazývají logické spojky, logické operátory, výrokové operátory, nebo v klasická logika, pravda-funkční spojky. Pravidla, která umožňují vytváření nových dobře formulovaných vzorců spojením dalších dobře formulovaných vzorců pomocí spojek pravdivých funkcí, viz dobře formulovaný vzorec.

Logické spojky lze použít k propojení více než dvou příkazů, takže o nich lze mluvit n-ary logické pojivo.

Běžné logické spojky

Symbol, jméno		Pravda stůl					Venn diagram
Nulové spojky (konstanty)
⊤	Pravda /tautologie				1
⊥	Faleš /rozpor				0
Unární spojky
		P =	0		1
	Tvrzení P		0		1
¬	Negace		1		0
Binární spojky
		P =	0		1
		Q =	0	1	0	1
	Tvrzení P		0	0	1	1
	Tvrzení Q		0	1	0	1
∧	Spojení		0	0	0	1
↑	Alternativní popření		1	1	1	0
∨	Disjunkce		0	1	1	1
↓	Společné popření		1	0	0	0
→	Materiál podmíněný		1	1	0	1
${displaystyle leftrightarrow}$	Exkluzivní nebo		0	1	1	0
↔	Dvojpodmínečné		1	0	0	1
←	Konverzní implikace		1	0	1	1
Více informací

Seznam běžných logických spojek

Mezi běžně používané logické spojky patří:^[1][3]

• Negace (ne): ¬, N (předpona), ~^[4]
• Spojení (a): ∧, K (předpona), &, ∙
• Disjunkce (nebo): ∨, A (předpona)
• Materiální implikace (pokud ... pak): →, C (předpona), ⇒, ⊃
• Biconditional (pokud a pouze pokud): ↔, E (předpona), ≡, =

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

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

• to je ne prší (${displaystyle eg}$P)
• Prší a Jsem uvnitř (${displaystyle Pwedge Q}$)
• Prší nebo Jsem uvnitř (${displaystyle Plor Q}$)
• Li prší, pak Jsem uvnitř (${displaystyle Pightarrow Q}$)
• Li Jsem uvnitř, pak prší (${displaystyle Qightarrow P}$)
• Jsem uvnitř kdyby a jen kdyby prší (${displaystyle Pleftrightarrow Q}$)

Je také běžné vzít v úvahu vždy pravda vzorec a vždy nepravdivé vzorec, který má být spojovací:^[1]

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

Historie notací

• Negace: objevil se symbol ¬ Hej v roce 1929^[5][6] (porovnat s Frege symbol ⫟ v jeho Begriffsschrift ); symbol ~ se objevil v Russell v roce 1908;^[7] alternativní notací je přidání vodorovné čáry na horní část vzorce, jako v ${displaystyle {overline {P}}}$;^[1] další alternativní notace je použít a hlavní symbol jako v P '.
• Spojení: symbol ∧ se objevil v Heytingu v roce 1929^[5] (porovnat s Peano je použití množinově-teoretické notace průsečík ∩^[8]); symbol a objevil se alespoň v Schönfinkel v roce 1924;^[9] symbol . pochází z Boole Výklad logiky jako elementární algebra.
• Disjunkce: objevil se symbol ∨ Russell v roce 1908^[7] (porovnat s Peano je použití množinově-teoretické notace svaz ∪); používá se také symbol +, a to navzdory nejednoznačnosti vyplývající ze skutečnosti, že + je běžné elementární algebra je exkluzivní nebo při logické interpretaci ve dvou prvcích prsten; přesně v historii bylo použito + spolu s tečkou v pravém dolním rohu Peirce,^[10]
• Implikace: symbol → je vidět v Hilbert v roce 1917;^[11] ⊃ byl používán Russellem v roce 1908^[7] (ve srovnání s Peanovou obrácenou C notací); ⇒ bylo použito ve Vax.^[12]
• Biconditional: symbol ≡ byl používán přinejmenším Russellem v roce 1908;^[7] ↔ bylo použito alespoň uživatelem Tarski v roce 1940;^[13] ⇔ byl použit ve Vaxu; další symboly se v historii objevily přesně, například ⊃⊂ in Gentzen,^[14] ~ ve Schönfinkelu^[9] nebo ⊂⊃ v Chazalu.^[15]
• Je pravda: symbol 1 pochází z Boole Výklad logiky jako elementární algebra přes dvouprvková booleovská algebra; další notace zahrnují ${displaystyle igwedge}$ (lze nalézt v Peanu).
• False: symbol 0 pochází také z Booleovy interpretace logiky jako prstenu; další notace zahrnují ${displaystyle igvee}$ (lze nalézt v Peanu).

Někteří autoři používali dopisy pro spojovací články v určité době historie: u. pro spojení (německé „und“ pro „a“) ​​a Ó. pro disjunkci (německý „oder“ pro „nebo“) v dřívějších dílech Hilberta (1904); Np pro negaci, K.pq pro konjunkci, Dpq pro alternativní popření, Apq pro disjunkci, Xpq za společné popření, Cpq pro implikaci, Epq pro biconditional v Łukasiewicz (1929);^[16] srov. Polská notace.

Nadbytek

Logické spojení jako obrácené implikace „←“ je ve skutečnosti stejné jako materiál podmíněný s vyměněnými argumenty; symbol pro konverzní implikaci je tedy nadbytečný. V některých logických kalkulích (zejména v klasická logika ), jsou určité podstatně odlišné složené výroky logicky ekvivalentní. Méně triviální příkladem redundance je klasická ekvivalence mezi ¬P ∨ Q a P → Q. Klasický logický systém proto nepotřebuje podmíněný operátor „→“, pokud „¬“ (ne) a „∨“ (nebo) jsou již používány, nebo může použít „→“ pouze jako syntaktický cukr pro sloučeninu, která má jednu negaci a jednu disjunkci.

Je jich šestnáct Booleovské funkce přidružení vstupu pravdivostní hodnoty P a Q se čtyřmístným číslem binární výstupy.^[17] Ty odpovídají možným možnostem binárních logických spojek pro klasická logika. Různé implementace klasické logiky si mohou vybrat různé funkčně kompletní podmnožiny spojek.

Jedním z přístupů je zvolit a minimální set a definovat další spojovací prvky nějakou logickou formou, jako v příkladu s výše uvedeným podmíněným materiálem. Následující jsou minimální funkčně kompletní sady operátorů v klasické logice, jejíž artefakty nepřesahují 2:

Jeden prvek

{↑}, {↓}.

Dva prvky

${displaystyle {vee, eg}}$, ${displaystyle {wedge, eg}}$, ${displaystyle {o, eg}}$, ${displaystyle {gets, eg}}$, ${displaystyle {o, ot}}$, ${displaystyle {gets, ot}}$, ${displaystyle {o, leftrightarrow}}$, ${displaystyle {gets, leftrightarrow}}$, ${displaystyle {o, rightarrow}}$, ${displaystyle {o, leftarrow}}$, ${displaystyle {gets, rightarrow}}$, ${displaystyle {gets, leftarrow}}$, ${displaystyle {rightarrow, eg}}$, ${displaystyle {leftarrow, eg}}$, ${displaystyle {rightarrow, op}}$, ${displaystyle {leftarrow, op}}$, ${displaystyle {rightarrow, leftrightarrow}}$, ${displaystyle {leftarrow, leftrightarrow}}$.

Tři prvky

${displaystyle {lor, leftrightarrow, ot}}$, ${displaystyle {lor, leftrightarrow, leftrightarrow}}$, ${displaystyle {lor, leftrightarrow, op}}$, ${displaystyle {land, leftrightarrow, ot}}$, ${displaystyle {land, leftrightarrow, leftrightarrow}}$, ${displaystyle {land, leftrightarrow, op}}$.

Dalším přístupem je použití spojovacích prostředků se stejnými právy určitého pohodlného a funkčně úplného, ​​ale ne minimální soubor. Tento přístup vyžaduje více výroků axiomy a každá rovnocennost mezi logickými formami musí být buď axiom nebo prokazatelná jako věta.

Situace je však v intuicionistická logika. Z jeho pěti spojek, {∧, ∨, →, ¬, ⊥}, lze pouze negaci „¬“ redukovat na další spojky (viz False (logika) § False, negace a rozpor více). Ani konjunkce, disjunkce ani podmíněný materiál nemají ekvivalentní formu vytvořenou z ostatních čtyř logických spojek.

Vlastnosti

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

Asociativita

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

Komutativita

Operandy pojiva mohou být zaměněny za zachování logické rovnocennosti s původním výrazem.

Distribuce

Spojovací prostředek označený · distribuuje přes jiný spojovací prostředek označený +, 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 ${displaystyle aland (alor b) = a}$ pro všechny operandy A, b.

Monotónnost

Li F(A₁, ..., A_n) ≤ F(b₁, ..., b_n) pro všechny A₁, ..., A_n, b₁, ..., b_n 0,1 {0,1} takové A₁ ≤ b₁, A₂ ≤ b₂, ..., A_n ≤ b_n. Např. ∨, ∧, ⊤, ⊥.

Afinita

Každá proměnná vždy dělá rozdíl v pravdivostní hodnotě operace, nebo nikdy nedělá rozdíl. Např., ¬, ↔, ${displaystyle leftrightarrow}$, ⊤, ⊥.

Dualita

Číst přiřazení pravdivostní hodnoty pro operaci shora dolů pravdivostní tabulka je totéž jako převzít doplněk čtení tabulky stejné nebo jiné spojky zdola nahoru. Bez uchýlení se k tabulkám pravdy to může být formulováno jako G(¬A₁, ..., ¬A_n) = ¬G(A₁, ..., A_n). Např. ¬.

Zachování pravdy

Složkou všech těchto argumentů jsou tautologie je tautologie sama. Např., ∨, ∧, ⊤, →, ↔, ⊂ (viz platnost ).

Zachování lži

Sloučenina všech těchto argumentů je rozpory je rozpor sám o sobě. Např., ∨, ∧, ${displaystyle leftrightarrow}$, ⊥, ⊄, ⊅ (viz platnost ).

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 prokázat jako věty, a symbol „≤“ znamená, že „… →…“ pro logické sloučeniny je důsledkem odpovídajících spojek „… →…“ pro výrokové proměnné. Nějaký mnohocenné logiky může mít nekompatibilní definice ekvivalence a řádu (důsledek).

Konjunkce i disjunkce jsou v klasické logice asociativní, komutativní a idempotivní, většina odrůd mnohohodnotné logiky a intuicionistické logiky. Totéž platí pro distributivitu konjunkce nad disjunkcí a disjunkce nad konjunkcí, stejně jako pro absorpční zákon.

V klasické logice a některých odrůdách mnohohodnotové logiky jsou konjunkce a disjunkce dvojí a negace je sebe-duální, druhá je také intuitivní logikou.

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Březen 2012)

Pořadí priority

Jako způsob snížení počtu nezbytných závorek lze uvést pravidla priority: ¬ má vyšší prioritu než ∧, ∧ vyšší než ∨ a ∨ vyšší než →. Například ${displaystyle Pvee Qwedge {např. R} ightarrow S}$ je zkratka pro ${displaystyle (Pvee (Qwedge (např. R))) ightarrow S}$.

Zde je tabulka, která ukazuje běžně používanou prioritu logických operátorů.^[18]

${displaystyle {egin {array} {c | c} {ext {Operator}} & {ext {Precedence}} hline eg & 1 land & 2 vee & 3 o & 4 leftrightarrow & 5end {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 menší přednost než implikace nebo bi-implikace.^[19] Někdy je priorita mezi spojkou a disjunkcí nespecifikována, což vyžaduje výslovné poskytnutí v daném vzorci se závorkami. Pořadí priorit určuje, které pojivo je „hlavní pojivo“ při interpretaci jiného než atomového vzorce.

Počítačová věda

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Březen 2012)

Pravda-funkční přístup k logickým operátorům je implementován jako logické brány v digitální obvody. Prakticky všechny digitální obvody (hlavní výjimkou je DOUŠEK ) jsou vytvořeny z NAND, ANI, NE, a přenosové brány; zobrazit více podrobností v Funkce pravdy v informatice. Logické operátory skončily bitové vektory (odpovídá konečnému Booleovy algebry ) jsou bitové operace.

Ale ne každé použití logického spojovacího prvku v programování má booleovskou sémantiku. Například, líné hodnocení je někdy implementován pro P ∧ Q a P ∨ Q, takže tyto spojky nejsou komutativní, pokud je jeden nebo oba výrazy P, Q mít vedlejší efekty. Také, a podmiňovací způsob, což v jistém smyslu odpovídá materiál podmíněný spojovací, je v zásadě non-Boolean, protože pro pokud (P), pak Q;, následné Q se neprovede, pokud předchůdce P je nepravdivé (ačkoli sloučenina jako celek je v takovém případě úspěšná ≈ „true“). To je blíže intuiciu a konstruktivistický pohledy na materiál podmíněné - spíše než na pohledy klasické logiky.

Viz také

Poznámky

Reference

• Bocheński, Józef Maria (1959), Précis matematické logiky, přeloženo 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.), Boston, MA: Academic Press, ISBN  978-0-12-238452-3
• Gamut, L.T.F. (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.), New York: Springer Science + Business Media, doi:10.1007/978-1-4419-1221-3, ISBN  978-1-4419-1220-6.

Další čtení

• Lloyd Humberstone (2011). Spojovací látky. MIT Stiskněte. ISBN  978-0-262-01654-4.

externí odkazy

• „Propoziční pojivo“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Lloyd Humberstone (2010), "Sentence Connectives ve formální logice ", Stanfordská encyklopedie filozofie (An abstraktní algebraická logika přístup ke spojovacím prvkům.)
• John MacFarlane (2005), "Logické konstanty ", Stanfordská encyklopedie filozofie.