V dnešnom svete čoraz častejšie používame rôzne autá a pomôcky. A to nielen vtedy, keď je potrebné použiť doslova neľudskú silu: premiestniť náklad, zdvihnúť ho do výšky, vykopať dlhú a hlbokú priekopu atď. Autá dnes montujú roboty, jedlo pripravujú multivarky a základné aritmetické výpočty sú vykonávané kalkulačkami. Čoraz častejšie počujeme výraz „Booleovská algebra“. Možno je čas pochopiť úlohu človeka pri vytváraní robotov a schopnosť strojov riešiť nielen matematické, ale aj logické problémy.
Logic
Logika v preklade z gréčtiny je usporiadaný systém myslenia, ktorý vytvára vzťahy medzi danými podmienkami a umožňuje vyvodzovať závery na základe premis a predpokladov. Dosť často sa jeden druhého pýtame: "Je to logické?" Prijatá odpoveď potvrdzuje naše predpoklady alebo kritizuje tok myšlienok. Ale proces sa nezastaví: pokračujeme v uvažovaní.
Niekedy je počet stavov (úvodných) taký veľký a vzťahy medzi nimi sú také spletité a zložité, že ľudský mozog nie je schopný „stráviť“všetko naraz. Pochopenie toho, čo sa deje, môže trvať viac ako jeden mesiac (týždeň, rok). alemoderný život nám nedáva také časové intervaly na rozhodovanie. A uchyľujeme sa k pomoci počítačov. A tu sa objavuje algebra logiky s vlastnými zákonmi a vlastnosťami. Stiahnutím všetkých počiatočných údajov umožňujeme počítaču rozpoznať všetky vzťahy, odstrániť rozpory a nájsť uspokojivé riešenie.
Matematika a logika
Slávny Gottfried Wilhelm Leibniz sformuloval koncept „matematickej logiky“, ktorej problémy boli pochopiteľné len pre úzky okruh vedcov. Tento smer nevzbudil zvláštny záujem a až do polovice 19. storočia málokto vedel o matematickej logike.
Veľký záujem vedeckej komunity vyvolal spor, v ktorom Angličan George Boole oznámil svoj zámer vytvoriť odvetvie matematiky, ktoré nemá absolútne žiadne praktické využitie. Ako si z histórie pamätáme, v tom čase sa aktívne rozvíjala priemyselná výroba, vyvíjali sa všetky druhy pomocných strojov a obrábacích strojov, čiže všetky vedecké objavy mali praktické zameranie.
Pri pohľade do budúcnosti povedzme, že booleovská algebra je najpoužívanejšou časťou matematiky v modernom svete. Takže Bull stratil argument.
George Buhl
Samotná osobnosť autora si zaslúži osobitnú pozornosť. Aj keď uvážime, že v minulosti ľudia vyrastali pred nami, nemožno si ešte nevšimnúť, že J. Buhl už ako 16-ročný učil na dedinskej škole a ako 20-ročný si otvoril vlastnú školu v Lincolne. Matematik ovládal päť cudzích jazykov a vo voľnom čase čítal dielaNewton a Lagrange. A toto všetko je o synovi jednoduchého robotníka!
V roku 1839 Boole prvýkrát predložil svoje vedecké práce do Cambridge Mathematical Journal. Vedec má 24 rokov. Booleova práca natoľko zaujala členov Kráľovskej spoločnosti, že v roku 1844 dostal medailu za príspevok k rozvoju matematickej analýzy. Niekoľko ďalších publikovaných prác, ktoré popisovali prvky matematickej logiky, umožnilo mladému matematikovi zaujať miesto profesora na Cork County College. Pripomeňme, že Buhl sám nemal žiadne vzdelanie.
Nápad
V princípe je Booleovská algebra veľmi jednoduchá. Existujú výroky (logické výrazy), ktoré možno z hľadiska matematiky definovať iba dvoma slovami: „pravda“alebo „nepravda“. Napríklad na jar kvitnú stromy - pravda, v lete sneží - lož. Krása tejto matematiky je v tom, že nie je striktne potrebné používať iba čísla. Akékoľvek tvrdenia s jednoznačným významom sú celkom vhodné pre algebru úsudkov.
Algebra logiky sa teda dá použiť doslova všade: pri plánovaní a písaní pokynov, analýze protichodných informácií o udalostiach a určovaní postupnosti akcií. Najdôležitejšie je pochopiť, že je úplne jedno, ako určíme pravdivosť alebo nepravdivosť výroku. Tieto „ako“a „prečo“je potrebné abstrahovať. Dôležité je iba vyhlásenie faktu: pravda – nepravda.
Pre programovanie sú samozrejme dôležité funkcie algebry logiky, ktoré sú zapísané príslušnýmiznaky a symboly. A naučiť sa ich znamená ovládať nový cudzí jazyk. Nič nie je nemožné.
Základné pojmy a definície
Bez toho, aby sme zachádzali do hĺbky, poďme sa zaoberať terminológiou. Booleovská algebra teda predpokladá:
- statements;
- logické operácie;
- funkcie a zákony.
Vyhlásenia sú akékoľvek kladné vyjadrenia, ktoré nemožno interpretovať nejednoznačne. Zapisujú sa ako čísla (5 > 3) alebo sú formulované známymi slovami (slon je najväčší cicavec). Zároveň fráza „žirafa nemá krk“má tiež právo na existenciu, iba booleovská algebra ju bude definovať ako „nepravda“.
Všetky tvrdenia musia byť jednoznačné, ale môžu byť elementárne a zložené. Posledne menované používajú logické spojovacie prvky. To znamená, že v algebre úsudkov sa zložené výroky tvoria pridávaním elementárnych výrokov pomocou logických operácií.
operácie booleovskej algebry
Už si pamätáme, že operácie v algebre úsudkov sú logické. Rovnako ako číselná algebra používa aritmetiku na sčítanie, odčítanie alebo porovnávanie čísel, prvky matematickej logiky vám umožňujú robiť zložité výroky, negovať alebo vypočítať konečný výsledok.
Logické operácie pre formalizáciu a jednoduchosť sa píšu pomocou vzorcov, ktoré poznáme z aritmetiky. Vlastnosti Booleovej algebry umožňujú písať rovnice a počítať neznáme. Logické operácie sa zvyčajne zapisujú pomocou pravdivostnej tabuľky. Jeho stĺpcedefinujte prvky výpočtu a operáciu, ktorá sa na nich vykonáva, a riadky zobrazujú výsledok výpočtu.
Základné logické akcie
Najbežnejšie operácie v Booleovej algebre sú negácia (NOT) a logické AND a OR. Takmer všetky akcie v algebre úsudkov možno opísať týmto spôsobom. Preštudujme si každú z troch operácií podrobnejšie.
Negácia (ne) sa vzťahuje len na jeden prvok (operand). Preto sa operácia negácie nazýva unárna. Na napísanie pojmu „nie A“použite nasledujúce symboly: ¬A, A¯¯¯ alebo !A. V tabuľkovej forme to vyzerá takto:
Funkcia negácie je charakterizovaná nasledujúcim výrokom: ak A je pravda, potom B je nepravda. Napríklad Mesiac sa točí okolo Zeme – pravda; Zem sa točí okolo Mesiaca - nepravda.
Logické násobenie a sčítanie
Logický AND sa nazýva operácia spojenia. Čo to znamená? Po prvé, že ho možno použiť na dva operandy, t.j. A je binárna operácia. Po druhé, že iba v prípade pravdivosti oboch operandov (A aj B) je pravdivý samotný výraz. Príslovie „Trpezlivosť a práca zomelie všetko“naznačuje, že len oba faktory pomôžu človeku vyrovnať sa s ťažkosťami.
Symboly používané na písanie: A∧B, A⋅B alebo A&&B.
Spojka je podobná násobeniu v aritmetike. Niekedy sa hovorí, že - logické násobenie. Ak vynásobíme prvky tabuľky riadok po riadku, dostaneme výsledok podobný logickému uvažovaniu.
Disjunkcia je logická operácia ALEBO. Má hodnotu pravdykeď je aspoň jedno z tvrdení pravdivé (buď A alebo B). Píše sa takto: A∨B, A+B alebo A||B. Pravdivé tabuľky pre tieto operácie sú:
Disjunkcia je ako aritmetické sčítanie. Operácia logického sčítania má len jedno obmedzenie: 1+1=1. Pamätáme si však, že v digitálnom formáte je matematická logika obmedzená na 0 a 1 (kde 1 je pravda, 0 je nepravda). Napríklad vyhlásenie „v múzeu môžete vidieť majstrovské dielo alebo stretnúť zaujímavého partnera“znamená, že môžete vidieť umelecké diela alebo môžete stretnúť zaujímavého človeka. Zároveň nie je vylúčená možnosť, že obe udalosti nastanú súčasne.
Funkcie a zákony
Takže už vieme, aké logické operácie používa booleovská algebra. Funkcie opisujú všetky vlastnosti prvkov matematickej logiky a umožňujú zjednodušiť zložité zložené podmienky problémov. Najzrozumiteľnejšou a najjednoduchšou vlastnosťou sa zdá byť odmietnutie odvodených operácií. Deriváty sú výhradné OR, implikácia a ekvivalencia. Keďže sme študovali iba základné operácie, budeme brať do úvahy aj vlastnosti iba z nich.
Asociativita znamená, že vo výrokoch ako „a A, a B a C“na poradí operandov nezáleží. Vzorec je napísaný takto:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
Ako vidíte, toto je charakteristické nielen pre konjunkciu, ale aj pre disjunkciu.
Komutativity uvádza, že výsledokkonjunkcia alebo disjunkcia nezávisí od toho, ktorý prvok bol považovaný za prvý:
A∧B=B∧A; A∨B=B∨A.
Distributivita umožňuje rozšíriť zátvorky v zložitých logických výrazoch. Pravidlá sú podobné ako pri otváraní zátvoriek pri násobení a sčítaní v algebre:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
Vlastnosti jedna a nula, ktoré môžu byť jedným z operandov, sú tiež podobné algebraickému násobeniu nulou alebo jednotkou a sčítaniu s jednotkou:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotencia nám hovorí, že ak sa vzhľadom na dva rovnaké operandy ukáže, že výsledok operácie je podobný, potom môžeme „vyhodiť“nadbytočné operandy, ktoré komplikujú priebeh uvažovania. Konjunkcia aj disjunkcia sú idempotentné operácie.
B∧B=B; B∨B=B.
Absorpcia nám tiež umožňuje zjednodušiť rovnice. Absorpcia uvádza, že keď sa na výraz s jedným operandom aplikuje ďalšia operácia s rovnakým prvkom, výsledkom je operand z operácie pohlcovania.
A∧B∨B=B; (A∨B)∧B=B.
Postupnosť operácií
Poradie operácií nemá malý význam. V skutočnosti, pokiaľ ide o algebru, existuje priorita funkcií, ktoré používa booleovská algebra. Vzorce sa dajú zjednodušiť iba vtedy, ak sa dodrží význam operácií. Zoradením od najvýznamnejšieho po najmenšieho dostaneme nasledujúcu postupnosť:
1. Popretie.
2. Konjunkcia.
3. Disjunkcia, exkluzívnaALEBO.
4. Implikácia, ekvivalencia.
Ako vidíte, iba negácia a konjunkcia nemajú rovnakú prednosť. A priorita disjunkcie a XOR sú rovnaké, rovnako ako priority implikácie a ekvivalencie.
Funkcie implikácie a ekvivalencie
Ako sme už povedali, okrem základných logických operácií využíva matematická logika a teória algoritmov aj derivácie. Najčastejšie používané sú implikácia a ekvivalencia.
Implikácia alebo logický dôsledok je vyhlásenie, v ktorom jedna akcia je podmienkou a druhá je dôsledkom jej implementácie. Inými slovami, toto je veta s predložkami "ak … potom." "Ak rád jazdíš, rád nosíš sane." To znamená, že na lyžovanie je potrebné utiahnuť sánky do kopca. Ak nemáte túžbu pohybovať sa dole z hory, nemusíte nosiť sane. Píše sa takto: A→B alebo A⇒B.
Ekvivalencia predpokladá, že výsledná akcia nastane iba vtedy, keď sú oba operandy pravdivé. Napríklad noc sa zmení na deň, keď (a iba vtedy) slnko vyjde nad obzor. V jazyku matematickej logiky je tento výrok napísaný takto: A≡B, A⇔B, A==B.
Iné zákony Booleovej algebry
Algebra úsudkov sa vyvíja a mnohí zainteresovaní vedci sformulovali nové zákony. Za najznámejšie sa považujú postuláty škótskeho matematika O. de Morgana. Všimol si a definoval také vlastnosti ako blízka negácia, doplnok a dvojitá negácia.
Zatvorená negácia znamená, že pred zátvorkou nie je žiadna negácia:nie (A alebo B)=nie A alebo NIE B.
Keď je operand negovaný, bez ohľadu na jeho hodnotu, hovorí sa o doplnku:
B∧¬B=0; B∨¬B=1.
A nakoniec, dvojitá negácia sa sama vyrovná. Tie. buď negácia zmizne pred operandom, alebo zostane iba jedna.
Ako riešiť testy
Matematická logika predpokladá zjednodušenie daných rovníc. Podobne ako v algebre, aj tu si musíte podmienku čo najviac uľahčiť (zbaviť sa zložitých vstupov a operácií s nimi) a potom začať hľadať správnu odpoveď.
Čo možno urobiť pre zjednodušenie? Preveďte všetky odvodené operácie na jednoduché. Potom otvorte všetky držiaky (alebo naopak, vyberte ho z držiakov, aby ste tento prvok skrátili). Ďalším krokom by malo byť uplatnenie vlastností Booleovej algebry v praxi (absorpcia, vlastnosti nuly a jednotky atď.).
V konečnom dôsledku by rovnica mala pozostávať z minimálneho počtu neznámych kombinovaných jednoduchými operáciami. Najjednoduchší spôsob, ako nájsť riešenie, je dosiahnuť veľké množstvo blízkych negatív. Potom sa odpoveď objaví akoby sama od seba.
