V dnešním světě stále častěji používáme nejrůznější auta a pomůcky. A to nejen tehdy, když je potřeba nasadit doslova nelidskou sílu: přemístit náklad, zvedat jej do výšky, kopat dlouhý a hluboký příkop atd. Auta dnes montují roboti, jídlo připravují multivarky a základní aritmetické výpočty jsou provádí kalkulačky. Stále častěji slyšíme výraz „Booleovská algebra“. Možná je na čase pochopit roli člověka při vytváření robotů a schopnost strojů řešit nejen matematické, ale i logické problémy.
Logic
V překladu z řečtiny je logika uspořádaný systém myšlení, který vytváří vztahy mezi danými podmínkami a umožňuje vyvozovat závěry na základě premis a předpokladů. Dost často se jeden druhého ptáme: "Je to logické?" Obdržená odpověď potvrzuje naše domněnky nebo kritizuje tok myšlenek. Ale proces se nezastaví: pokračujeme v uvažování.
Někdy je počet podmínek (úvodních) tak velký a vztahy mezi nimi jsou tak spletité a složité, že lidský mozek není schopen „strávit“vše najednou. Pochopení toho, co se děje, může trvat déle než jeden měsíc (týden, rok). Alemoderní život nám nedává takové časové intervaly pro rozhodování. A uchýlíme se k pomoci počítačů. A zde se objevuje algebra logiky se svými vlastními zákony a vlastnostmi. Stažením všech počátečních dat umožňujeme počítači rozpoznat všechny vztahy, odstranit rozpory a najít uspokojivé řešení.
Matematika a logika
Slavný Gottfried Wilhelm Leibniz formuloval koncept „matematické logiky“, jehož problémy byly srozumitelné jen úzkému okruhu vědců. Tento směr nevzbudil zvláštní zájem a až do poloviny 19. století vědělo o matematické logice jen málo lidí.
Velký zájem vědecké komunity vyvolal spor, ve kterém Angličan George Boole oznámil svůj záměr vytvořit obor matematiky, který nemá absolutně žádné praktické uplatnění. Jak si z historie pamatujeme, průmyslová výroba se v té době aktivně rozvíjela, vyvíjely se všechny druhy pomocných strojů a obráběcích strojů, to znamená, že všechny vědecké objevy měly praktické zaměření.
Když se podíváme do budoucna, řekněme, že Booleova algebra je nejpoužívanější částí matematiky v moderním světě. Takže Bull ztratil argument.
George Buhl
Samotná osobnost autora si zaslouží zvláštní pozornost. I když uvážíme, že v minulosti lidé vyrůstali před námi, nelze si stále nevšimnout, že v 16 letech J. Buhl učil na vesnické škole a ve 20 letech si otevřel vlastní školu v Lincolnu. Matematik hovořil plynně pěti cizími jazyky a ve volném čase četl dílaNewton a Lagrange. A to vše je o synovi prostého dělníka!
V roce 1839 Boole poprvé předložil své vědecké práce do Cambridge Mathematical Journal. Vědci je 24 let. Booleova práce natolik zaujala členy Královské společnosti, že v roce 1844 obdržel medaili za svůj příspěvek k rozvoji matematické analýzy. Několik dalších publikovaných prací, které popisovaly prvky matematické logiky, umožnilo mladému matematikovi zaujmout místo profesora na College of Cork. Připomeňme, že Buhl sám neměl žádné vzdělání.
Nápad
V principu je Booleovská algebra velmi jednoduchá. Existují výroky (logické výrazy), které lze z hlediska matematiky definovat pouze dvěma slovy: „pravda“nebo „nepravda“. Například na jaře stromy kvetou - pravda, v létě sněží - lež. Krása této matematiky spočívá v tom, že není nutné používat pouze čísla. Jakékoli výroky s jednoznačným významem jsou docela vhodné pro algebru úsudků.
Algebru logiky lze tedy použít doslova všude: při plánování a psaní pokynů, analýze protichůdných informací o událostech a určování posloupnosti akcí. Nejdůležitější je pochopit, že je zcela jedno, jak určíme pravdivost či nepravdivost výroku. Tato „jak“a „proč“je třeba abstrahovat. Důležité je pouze konstatování faktu: pravda-nepravda.
Pro programování jsou samozřejmě důležité funkce algebry logiky, které jsou zapsány odpovídajícímiznaky a symboly. A naučit se je znamená ovládat nový cizí jazyk. Nic není nemožné.
Základní pojmy a definice
Aniž bychom zacházeli do hloubky, pojďme se zabývat terminologií. Booleovská algebra tedy předpokládá:
- statements;
- logické operace;
- funkce a zákony.
Prohlášení jsou jakékoli potvrzující výrazy, které nelze interpretovat nejednoznačně. Jsou psány jako čísla (5 > 3) nebo formulovány známými slovy (slon je největší savec). Zároveň fráze „žirafa nemá krk“má také právo existovat, pouze Booleovská algebra ji definuje jako „nepravdivou“.
Všechny výroky musí být jednoznačné, ale mohou být elementární a složené. Ty druhé používají logické spojky. To znamená, že v algebře úsudků se složené výroky tvoří přidáním elementárních výroků pomocí logických operací.
Booleovské algebraické operace
Už si pamatujeme, že operace v algebře úsudků jsou logické. Stejně jako číselná algebra používá aritmetiku k sčítání, odečítání nebo porovnávání čísel, prvky matematické logiky vám umožňují vytvářet složitá tvrzení, negovat nebo vypočítat konečný výsledek.
Logické operace pro formalizaci a jednoduchost jsou psány pomocí vzorců, které známe z aritmetiky. Vlastnosti Booleovy algebry umožňují psát rovnice a počítat neznámé. Logické operace se obvykle zapisují pomocí pravdivostní tabulky. Jeho sloupcedefinujte prvky výpočtu a operaci, která se na nich provádí, a řádky zobrazují výsledek výpočtu.
Základní logické akce
Nejběžnější operace v Booleově algebře jsou negace (NOT) a logické AND a OR. Téměř všechny akce v algebře úsudků lze popsat tímto způsobem. Pojďme si každou ze tří operací prostudovat podrobněji.
Negace (ne) se vztahuje pouze na jeden prvek (operand). Proto se operace negace nazývá unární. K napsání pojmu „ne A“použijte následující symboly: ¬A, A¯¯¯ nebo !A. V tabulkové formě to vypadá takto:
Negační funkce je charakterizována následujícím výrokem: je-li A pravdivé, pak B je nepravdivé. Například Měsíc obíhá kolem Země – pravda; Země se točí kolem Měsíce - nepravda.
Logické násobení a sčítání
Logický AND se nazývá operace konjunkce. Co to znamená? Za prvé, že může být aplikován na dva operandy, tj. A je binární operace. Za druhé, že pouze v případě pravdivosti obou operandů (A i B) je pravdivý samotný výraz. Přísloví „Trpělivost a práce všechno semele“naznačuje, že pouze oba faktory pomohou člověku vyrovnat se s obtížemi.
Symboly používané pro psaní: A∧B, A⋅B nebo A&&B.
Konjunkce je podobná násobení v aritmetice. Někdy se říká, že - logické násobení. Pokud vynásobíme prvky tabulky řádek po řádku, dostaneme výsledek podobný logickému uvažování.
Disjunkce je logická operace NEBO. Má hodnotu pravdykdyž je alespoň jedno z tvrzení pravdivé (buď A nebo B). Píše se takto: A∨B, A+B nebo A||B. Pravdivostní tabulky pro tyto operace jsou:
Disjunkce je jako aritmetické sčítání. Operace logického sčítá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 pravda, 0 je nepravda). Například výrok „v muzeu můžete vidět mistrovské dílo nebo se setkat se zajímavým partnerem“znamená, že můžete vidět umělecká díla nebo se můžete setkat se zajímavou osobou. Zároveň není vyloučena možnost, že obě události nastanou současně.
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í zjednodušit složité složené podmínky problémů. Nejsrozumitelnější a nejjednodušší vlastností se zdá být odmítnutí odvozených operací. Deriváty jsou výhradní OR, implikace a ekvivalence. Protože jsme studovali pouze základní operace, budeme také uvažovat pouze o jejich vlastnostech.
Asociativita znamená, že v příkazech jako "a A, a B a C" na pořadí operandů nezáleží. Vzorec je napsán takto:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
Jak vidíte, toto je charakteristické nejen pro konjunkci, ale také pro disjunkci.
Komutativity uvádí, že výsledekkonjunkce nebo disjunkce nezávisí na tom, který prvek byl uvažován jako první:
A∧B=B∧A; A∨B=B∨A.
Distributivita umožňuje rozšiřování závorek ve složitých logických výrazech. Pravidla jsou podobná jako u otevírání závorek při násobení a sčítání v algebře:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
Vlastnosti jedničky a nuly, které mohou být jedním z operandů, jsou také podobné algebraickému násobení nulou nebo jedničkou a sčítání s jedničkou:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotence nám říká, že pokud se s ohledem na dva stejné operandy ukáže, že výsledek operace je podobný, můžeme „zahodit“nadbytečné operandy, které komplikují průběh uvažování. Konjunkce i disjunkce jsou idempotentní operace.
B∧B=B; B∨B=B.
Absorpce nám také umožňuje zjednodušit rovnice. Absorpce uvádí, že když je na výraz s jedním operandem aplikována další operace se stejným prvkem, výsledkem je operand z operace pohlcování.
A∧B∨B=B; (A∨B)∧B=B.
Posloupnost operací
Posloupnost operací nemá malý význam. Ve skutečnosti, pokud jde o algebru, existuje priorita funkcí, které používá booleovská algebra. Vzorce lze zjednodušit pouze při dodržení významu operací. Seřazením od nejvýznamnější po nejmenší získáme následující sekvenci:
1. Odmítnutí.
2. Konjunkce.
3. Disjunkce, exkluzivníNEBO.
4. Implikace, ekvivalence.
Jak vidíte, pouze negace a konjunkce nemají stejnou přednost. A priorita disjunkce a XOR jsou stejné, stejně jako priority implikace a ekvivalence.
Funkce implikace a ekvivalence
Jak jsme již řekli, kromě základních logických operací využívá matematická logika a teorie algoritmů derivace. Nejčastěji používané jsou implikace a ekvivalence.
Implicitní nebo logický důsledek je výrok, ve kterém jedna akce je podmínkou a druhá je důsledkem její implementace. Jinými slovy, jedná se o větu s předložkami "pokud … pak." "Pokud rádi jezdíte, rádi vozíte sáně." To znamená, že na lyžování je potřeba do kopce utáhnout saně. Pokud nechcete sjíždět horu, nemusíte nosit saně. Píše se takto: A→B nebo A⇒B.
Ekvivalence předpokládá, že k výsledné akci dojde pouze tehdy, když jsou oba operandy pravdivé. Noc se například změní v den, když (a teprve když) slunce vyjde nad obzor. V jazyce matematické logiky je tento výrok zapsán následovně: A≡B, A⇔B, A==B.
Další zákony Booleovy algebry
Algebra úsudků se vyvíjí a mnoho zainteresovaných vědců formulovalo nové zákony. Za nejznámější jsou považovány postuláty skotského matematika O. de Morgana. Všiml si a definoval takové vlastnosti jako těsná negace, doplněk a dvojitá negace.
Zavřená negace znamená, že před závorkou není žádná negace:ne (A nebo B)=ne A nebo NE B.
Když je operand negován, bez ohledu na jeho hodnotu, mluví se o doplňku:
B∧¬B=0; B∨¬B=1.
A konečně, dvojitá negace se sama vyrovnává. Tito. buď negace zmizí před operandem, nebo zůstane jen jedna.
Jak řešit testy
Matematická logika předpokládá zjednodušení daných rovnic. Stejně jako v algebře si nejprve musíte podmínku co nejvíce usnadnit (zbavit se složitých vstupů a operací s nimi) a poté začít hledat správnou odpověď.
Co lze udělat pro zjednodušení? Převeďte všechny odvozené operace na jednoduché. Poté otevřete všechny držáky (nebo naopak, vyjměte jej z držáků, abyste tento prvek zkrátili). Dalším krokem by měla být aplikace vlastností Booleovy algebry v praxi (absorpce, vlastnosti nuly a jedničky atd.).
V konečném důsledku by rovnice měla sestávat z minimálního počtu neznámých kombinovaných jednoduchými operacemi. Nejjednodušší způsob, jak najít řešení, je dosáhnout velkého počtu blízkých záporů. Pak se odpověď objeví jakoby sama od sebe.
