În lumea de astăzi, folosim din ce în ce mai mult o varietate de mașini și gadgeturi. Și nu numai atunci când este necesar să aplicați o forță inumană: mutați încărcătura, ridicați-o la o înălțime, săpați un șanț lung și adânc etc. Mașinile de astăzi sunt asamblate de roboți, mâncarea este pregătită de multicookers și calculele aritmetice elementare sunt efectuate de calculatoare. Din ce în ce mai des auzim expresia „algebră booleană”. Poate că este timpul să înțelegem rolul omului în crearea roboților și capacitatea mașinilor de a rezolva probleme nu numai matematice, ci și logice.
Logic
Tradusă din greacă, logica este un sistem ordonat de gândire care creează relații între condiții date și vă permite să trageți concluzii bazate pe premise și presupuneri. Destul de des ne întrebăm unul pe altul: „Este logic?” Răspunsul primit confirmă presupunerile noastre sau critică trenul de gândire. Dar procesul nu se oprește: continuăm să raționăm.
Uneori, numărul de condiții (introductive) este atât de mare, iar relațiile dintre ele sunt atât de complicate și complexe încât creierul uman nu este capabil să „digere” totul deodată. Poate dura mai mult de o lună (săptămână, an) pentru a înțelege ce se întâmplă. Darviața modernă nu ne oferă astfel de intervale de timp pentru luarea deciziilor. Și apelăm la ajutorul computerelor. Și aici apare algebra logicii, cu propriile legi și proprietăți. Prin descărcarea tuturor datelor inițiale, permitem computerului să recunoască toate relațiile, să elimine contradicțiile și să găsească o soluție satisfăcătoare.
Matematică și logică
Famosul Gottfried Wilhelm Leibniz a formulat conceptul de „logică matematică”, ale cărei probleme erau înțelese doar de un cerc restrâns de oameni de știință. Această direcție nu a trezit un interes deosebit și, până la mijlocul secolului al XIX-lea, puțini oameni știau despre logica matematică.
Un mare interes în comunitatea științifică a provocat o dispută în care englezul George Boole și-a anunțat intenția de a crea o ramură a matematicii care nu are absolut nicio aplicație practică. După cum ne amintim din istorie, producția industrială se dezvolta activ în acea perioadă, se dezvoltau tot felul de mașini auxiliare și mașini-unelte, adică toate descoperirile științifice aveau un accent practic.
Privind în viitor, să presupunem că algebra booleană este cea mai folosită parte a matematicii în lumea modernă. Așa că Bull și-a pierdut argumentul.
George Buhl
Însăși personalitatea autorului merită o atenție specială. Chiar și având în vedere că în trecut oamenii au crescut înaintea noastră, este încă imposibil să nu remarcăm că la vârsta de 16 ani, J. Buhl a predat la o școală din sat, iar la 20 de ani și-a deschis propria școală în Lincoln. Matematicianul vorbea fluent cinci limbi străine, iar în timpul liber citea lucrăriNewton și Lagrange. Și toate acestea sunt despre fiul unui simplu muncitor!
În 1839, Boole și-a prezentat pentru prima dată lucrările științifice la Cambridge Mathematical Journal. Omul de știință are 24 de ani. Lucrarea lui Boole i-a interesat atât de mult pe membrii Societății Regale, încât în 1844 a primit o medalie pentru contribuția sa la dezvoltarea analizei matematice. Mai multe lucrări publicate, care descriu elementele logicii matematice, i-au permis tânărului matematician să preia postul de profesor la Colegiul Comitatului Cork. Amintiți-vă că Buhl însuși nu a avut studii.
Idee
În principiu, algebra booleană este foarte simplă. Există afirmații (expresii logice) care, din punctul de vedere al matematicii, pot fi definite doar prin două cuvinte: „adevărat” sau „fals”. De exemplu, primăvara copacii înfloresc - adevărat, vara ninge - o minciună. Frumusețea acestei matematici este că nu există o nevoie strictă de a folosi doar numere. Orice afirmații cu un înțeles lipsit de ambiguitate sunt destul de potrivite pentru algebra judecăților.
Astfel, algebra logicii poate fi folosită literalmente peste tot: în programarea și scrierea instrucțiunilor, analizarea informațiilor conflictuale despre evenimente și determinarea secvenței acțiunilor. Cel mai important lucru este să înțelegem că este complet neimportant modul în care determinăm adevărul sau falsitatea afirmației. Aceste „cum” și „de ce” trebuie eliminate. Doar afirmația faptului contează: adevărat-fals.
Bineînțeles, pentru programare, sunt importante funcțiile algebrei logicii, care sunt scrise de corespunzătoaresemne și simboluri. Și a le învăța înseamnă a stăpâni o nouă limbă străină. Nimic nu este imposibil.
Concepte și definiții de bază
Fără a intra în profunzime, să ne ocupăm de terminologie. Deci algebra booleană presupune:
- declarații;
- operații logice;
- funcții și legi.
Declarațiile sunt orice expresii afirmative care nu pot fi interpretate în mod ambiguu. Ele sunt scrise ca numere (5 > 3) sau formulate în cuvinte familiare (elefantul este cel mai mare mamifer). În același timp, expresia „girafa nu are gât” are și dreptul de a exista, doar algebra booleană o va defini ca „falsă”.
Toate afirmațiile trebuie să fie lipsite de ambiguitate, dar pot fi elementare și compuse. Acestea din urmă folosesc conexiuni logice. Adică, în algebra judecăților, enunțurile compuse se formează prin adăugarea de enunțuri elementare prin intermediul operațiilor logice.
Operații de algebră booleană
Ne amintim deja că operațiile în algebra judecăților sunt logice. Așa cum algebra numerelor folosește aritmetica pentru a adăuga, scădea sau compara numere, elementele logicii matematice vă permit să faceți declarații complexe, să anulați sau să calculați rezultatul final.
Operațiile logice pentru formalizare și simplitate sunt scrise prin formule familiare nouă în aritmetică. Proprietățile algebrei booleene fac posibilă scrierea ecuațiilor și calcularea necunoscutelor. Operațiile logice sunt de obicei scrise folosind un tabel de adevăr. Coloanele saledefiniți elementele calculului și operația care se efectuează asupra acestora, iar liniile arată rezultatul calculului.
Acțiuni logice de bază
Cele mai frecvente operații în algebra booleană sunt negația (NU) și AND și SAU logic. Aproape toate acțiunile din algebra judecăților pot fi descrise în acest fel. Să studiem fiecare dintre cele trei operații mai detaliat.
Negația (nu) se aplică doar unui element (operand). Prin urmare, operația de negație se numește unară. Pentru a scrie conceptul „nu A” folosiți următoarele simboluri: ¬A, A¯¯¯ sau !A. În formă tabelară, arată astfel:
Funcția de negație este caracterizată de următoarea afirmație: dacă A este adevărat, atunci B este fals. De exemplu, Luna se învârte în jurul Pământului – adevărat; Pământul se învârte în jurul lunii - fals.
Înmulțirea și adunarea logică
ȘI logic se numește operația de conjuncție. Ce înseamnă? În primul rând, că poate fi aplicat la doi operanzi, adică și este o operație binară. În al doilea rând, că numai în cazul adevărului ambilor operanzi (atât A cât și B) expresia în sine este adevărată. Proverbul „Răbdarea și munca vor macina totul” sugerează că numai ambii factori vor ajuta o persoană să facă față dificultăților.
Simboluri folosite pentru scriere: A∧B, A⋅B sau A&&B.
Conjuncția este similară cu înmulțirea din aritmetică. Uneori se spune că - înmulțirea logică. Dacă înmulțim elementele rândului tabelului cu rând, obținem un rezultat similar raționamentului logic.
Disjuncția este o operație logică SAU. Ia valoarea adevăruluicând cel puțin una dintre afirmații este adevărată (fie A sau B). Se scrie astfel: A∨B, A+B sau A||B. Tabelele de adevăr pentru aceste operațiuni sunt:
Disjuncția este ca adunarea aritmetică. Operația logică de adunare are o singură limitare: 1+1=1. Dar ne amintim că în format digital, logica matematică este limitată la 0 și 1 (unde 1 este adevărat, 0 este fals). De exemplu, afirmația „într-un muzeu poți vedea o capodoperă sau poți întâlni un interlocutor interesant” înseamnă că poți vedea opere de artă sau poți întâlni o persoană interesantă. În același timp, nu este exclusă posibilitatea ca ambele evenimente să apară simultan.
Funcții și legi
Deci, știm deja ce operații logice folosește algebra booleană. Funcțiile descriu toate proprietățile elementelor logicii matematice și vă permit să simplificați condiții complexe complexe ale problemelor. Cea mai de înțeles și mai simplă proprietate pare să fie respingerea operațiilor derivate. Derivatele sunt OR exclusive, implicație și echivalență. Deoarece am studiat doar operațiile de bază, vom lua în considerare și proprietățile numai ale acestora.
Asociativitatea înseamnă că în afirmații precum „și A, și B și C”, ordinea operanzilor nu contează. Formula este scrisă astfel:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
După cum puteți vedea, aceasta este caracteristică nu numai conjuncției, ci și disjuncției.
Comutativitatea afirmă că rezultatulconjuncția sau disjuncția nu depinde de ce element a fost considerat primul:
A∧B=B∧A; A∨B=B∨A.
Distributivitatea permite extinderea parantezelor în expresii logice complexe. Regulile sunt similare cu deschiderea parantezelor în înmulțire și adunare în algebră:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
Proprietățile lui unu și zero, care pot fi unul dintre operanzi, sunt, de asemenea, similare cu înmulțirea algebrică cu zero sau cu unu și cu adunarea cu unu:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotenta ne spune că dacă, în raport cu doi operanzi egali, rezultatul unei operații se dovedește a fi similar, atunci putem „arunca” operanzii suplimentari care complică cursul raționamentului. Atât conjuncția, cât și disjuncția sunt operații idempotente.
B∧B=B; B∨B=B.
Absorbția ne permite, de asemenea, să simplificăm ecuațiile. Absorbția afirmă că atunci când o altă operație cu același element este aplicată unei expresii cu un operand, rezultatul este operandul din operația de absorbție.
A∧B∨B=B; (A∨B)∧B=B.
Secvența de operații
Succesiunea operațiilor este de o importanță nu mică. De fapt, ca și pentru algebră, există o prioritate a funcțiilor pe care le folosește algebra booleană. Formulele pot fi simplificate numai dacă se respectă semnificația operațiilor. Clasând de la cel mai semnificativ la cel mai puțin, obținem următoarea secvență:
1. Respingere.
2. Conjuncție.
3. Disjuncție, exclusivitateSAU
4. Implicație, echivalență.
După cum puteți vedea, numai negația și conjuncția nu au prioritate egală. Și prioritatea disjuncției și XOR sunt egale, precum și prioritățile de implicare și echivalență.
Funcții de implicare și echivalență
După cum am spus deja, pe lângă operațiile logice de bază, logica matematică și teoria algoritmilor folosesc derivate. Cele mai utilizate sunt implicarea și echivalența.
Implicația, sau consecința logică, este o declarație în care o acțiune este o condiție, iar ceal altă este o consecință a implementării acesteia. Cu alte cuvinte, aceasta este o propoziție cu prepoziții „dacă… atunci”. „Dacă îți place să călărești, adoră să cari sănii.” Adică, pentru schi, trebuie să strângeți sania în sus pe deal. Dacă nu există dorința de a vă deplasa pe munte, atunci nu trebuie să cărați sania. Este scris astfel: A→B sau A⇒B.
Echivalența presupune că acțiunea rezultată are loc numai atunci când ambii operanzi sunt adevărati. De exemplu, noaptea se transformă în zi când (și numai când) soarele răsare peste orizont. În limbajul logicii matematice, această afirmație este scrisă astfel: A≡B, A⇔B, A==B.
Alte legi ale algebrei booleene
Algebra judecăților se dezvoltă, iar mulți oameni de știință interesați au formulat noi legi. Postulatele matematicianului scoțian O. de Morgan sunt considerate cele mai cunoscute. El a observat și a definit proprietăți ca negație apropiată, complement și negație dublă.
Negația apropiată înseamnă că nu există nicio negație înaintea parantezei:nu (A sau B)=nu A sau NU B.
Când un operand este negat, indiferent de valoarea lui, se vorbește de un complement:
B∧¬B=0; B∨¬B=1.
Și, în sfârșit, dubla negație se compensează singură. Acestea. fie negația dispare înaintea operandului, fie rămâne doar una.
Cum se rezolvă teste
Logica matematică implică simplificarea ecuațiilor date. La fel ca în algebră, trebuie mai întâi să faci condiția cât mai ușoară posibil (scăpați de intrările și operațiunile complexe cu acestea), apoi să începeți să căutați răspunsul corect.
Ce se poate face pentru a simplifica? Convertiți toate operațiunile derivate în operațiuni simple. Apoi deschideți toate parantezele (sau invers, scoateți-l din paranteze pentru a scurta acest element). Următorul pas ar trebui să fie aplicarea proprietăților algebrei booleene în practică (absorbție, proprietăți de zero și unu etc.).
În cele din urmă, ecuația ar trebui să conțină numărul minim de necunoscute combinate prin operații simple. Cel mai simplu mod de a găsi o soluție este de a obține un număr mare de negative apropiate. Apoi răspunsul va apărea ca de la sine.
