forma normala conjunctiva - l
CNF formulă nu este:
Dar aceste 3 formule nu sunt în CNF echivalente cu următoarele formule în CNF:
Construcție de CNF
Un algoritm pentru construirea CNF
1) Scapă de toate operațiile logice conținute în formulă, înlocuindu-le cu bază: conjuncție, disjuncție, negație. Acest lucru se poate realiza folosind formula sunt echivalente:
2) Se înlocuiește semnul negației referitor la întreaga expresie, semne negare legate de variabile individuale pe baza enunțuri cu formulele:
3) Scapă de semne duble negative.
4) Se aplică, dacă este necesar, pentru operațiunile proprietăților conjunction și disjuncție distributivitatii și absorbție a formulei.
EXEMPLU construirea CNF
Pentru a da formula CNF
F transforma formula formulei care nu cuprinde →:
Formula obținută se transferă negarea variabilelor și va reduce dubla negație:
k -konyunktivnaya formă normală
k -konyunktivnoy numit formă normală formă normală conjunctivă în care fiecare disjuncție conține exact k literali.
De exemplu, următoarea formulă este înregistrată în 2 CNF:
Trecerea de la CNF la SKNF
În cazul în care un simplu disjuncție este lipsită de orice variabilă (de exemplu, z), apoi se adaugă la ea expresia (nu se modifică foarte disjuncției), iar apoi dezvăluie parantezele folosind legea distributiv:
Astfel, de la primit CNF SKNF.
O gramatica formală care descrie CNF
Următoarea gramatica formală descrie toate formulele indicate în CNF:
<КНФ> → <дизъюнкт> <КНФ> → <КНФ> ∧ <дизъюнкт> <дизъюнкт> → <литерал> <дизъюнкт> → (<дизъюнкт> ∨ <литерал>) <литерал> → <терм> <литерал> → ¬<терм>
unde <терм> denotă o variabilă booleană arbitrar.
Formula sarcina de fezabilitate CNF
În teoria complexității computaționale joacă un rol problemă importantă satisfiabilitate booleană în formă normală conjunctivă. Conform teoremei lui Cook. această problemă este NP-completă. și se reduce la problema realizability formulelor din 3-CNF, care este redus și care, la rândul său, a redus celelalte probleme NP-complete.
Problema formulelor satisfiabilitate 2-CNF pot fi rezolvate în timp liniar.
notițe
literatură
Vezi ce „forma normală conjunctivă“ în alte dicționare:
formă normală conjunctivă - formula propozitionala având forma (*) unde fiecare ij C, i = 1. n; j = 1. mi, este fie o variabilă sau o negare a variabilei. K. n. f. (*) Este o tautologie dacă și numai dacă pentru orice isredi cu i1. Cimi. ... ... Enciclopedia de Matematică
formă normală K-conjunctivă - (k CNF) în forma normală logica Boolean în care o formulă Boolean este conjuncția mai multe clauze, fiecare dintre ele conținând exact k literals. De exemplu, următoarea formulă este înregistrată în 2 CNF ... Wikipedia
Forma normală (dezambiguizare) - Formular formă normală normal în relațiile baze de date de proprietate în modelul de date relațională. Forma normală de matematică în vreun sens sau o altă formă simplă sau canonică la care obiectul este o transformare ... ... Wikipedia
formă normală disjunctivă - (DNF) într-o formă normală logică Boolean în care o formulă Boolean este o disjuncție de conjuncții de literali. Orice formula Boolean poate fi redus la DNP. [1] Puteți utiliza legea negație dublă, legea dreptului de Morgan ... ... Wikipedia
Formele perfect normal - forma disjunctivă sau conjunctivă normală perfectă perfectă (. a se vedea funcții booleene, forme normale) ... Enciclopedia de Matematică
Funcția boolean - Acest articol sau secțiune este o listă de surse sau legături externe, dar surse individuale declarații rămân neclare din cauza lipsei de note de subsol ... Wikipedia
expresii booleene - Teoria sistemelor funcționale discrete ale funcției booleene se numește o funcție de tip. în cazul în care un set Boolean și n întreg nenegativ, care se numește aritatea funcției sau de teren. Elementele 1 (unu) și 0 (zero) este interpretat ca standard ... ... Wikipedia
- matematică discretă și logica matematică Partea I. Evgeniya Filenko. Acest lucru include informațiile de bază și model exemplele necesare în următoarele secțiuni, dintre care unele nu sunt suficient tratate în literatura de specialitate existente: 1. Seturile de ... Citește mai mult Vand (numai Ucraina) pentru 4887 UAH