Eu și algebra logică

Definiție 1. Funcția algebrei variabilelor logice este orice funcție a variabilelor n ale căror argumente iau două valori 1 și 0, iar funcția în sine are una din două valori: 1 sau 0.

Fiecare formula algebrică a logicii este o funcție a algebrului logicii. Formula identică, identică și apoi identică, este o funcție constantă.

Se poate arăta că orice funcție a algebrei logice poate fi reprezentată sub forma unei formule de logică și această reprezentare este după cum urmează:

(*)

Formula (*) poate fi transformată într-o formulă care conține numai variabile de expresie elementară și are următoarele proprietăți de perfecțiune (sau proprietăți (C)):

1) fiecare sumă logică a formulei conține toate variabilele care apar în funcție;

2) toate sumele logice ale formulei sunt diferite;

3) nici o summă logică a formulei nu conține aceeași variabilă și negarea ei;

4) nici o summă logică a formulei nu conține aceeași variabilă de două ori.

Folosind tabelul de adevăr care definește funcția, este ușor să obțineți formula corespunzătoare algebricii logice posedând proprietățile (C). Într-adevăr, pentru fiecare set de valori ale variabilelor pe care funcția ia valoarea 1, vom scrie conjuncția variabilelor propoziționale elementare, luând pentru termenul de conjuncție

Eu și algebra logică
, dacă valoarea
Eu și algebra logică
pe setul specificat de valori ale variabilelor există 1 și negarea
Eu și algebra logică
, dacă valoarea
Eu și algebra logică
0. Disjuncția tuturor conjuncturilor obținute în acest fel este, de asemenea, formula dorită.

Definiție 2. O conjuncție elementară a variabilelor n este conjuncția variabilelor sau negările lor.

Definiția 3. O formă normală disjunctivă (DNF) cu formula A este o formulă echivalentă cu ea, care este o disjuncție a conjuncțiilor elementare.

Definiția 4. O formă normală disjunctivă perfectă (SDNF) cu formula A se numește DNF A. care posedă proprietățile (C).

CDNF A poate fi obținut în două moduri: a) folosind un tabel de adevăr (vezi mai sus); b) prin transformări echivalente.

Regula pentru obținerea unui CDNF din Formula A utilizând transformări echivalente.

1. Pentru formula A, obținem orice DNF.

2. Din DNP A, prin transformări echivalente, obținem SDNF, obținând succesiv realizarea celor patru proprietăți ale SDNF:

1) Fie B un summand de DNF care nu conține

Eu și algebra logică
. Apoi, este necesar să notăm termenul B din DNF A pentru termenul respectiv.

2) Dacă există doi termeni neidentificați în DNP A

Eu și algebra logică
, atunci extra ar trebui să fie aruncat, pentru că.

3) Dacă într-un anumit termen B în DNP A variabila

Eu și algebra logică
intră de două ori, variabila suplimentară trebuie eliminată, deoarece
Eu și algebra logică
.

4) Dacă termenul B din DNP A conține o conjuncție

Eu și algebra logică
, atunci variabila suplimentară trebuie eliminată, deoarece
Eu și algebra logică
, și, prin urmare,
Eu și algebra logică
, și o declarație falsă din disjuncție poate fi aruncată (în virtutea echivalenței
Eu și algebra logică
).

Definiția 5. O disjuncție elementară a variabilelor n este o disjuncție a variabilelor sau negările lor.

Definiția 6. O conjuncție de formă normală (CNF) cu formula A este o formulă echivalentă cu aceasta, care este o combinație de disjuncții elementare.

Definiția 7. O formă normală conjunctivă ideală cu formula A (SKNF A) se numește CNF A. Aceasta satisface patru proprietăți:

1) toate disjuncțiile elementare incluse în CNF A. conțin toate variabilele;

2) toate disjunctiile elementare care fac parte din CNF A. sunt diferite;

3) fiecare disjuncție elementară inclusă în CNF A. conține o singură variabilă;

4) nu o singură disjuncție elementară inclusă în CNF A. conține o variabilă și negarea ei.

SKNF A poate fi obținut în două moduri: a) folosind o tabelă de adevăr (folosind legea dualității, folosim tabelul de adevăr

Eu și algebra logică
, și, luând negarea
Eu și algebra logică
, obținem SKNFA); b) prin transformări echivalente.

Regula pentru obținerea SKNF de la Formula A utilizând transformări echivalente.

1. Pentru formula A, obținem orice CNF.

2. Din CNF A, prin transformări echivalente, obținem SKNF A. realizând în mod consecvent realizarea a patru proprietăți ale SKNF.

1) Dacă disjuncția elementară B. inclusă în CNF A. nu conține o variabilă

Eu și algebra logică
, apoi înlocuim B cu.

2) Dacă într-o disjuncție elementară B o variabilă

Eu și algebra logică
, intră de două ori, variabila suplimentară trebuie eliminată, deoarece
Eu și algebra logică
.

3) Dacă CNF A conține două disjuncții elementare identice, atunci se poate renunța, deoarece

Eu și algebra logică
.

4) Dacă există o pereche în disjuncția elementară

Eu și algebra logică
, acesta poate fi aruncat, deoarece
Eu și algebra logică
, și adevărata afirmație a conjuncției poate fi aruncată (în virtutea echivalenței
Eu și algebra logică
).

Exemplul 1. Găsiți formula care definește funcția $ (x, y, z) dintr-un tabel de adevăr dat:

Soluția. Folosind regula pentru obținerea unei formule pentru algebra logică din tabelul de adevăr pentru funcția Φ (x, y, z), obținem:

.

Simplificând această formulă, obținem:

Eu și algebra logică

Astfel, se poate presupune formula dorită care definește funcția Φ (x, y, z)

Eu și algebra logică
, sau
Eu și algebra logică
, sau în alte formule echivalente.

Exemplul 2. Următoarea formulă conduce la SDNF, care a condus-o anterior prin transformări echivalente cu DNF :.

Eu și algebra logică

Exemplul 3. Pentru formula din Exemplul 2, găsiți CDNF prin compilarea unui tabel de adevăr.

Soluția. Să compunem tabelul de adevăr pentru formula.

Exemplul 4. Pentru formula din Exemplul 2, găsiți SKNF prin transformări echivalente, care l-au condus anterior la CNF.

Soluția. Din exemplul 2:

.

Exemplul 5. Pentru formula din Exemplul 2, găsiți SKNF scriind DNF înaintea negării sale și apoi utilizând formula dualității.

Toate formulele algebrice ale logicii sunt împărțite în trei clase: 1) identice; 2) identic fals; 3) fezabil.

Formula A este numită satisfăcătoare. dacă ia valoarea 1 pe cel puțin un set de valori ale variabilelor care intră în ea și nu este identic adevărat.

Teorema. Pentru formula algebră a logicii să fie identic adevărată (falsă), este necesar și suficient ca orice disjuncție elementară (conjuncție) care apare în CNF A (DNP A) să conțină o variabilă și negarea ei.

Exemplul 6. Formula va fi identică, identică, falsă sau realizabilă?

Soluția. Să dăm un exemplu într-o formă normală:

Derivarea DNP nu este identică, deoarece fiecare conjuncție elementară nu conține o variabilă și negarea acesteia. Prin urmare, formula originală este identică sau posibilă. Transformăm această formulă la CNF.

Acest produs nu este identic, deoarece suma elementară

Eu și algebra logică
Nu este identic adevărat, de aceea este posibil.

1.34. Folosind tabelul de adevăr, găsiți formulele care definesc funcțiile

Eu și algebra logică
,
Eu și algebra logică
,
Eu și algebra logică
,
Eu și algebra logică
, și să le oferiți un aspect mai simplu:

1,35. lăsa

Eu și algebra logică
- Funcția booleană care ia valoarea 1 dacă și numai dacă exact una dintre variabile are valoarea 1. Faceți un tabel pentru funcție
Eu și algebra logică
și exprimă această funcție prin operațiile logice de bază.

1.36. Noi numim funcția majorității

Eu și algebra logică
Funcția booleană a trei variabile, ale căror valori iau majoritatea variabilelor.

a) Creați un tabel care definește funcția majorității și exprimați această funcție prin operațiile de bază.

b) Simplificați expresia

Eu și algebra logică
.

1.37. Funcțiile booleene

Eu și algebra logică
se numește dublă în ceea ce privește funcția booleană
Eu și algebra logică
, dacă

.

Pentru fiecare funcție booleană a două variabile, găsiți funcția booleană duală.

1,38. Funcțiile booleene

Eu și algebra logică
se numește:

a) păstrarea 0 dacă;

b) păstrarea 1 dacă.

Printre funcțiile booleene a una și două variabile, găsiți toate funcțiile care păstrează 1 și toate funcțiile păstrând 0.

1.39. Pentru formulele următoare, găsiți CDNF și SKNF, fiecare în două moduri (prin egalizarea transformărilor și folosirea tabelelor de adevăr):

1,40. Găsiți CDNF pentru orice formulă identică, care conține: 1) o variabilă, 2) două variabile, 3) trei variabile.

1.41. Găsiți SKNF pentru orice formulă identică, care conține: 1) o variabilă, 2) două variabile, 3) trei variabile.

1.42. Dovediți echivalența formulelor

Eu și algebra logică
și
Eu și algebra logică
prin compararea formelor lor normale (conjunctive sau disjunctive).

1.43. Găsiți cea mai simplă formă de formule având următoarele forme normale perfecte:

1,44. Folosind criteriul adevărului identic și falsitatea identică a formulei, pentru a stabili dacă formula dată este identică, identică, falsă sau realizabilă:

Articole similare