Meniul
AcasăTelefon

Construiți un circuit și un tabel de adevăr. Forma normală disjunctivă perfectă

Funcția logică este o funcție în care variabilele iau doar două valori: una logică sau zero logic. Adevărul sau falsitatea propozițiilor complexe este o funcție a adevărului sau falsitatea celor simple. Această funcție se numește funcție de judecată booleană f (a, b).

Orice funcție logică poate fi specificată folosind un tabel de adevăr, pe partea stângă a căruia este scris un set de argumente, iar în partea dreaptă - valorile corespunzătoare ale funcției logice.

La construirea unui tabel de adevăr, este necesar să se țină cont de ordinea în care sunt efectuate operațiile logice. Operațiile într-o expresie logică se efectuează de la stânga la dreapta, ținând cont de paranteze, în următoarea ordine:

  • 1. inversiune;
  • 2. conjuncție;
  • 3. disjuncție;
  • 4. implicare și echivalență.

Pentru a schimba ordinea specificată a operațiilor logice, se folosesc paranteze.

Se propune urmatorul algoritm de construcție a tabelului de adevăr.

  • 1. Definiți numărul de seturi de variabile de intrare- toate combinațiile posibile de valori ale variabilelor incluse în expresii, conform formulei: Q=2 n, unde n este numărul de variabile de intrare. Acesta determină numărul de rânduri din tabel.
  • 2. Introduceți toate seturile de variabile de intrare în tabel.
  • 3. Determinați numărul de operații logice și succesiunea executării acestora.
  • 4. Completați coloanele cu rezultatele efectuării operațiilor logice în secvența indicată.

Pentru a nu repeta sau pierde nicio combinație posibilă de valori ale variabilelor de intrare, ar trebui să utilizați una dintre metodele sugerate mai jos pentru a completa tabelul.

Metoda 1. Fiecare set de valori ale variabilelor sursă este un cod numeric în sistemul de numere binar, iar numărul de cifre ale numărului este egal cu numărul de variabile de intrare. Primul set este numărul 0. Adăugând 1 la numărul curent de fiecare dată, obținem următorul set. Ultimul set este valoarea maximă a numărului binar pentru o lungime de cod dată.

De exemplu, pentru o funcție de trei variabile, succesiunea de mulțimi constă din numere:

Metoda 2. Pentru o funcție a trei variabile, secvența de date poate fi obținută după cum urmează:

  • a) împărțiți coloana de valori a primei variabile în jumătate și completați jumătatea superioară cu zerouri, jumătatea inferioară cu unu;
  • b) în coloana următoare pentru a doua variabilă, împărțiți din nou jumătatea în jumătate și completați-o cu grupuri de zerouri și unu; umpleți cealaltă jumătate în același mod;
  • c) faceți acest lucru până când grupurile de zerouri și unu sunt formate dintr-un caracter.

Metoda 3. Utilizați tabelul de adevăr cunoscut pentru cele două argumente. Când adăugați un al treilea argument, scrieți mai întâi primele 4 rânduri ale tabelului, combinându-le cu valoarea celui de-al treilea argument egală cu 0, apoi scrieți din nou aceleași 4 rânduri, dar acum cu valoarea celui de-al treilea argument egală cu 1 Ca rezultat, tabelul pentru trei argumente va fi de 8 rânduri:

De exemplu, să construim un tabel de adevăr pentru o funcție logică:

Numărul de variabile de intrare într-o expresie dată este trei (A,B,C). Aceasta înseamnă că numărul de seturi de intrare Q=2 3 =8 .

Coloanele tabelului de adevăr corespund valorilor expresiilor originale A,B,C, rezultate intermediare și ( B V C), precum și valoarea finală dorită a unei expresii aritmetice complexe:

  • 0 0 0 1 0 0
  • 0 0 1 1 1 1
  • 0 1 0 1 1 1
  • 0 1 1 1 1 1
  • 1 0 0 0 0 0
  • 1 0 1 0 1 0
  • 1 1 0 0 1 0
  • 1 1 1 0 1 0
  • 7.4. Funcțiile logice și transformările lor. Legile logicii

Pentru operațiile de conjuncție, disjuncție și inversare sunt definite legile algebrei booleene, permițând transformări identice (echivalente) ale expresiilor logice.

Legile logicii

  • 1. ¬¬A
  • 2. A&B
  • 3.AVB
  • 4. A&(B&C)
  • 5.AV(BVC)
  • 6. A&(BVC)
  • 7.AV(B&C)
  • 8. A&A
  • 9.AVA
  • 10. AV¬A
  • 11. A&¬A
  • 12. A&I
  • 13. AVI
  • 14. A&L
  • 15. AVL
  • 16.¬(A&B)
  • 17.¬(AVB)
  • 18. A => B

Pe baza legilor, este posibilă simplificarea expresiilor logice complexe. Acest proces de înlocuire a unei funcții logice complexe cu una mai simplă, dar echivalentă se numește minimizarea funcției.

Exemplul 1. Simplificați expresiile astfel încât formulele rezultate să nu conțină negația enunțurilor complexe.

Soluţie

Exemplul 2. Minimizați funcția

Pentru simplificarea expresiei s-au folosit formulele de absorbtie si aderenta.

Exemplul 3. Găsiți negația următoarei afirmații: „Dacă lecția este interesantă, atunci niciunul dintre elevi (Misha, Vika, Sveta) nu se va uita pe fereastră”.

Soluţie

Să notăm afirmațiile:

Y- „Lecția este interesantă”;

M- „Misha se uită pe fereastră”;

B- „Vika se uită pe fereastră”;

C- „Sveta se uită pe fereastră”.

La simplificarea expresiei s-a folosit formula de înlocuire a operațiilor și legea lui De Morgan.

Exemplul 4. Determinați participantul la infracțiune pe baza a două premise: tabelul logic al computerului

  • 1) „Dacă Ivanov nu a participat sau Petrov a participat, atunci a participat Sidorov”;
  • 2) „Dacă Ivanov nu a participat, atunci Sidorov nu a participat.”

Soluţie

Să inventăm expresiile:

eu- „Ivanov a participat la crimă”;

P- „Petrov a participat la crimă”;

S- „Sidorov a participat la crimă”.

Să scriem premisele sub formă de formule:

Să verificăm rezultatul folosind tabelul de adevăr:


Răspuns: Ivanov a participat la crimă.

Construirea unei funcții logice din tabelul său de adevăr

Am învățat cum să creăm un tabel de adevăr pentru o funcție logică. Să încercăm să rezolvăm problema inversă.

Luați în considerare rândurile în care valoarea de adevăr a funcției Z este adevărată (Z=1). Funcția pentru acest tabel de adevăr poate fi scrisă după cum urmează: Z(X,Y) = (¬ X& ¬Y)V(X& ¬Y).

Fiecare linie în care funcția este adevărată (egale cu 1) corespunde unei paranteze reprezentând o conjuncție de argumente, iar dacă valoarea argumentului este O, atunci o luăm cu negație. Toate suporturile sunt conectate între ele printr-o operație de disjuncție. Formula rezultată poate fi simplificată prin aplicarea legilor logicii:

Z(X,Y)<=>((¬X& ¬Y) VX)&((¬X&Y)V ¬Y)<=>(XV(¬X& ¬Y)) &(¬YV(¬X&¬Y))<=>((XV¬X)&(XV ¬Y))&((Y¬V ¬X)&(¬YV ¬Y))<=>(1&(XV ¬Y))&((¬YV ¬X)& ¬Y)<=>(XV ¬Y)&((¬YV ¬X)& ¬Y).

Verificați formula rezultată: creați un tabel de adevăr pentru funcția Z(X,Y).

Scrieți regulile pentru construirea unei funcții logice folosind tabelul de adevăr:

  • 1. Selectați acele rânduri din tabelul de adevăr în care valoarea funcției este egală cu 1.
  • 2. Notați formula necesară sub forma unei disjuncții a mai multor elemente logice. Numărul acestor elemente este egal cu numărul de linii selectate.
  • 3. Scrieți fiecare element logic din această disjuncție ca o conjuncție de argumente ale funcției.
  • 4. Dacă valoarea oricărui argument al funcției din rândul corespunzător al tabelului este 0, atunci luăm acest argument cu o negație.

Învățăm să compunem expresii logice din enunțuri, definim conceptul de „tabel de adevăr”, studiem succesiunea de acțiuni pentru construirea tabelelor de adevăr, învățăm să găsim sensul expresiilor logice prin construirea tabelelor de adevăr.

Obiectivele lecției:

  1. Educational:
    1. Învață să formezi expresii logice din enunțuri
    2. Introduceți conceptul de „tabel de adevăr”
    3. Studiați succesiunea acțiunilor pentru construirea tabelelor de adevăr
    4. Învață să găsești sensul expresiilor logice construind tabele de adevăr
    5. Introduceți conceptul de echivalență a expresiilor logice
    6. Învață să demonstrezi echivalența expresiilor logice folosind tabele de adevăr
    7. Consolidați abilitățile de a găsi valorile expresiilor logice prin construirea de tabele de adevăr
  2. Educational:
    1. Dezvoltați gândirea logică
    2. Dezvoltați atenția
    3. Dezvoltați memoria
    4. Dezvoltați discursul elevilor
  3. Educational:
    1. Dezvoltați capacitatea de a asculta profesorii și colegii de clasă
    2. Cultivați acuratețea în păstrarea notebook-ului
    3. Cultivați disciplina

În timpul orelor

Organizarea timpului

Buna baieti. Continuăm să studiem elementele de bază ale logicii, iar subiectul lecției noastre de astăzi este „Alcătuirea expresiilor logice. Tabelele de adevăr.” După ce ați studiat acest subiect, veți afla cum sunt făcute formele logice din enunțuri și cum să le determinați adevărul prin compilarea tabelelor de adevăr.

Verificarea temelor

Notați pe tablă soluțiile la problemele legate de teme
Toți ceilalți, deschideți caietele, voi trece și voi verifica cum v-ați făcut temele.
Să facem din nou operațiile logice
În ce caz va fi adevărată afirmația compusă ca rezultat al operației de înmulțire logică?
O afirmație compusă formată ca rezultat al operației de înmulțire logică este adevărată dacă și numai dacă toate afirmațiile simple incluse în ea sunt adevărate.
În ce caz afirmația compusă va fi falsă ca urmare a operației de adunare logică?
O afirmație compusă formată ca urmare a operației de adunare logică este falsă dacă toate afirmațiile simple incluse în ea sunt false.
Cum afectează inversiunea o declarație?
Inversarea face ca o afirmație adevărată să fie falsă și, dimpotrivă, o afirmație falsă adevărată.
Ce poți spune despre implicație?
Consecința logică (implicația) se formează prin combinarea a două enunțuri într-unul singur folosind figura de stil „dacă..., atunci...”.
Desemnat A-> ÎN
O afirmație compusă formată folosind operația de consecință logică (implicație) este falsă dacă și numai dacă dintr-o premisă adevărată (prima afirmație) rezultă o concluzie falsă (a doua afirmație).
Ce puteți spune despre operația de echivalență logică?
Egalitatea logică (echivalența) se formează prin combinarea a două enunțuri într-una singură folosind figura de stil „... dacă și numai dacă...”, „... în acel și numai în acel caz...”
O afirmație compusă formată prin operația logică de echivalență este adevărată dacă și numai dacă ambele afirmații sunt simultan fie false, fie adevărate.

Explicarea noului material

Bine, am revizuit materialul acoperit, să trecem la un subiect nou.

În ultima lecție, am găsit valoarea unei instrucțiuni compuse prin înlocuirea valorilor originale ale variabilelor logice primite. Și astăzi vom învăța că este posibil să construim un tabel de adevăr care să determine adevărul sau falsitatea unei expresii logice pentru toate combinațiile posibile ale valorilor inițiale ale afirmațiilor simple (variabile logice) și că putem determina valorile a variabilelor logice inițiale, știind de ce rezultat avem nevoie.

Să ne uităm din nou la exemplul nostru din ultima lecție.

și construiți un tabel de adevăr pentru această afirmație compusă

La construirea tabelelor de adevăr, există o anumită secvență de acțiuni. Să-l notăm

  1. Este necesar să se determine numărul de rânduri din tabelul de adevăr.
  • număr de linii = 2 n, unde n este numărul de variabile logice
  • Este necesar să se determine numărul de coloane din tabelul de adevăr, care este egal cu numărul de variabile logice plus numărul de operații logice.
  • Este necesar să construiți un tabel de adevăr cu numărul specificat de rânduri și coloane, introduceți numele coloanelor din tabel în conformitate cu succesiunea operațiilor logice, ținând cont de paranteze și priorități;
  • Populați coloanele variabile de intrare cu seturi de valori
  • Completați tabelul de adevăr coloană cu coloană, efectuând operații logice în conformitate cu succesiunea stabilită.

    • Înregistrate. Construirea unui tabel de adevăr
    Ce facem mai întâi?
    Determinați numărul de coloane dintr-un tabel
    Cum facem asta?
    Numărăm numărul de variabile. În cazul nostru, funcția logică contine 2 variabile
    Care?
    A și B
    Deci câte rânduri vor fi în tabel?
    Numărul de rânduri din tabelul de adevăr trebuie să fie 4.
    Ce se întâmplă dacă există 3 variabile?
    Număr de linii = 2³ = 8
    Dreapta. Ce facem mai departe?
    Determinăm numărul de coloane = numărul de variabile logice plus numărul de operații logice.
    Cât va fi în cazul nostru?
    În cazul nostru, numărul de variabile este de două, iar numărul de operații logice este de cinci, adică numărul de coloane din tabelul de adevăr este șapte.
    Amenda. Mai departe?
    Construim un tabel cu numărul specificat de rânduri și coloane, desemnăm coloanele și introducem în tabel seturi posibile de valori ale variabilelor logice originale și completăm tabelul de adevăr pe coloane.
    Ce operație vom efectua mai întâi? Doar fii atent la paranteze și priorități
    Puteți face mai întâi negația logică sau puteți găsi mai întâi valoarea din prima paranteză, apoi inversul și valoarea din a doua paranteză, apoi valoarea dintre acele paranteze

    ┐Аv┐В

    (AvB)&(┐Av┐B)

    Acum putem determina valoarea unei funcții logice pentru orice set de valori ale variabilelor logice
    Acum notați elementul „Expresii logice echivalente”.
    Sunt numite expresii logice pentru care ultimele coloane ale tabelelor de adevăr coincid echivalent. Pentru a desemna expresii logice echivalente, se folosește semnul „=”,
    Să demonstrăm că expresiile logice ┐ A& ┐ B și AvB sunt echivalente. Să construim mai întâi un tabel de adevăr pentru o expresie logică


     Câte coloane vor fi în tabel? 5
    Ce operație vom efectua mai întâi? Inversiunea A, inversiunea B

    ┐A&┐B

    Acum să construim un tabel de adevăr pentru expresia logică AvB
    Câte rânduri vor fi în tabel? 4
    Câte coloane vor fi în tabel? 4

    Cu toții înțelegem că, dacă trebuie să găsim o negație pentru întreaga expresie, atunci prioritatea, în cazul nostru, aparține disjuncției. Prin urmare, efectuăm mai întâi disjuncția și apoi inversiunea. În plus, putem rescrie expresia noastră booleană AvB. Deoarece trebuie să găsim negația întregii expresii, și nu variabile individuale, apoi inversarea poate fi scoasă din paranteze ┐(AvB) și știm că mai întâi găsim valoarea între paranteze

    ┐(AvB)

    Am construit mese. Acum să comparăm valorile din ultimele coloane ale tabelelor de adevăr, deoarece Ultimele coloane sunt cele care rezultă. Ele coincid, așadar, expresiile logice sunt echivalente și putem pune semnul „=” între ele

    Rezolvarea problemelor

    1.

    Câte variabile conține această formulă? 3
    Câte rânduri și coloane vor fi în tabel? 8 și 8
    Care va fi succesiunea operațiilor din exemplul nostru? (inversiunea, operațiunile între paranteze, operarea în afara parantezelor)

    Bv┐B (1)

    (1) =>┐C

    Av(Bv┐B=>┐C)

    2. Folosind tabele de adevăr, demonstrați echivalența următoarelor expresii logice:

    (A → B) ȘI (Av┐B)

    Ce concluzie tragem? Aceste expresii logice nu sunt echivalente

    Teme pentru acasă

    Demonstrați folosind tabele de adevăr că expresiile logice

    ┐A v ┐B și A&B sunt echivalente

    Explicația materialului nou (continuare)

    Am folosit conceptul de „tabel de adevăr” de mai multe lecții la rând și ce este un tabel de adevăr, Cum crezi?
    Un tabel de adevăr este un tabel care stabilește o corespondență între posibile seturi de valori ale variabilelor logice și valorile funcției.
    Cum ți-ai făcut temele, care a fost concluzia?
    Expresiile sunt echivalente
    Amintiți-vă, în lecția anterioară am făcut o formulă dintr-o declarație compusă, înlocuind afirmațiile simple 2*2=4 și 2*2=5 cu variabilele A și B
    Acum să învățăm cum să formăm expresii logice din declarații

    Notează sarcina

    Scrieți următoarele afirmații sub forma unei formule logice:

    1) Dacă Ivanov este sănătos și bogat, atunci este sănătos

    Să analizăm afirmația. Identificarea afirmațiilor simple

    A – Ivanov este sănătos
    B – Ivanov este bogat

    Bine, atunci cum ar arăta formula? Doar nu uitați, pentru a nu pierde sensul enunțului, puneți paranteze în formulă

    2) Un număr este prim dacă este divizibil numai cu 1 și cu el însuși

    A - numărul este divizibil doar cu 1
    B - numărul este divizibil numai cu el însuși
    C - numărul este prim

    3) Dacă un număr este divizibil cu 4, el este divizibil cu 2

    A - divizibil cu 4
    B - divizibil cu 2

    4) Un număr arbitrar este fie divizibil cu 2, fie divizibil cu 3

    A - divizibil cu 2
    B - divizibil cu 3

    5) Un sportiv este supus descalificării dacă se comportă incorect față de un adversar sau de un judecător și dacă a luat „doping”.

    A - sportivul este supus descalificării
    B - se comportă incorect față de un adversar
    C - se comporta incorect fata de judecator
    D - a luat „doping”.

    Rezolvarea problemelor

    1. Construiți un tabel de adevăr pentru formula

    ((p&q)→ (p→ r)) v p

    Să explicăm câte rânduri și coloane vor fi în tabel? (8 și 7) Care va fi succesiunea operațiilor și de ce?

    (p&q)→ (p→ r)

    ((p&q)→ (p→ r)) v p

    Ne-am uitat la ultima coloană și am ajuns la concluzia că pentru orice set de parametri de intrare formula capătă o valoare adevărată; o astfel de formulă se numește tautologie. Să notăm definiția:

    O formulă se numește lege a logicii, sau tautologie, dacă ia valoarea identică „adevărată” pentru orice set de valori ale variabilelor incluse în această formulă.
    Și dacă toate valorile sunt false, ce credeți că se poate spune despre o astfel de formulă?
    Putem spune că formula este imposibilă

    2. Scrieți următoarele afirmații sub forma unei formule logice:

    Administrația portului maritim a emis următorul ordin:

    1. Dacă căpitanul unei nave primește instrucțiuni speciale, el trebuie să părăsească portul pe nava sa
    2. Dacă comandantul nu primește instrucțiuni speciale, el nu trebuie să părăsească portul, altfel va pierde de acum înainte accesul în acel port.
    3. Căpitanul fie este privat de acces în acest port, fie nu primește instrucțiuni speciale

    Identificăm afirmații simple și creăm formule

    • A - căpitanul primește instrucțiuni speciale
    • B - părăsește portul
    • C - lipsit de acces în port
    1. ┐A→(┐B v C)
    2. C v ┐A

    3. Notați enunțul compus „(2*2=4 și 3*3 = 9) sau (2*2≠4 și 3*3≠9)” sub forma unei expresii logice. Construiți un tabel de adevăr.

    A=(2*2=4) B=(3*3 = 9)

    (A&B) v (┐A&┐B)

    ┐A&┐B

    (A&B) v (┐A&┐B)

    Teme pentru acasă

    Alegeți o afirmație compusă care are același tabel de adevăr ca not (nu A și nu (B și C)).

    1. A&B sau C&A;
    2. (A sau B) și (A sau C);
    3. A și (B sau C);
    4. A sau (nu B sau C).

    Algebra logicii

    Algebra logicii

    Algebra logicii(Engleză) algebra logicii) este una dintre principalele ramuri ale logicii matematice, în care metodele algebrice sunt utilizate în transformările logice.

    Fondatorul algebrei logicii este matematicianul și logicianul englez J. Boole (1815-1864), care și-a bazat învățătura logică pe analogia dintre algebră și logică. El a notat orice afirmație folosind simbolurile limbajului pe care l-a dezvoltat și a primit „ecuații”, a căror adevăr sau falsitate putea fi dovedită pe baza anumitor legi logice, precum legile comutativității, distributivității, asociativității etc.

    Modern algebra logicii este o ramură a logicii matematice și studiază operațiile logice asupra enunțurilor din punctul de vedere al valorii lor de adevăr (adevărat, fals). Afirmațiile pot fi adevărate, false sau pot conține adevăr și fals în proporții diferite.

    Declarație logică este orice propoziție declarativă al cărei conținut poate fi declarat fără echivoc ca fiind adevărat sau fals.

    De exemplu, „de 3 ori 3 este egal cu 9”, „Arhangelsk este la nord de Vologda” sunt afirmații adevărate, dar „Cinci este mai puțin de trei”, „Marte este o stea” sunt false.

    Evident, nu orice propoziție poate fi o afirmație logică, deoarece nu are întotdeauna sens să vorbim despre falsitatea sau adevărul ei. De exemplu, afirmația „Informatica este un subiect interesant” este vagă și necesită informații suplimentare, iar afirmația „Pentru un elev de clasa a 10-A Ivanov A.A., informatica este un subiect interesant”, în funcție de interesele lui Ivanov A.A. , poate lua semnificația „adevărat” sau „minciună”.

    Cu exceptia algebră propozițională cu două valori, în care sunt acceptate doar două valori - „adevărat” și „fals”, există algebră propozițională multivalorică.Într-o astfel de algebră, pe lângă valorile „adevărat” și „fals”, sunt folosite valori de adevăr precum „probabil”, „posibil”, „imposibil”, etc.

    În algebră, logica diferă simplu(elementar) declarații, desemnat prin litere latine (A, B, C, D, ...), și complex(compozit), alcătuit din mai multe simple folosind conjunctive logice, de exemplu, cum ar fi „nu”, „și”, „sau”, „dacă și numai atunci”, „dacă... atunci”. Adevărul sau falsitatea afirmațiilor complexe obținute în acest mod este determinată de sensul afirmațiilor simple.

    Să o notăm ca A afirmația „Algebra logicii este aplicată cu succes în teoria circuitelor electrice” și prin ÎN— „Algebra logică este folosită în sinteza circuitelor relee.”

    Apoi afirmația compusă „Algebra logicii este aplicată cu succes în teoria circuitelor electrice și în sinteza circuitelor relee” poate fi scrisă pe scurt ca A și B; aici „și” este un conjunctiv logic. Este evident că din enunţuri elementare A și B sunt adevărate, atunci afirmația compusă este adevărată A și B.

    Fiecare conjunctiv logic este considerat ca o operație pe instrucțiuni logice și are propriul nume și denumire.

    Există doar două valori logice: adevarat adevarat)Și fals (FALSE). Aceasta corespunde reprezentării digitale − 1 Și 0 . Rezultatele fiecărei operații logice pot fi scrise sub forma unui tabel. Astfel de tabele se numesc tabele de adevăr.

    Operații de bază ale logicii algebrei

    1. Negație logică, inversare(lat. inversiune- inversarea) este o operație logică, în urma căreia se obține o nouă instrucțiune dintr-o instrucțiune dată (de exemplu, A) nu A), Care e numit negarea afirmației inițiale, este indicat simbolic printr-o bară ($A↖(-)$) sau prin convenții precum ¬, „nu”, și citește: „nu A”, „A este fals”, „nu este adevărat că A”, „negarea lui A”. De exemplu, „Marte este o planetă a sistemului solar” (afirmația A); „Marte nu este o planetă în sistemul solar” ($A↖(-)$); afirmația „10 este un număr prim” (enunțul B) este falsă; Afirmația „10 nu este un număr prim” (afirmația B) este adevărată.

    Se numește o operație utilizată pe o singură cantitate unar. Tabelul de valori pentru această operație arată ca

    Enunțul $A↖(-)$ este fals când A este adevărat și adevărat când A este fals.

    Geometric, negația poate fi reprezentată astfel: dacă A este o anumită mulțime de puncte, atunci $A↖(-)$ este complementul mulțimii A, adică toate punctele care nu aparțin mulțimii A.

    2.Conjuncție(lat. conjunctio- conexiune) - înmulțire logică, o operație care necesită cel puțin două mărimi logice (operanzi) și conectează două sau mai multe instrucțiuni folosind un conjunctiv "Și"(De exemplu, „A și B”), care este notat simbolic prin semnul ∧ (A ∧ B) și spune: „A și B”. Următoarele semne sunt, de asemenea, folosite pentru a indica conjuncția: A ∙ B; A și B, A și B, iar uneori nu există nici un semn între afirmații: AB. Exemplu de înmulțire logică: „Acest triunghi este isoscel și dreptunghic”. O afirmație dată poate fi adevărată numai dacă ambele condiții sunt îndeplinite, altfel afirmația este falsă.

    A B A∧B
    1 0 0
    0 1 0
    0 0 0
    1 1 1

    Afirmație A ∧ ÎN adevărat numai dacă ambele afirmații sunt AȘi ÎN sunt adevărate.

    Geometric, conjuncția poate fi reprezentată astfel: dacă A, B A ∧ ÎN există o intersecție de mulțimi AȘi ÎN.

    3. Disjuncția(lat. disjuncție- împărțire) - adunare logică, o operație care conectează două sau mai multe declarații folosind un conjunctiv "sau"(De exemplu, "A sau B"), care este notat simbolic prin semnul ∨ (A∨ ÎN) si citeste: "A sau B". Următoarele semne sunt, de asemenea, folosite pentru a indica disjuncția: A + B; A sau B; A | B. Un exemplu de adunare logică: „Numărul x este divizibil cu 3 sau 5.” Această afirmație va fi adevărată dacă ambele condiții sau cel puțin una dintre condiții sunt îndeplinite.

    Tabelul de adevăr al operației are forma

    A B A ∨ B
    1 0 1
    0 1 1
    0 0 0
    1 1 1

    Afirmație A∨ ÎN este falsă numai atunci când ambele afirmații sunt AȘi ÎN fals.

    Geometric, adunarea logică poate fi reprezentată astfel: dacă A, B sunt niște seturi de puncte, atunci A ∨ ÎN este o uniune de seturi AȘi ÎN, adică o figură care combină atât un pătrat, cât și un cerc.

    4. Disjuncție strict separativă, adunare modulo doi- o operație logică care conectează două instrucțiuni folosind un conjunctiv "sau", folosit în sens exclusiv, care este notat simbolic prin semnele ∨ ∨ sau ⊕ ( A ∨ ∨ B, A ⊕ ÎN) și citește: "Ori a, ori b". Un exemplu de adunare modulo doi este afirmația „Acest triunghi este obtuz sau acut”. Afirmația este adevărată dacă oricare dintre condiții este îndeplinită.

    Tabelul de adevăr al operației are forma

    A ÎN A⊕ B
    1 0 1
    0 1 1
    0 0 0
    1 1 0

    Afirmația A ⊕ B este adevărată numai dacă enunțurile A și B au semnificații diferite.

    5. Implicare(lat. implicit- closely connect) - o operație logică care conectează două instrucțiuni folosind un conectiv "daca atunci"într-o declarație complexă, care este indicată simbolic prin semnul → ( A → ÎN) și citește: „dacă A, atunci B”, „A implică B”, „din A urmează B”, „A implică B”. Semnul ⊃ (A ⊃ B) este de asemenea folosit pentru a desemna implicația. Un exemplu de implicație: „Dacă patrulaterul rezultat este un pătrat, atunci un cerc poate fi descris în jurul lui.” Această operație conectează două expresii logice simple, dintre care prima este o condiție, iar a doua este o consecință. Rezultatul unei operații este fals numai atunci când premisa este adevărată și consecința este falsă. De exemplu, „Dacă 3 * 3 = 9 (A), atunci Soarele este o planetă (B)”, rezultatul implicației A → B este fals.

    Tabelul de adevăr al operației are forma

    A ÎN A→ÎN
    1 0 0
    0 1 1
    0 0 1
    1 1 1

    Pentru operația de implicare, este adevărată afirmația că orice poate decurge dintr-o minciună, dar numai adevărul poate decurge din adevăr.

    6. Echivalență, dublă implicație, echivalență(lat. aequalis- egală şi valentis- având forță) - o operație logică care permite din două afirmații AȘi ÎN obține o nouă expresie A ≡ B care scrie: "A este echivalent cu B". Următoarele semne sunt, de asemenea, folosite pentru a indica echivalența: ⇔, ∼. Această operație poate fi exprimată prin conjunctive „atunci și numai atunci”, „necesar și suficient”, „echivalent”. Un exemplu de echivalență este afirmația: „Un triunghi este dreptunghic dacă și numai dacă unul dintre unghiuri are 90 de grade.”

    Tabelul de adevăr al operației de echivalență are forma

    A ÎN A∼ ÎN
    1 0 0
    0 1 0
    0 0 1
    1 1 1

    Operația de echivalență este opusă adunării modulo doi și se evaluează la adevărat dacă și numai dacă valorile variabilelor sunt aceleași.

    Cunoscând semnificațiile afirmațiilor simple, este posibil să se determine semnificațiile enunțurilor complexe pe baza tabelelor de adevăr. Este important de știut că pentru a reprezenta orice funcție din algebra logicii sunt suficiente trei operații: conjuncție, disjuncție și negație.

    Prioritatea operațiilor logice este următoarea: negație ( "Nu") are cea mai mare prioritate, apoi conjuncția ( "Și"), după conjuncție - disjuncție ( "sau").

    Cu ajutorul variabilelor logice și al operațiilor logice, orice declarație logică poate fi formalizată, adică înlocuită cu o formulă logică. În acest caz, enunțurile elementare care formează un enunț compus pot fi absolut fără legătură în sens, dar acest lucru nu interferează cu determinarea adevărului sau falsității enunțului compus. De exemplu, afirmația „Dacă cinci este mai mare decât doi ( A), apoi marțea vine întotdeauna după luni ( ÎN)" - implicație A→ ÎN, iar rezultatul operației în acest caz este „adevărat”. În operațiile logice nu se ține cont de sensul enunțurilor, ci doar de adevărul sau falsitatea acestora.

    Luați în considerare, de exemplu, construcția unei declarații compuse din enunțuri AȘi ÎN, care ar fi fals dacă și numai dacă ambele afirmații sunt adevărate. În tabelul de adevăr pentru operația de adunare modulo doi găsim: 1 ⊕ 1 = 0. Și afirmația ar putea fi, de exemplu, astfel: „Această bilă este complet roșie sau complet albastră”. Prin urmare, dacă declarația A„Această minge este complet roșie” este un adevăr și o afirmație ÎN„Această minge este complet albastră” este adevărată, atunci afirmația compusă este falsă, deoarece mingea nu poate fi roșie și albastră în același timp.

    Exemple de rezolvare a problemelor

    Exemplul 1. Pentru valorile specificate ale lui X, determinați valoarea instrucțiunii logice ((X > 3) ∨ (X< 3)) → (X < 4) :

    1) X = 1; 2) X = 12; 3) X = 3.

    Soluţie. Secvența operațiilor este următoarea: mai întâi se efectuează operațiile de comparare între paranteze, apoi disjuncția și în sfârșit se realizează operația de implicare. Operația de disjuncție ∨ este falsă dacă și numai dacă ambii operanzi sunt falși. Tabelul de adevăr pentru implicație arată ca

    A B A → B
    1 0 0
    0 1 1
    0 0 1
    1 1 1

    De aici obținem:

    1) pentru X = 1:

    ((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

    2) pentru X = 12:

    ((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

    3) pentru X = 3:

    ((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

    Exemplul 2. Indicați setul de valori întregi ale lui X pentru care expresia ¬((X > 2) → (X > 5)) este adevărată.

    Soluţie. Operația de negație se aplică întregii expresii ((X > 2) → (X > 5)), prin urmare, când expresia ¬((X > 2) → (X > 5)) este adevărată, expresia ((X > 5) > 2) →(X > 5)) este falsă. Prin urmare, este necesar să se determine pentru ce valori ale lui X expresia ((X > 2) → (X > 5)) este falsă. Operația de implicare capătă valoarea „falsă” doar într-un caz: atunci când o minciună decurge din adevăr. Și acest lucru este valabil numai pentru X = 3; X = 4; X = 5.

    Exemplul 3. Pentru care dintre următoarele cuvinte este falsă afirmația ¬(prima literă este o vocală ∧ a treia literă o vocală) ⇔ un șir de 4 caractere? 1) assa; 2) kuku; 3) porumb; 4) eroare; 5) om puternic.

    Soluţie. Să luăm în considerare toate cuvintele propuse succesiv:

    1) pentru cuvântul assa obținem: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 - afirmația este adevărată;

    2) pentru cuvântul kuku obținem: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 - afirmația este adevărată;

    3) pentru cuvântul porumb obținem: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - afirmația este falsă;

    4) pentru cuvântul eroare obținem: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 - afirmația este adevărată;

    5) pentru cuvântul strongman obținem: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - afirmația este falsă.

    Expresii logice și transformarea lor

    Sub expresie logică trebuie înțeles ca o înregistrare care poate lua valoarea logică „adevărat” sau „fals”. Cu această definiție, printre expresiile logice este necesar să se distingă:

    • expresii care folosesc operații de comparare („mai mare decât”, „mai mic decât”, „egal cu”, „nu este egal cu”, etc.) și iau valori logice (de exemplu, expresia a > b, unde a = 5 și b = 7, este egal cu valoarea „fals”);
    • expresii logice directe asociate cu mărimi logice și operații logice (de exemplu, A ∨ B ∧ C, unde A = adevărat, B = fals și C = adevărat).

    Expresiile booleene pot include funcții, operații algebrice, operații de comparare și operații logice. În acest caz, prioritatea acțiunilor este următoarea:

    1. calculul dependențelor funcționale existente;
    2. efectuarea de operații algebrice (întâi înmulțirea și împărțirea, apoi scăderea și adunarea);
    3. efectuarea de operații de comparare (în ordine aleatorie);
    4. efectuarea de operatii logice (mai intai operatiile de negatie, apoi operatiile de inmultire logica, adunare logica, iar in sfarsit operatiile de implicare si echivalare).

    O expresie booleană poate folosi paranteze, care schimbă ordinea în care sunt efectuate operațiile.

    Exemplu. Găsiți sensul expresiei:

    $1 ≤ a ∨ A ∨ sin(π/a - π/b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B)$ pentru a = 2, b = 3, A = adevărat, B = fals.

    Soluţie. Ordinea de numărare a valorilor:

    1) b a + a b > a + b, după substituție obținem: 3 2 + 2 3 > 2 + 3, adică 17 > 2 + 3 = adevărat;

    2) A ∧ B = adevărat ∧ fals = fals.

    Prin urmare, expresia dintre paranteze este (b a + a b > a + b ∨ A ∧ B) = adevărat ∨ fals = adevărat;

    3) 1≤ a = 1 ≤ 2 = adevărat;

    4) sin(π/a - π/b)< 1 = sin(π/2 - π/3) < 1 = истина.

    După aceste calcule obținem în sfârșit: adevărat ∨ A ∧ adevărat ∧ ¬B ∧ ¬ adevărat.

    Acum trebuie efectuate operațiile de negație, apoi de înmulțire logică și de adunare:

    5) ¬B = ¬fals = adevărat; ¬adevărat = fals;

    6) A ∧ adevărat ∧ adevărat ∧ fals = adevărat ∧ adevărat ∧ adevărat ∧ fals = fals;

    7) adevărat ∨ fals = adevărat.

    Astfel, rezultatul unei expresii logice pentru valori date este „adevărat”.

    Notă. Având în vedere că expresia inițială este, în cele din urmă, suma a doi termeni, iar valoarea unuia dintre ei este 1 ≤ a = 1 ≤ 2 = adevărat, fără alte calcule putem spune că rezultatul pentru întreaga expresie este și „adevărat”. ”.

    Transformări identice ale expresiilor logice

    În algebra logicii sunt respectate legi de bază care permit transformări identice ale expresiilor logice.

    Lege Pentru ∨ Pentru ∧
    Călător A ∨ B = B ∨ A A ∧ B = B ∧ A
    Conjunctiv A ∨ (B ∨ C) = (B ∨ A) ∨ C A ∧ (B ∧ C) = (A ∧ B) ∧ C
    Distributie A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
    regulile lui De Morgan $(A ∨ B)↖(-)$ = $A↖(-) ∧ B↖(-)$ $(A ∧ B)↖(-)$ = $A↖(-) ∨ B↖(-)$
    Idempotenta A ∨ A = A A ∧ A = A
    Preluări A ∨ A ∧ B = A A ∧ (A ∨ B) = A
    Legătura (A ∧ B) ∨ (A↖(-) ∧ B) = B (A ∨ B) ∧ (A↖(-) ∨ B) = B
    Operarea unei variabile cu inversarea acesteia $A ∨ A↖(-)$ = 1 $A ∧ A↖(-)$ = 0
    Operare cu constante A ∨ 0 = A
    A ∨ 1 = 1    		 A ∧ 1 = A
    A ∧ 0 = 0
    Dublu negativ $A↖(=)$ = A

    Dovezile acestor afirmații se fac pe baza construcției de tabele de adevăr pentru înregistrările corespunzătoare.

    Transformările echivalente ale formulelor logice au același scop ca și transformările formulelor din algebra obișnuită. Acestea servesc la simplificarea formulelor sau la reducerea lor la o anumită formă, folosind legile de bază ale algebrei logice. Sub simplificarea formulei, care nu conține operațiile de implicare și echivalență, este înțeles ca o transformare echivalentă care duce la o formulă care conține fie un număr mai mic de operații, fie un număr mai mic de variabile față de cea inițială.

    Unele transformări ale formulelor logice sunt similare transformărilor formulelor din algebra obișnuită (luând factorul comun din paranteze, folosind legi comutative și combinaționale etc.), în timp ce alte transformări se bazează pe proprietăți pe care operațiile algebrei obișnuite nu le au ( folosind legea distributivă pentru conjuncție, legile absorbției, lipirii, de Morgan etc.).

    Să ne uităm la câteva exemple de tehnici și metode utilizate pentru a simplifica formulele logice:

    1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

    Pentru a transforma aici, puteți aplica legea idempotei, legea distributivă; operarea unei variabile cu inversare și operarea cu constantă.

    2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1.

    Aici, pentru simplitate, se aplică legea absorbției.

    3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

    La transformare se aplică regula de Morgan, operația unei variabile cu inversarea acesteia și operația cu o constantă.

    Exemple de rezolvare a problemelor

    Exemplul 1. Găsiți o expresie logică echivalentă cu expresia A ∧ ¬(¬B ∨ C) .

    Soluţie. Aplicam regula lui de Morgan pentru B si C: ¬(¬B ∨ C) = B ∧ ¬C.

    Obținem o expresie echivalentă cu cea inițială: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

    Răspuns: A ∧ B ∧ ¬C.

    Exemplul 2. Indicați valoarea variabilelor logice A, B, C, pentru care valoarea expresiei logice (A ∨ B) → (B ∨ ¬C ∨ B) este falsă.

    Soluţie. Operația de implicare este falsă numai dacă dintr-o premisă adevărată decurge o afirmație falsă. Prin urmare, pentru o expresie dată, premisa A ∨ B trebuie să fie „adevărată”, iar consecința, adică expresia B ∨ ¬C ∨ B, trebuie să fie „falsă”.

    1) A ∨ B — rezultatul disjuncției este „adevărat” dacă cel puțin unul dintre operanzi este „adevărat”;

    2) B ∨ ¬C ∨ B - expresia este falsă dacă toți termenii au valoarea „fals”, adică B este „fals”; ¬C este „fals”, deci variabila C are valoarea „adevărat”;

    3) dacă luăm în considerare premisa și luăm în considerare că B este „fals”, obținem că valoarea lui A este „adevărată”.

    Răspuns: A este adevărat, B este fals, C este adevărat.

    Exemplul 3. Care este cel mai mare număr întreg X pentru care enunțul (35

    Soluţie. Să notăm tabelul de adevăr pentru operația de implicare:

    A B A → B
    1 0 0
    0 1 1
    0 0 1
    1 1 1

    Expresia X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

    Răspuns: X = 5.

    Utilizarea expresiilor booleene pentru a descrie regiunile geometrice

    Expresiile logice pot fi folosite pentru a descrie regiuni geometrice. În acest caz, sarcina este formulată după cum urmează: scrieți pentru o anumită regiune geometrică o expresie logică care ia valoarea „adevărată” pentru valorile x, y dacă și numai dacă aparține orice punct cu coordonate (x; y). la regiunea geometrică.

    Să luăm în considerare descrierea unei regiuni geometrice folosind o expresie logică folosind exemple.

    Exemplul 1. Este specificată o imagine a unei regiuni geometrice. Scrieți o expresie logică care să descrie setul de puncte care îi aparțin.

    1) .

    Soluţie. O regiune geometrică dată poate fi reprezentată ca o mulțime de următoarele regiuni: prima regiune - D1 - semiplan $(x)/(-1) +(y)/(1) ≤ 1$, a doua - D2 - un cerc cu centrul la origine $x ^2 + y^2 ≤ 1$. Intersecția lor D1 $∩$ D2 reprezintă regiunea dorită.

    Rezultat: expresie logică $(x)/(-1)+(y)/(1) ≤ 1 ∧ x^2 + y^2 ≤ 1$.

    2)

    Această zonă poate fi scrisă astfel: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

    Notă. Când se construiește o expresie logică, se folosesc inegalități libere, ceea ce înseamnă că limitele figurilor aparțin și zonei umbrite. Dacă utilizați inegalități stricte, limitele nu vor fi luate în considerare. Limitele care nu aparțin zonei sunt de obicei afișate ca linii punctate.

    Puteți rezolva problema inversă și anume: desenați o regiune pentru o expresie logică dată.

    Exemplul 2. Desenați și umbriți zona pentru care este îndeplinită condiția logică y ≥ x ∧ y + x ≥ 0 ∧ y< 2 .

    Soluţie. Zona căutată este intersecția a trei semiplane. Construim drepte pe planul (x, y) y = x; y = -x; y = 2. Acestea sunt limitele regiunii, iar ultima limită y = 2 nu aparține regiunii, așa că o desenăm cu o linie punctată. Pentru a satisface inegalitatea y ≥ x, punctele trebuie să fie la stânga dreptei y = x, iar inegalitatea y = -x este satisfăcută pentru punctele care sunt la dreapta dreptei y = -x. Condiția y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

    Utilizarea funcțiilor logice pentru a descrie circuitele electrice

    Funcțiile logice sunt foarte utile pentru descrierea funcționării circuitelor electrice. Deci, pentru circuitul prezentat în Fig., unde valoarea variabilei X este starea comutatorului (dacă este pornit, valoarea lui X este „adevărată”, iar dacă este oprită, valoarea este „falsă” ), această valoare a lui Y este starea becului (dacă este aprins - valoarea este „adevărat”, iar dacă nu - „fals”), funcția logică va fi scrisă astfel: Y = X. Se numește funcția Y funcția de conductivitate.

    Pentru circuitul prezentat în fig., funcția logică Y are forma: Y = X1 ∪ X2, deoarece un singur comutator este suficient pentru ca becul să se aprindă. În circuitul din Fig., pentru ca becul să se aprindă, ambele întrerupătoare trebuie să fie pornite, prin urmare, funcția de conductivitate are forma: Y = X1 ∧ X2.

    Pentru un circuit mai complex, funcția de conductivitate va avea forma: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

    Circuitul poate conține și contacte de scurtcircuit. În acest caz, contactul deschis acționează ca un comutator pentru a se asigura că becul se aprinde atunci când butonul este eliberat și nu este apăsat. Pentru astfel de circuite, întrerupătorul este descris prin negație.

    Cele două scheme sunt numite echivalent, dacă un curent trece prin unul dintre ele, atunci trece și prin celălalt. Dintre două circuite echivalente, circuitul mai simplu este cel a cărui funcție de conductivitate conține un număr mai mic de elemente. Sarcina de a găsi cele mai simple circuite dintre cele echivalente este foarte importantă.

    Utilizarea aparatului algebrei logice în proiectarea circuitelor logice

    Matematica algebrei logice este foarte utilă pentru a descrie modul în care funcționează hardware-ul computerului. Atunci când este procesată pe un computer, orice informație este prezentată în formă binară, adică este codificată printr-o anumită secvență de 0 și 1. Prelucrarea semnalelor binare corespunzătoare lui 0 și 1 se realizează în calculator prin elemente logice. Porți logice care efectuează operații logice de bază ȘI, SAU, NU, sunt prezentate în Fig.

    Simbolurile pentru elementele logice sunt standard și sunt utilizate la elaborarea circuitelor logice ale unui computer. Folosind aceste circuite, puteți implementa orice funcție logică care descrie funcționarea unui computer.

    Din punct de vedere tehnic, un element logic al computerului este implementat sub forma unui circuit electric, care este o conexiune a diferitelor părți: diode, tranzistoare, rezistențe, condensatoare. Intrarea unui element logic, care se mai numește și poartă, primește semnale electrice de niveluri de tensiune înaltă și joasă, iar un semnal de ieșire este, de asemenea, emis la un nivel ridicat sau scăzut. Aceste niveluri corespund uneia dintre stările sistemului binar: 1 - 0; ADEVĂRUL ESTE FALS. Fiecare element logic are propriul său simbol, care își exprimă funcția logică, dar nu indică ce fel de circuit electronic este implementat în el. Acest lucru facilitează scrierea și înțelegerea circuitelor logice complexe. Funcționarea circuitelor logice este descrisă folosind tabele de adevăr. Simbolul din diagrama SAU este semnul „1” - de la denumirea învechită a disjuncției ca „>=1” (valoarea disjuncției este 1 dacă suma celor doi operanzi este mai mare sau egală cu 1). Semnul „&” din diagrama AND este o abreviere pentru cuvântul englezesc și.

    Circuitele logice electronice sunt realizate din elemente logice care efectuează operații logice mai complexe. Un set de elemente logice format din elemente NU, SAU și ȘI, cu ajutorul cărora puteți construi o structură logică de orice complexitate, se numește complet funcțional.

    Construirea tabelelor de adevăr ale expresiilor logice

    Pentru o formulă logică poți scrie oricând tabelul de adevăr, adică să prezinte o funcție logică dată în formă tabelară. În acest caz, tabelul ar trebui să conțină toate combinațiile posibile de argumente ale funcției (formule) și valorile funcției corespunzătoare (rezultatele formulei pe un set dat de valori).

    O formă convenabilă de înregistrare la găsirea valorilor funcției este un tabel care conține, pe lângă valorile variabilelor și valorile funcției, și valorile calculelor intermediare. Să luăm în considerare un exemplu de construire a unui tabel de adevăr pentru formula $(X1)↖(-) ∧ X2 ∨ (X1 ∨ X2)↖(-) ∨ X1$.

    X1 X2 $(X1)↖(-)$ $(X1)↖(-)$ \ X2 X1 ∧ X2 $(X1 ∨ X2)↖(-)$ $(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$ $(X1)↖(-)$ ∧ X2 ∨ $(X1 ∨ X2)↖(-)$ ∨ X1
    1 1 0 0 1 0 0 1
    1 0 0 0 1 0 0 1
    0 1 1 1 1 0 1 1
    0 0 1 0 0 1 1 1

    Dacă o funcție ia valoarea 1 pentru toate seturile de valori variabile, este identic adevărat; dacă pentru toate seturile de valori de intrare funcția ia valoarea 0, este identic fals; dacă setul de valori de ieșire conține atât 0, cât și 1, funcția este apelată fezabil. Exemplul de mai sus este un exemplu de funcție identic adevărată.

    Cunoscând forma analitică a unei funcții logice, puteți merge oricând la forma tabelară a funcțiilor logice. Folosind un tabel de adevăr dat, puteți rezolva problema inversă și anume: pentru un tabel dat, construiți o formulă analitică pentru o funcție logică. Există două forme de construire a dependenței analitice a unei funcții logice bazată pe o funcție specificată în tabel.

    1. Forma normală disjunctivă (DNF)- suma produselor formate din variabile si negatiile acestora pentru valori false.

    Algoritmul pentru construirea unui DNF este următorul:

    1. în tabelul de adevăr, funcțiile selectează seturi de argumente pentru care formele logice sunt egale cu 1 („adevărat”);
    2. toate seturile logice selectate sunt scrise ca produse logice ale argumentelor, conectându-le secvențial între ele folosind operația de sumă logică (disjuncție);
    3. pentru argumentele care sunt false, se introduce o operație de negație în înregistrarea construită.

    Exemplu. Construiți o funcție care determină că primul număr este egal cu al doilea folosind metoda DNF. Tabelul de adevăr al funcției arată ca

    X1 X2 F(X1, X2)
    1 1 1
    0 1 0
    1 0 0
    0 0 1

    Soluţie. Selectăm seturi de valori de argument în care funcția este egală cu 1. Acestea sunt primul și al patrulea rând din tabel (nu ținem cont de rândul antetului la numerotare).

    Notăm produsele logice ale argumentelor acestor mulțimi, combinându-le cu o sumă logică: X1 ∧ X2 ∨ X1 ∧ X2.

    Notăm negația argumentelor mulțimilor selectate care au o valoare falsă (al patrulea rând al tabelului; al doilea set din formulă; primul și al doilea elemente): X1 ∧ X2 ∨ $(X1)↖(- )$ ∧ $(X2)↖(-)$.

    Răspuns: F(X1, X2) = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

    2. Forma normală conjunctivă (CNF)- produsul sumelor formate din variabile si negatiile acestora pentru valori adevarate.

    Algoritmul pentru construirea CNF este următorul:

    1. în tabelul de adevăr sunt selectate seturi de argumente pentru care formele logice sunt egale cu 0 („fals”);
    2. toate seturile logice selectate ca sume logice de argumente sunt scrise secvențial, conectându-le între ele folosind operarea unui produs logic (conjuncție);
    3. pentru argumentele care sunt adevărate, se introduce o operație de negație în înregistrarea construită.

    Exemple de rezolvare a problemelor

    Exemplul 1. Să luăm în considerare exemplul anterior, adică să construim o funcție care determină că primul număr este egal cu al doilea, folosind metoda CNF. Pentru o funcție dată, tabelul său de adevăr are forma

    X1 X2 F(X1, X2)
    1 1 1
    0 1 0
    1 0 0
    0 0 1

    Soluţie. Selectăm seturi de valori de argument în care funcția este egală cu 0. Acestea sunt rândurile a doua și a treia (nu ținem cont de linia antetului la numerotare).

    Notăm sumele logice ale argumentelor acestor mulțimi, combinându-le cu un produs logic: X1 ∨ X2 ∧ X1 ∨ X2.

    Notăm negația argumentelor mulțimilor selectate care au o valoare adevărată (al doilea rând al tabelului, primul set al formulei, al doilea element; pentru a treia linie, iar acesta este al doilea set al formulei , primul element): X1 ∨ $(X2)↖(-)$ ∧ $( X1)↖(-)$ ∨ X2.

    Astfel, a fost obținută o înregistrare a funcției logice în CNF.

    Răspuns: X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2.

    Valorile funcției obținute prin cele două metode sunt echivalente. Pentru a demonstra această afirmație, folosim regulile logicii: F(X1, X2) = X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2 = X1 ∧ $(X1)↖ (-)$ ∨ X1 ∧ X2 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ $(X2)↖(-)$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $(X2 )↖(- )$ ∧ $(X1)↖(-)$ ∨ 0 = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

    Exemplul 2. Construiți o funcție logică pentru un tabel de adevăr dat:

    Formula necesară: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 .

    Se poate simplifica: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 = X2 ∧ (X1 ∨ $(X1)↖(-)$) = X2 ∧ 1 = X2.

    Exemplul 3. Pentru tabelul de adevăr dat, construiți o funcție logică folosind metoda DNF.

    X1 X2 X3 F(X1, X2, X3)
    1 1 1 1 X1 ∧ X2 ∧ X3
    1 0 1 0
    0 1 1 1 $(X1)↖(-)$ ∧ X2 ∧ X3
    0 0 1 0
    1 1 0 1 X1 ∧ X2 ∧ $(X3)↖(-)$
    1 0 0 1 X1 ∧ $(X2)↖(-)$ ∧ $(X3)↖(-)$
    0 1 0 0
    0 0 0 0

    Formula necesară: X1 ∧ X2 ∧ X ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∪ X1 ∧ $(X2)↖(-)$ ∧ $ (X3)↖(-)$.

    Formula este destul de greoaie și ar trebui simplificată:

    X1 ∧ X2 ∧ X3 ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∨ X1 ∧ $(X2)↖(-)$ ∧ $(-)$ ∧ ↖(-)$ = X2 ∧ X3 ∧ (X1 ∨ $(X1)↖(-)$) ∨ X1 ∧ $(X3)↖(-)$ ∧ (X2 ∨ $(X2)↖(-)$) = X2 ∧ X3 ∨ X1 ∧ $(X3)↖(-)$.

    Tabele de adevăr pentru rezolvarea problemelor logice

    Compilarea tabelelor de adevăr este una dintre modalitățile de a rezolva probleme logice. Când se utilizează această metodă de rezolvare, condițiile pe care le conține problema sunt înregistrate folosind tabele special compilate.

    Exemple de rezolvare a problemelor

    Exemplul 1. Creați un tabel de adevăr pentru un dispozitiv de securitate care utilizează trei senzori și este declanșat atunci când doar doi dintre ei sunt scurtcircuitati.

    Soluţie. Evident, rezultatul soluției va fi un tabel în care funcția dorită Y(X1, X2, X3) va avea valoarea „adevărată” dacă oricare două variabile au valoarea „adevărată”.

    X1 X2 X3 Y(X1, X2, X3)
    1 1 1 0
    1 1 0 1
    1 0 1 1
    1 0 0 0
    0 1 1 1
    0 1 0 0
    0 0 1 0
    0 0 0 0

    Exemplul 2. Faceți un program de lecție pentru ziua respectivă, ținând cont că o lecție de informatică poate fi doar prima sau a doua, o lecție de matematică - prima sau a treia și o lecție de fizică - a doua sau a treia. Este posibil să creați un program care să îndeplinească toate cerințele? Câte opțiuni de programare există?

    Soluţie. Problema poate fi rezolvată cu ușurință dacă creați tabelul corespunzător:

    Prima lecție Lectia 2 Lecția 3
    Informatică 1 1 0
    Matematică 1 0 1
    Fizică 0 1 1

    Tabelul arată că există două opțiuni pentru programul dorit:

    1. matematică, informatică, fizică;
    2. informatică, fizică, matematică.

    Exemplul 3. Trei prieteni au venit în tabăra sportivă - Peter, Boris și Alexey. Fiecare dintre ei este pasionat de două sporturi. Se știe că există șase astfel de sporturi: fotbal, hochei, schi, înot, tenis, badminton. Se mai stie ca:

    1. Boris este cel mai mare;
    2. un fotbalist mai tânăr decât un jucător de hochei;
    3. joacă fotbal și hochei, iar Peter locuiește în aceeași casă;
    4. când apare o ceartă între un schior și un tenismen, Boris îi împacă;
    5. Peter nu poate juca tenis sau badminton.

    Ce sport se bucură de fiecare băiat?

    Soluţie. Să întocmim un tabel și să reflectăm condițiile problemei în el, completând celulele corespunzătoare cu numerele 0 și 1, în funcție de faptul că afirmația corespunzătoare este falsă sau adevărată.

    Deoarece există șase tipuri de sport, se dovedește că toți băieții sunt interesați de diferite sporturi.

    Din condiția 4 rezultă că Boris nu este interesat de schi sau tenis, iar din condițiile 3 și 5 că Peter nu știe să joace fotbal, hochei, tenis și badminton. În consecință, sporturile preferate ale lui Peter sunt schiul și înotul. Să punem acest lucru în tabel și să umplem celulele rămase ale coloanelor „Schi” și „Îot” cu zerouri.

    Tabelul arată că numai Alexey poate juca tenis.

    Din condițiile 1 și 2 rezultă că Boris nu este fotbalist. Astfel, Alexey joacă fotbal. Să continuăm să completăm tabelul. Să introducem zerouri în celulele goale ale liniei „Alexey”.

    În sfârșit înțelegem că Boris este interesat de hochei și badminton. Masa finală va arăta astfel:

    Răspuns: Lui Peter îi place să schieze și să înoate, Boris joacă hochei și badminton, iar Alexey joacă fotbal și tenis.

    În circuitele digitale, un semnal digital este un semnal care poate lua două valori, considerat un „1” logic și un „0” logic.

    Circuitele logice pot conține până la 100 de milioane de intrări, iar astfel de circuite gigantice există. Imaginați-vă că funcția (ecuația) booleană a unui astfel de circuit a fost pierdută. Cum să-l restabiliți cu cea mai mică pierdere de timp și fără erori? Cea mai productivă modalitate este de a împărți diagrama în niveluri. Cu această metodă, funcția de ieșire a fiecărui element din nivelul anterior este înregistrată și înlocuită cu intrarea corespunzătoare din nivelul următor. Astăzi vom lua în considerare această metodă de analiză a circuitelor logice cu toate nuanțele sale.

    Circuitele logice sunt implementate folosind elemente logice: „NU”, „ȘI”, „SAU”, „ȘI-NU”, „SAU-NU”, „XOR” și „Echivalență”. Primele trei elemente logice vă permit să implementați orice funcție logică, indiferent cât de complexă, pe o bază booleană. Vom rezolva probleme pe circuite logice implementate precis pe o bază booleană.

    Mai multe standarde sunt folosite pentru a desemna elemente logice. Cele mai comune sunt americane (ANSI), europene (DIN), internaționale (IEC) și ruse (GOST). Figura de mai jos prezintă denumirile elementelor logice din aceste standarde (pentru a mări, puteți face clic pe figură cu butonul stâng al mouse-ului).

    În această lecție vom rezolva probleme privind circuitele logice, în care elementele logice sunt desemnate în standardul GOST.

    Problemele circuitelor logice sunt de două tipuri: sarcina de a sintetiza circuite logice și sarcina de a analiza circuite logice. Vom începe cu al doilea tip de sarcină, deoarece în această ordine putem învăța rapid să citim circuitele logice.

    Cel mai adesea, în legătură cu construcția circuitelor logice, funcțiile algebrei logice sunt luate în considerare:

    • trei variabile (vor fi luate în considerare în probleme de analiză și într-o problemă de sinteză);
    • patru variabile (în probleme de sinteză, adică în ultimele două paragrafe).

    Să luăm în considerare construcția (sinteza) circuitelor logice

    • în baza booleană „ȘI”, „SAU”, „NU” (în penultimul paragraf);
    • în bazele de asemenea comune „ȘI-NU” și „SAU-NU” (în ultimul paragraf).

    Problemă de analiză a circuitului logic

    Sarcina analizei este de a determina funcția f, implementat de un circuit logic dat. Când rezolvați o astfel de problemă, este convenabil să respectați următoarea secvență de acțiuni.

    1. Diagrama logică este împărțită în niveluri. Nivelurilor li se atribuie numere secvențiale.
    2. Ieșirile fiecărui element logic sunt desemnate prin numele funcției dorite, echipată cu un index digital, unde prima cifră este numărul nivelului, iar cifrele rămase sunt numărul de serie al elementului din nivel.
    3. Pentru fiecare element se scrie o expresie analitică care leagă funcția sa de ieșire cu variabilele de intrare. Expresia este determinată de funcția logică implementată de elementul logic dat.
    4. Înlocuirea unor funcții de ieșire prin altele se realizează până când se obține o funcție booleană, exprimată în termeni de variabile de intrare.

    Exemplul 1.

    Soluţie. Împărțim circuitul logic în niveluri, care este deja prezentat în figură. Să notăm toate funcțiile, începând de la primul nivel:

    X, y, z :

    X y z f
    1 1 1 0 1 1 1 1
    1 1 0 0 0 0 1 0
    1 0 1 0 0 0 1 0
    1 0 0 0 0 0 1 0
    0 1 1 0 0 0 1 0
    0 1 0 0 0 0 1 0
    0 0 1 0 0 0 1 0
    0 0 0 1 0 1 0 0

    Exemplul 2. Găsiți funcția booleană a unui circuit logic și construiți un tabel de adevăr pentru circuitul logic.

    Exemplul 3. Găsiți funcția booleană a unui circuit logic și construiți un tabel de adevăr pentru circuitul logic.


    Continuăm să căutăm împreună funcția booleană a circuitului logic

    Exemplul 4. Găsiți funcția booleană a unui circuit logic și construiți un tabel de adevăr pentru circuitul logic.

    Soluţie. Împărțim diagrama logică în niveluri. Să notăm toate funcțiile, începând de la primul nivel:

    Acum să notăm toate funcțiile, înlocuind variabilele de intrare X, y, z :

    Ca rezultat, obținem funcția pe care circuitul logic o implementează la ieșire:

    .

    Tabel de adevăr pentru acest circuit logic:

    X y z f
    1 1 1 0 1 1
    1 1 0 0 1 1
    1 0 1 1 0 1
    1 0 0 0 0 0
    0 1 1 0 1 1
    0 1 0 0 1 1
    0 0 1 0 1 1
    0 0 0 0 1 1

    Exemplul 5. Găsiți funcția booleană a unui circuit logic și construiți un tabel de adevăr pentru circuitul logic.

    Soluţie. Împărțim diagrama logică în niveluri. Structura acestui circuit logic, spre deosebire de exemplele anterioare, are 5 niveluri, nu 4. Dar o variabilă de intrare - cea mai joasă - parcurge toate nivelurile și intră direct în elementul logic din primul nivel. Să notăm toate funcțiile, începând de la primul nivel:

    Acum să notăm toate funcțiile, înlocuind variabilele de intrare X, y, z :

    Ca rezultat, obținem funcția pe care circuitul logic o implementează la ieșire:

    .

    Tabel de adevăr pentru acest circuit logic:

    X y z f
    1 1 1 1 1 1
    1 1 0 1 1 1
    1 0 1 1 0 1
    1 0 0 1 0 1
    0 1 1 1 1 1
    0 1 0 1 1 1
    0 0 1 1 0 1
    0 0 0 1 0 1

    Problema sintetizării circuitelor logice pe bază booleană

    Dezvoltarea unui circuit logic conform descrierii sale analitice se numește problema sintezei circuitelor logice.

    Fiecare disjuncție (suma logică) corespunde unui element „SAU”, al cărui număr de intrări este determinat de numărul de variabile din disjuncție. Fiecare conjuncție (produs logic) corespunde unui element „ȘI”, al cărui număr de intrări este determinat de numărul de variabile din conjuncție. Fiecare negație (inversie) corespunde unui element „NU”.

    Designul logic începe adesea cu definirea funcției logice pe care circuitul logic trebuie să o implementeze. În acest caz, este dat doar tabelul de adevăr al circuitului logic. Vom analiza doar un astfel de exemplu, adică vom rezolva o problemă care este complet opusă problemei de analiză a circuitelor logice discutată mai sus.

    Exemplul 6. Construiți un circuit logic care implementează o funcție cu un tabel de adevăr dat.

    Scopul serviciului. Calculatorul online este conceput pentru construirea unui tabel de adevăr pentru o expresie logică.
    Tabel de adevăr – un tabel care conține toate combinațiile posibile de variabile de intrare și valorile lor de ieșire corespunzătoare.
    Tabelul de adevăr conține 2n rânduri, unde n este numărul de variabile de intrare și n+m sunt coloane, unde m sunt variabile de ieșire.

    Instrucțiuni. Când introduceți de la tastatură, utilizați următoarele notații: De exemplu, expresia logică abc+ab~c+a~bc trebuie introdusă astfel: a*b*c+a*b=c+a=b*c
    Pentru a introduce date sub forma unei diagrame logice, utilizați acest serviciu.

    Reguli pentru introducerea unei funcții logice

    1. În loc de simbolul v (disjuncție, SAU), utilizați semnul +.
    2. Nu este nevoie să specificați o desemnare a funcției înainte de o funcție logică. De exemplu, în loc de F(x,y)=(x|y)=(x^y) trebuie să introduceți pur și simplu (x|y)=(x^y) .
    3. Numărul maxim de variabile este de 10.

    Proiectarea și analiza circuitelor logice computerizate se realizează folosind o ramură specială a matematicii - algebra logică. În algebra logicii se pot distinge trei funcții logice principale: „NU” (negație), „ȘI” (conjuncție), „SAU” (disjuncție).
    Pentru a crea orice dispozitiv logic, este necesar să se determine dependența fiecăreia dintre variabilele de ieșire de variabilele de intrare existente; această dependență se numește funcție de comutare sau funcție de algebră logică.
    O funcție de algebră logică se numește complet definită dacă sunt date toate cele 2n dintre valorile sale, unde n este numărul de variabile de ieșire.
    Dacă nu toate valorile sunt definite, funcția se numește parțial definită.
    Un dispozitiv este numit logic dacă starea lui este descrisă folosind o funcție de algebră logică.
    Următoarele metode sunt utilizate pentru a reprezenta o funcție algebrică logică:

    • descrierea verbală este o formă care este utilizată în stadiul inițial de proiectare și are o reprezentare condiționată.
    • descrierea unei funcții de algebră logică sub forma unui tabel de adevăr.
    • descrierea unei funcții algebrice logice sub forma unei expresii algebrice: se folosesc două forme algebrice ale FAL:
      A) DNF – formă normală disjunctivă este suma logică a produselor logice elementare. DNF este obținut din tabelul de adevăr folosind următorul algoritm sau regulă:
      1) în tabel sunt selectate acele rânduri de variabile pentru care funcția de ieșire =1.
      2) pentru fiecare linie de variabile se scrie un produs logic; Mai mult, variabilele =0 sunt scrise cu inversare.
      3) produsul rezultat este însumat logic.
      Fdnf= X 1 *X 2 *X 3 ∨ X 1 x 2 X 3 ∨ X 1 X 2 x 3 ∨ X 1 X 2 X 3
      Se spune că un DNF este perfect dacă toate variabilele au același rang sau ordine, adică Fiecare lucrare trebuie să includă toate variabilele în formă directă sau inversă.
      b) CNF – formă normală conjunctivă este un produs logic al unor sume logice elementare.
      CNF poate fi obținut din tabelul de adevăr folosind următorul algoritm:
      1) selectați seturi de variabile pentru care funcția de ieșire =0
      2) pentru fiecare set de variabile scriem o sumă logică elementară, iar variabilele =1 se scriu cu inversare.
      3) sumele rezultate sunt înmulțite logic.
      Fsknf=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
      CNF se numește perfect, dacă toate variabilele au același rang.
    În formă algebrică, puteți construi un circuit al unui dispozitiv logic folosind elemente logice.

    Figura 1 - Diagrama dispozitivului logic

    Toate operațiile algebrei logicii sunt definite tabele de adevăr valorile. Tabelul de adevăr determină rezultatul unei operații pentru oricine este posibil x valorile logice ale afirmațiilor originale. Numărul de opțiuni care reflectă rezultatul aplicării operațiilor va depinde de numărul de instrucțiuni din expresia logică. Dacă numărul de afirmații dintr-o expresie logică este N, atunci tabelul de adevăr va conține 2 N rânduri, deoarece există 2 N combinații diferite de valori posibile ale argumentului.

    Operațiunea NOT - negație logică (inversie)

    O operație logică NU se aplică unui singur argument, care poate fi o expresie logică simplă sau complexă. Rezultatul operației NU este următorul:
    • dacă expresia originală este adevărată, atunci rezultatul negației sale va fi fals;
    • dacă expresia originală este falsă, atunci rezultatul negației sale va fi adevărat.
    Următoarele convenții NU sunt acceptate pentru operația de negație:
    nu A, Â, nu A, ¬A, !A
    Rezultatul operației de negație NU este determinat de următorul tabel de adevăr:
    Anu A
    0 1
    1 0

    Rezultatul operației de negație este adevărat atunci când afirmația inițială este falsă și invers.

    Operație SAU - adunare logică (disjuncție, unire)

    Operația logic OR îndeplinește funcția de a combina două instrucțiuni, care pot fi fie o expresie logică simplă, fie o expresie logică complexă. Declarațiile care sunt punctele de plecare pentru o operație logică se numesc argumente. Rezultatul operației SAU este o expresie care va fi adevărată dacă și numai dacă cel puțin una dintre expresiile originale este adevărată.
    Denumiri utilizate: A sau B, A V B, A sau B, A||B.
    Rezultatul operației OR este determinat de următorul tabel de adevăr:
    Rezultatul operației SAU este adevărat atunci când A este adevărat, sau B este adevărat sau ambele A și B sunt adevărate și false când argumentele A și B sunt false.

    Operația ȘI - înmulțire logică (conjuncție)

    Operația logică AND îndeplinește funcția de intersecție a două afirmații (argumente), care poate fi fie o expresie logică simplă, fie o expresie logică complexă. Rezultatul operației AND este o expresie care va fi adevărată dacă și numai dacă ambele expresii originale sunt adevărate.
    Denumirile utilizate: A și B, A Λ B, A și B, A și B.
    Rezultatul operației AND este determinat de următorul tabel de adevăr:
    ABA și B
    0 0 0
    0 1 0
    1 0 0
    1 1 1

    Rezultatul operației AND este adevărat dacă și numai dacă afirmațiile A și B sunt ambele adevărate și false în toate celelalte cazuri.

    Operațiunea „IF-THEN” - consecință logică (implicație)

    Această operație conectează două expresii logice simple, dintre care prima este o condiție, iar a doua este o consecință a acestei condiții.
    Denumiri folosite:
    dacă A, atunci B; A implică B; dacă A atunci B; A→B.
    Tabelul de adevăr:
    ABA → B
    0 0 1
    0 1 1
    1 0 0
    1 1 1

    Rezultatul operației de implicare este fals numai dacă premisa A este adevărată și concluzia B (consecința) este falsă.

    Operația „A dacă și numai dacă B” (echivalență, echivalență)

    Denumirea utilizată: A ↔ B, A ~ B.
    Tabelul de adevăr:
    ABA↔B
    0 0 1
    0 1 0
    1 0 0
    1 1 1

    Operația „Adăugare modulo 2” (XOR, exclusiv sau, disjuncție strictă)

    Notația folosită: A XOR B, A ⊕ B.
    Tabelul de adevăr:
    ABA⊕B
    0 0 0
    0 1 1
    1 0 1
    1 1 0

    Rezultatul operației de echivalență este adevărat numai dacă A și B sunt ambele adevărate sau false în același timp.

    Prioritatea operațiilor logice

    • Acțiuni între paranteze
    • Inversiunea
    • Conjuncție (&)
    • Disjuncție (V), SAU exclusiv (XOR), suma modulo 2
    • Implicație (→)
    • Echivalență (↔)

    Forma normală disjunctivă perfectă

    Forma normală disjunctivă perfectă a unei formule(SDNF) este o formulă echivalentă, care este o disjuncție a conjuncțiilor elementare și are următoarele proprietăți:
    1. Fiecare termen logic al formulei conține toate variabilele incluse în funcția F(x 1,x 2,...x n).
    2. Toți termenii logici ai formulei sunt diferiți.
    3. Niciun termen logic nu conține o variabilă și negația acesteia.
    4. Niciun termen logic dintr-o formulă nu conține aceeași variabilă de două ori.
    SDNF poate fi obținut fie folosind tabele de adevăr, fie folosind transformări echivalente.
    Pentru fiecare funcție, SDNF și SCNF sunt definite în mod unic până la permutare.

    Forma normală conjunctivă perfectă

    Forma normală conjunctivă perfectă a unei formule (SCNF) Aceasta este o formulă echivalentă cu aceasta, care este o conjuncție de disjuncții elementare și satisface proprietățile:
    1. Toate disjuncțiile elementare conțin toate variabilele incluse în funcția F(x 1 ,x 2 ,...x n).
    2. Toate disjuncțiile elementare sunt diferite.
    3. Fiecare disjuncție elementară conține o variabilă o dată.
    4. Nici o singură disjuncție elementară nu conține o variabilă și negația ei.