Formele normale disjuncte și conjunctive perfecte (PDNF și sknf)

Acasă | Despre noi | feedback-ul

Definiția. coroborat elementară se numește o conjuncție de literali (variabile sau negațiile lor) luate nu mai mult de o dată.

De exemplu, o conjuncție. . 1 sunt elementare. Care prima conjuncție elementară are rang (număr de literali) 2, al doilea - 3, iar al treilea - 0.

Următoarele conjuncțiile :. . . . 0 nu sunt elementare.

Definiția. Funcția booleană conjuncție elementară. conținând n literals, numit complet (sau mintermom).

Definiția. Disjuncție orice set finit de conjunctii elementare functii Booleene F este numită o formă normală disjunctivă (DNF) a funcției F. Numărul conjuncțiilor elementare (termeni, termeni) constituind DNP numita lungime DNP.

Exemplu, DNP are o lungime egală cu 3.

Pentru o funcție booleană arbitrară F există, în general vorbind, o mulțime de punere în aplicare diferite DNF sale, care diferă în lungime, numărul de apariții de literali, etc.

Definiția. Două (sau mai multe) DNF de punere în aplicare aceeași funcție booleană F. numită echivalentă (sau să fie echivalent).

De exemplu, pentru funcția. vector predeterminate Boolean w (F) = (00100111), echivalent următor DNF:

Definiția. DNP Boolean Funcția F. constând numai din conjunctions complet elementare numite sovershennoyDNF (PDNF).

De exemplu, (1) - funcția PDNF F.

Rețineți că PDNF este unică (până termeni permutare) pentru o anumită funcție booleană F.

Orice funcție Boolean F. formulă predeterminată folosind equipollences bază convertit la DNP, și apoi la PDNF.

Exemplu. Se aduce la minte PDNF Boolean funcția F =.

Decizie. Cu principalele echivalențe pentru a transforma DNF:

Aplicarea legii lipire (în ordine inversă), completează coroborat. pentru a finaliza conjuncțiilor elementare:

Din moment. după reducerea aceleași conjuncțiile obține PDNF: F =.

Formează tabelul de adevăr pentru funcția Boolean F = (funcția din exemplul anterior). Observați legătura dintre PDNF și tabelul de adevăr.

Tabelul PDNF adevăr