V logice je logická spojka (nazývaná také logický operátor) symbol nebo slovo používané ke spojení dvou nebo více vět (formálního nebo přirozeného jazyka) gramaticky platným způsobem tak, že vzniklá složená věta má pravdivostní hodnotu závislou na příslušných pravdivostních hodnotách původních vět.
Každou logickou spojku lze vyjádřit jako funkci, která se nazývá pravdivostní funkce. Z tohoto důvodu se logické spojky někdy nazývají pravdivostně funkční spojky. Nejběžnějšími logickými spojkami jsou binární spojky (nazývané také dyadické spojky), které spojují dvě věty, jejichž pravdivostní hodnoty lze považovat za operandy funkce. Běžně se za unární konektor považuje také negace.
Logické spojky spolu s kvantifikátory jsou dva hlavní typy logických konstant používaných ve formálních systémech, jako je výroková logika a predikátová logika.
Slova and a so jsou gramatické spojky, které spojují věty (A) a (B) do složených vět (C) a (D). Spojka a v (C) je logickou spojkou, protože pravdivost věty (C) je zcela určena větami (A) a (B): nemělo by smysl tvrdit (A) a (B), ale popírat (C). Avšak so v (D) není logickou spojkou, protože by bylo zcela rozumné tvrdit (A) a (B), ale popírat (D): možná přece Jill šla na kopec pro vědro vody, nikoli proto, že Jack na kopec vůbec šel.
Různá anglická slova a dvojice slov vyjadřují pravdivostní funkce a některá z nich jsou synonyma. Příklady (s názvem vztahu v závorce):
Ve formálních jazycích jsou pravdivostní funkce reprezentovány jednoznačnými symboly, které lze přesně definovat pomocí pravdivostních tabulek. Existuje 16 binárních pravdivostních tabulek, a tedy 16 různých logických spojek, které spojují přesně dva výroky, které lze definovat. Ne všechny z nich se běžně používají. Tyto symboly se nazývají „pravdivostně funkční spojky“, „logické spojky“, „logické operátory“ nebo „výrokové operátory“. Pravidla, která umožňují konstruovat nové dobře formulované formule spojením jiných dobře formulovaných formulí pomocí pravdivostně-funkčních konektorů, viz dobře formulované formule.
Vennovy diagramy znázorňují logické spojovací omezení všech kvantifikátorů na pevnou oblast diskurzu ve formálním jazyce.
Logické spojky lze použít k propojení více než dvou výroků. Techničtější definice říká, že „n-ární logická spojka“ je funkce, která přiřazuje pravdivostní hodnoty „true“ nebo „false“ n-ticím 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 formuli vždy pravdivou a formuli vždy nepravdivou za konektivní:
Někteří autoři v určitém historickém období používali písmena pro spojky: u. pro konjunkci (německé „und“ pro „a“) a o. pro disjunkci (německé „oder“ pro „nebo“) ve starších pracích Hilberta (1904); N pro negaci, K pro konjunkci, A pro disjunkci, C pro implikaci, E pro bikondicionál u Łukasiewicze (1929).
Tabulka binárních logických spojek
Existuje šestnáct booleovských funkcí přiřazujících vstupům P a Q čtyřmístné binární výstupy.
Ne všechny výše uvedené operátory jsou pro funkčně úplný logický kalkul nezbytné. Některé složené výroky jsou logicky ekvivalentní. Například ¬P ∨ Q je logicky ekvivalentní P → Q. Podmíněný operátor „→“ tedy není nutný, pokud jsou již použity operátory „¬“ (ne) a „∨“ (nebo).
Minimální množina operátorů, která může vyjádřit každý výrok vyjádřitelný ve výrokovém kalkulu, se nazývá minimální funkčně úplná množina. Minimálně úplnou množinu operátorů tvoří pouze operátory NAND {↑} a NOR {↓}.
Následují minimální funkčně úplné množiny operátorů, jejichž arity nepřesahují 2:
Logické spojky mají každá jiný soubor vlastností, které mohou být vyjádřeny ve větách obsahujících danou spojku. Některé z těchto vlastností, které může mít logická spojka, jsou:
Množina operátorů je funkčně úplná tehdy a jen tehdy, když pro každou z následujících pěti vlastností obsahuje alespoň jeden člen, který ji postrádá:
V dvouhodnotové logice existují 2 nulové operátory (konstanty), 4 unární operátory, 16 binárních operátorů, 256 ternárních operátorů a n-ární operátory. V tříhodnotové logice jsou 3 nulové operátory (konstanty), 27 unárních operátorů, 19683 binárních operátorů, 7625597484987 ternárních operátorů a n-árních operátorů. V k-hodnotové logice existuje k nulových operátorů, unárních operátorů, binárních operátorů, ternárních operátorů a n-árních operátorů. N-ární operátor v k-hodnotové logice je funkce z . Proto je počet takových operátorů , čímž 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 nižší arity a zbytek vstupů ignorují. Z 256 výše citovaných ternárních booleovských operátorů jsou z nich takové degenerované formy binárních operátorů nebo operátorů nižší aritmetiky s využitím principu inkluze a exkluze. Jedním z takových operátorů je ternární operátor, který je vlastně unárním operátorem aplikovaným na jeden vstup a ignorujícím zbylé dva vstupy.
Operátor „Not“ je unární operátor, přijímá jediný člen (¬P). Ostatní jsou binární operátory, které berou dva termy a vytvářejí složený výrok (P Q, P Q, P → Q, P ↔ Q).
Množinu logických operátorů lze rozdělit na nesouvislé podmnožiny takto:
V tomto rozdělení je množina operátorových symbolů arity .
Ve známějších výrokových kalkulech se obvykle dělí takto:
Zde je tabulka, která ukazuje běžně používanou prioritu logických operátorů.
Pořadí přednosti určuje, který konektor je „hlavní konektor“ při interpretaci neatomické formule.
Princip kompozičnosti
Namísto 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 v principu kompozicionality významu.
Nechť I je interpretační funkce, nechť Φ, Ψ jsou libovolné dvě věty a nechť pravdivostní funkce fnand je definována jako:
Pak jsou pro usnadnění fnot, for fand atd. definovány pomocí fnand:
nebo alternativně fnot, neboť fand atd. jsou definovány přímo:
Je-li tedy S věta, která je řetězcem symbolů sestávajícím z logických symbolů v1…vn představujících logické spojky a nelogických symbolů c1…cn , pak tehdy a jen tehdy, když I(v1)…I(vn) byly poskytnuty interpretace v1 až vn pomocí fnand (nebo jiné množiny 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ávalo a požadovalo, S je pravdivý nebo nepravdivý pouze při interpretaci všech jeho nelogických symbolů.
Logické operátory jsou v číslicových obvodech implementovány jako logická hradla. Prakticky všechny číslicové obvody (hlavní výjimkou je paměť DRAM) jsou sestaveny z hradel NAND, NOR, NOT a přenosových hradel. Poměrně běžná jsou hradla NAND a NOR se třemi a více vstupy namísto obvyklých dvou vstupů, přestože jsou logicky ekvivalentní kaskádě dvouvstupových hradel. Všechny ostatní operátory jsou realizovány rozkladem na logicky ekvivalentní kombinaci 2 nebo více výše uvedených logických hradel.
„Logická ekvivalence“ „pouze NAND“, „pouze NOR“ a „NOT a AND“ je podobná Turingově ekvivalenci.
Je nějaká nová technologie (například reverzibilní výpočet, bezhodinová logika nebo výpočet kvantových bodů) „funkčně úplná“ v tom smyslu, že ji lze použít k vytvoření počítačů, které mohou provádět všechny druhy výpočtů, které mohou provádět počítače založené na CMOS? Pokud dokáže implementovat operátor NAND, teprve pak je funkčně úplný.
To, že všechny logické spojky lze vyjádřit pouze pomocí NOR, dokazuje naváděcí počítač Apollo.