Disjunkce

Disjunkce
NEBO
Vennův diagram
Definice	$x+y$
pravdivostní tabulka	$(0111)$
logická brána
normální formy
Disjunktivní	$x+y$
spojivkové	$x+y$
Zhegalkinův polynom	$x\oplus y\oplus 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

Disjunkce (z lat. disjunctio - „disjunkce“), logické sčítání , logické OR , včetně OR ; někdy je jen OR logická operace , ve své aplikaci co nejblíže spojení „nebo“ ve smyslu „buď to, nebo to, nebo obojí najednou“ [1] .

Disjunkce může být buď binární (má dva operandy) nebo -ary (má operandy) pro libovolný . $n$ $n$ $n$

Záznam může být prefix - znak operace je před operandy ( polská notace ), infix - znak operace je mezi operandy nebo postfix - znak operace je za operandy. Když je počet operandů větší než dva, jsou předponové a postfixové zápisy ekonomičtější.

Notace

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

a\lor b,\;a

|| |

b,\;a

b,\;a~{\mbox{OR}}\,\,b

,\;\max(a,b).

V moderní matematice a matematické logice je přitom nejrozšířenější zápis doporučený mezinárodní normou ISO 31-11 [2] . Neobjevilo se to okamžitě: George Boole , který položil základ pro systematickou aplikaci symbolické metody na logiku, nepracoval s disjunkcí (místo toho používal striktní disjunkci , kterou označil znakem + ), a William Jevons navrhl znak pro disjunkci . Ernst Schroeder a P. S. Poretsky opět použili znaménko + , ale ve vztahu k obvyklé disjunkci [3] . Symbol jako označení disjunkce se poprvé vyskytuje v článku „Matematická logika založená na teorii typů“ [4] od Bertranda Russella (1908); je odvozeno z lat. vel , což znamená "nebo" [5] [6] . $a\lor b$ ·|· $\lor$

Zápis ⋁pro disjunkci byl také používán v raném programovacím jazyce Algol 60 [7] . Vzhledem k absenci 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 jiné zápisy pro disjunkci. Ve Fortranu IV a PL/I se tedy používala označení .OR.a |(s možností nahrazení posledně jmenovaného klíčovým slovem OR ) [8] ; vyhrazené slovo [9] [10] se používá v Pascalu a Adě ; jazyky C a C++ používají zápis pro bitovou disjunkci a pro logickou disjunkci [11] ). or |||

Konečně, při přirozeném uspořádání pravdivostních hodnot dvouhodnotové logiky (když se předpokládá, že ), se ukazuje, že Disjunkce se tedy ukazuje jako speciální případ operace výpočtu maxima ; to otevírá nejpřirozenější způsob, jak definovat operaci disjunkce v systémech mnohohodnotové logiky [12] [13] . $0<1$ $(a\lor b)\,=\,\max(a,b).$

Booleovská algebra

Logická funkce MAX ve dvouhodnotové (binární) logice se nazývá disjunkce ( logické "OR" , logické sčítání nebo jednoduše "OR" ). Výsledek se rovná největšímu operandu.

V Booleově algebře je disjunkce funkcí dvou, tří nebo více proměnných (jsou také operandy operace, jsou také argumenty funkce). Výsledek je tedy , pokud jsou všechny operandy stejné ; ve všech ostatních případech je výsledkem . $0$ $0$ $jeden$

pravdivostní tabulka
$A$	$b$	$a\lor b$
$0$	$0$	$0$
$0$	$jeden$	$jeden$
$jeden$	$0$	$jeden$
$jeden$	$jeden$	$jeden$

Pravdivostní tabulka pro ternární (tři operandy) disjunkci:

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

Vícehodnotová logika

Operace, nazývaná v binární logice disjunkce , se ve vícehodnotové logice nazývá maximum : , kde , a je hodnota logiky. Jiné možnosti jsou možné $max(a,b)$ $a,b\in [0,...,n-1]$ $n$ [ co? ] . Zpravidla se snaží zachovat kompatibilitu s Booleovou algebrou pro hodnoty operandů . $0.1$

Název tohoto maxima operace má smysl v logikách s libovolnou hodnotou, včetně binární logiky, a názvy disjunkce , logické "OR" , logické sčítání a jednoduše "OR" jsou charakteristické 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 disjunkce 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 disjunkce. Jedna z nejběžnějších možností obsahuje 3 axiomy pro disjunkci:

$a\to a\nebo b$
$b\to a\nebo b$
$(a\to c)\to ((b\to c)\to ((a\nebo b)\to c))$

Tyto axiomy lze použít k prokázání dalších vzorců obsahujících operaci disjunkce. 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

Mnemotechnické pravidlo pro disjunkci s libovolným počtem vstupů je: Výstup bude:

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

Teorie množin

V podmínkách teorie množin je disjunkce analogická operaci sjednocení .

Programování

V počítačových jazycích existují dvě hlavní varianty disjunkce: logické "OR" a bitové "OR". Například v C/C++/Perl/PHP je logické "OR" označeno symbolem "||" a bitově "OR" symbolem "|". V jazycích Pascal/Delphi se oba druhy disjunkce označují pomocí klíčového slova " nebo " a výsledek operace 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é "OR" se používá v operátorech podmíněného skoku nebo v podobných případech, kdy je vyžadován výsledek nebo . Například: $false$ $skutečný$

pokud ( a || b ) { /* nějaké akce */ };

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

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 $skutečný$ $b$

{$B-}

nebo vypnutí

{$B+}

podobné chování. Pokud například levý operand zkontroluje, zda je třeba vyhodnotit pravý operand:

if ( a == NULL || a -> x == 0 ) { /* nějaké akce */ };

V tomto příkladu kvůli kontrole na levém operandu nikdy nedojde k dereference nulového ukazatele na pravém operandu.

Bitový OR 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 NEBO b =	${\displaystyle 01101101_{2))$

Vztah k přirozenému jazyku

Na podobnost mezi disjunkcí a spojkou „nebo“ v přirozeném jazyce se často poukazuje, když se používá ve smyslu „buď to, nebo ono, nebo obojí najednou“. V právních dokumentech často píší: "a (nebo)", někdy "a / nebo", což znamená "buď to, nebo to, nebo obojí najednou." Složený výrok "A a/nebo B" je považován za nepravdivý, když oba výroky A i B jsou nepravdivé, jinak je složený výrok pravdivý. To přesně odpovídá definici disjunkce v Booleově algebře, pokud "pravda" je označena a "nepravda" je označena . $jeden$ $0$

Nejednoznačnost přirozeného jazyka spočívá v tom, že spojení „nebo“ se používá ve dvou významech: buď k označení disjunkce, pak pro další operaci – striktní disjunkce ( výhradní „OR“ ).

Viz také

Poznámky

↑ Gutnikov V.S. Integrovaná elektronika v měřicích přístrojích. - L .: Energie , 1974. - 144 s. - S. 14-16.
↑ Kondakov, 1975 , s. 534.
↑ Stjažkin N. I. . Formování matematické logiky. — M .: Nauka , 1967. — 508 s. - S. 320, 349, 352, 368.
↑ Russell B. Matematická logika založená na teorii typů // American Journal of Mathematics . - 1908. - Sv. 30, č. 3. - S. 222-262.
↑ Nejstarší použití symbolů teorie množin a logiky . // Webové stránky Webové stránky Jeffa Millera . Získáno 5. února 2016. Archivováno z originálu 20. února 1999. (neurčitý)
↑ Kondakov, 1975 , s. 149-150.
↑ 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.

Literatura

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

Slovníky a encyklopedie	Velká dánština
V bibliografických katalozích	GND : 4378735-6 J9U : 987007532489205171 LCCN : sh93005045

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ů