forma normala conjunctiva Perfect - studopediya

Pentru aceeași formulă se poate face o mulțime echivalentă CNF. Dar printre ei există un CNF unic, cu proprietățile perfecțiune.

Enumerăm proprietatile perfecțiunii CNF:

1. Fiecare formulă multiplicator logic conține toate variabilele incluse în această funcție.

2. Factori Toate logice sunt diferite.

3. Nici un factor nu conține atât o variabilă și negația.

4. Nici un factor nu conține aceeași variabilă de două ori.

CNF pentru care proprietățile perfecțiunii executate este numită perfectă CNF (SKNF).

Nu în mod identic cu formula adevărată are un SKNF unic.

O modalitate de a obține SKNF este de a utiliza tabele de adevăr pentru:

1. Se aduce PDNF.

2. Pentru construirea SKNFA PDNF negație, adică

Sau seturi de variabile, în care A este falsă, face disjunctia elementar, în care variabilele care au intrat cu valoarea de adevăr este introdus cu negarea, iar valoarea rezidă - fără negație. Din disjunctiile elementare obținute constituie împreună.

O altă metodă se bazează pe transformări echivalente

Aici sunt algoritmul corespunzător:

1. Prin transformări echivalente pentru a obține unele - sau CNF.

2. În cazul în care un disjunctie elementar în nu conține o variabilă xi. apoi introduce folosind echivalența. Și folosind proprietatea distributiv.

3. Dacă CNF include două disjuncție identice B, apoi excesul este îndepărtat folosind proprietatea idempotența în B ° B.

4. În cazul în care orice disjuncție conține xi împreună cu negarea, atunci B º 1. Și în regula CNF.

5. Dacă orice disjuncție conține xi variabil de două ori, una dintre ele este aruncată folosind xi proprietatea v xi ° xi.

1. Creați formula SKNF pentru masa de adevăr și prin transformări echivalente.

Formam un tabel de adevăr, care conține patru rânduri pentru

3. Prin transformări echivalente a obține SKNFA.

Sarcini pentru decizia independentă.

1. Pentru formulele următoare și pentru a găsi PDNF SKNF la fiecare două moduri (prin echivalent-formare și transformare folosind tabelul de adevăr):

2. Găsiți PDNF pentru toate formula identic cis tulbure care cuprinde: 1) o singură variabilă, 2) două variabile, 3) trei variabile.

3.Găsiți SKNF pentru toate identic-loji formula clorhidric care cuprinde: 1) o singură variabilă, 2) două variabile, 3) trei variabile.

4. Dovedește echivalențele și compararea formelor lor perfecte normale (conjunctive sau disjuncte).

5. Găsiți o formă mai simplă a formulelor care sunt sub formă perfect normal următoarea:

1. Lista proprietățile perfectiunii pentru DNF.

2. Lista proprietatile de perfectiune pentru CNF.

3. Cât de mult de o formulă poate face PDNF și SKNF?

4. În ceea ce privește tabelul de adevăr pentru a face PDNF?

5. Comunicarea între SDNFA și SKNFA.

6. Cum de a face modificări cu echivalentul formulei PDNF și SKNF?