Boolean algebra nebo výpočet Boolean, je ta část matematiky , která se zabývá přístupem algebraické do logického pohledu, pokud jde o proměnné , z operátorů a funkcí na logických proměnných, což umožňuje použít algebraické techniky pro nakládání s dvěma hodnotami projevů kalkulu propozice . Začalo to v roce 1854 britský matematik George Boole . Dnes Boolean algebra najde mnoho aplikací v informatice a v provedení z elektronických obvodů .
Poprvé byl použit pro telefon spínacích obvodů podle Claude Shannon .
Booleova algebra logických funkcí umožňuje modelovat logické uvažování vyjádřením „stavu“ jako funkce podmínek. Například pokud studujeme výraz Komunikace a výraz Vyzvednout;
Komunikace = vysílač a přijímač
Komunikace by byla „PRAVDA“, pokud by byly aktivní obě proměnné Sender AND Receiver (jedná se o logickou funkci v závislosti na proměnných Sender a Receiver )Vyzvednout = (vyzvánění A rozhodnutí odpovědět) NEBO rozhodnutí zavolat
Vyzvednout by bylo „TRUE“ buď, pokud jste slyšet zvonění současně a vy rozhodnete odpovědět , nebo ( OR ), pokud si prostě rozhodnou výzvu .Booleova algebra, která je doménou společnou pro tři disciplíny, se setkáváme s různými notacemi, abychom označili stejný objekt. Ve zbytku článku uvedeme různé notace, ale budeme mít privilegium pro zachování určité homogenity.
Říkáme B set skládá ze dvou prvků nazývaných pravdivostní hodnoty {true, false}. Tato sada je také uvedena
s pro a pro .
Zápis bude v následujícím upřednostňován .
Na této sadě můžeme definovat dva binární zákony (nebo operace), zákony AND a OR a unární operaci, negaci (nebo doplněk).
U všech následujících příkladů a vlastností
Tabulka zákonů ET | ||
b \ a | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
Je definován následovně: a AND b je PRAVDA právě tehdy, když a je PRAVDA a b je PRAVDA.
Tento zákon je také známý:
V následujícím textu bude upřednostňován zápis „ “.
Tabulka tohoto zákona (analogická s tabulkou sčítání nebo násobení ) není pravdivostní tabulkou .
Tabulka zákona NEBO | ||
b \ a | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 1 |
Je definován následovně: a OR b je PRAVDA právě tehdy, když a je PRAVDA nebo b je PRAVDA. (Zejména, pokud a je pravda a b je také pravda, pak je OR b pravda.)
Tento zákon je také známý:
Přednostně budou v následujícím zápisu , ale péče bude brát v úvahu skutečnost, že tento zákon není obvyklý přídavek do Z / 2 Z . To je důvod, proč se v matematice a matematické logice notace nepoužívá k označení „nebo včetně“: je vyhrazena pro „ nebo výlučné “, což je operace, která (spojená s „a“) vytvoří jakoukoli algebru booleovské Booleovská kroužek , zejména Z / 2 Z - algebry .
Negace a je TRUE právě tehdy, když a je FALSE.
Negace a je zaznamenána:
Zápis bude v následujícím upřednostňován .
Pak dostaneme a .
Na operátory má vliv několik společných vlastností:
Kromě toho má každý operátor neutrální prvek a absorpční prvek :
Jsou možná zjednodušení, například:
věta o shodě platí pro operátory booleovské algebry:
Nakonec se řídí zásadou komplementarity:
Pak zjistíme všechny vlastnosti, které dávají B je struktura booleovské algebry .
PřednostPro zjednodušení zápisů je obvyklé, aby booleovské operace podléhaly stejným pravidlům priority jako obvyklé aritmetické operace: funkce AND (logické násobení) má tedy přednost před funkcí OR (logický součet). Tak :
Stále je možné umístit do výpočtů závorky, které mění pořadí priorit operací.
De Morganova věta
De Morganův první zákon (disjunkční negace)
je vyjádřena následující rovností
V obou případech bude výraz TRUE pouze v |
De Morganův druhý zákon (negace konjunkce)
V obou případech je výraz bude FALSE, pouze |
Matematicky, je logická funkce , nebo logický operátor je aplikace, B n v B .
V elektronice je logická funkce černá skříňka, která přijímá určitý počet logických proměnných jako vstup a která vydává logickou proměnnou v závislosti na vstupních proměnných. Logická funkce článku vysvětluje, jak postavit černé skříňky některých základních funkcí.
Pravdivostní tabulka umožňuje určit stav výstupu podle stavy vstupů. Charakterizuje logickou funkci.
Libovolnou tabulku pravdivosti, a tedy jakoukoli logickou funkci, lze popsat pomocí tří základních operací:
Také dokazujeme, že existují přesně logické funkce parametrů. Postačí ve skutečnosti zvážit všechny možné pravdivostní tabulky nebo zvážit vývoj funkce parametrů.
Pocházejí ze tří základních operací a poté jsou definovány
|
|
|
|
Jedná se o logické funkce se dvěma proměnnými. Mezi nimi jsou některé dostatečně zajímavé, aby se dalo pojmenovat.
Exkluzivní disjunkceTabulka pravd XOR | ||
na | b | a b |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Dosud studované OR je třeba chápat takto: „jeden nebo druhý nebo oba“. Nazývá se také „včetně OR“. Výhradní OR (nebo XOR pro 'e X clusive OR' ) se chápe jako: „jedno nebo druhé, ale ne obojí“.
a XOR bMůžeme to také definovat pomocí modulo na běžném součtu :
„Výhradní nebo“ je někdy označeno aritmetickým znaménkem ( odlišným od ). Funkčně, ale také používá + obklopený: .
Vlastnost - Libovolnou tabulku pravdivosti, libovolnou logickou funkci, lze popsat pomocí konstanty 1 a dvou operací: výlučná disjunkce a konjunkce, protože:, a
RovnocennostPravdivostní tabulka EQV | ||
na | b | a b |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Ekvivalence (označený EQV nebo XNOR) platí v případě, že oba vstupy mají stejnou hodnotu a falešných jinak. Je to negace „exkluzivního nebo“.
Ekvivalence může být psánRovnocennost je často označena znakem . Lze jej také poznamenat „==“ v určitých jazycích (C, C ++, PHP…) a „⊙“ v elektronice.
ÚčastTabulka pravdivosti IMP | ||
na | b | a b |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Tato operace není komutativní . a je dostatečná podmínka pro b, což je nutná podmínka pro a.
Ale
Výkres :
Z prohlášení „KDYŽ žiji v (metropolitní) Francii, POTOM žiji v Evropě. » , Můžeme odvodit « KDYŽ nežiji v Evropě, POTOM nežiji ve Francii. » Ale ne « POKUD nežiji ve Francii, POTOM nežiji v Evropě. » Protože mohu žít v Evropě jinde než ve Francii, aniž bych to odporoval původnímu prohlášení.
InhibiceTabulka pravdy INH | ||
na | b | |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
Pokud TRUE, je výraz TRUE, s výjimkou případů, b je TRUE.
Tato operace není komutativní.
Tabulka pravdivosti se zruší | ||||||||||||||||||||||||||||||||||||||||||
na | b | vs. | d | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 0 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 1 | 1 |
Zákonnost Vyzvednout = (vyzvánění A rozhodnutí odpovědět) NEBO rozhodnutí zavolat překládá následující praktickou situaci: Zvedneme telefon, když se rozhodneme někomu zavolat nebo když zazvoní telefon a my se rozhodneme odpovědět .
Skládá se ze tří proměnných:
proměnná d = "Vyzvednout" je logickou funkcí 3 předchozích a lze ji zapsat d = ab + c
Pravdivostní tabulka této funkce d je pak následující (vpravo):
Pravdivá tabulka stání2 | ||||||||||||||||||||||||||||||||||||||||||
na | b | vs. | d2 | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 1 | 0 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 0 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 1 | 1 |
Tabulka naznačuje absurdní situaci: když se rozhodnete někomu zavolat a telefon zazvoní, aniž byste chtěli odpovědět, zvedli byste se. Modifikace tabulky jako opačná by tuto absurditu napravila. Tato tabulka odpovídá logické funkci Pick up d2 nebo d2, kterou lze určit a zjednodušit .
Logická funkce se čtyřmi proměnnýmiDobrý student si klade otázku, jestli je moudré jít jednu noc ven. Musí se rozhodnout podle čtyř proměnných:
Tento student bude moci odejít, pokud:
Logický výraz, který se má ukončit podle stavu proměnných a, b, c a d, lze tedy zapsat takto:Konec =
Lze určit logickou funkci
Příklad: V příkladu „Pick up2“ ukazuje čtení tabulky, že se rovná kdy nebo nebo nebo .To umožňuje definovat d2 pomocí
Je možné najít výraz minimalizující počet výrazů a počet písmen v každém výrazu. To je cílem některých technických, jako je metoda Quine-McCluskey , Karnaughovy diagramy , konsensuální metoda , duální polarizace ...
Příklad (pokračování): předchozí součet lze snížit faktorizací prvních dvou členů o a faktorizaci posledních dvou členů o
Logické výrazy jsou v informatice často zastoupeny jako stromová struktura .
K prvnímu vrcholu (kořenu) jsou připojeny různé dílčí stromy (nebo větve). Slepé vrcholy se nazývají listy.
Každý vnitřní vrcholů odpovídá „pokud je pak jinak “ booleovské voliče , který snižuje dotaz na dva jednodušší podotázkami, případně snížena na 1 / pravda, nebo 0 / nepravda.
Vyhodnocení funkce fv závislosti na proměnné q vybrané pro první otázku je potom , což vede ke dvěma nezávislým výrazům .
Buď ; můžeme psát
Stromy v závislosti na výrazu a pořadí otázek, pro stejný výraz budou některé dotazníky jednodušší než jiné.