Booleovská logika je ucelený systém pro logické operace, používaný v mnoha systémech. Byl pojmenován po Georgi Booleovi, který jako první definoval algebraický systém logiky v polovině 19. století. Booleovská logika má mnoho aplikací v elektronice, počítačovém hardwaru a softwaru a je základem veškeré moderní digitální elektroniky. V roce 1938 ukázal Claude Shannon, jak elektrické obvody s relé byly vzorem pro Booleovskou logiku. Tato skutečnost se záhy ukázala jako nesmírně důležitá se vznikem elektronického počítače.
Pomocí algebry množin obsahuje tento článek základní úvod do množin, booleovských operací, Vennových diagramů, pravdivostních tabulek a booleovských aplikací. Článek o booleovské algebře pojednává o typu algebraické struktury, která splňuje axiomy booleovské logiky. Binární aritmetický článek pojednává o použití binárních čísel v počítačových systémech.
Nastavit logiku vs Booleovská logika
Sady mohou obsahovat libovolné elementy. Nejprve začneme diskusí o obecné množinové logice, pak se omezíme na logickou logiku, kde elementy (nebo „bity“) každý obsahuje pouze dvě možné hodnoty, nazývané různými názvy, jako „true“ a „false“, „yes“ a „no“, „on“ a „off“ nebo „1“ a „0“.
Vennův diagram znázorňující průnik množin „A AND B“ (ve fialovém/tmavém stínování), spojení množin „A OR B“ (všechny barevné oblasti) a exkluzivní případ OR „množina A XOR B“ (všechny barevné oblasti kromě fialové). „Vesmír“ je reprezentován celou plochou v obdélníkovém rámci.
Představte si, že množina A obsahuje všechna sudá čísla (násobky dvou) ve „vesmíru“ (definovaném v příkladu níže jako všechna celá čísla mezi 0 a 30 včetně) a množina B obsahuje všechny násobky tří ve „vesmíru“. Pak by průnik obou množin (všech prvků v množinách A a B) byly všechny násobky šesti ve „vesmíru“. Komplement množiny A (všech prvků NENÍ v množině A) by byla všechna lichá čísla ve „vesmíru“.
Řetězové operace společně
Zatímco v libovolné booleovské operaci jsou spojeny nanejvýš dvě množiny, nová množina vytvořená touto operací pak může být spojena s dalšími množinami využívajícími další booleovské operace. Pomocí předchozího příkladu můžeme definovat novou množinu C jako množinu všech násobků pěti ve „vesmíru“. Tedy „množiny A A A B A C“ by byly všechny násobky 30 ve „vesmíru“. Pokud je to výhodnější, můžeme považovat množinu AB za průnik množin A a B, nebo množinu všech násobků šesti ve „vesmíru“. Pak můžeme říci, že „množiny AB A C“ jsou množinou všech násobků 30 ve „vesmíru“. Pak bychom to mohli vzít ještě o krok dál a nazvat tento výsledek množinou ABC.
Zatímco libovolný počet logických AND (nebo libovolný počet logických ORS) může být zřetězen bez nejednoznačnosti, kombinace AND a ORS a NOT může vést k nejednoznačným případům. V takových případech mohou být použity závorky k objasnění pořadí operací. Jako vždy se nejprve provádějí operace v rámci nejvnitřnější dvojice, poté následuje další dvojice ven atd., dokud nejsou dokončeny všechny operace v rámci závorek. Poté se provádějí všechny operace mimo závorky.
Aplikace na binární hodnoty
V tomto příkladu jsme použili přirozená čísla, zatímco v booleovské logice jsou použita binární čísla. Vesmír by například mohl obsahovat jen dva prvky, „0“ a „1“ (nebo „true“ a „false“, „yes“ a „no“, „on“ nebo „off“ atd.). Mohli bychom také kombinovat binární hodnoty dohromady, abychom získali binární slova, jako v případě dvou číslic, „00“, „01“, „10“ a „11“. Při použití množinové logiky na tyto hodnoty bychom mohli mít množinu všech hodnot, kde první číslice je „0“ („00“ a „01“) a množinu všech hodnot, kde první a druhá číslice jsou odlišné („01“ a „10“). Průnik obou množin by pak byl jediný prvek, „01“. To by mohl ukázat následující booleovský výraz, kde „1st“ je první číslice a „2nd“ je druhá číslice:
(NE1. místo) AND (1. místo XOR 2.)
Symboly pro dvě primární binární operace definujeme jako (logický průnik AND/set) a (logický OR/set union) a pro jednu unární operaci / ~ (logický NOT/set complement). Použijeme také hodnoty 0 (logický FALSE/prázdná množina) a 1 (logická TRUE/the universe). Následující vlastnosti platí jak pro logickou logiku, tak pro logiku množin (i když zde je zobrazena pouze notace pro logickou logiku):
První tři vlastnosti definují mřížku; prvních pět definuje booleovskou algebru.
Zbývajících pět je důsledkem prvních pěti.
Matematici a inženýři často používají plus (+) pro OR a znaménko výrobku () pro AND. OR a AND jsou do jisté míry analogické sčítání a násobení v jiných algebraických strukturách a tato notace velmi usnadňuje získání součtu součinů pro normální algebru. NESMÍ být reprezentováno čarou nakreslenou nad výrazem, který je negován (). Běžně to také vede k tomu, že je dána vyšší přednost než +, což v některých případech odstraňuje potřebu závorek.
Jiná notace používá „meet“ pro AND a „join“ pro OR. To však může vést k záměně, protože termín „join“ se také běžně používá pro jakoukoliv logickou operaci, která kombinuje množiny dohromady, což zahrnuje jak AND, tak OR.
Základní matematika použití booleovských pojmů
Anglický jazyk používání booleovských termínů
Je třeba dávat pozor při převádění anglické věty do formálního booleovského prohlášení. Mnoho anglických vět má nepřesný význam. Např. „Všechno, co se
třpytí, není zlato,“ by mohlo znamenat, že nic, co se třpytí, není zlato, nebo že některé věci, které se třpytí, nejsou zlato.
V některých případech lze AND a OR zaměnit v angličtině:
Někdy mají anglická slova „and“ a „or“ význam, který je zjevně opačný než jeho význam v boolské logice:
V závislosti na kontextu může slovo „nebo“ odpovídat buď logickému OR nebo logickému XOR:
Logické XOR lze přeložit jako „jedno, nebo druhé, ale ne obojí“. Ve většině případů je tento koncept nejefektivněji sdělen v angličtině pomocí „either/or“.
Slovo kombinace „a/nebo“ se někdy používá v angličtině k upřesnění logického OR, když pouhé použití slova „nebo“ by mohlo být mylně považováno za logické XOR:
To může být významná výzva při poskytování přesných specifikací počítačového programu nebo elektronického obvodu v angličtině. Popis takové funkce může být nejednoznačný. Vezměme si například výrok „Program by měl ověřit, zda žadatel zaškrtl mužskou nebo ženskou kolonku“. To by mělo být interpretováno jako XOR a ověření by mělo zajistit, aby byla vybrána jedna a pouze jedna kolonka. V jiných případech může být správný výklad angličtiny méně zřejmý; při určení původního záměru by měl být konzultován autor specifikace.
Konstrukce digitálních elektronických obvodů
Booleovská logika se také používá pro návrh obvodů v elektrotechnice; zde 0 a 1 mohou reprezentovat dva různé stavy jednoho bitu v digitálním obvodu, typicky vysoké a nízké napětí. Obvody jsou popsány výrazy obsahujícími proměnné a dva takové výrazy jsou shodné pro všechny hodnoty proměnných tehdy a jen tehdy, když mají odpovídající obvody stejné chování vstupu a výstupu. Navíc každé možné chování vstupu a výstupu může být modelováno vhodným Booleovským výrazem.
Brány se základní logikou, jako jsou brány AND, OR a NOT, mohou být použity samostatně nebo ve spojení s branami NAND, NOR a XOR k ovládání digitální elektroniky a obvodů. Zda jsou tyto brány zapojeny sériově nebo paralelně, řídí prioritu operací.
Relační databáze používají SQL nebo jiné databázově specifické jazyky k provádění dotazů, které mohou obsahovat Booleovskou logiku. Pro tuto aplikaci může být každý záznam v tabulce považován za „prvek“ z „množiny“. Například v SQL se tyto příkazy SELECT používají k načtení dat z tabulek v databázi:
Závorky mohou být použity k explicitnímu určení pořadí, ve kterém dochází k booleovským operacím, když je přítomno více operací:
V případě potřeby lze také použít více sad vnořených závorek.
Jakákoli booleovská operace (nebo operace), která kombinuje dvě (nebo více) tabulek dohromady, je v relační databázové terminologii označována jako join.
V oblasti elektronických lékařských záznamů používají některé softwarové aplikace Booleovskou logiku pro vyhledávání v databázích svých pacientů, a to v technologii, která byla pojmenována Concept Processing.
Dotazy vyhledávačů také používají logickou logiku Boolean. Pro tuto aplikaci lze každou webovou stránku na internetu považovat za „prvek“ nějaké „množiny“. Následující příklady používají syntaxi podporovanou společností Google.