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:
A → B = ך AVB A⇔B = (A ^ B) v (ך Av ך B)
2) Se înlocuiește semnul negației referitor la întreaga expresie, semne negare legate de variabile individuale pe baza enunțuri cu formulele:
ך (AVB) = ך A ^ ך B ך (A ^ B) = ך Av ך B
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 disjunctiv
Pentru a da DNP formula: F = ((X → Y) ↓ ך (Y → Z))
Ne exprimăm operații logice și → ↓ de: v ^ ך
F = ((ך XvY) ↓ ך (ך YvZ)) = ך ((ך XvY) v ך (ך YvZ))
Formula obținută se transferă negarea variabilelor și va reduce dubla negație:
F = ך ((ך XvY) v ך (ך YvZ)) = (X ^ ך ך ך Y) ^ (ך YvZ) = (X ^ ך Y) ^ (ך YvZ)
Folosind distributivitate, vom da o formulă pentru a DNF:
forma normală conjunctivă (CNF) în logica Boolean - o formă normală în care o formulă Boolean este dizyunktsiyliteralov conjuncție. forma normala conjunctiva este convenabil pentru demonstrarea automată teorema. Orice formula Boolean poate fi redus la CNF. Pentru a face acest lucru, puteți utiliza: Legea dublei negație, legea lui de Morgan, distributivitatea.
Exemplele și exemplele contra
ך A ^ (BVC) (AVB) ^ (ך BvCv ך D) ^ (E ך Dv) A ^ B
CNF formulă nu este:
ך (BVC) (A ^ B) vC A ^ (Bv (D ^ E))
Dar aceste 3 formule nu sunt în CNF echivalente cu următoarele formule în CNF:
ך B ^ ך C (CVM) ^ (BVC) A ^ (BVD) ^ (BVE)
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:
A → B = ך AVB A↔B = (A ^ B) v (ך A ^ ך B)
2) Se înlocuiește semnul negației referitor la întreaga expresie, semne negare legate de variabile individuale pe baza enunțuri cu formulele:
ך (AVB) = ך A ^ ך B ך (A ^ B) = ך Av ך B
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 →:
F = (ך XvY) ^ (ך (ך Y → Z) v ך X) = (ך XvY) ^ (ך (ך ך YvZ) v ך X)
Formula obținută se transferă negarea variabilelor și va reduce dubla negație:
F = (ך XvY) ^ ((ך Y ^ ך Zv ך X) = (ך XvY) ^ ((ך Y ^ ך Z) v ך X)
Prin lege, distributiva obține CNF:
F = (ך XvY) ^ (ך Xv ך Y) ^ (ך Xv ך Z)
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:
(AVB) ^ (ך BVC) ^ (Bv ך C)
Trecerea de la CNF la SKNF
Dacă o variabilă (de exemplu, z) nu este suficient într-o disjuncție simplu, apoi se adaugă la ea expresia. (Nu se modifică foarte disjuncției), iar apoi dezvăluie parantezele folosind legea distributiv:
(XvY) ^ (Xv ך Yv ך Z) = (XvYv (Z ^ ך Z)) ^ (Xv ך Yv ך Z) = (XvYvZ) ^ (XvY v ך Z) ^ (Xv ך Yv ך Z)
Astfel, de la primit CNF SKNF.
Trecerea de la CNF la SKNF
Dacă un simplu disjuncție lipsit de orice variabilă (de exemplu, z), apoi se adaugă la ea expresia: Z ^ ך Z = 0 (nu se schimbă foarte disjuncției), iar apoi dezvăluie consolele folosind distributivitate:
(XvY) ^ (Xv ך Y ך Z) = (XvYv (Zv ך Z)) ^ (Xv ך Yv ך Z) = (XvYvZ) ^ (XvYv ך Z) ^ (Xv ך Yv ך Z) Astfel, din CNF obținut SKNF.
25. forme normale disjuncte și conjunctive perfecte și algoritmi pentru a aduce la ele. Exemple.
Perfect forma normala conjunctiva (SKNF) - aceasta este o astfel de formă normală conjunctivă. care îndeplinește trei condiții:
nu are aceleași disjunctiile elementare
în fiecare disjuncție nu este aceleași variabile propoziționale
fiecare disjuncție elementar conține fiecare literă propozițională din membrii unui anumit scrisori propoziționale CNF.
k -konyunktivnoy numit formă normală formă normală conjunctivă în care fiecare disjuncție conține exact kliteralov.
De exemplu, următoarea formulă este înregistrată în 2 CNF:
Perfect formă normală disjunctivă (PDNF) - aceasta este o astfel de DNF. care îndeplinește trei condiții:
nu are aceleași conjuncțiile elementare
în fiecare conjuncției nu este aceleași litere propoziționale
fiecare conjuncție elementară conține fiecare literă propozițională din membrii acestei DNF scrisori propozitionale, și în aceeași ordine.
Pentru orice funcție booleană are propria PDNF, cu un singur.
Pentru a obține funcții PDNF necesare pentru a face tabelul de adevăr. De exemplu, să ia una din tabelul de adevăr: