Forma normală conjunctivă a unei funcții logice. Forme conjunctive de reprezentare a funcţiilor logice
Forma normală conjunctivă este convenabilă pentru demonstrarea automată a teoremei. Orice formulă booleană poate fi convertită în CNF. Pentru a face acest lucru, puteți folosi: legea dublei negații, legea lui de Morgan, distributivitatea.
YouTube colegial
-
1 / 5
Formule în KNF:
¬ A ∧ (B ∨ C), (\ displaystyle \ neg A \ wedge (B \ vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E), (\ displaystyle (A \ vee B) \ wedge (\ neg B \ vee C \ vee \ neg D) \ wedge ( D \ vee \ neg E),) A ∧ B. (\ displaystyle A \ wedge B.)Formule nu în KNF:
¬ (B ∨ C), (\ displaystyle \ neg (B \ vee C),) (A ∧ B) ∨ C, (\ displaystyle (A \ wedge B) \ vee C,) A ∧ (B ∨ (D ∧ E)). (\ displaystyle A \ wedge (B \ vee (D \ wedge E)).)Dar aceste 3 formule care nu sunt în CNF sunt echivalente cu următoarele formule în CNF:
¬ B ∧ ¬ C, (\ displaystyle \ neg B \ wedge \ neg C,) (A ∨ C) ∧ (B ∨ C), (\ displaystyle (A \ vee C) \ wedge (B \ vee C),) A ∧ (B ∨ D) ∧ (B ∨ E). (\ displaystyle A \ wedge (B \ vee D) \ wedge (B \ vee E).)Construirea CNF-ului
Algoritm pentru construirea CNF
1) Scăpați de toate operațiile logice conținute în formulă, înlocuindu-le cu cele principale: conjuncție, disjuncție, negație. Acest lucru se poate face folosind formule echivalente:
A → B = ¬ A ∨ B, (\ displaystyle A \ rightarrow B = \ neg A \ vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B). (\ displaystyle A \ leftrightarrow B = (\ neg A \ vee B) \ wedge (A \ vee \ neg B).)2) Înlocuiți semnul de negație, referitor la întreaga expresie, cu semnele de negație, referitor la declarații de variabile individuale bazate pe formule:
¬ (A ∨ B) = ¬ A ∧ ¬ B, (\ displaystyle \ neg (A \ vee B) = \ neg A \ wedge \ neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B. (\ displaystyle \ neg (A \ wedge B) = \ neg A \ vee \ neg B.)3) Scăpați de semnele de dublă negație.
4) Aplicați, dacă este necesar, la operațiile de conjuncție și disjuncție proprietățile distributivității și formula de absorbție.
Un exemplu de construire a unui CNF
Să aducem la CNF formula
F = (X → Y) ∧ ((¬ Y → Z) → ¬ X). (\ displaystyle F = (X \ rightarrow Y) \ wedge ((\ neg Y \ rightarrow Z) \ rightarrow \ neg X).)Să transformăm formula F (\ stil de afișare F) la o formulă care nu conține → (\ stil de afișare \ săgeată la dreapta):
F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ wedge (\ neg (\ neg Y \ rightarrow Z) \ vee \ neg X) = (\ neg X \ vee Y) \ wedge (\ neg (\ neg \ neg Y \ vee Z) \ vee \ neg X).)În formula rezultată, transferăm negația la variabile și reducem dublele negative:
F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ wedge ((\ neg Y \ wedge \ neg Z) \ vee \ neg X).)De exemplu, următoarea formulă este scrisă în 2-CNF:
(A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C). (\ displaystyle (A \ lor B) \ land (\ neg B \ lor C) \ land (B \ lor \ neg C).)Simplu conjuncţie numit conjuncţie unu sau mai multe variabile, la acest fiecare variabil se intalneste nu Mai mult unu ori (sau în sine, sau a ei negare).
De exemplu, este o conjuncție simplă,
Disjunctiv normal formă(DNF) numit disjuncție simplu conjuncţii.
De exemplu, expresia este DNF.
Perfect disjunctiv normal formă(SDNF) numit asa de disjunctiv normal forma, la care v fiecare conjuncţie sunt incluse toate variabile dat listă (sau înșiși, sau al lor negări), în plus v unu și volum la felBine.
De exemplu, expresia este DNF, dar nu SDNF. Expresie
este SDNF.Definiții similare (cu înlocuirea conjuncției cu disjuncție și invers) sunt valabile pentru CNF și SKNF. Iată formulările exacte.
Simplu disjuncție numit disjuncție unu sau mai multe variabile, la acest fiecare variabil intra nu Mai mult unu ori (sau în sine, sau a ei negare) De exemplu, o expresie este o disjuncție simplă,
Conjunctiv normal formă(CNF) numit conjuncţie simplu disjuncţii(de exemplu, expresia este CNF).
O formă normală conjunctivă perfectă (SCNF) este o CNF în care fiecare disjuncție simplă conține toate variabilele listei date (fie ele însele, fie negațiile lor) și în aceeași ordine.
De exemplu, expresia
este SKNF.Iată algoritmii pentru trecerea de la o formă la alta. Desigur, în cazuri specifice (cu o anumită abordare creativă), utilizarea algoritmilor este mai laborioasă decât transformările simple folosind un anumit tip de această formă:
a) trecerea de la DNF la CNF
Algoritmul pentru această tranziție este următorul: punem două negații deasupra DNF și, folosind regulile de Morgan (fără a atinge negația superioară), aducem negația DNF înapoi la DNF. În acest caz, trebuie să deschideți paranteze folosind regula de absorbție (sau regula lui Blake). Negația (superioară) a DNF-ului obținut (din nou conform regulii de Morgan) ne oferă imediat CNF:
Rețineți că CNF poate fi obținut și din expresia inițială, dacă scoatem laîn afara parantezelor;
b) trecerea de la CNF la DNF
Această tranziție se realizează prin simpla deschidere a parantezelor (în acest caz, din nou, se folosește regula de absorbție)
Astfel, am primit DNF.
Tranziția inversă (de la SDNF la DNF) este asociată cu problema minimizării DNF. Acest lucru va fi discutat mai detaliat în Sec. 5, aici vom arăta cum să simplificăm DNF (sau SDNF) conform regulii lui Blake. Acest DNF este numit abreviat DNF;
c) abrevierea DNF (sau SDNF) prin regulă Blake
Aplicarea acestei reguli are două părți:
Dacă printre termenii disjunși din DNF există termeni
, apoi la întreaga disjuncție adăugăm termenul LA 1 LA 2. Facem aceasta operatie de mai multe ori (poate fi secventiala, poate fi simultan) pentru toate perechile posibile de termeni, iar apoi, aplicam absorbtia obisnuita;Dacă termenul adăugat a fost deja conținut în DNF, atunci poate fi eliminat cu totul, de exemplu,
sau
Desigur, DNF abreviat nu este definit în mod unic, dar toate conțin același număr de litere (de exemplu, există un DNF
, după ce i-ai aplicat regula lui Blake, poți ajunge la un DNF echivalent cu acesta):c) trecerea de la DNF la SDNF
Dacă unei conjuncții simple îi lipsește o variabilă, de exemplu, z, introduceți expresia în ea, apoi extindeți parantezele (în acest caz, nu scriem termeni disjunși repeți). De exemplu:
d) trecerea de la CNF la SKNF
Această tranziție se realizează într-o manieră similară celei precedente: dacă unei simple disjuncții îi lipsește o variabilă (de exemplu, z, apoi îi adăugăm o expresie (acest lucru nu schimbă disjuncția în sine), după care extindem paranteze folosind legea distribuției):
Astfel, SKNF este obținut din CNF.
Rețineți că CNF minim sau prescurtat este de obicei obținut din DNF-ul corespunzător.
Disjuncție simplă(disjuncție inclusivă) sau disjunct(English disjunct) este o disjuncție a uneia sau mai multor variabile sau a negațiilor acestora, iar fiecare variabilă apare nu mai mult de o dată.
Disjuncție simplă
- complet dacă fiecare variabilă (sau negația ei) apare în ea exact o dată;
- monoton dacă nu conţine variabile negative.
Forma normală conjunctivă, CNF(ing. forma normală conjunctivă, CNF) formă normală, în care funcția booleană are forma conjuncției mai multor propoziții simple.
Exemplu CNF: $ f (x, y) = (x \ lor y) \ land (y \ lor \ neg (z)) $
SKNF
Forma normală conjunctivă perfectă, SKNF(forma normală conjunctivă perfectă, PCNF) este un CNF care îndeplinește următoarele condiții:
- nu are aceleaşi disjuncţii simple
- fiecare disjuncție simplă este completă
Exemplu SKNF:$ f (x, y, z) = (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $
Teorema: Pentru orice funcţie booleană$ f (\ vec (x)) $, nu este egal cu identitatea, există un SKNF care o definește.
Dovada: Deoarece inversul funcției $ \ neg (f) (\ vec x) $ este egal cu unul pe acele tupluri pe care $ f (\ vec x) $ este egal cu zero, atunci SDNF pentru $ \ neg (f) (\ vec x) $ poate fi scris după cum urmează:
$ \ neg (f) (\ vec x) = \ bigvee \ limits_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n) ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ wedge x_ (2) ^ (\ sigma_ (2)) \ wedge ... \ wedge x_ (n) ^ (\ sigma_ (n) ))) $, unde $ \ sigma_ (i) $ denotă prezența sau absența negației pentru $ x_ (i) $
Găsiți inversul părților stânga și dreaptă ale expresiei:
$ f (\ vec x) = \ neg ((\ bigvee \ limits_ (f (x ^ (\ sigma_ (1))), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n) ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ wedge x_ (2) ^ (\ sigma_ (2)) \ wedge ... \ wedge x_ (n) ^ (\ sigma_ (n) ))))) $
Aplicând regula lui de Morgan de două ori expresiei obținute în partea dreaptă, obținem: $ f (\ vec x) = \ bigwedge \ limits_ (f (x ^ (\ sigma_1), x ^ (\ sigma_2), \ dots , x ^ (\ sigma_n)) = 0) $ $ (\ neg (x_1 ^ (\ sigma_1)) \ vee \ neg (x_2 ^ (\ sigma_2)) \ vee \ dots \ vee \ neg (x_n ^ (\ sigma_n) ))) $
Ultima expresie este SKNF. Deoarece SKNF este obținut din SDNF, care poate fi construit pentru orice funcție care nu este identic zero, se demonstrează teorema.
Algoritm pentru construirea SKNF conform tabelului de adevăr
- În tabelul de adevăr marchem acele seturi de variabile pe care valoarea funcției este egală cu $ 0 $.
- Pentru fiecare mulțime marcată, scriem disjuncția tuturor variabilelor după următoarea regulă: dacă valoarea unei variabile este $ 0 $, atunci variabila însăși este inclusă în disjuncție, în caz contrar negația ei.
- Conectăm toate disjuncțiile rezultate prin operații de conjuncție.
Un exemplu de construire a SKNF pentru mediană
1). În tabelul de adevăr marchem acele seturi de variabile pe care valoarea funcției este egală cu $ 0 $.
X y z $ \ langle x, y, z \ rangle $ 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 2). Pentru fiecare mulțime marcată, scriem conjuncția tuturor variabilelor după următoarea regulă: dacă valoarea unei variabile este $ 0 $, atunci includem variabila însăși în disjuncție, în caz contrar negația ei.
X y z $ \ langle x, y, z \ rangle $ 0 0 0 0 $ (x \ lor y \ lor z) $ 0 0 1 0 $ (x \ lor y \ lor \ neg (z)) $ 0 1 0 0 $ (x \ lor \ neg (y) \ lor z) $ 0 1 1 1 1 0 0 0 $ (\ neg (x) \ lor y \ lor z) $ 1 0 1 1 1 1 0 1 1 1 1 1 3). Conectăm toate disjuncțiile rezultate prin operații de conjuncție.
$ \ langle x, y, z \ rangle = (x \ lor y \ lor z) \ land (\ neg (x) \ lor y \ lor z) \ land (x \ lor \ neg (y) \ lor z) \ land (x \ lor y \ lor \ neg (z)) $
Exemple SKNF pentru unele funcții
Săgeata lui Pierce: $ x \ downarrow y = (\ neg (x) \ lor (y)) \ land ((x) \ lor \ neg (y)) \ land (\ neg (x) \ lor \ neg (y) ) $
Exclusiv sau: $ x \ oplus y \ oplus z = (\ neg (x) \ lor \ neg (y) \ lor z) \ land (\ neg (x) \ lor y \ lor \ neg (z)) \ land (x \ lor \ neg (y) \ lor \ neg (z)) \ land (x \ lor y \ lor z) $
Definiția 1.Monomiul conjunctiv (conjuncție elementară) din variabile se numește conjuncția acestor variabile sau negațiile lor.
De exemplu, Este o conjuncție elementară.
Definiția 2.Monomiul disjunctiv (disjuncția elementară) din variabile se numește disjuncția acestor variabile sau negațiile lor.
De exemplu, - disjuncție elementară.
Definiția 3. O formulă echivalentă cu o formulă de algebră propozițională dată și fiind o disjuncție de monomii conjunctive elementare se numește forma normală disjunctivă(DNF) din această formulă.
De exemplu,- DNF.
Definiția 4. O formulă echivalentă cu o formulă de algebră propozițională dată și fiind conjuncția monomiilor disjunctive elementare se numește forma normală conjunctivă(CNF) din această formulă.
De exemplu, - CNF.
Pentru fiecare formulă a algebrei propoziționale, se poate găsi un set de forme normale disjunctive și conjunctive.
Algoritm pentru construirea formelor normale
Folosind echivalențe ale algebrei logicii, înlocuiți toate operațiile din formulă cu cele de bază: conjuncție, disjuncție, negație:
Scapa de semnele de dubla negatie.
Aplicați, dacă este necesar, la operațiile de conjuncție și disjuncție proprietățile distributivității și formula de absorbție.
2.6. Formele normale disjunctive perfecte și conjunctive perfecte
Orice funcție booleană poate avea multe reprezentări sub formă de DNF și CNF. Un loc special printre aceste reprezentări îl ocupă perfect DNF (SDNF) și perfect CNF (SKNF).
Definiția 1. Forma normală disjunctivă perfectă(SDNF) este un DNF în care în fiecare monom conjunctiv fiecare variabilă din mulțime apare exact o dată și apare fie ea însăși, fie negația sa.
În mod constructiv, SDNF pentru fiecare formulă a algebrei propoziționale redusă la DNF poate fi definit după cum urmează:
Definiția 2. Forma normală disjunctivă perfectă(SDNF) a unei formule de algebră propozițională se numește DNF, care are următoarele proprietăți:
Definiția 3. Forma normală conjunctivă perfectă(SKNF) este un CNF în care în fiecare monom disjunctiv fiecare variabilă din mulțime apare exact o dată și apare fie ea însăși, fie negația sa.
Din punct de vedere structural, SKNF pentru fiecare formulă a algebrei propoziționale redusă la CNF poate fi definit după cum urmează.
Definiția 4. Forma normală conjunctivă perfectă(SKNF) a unei formule de algebră propozițională dată se numește CNF ei care satisface următoarele proprietăți.
Teorema 1. Fiecare funcție booleană a variabilelor care nu este identic falsă poate fi reprezentată în SDNF și, în plus, într-un mod unic.
Modalități de a găsi SDNF
1-a cale
a 2-a cale
selectați liniile în care formula ia valoarea 1;
compunem o disjuncție de conjuncții, cu condiția ca dacă o variabilă este inclusă într-o conjuncție cu valoarea 1, atunci scriem această variabilă, dacă are valoarea 0, atunci negația ei. Primim SDNF.
Teorema 2. Fiecare funcție booleană a variabilelor care nu este identic adevărată poate fi reprezentată în SKNF și, în plus, într-un mod unic.
Modalități de a găsi SKNF
1-a cale- folosind transformări echivalente:
a 2-a cale- folosind tabele de adevăr:
selectați liniile în care formula ia valoarea 0;
compunem o conjuncție de disjuncții, cu condiția ca dacă o variabilă este inclusă într-o disjuncție cu valoarea 0, atunci scriem această variabilă, dacă cu valoarea 1, atunci negația ei. Primim SKNF.
Exemplul 1. Trasează funcțiile CNF.
Soluţie
Să excludem pachetul „” folosind legile de transformare a variabilelor:
= / de Morgan și legile dublei negații / =
/ legi distributive / =
Exemplul 2. Aduceți formula la DNF.
Soluţie
Să exprimăm operațiile logice în termeni și:
= / vom referi negația la variabile și vom reduce dublele negative / =
= / legea distribuției /.
Exemplul 3. Scrieți formula în DNF și SDNF.
Soluţie
Folosind legile logicii, vom aduce această formulă la o formă care conține doar disjuncții ale conjuncțiilor elementare. Formula rezultată va fi DNF dorită:
Pentru a construi SDNF, vom alcătui un tabel de adevăr pentru această formulă:
Marcam acele rânduri ale tabelului în care formula (ultima coloană) ia valoarea 1. Pentru fiecare astfel de rând, scriem formula care este adevărată pe setul de variabile, al rândului dat:
linia 1:;
linia 3:;
linia 5:.
Disjuncția acestor trei formule va lua valoarea 1 numai pe seturile de variabile din rândurile 1, 3, 5 și, prin urmare, va fi forma normală disjunctivă perfectă dorită (SDNF):
Exemplul 4. Aduceți formula la SKNF în două moduri:
a) folosind transformări echivalente;
b) folosind tabelul de adevăr.
Soluţie:
Transformăm a doua disjuncție elementară:
Formula este:
b) alcătuiește un tabel de adevăr pentru această formulă:
Marcam acele rânduri ale tabelului în care formula (ultima coloană) ia valoarea 0. Pentru fiecare astfel de rând, scriem formula care este adevărată pe setul de variabile, al rândului dat:
randul 2:;
linia 6:.
Conjuncția acestor două formule va lua valoarea 0 numai pe seturile de variabile din liniile 2 și 6 și, prin urmare, va fi forma normală conjunctivă perfectă dorită (SCNF):
Întrebări și sarcini pentru soluții independente
1. Folosind transformări echivalente, aduceți formulele la DNF:
2. Folosind transformări echivalente, aduceți formulele la CNF:
3.Utilizați a doua lege distributivă pentru a converti DNF în CNF:
A)
;4. Convertiți DNF-urile date în SDNF-uri:
5. Convertiți CNF-ul dat în SKNF:
6. Pentru formulele logice date, construiți SDNF și SKNF în două moduri: folosind transformări echivalente și folosind tabelul de adevăr.
b)
;Forme normale disjunctive și conjunctive ale algebrei propoziționale. Pentru fiecare funcție a logicii afirmațiilor, puteți crea un tabel de adevăr. Problema inversă este, de asemenea, întotdeauna rezolvabilă. Să introducem mai multe definiții.
Conjuncții elementare (conjuncții) se numesc conjuncţii de variabile sau negaţii ale acestora, în care fiecare variabilă apare cel mult
o singura data.
Forma normală disjunctivă(DNF) este o formulă care are forma unei disjuncții de conjuncții elementare.
Propoziții elementare (propoziții) se numesc disjuncţii de variabile cu sau fără negaţii.
Forma normală conjunctivă(CNF) este o formulă care are forma unei conjuncții de disjuncții elementare.
Pentru fiecare funcție a algebrei propozițiilor, se poate găsi un set de forme normale disjunctive și conjunctive.
Algoritm pentru construirea DNF:
1. Accesați operațiuni booleene folosind formule de transformare echivalente.
2. Mergeți la formule cu negații apropiate, adică la o formulă în care negațiile sunt situate nu mai sus decât deasupra variabilelor - pentru a aplica legile lui de Morgan.
3. Extindeți paranteze - aplicați legile distribuției.
4. Luați termenii repeți o singură dată - legea idempotității.
5. Aplicați legile absorbției și semiabsorbției.
Exemplul 6. Găsiți formule DNF:.
Algebra booleană este valabilă principiul dualității... Este după cum urmează.
Funcția este numită dual la funcţia dacă. Acestea. pentru a găsi o funcție care este duală cu una dată, este necesar să construim negația funcției din negațiile argumentelor.
Exemplul 7. Găsiți funcția duală la.
Dintre funcțiile elementare ale algebrei booleene, 1 este dual cu 0 și invers, x este dual cu x, dual, dual și invers.
Dacă în formula F 1 reprezentând funcţia se înlocuiesc toate conjuncţiile
pe disjuncție, disjuncție pe conjuncție, 1 la 0, 0 la 1, apoi obținem formula F * reprezentând funcția * duală.
Forma normală conjunctivă (CNF) este un concept dual pentru DNF, prin urmare este ușor să o construiți conform schemei:
Exemplul 8. Găsiți CNF-ul formulei:.
Folosind rezultatul din Exemplul 6, avem
Formele normale disjunctive perfecte și conjunctive perfecte.În fiecare dintre tipurile de forme normale (disjunctive și conjunctive), se poate distinge o clasă de forme perfecte SDNF și SKNF.
O conjuncție elementară perfectă este produsul logic al tuturor variabilelor cu sau fără negație, iar fiecare variabilă apare în produs o singură dată.
Orice DNF poate fi redus la SDNF prin divizarea conjuncțiilor care nu conțin toate variabilele, de exemplu. adunarea pentru variabila lipsă x i se înmulțește folosind legea distribuției
Exemplul 9. Găsiți SDNF pentru exemplul 6 DNF
Disjuncția elementară perfectă este suma logică a tuturor variabilelor cu sau fără negații, iar fiecare variabilă este inclusă în sumă o singură dată.
Orice CNF poate fi redus la SKNF prin adăugarea unui termen de conjuncție care nu conține nicio conjuncție variabilă X i și aplicând legea distributivă
Exemplul 10. Aduceți CNF la SKNF:
Pentru a construi SKNF, puteți utiliza schema
Exemplul 11. Găsiți SKNF pentru formula din exemplul 6.
Fiecare funcție are SDNF și, în plus, este unică. Fiecare funcție are un SKNF și, în plus, singura.
pentru că SDNF și SKNF sunt definite prin formule în mod unic, ele pot fi construite conform tabelului de adevăr al formulei.
Pentru a construi SDNF, este necesar să selectați liniile în care F ia valoarea 1 și să scrieți conjuncțiile elementare perfecte pentru ele. Dacă valoarea unei variabile din rândul necesar al tabelului de adevăr este egală cu unu, atunci într-o conjuncție perfectă se ia fără negație, dacă zero, atunci cu negație. Apoi conjuncțiile perfecte (numărul lor este egal cu numărul celor din tabel) sunt legate prin semne de disjuncție.
Pentru a construi SKNF conform tabelului de adevăr, este necesar să selectați liniile din acesta, unde F = 0, și să scrieți disjuncțiile elementare perfecte, apoi să le conectați cu semne de conjuncție. Dacă în rândul necesar al tabelului de adevăr (F = 0) valoarea variabilei corespunde cu zero, atunci într-o clauză perfectă se ia fără negație, dacă este una - atunci cu negație.
Exemplul 12. Găsiți SDNF și SKNF folosind tabelul de adevăr pentru formula exemplului 6.
Tabelul 14 arată doar valoarea finală a lui F = 10101101. Ar trebui să vă convingeți singur de validitatea acestei afirmații prin construirea unui tabel de adevăr extins.
Tabelul 14
X y z
