Boolean algebra. algebra logiky. Základy matematickej logiky

V dnešnom svete sme stále viac využívajú celý rad strojov a pomôcok. A nie iba vtedy, ak je nevyhnutné aplikovať doslova nadľudskú silu: presunúť záťaž ho zdvihnúť do výšky, vykopať dlhý a hlboký priekopa, atď. Autá dnes zbierať roboty, jedlo sa varí multivarki a základné výpočty aritmetické vyrábať kalkulačky ... Stále častejšie počujeme frázu "Boolean algebra". Možno nadišiel čas na pochopenie úloha ľudských bytostí pri vytváraní robotov a strojov schopnosť riešiť nielen matematických, ale aj logické problémy.

logika

V gréckej logiky - usporiadaný systém myslenia, ktorý vytvára vzťah medzi daným podmienkam a umožňuje robiť závery založené na predpokladoch a odhadoch. Pomerne často sa pýtame seba: "Je to logické," Odpoveď potvrdzuje naše predpoklady, alebo kritizuje myšlienok. Ale proces nekončí: budeme aj naďalej hovoriť.

Niekedy je rad podmienok (vstup) je tak veľký, a vzťah medzi nimi je tak mätúce a zložité, že ľudský mozog nie je schopný "stráviť" naraz. Pre pochopenie toho, čo sa deje, môžete potrebovať viac ako jeden mesiac (týždeň, rok). Ale moderný život nedáva tieto časové intervaly, aby urobil rozhodnutie. A my sme sa uchýliť k pomoci počítačov. A je to tu, že je algebra a logika, so svojimi zákonmi a vlastnosťami. Po stiahnutí všetkých pôvodných dát, necháme počítač rozpoznať všetky vzťahy, odstrániť rozpory a nájsť uspokojivé riešenie.

Matematika a logika

Slávne Gotfrid Vilgelm Leybnits formulovaný pojem "formálne logike", ktoré úlohy boli zrozumiteľné len malý okruh vedcov. Zvlášť zaujímavé je smer nespôsobil, a až do polovice XIX storočia matematickej logiky známa málo.

Veľký záujem o vedeckej komunite spôsobila spor, v ktorom Angličan Dzhordzh Bul deklarovaný úmysel zriadiť pobočku matematiky, ktoré nemajú absolútne žiadne praktické využitie. Ako vieme z histórie, v súčasnej dobe aktívne rozvíja priemyselná výroba, sme vyvinuli všetky druhy pomocných zariadení, t. E. Všetky vedecké objavy mali praktickú orientáciu.

Pri pohľade do budúcnosti, môžeme povedať, že logická algebra - najpoužívanejšie na svete, dnes časť matematiky. Takže vaše tvrdenie Buhl stratená.

Dzhordzh Bul

Osobnosť autora si zaslúžia osobitnú pozornosť. Dokonca aj vzhľadom na to, že v minulosti ľudia vyrástol pred nami, stále je potrebné poznamenať, že v 16 rokoch John. Buhl učil na dedinskej škole a až 20 rokov otvoril vlastnú školu v Lincoln. Matematik dokonale zvládnutú päť cudzích jazykov, a vo svojom voľnom čase, čítal diela Newton a Lagrange. A to všetko - na syna obyčajného pracovníka!

V roku 1839, Buhl poslal svoje prvé vedeckých prác v Cambridge Mathematical Journal. Vedec otočil 24 rokov. Booleova práca je tak zainteresovaných členov kráľovskej spoločnosti, v roku 1844 ho získal medailu za jeho prínos k rozvoju matematickej analýzy. Niekoľko publikovaných prác, v ktorých sú prvky matematickej logiky, matematiky povolené mladý vziať post profesora na College of Cork County boli popísané. Pripomeňme, že na veľmi Boole vzdelanie nebol.

idea

V zásade platí, Boolova algebra je veľmi jednoduché. K dispozícii sú výkazy (logické výrazy), že z pohľadu matematiky, môžu byť definované len v dvoch slovách: "true" alebo "false". Napríklad stromov na jar kvitnú - pravda, v lete sneží - lož. Krása matematiky je, že to nie je nevyhnutné používať iba čísla. Pre rozhodnutie algebry celkom fit žiadna vyhlásenie s unikátnou zmysel.

To znamená, že algebra logiky možno použiť doslova všade: v plánovacom a písanie inštrukcie, analýza protichodných informácií o udalostiach a stanovenie postupnosti akcií. Najdôležitejšia vec - si uvedomiť, že nezáleží na tom, ako zistiť pravdu, alebo nepravdivosť vyhlásení. Z týchto "ako" a "prečo" treba ignorovať. Na čom záleží, je len konštatovanie faktu: pravda je lož.

Samozrejme, programovanie najdôležitejšie funkcie algebry logiky, ktoré sú zaznamenané so zodpovedajúcimi znaky a symboly. A naučiť je - to znamená naučiť nový cudzí jazyk. Nič nie je nemožné.

Základné pojmy a definície

Bez toho aby sme sa púšťali do hĺbky zaoberáme terminológie. Takže, Boolean algebra predpokladá:

• vyhlásenia;
• logické operácie;
• Funkcie a zákony.

Vyhlásenie - akékoľvek kladné výraz, ktorý môže byť interpretovaný Dvojhodnotové. Sú písané ako čísla (5> 3) alebo formulovaných známych slov (slonie - najväčší cicavce). V tomto prípade je výraz "krk žirafa nie je" má tiež právo na existenciu, iba Boolean algebra definujú ako "lži."

Všetky vyhlásenia by malo byť jednoznačné, ale môžu byť základné alebo zlúčeniny. Nedávne použitia logický zväzok. E. Vo zlúčenine závierka algebry rozsudkov vytvoreného pridaním základných logických operácií.

Boolean algebra operácie

Už sme si uvedomiť, že operácia v algebre rozhodnutí - logické. Rovnako ako algebry čísiel pomocou aritmetické operácie sčítanie, odčítanie, alebo porovnať čísla, matematickej logiky prvky umožňujú vytvoriť komplexné príkazy, popierať alebo pre výpočet konečného výsledku.

Logické operácie pre formalizáciu a jednoduchosti vyjadrené vzorcom, poznáme v aritmetike. Vlastnosti Boolova algebra rovníc, aby bolo možné zaznamenať a vypočítať neznáme. Logické operácie sú obvykle zaznamenané pravdivostná tabuľky. Jeho prvky definuje stĺpce a prevádzku výpočtovej ktorý je vykonávaný na nich, a riadky ukazujú výsledky výpočtov.

Základná logika akcie

Medzi najčastejšie v boolovské algebry operácie sú negácie (NOT) a logické AND a OR. Takže je možné popísať prakticky všetky kroky v algebre rozsudkov. Študovali sme v detaile každej z troch operácií.

Negácia (ne) sa aplikuje len na jeden prvok (operandu). Preto operácie sa nazýva unárne negácie. Ak chcete nahrávať pojem "nie" za použitie týchto symbolov: ¬A, A alebo A!. Vo forme tabuľky vyzerá takto:

Funkcia popretie typické pre takéto vyhlásenie: Ak je to pravda, potom A - je falošný. Napríklad Mesiac obieha okolo Zeme - pravdu; Zem obieha okolo Mesiaca - lož.

Logické násobenie a pridanie

Logické AND operácie sa nazýva konjunkcia. Čo to znamená? Po prvé, že to môže byť aplikovaný na dva operandy, teda I - .. Binárne operácie. Po druhé, to je iba v prípade, že o pravdivosti oba operandy (obaja A a B) je pravdivé a samotný výraz. Príslovia "Trpezlivosť a trochu úsilia," naznačuje, že iba dva faktory môžu pomôcť človeku vyrovnať sa s ťažkosťami.

symboly sú použité na záznam: A∧B, A⋅B alebo A && B.

Spojenie je podobný násobenie v aritmetiky. Niekedy sa aj povedať - logický súčin. Ak máte násobiť prvky riadkov v tabuľke, získame podobný výsledok ako logického myslenia.

Disjunkcia je logická operácia OR. Je pravda, ak aspoň jeden z tvrdení je pravdivé (A alebo B). To je napísané takto: A∨B, A + B alebo A || B. Pravda tabuľky pre tieto operácie sú nasledovné:

Disjunkcia podobné aritmetické sčítanie. logické operácie sčítanie má iba jedno obmedzenie: 1 + 1 = 1. Ale my sme si uvedomiť, že v digitálnom formáte je obmedzená na matematickej logiky 0 a 1 (kde 1 - pravda, 0 - false). Napríklad tvrdenie "v múzeu môžete vidieť dielo alebo nájsť dobrú spoločnosť" znamená, že to, čo vidíte, umeleckých diel, a je možné sa stretnúť zaujímavý človek. V rovnakej dobe, nevylučujú možnosť súčasného splnenia oboch akcií.

Funkcie a zákony

Takže už vieme, čo je logické operácie s použitím Boolean algebra. Funkcie opisuje všetky vlastnosti prvkov matematickej logiky, a nám umožňujú zjednodušiť zložité zložené príkazy. Najviac jasný a jednoduchý zdá odmietnutie vlastníctva operácií s derivátmi. Deriváty sa rozumie XOR, dôsledky a ekvivalencie. Ako sme už čítal len so základnými funkciami, a potom vlastnosť je tiež zvážiť, je jediný.

Asociativita znamená, že vo vyhlásení, ako je "obe A a B, a výpis sekvencie B 'z operandov nezáleží. Vzorec je zapísaný nasledovne:

(A∧B) ∧V = A∧ (B∧V) = A∧B∧V,

(A∨B) ∨V = A∨ (B∨V) = A∨B∨V.

Ako môžete vidieť, že to nie je jedinečné konjunkcii ale disjunkcia.

Commutativity tvrdia, že výsledkom spojenia alebo disjunkcia nezáleží, na ktorom bol bod považovaný od začiatku:

A∧B = B∧A; A∨B = B∨A.

Distributivity umožňuje zverejniť zátvorky v zložitých logických výrazov. Pravidlá sú podobné ľavú zátvorku v násobenie a navyše v algebry:

A∧ (B∨V) = A∧B∨A∧V; A∨B∧V = (A∨B) ∧ (A∨V).

vlastnosti jednotky a poškriabaniu, ktorý môže byť jedným z operandov sú tiež podobné algebraického násobenie nula alebo jedna, a pridaním jednotky:

A∧0 = 0, A∧1 = A; A∨0 = A, A∨1 = 1.

Idempotence nám hovorí, že v prípade relatívne dva rovnaké operandmi výsledok operácie je rovnaká, môžete si "hodiť" prebytočné komplikovať uvažovania operandy. A konjunkcia a disjunkcia operácie sú idempotent.

B∧B = B; B∨B = B.

Akvizícia nám tiež umožňuje zjednodušiť rovnice. Absorpcia sa uvádza, že keď je expresia vzťahujúce sa na jeden operand, ďalšie operácie s rovnakým prvkom výsledku operandu absorbuje prevádzku.

A∧B∨B = B; (A∨B) ∧B = B.

sled operácií

Sled operácií má veľký význam. V skutočnosti, pokiaľ ide o algebry, tam je prioritou funkcia, ktorá používa Boolean algebra. Rovnica môže byť zjednodušiť iba s výhradou významu operácií. Poradie najvýznamnejšie k zanedbateľné, získame nasledovné sekvenciu:

1. Denial.

2. Spojenie.

3. disjunkcia, XOR.

4. Z toho vyplýva, ekvivalencie.

Ako môžete vidieť, iba negáciu spojenie a nemajú rovnakú prioritu. Prioritou k rozpojenie a XOR sú si rovné, rovnako ako priority implikácie a ekvivalencie.

Funkcia implikácie a ekvivalencie

Ako sme už povedali, okrem základných logických operácií, matematickej logiky a teórie algoritmov s využitím derivátov. To je najviac často implikácie a ekvivalencie.

Z toho vyplýva, alebo logický dôsledok - toto vyhlásenie, v ktorom jedna akcia je stav, a ďalšie - v dôsledku jeho vykonávania. Inými slovami, tento návrh sa zámienkou, že "ak ... potom". "Po večeri prichádza zúčtovanie." E. Pre jazdu musia byť dotiahnuté na sánkovať kopca. Ak nie je ochota pohybovať sa dole z hory, a potom pretiahnite sane nie je nutné. Je napísané takto: A → B alebo A⇒B.

Ekvivalencie vyplýva, že čistý efekt nastáva iba v prípade, že sú splnené oba operandy. Napríklad noc ustupuje dňu potom (a len vtedy), keď je slnko nad obzorom. V reči matematickej logiky tohto tvrdenia je napísaný ako A≡B, A⇔B, A == B.

Iné zákony Booleovej algebry

úsudok algebra sa vyvíja, a mnohí majú záujem vedcov formulovať nové zákony. Najznámejšie sú považované postuluje škótsky matematik O. De Morgan. Všimol si, a dal definíciu takých vlastností, ako úzke negáciu, sčítanie a dvojaký zápor.

Zavrieť odmietnutie naznačuje, že pred tým, než zátvorka poprieť: nie (A alebo B) = nie A alebo B. NOT

Ak je operand nepovolený, bez ohľadu na jeho hodnotu, povedzme o pridania:

B∧¬B = 0; B∨¬B = 1.

A konečne, dvojitá negácie sám kompenzuje. tj predtým jeden operand negácia zmizne, alebo zostane len jedna.

Ako riešiť testy

Logika znamená zjednodušenie vopred stanovenej rovnice. Rovnako ako vo lži algebre, je nutné maximálne uľahčiť prvú podmienku (ako sa zbaviť komplikovaných vstupných operácií, a spolu s nimi), potom začať hľadať správnu odpoveď.

Čo robiť, aby zjednodušiť? Previesť všetky deriváty v jednoduchom prevádzke. Potom odhaliť všetky zátvorky (alebo naopak, aby sa držiaky na zníženie tohto prvku). Ďalším krokom by malo byť použitie logické vlastnosti algebry v praxi (absorpčné vlastnosti nulou a jednotkou, a t.).

Nakoniec, rovnice by mal pozostávať z minimálneho počtu neznámych, v kombinácii s jednoduchých operácií. Najjednoduchší spôsob, ako hľadať riešenie, ak urobíte veľké množstvo blízkych negatívov. Potom odpoveď vyskočí akoby sám od seba.