Informatica. Conversia expresiilor booleene

Lucrarea propusă va fi examinată în detaliuproblema transformării expresiilor logice. În plus, vă sugerăm să luați un curs scurt pe logică, unde vor fi examinate principalele legi și concepte. Transformarea expresiilor logice este un proces destul de complicat, dacă nu cunoașteți toate nuanțele subiectului însuși.

Cursul de informatică va părea simplu șidă-i plăcere dacă citiți cu atenție acest articol și cunoașteți regulile și legile transformării, rezolvarea problemelor și elaborarea schemelor. Vă sugerăm să începeți chiar acum.

Stiinta Logica

Elementele de bază ale logicii - acesta este un subiect destul de dificil,pe el sunt scrise o mulțime de volume. În acest articol, vom analiza elementele de bază și legile transformării expresiilor logice, adică informațiile vor fi maxim comprimate și concentrate. Acest lucru este necesar pentru a lua în considerare tehnologiile computerizate și proiectarea circuitelor.

Pentru început, ce este logic și de ce este necesar? Este important de menționat că aceasta este o știință întreagă care ia în considerare formele și metodele de raționament. Tot ceea ce vedem, ascultăm sau facem, respectă legile. Aruncă mingea de la o înălțime - întotdeauna zboară în jos, deoarece respectă legile fizicii. Încă dimineața adăugăm cafea parfumată, adăugăm zahăr, iar substanțele pierdute se dizolvă instantaneu în apă, respectând legile fizicii. Vorbim cu prietenii, împărtășindu-ne planurile: "Dacă îmi protejez bine lucrarea, o să obțin o diplomă roșie", "Nu pot veni cu mașina, pentru că este în reparație". Fără a observa, ne construim toate conversațiile, bazându-ne pe logică și pe legile ei. Deci, de ce avem nevoie de știința logicii? Bineînțeles, știind legile sale, puteți determina cu acuratețe rezultatul unui eveniment, deoarece nu trebuie să acționați la întâmplare și să vă asumați riscuri.

Deși gândirea este un proces destul de complex, totuși ea poate fi împărțită în anumite componente, mai precis, forme (prin care are loc exprimarea gândirii):

• concepte;
• declarații;
• raționament;
• probe.

Apoi, vă sugerăm să mergeți la funcții logice și să convertiți expresii logice. Informatica va fi distractivă și destul de simplă pentru dvs. dacă citiți cu atenție acest articol.

Funcții logice

Acum ne propunem să ne cunoaștem logicfuncții. Adesea, în biletele de examinare uniformă de stat din partea B, există probleme cu transformarea expresiilor logice în segmente numerice. Ele nu pot fi rezolvate fără a cunoaște funcțiile logicii.

Care este principala sarcină a acestei științe? Desigur, studiul expresiilor logice (complexe și simple). Cum apare o declarație complexă? Prin fuziunea simplă, ceea ce se întâmplă prin pachete, care sunt numite în mod obișnuit funcții.

În total, puteți distinge cinci pachete:

• inversiune (adică negație, cu ajutorul acestei funcții se poate obține o declarație, opusul căruia: merg la cinema astăzi - nu merg la cinema astăzi);
• disjuncție (această funcție este adesea numită logicăîn plus, pentru a deveni clar, să oferim un exemplu simplu din viață: "dacă am dureri de cap sau stomac, atunci nu voi merge la școală" - această expresie va fi adevărată dacă se ia în considerare una dintre cerințe);
• conjuncție (adesea denumită multiplicare logică: "dacă mă spăl vase și fac lecții, atunci voi ieși cu prietenii" - această expresie va fi adevărată dacă se iau în considerare două condiții);
• implicare (în logică se numește această funcțieDin păcate, nu poate fi ilustrată de situația vieții; o functie falsa va fi in cazul in care ceva ar fi vrut sa fie facut, dar nu a functionat, in alte cazuri functia va fi adevarata);
• echivalența (sau egalitatea, dacă două afirmații sunt adevărate sau false, atunci ca rezultat vom obține adevărul).

Este important să rețineți că în domeniul informaticii orice simplăexpresia este marcată prin litera principală a alfabetului latin. Apoi, trebuie să vă amintiți tabelul de adevăr pentru fiecare funcție. Rețineți că nu este necesar să o învățați, va fi suficient doar să înțelegeți funcțiile.

Tabele de adevăr

conjuncție

despărțire

inversiune

implicație

echivalență

În plus, este important să rețineți faptul că minciunaîn logică este notată cu numărul 0 și expresia adevărată cu numărul 1. Pentru comoditate, puteți folosi atât semne plus cât și minus. Acordați atenție faptului că expresiile false și adevărate din tabelele propuse sunt indicate prin literele "L" și, respectiv, "I".

clădire

Înainte de a trece la transformarea expresiilor logice, este necesar să ne cunoaștem chiar construcția lor. Orice compus sau, după cum sa spus mai înainte, o expresie complexă constă din două părți:

• Variabilele, care sunt marcate cu majuscule ale alfabetului latin;
• Semnele care denotă o funcție și conectează expresii simple între ele.

Cum de a face o expresie în limba de algebră a logicii? Pentru aceasta trebuie să faceți mai multe lucruri:

• pentru a împărți întreaga propoziție în expresii simple;
• desemnați aceste elemente cu litere;
• a face distincția între expresiile simple;
• scrie expresia rezultată folosind simboluri speciale ale algebrului logicii.

Să luăm în considerare un exemplu simplu: (Z * F = 5 sau Z * F = 4) Și (Z * F nu este egal cu 5 sau Z * F nu este egal cu 4). În loc de variabile, înlocuiți 2. Apoi vom obține expresia (4 = 5 sau 4 = 4) și (4 nu este 5 sau 4 nu este 4). După operațiile efectuate, trebuie să selectăm expresiile și relațiile dintre ele, ar trebui să fie după cum urmează: (Z sau F) și (nu Z sau nu F). După aceasta, trebuie să convertim această înregistrare, înlocuind sensul afirmațiilor. Dacă expresia este corectă, atunci trebuie să înlocuiți 1, altfel - 0. Obținem: G = 1 și 1. După calculele necesare, obținem rezultatul: G = 1, adică expresia complexă este adevărată.

legii

Acum vă sugerăm să luați în considerare legile logicii șireguli pentru conversia expresiilor logice. Este important să menționăm că orice expresie logică poate fi transformată într-o altă expresie logică prin legile logicii. Acum vom analiza detaliat toate cele zece reguli.

Primul din lista noastră este "legea dublei negări". Aceasta este expresia "nu (nu A)" va fi egală cu expresia "A".

Legea comunicativă este, de asemenea, în matematică, este ușor de amintit. A + B = B + A, A * B = B * A.

Legea asocierii - (D + E) + F = (D + F) + E, aceeași lege se aplică înmulțirii logice.

Legea distributivă este o deschidere elementară a parantezelor. Exemplu: (A + B) * C = (A * C) + (B * C).

Legea lui De Morgan: nu (A + B) = notA * notB, nu (A * B) = notA + notB, AnimationB = notA + B, nu (AnimationB) = A * neB.

Idempotency: X + X = X sau C * C = C.

Eliminarea constantelor: X + 1 = 1, X + 0 = X; X * 1 = X, X * 0 = 0.

Apoi distingem legea contradicției, urmând-o, putem afirma următoarea egalitate: B * nu B = 0.

În logică există, de asemenea, o lege de absorbție, care în practică arată astfel: C + (C * D) = C sau C * (C + D) = C.

De asemenea, este important ca pentru transformarea expresiilor logice să se țină cont de legea excluderii: (C * E) + (nu C * E) = E sau (C + E) * (nu C + E) = E.

Dacă vă examinați și vă amintiți totul în detaliuprezentate în această secțiune a legilor, atunci problemele cu transformarea nu vor apărea niciodată. La fel de important este și ordinea execuției funcțiilor. Acordați mai multă atenție la acest punct, distribuția corectă a ordinii funcțiilor este cheia soluției corecte a problemei.

Reguli și legi ale transformării și simplificării, ordinea de executare a acțiunilor cu exemple

Legile logice și regulile de transformareexpresiile logice sunt foarte ușor de reținut. Dacă vă îndoiți de veridicitatea a cel puțin una dintre ele, verificați-vă. Pentru a face acest lucru, trebuie să petreceți 10 minute din timpul dvs. și să compilați tabelele de adevăr pentru a obține un răspuns.

Acum ne propunem să luăm în considerare legile logice șireguli pentru conversia expresiilor logice pe exemple specifice. Acest lucru este necesar pentru a consolida în mod corespunzător cunoștințele. Acordați o atenție deosebită succesiunii acțiunilor.

Ne sunt date: C + (nu C * E). Este necesară simplificarea expresiei. Primul pas este să deschideți parantezele. Atunci vom obține expresia: (C + notC) * (C + E). Observăm imediat că adăugarea logică a două declarații opuse ne dă adevărul. Ce obținem ca rezultat: 1 * (C + E). Din nou, deschideți parantezele: (1 * C) + (1 + E). Acum încă o dată ne amintim legile și obținem răspunsul: C + E.

După cum ați văzut deja, totul este simplu. Pentru a rezolva astfel de probleme, este necesar să ne amintim legile care au fost enumerate în ultima secțiune. Propunem să continuăm soluționarea problemelor logice, deoarece această sarcină este deja puțin mai complicată decât cea anterioară.

Rezolvarea problemelor

Ne-am familiarizat cu elementele de bază ale științei sub numele"Logica", transformarea expresiilor logice, am luat în considerare pe scurt legile enumerate. Cele mai complexe sarcini cu crearea de expresii logice sunt sarcini. Este important de remarcat că acestea pot fi rezolvate prin raționament, convertirea unei expresii sau prin utilizarea unei metode tabulare. Vă sugerăm să luați în considerare unul dintre ele în detaliu.

Au fost trei băieți (Cyril, Anton și Kostya)o cameră. Dintr-o data, o mama din bucatarie aude sunetul unei pahare sparte. Am fugit la fiii mei și am întrebat: "Cine a făcut asta?" Răspunsul a fost: Cyril a spus că paharul nu a fost rupt de Kostya, ci de Anton; Anton a spus că era Kostya, nu Cyril; Kostya susține că Anton nu este vinovatul. Știm că unul dintre băieți ia spus mamei o minciună. Trebuie să aflăm cine a spart paharul.

Dacă să argumentăm logic, răspunsurile lui Cyril și al luiAnton se contrazic unul pe altul, la fel ca Cyril de la Bones. Prin urmare, ele nu pot fi adevărate. Facem următoarea concluzie - Anton și Kostya au spus adevărul, iar Cyril este vinovatul cărnii sparte. Aceasta a fost metoda de reflecție utilizată. Acum ne vom uita la soluția aceleiași probleme, numai cu ajutorul metodei de transformare a expresiei. În primul rând, introducem abrevieri:

• KR - paharul este rupt de Cyril;
• A - paharul este rupt de Anton;
• K este vinovatul lui Kostya.

Răspunsurile băieților:

• Cyril - neK, A;
• Anton - non-RK, K;
• Kostya nu este.

Propunem să formulăm o expresie dacă Kostyaa mințit și Cyril și Anton au spus adevărul: neK * A = 1 și K * nKR = 1 și A = 1. Transformând expresia, obținem o contradicție: 0 = 1. Presupunerea noastră este incorectă, merită verificată alte ipoteze.

Dacă presupunem că Cyril a mințit și AntonKostya a spus mama ei adevărul, atunci următoarea expresie: K * Nea = 1 și k = 1 * Necro și Nea = 1. Simplificarea expresiei ne KR * * Nea HEK = 1. Acest lucru sugerează că ipoteza noastră a fost corectă, într-adevăr, Cyril a rupt o ceașcă și a mințit mama.

Metoda tabelară de soluție

Legile considerate de logică și transformareexpresii logice, ne-au ajutat cu siguranță să facem față sarcinii, care este prezentată în secțiunea anterioară. Acum vă sugerăm să luați în considerare metoda tabelului de rezolvare a problemei următoare.

Dmitry, Anatoly și Lyudmila sunt fanii luimail, știm că toată lumea trăiește în diferite părți ale lumii și are hobby-uri diferite. Determinați cine trăiește în ce oraș și ce este dependent. Se cunosc următoarele fapte:

• Dmitri nu fusese niciodată la Paris, iar Ludmila era la Roma;
• cineva care trăiește în Paris nu-i plac filmele;
• o persoană care locuiește în Roma, este angajată în voce;
• Lyudmila este dezgustat de balet.

Pentru a rezolva problema, trebuie să compilați o masă mică.

Mai mult decât atât, este necesară o atenție maximă. Tot ceea ce citiți în această condiție ar trebui să se reflecte în acest tabel. Pe măsură ce umplutura devine clară, următoarele vor deveni clare:

• Dmitri trăiește în Roma și este implicat în voce;
• Anatoly locuiește în Paris și adesea participă la balet;
• Ludmila este un mare fan al cinematografiei, care locuiește în SUA.

Plătiți din nou atenția asupra faptului că expresia adevărată este marcată cu numărul 1, iar cea falsă este 0. Când completați tabelul cu aceste simboluri, veți găsi rapid răspunsul la întrebarea care vă interesează.

Mikroskhematika

Exemple de conversie a expresiilor logice,pe care le-am considerat, sunt destul de complicate la prima vedere. Pe biletele examenului de stat unificat, condiția poate fi dată sub forma unui microcircuit.

Este important să știm că toate dispozitivele digitale se bazează pe elemente logice, adică anumite dispozitive care realizează o singură funcție logică.

Am vorbit deja despre o astfel de funcție ca o conjuncție(multiplicare logică). Este de obicei indicat de simbolul &. Această funcție este necesară pentru corelarea mai multor valori. În imagine veți vedea schema de multiplicare logică.

Funcția de disjuncție este necesară pentru implementarea disjuncției unor valori de intrare. Atunci când scrieți o expresie, această funcție este de obicei indicată de simbolul Ú. Imaginea arată schema.

Funcția de inversiune servește drept convertorul unei expresii la contrariul. În figură, vedeți cum arată schema "nu".

Un exemplu de simplificare a formulei # 1

Regulile considerate pentru transformarea logicăexpresiile trebuie consolidate în practică. În urmărirea acestui scop, propunem să rezolvăm în mod independent două exemple de complexitate medie și să le comparăm cu rezultatele din această secțiune a articolului.

Dacă nu ați memorat încă formulele pentru conversia expresiilor logice, vă puteți face un mic "memento". Veți vedea că în curând nu o veți urmări.

Exemplu: (X + T) * (notX + T) * (M + notT). Nu scrieți orbește, încercați să rezolvați singur exemplul.

În timpul simplificării obținem următoarea notație: T * (M + neT) = (T * M) + (T * neT) = (T * neM) + 0 = M.

După cum puteți vedea, dintr-o lungă și greoaieexpresia complexă avem un scurt T * M. Dacă nu ați reușit să rezolvați singur acest exemplu, reveniți la punctul în care am considerat transformarea expresiilor logice, a sarcinilor.

Un exemplu de simplificare a formulei # 2

În această secțiune vă sugerăm să simplificațiexpresia (E + H) * (E + K). Să analizăm soluția pas cu pas. Mai întâi de toate, trebuie să deschidem brațele, să ne amintim cursul matematicii inițiale. Ca rezultat, obținem următoarea expresie: E * E + E * K + H * E + H * K. Mai mult, observăm că această expresie este o parte din E * E, amintiți-vă idempotența legea și să transforme intrare: E + E * K * N * E * N + K. Etapa următoare transformare a E + E * Prin utilizarea bracketing E variabilă și proprietate: A + 1 = 1. Obținem expresia: E + H * E + H * K. Procedăm în mod similar cu ultimul punct și îl scoatem din parantezele E. Ca rezultat, primim răspunsul: E + H * K.

Fiți atenți la faptul că sarcinile par complicate doar la prima vedere. Pentru a le "da click pe semințe", trebuie doar să înveți legile de bază ale logicii.