Schema logică imagine pentru următoarea expresie. Construcția circuitelor logice funcționale pentru funcții specificate. Sarcina de testare

Numărul de lucrări de laborator 2. Algebra logică

scopul de a lucra

Examinați elementele de bază ale algebrei logice.

Sarcinile muncii de laborator

Ca urmare a ocupației, studentul trebuie:

    • definiții ale conceptelor de bază (declarații simple și complexe, operațiuni logice, expresii logice, funcție logică);
    • procedura de efectuare a operațiunilor logice;
    • algoritm pentru construirea meselor de adevăr;
    • scheme de elemente logice de bază;
    • legi logice și reguli pentru conversia expresiilor logice;
    • aplicați pixuri logice pentru a simplifica expresiile logice;
    • construiți tabelele adevărului;
    • construiți scheme logice ale expresiilor complexe.

Informații generale teoretice

Concepte de bază ale algebrei logice

Baza logică a computerului este algebra logicii, care ia în considerare operațiile logice pe declarații.

Algebra Logic. - Aceasta este secțiunea de învățare matematică a declarațiilor considerate de valorile lor logice (adevărul sau falsitatea) și operațiunile logice asupra lor.

Declarație logică - Aceasta este o ofertă narativă pentru care se poate spune fără echivoc, este cu adevărat sau falsă.

Exemplu."3 - Un număr simplu" este o declarație, deoarece este adevărat.

Nu există nicio propunere este o declarație logică.

Exemplu. Oferta "Să mergem la filme" nu este o declarație. Propunerile chestionare și motivante nu sunt declarații.

Forma de primăvară - Aceasta este o propunere narativă care conține direct sau indirect cel puțin o variabilă și devine o declarație atunci când toate variabilele sunt înlocuite cu valorile lor.

Exemplu. "X + 2\u003e 5" este o formă utilă, care la x\u003e 3 este adevărată, altfel falsă.

Logica Algebra ia în considerare orice declarație numai dintr-un punct de vedere - fie că este adevărat sau fals. Cuvintele și frazele "nu", "și" "," sau ", dacă ...", "atunci și numai atunci" și alții permit noi declarații din declarațiile deja specificate. Aceste cuvinte și fraze sunt numite ligamente logice.

Declarațiile formate din alte afirmații care utilizează ligamente logice sunt numite compus (complicat). Declarații care nu sunt numite compozite elementar (simplu).

Exemplu. Declarația "Numărul 6 este împărțită în 2" - o declarație simplă. Declarația "Numărul 6 este împărțit în 2, iar numărul 6 este împărțit în 3" - o declarație compozită formată din două simple folosind un pachet logic "și".

Adevărul sau falsitatea declarațiilor compozite depind de adevărul sau de falsificarea declarațiilor elementare, dintre care constau.

Pentru a se referi la declarațiile logice, ele sunt numere prescrise.

Exemplu. Denota de o declarație simplă "Numărul 6 este împărțit în 2", și printr-o declarație simplă "Numărul 6 este împărțit în 3". Apoi, declarația compozită "numărul 6 este împărțită în 2, iar numărul 6 este împărțit în 3" poate fi scris ca "A și B". Aici, "și" este o grămadă logică și, în - variabile logice care pot dura numai timp - "adevăr" sau "minciuni", indicate, respectiv "1" și "0".

Fiecare buchet logic este considerată o operațiune privind declarațiile logice și are numele și desemnarea (Tabelul 1).

Tabelul 1. Operații logice de bază


NU Funcționarea, exprimată prin cuvântul "nu", se numește negare Și trase de punctul de deasupra declarației (sau semnului). Spunând și adevărat când a este falsă și falsă când este adevărat.

Exemplu. Lăsați-i \u003d "Astăzi sunt acoperiți, apoi a \u003d" Astăzi nu este tulbure ".

ȘI Funcționarea exprimată de un pachet "și" numit conjuncție (Lat. Conjuncto-conexiune) sau înmulțirea logică și notată cu punctul "" (poate fi, de asemenea, marcată de semne sau &). Spunând și în adevărat atunci și numai atunci când ambele afirmații a și în adevăr.

Exemplu. Declarația "Numărul 6 este împărțit în 2, iar numărul 6 este împărțit în 3" - cu adevărat, iar declarația "numărul 6 este împărțită în 2, iar numărul 6 este mai mare de 10" - FALSE.

SAU Funcționarea exprimată printr-un pachet "sau" (în sensul neexclusiv al cuvântului), numit disjuncție (Lat. Disjuntio - separare) sau adăugare logică și este indicată de semn

(sau plus). Spunând și în mod fals atunci și numai atunci când ambele afirmații și în fals.

Exemplu: Declarația "Numărul 6 este împărțit în 2 sau numărul 6 mai mult de 10" - cu adevărat, iar declarația "numărul 6 este împărțită în 5 sau numărul 6 mai mult de 10" - FALSE.

Dacă ... Operațiunea exprimată de pachete "Dacă ..., atunci", "de la ... urmează", "... implică ...", a sunat implicare (Lat. Implico - strâns legată) și este indicată de semnul →. Spunând un → în mod fals atunci și numai dacă este adevărat, dar în fals.

Exemplu. Declarație "Dacă elevul a trecut toate examenele" Excelent ", va primi o bursă". Evident, această implicare ar trebui să fie recunoscută ca falsă numai dacă studentul a trecut pe "excelent" toate examenele, dar nu a primit burse. În alte cazuri, atunci când nu toate examenele sunt predate la "excelent", iar bursa este obținută (de exemplu, datorită faptului că elevul locuiește într-o familie cu venituri mici) sau când examenele nu sunt îndeplinite deloc și acolo Nu poate fi nici un discurs despre burse, implicația poate fi recunoscută adevărată.

Echivalent Funcționarea exprimată de pachete "atunci și numai atunci", "este necesar și suficient", "... este echivalent ...", a sunat echivalent sau implicație dublă Și indicată de semnul ↔ sau ~. Declarația A↔V este adevărată și numai dacă valorile A și B coincid.

Exemplu: Declarația "Numărul este chiar atunci și numai dacă este împărțit fără un reziduu cu 2" este adevărat și declarația "Numărul este ciudat dacă și numai dacă este împărțit fără restul de 2" - FALSE.

Sau fie Operațiunea exprimată de pachete "fie ... fie" se numește excluzând sau sau adăugarea prin modulul 2 Și a indicat XOR sau. Spunând și în adevăr și numai dacă valorile A și B nu coincid.

Exemplu. Declarația "Numărul 6 sau este ciudat fie împărțit fără un reziduu pentru 2" este adevărat și afirmația "fie numărul 6 este chiar sau numărul 6 este împărțit în 3" este fals, deoarece ambele declarații sunt incluse în el.

Cometariu. Implicația poate fi exprimată prin disjuncție și negare:

Echivalența poate fi exprimată prin negare, disjuncție și conjuncție:

Excluzând sau poate fi exprimată prin negare, disjuncție și conjuncție:

Ieșire. Calorarea, disjuncția și operațiunile de conjuncție sunt suficiente pentru a descrie și a procesa declarații logice.

Procedura de efectuare a operațiunilor logice este dată de paranteze rotunde. Dar pentru a reduce numărul de paranteze, am convenit să presupunem că operațiunea de negare este mai întâi efectuată ("nu"), apoi conjuncția ("și"), după o conjuncție ("sau") și excluzând sau ultima dată - implicare și echivalența.

Folosind variabile logice și simboluri ale operațiunilor logice, orice declarație poate fi formalizată, adică înlocuirea formulei logice (expresia logică).

Formula logică - Aceasta este o înregistrare de declarație simbolică constând din valori logice (constante sau variabile), combinate cu operațiuni logice (ligamente).

Funcția logică - Aceasta este o funcție a variabilelor logice care pot primi numai două valori: 0 sau 1. La rândul său, variabila logică în sine (argumentul funcției logice) poate dura numai două valori: 0 sau 1.

Exemplu. - funcția logică a două variabile A și B.

Valorile funcției logice pentru diferite combinații de valori ale variabilelor de intrare - sau, după caz, seturile de variabile de intrare sunt, de obicei, specificate de un tabel special. Acest tabel este numit titlul titlului..

Dăm tabelul de adevăr al operațiunilor logice de bază (Tabelul 2)

masa 2

A. B.

Bazându-se pe datele de tabel de adevăr ale operațiunilor logice de bază, puteți face tabele de adevăr pentru formule mai complexe.

Algoritmul pentru construirea de mese de adevăr pentru expresii complexe:

  • numărul de rânduri \u003d 2 n + șir pentru antet,
  • n - numărul de declarații simple.
  • numărul de coloane \u003d numărul de variabile + numărul de operațiuni logice;
  • determinați numărul de variabile (expresii simple);
  • determinați numărul de operațiuni logice și secvența execuției acestora.

Exemplul 1. Faceți un tabel de adevăr pentru formula și non-nu, care poate fi scris după cum urmează :.

1. Determinați numărul de rânduri:

La intrare două declarații simple: a și b, prin urmare n \u003d 2 și numărul de rânduri \u003d 2 2 + 1 \u003d 5.

2. Determinați numărul de coloane:

Expresia este alcătuită din două expresii simple (A și B) și două operații logice (1 inversiune, 1 conjuncție), adică. Numărul de coloane ale mesei de adevăr \u003d 4.

3. Umpleți coloanele ținând cont de tabelele de adevăr ale operațiunilor logice (tabelul 3).

Tabelul 3. Tatac de Adevăr pentru operarea logică


Notă: Și nu Apelați, de asemenea "Strike Scheffer" (denotă |) sau "Anticoruncțional"; SAU NU Apelați, de asemenea "Pierce arrow" (denotă ↓) sau "Antidiasjuncția".


Exemplul 2. Faceți un tabel de adevăr al unei expresii logice.


Decizie:

1. Determinați numărul de rânduri:

La intrare două declarații simple: a și b, prin urmare n \u003d 2 și numărul de rânduri \u003d 2 2 + 1 \u003d 5.

2. Determinați numărul de coloane:

Expresia este alcătuită din două expresii simple (A și B) și cinci operațiuni logice (2 inversiuni, 2 conjuncții, 1 disjuncție), adică. Numărul de coloane ale Tabelului Adevăr \u003d 7.

În primul rând, operațiunile inversiunii sunt efectuate, apoi conjuncție, ultima operațiune este funcționarea disjuncției.

3. Umpleți coloanele ținând cont de tabelele de adevăr ale operațiunilor logice (Tabelul 5).

Tabelul 5. Tatac de Adevăr pentru operarea logică
Deoarece orice operație logică poate fi reprezentată ca o combinație de trei principale, orice dispozitiv de calculator care produc prelucrarea sau depozitarea informațiilor pot fi asamblate de la elemente logice de bază din "cărămizi".

Elementele logice ale computerului funcționează cu semnale reprezentând impulsuri electrice. Există un impuls - sensul logic al semnalului - 1, nici un impuls - 0. Semnalele argumentelor sunt recepționate la intrările elementului logic, valoarea semnalului a funcției apare la ieșire.

Conversia semnalului Elementul logic este setat de tabelul de stat, care este de fapt un tabel de adevăr corespunzător funcției logice, este reprezentat numai sub formă de scheme logice. În acest formular, este convenabil să se prezinte lanțurile operațiunilor logice și să producă calculele.

Algoritmul pentru construirea schemelor logice.

  1. Determinați numărul de variabile logice.
  2. Determinați numărul de operațiuni logice și comanda acestora.
  3. Imagine pentru fiecare operație logică pe care elementul logic îl corespunde.
  4. Conectați elementele logice în ordinea operațiilor logice.

Exemplu. Pentru o anumită funcție logică, construiți o schemă logică.

Decizie.

  1. Numărul variabilelor logice \u003d 2 (A și B).
  2. Numărul de operații \u003d 5 (2 inversiune, 2 conjuncții, 1 disjuncție). În primul rând, operațiunile inversiunii sunt efectuate, apoi conjuncție, ultima operațiune este funcționarea disjuncției.
  3. Schema va conține 2 invertoare, 2 congele și 1 disjunctor.
  4. Clădirea ar trebui să fie inițiată cu o operațiune logică, care trebuie efectuată ultima dată. În acest caz, o astfel de operație este o adăugare logică, prin urmare, ieșirea trebuie să fie un disjunctor. Pe aceasta, semnalele sunt hrănite din două congensoare la care, la rândul său, un semnal de intrare este servit normal și unul inversat (de la invertoare).


Informații similare.


Vom fi familiarizați cu ei alternativ.

Construirea unei scheme de logică pentru o anumită funcție logică.

O sarcină:

Funcția logică Dana:

Faceți o schemă logică pentru aceasta.

Decizie:

Să separăm procedura de efectuare a operațiunilor logice, ghidate de reguli:
  1. negare
  2. multiplicare
  3. plus
Nu uitați de prioritatea parantezelor.
Primim:

Construiți schema la ordinea specificată.

Înregistrarea unei funcții logice conform unei anumite scheme logice.

O sarcină:

Dana logică Schema:

Face o funcție logică pe ea.

Decizie:

Considerăm că schema de la sfârșit și scriem operațiunile logice corespunzătoare, având în vedere că în funcția înregistrată, trei operanzi A, B, cu

Puteți să vă conectați mai întâi funcțiile intermediare ale diagramei obținute la ieșirea fiecărui bloc și apoi să le introduceți cu operații logice.

Determinarea semnalului la ieșirea circuitului logic conform valorilor semnalelor specificate la toate intrările din această schemă.

O sarcină:

Diagrama logică Dana și valorile semnalelor la toate intrările:

Determinați valoarea funcției F la ieșirea circuitului.

Decizie:

Folosind tabelele de Adevăr pentru elementele logice corespunzătoare ale circuitului, am setat valorile semnalelor la ieșiri și, în consecință, la intrările fiecărui element logic, nu voi ajunge la capătul circuitului. Primim:

Răspuns:

Valoarea funcției F la ieșirea circuitului \u003d 1.

Construiți un tabel de adevăr pentru o anumită schemă logică.

O sarcină:

Dana logică Schema:

Construiți un tabel de adevăr.

Decizie:

Verificați numărul de intrări din diagramă. Numărul de combinații de semnal cu 2 intrări este de 4, pentru că 3 intrări este de 8, pentru 4 intrări este de 16, etc. Facem un tabel de adevăr în care primele coloane sunt intrările circuitului marcate cu litere după coloane - Funcțiile obținute pe ieșirile fiecărui element de schemă și șiruri - reflectă diferite combinații de semnale la intrări. Numărul de linii coincide cu numărul de combinații de semnal. Folosind tabelele de Adevăr Pentru elementele logice corespunzătoare ale circuitului, am stabilit valorile semnalelor la ieșirile fiecărui element logic, adică pentru fiecare coloană, nu voi ajunge la capătul circuitului. Primim:

Răspuns:

4) Răspuns:l v 0 & l \u003d 1.

Exemplul 2.

Construiți o schemă logică corespunzătoare expresiei logice

F \u003d x & y v (y v x).

Calculați valorile expresiei pentru x \u003d 1, y \u003d 0.

1) Două variabile: x și y;

2) Operații logice Trei: conjuncție și două disjuncții: 14 3 2 x & y v (y v x).

3) Construiți schema de la stânga la dreapta, în conformitate cu procedura de operațiuni logice:


3) Calculați valoarea expresiei: F \u003d L & 0 V (0 V 1) \u003d 0

Exercițiu

Construiți o schemă logică corespunzătoare unei expresii logice și găsiți valoarea expresiei logice:

A) F \u003d A v B & C, dacă A \u003d 1, B \u003d 1, C \u003d 1.

B) f \u003d (a v B & C), dacă a \u003d 0, b \u003d 1, c \u003d 1.

B) f \u003d a v B & C, dacă a \u003d 1, b \u003d 0, c \u003d 1.

D) f \u003d (a v c) & (cu v c), dacă \u003d 0, b \u003d 1, c \u003d 0.

E) f \u003d (A & C & C), dacă a \u003d 0, b \u003d 0, c \u003d 1.

E) F \u003d (A & B & C) V (B & C VA), dacă A \u003d 1, B \u003d 1, C \u003d 0.

G) f \u003d B & A v B & A, dacă A \u003d 0, B \u003d 0.

Legii logice.

Dacă expresia logică conține un număr mare de operații, atunci este destul de dificil ca acesta să fie un tabel de adevăr, deoarece este necesar să sorți un număr mare de opțiuni. În astfel de cazuri, formula este convenabilă pentru a duce la forma normală.

Formula are o formă normală dacă nu există semne de echivalență, implicații, negări duble și semne de negare sunt doar sub variabile logice.

Pentru a aduce formula la o formă normală, folosiți legile logice și regulile transformărilor logice.

A \u003d A. Legea identității
A & A \u003d 0 Legea contradicției
AV A \u003d L Legea unei treimi exclusive
A \u003d A. Dreptul de negare dublă
A & 0 \u003d 0 A v 0 \u003d a Acorduri de excepție
A & 1 \u003d A A V 1 \u003d 1 Acorduri de excepție
A & A \u003d A V A \u003d a Regula Idempotency
Ava \u003d L.
(Și → c) \u003d A & IN
A → B \u003d A v B
A & (av b) \u003d a Legea absorbției
A v (A & B) \u003d a Legea absorbției
Și & (AV C) \u003d A & IN
Ava & B \u003d A v B
(AVB) VC \u003d AV (BVC) (A & B) & C \u003d A & C & C) Acordul de asociere
(A & B) V (A & C) \u003d A & BVC (AVB) & (AVC) \u003d AV (B & C) Regula de distribuție
AVB \u003d BVA A & B \u003d B & A Regula de comutare
Aób \u003d A & BV (A & B)
(AVB) \u003d A & B Legile Morgan
(A & B) \u003d AV B Legile Morgan

Exemplu

Simplificați o expresie logică F.= ((A.v. C) → (înv. DIN)). Această expresie logică trebuie administrată formei normale, deoarece Are implicații și negare a operațiunii logice.

1. Scoateți implicațiile și negarea. Utilizăm (8). Se va dovedi: ((AVB) → (BVC)) \u003d (AVB) & (BVC).

2. Aplicați legea dublă de negare (4). Primiți: (AVB) & (BVC) \u003d (AVB) & (BVC)

3. Aplicați regula de distribuție (15). Primim:

(AVB) & (BVC) \u003d (AVB) & BV (AVB) & C.

4. Aplicați Legea Comutare (17) și Distribuția (15). Primiți: (AVB) & BV (AVB) & C = A & BVB & BVA & CVB & C.

5. Aplicați (16) și obținem: A & BVB & BVA & CVB & C \u003d A & BVBVA & CVA & C

6. Aplicați (15), adică voi transfera la paranteze V. Obținem:

A & BVBV A & CV B & C \u003d B & C (AV1) V A & CV B & C

7. Aplicați (6). Avem: In & (AVL) V A & CV B & C \u003d BV A & CV B & C.

8. Scoateți termenii componentelor, grupați și lăsați în paranteze. Primim:
BVA & CVB & C \u003d B & (1VC) VA & C.

9. Aplicați (6) și obțineți răspunsul:

Răspuns: F \u003d ((a v c) → (în v c)) \u003d în v A & C.

Simplificați expresia:

1) F \u003d (A & B) V (b V C).

2) F \u003d (A → B) V (B → A).

3) F \u003d A & C VA & C.

4) f \u003d un vb vc v a v b v C.

5) F \u003d (X & Y V (X & Y)).

6) f \u003d x & (y v x).

7) F \u003d (x VZ) & (x vz) & (y v z).

10) F \u003d B & C & (AVA).

11) F \u003d A & B & CVAVB

12) F \u003d (AVB) & (BVA) & (CVB)

Simplificați expresia:

1. f \u003d.A & C VA & C.

2. F \u003d A ↔ B V A & C

3. F \u003d A & (B↔C)

4. F \u003d (x v y) & (y ↔ x).

5. f \u003d.Un vb vc v a v b v C.

6. F \u003d (AVB) → (AVC)

7. F \u003d A ↔ (în V c)

8. F \u003d A & B → C & D.

9. f \u003d.(X & y v (x & y)).

10. f \u003d (x v y) & (y v x).

11. F \u003d A ↔ B & C

12. F \u003d (A v B) & (b v a → b).

13. F \u003d.X & (y v x).

14. F \u003d A → B V A & C

15. F \u003d X & Y V X.

16. F \u003d ((x v y) & (z → x)) & (z v y).

17. F \u003d.(X V z) & (x vz) & (y v z).

18. F \u003d A → (în V c)

19. F \u003d A ↔ B V C

20. F \u003d ((x v y) & (z v x)) & (z → y).

21. F \u003d (B & (A → C))

22. F \u003d A → B V A & C

23. F \u003d A ↔ (în V c)

24. F \u003d ((x v y) & (z v x)) & (z v y).

25. F \u003d.(A → B) V (B → A).

26. F \u003d A & B & C & D.

27. F \u003d A ↔ (în V c)

28. F \u003d A & (B → C).

29. F \u003d.A & (AVB)

30. F \u003d A ↔ (în V c)

31. F \u003d A → B V A & C

32. F \u003d (A v B) & (b v a v b).

33. f \u003d.B & C & (AVA).

34. F \u003d A & B V A & C

35. F \u003d X & Y ↔ X.

36. F \u003d ((x v y) & (z → x)) & (z ↔ y).

37. F \u003d.A & B & CVAVB

38. F \u003d (x → y) & (y v x).

39. F \u003d A → B & C

40. F \u003d (a ↔ b) & (b v A & b).

41. f \u003d.(AVB) & (BVA) & (CVB) .

42. F \u003d A & B V A & C

43. F \u003d A & (BVC)

44. F \u003d (x → y) & (y ↔ x).

45. F \u003d.AV (A & B)

46. \u200b\u200bF \u003d A & B ↔ C & D.

47. F \u003d A ↔ (în V c)

48. F \u003d (X & Y) V (Y & X).

Numirea serviciului. Calculatorul online este proiectat pentru construirea mesei adevărului pentru expresia logică.
Tabelul total care conține toate combinațiile posibile de variabile de intrare și valorile corespunzătoare la ieșire.
Tabelul Adevărului conține șirurile de 2 N, unde N este numărul de variabile de intrare și coloanele N + M, unde M este variabilele de ieșire.

Instrucțiuni. Când introduceți tastatura, utilizați următoarea notație: De exemplu, o expresie logică ABC + Ab ~ C + A ~ BC trebuie să fie administrată după cum urmează: A * B * C + A * B \u003d C + A \u003d B * C
Pentru a introduce date sub forma unui circuit logic, utilizați acest serviciu.

Reguli de intrare logică

  1. În loc de simbol v (disjuncție, sau), utilizați semnul +.
  2. Înainte de funcția logică, nu este necesar să specificați funcția de desemnare. De exemplu, în loc de f (x, y) \u003d (x | y) \u003d (x ^ y), este necesar să introduceți simplu (x | y) \u003d (x ^ y).
  3. Numărul maxim de variabile este de 10.

Proiectarea și analiza schemelor logice ale computerului se efectuează utilizând o secțiune specială a matematicii - algebră logică. În algebra logică, este posibilă evidențiarea a trei funcții logice principale: "nu" (refuz), "și" (conjuncția) "sau" (Disjuncția).
Pentru a crea orice dispozitiv logic, este necesar să se determine dependența fiecărei variabile de ieșire din variabilele de intrare activă, o astfel de dependență se numește o funcție de comutare sau funcția algebrei logice.
Funcția algebrei logice este numită complet definită dacă toate 2 N este setată, unde n este numărul de variabile de ieșire.
Dacă nu toate valorile sunt definite, funcția este numită parțial definită.
Dispozitivul este numit logic dacă starea sa este descrisă utilizând funcția de algebră logică.
Pentru a reprezenta logica de algebră a funcției, se utilizează următoarele metode:

  • o descriere verbală este o formă care este utilizată la etapa de proiectare inițială are o reprezentare condiționată.
  • descrierea funcției algebrei logice sub formă de masă de adevăr.
  • descrierea funcției algebrei logice sub formă de expresie algebrică: Se utilizează două forme algebrice:
    dar) DNF - Forma normală disjunctivă - Aceasta este cantitatea logică de lucrări logice elementare. DNF este obținut din tabelul de adevăr conform următorului algoritm sau regulă:
    1) Tabelul este selectat acele linii de variabile pentru care funcția de la ieșire \u003d 1.
    2) Pentru fiecare rând de variabile, este înregistrat un produs logic; Mai mult, variabilele \u003d 0 sunt înregistrate cu inversiune.
    3) Produsul rezultat este rezumat logic.
    Fdff \u003d x 1 * x 2 * x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3
    DNF se numește perfect dacă toate variabilele au același rang sau ordine, adică Fiecare produs trebuie să includă toate variabilele în formă directă sau inversă.
    b) KNF - formă normală conjunctivă - Acesta este un produs logic al sumelor logice elementare.
    CNF poate fi obținut din tabelul adevăr conform următorului algoritm:
    1) Selectați seturile de variabile pentru care funcția de la ieșire \u003d 0
    2) Pentru fiecare set de variabile, scrieți cantitatea logică elementară, iar variabilele \u003d 1 sunt scrise cu invers.
    3) Sumele primite logic.
    FSKNF \u003d (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 perfectDacă toate variabilele au același rang.
Prin forma algebrică, puteți construi o diagramă logică utilizând elemente logice.

Figura1 - Diagrama dispozitivului logic

Sunt determinate toate operațiunile algebrei logice titlurile adevărului Valori. Tatac de Adevăr determină rezultatul executării operațiunii pentru toate posibilex valorile logice ale afirmațiilor inițiale. Numărul de opțiuni care reflectă rezultatul utilizării operațiunilor va depinde de numărul de declarații din punct de vedere logic. Dacă numărul de declarații în expresia logică n, tabelul adevărului va conține șiruri de 2 n, deoarece există 2 n combinații diferite de valori posibile ale argumentelor.

Operațiunea Not - negare logică (inversiune)

Operația logică nu se aplică unui argument, care poate fi simplă și o expresie logică complexă. Rezultatul operației nu este următorul:
  • dacă expresia inițială este cu adevărat adevărată, atunci rezultatul refuzului său va fi fals;
  • dacă expresia inițială este falsă, atunci rezultatul refuzului său va fi adevărat.
Următoarele denumiri condiționate nu sunt luate pentru funcționarea de negare:
nu a, nu a, ¬, a
Rezultatul operației negative nu este determinat de următorul tabel de adevăr:
A.nu A.
0 1
1 0

Rezultatul operației negative este adevărat atunci când declarația inițială este falsă și invers.

Funcționare sau - adăugare logică (disjuncție, asociere)

O operație logică sau efectuează funcția de combinare a două afirmații, care poate fi simplă și o expresie logică complexă. Declarațiile care sunt inițiale pentru o operațiune logică se numesc argumente. Rezultatul operației sau este o expresie care va fi adevărată și numai dacă devine cu adevărat una dintre expresiile inițiale.
Aplicații utilizate: A sau B și V B, A sau B, A || b.
Rezultatul operației sau este determinat de următorul text de adevăr:
Rezultatul operației sau este adevărat atunci când este adevărat A, sau cu adevărat sau adevărat și și în același timp și este fals atunci când argumentele A și B sunt false.

Funcționare și - multiplicare logică (conjuncție)

Operațiunea logică și efectuează intersecția a două declarații (argumente), care poate fi simplă și o expresie logică complexă. Rezultatul operației este expresia care va fi adevărată și numai dacă ambele expresii inițiale sunt adevărate.
Aplicații aplicate: A și B, A λ B, A & B, A și B.
Rezultatul operației este determinat de următorul text de adevăr:
A.B.A și B.
0 0 0
0 1 0
1 0 0
1 1 1

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

Funcționarea "dacă ceva" - următoarele (implicații)

Această operațiune leagă două expresii logice simple, dintre care prima este o afecțiune, iar cea de-a doua este consecința acestei afecțiuni.
Aplicații aplicate:
dacă a, apoi în; Și implică; Dacă este atunci; A → V.
Tabelul rezervorului:
A.B.A → B.
0 0 1
0 1 1
1 0 0
1 1 1

Rezultatul operației de urmărire (implicare) este fals numai atunci când premisa este adevărată, iar concluzia (consecința) este falsă.

Funcționare "și apoi numai dacă în" (echivalență, echivalență)

Desemnarea aplicabilă: a ↔ B, a ~ V.
Tabelul rezervorului:
A.B.A↔B.
0 0 1
0 1 0
1 0 0
1 1 1

Funcționarea "Adăugarea modulului 2" (Xor, cu excepția sau, disjuncția strictă)

Desemnarea aplicabilă: A XOR B, A ⊕ V.
Tabelul rezervorului:
A.B.A⊕B.
0 0 0
0 1 1
1 0 1
1 1 0

Rezultatul funcționării echivalenței este adevărat numai atunci când a și în același timp este adevărat sau simultan fals.

Prioritatea operațiunilor logice

  • Acțiuni în paranteze
  • Inversiune
  • Conjuncție (&)
  • Disjuncția (v), cu excepția sau (Xor), suma modulului 2
  • Implicație (→)
  • Echivalență (↔)

Perfect Formular normal disjunctiv

Perfect disjunctiv formula normală (SDNF) este o formulă echivalentă, care este o disjuncție a conjuncțiilor elementare, care are proprietăți:
  1. Fiecare componentă logică a formulei conține toate variabilele incluse în funcția f (x 1, x 2, ... x N).
  2. Toți termenii logici ai formulelor sunt diferite.
  3. Nici un termen logic nu conține o variabilă și o negociere.
  4. Nici un termen logic de formula nu conține aceeași variabilă de două ori.
SDNF poate fi obținut sau utilizând tabelele adevărului sau utilizând transformări echivalente.
Pentru fiecare funcție, SDNF și SCFF sunt determinate singure până la permutarea.

Perfect formă normală conjunctivă

Formula de formulare normală conjunctivă perfectă (SCPF)este echivalentă cu formula ei, care este o conjuncție a disjuncțiilor elementare care satisfac 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 dată o variabilă o dată.
  4. Nici o disjuncție elementară conține o variabilă și o negociere.

La construirea nodurilor computerizate separate, este destul de des necesar să rezolvăm problema construirii circuitelor logice funcționale pentru funcțiile specificate. Pentru aceasta, este suficient să fie că afirmația adevărată corespunde faptului că lanțul conduce curentul, iar lanțul fals este rupt.

Operațiunile logice ale conjuncției, disjuncției, inversiunii sunt implementate într-un computer utilizând următoarele scheme elementare.

Conjuncția este un element logic "și":

Acest element efectuează funcționarea multiplicării logice (conjuncție): F \u003d x 1 ù x 2 ùx 3 ù ... ùx n; și are n intrări și o ieșire.

Disjuncția este un element logic "sau":

Acest element efectuează funcționarea adăugării logice (disjuncționare): f \u003d x 1 ú x 2 úx 3 ú ... úx n; și are n intrări și o ieșire.

Inversiunea este un element logic "nu":

Acest element efectuează funcționarea negării logice (inversiune): f \u003d; Și are o intrare și o singură cale de ieșire.

Schemele funcționale complexe pot fi proiectate din principalele elemente logice folosind legile de bază ale algebrei booleene

Exemplu de sarcină de testare

Sarcina:

Dana funcția,

1. Faceți o schemă logică funcțională pentru această caracteristică.

2. Simplificați funcția logică (folosind legile algebrei booleene) și verificați conversia în tabelul adevărului.

3. Faceți o schemă logică funcțională pentru funcția simplificată.

Performanţă:

1. Faceți un tabel de adevăr pentru o anumită funcție:

X. Y.

2. Faceți o schemă logică funcțională pentru o anumită funcție:

3. Simplificați funcția specificată utilizând legile algebrei booleene:

a) Potrivit Legii de Morgana - 9

b) În conformitate cu Legea Idempotency - 13

c) Denial refuzul legii - 1

d) Dreptul de distribuție - 6

e) Proprietăți 1 și 0 - 19

e) Proprietăți 1 și 0 - 16

Astfel, funcția simplificată are forma:

4. Faceți un tabel de adevăr pentru funcția simplificată:

X. Y.

Astfel, compararea tabelelor Adevărului pentru funcțiile inițiale și simplificate (ultimele coloane), încheiem cu privire la corectitudinea transformării efectuate.

5. Faceți o schemă logică funcțională pentru funcția simplificată:

Sarcina de testare

Funcția F (x, y) este dată, numărul funcției din tabel corespunde numărului de secvență al elevului de pe listă.

4. Faceți o schemă logică funcțională pentru această caracteristică.

5. Simplificați funcția logică (folosind legile de algebră booleană) și verificați conversia în tabelul adevărului.