Curs 6. Forma canonică a formulelor logice care sunt utilizate în calculator
6.1 termeni cheie. Conceptul PDNF și SKNF.
6.2 Algoritmi pentru construirea și PDNF SKNF pe masa de adevăr.
Fiecare formulă logică ce definește unele funcții booleene. În același timp, este clar că putem scrie un număr infinit de formula sa este pentru orice funcție booleană (a se vedea. Sarcina 3 la § 3.6). Într-adevăr, în cazul în care există cel puțin o formulă care exprimă funcția Boolean, folosind apoi transformarea identității, este posibil să se schimbe această formulă construind arbitrar complex cu formula echivalentă, de exemplu,
un ≡ xor b (a și (nu b)) sau ((nu a) și b).
Unul dintre principalele obiective ale boolean - găsirea unor forme canonice (de exemplu, formulele construite de o anumită regulă, canonul ..), precum și cele mai simple formule care reprezintă funcții booleene.
Definiție 1. Dacă funcția logică este exprimată printr-o disjuncție, conjuncție și negație variabilelor, o astfel de prezentare se numește normală.
Printre formele normale secreta cele în care funcțiile sunt scrise într-un mod unic. Acestea sunt numite perfecte.
Un rol aparte în algebra claselor logice juca forme perfecte disjuncte și conjunctive normale (PDNF și SKNF). Acestea se bazează pe conceptul de disjuncție elementar și conjuncție elementară.
Definiție 2. Formula este numită conjuncția elementară, dacă este o combinație de una sau mai multe variabile, luate cu sau fără negarea negației. O variabilă sau negația este considerată un termen coroborat elementar.
Exemplul 1. conjunctions Formula sunt elementare; primele două dintre ele - un termen-.
3. Determinarea formulei se numește o formă normală disjunctivă (DNF), în cazul în care nu se repetă disjuncție elementar conjuncțiilor. DNP poate fi scris ca, în cazul în care fiecare Ai - conjuncție elementară.
Exemplul 2. Aici sunt două forme normale disjunctive:
Definiție 4. O formulă în variabile k se numește o formă normală disjunctivă perfectă (PDNF) în cazul în care:
1) A este un DNF în care fiecare conjuncție elementară este o combinație de variabile k, iar pe poziția i-lea această conjuncție este în valoare de o variabilă sau negația ei;
2) toate conjuncția elementare astfel DNP sunt distincte.
Sarcina 1. Formule:
;
;
Stabili dacă acestea sunt PDNF două variabile.
Decizie. Formula A este PDNF două variabile. Formulele B și C nu sunt PDNF. Formula B depinde de trei variabile, dar numărul de variabile în mai puțin de trei conjuncții elementare. Formula cu variabile x2 de două ori incluse în aceeași conjuncția elementară.
formă normală disjunctivă perfectă este o formulă construită pe reguli bine definite pentru a în ordinea conjuncțiilor elementare (termeni disjuncte) în aceasta. Este un exemplu de reprezentare neambiguă a funcției booleene ca (algebric) înregistrarea formular.
Definiție 5. Formula este numită disjuncției elementar, dacă este o disjuncție (probabil un termen) variabile și negații variabilelor.
Exemplul 1 dau trei disjuncție elementar:
.
6. Determinarea formulei se numește o formă normală conjunctivă (CNF) în cazul în care nu se repetă conjuncție disjuncții elementare.
CNF este scris sub forma, în cazul în care fiecare Ai - disjuncție elementar.
Ele sunt forma normala conjunctiva.
Definiție 7. O formulă în variabile k este numit perfecta forma normala conjunctiva (SKNF) în cazul în care:
1) Care este CNF, în care fiecare disjuncție elementar este o disjuncție de variabile k, iar pe poziția i-lea disjuncției este în valoare de o variabilă x sau negația ei;
2) toate disjuncției elementar CNF într-o astfel reciproc diferite.
2. Formulele țintă și. Stabili dacă acestea sunt SKNF.
Decizie. Formula A este SKNF și Formula B nu este SKNF ca variabilă dublu intră primul termen conjunctive, în plus, numărul de variabile din fiecare disjuncție elementar mai puțin de trei, în timp ce formula depinde de trei variabile.
Întrebare. Are orice funcție logică poate fi reprezentată într-una din formele perfecte canonice considerate?
Răspuns. Da, orice funcție booleană, nu identic egal cu 0 sau 1, pot fi reprezentate ca PDNF sau SKNF.
Pentru a susține această afirmație este o teoremă.
Teorema 1. Fie - funcția booleană de n variabile, nu identic zero. Apoi, există este forma perfectă normală disjunctivă, care exprimă funcția f.
Un algoritm pentru construirea de masă PDNF de adevăr:
1. Tabelul de adevăr nota setul de variabile pe care valoarea funcției f este egal cu unitatea.
2. Scrieți fiecare marcate prin conjuncția unui set de toate variabilele în modul următor: în cazul în care valoarea unei variabile în acest set este 1, coroborat includ variabila în sine, în caz contrar - negația.
3. conjuncțiile Toate primite în legătură cu disjuncție.
Corolar Teorema 1. Pentru orice formulă poate fi considerat că este echivalentul DNF.
Exemplul 3 necesară pentru a construi o formulă pentru funcția f (x1, x2 x3 ..) definită de un tabel de adevăr:
Folosind algoritmul descris mai sus pentru a construi PDNF-l:
Teorema 2. Fie - funcția booleană de n variabile, nu identic egal cu unu. Apoi, există este forma perfecta normala conjunctiva, care exprimă funcția f.
Bazat pe Teorema 2 putem propune următorul algoritm pentru construirea SKNF funcția de tabelă de adevăr.
Un algoritm pentru construirea SKNF a tabelului de adevăr ^
1. Tabelul de adevăr nota setul de variabile pe care valoarea funcției f este egal cu zero.
2. Scrieți fiecare set distins disjungerea toate variabilele în felul următor: dacă valoarea unei variabile în acest set este egal cu 0, coroborat includ variabila în sine, în caz contrar - negația.
3. Operațiunile de disjuncție asociază toate primite de colaborare.
Consecinta Teorema 2. Pentru orice formulă poate fi considerat că este echivalentul cnf.
Exemplul 4. Funcția implicație expres prin operații negare disjuncție și conjuncție. Pentru a face acest lucru, vom scrie funcțiile implicație tabelului de adevăr: