Forma normală conjunctivă

Forma normală conjunctivă ( CNF ) în logica booleană  este o formă normală în care o formulă booleană are forma unei conjuncții de disjuncții de literale . Forma normală conjunctivă este convenabilă pentru demonstrarea automată a teoremei . Orice formulă booleană poate fi convertită în CNF. [1] Pentru aceasta puteți folosi: legea dublei negații , legea lui de Morgan , distributivitatea .

Exemple și contraexemple

Formule în CNF :

Formule care nu sunt în CNF :

Dar aceste 3 formule nu sunt în CNF echivalente cu următoarele formule în CNF:

Construcția CNF

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:

2) Înlocuiți semnul de negație, referitor la întreaga expresie, cu semne de negație, referitor la declarații de variabile individuale, pe baza formulelor:

3) Scapa de semnele negative duble.

4) Aplicați, dacă este necesar, la operațiile de conjuncție și disjuncție proprietățile formulelor de distributivitate și absorbție.

Un exemplu de construire a unui CNF

Să reducem formula la CNF

Să transformăm formula într-o formulă care nu conține :

În formula rezultată, transferăm negația la variabile și reducem negațiile duble:

Conform legii distributivității , obținem CNF:

k -forma normală conjunctivă

O formă normală k -conjunctivă este o formă normală conjunctivă în care fiecare disjuncție conține exact k literali .

De exemplu, următoarea formulă este scrisă în 2-CNF:

Tranziția de la KNF la SKNF

Dacă o variabilă lipsește într-o disjuncție simplă (de exemplu, z), atunci îi adăugăm expresia: (aceasta nu schimbă disjuncția în sine), după care deschidem paranteze folosind legea distribuției :

Astfel, SKNF este obținut din CNF.

Gramatică formală care descrie CNF

Următoarea gramatică formală descrie toate formulele reduse la CNF:

<CNF> → <disjunct> <CNF> → <CNF> ∧ <disjunct> <disjunct> → <literal>; <disjunct> → (<disjunct> ∨ <literal>) <literal> → <termen> <literal> → ¬<termen>

unde <term> denotă o variabilă booleană arbitrară.

Problema de satisfacție pentru o formulă în CNF

În teoria complexității computaționale, un rol important îl joacă problema satisfacabilității formulelor booleene în formă normală conjunctivă. Conform teoremei lui Cooke , această problemă este NP-complet și se reduce la problema de satisfacție pentru formulele din 3-CNF, care se reduce și la care alte probleme NP-complete se reduc la rândul lor .

Problema de satisfacție pentru formulele 2-CNF poate fi rezolvată în timp liniar.

Caracteristici de notație

Trebuie remarcat faptul că, pentru comoditatea percepției, simbolurile înmulțirii și adunării aritmetice sunt adesea folosite ca desemnare pentru conjuncție și disjuncție, în timp ce simbolul înmulțire este adesea omis. În acest caz, formulele de algebră booleană arată ca polinoame algebrice, ceea ce este mai familiar pentru ochi, dar poate duce uneori la neînțelegeri.

De exemplu, următoarele intrări sunt echivalente:

Din acest motiv, CNF în literatura de limbă rusă este uneori numit „produsul sumelor”, care este o hârtie de calc din termenul englez „produs al sumelor”.

Vezi și

Note

  1. ↑ Pozdnyakov S.N., Rybin S.V. Matematică discretă. - S. 303.

Literatură

Link -uri