Spojení

Spojení
A
Vennův diagram
Definice	$xy$
pravdivostní tabulka	$(0001)$
logická brána
normální formy
Disjunktivní	$xy$
spojivkové	$xy$
Zhegalkinův polynom	$xy$
Členství v předkompletních třídách
Ušetří 0	Ano
Ušetří 1	Ano
Monotónní	Ano
lineární	Ne
Self-duální	Ne

Konjunkce (z latinského conjunctio - „spojení, spojení“) je logická operace ve významu co nejblíže spojení „a“. Synonyma: logické "AND" , logické násobení , někdy jen "AND" [1] .

Konjunkce může být binární operace (tj. mít dva operandy), ternární operace (tj. mít tři operandy) nebo n-ární operace (tj. mít n operandů).

Notace

Nejběžnější zápis operace spojky je:

$a\land b,\quad a\And \And b,\quad a\And b,\quad a\cdot b,\quad a\,\,\mathrm {AND} \,\,b,\ quad\min(a,b)$

(v případě použití tečky jako znaku logického násobení lze toto znaménko, stejně jako při běžném násobení v algebře , vynechat: [1] ). $ab$

Zápis doporučený normou ISO 31-11 je přitom nejpoužívanější v moderní matematice a matematické logice , kde však konkuruje znaku ampersand & [1] ; posledně jmenovaný, objevující se v 1. století př. Kr. E. jako grafickou zkratku ( ligatura ) latinského union et 'and', již v roce 1685 používali Jacob a Johann Bernoulli jako logické spojení (spojoval v nich však nikoli výroky , ale pojmy ) [2] [3] . George Boole (následovaný dalšími průkopníky systematické aplikace symbolické metody na logiku: W. S. Jevons , E. Schroeder , P. S. Poretsky ) označoval konjunkci se znaménkem - jako obyčejné násobení [4] . Symbol ⋀ (převrácený disjunkční znak ) jako symbol pro konjunkci navrhl Arend Heyting (1930) [5] . $a\země b$ $\cdot$

Zápis ⋀pro konjunkci byl také používán v raném programovacím jazyce Algol 60 [6] . Kvůli nedostatku odpovídajícího znaku ve standardních znakových sadách (například v ASCII nebo EBCDIC ) používaných na většině počítačů však nejrozšířenější programovací jazyky poskytovaly pro spojení jiné zápisy. Ve Fortranu IV a PL/I se tedy používalo označení .AND.a &(s možností nahrazení posledně jmenovaného klíčovým slovem AND ) [7] ; Pascal a Ada používají vyhrazené slovo and[8] [9] ; jazyky C a C++ používají zápis &pro bitovou konjunkci a &&pro logickou konjunkci [10] ).

Konečně, při přirozeném uspořádání pravdivostních hodnot dvouhodnotové logiky (když se předpokládá, že ), se ukazuje, že konjunkce se tedy ukazuje jako speciální případ operace výpočtu minima ; otevírá se tím nejpřirozenější způsob, jak definovat fungování konjunkce v systémech mnohohodnotové logiky (ačkoli se někdy uvažují i jiné způsoby zobecňující konjunkce - např. v případě k -hodnotové logiky, ve které množina pravdivostních hodnot je reprezentován počátečním segmentem pologrupy přirozených čísel ) [11] [12] . $0<1$ $(a\land b)\,=\,\min(a,b).$ $(a\land b)\,=\,ab\;(\operatorname {mod} k)$ $\{0,\tečky ,k-1\}$ $\mathbb {N}$

Booleovská algebra

Definice.
Logická funkce MIN ve dvouhodnotové (binární) logice se nazývá konjunkce ( logické "AND" , logické násobení nebo jednoduše "AND" ).

Pravidlo: Výsledek se rovná nejmenšímu operandu.

Popis.
V Booleově algebře je spojka funkcí dvou, tří nebo více proměnných (jsou také operandy operace, jsou také argumenty funkce). Proměnné mohou nabývat hodnot z množiny . Výsledek také patří do sestavy . Výsledek se vypočítá podle jednoduchého pravidla nebo podle pravdivostní tabulky . Místo hodnot lze použít libovolnou jinou dvojici vhodných znaků, např. nebo nebo „nepravda“, „pravda“, ale u takového označení je nutné dodatečně definovat senioritu, např. , s digitálním označením, seniorita je přirozené . Pravidlo: výsledek je , pokud jsou všechny operandy stejné ; ve všech ostatních případech je výsledkem . $\{0,1\}$ $\{0,1\}$ $0.1$ $false,true$ $F,T$ $pravda > nepravda$ $1 > 0$
$jeden$ $jeden$ $0$

Pravdivostní tabulky:
pro binární konjunkci

$A$	$b$	$a\země b$
$0$	$0$	$0$
$jeden$	$0$	$0$
$0$	$jeden$	$0$
$jeden$	$jeden$	$jeden$

pro ternární konjunkci

$A$	$b$	$C$	$a\land b\land c$
0	0	0	0
jeden	0	0	0
0	jeden	0	0
jeden	jeden	0	0
0	0	jeden	0
jeden	0	jeden	0
0	jeden	jeden	0
jeden	jeden	jeden	jeden

Konjunkce je komutativní , asociativní a distributivní vzhledem ke slabé disjunkci [13] .

Vícehodnotová logika

Operace, nazývaná konjunkce v binární logice , v multi-cenil logiky je obvykle spojena s minimální operací : , kde a je hodnota logiky; jsou však možné i jiné možnosti zobecnění obvyklé konjunkce na případ množiny. Zpravidla se snažíme zachovat kompatibilitu s Booleovou algebrou pro hodnoty operandů a . $min(a,b)$ $a,b\in \{0,\tečky ,k-1\},$ $k$ $0$ $k-1$

Název tohoto minima operace má smysl v logikách s libovolnou hodnotou, včetně binární logiky, a názvy konjunkce , logické "AND" , logické násobení a jednoduše "AND" jsou typické pro binární logiku a při přechodu na vícehodnotová logika.

Klasická logika

V klasickém výrokovém počtu jsou vlastnosti konjunkce definovány pomocí axiomů . Klasický výrokový počet může být dán různými systémy axiomů a některé z nich budou popisovat vlastnosti konjunkce. Jedna z nejběžnějších možností obsahuje 3 axiomy pro spojení:
$a\land b\to a$
$a\land b\to b$
$a\to (b\to (a\land b))$

Pomocí těchto axiomů lze dokázat další formule obsahující operaci konjunkce. Vezměte prosím na vědomí, že v klasickém výrokovém počtu se výsledek nepočítá z hodnot operandů (jako v Booleově algebře), ale je nutné dokázat vzorec jako celek na základě axiomů a inferenčních pravidel.

Obvod

Logický prvek, který implementuje funkci konjunkce, se nazývá match obvod [13] . Mnemotechnické pravidlo pro spojení s libovolným počtem vstupů je: Výstup bude:

"1" tehdy a jen tehdy, když všechny vstupy mají "1",
"0" tehdy a jen tehdy, když alespoň jeden vstup má "0"

Teorie množin

V podmínkách teorie množin je konjunkce obdobou operace průniku .

Programování

V počítačových jazycích se používají dvě hlavní verze spojky: logické "AND" a bitové (bitové) "AND". Například v jazycích C/C++ je logické AND označeno symbolem "&&" a bitové je označeno symbolem "&". V terminologii používané v C# se operace „&“ nazývá logický „AND“ a operace „&&“ se nazývá podmíněná „AND“ , protože hodnoty operandů jsou podmínkou pro pokračování výpočtu. V jazycích Pascal/Delphi se oba druhy spojení označují pomocí klíčového slova " a " a výsledek akce je určen typem operandů. Pokud jsou operandy typu boolean (například Boolean), provede se logická operace, pokud je celé číslo (například Byte) bitovou operací.

Logické "AND" se používá v příkazech podmíněného skoku nebo v podobných případech, kdy je vyžadován výsledek nebo . Například: $false$ $skutečný$

if ( a & b & c ) { /* nějaké akce */ };

Porovnání v tomto případě bude pokračovat až do konce výrazu, bez ohledu na mezivýsledky. Princip podmíněného "AND" v podobné situaci:

a = nepravda _ b = pravda ; c = pravda ; if ( a && b && c ) { /* nějaké akce */ };

Ověřování pravdivosti výrazu se v tomto případě zastaví po kontrole proměnné a, protože další porovnávání nedává smysl.

Výsledek bude stejný , pokud jsou oba operandy stejné (není stejné pro číselné typy ). V každém jiném případě bude výsledek . $skutečný$ $skutečný$ $0$ $false$

V tomto případě se použije standardní konvence: pokud je hodnota levého operandu rovna , pak se hodnota pravého operandu nevypočítá (místo toho může existovat složitý vzorec). Tato konvence urychluje provádění programu a v některých případech je užitečnou technikou. Kompilátor Delphi podporuje speciální direktivu, která obsahuje $false$ $b$

{$B-}

nebo vypnutí

{$B+}

podobné chování. Pokud například levý operand testuje, zda lze vyhodnotit pravý operand:

if ( a != 0 && b / a > 3 ) { /* nějaké akce */ };

V tomto příkladu se kvůli kontrole na levém operandu pravý operand nikdy nebude dělit nulou.

Bitové "AND" provádí obvyklou operaci booleovské algebry na všech bitech levého a pravého operandu v párech. Například,

-li
a =	${\displaystyle 01100101_{2))$
b=	${\displaystyle 00101001_{2))$
pak
a a b =	$00100001_{2}$

Vztah k přirozenému jazyku

Často se poukazuje na podobnost mezi spojkou a spojkou „a“ v přirozeném jazyce. Složený výrok " A a B " je považován za pravdivý, pokud jsou pravdivé oba výroky A i B , jinak je složený výrok nepravdivý. To přesně odpovídá definici konjunkce v Booleově algebře, pokud "pravda" je označena a "nepravda" je označena . Současně se často používá standardní klauzule o nejednoznačnosti přirozeného jazyka . Například v závislosti na kontextu může spojení „a“ nést další konotaci „a pak“, „a proto“, „a pak“. Rozdíl mezi logikou přirozeného jazyka a matematickou logikou vtipně vyjádřil americký matematik Stephen Kleene , když poznamenal, že v přirozeném jazyce „Mary se vdala a měla dítě“ není totéž jako „Mary porodila dítě a vdala se“. $jeden$ $0$

Viz také

Poznámky

↑ 1 2 3 Kondakov, 1975 , s. 264-266, 534-536.
↑ Ampersand . // Webový online etymologický slovník . Získáno 7. února 2016. Archivováno z originálu 18. února 2011. (neurčitý)
↑ Kondakov, 1975 , s. 67.
↑ Stjažkin N. I. . Formování matematické logiky. — M .: Nauka , 1967. — 508 s. - S. 321, 348, 352, 368.
↑ Nejstarší použití symbolů teorie množin a logiky . // Webové stránky Webové stránky Jeffa Millera . Datum přístupu: 7. února 2016. Archivováno z originálu 21. srpna 2011. (neurčitý)
↑ Kondakov, 1975 , s. třicet.
↑ Pratt T. Programovací jazyky: vývoj a implementace. — M .: Mir , 1979. — 574 s. - S. 352, 439.
↑ Grogono P. . Programování v Pascalu. — M .: Mir , 1982. — 384 s. - S. 51.
↑ Wegner P. . Programování v jazyce Ada. — M .: Mir , 1983. — 240 s. - S. 68.
↑ Ellis M. , Stroustrup B. . Referenční příručka k programovacímu jazyku C++ s komentáři. — M .: Mir , 1992. — 445 s. — ISBN 5-03-002868-4 . - S. 65, 86-87.
↑ Yablonsky S. V. . Úvod do diskrétní matematiky. — M .: Nauka , 1979. — 272 s. - S. 9-10, 37.
↑ Rvachev V. L. . Teorie R -funkcí a některé její aplikace. - Kyjev: Naukova Dumka , 1982. - 552 s. - S. 38, 66.
↑ 1 2 Slovník kybernetiky. 2. vydání / Ed. V. S. Michalevič. - Kyjev: Ukrajinská sovětská encyklopedie , 1989. - 751 s. - ISBN 5-88500-008-5 .

Literatura

Kondakov N.I. Logický slovník-příručka. 2. vyd . — M .: Nauka , 1975. — 720 s.

V bibliografických katalozích	GND : 4164990-4

Booleovské operace
Disjunkce (OR) Konjunkce (AND) Odmítnutí (NE) Exkluzivní "nebo" (XOR) Pierce Arrow (NOR) Schaefferův zdvih (NAND) Ekvivalence (XNOR) implikace Podmíněná disjunkce (ternární)

Logika

Filosofie • Sémantika • Syntaxe • Historie

Logické skupiny

klasická logika	Aristotelská logika výroková logika Logika prvního řádu Logika druhého řádu logika vyššího řádu
matematická logika	teorie množin Teorie modelu Teorie vyčíslitelnosti Důkazová teorie a konstruktivní matematika Lineární logika formální systém přirozený závěr Sekvenční počet Algebra logiky Relevantní logika Deontická logika intuicionistická logika Lambekův počet
Neklasická logika	intuicionismus fuzzy logika Substrukturální logika logika Popisná logika Vícehodnotová logika Logická syntéza Závazná logika Časová logika Modální logika ( Hybrid logic ) epistemická logika
Filosofická logika	Kritické myšlení neformální logika deduktivní uvažování

Komponenty

Seznam booleovských symbolů