Booleovská algebra. Algebra logiky. Prvky matematické logiky

V moderním světě stále více používáme různé stroje a pomůcky. A ne pouze tehdy, pokud je nezbytné aplikovat doslova nadlidskou sílu: přesunout zátěž jej zvednout do výšky, vykopat dlouhý a hluboký příkop, atd. Auta dnes sbírat roboty, jídlo se vaří Multivarki a základní výpočty aritmetické vyrábět kalkulačky ... Častěji slyšíme výraz "booleovská algebra". Možná nadešel čas k pochopení role lidských bytostí při vytváření robotů a strojů schopnost řešit nejen matematický ale logické úkoly.

Logika

Řečeno z řečtiny, logika je řádný systém myšlení, který vytváří vztahy mezi danými podmínkami a umožňuje vyvozovat závěry na základě předpokladů a předpokladů. Často se navzájem ptali: "Je to logické?" Odpověď odpovídá našim předpokladům nebo kritizuje průběh myšlení. Tento proces však nezastaví: pokračujeme v tom, abychom rozuměli.

Někdy je počet podmínek (úvodní) tak velký, a vzájemné vztahy mezi nimi jsou tak zmatené a složité, že lidský mozek není schopen "strávit" všechno najednou. Může to trvat déle než měsíc (týden, rok), abyste pochopili, co se děje. Ale moderní život nám nedává takové časové intervaly pro rozhodování. A uchýlíme se k pomoci počítačů. A právě tam se objeví algebra logiky se svými zákony a vlastnostmi. Po stažení všech původních dat umožňujeme počítači rozpoznat všechny vztahy, odstranit rozpory a najít uspokojivé řešení.

Matematika a logika

Nejslavnější Gottfried Wilhelm Leibniz formuloval pojem "matematická logika", jehož úkoly byly přístupné pouze úzkému okruhu vědců. Zvláštní zájem v tomto směru nezpůsobil a až do poloviny 19. století vědělo několik lidí o matematické logice.

Velký zájem o vědecké komunity vyvolal spor, ve kterém Angličan George Buhl oznámil svůj úmysl vytvořit sekci matematiky, která by neměla žádnou praktickou aplikaci. Jak si pamatujeme z historie, v té době se aktivně rozvíjela průmyslová výroba, vyvinuly se všechny druhy pomocných strojů a strojů, to znamená, že všechny vědecké objevy měly praktickou orientaci.

Při pohledu do budoucna říkáme, že booleovská algebra je nejvíce používaná část matematiky v moderním světě. Spor tedy ztratil svůj Boule.

George Boule

Samotná osobnost autora si zaslouží zvláštní pozornost. Dokonce i vzhledem k tomu, že v minulosti lidé vyrostl před námi, stále je třeba poznamenat, že v 16 letech John. Buhl učil na vesnické škole a až 20 let otevřel vlastní školu v Lincoln. Matematik dokonale zvládl pět cizích jazyků a ve volném čase přečetl díla Newtona a Lagrange. A to vše je o synovi jednoduchého dělníka!

V roce 1839 Boule nejprve poslal své vědecké práce do Cambridge Mathematical Journal. Vědec byl 24 let. Booleova práce byla pro členy Královské vědecké společnosti tak zajímavá, že v roce 1844 získal medaili za svůj příspěvek k rozvoji matematická analýza. Několik dalších publikovaných děl, ve kterých byly popsány prvky matematické logiky, dovolil mladému matematikovi, aby se stal profesorem na Cork County College. Připomeňme, že on sám nebyl vzdělaný.

Nápad

Booleovská algebra je v zásadě velmi jednoduchá. Tam jsou výkazy (logické výrazy), které lze z matematického hlediska definovat pouze dvěma slovy: "pravda" nebo "lhát". Například na jaře stromy kvetou - pravda, v létě to sněží - leží. Veškeré kouzlo této matematiky spočívá v tom, že neexistuje žádná přísná nutnost používat pouze čísla. Jakákoli tvrzení s jednoznačným významem jsou dokonale vhodná pro algebra návrhů.

Logická algebra lze tedy použít doslova všude: v pokynech pro plánování a psaní, analýze konfliktních informací o událostech a určení pořadí akcí. Nejdůležitější je pochopit, že nezáleží na tom, jak jsme určili pravdu nebo falešnost prohlášení. Z těchto "jak" a "proč" by mělo být abstrahováno. Jediné, na čem záleží, je prohlášení o skutečnosti: pravda - nepravda.

Funkce algebry logiky jsou samozřejmě důležité pro programování, které jsou psány s příslušnými znaky a symboly. A naučit je znamená zvládnout nový cizí jazyk. Nic není nemožné.

Základní pojmy a definice

Aniž bychom se dostali do hlubin, pochopíme terminologii. Booleovská algebra tedy předpokládá přítomnost:

• prohlášení;
• logické operace;
• funkcí a zákonů.

Výrazy jsou jakékoliv kladné výrazy, které nelze interpretovat dvojitou hodnotou. Jsou psány ve formě čísel (5> 3) nebo formulovány s obvyklými slovy (slon je největším savcem). V tomto případě má výraz "žirafa nemá krk" také právo existovat, pouze booleovská algebra ji definuje jako "lož".

Všechna prohlášení musí být jednoznačná, ale mohou být elementární a složená. Ty používají logické spojnice. To znamená, že v propoziční algebrové sestavě jsou výkazy tvořeny přidáním elementárních prvků pomocí logických operací.

Operace booleovské algebry

Už si pamatujeme, že operace v algebře výroků jsou logické. Stejně jako algebra čísel používá aritmetické operace pro přidávání, odečítání nebo porovnávání čísel, prvky matematické logiky umožňují sestavit složité výkazy, popřít nebo vypočítat konečný výsledek.

Logické operace pro formalizaci a jednoduchost jsou zapsány podle vzorců obvyklých pro nás v aritmetice. Vlastnosti booleovské algebry umožňují psát rovnice a vypočítat neznámé. Logické operace jsou obvykle psány pomocí pravdivé tabulky. Jeho sloupce definují výpočtové prvky a operaci, která se na nich provádí, a řádky zobrazují výsledek výpočtů.

Základní logické akce

Nejběžnější operace při booleovských operacích jsou negace (NOT) a logická AND a OR. Takže můžete popsat téměř všechny akce v algebře soudů. Budeme podrobně studovat všechny tři operace.

Odmítnutí (ne) platí pouze pro jeden prvek (operand). Operace negace se proto nazývá unární. Použijte následující symboly pro zápis konceptu non-A: ne-A, Amacr-macr-macr- nebo! A. V tabulkové podobě vypadá takto:

Pro funkci negace je typické následující příkaz: pokud A je pravda, pak A je false. Například Měsíc se točí kolem Země - pravda - Země se točí kolem Měsíce - lež.

Logické násobení a přidání

Logická AND se nazývá spojovací operace. Co to znamená? Za prvé, že lze použít na dva operandy, tj. Já je binární operace. Za druhé, pouze v případě pravdy obou operandů (a A a B) je samotný výraz pravdivý. Přísloví "Trpělivost a práce se bude lišit" předpokládá, že pouze dva faktory pomohou člověku vyrovnat se s obtížemi.

Pro psaní se používají symboly Aand-B, Asdot-B nebo AB.

Spojení je analogické k množení v aritmetice. Někdy říkají takové logické násobení. Pokud vynásobíme prvky tabulky řádky, získáme výsledek podobný logickému myšlení.

Rozdělení se nazývá logická operace OR. Hodnota pravdy trvá, když je alespoň jedna z nich výroky jsou pravdivé (nebo A nebo B). Je napsáno takto: Aor-B, A + B nebo A || B. Pravdivé tabulky pro tyto operace jsou:

Rozdělení je jako aritmetický přírůstek. Funkce logického přidání má pouze jedno omezení: 1 + 1 = 1. Ale pamatujeme si, že v digitálním formátu je matematická logika omezena na 0 a 1 (kde 1 je pravdivé, 0 je nepravé). Například prohlášení "v muzeu můžete vidět mistrovské dílo nebo setkání se zajímavým partnerem" znamená, že můžete vidět umělecká díla a můžete se seznámit se zajímavým člověkem. Současně není vyloučena možnost současného uskutečnění obou událostí.

Funkce a zákony

Takže už víme, jaké logické operace používá booleovská algebra. Funkce popisují všechny vlastnosti prvků matematické logiky a umožňují vám zjednodušit složité složené podmínky úloh. Nejrozumnější a nejjednodušší je vlastnost opuštění derivátových operací. Deriváty jsou výlučné NEBO, důsledky a rovnocennost. Jelikož jsme se seznámili pouze se základními operacemi, budeme zvažovat pouze jejich vlastnosti.

Asociativita znamená, že ve výkazech jako "a A, B a B," nezáleží na výčtu operandů. Vzorec je následující:

(Aand-B) a -B = Aand- (Band-B) = Aand-Band-B,

(Aor-B) nebo -B = Aor- (Bor-B) = Aor-Bor-B.

Jak vidíme, je to zvláštní nejen souvislostem, ale i disjunkcím.

Komutativnost tvrdí, že výsledek spojení nebo disjunkce nezávisí na tom, který prvek byl zvažován na začátku:

Aand-B = pásmo-A-Aor-B = BOR-A.

Distributivita umožňuje otevřít závorky v komplexních logických výrazech. Pravidla jsou podobná popisu závorek při vynásobení a přidávání algebry:

Aand- (Bor-B) = Aand-Bor-Aand-B- Aor-Band-B = (Aor-B) a- (Aor-B).

Vlastnosti jednotky a nula, který může být jeden z operandů, jsou také analogické k algebraickým násobením nula nebo jedna a přidání k jednomu:

Aand-0 = 0, Aand-1 = A-Aor-0 = A, Aor-1 = 1.

Idempotency říká nám, že pokud se výsledek operace ukáže jako podobný ve vztahu ke dvěma stejným operandům, pak můžete "odhodit" další opery, které komplikují průběh uvažování. Jak spojení, tak disjunkce jsou idempotentní operace.

Бand-Б = Б- Бор-Б = Б.

Absorpce také nám umožňuje zjednodušit rovnice. Absorpce uvádí, že když operace se stejným operandem je aplikována na výraz s jedním operandem, výsledkem je operand z operace absorpce.

Aand-Bor-B = B- (Aor-B) a B = B.

Sekvence operací

Sekvence operací nemá žádný význam. Ve skutečnosti, pokud jde o algebra, existuje priorita funkcí, která používá booleovskou algebru. Vzorce lze zjednodušit pouze tehdy, když je pozorována důležitost operací. Pořadí od nejvýznamnějších po méně významné získáme následující postup:

1. Odmítnutí.

2. Spojení.

3. Rozdělení bez OR.

4. Důsledky, rovnocennost.

Jak vidíme, pouze popírání a spojování nemají stejné priority. A priorita disjunkce a exkluzivní OR je stejná, stejně jako priority implikace a rovnocennosti.

Implicitní a ekvivalentní funkce

Jak již bylo řečeno, kromě základních logických operací matematická logika a teorie algoritmů používají deriváty. Nejčastěji používané důsledky a rovnocennost.

Implicace nebo logické následování je prohlášení, ve kterém jedna akce je podmínkou a druhá je důsledkem jejího naplnění. Jinými slovy, tato věta s pretexty "jestliže ... pak." "Chtěli byste jezdit, milovat a sáňkovat, abyste je mohli nosit." To znamená, že pro bruslení je nutné napínat sáňky na kopec. Pokud není touha opustit horu, nemusíte mít sáňky. Je napsáno takto: A → B nebo ArArr-B.

Ekvivalence předpokládá, že výsledná akce nastane pouze tehdy, jsou-li oba operandy pravdivé. Například, noc je nahrazena dnem pak (a teprve potom), když slunce vychází z obzoru. V jazyce matematické logiky je toto prohlášení napsáno jako: Aequiv-B, AhArr-B, A == B.

Jiné zákony booleovské algebry

Vývojová algebra se vyvíjí a mnoho vědců vědců formulovalo nové zákony. Nejslavnějšími jsou postuláty skotského matematika O. de Morgana. Poznamenal a definoval takové vlastnosti, jako je blízká negace, doplnění a dvojnásobná negace.

Zavřít Negation naznačuje, že před závorem není žádná jediná negativa: ne (A nebo B) = není A nebo NOT B.

Když je operand negován, bez ohledu na jeho význam, Kromě toho:

Pásmo-ne-B = 0- Bor-ne-B = 1.

A konečně, dvojitá negace vyrovnává se. Tedy. Před operandem buď zmizí negace, nebo zůstane jen jedna.

Jak řešit testy

Matematická logika předpokládá zjednodušení daných rovnic. Stejně jako v algebře, je nejprve nutné co nejjednodušší stav (zbavit se složitých úvodů a operací s nimi) a pak pokračovat v nalezení správné odpovědi.

Co můžeme udělat pro zjednodušení věcí? Převést všechny odvozené operace na jednoduché. Poté otevřete všechny závorky (nebo naopak, vykreslete závorky pro zkrácení tohoto prvku). Dalším krokem je aplikace vlastností booleovské algebry v praxi (absorpce, vlastnosti nuly a jednotky atd.).

Nakonec musí rovnice sestávat z minimálního počtu neznámých, spojených jednoduchými operacemi. Nejjednodušší je najít řešení, pokud dosáhnete velkého počtu úzkých negací. Pak se odpověď objeví jako sama.