Concepte de bază ale algebrei logice

Descriere: Algebra logică este o anumită parte a logicii matematice, numită calculul propozițional. O afirmație este o afirmație care poate fi adevărată ("da") sau falsă ("nu"). Același cuvânt nu poate fi atât adevărat, cât și fals.

Mărime fișier: 68.13 KB

Lucrarea a fost descărcată: 30 de persoane.

Dacă această lucrare nu vă convine în partea de jos a paginii, există o listă de lucrări similare. De asemenea, puteți utiliza butonul de căutare

Subiect 1.5. Concepte de bază ale algebrei logice

1.5.1. Definiții de bază ale algebrului logicii

1.5.2. Legătura dintre algebra logică și codarea binară

1.5.3. Elemente logice elementare și elemente logice

1.5.4. Funcții booleene arbitrare # 150; DNP și CNF

1.5.5. Întrebări de control pe tema "Concepte de bază ale algebrei logice"

1.5.6. Sarcini de testare pe tema "Concepte de bază ale algebrei logice"

1.5.1. Definiții de bază ale algebrului logicii

Algebra logicii # 150; o anumită parte a logicii matematice, numită calculul propozițional.

declarație # 150; o afirmație care poate fi adevărată ("da") sau falsă ("nu"). Același cuvânt nu poate fi atât adevărat, cât și fals. Prin urmare, în algebra logică sunt considerate numai două semnificații ale propozițiilor:

adevărat (îi este atribuită o valoare de 1);

false (îi este atribuită o valoare de 0).

algebra logicii, în afară de meaningfulness semantică a declarațiilor face posibilă determinarea componentelor declarații false sau adevărate (funcții) prin metode algebrice.

Variabilele logice și funcțiile din ele, care pot avea doar 2 valori # 150; 0 și 1 se numesc variabile și funcții logice sau booleene. Valoarea unei funcții logice depinde de combinația specifică a valorilor tuturor argumentelor sale n - un set de argumente.

Funcția logică a n argumentelor binare este complet determinată de tabelul de adevăr. Tabelul de adevăr - un tabel în care se înregistrează valorile funcției logice pentru fiecare din cele 2 n seturi de argumente de intrare. Pentru a defini în întregime o funcție logică, este suficient să enumerăm fie toate seturile pentru care această funcție are valori egale cu 1. Sau toate seturile pentru care această funcție are valori egale cu 0.

1.5.2. Legătura dintre algebra logică și codarea binară

unitate logică matematică algebră este foarte convenabil pentru a descrie hardware-ul computerului funcționează, din moment ce sistemul principal de numărul cu care computerul se execută, un sistem binar în care sunt utilizate numai numerele 1 și 0.

Din aceasta urmează:

aceleași dispozitive informatice pot fi utilizate pentru procesarea și stocarea atât a informațiilor numerice reprezentate în sistemul binar cât și a variabilelor logice;

în etapa de proiectare a algebrei logica hardware poate simplifica în mod semnificativ funcțiile logice care descriu funcționarea circuitelor de calculator și, prin urmare, reduce numărul de elemente logice elementare din care sunt zeci de mii de noduri sunt computerul principal.

Datele și comenzile din computer sunt reprezentate ca secvențe binare cu structură și lungime diferite. Există diferite moduri fizice de codare a informațiilor binare. În dispozitive electronice ale unui calculator, unitățile binare sunt cel mai adesea codificate cu un nivel de tensiune mai mare decât zerouri binare, de exemplu, așa cum se arată în Fig. 1.5.2-1.

Element logic al computerului # 150; aceasta face parte dintr-un circuit logic electronic care implementează o funcție logică elementară.

elemente logice simple ale calculatoarelor sunt circuite electronice, "AND", "SAU", "NU", "ȘI # 150; NU", "SAU # 150; NU". 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 simplifică înregistrarea și înțelegerea circuitelor logice complexe.

Lucrarea elementelor logice, precum și funcțiile logice, este descrisă cu ajutorul tabelelor de adevăr.

1.5.3. Elemente logice elementare și elemente logice

Funcțiile logice care depind de una sau două variabile sunt numite funcții elementare. Funcțiile de bază ale logicii includ următoarele funcții elementare: negare; înmulțire logică; negarea de la multiplicarea logică; adăugare logică; negarea adăugării logice; echivalență; negarea echivalenței.

Funcția de negare este o funcție logică a unui argument, care ia valoarea 1. Dacă argumentul este 0. și ia valoarea 0. Dacă argumentul este 1. și se numește negare (inversiune) sau funcție logică NOT.

Înregistrarea funcției logice NU # 150;. în cazul în care bara peste variabila # 150; inversiune semn. Funcția logică NU de la un argument este descrisă de tabelul de adevăr:

Înregistrarea funcțiilor logice:

Elementul logic "OR # 150; NU "constă dintr - un element" OR "și un invertor și

Aceasta negaționează rezultatul funcției logice "OR". Denumirea convențională pe schemele structurale ale elementului logic "SAU # 150; NU "cu două intrări este prezentată în Fig. 1.5.3-5.

În expresiile complexe care utilizează operații logice AND, se efectuează mai întâi operațiile NEBO NOT negating. apoi operațiile conjuncției I și, în cele din urmă, operațiile de disjuncție OR.

Pentru a schimba secvența de operațiuni specificată, parantezele trebuie utilizate în expresii.


1.5.4. Funcții booleene arbitrare # 150; DNP și CNF

Să presupunem că o funcție logică arbitrară a argumentelor n este dată de un singur set de argumente, la care această funcție ia valoarea 1.

Formam o conjuncție (funcția logică ȘI) a tuturor n argumente argumente în respectivul set egal cu 0, ia inversiunea semn, ca argumente egale cu 1 din respectivul set, - fără a marca inversiune, deoarece, conform definiției conjuncției la funcția logică și presupune o valoare de 1. este necesar ca toate argumentele să fie egale cu 1.

Exemplul 1.5.4-1. Se dă o funcție logică a 4 argumente X1, X2, X3, X4. care ia valoarea 1 pentru setul X1 = 0, X2 = 1, X3 = 1, X4 = 0 și 0 pentru toate celelalte seturi.

Să compunem expresia pentru această funcție:

Să presupunem că o funcție logică arbitrară a argumentelor n este dată de un singur set de argumente, la care această funcție ia valoarea 0.

Form disjunctia (OR logic funcția) a tuturor argumentelor n, după cum urmează: Cazul egal cu 0 într-un set predeterminat, să ia fără inversare semn, ca un argument al unui set predeterminat 1. - cu o inversare semn, deoarece, conform definiției funcției logice disjuncție la SAU a fost setat la 0. Toate argumentele trebuie să fie 0.

Exemplul 1.5.4-2. O funcție logică a patru argumente X1, X2, X3 este dată. X4. care ia valoarea 0 pentru următorul set X1 = 0, X2 = 0, X3 = 1, X4 = 1 și 1 pentru toate celelalte seturi.

Să compunem expresia pentru această funcție:

O funcție logică arbitrar definit pe listă toate seturile de argumente, pe care le primește valoarea 1 este determinată după cum urmează: pentru fiecare dintre aceste seturi este compus conjuncție, disjuncție și apoi au format toate aceste conjuncții.

Exemplul 1.5.4-3. Să presupunem că funcția 4 a argumentelor X1, X2, X3, X4 are valoarea 1 pentru seturi:

X1 = 1X2 = 0X3 = 1X4 = 0

X1 = 0 X2 = 0 X3 = 1X4 = 1

X1 = 1X2 = 1X3 = 0X4 = 1

și 0 pentru toate celelalte seturi.

Apoi, funcția va arăta astfel:

Pentru oricare dintre următoarele seturi de funcții F (X1, X2, X3, X4) va reprezenta disjunctiile audio 1 și restul 0. adică va fi egal cu 1. iar pe seturile rămase va fi o disjuncție a unor zerouri, adică va fi 0.

O funcție logică arbitrar definit pe listă toate seturile de argumente, pe care le primește valoarea 0 este definită după cum urmează: pentru fiecare dintre aceste seturi este compus disjuncție, și apoi este format din conjuncția tuturor disjuncțiilor.

Exemplul 1.5.4-4. Să presupunem că este dată o funcție de 3 argumente F (X1, X2, X3). care ia valoarea 0 pentru seturi

și 1 pentru toate celelalte seturi.

Apoi, funcția formată în acest fel va arăta astfel:

Pentru oricare dintre următoarele seturi de funcții F (X1, X2, X3) va fi zero, iar conjuncția unităților rămase, adică este egal cu 0. în timp ce seturile rămase vor fi conjuncției unor unități, adică egal cu 1.

Din cele de mai sus, putem trage următoarea concluzie: o funcție logică arbitrară a argumentelor n poate fi exprimată prin intermediul funcțiilor logice AND, OR, NOT (conjuncție, disjuncție, negare).

Funcțiile logice, care sunt disjuncții ale membrilor individuali, fiecare dintre care este la rândul său o funcție care conține doar conjuncții și inversiuni, se numesc funcții logice ale formei disjunctive.

Funcțiile logice ale formei disjunctive, în care inversiunea se aplică numai direct argumentelor, de exemplu, dar nu unor funcții mai complexe, cum sunt, de exemplu, funcțiile disjunctive normale.

Dacă fiecare membru al unei funcții normale disjunctive de n argumente conține toate n argumentele, unele dintre ele având semnul inversiunii și o parte fără ea, atunci funcția este numită perfectă (SDNF). De exemplu, funcția

este un CDNF.

Fiecare termen al unui astfel de form devine 1 numai pentru un singur set de argumente, iar numărul de termeni este egal cu numărul de seturi diferite care inversează funcția în 1.

În funcțiile normale disjunctive imperfecte ale n argumentelor, unii membri conțin mai puțin de n argumente. Acești membri iau valoarea 1 pentru mai multe seturi de argumente. Prin urmare, numărul de membri în forme imperfecte este mai mic decât numărul membrilor în forme perfecte ale acelorași funcții.

este o formă normală conjunctivă normală a funcțiilor logice (SKNF).

Exemplul 1.5.4-5. Scrieți o expresie pentru o funcție care ia valoarea 1 pe seturile 2 și 6.

Să scriem numerele 2 și 6 în sistemul binar:

2 în sistemul binar # 150; 10 (sau 010),

6 în sistemul binar # 150; 11 0.

Aceasta înseamnă că funcția dorită va fi o funcție a trei variabile: X1, X2, X3.

Seturile pe care funcția devine 1.

Formăm expresia pentru funcție

Care este algebra logicii?

Care este utilizarea algebrei booleene (algebra logică)?

Ce se numește o zicală?

Care sunt semnificațiile afirmațiilor?

Ce inseamna algebra studiului logic?

Ce variabile se numesc logice sau booleene?

Ce funcții sunt numite logice?

Ce determină funcția logică?

Ce este un tabel de adevăr?

Care funcții logice sunt numite funcții elementare?

Ce funcție se numește funcția de negare?

Cum este descrisă funcția de negare?

Ce funcție se numește funcția de multiplicare logică?

Cum este descrisă funcția de multiplicare logică?

Ce funcție se numește funcția de adăugare logică?

Cum se descrie funcția de adăugare logică?

Cum este descrisă funcția de negare din înmulțirea logică?

Cum este descrisă funcția de negare din adăugarea logică?

Care este ordinea operațiilor de negare, conjuncție și disjuncție în expresii logice complexe?

Cum să exprimați o funcție logică arbitrară care are o valoare de 1 pe un singur set de argumente?

Cum să exprimați o funcție logică arbitrară care are valoarea 0 pe un singur set de argumente?

Așa cum și-a exprimat în funcții definite seturi arbitrare de argumente logice listare pe care le primește valoarea 1.

Așa cum și-a exprimat în funcții definite seturi arbitrare listare logice de argumente pe care le ia valoarea 0.

Ce funcții logice se numesc funcții logice ale unei forme disjunctive?

Ce funcții logice se numesc funcții logice ale unei forme conjunctive?

Care sunt funcțiile logice numite funcții normale?

Ce funcții logice sunt numite perfecte?

Care este diferența dintre funcțiile logice ale formelor perfecte și imperfecte.


1.5.6. Sarcini de testare pe tema "Concepte de bază ale algebrei logice"

Funcția logică este

funcție normală disjunctivă

  1. funcția normală conjunctivă normală (SKNF)

funcția normală disjunctivă funcțională (SDNF)

Algebra logicii # 150; aceasta este

  1. o anumită parte a logicii matematice, numită calculul propozițional
  2. o parte din matematică care se ocupă de calculul expresiilor
  3. parte a matematicii care se ocupă cu calcularea expresiilor algebrice folosind legile logicii

Variabilele logice și funcțiile logice pot lua următoarele valori ...

Funcția logică este complet determinată

  1. adevăr tabel
  2. un singur set de argumente
  3. zero set de argumente
  4. tabel de seturi de argumente

Funcțiile logice elementare depind de

  1. din unul sau două argumente
  2. din trei argumente
  3. din patru argumente
  4. din orice număr de argumente

Ordinea operațiilor logice în expresii logice complexe este următoarea

  1. negare, multiplicare logică, adăugare logică
  2. înmulțire logică, negare, adăugare logică
  3. înmulțire logică, adăugare logică, negare
  4. orice

Funcțiile logice sunt numite funcții normale

  1. Dacă inversiunea este aplicată direct în argumente
  2. Dacă inversiunea se aplică funcțiilor logice individuale
  3. Dacă inversiunea este aplicată întregii funcții logice
  4. nu există un răspuns corect


Funcțiile logice sunt numite perfecte

  1. dacă fiecare membru al unei funcții normale disjunctive (sau conjunctive) a n conține toate argumentele n
  2. dacă fiecare membru al unei funcții normale disjunctive (sau conjunctive) de n argumente conține n argumente cu negări
  3. dacă fiecare membru al unei funcții normale disjunctive (sau conjunctive) a argumentelor n conține cel puțin un argument cu negare
  4. dacă fiecare membru al unei funcții normale disjunctive (sau conjunctive) de n argumente conține toate n argumentele fără negări

Dacă funcția logică presupune valoarea 0 în seturi 0, 2, 3, 5, se ia valoarea 1

  1. pe seturile 1, 4, 6, 7
  2. pe seturi 4, 5, 7
  3. pe seturi 6, 7
  4. pe seturile 1, 2, 3, 4, 5

Funcția normală conjunctivă normală (SKNF este

Articole similare