Logický spojovací (též logický operátor) je v logice symbol nebo slovo, které se používá ke spojení dvou nebo více vět (buď formálního nebo přirozeného jazyka) gramaticky platným způsobem tak, že složená věta má pravdivostní hodnotu závislou na příslušných pravdivostních hodnotách původních vět.
Každá logická spojka může být vyjádřena jako funkce, nazývaná pravdivostní funkce. Z tohoto důvodu jsou logické spojky někdy nazývány pravdivě-funkční spojky. Nejběžnější logické spojky jsou binární spojky (nazývané také dyadické spojky), které spojují dvě věty, jejichž pravdivostní hodnoty mohou být považovány za operandy funkce. Také běžně je negace považována za unární spojku.
Logické spojky spolu s kvantifikátory jsou dva hlavní typy logických konstant používané ve formálních systémech, jako je výroková logika a predikátová logika.
Slova a a tak jsou gramatické spojky spojující věty (A) a (B) za účelem vytvoření složených vět (C) a (D). A v (C) je logická spojka, protože pravdivost (C) je zcela určena (A) a (B): nemělo by smysl potvrzovat (A) a (B), ale popírat (C). Nicméně tak v (D) není logická spojka, protože by bylo docela rozumné potvrzovat (A) a (B), ale popírat (D): možná nakonec Jill šla na kopec pro vědro s vodou, ne proto, že by Jack vůbec šel na Kopec.
Různá anglická slova a slovní páry vyjadřují pravdivostní funkce a některá z nich jsou synonyma. Příklady (s názvem vztahu v závorkách) jsou:
Ve formálních jazycích jsou pravdivostní funkce reprezentovány jednoznačnými symboly; ty mohou být přesně definovány pomocí pravdivostních tabulek. Existuje 16 binárních pravdivostních tabulek, a tedy 16 různých logických spojnic, které spojují přesně dva příkazy, které mohou být definovány. Ne všechny z nich se běžně používají. Tyto symboly se nazývají „pravdivě-funkční spojky“, „logické spojky“, „logické operátory“ nebo „výrokové operátory“. Viz dobře vytvořený vzorec pro pravidla, která umožňují sestavení nových dobře vytvořených vzorců spojením jiných dobře vytvořených vzorců pomocí pravdivě-funkčních spojek.
Vennovy diagramy ilustrují logické spojovací omezení všech kvantifikátorů na pevnou doménu diskurzu ve formálním jazyce.
Logické spojky mohou být použity k propojení více než dvou příkazů. Odbornější definice je, že „n-ární logická spojka“ je funkce, která přiřazuje pravdivostní hodnoty „true“ nebo „false“ k n-tuples pravdivostních hodnot.
Běžné logické spojky
Seznam běžných logických spojek
Pro výrok P = Prší a Q = Jsem uvnitř.
Je také běžné považovat vždy pravdivý vzorec a vždy falešný vzorec za spojovací:
Někteří autoři používali v některých obdobích historie písmena pro spojky: u. pro spojku (německy „und“ pro „a“) a o. pro disjunkci (německy „oder“ pro „nebo“) v dřívějších Hilbertových dílech (1904); N pro negaci, K pro spojku, A pro disjunkci, C pro implikaci, E pro biconditional v Łukasiewicz (1929).
Tabulka binárních logických spojek
Existuje šestnáct booleovských funkcí, které spojují vstupy P a Q se čtyřmístnými binárními výstupy.
Ne všechny výše uvedené operátory jsou nutné pro funkčně kompletní logický kalkul. Určité složené příkazy jsou logicky ekvivalentní. Například ¬ P ∨ Q je logicky ekvivalentní k P → Q. Podmíněný operátor „→“ tedy není nutný, pokud „¬“ (not) a „∨“ (or) jsou již používány.
Minimální množina operátorů, která může vyjádřit každý výrok vyjádřený v výrokovém kalkulu, se nazývá minimální funkčně úplná množina. Minimálně úplná množina operátorů je dosažena samotným NAND {↑} a samotným NOR {↓}.
Níže jsou uvedeny minimální funkčně úplné množiny operátorů, jejichž aritmetika nepřesahuje 2:
Logické spojky mají každý jiný soubor vlastností, které mohou být vyjádřeny v větách obsahujících spojky. Některé z těch vlastností, které logické spojky mohou mít jsou:
Sada operátorů je funkčně kompletní tehdy a jen tehdy, pokud pro každou z následujících pěti vlastností obsahuje alespoň jednoho člena, který ji postrádá:
V dvouhodnotové logice jsou 2 nullary operátory (konstanty), 4 unary operátory, 16 binární operátory, 256 ternary operátory a n-ary operátory. V trojhodnotové logice jsou 3 nullary operátory (konstanty), 27 unary operátory, 19683 binární operátory, 7625597484987 ternary operátory a n-ary operátory. V k-hodnotové logice jsou k nullary operátory, unary operátory, binární operátory, ternary operátory a n-ary operátory. N-ary operátor v k-hodnotové logice je funkce od . Proto je počet takových operátorů , podle kterého byla výše uvedená čísla odvozena.
Některé operátory určité arity jsou však ve skutečnosti degenerované formy, které na některých vstupech provádějí operaci s nižším aritmetickým číslem a zbytek vstupů ignorují. Z výše uvedených 256 trojných booleovských operátorů jsou takovými degenerovanými formami binárních operátorů nebo operátorů s nižším aritmetickým číslem, které používají princip vyloučení. Trojnásobný operátor je jedním z takových operátorů, který je ve skutečnosti unární operátor aplikovaný na jeden vstup a ostatní dva vstupy ignoruje.
„Ne“ je unární operátor, má jeden výraz (¬ P). Zbytek jsou binární operátory, pro složený příkaz jsou potřeba dva výrazy (P Q, P Q, P → Q, P ↔ Q).
Soubor logických operátorů lze rozdělit do disjunktních podskupin takto:
V této oblasti, je sada operátoru symboly arity .
V známější výrokové kalkuly, je typicky rozdělena takto:
Zde je tabulka, která ukazuje běžně používanou prioritu logických operátorů.
Pořadí priorit určuje, který spojivec je „hlavním spojivem“ při interpretaci neatomického vzorce.
Zásada kompozice
Místo použití pravdivostních tabulek lze logické spojovací symboly interpretovat pomocí interpretační funkce a funkčně úplné množiny pravdivostních funkcí (Gamut 1991), jak je podrobně popsáno principem kompozitivity významu.
Nechť jsem interpretační funkcí, nechť Φ, Ψ jsou libovolné dvě věty a nechť pravdivostní funkce fnand je definována takto:
Pak, pro pohodlí, fnot, pro fand a tak dále jsou definovány pomocí fnand:
nebo alternativně fnot, pro fand a tak dále jsou definovány přímo:
Je-li tedy S věta, která je řetězcem symbolů skládajících se z logických symbolů v1…vn představujících logické spojky a nelogických symbolů c1…cn , pak tehdy a jen tehdy, pokud I(v1)…I(vn) byla poskytnuta interpretace v1 na vn pomocí fnand (nebo jiného souboru funkčních úplných pravdivostních funkcí), pak pravdivostní hodnota I(s) je určena výhradně pravdivostními hodnotami c1…cn, tj. I(c1)…I(cn). Jinými slovy, jak se očekává a vyžaduje, S je pravda nebo lež pouze při interpretaci všech svých nelogických symbolů.
Logické operátory jsou implementovány jako logické brány v digitálních obvodech. Prakticky všechny digitální obvody (hlavní výjimkou je DRAM) jsou sestaveny z NAND, NOR, NOT a přenosových bran. NAND a NOR brány s 3 a více vstupy namísto obvyklých 2 vstupů jsou poměrně běžné, i když jsou logicky ekvivalentní kaskádě 2-vstupních bran. Všechny ostatní operátory jsou implementovány jejich rozdělením do logicky ekvivalentní kombinace 2 a více výše uvedených logických bran.
„Logická ekvivalence“ pojmů „NAND alone“, „NOR alone“ a „NOT and AND“ je podobná Turingově ekvivalenci.
Je nějaká nová technologie (například reverzibilní výpočty, logika bez hodin nebo výpočty s kvantovými tečkami) „funkčně úplná“ v tom smyslu, že může být použita k sestavení počítačů, které umí všechny druhy výpočtů, které umí počítače založené na CMOS? Pokud dokáže implementovat operátora NAND, teprve pak je funkčně úplná.
Skutečnost, že všechny logické spojky mohou být vyjádřeny pouze pomocí NOR, je demonstrována naváděcím počítačem Apollo.