Forma normală conjunctivă a unei funcții logice. Forme conjunctive de reprezentare a funcţiilor logice
Pentru orice formulă logică, cu ajutorul transformărilor identice, se poate construi un număr infinit de formule echivalente cu aceasta. În algebra logicii, una dintre sarcinile principale este căutarea formelor canonice (adică formule construite după o singură regulă, canon).
Dacă o funcție logică este exprimată prin disjuncție, conjuncție și negație de variabile, atunci această formă de reprezentare se numește normală.
Dintre formele normale se remarcă formele perfecte normale (acele forme în care funcțiile sunt scrise într-un mod unic).
Forma normală disjunctivă perfectă (PDNF)
Definiție. O formulă se numește conjuncție elementară dacă este formată din conjuncția unui anumit număr de variabile sau negațiile acestora.
Exemple: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4
Definiție. O formulă se numește formă normală disjunctivă (DNF) dacă este o disjuncție a conjuncțiilor elementare care nu se repetă.
DNF se scrie sub următoarea formă: F 1 ∨ F 2 ∨ ... ∨ F n , unde F i este o conjuncție elementară
Exemple: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2
Definiție. O formulă logică în k variabile se numește formă normală disjunctivă perfectă (PDNF) dacă:
1) formula este un DNF, în care fiecare conjuncție elementară este o conjuncție de k variabile x 1, x 2, ..., x k și pe locul i această conjuncție este fie variabila x i, fie negația ei;
2) toate conjuncțiile elementare dintr-un astfel de DNF sunt distincte perechi.
Exemplu: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)
Forma normală conjunctivă perfectă (SKNF)
Definiție. O formulă se numește disjuncție elementară dacă este formată din disjuncția unui anumit număr de variabile sau negațiile acestora.
Exemple: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3
Definiție. O formulă se numește formă normală conjunctivă (CNF) dacă este o conjuncție de disjuncții elementare nerepetate.
CNF se scrie sub următoarea formă: F 1 ∧ F 2 ∧ ... ∧ F n , unde F i este o disjuncție elementară
Exemple: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)
Definiție. O formulă logică în k variabile se numește formă normală conjunctivă perfectă (KDNF) dacă:
1) formula este un CNF, în care fiecare disjuncție elementară este o disjuncție a k variabile x 1 , x 2 , …, x k , iar locul i al acestei disjuncții este fie variabila x i, fie negația ei;
2) toate disjuncțiile elementare dintr-un astfel de CNF sunt distincte perechi.
Exemplu: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)
observa asta orice funcție logică care nu este identic egală cu 0 sau 1 poate fi reprezentată ca SDNF sau SKNF.
Algoritm pentru construirea SDNF conform tabelului de adevăr
- Selectați toate rândurile din tabel în care valoarea funcției este egală cu unu.
- Pentru fiecare astfel de linie, scrieți conjuncția tuturor variabilelor după cum urmează: dacă valoarea unei variabile din această mulțime este egală cu 1, atunci includem variabila însăși în conjuncție, în caz contrar, negația ei.
- Conectăm toate conjuncțiile rezultate prin operații de disjuncție.
Algoritm pentru construirea SKNF conform tabelului de adevăr
- Selectați toate rândurile din tabel în care valoarea funcției este egală cu zero.
- Pentru fiecare astfel de rând, scrieți disjuncția tuturor variabilelor după cum urmează: dacă valoarea unei variabile din această mulțime este 0, atunci includem variabila în sine în conjuncție, în caz contrar, negația ei.
- Conectăm toate disjuncțiile obținute prin operații de conjuncție.
Analiza algoritmilor arată că, dacă valoarea funcției este egală cu 0 pe majoritatea rândurilor tabelului de adevăr, atunci pentru a obține formula sa logică, este mai bine să construiți un SDNF, în caz contrar - SKNF.
Exemplu: dat un tabel de adevăr al unei funcții logice a trei variabile. Construiți o formulă logică care implementează această funcție.
| X | y | z | F(x, y, z) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
pentru că pe majoritatea rândurilor din tabelul de adevăr, valoarea funcției este egală cu 1, apoi construim SKNF. Ca rezultat, obținem următoarea formulă logică:
F = (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)
Să verificăm formula rezultată. Pentru a face acest lucru, construim un tabel de adevăr al funcției.
| X | y | z | X | ¬ x ∨ y ∨ z | ¬z | ¬ x ∨ y ∨ ¬ z | F(x, y, z) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
Comparând tabelul de adevăr inițial și cel construit pentru formula logică, observăm că coloanele cu valoarea funcției sunt aceleași. Aceasta înseamnă că funcția logică este construită corect.
Să introducem conceptul de disjuncție elementară.
O disjuncție elementară este o expresie a formei
Forma normală conjunctivă (CNF) a unei funcții logice este conjuncția oricărui set finit de disjuncții elementare distincte în perechi. De exemplu, funcții logice
sunt conjuncţii ale disjuncţiilor elementare. Prin urmare, ele sunt scrise în formă normală conjunctivă.
O funcție logică arbitrară dată de o expresie analitică poate fi redusă la CNF prin efectuarea următoarelor operații:
Utilizarea regulii de inversare dacă operația de negație este aplicată unei expresii logice;
Utilizări ale axiomei distributivității cu privire la înmulțire:
Folosind operația de absorbție:
Excepții în disjuncțiile variabilelor repetate sau negațiile acestora;
Îndepărtarea tuturor disjuncțiilor elementare identice, cu excepția uneia;
Ștergerea tuturor disjuncțiilor care includ simultan o variabilă și negația acesteia.
Valabilitatea operațiilor enumerate decurge din axiomele de bază și relațiile de identitate ale algebrei logicii.
O formă normală conjunctivă se numește perfectă dacă fiecare disjuncție elementară inclusă în ea conține în formă directă sau inversă toate variabilele de care depinde funcția.
Transformarea CNF în CNF perfect se realizează prin efectuarea următoarelor operații:
Adăugări la fiecare disjuncție elementară de conjuncții de variabile și negații ale acestora, dacă nu sunt incluse în această disjuncție elementară;
Utilizarea axiomei distributivității;
Eliminarea tuturor disjuncțiilor elementare identice, cu excepția uneia.
Orice funcție logică poate fi reprezentată într-un CNF perfect, cu excepția
identic egal cu unu (). O proprietate distinctivă a unui CNF perfect este că reprezentarea unei funcții logice în el este unică.
Disjuncțiile elementare incluse într-o funcție CNF perfectă se numesc constituenți zero. Fiecare componentă zero dintr-un CNF perfect dispare pe singurul set de valori variabile, care este setul zero al funcției. În consecință, numărul de seturi zero ale unei funcții logice coincide cu numărul de constituenți zero incluși în CNF-ul său perfect.
Funcția logică constantă zero în CNF perfect este reprezentată de conjuncția 2nconstituent a lui zero. Să formulăm o regulă pentru compilarea SKNF a unei funcții logice conform tabelului de corespondență.
Pentru fiecare linie a tabelului de corespondență în care funcția este egală cu zero, este compilată o disjuncție elementară a tuturor variabilelor. Disjuncția include variabila în sine, dacă valoarea ei este egală cu zero, sau negația, dacă valoarea ei este egală cu unu. Disjuncțiile elementare rezultate sunt combinate prin semnul conjuncției.
Exemplul 3.4. Pentru funcția logică z(x) dată de tabelul de căutare 2.2, definim forma conjunctivă perfectă.
Pentru primul rând al tabelului, care corespunde setului de funcții zero 000, găsim componenta nulă . Efectuând operații similare pentru al doilea, al treilea și al cincilea rând, determinăm funcția CNF perfectă dorită:
Trebuie remarcat faptul că pentru funcțiile al căror număr de seturi de unități depășește numărul de seturi zero, este mai compact să le scrieți sub forma SKNF și invers.
Definiția 1.Monomiul conjunctiv (conjuncție elementară) din variabile se numește conjuncția acestor variabile sau negațiile lor.
De exemplu, este o conjuncție elementară.
Definiția 2.Monomiul disjunctiv (disjuncția elementară) din variabile se numește disjuncția acestor variabile sau negațiile lor.
De exemplu, este o disjuncție elementară.
Definiția 3. O formulă care este echivalentă cu o formulă de algebră propozițională dată și este o disjuncție de monomii conjunctive elementare se numește forma normală disjunctivă(DNF) din această formulă.
De exemplu,- DNF.
Definiția 4. O formulă care este echivalentă cu o formulă de algebră propozițională dată și este o conjuncție de monomii disjunctive elementare se numește forma normală conjunctivă(CNF) din această formulă.
De exemplu, – KNF.
Pentru fiecare formulă de algebră propozițională, se poate găsi un set de forme normale disjunctive și conjunctive.
Algoritm pentru construirea formelor normale
Folosind echivalențe ale algebrei logicii, înlocuiți toate operațiile din formulă cu cele principale: conjuncție, disjuncție, negație:
Scapa de dublele negative.
Aplicați, dacă este necesar, la operațiile de conjuncție și disjuncție proprietățile formulelor de distributivitate și absorbție.
2.6. Formele normale disjunctive perfecte și conjunctive perfecte
Orice funcție booleană poate avea multe reprezentări DNF și CNF. Un loc special printre aceste reprezentări îl ocupă perfect DNF (SDNF) și perfect CNF (SKNF).
Definiția 1. Forma normală disjunctivă perfectă(SDNF) este un DNF în care fiecare monom conjunctiv conține fiecare variabilă din mulțime exact o dată și intră fie el însuși, fie negația sa.
Din punct de vedere structural, SDNF pentru fiecare formulă a algebrei propoziționale redusă la DNF poate fi definit după cum urmează:
Definiția 2. Forma normală disjunctivă perfectă(SDNF) a unei formule de algebră propozițională se numește DNF, care are următoarele proprietăți:
Definiția 3. Forma normală conjunctivă perfectă(SKNF) este un CNF în care fiecare monom disjunctiv conține fiecare variabilă din mulțime exact o dată și intră fie el însuși, fie negația sa.
Din punct de vedere structural, SKNF pentru fiecare formulă a algebrei propoziționale redusă la CNF poate fi definit după cum urmează.
Definiția 4. Forma normală conjunctivă perfectă(SKNF) a unei formule de algebră propozițională dată este CNF a acesteia, care satisface următoarele proprietăți.
Teorema 1. Fiecare funcție booleană a variabilelor care nu este identic falsă poate fi reprezentată în SDNF și, în plus, într-un mod unic.
Modalități de a găsi SDNF
1-a cale
a 2-a cale
selectați liniile în care formula ia valoarea 1;
facem o disjuncție de conjuncții, cu condiția ca dacă variabila este inclusă în conjuncția cu valoarea 1, atunci scriem această variabilă, dacă cu valoarea 0, atunci negația ei. Primim SDNF.
Teorema 2. Fiecare funcție booleană a variabilelor care nu este identic adevărată poate fi reprezentată în SKNF și, mai mult, într-un mod unic.
Modalități de a găsi SKNF
1-a cale– cu ajutorul transformărilor echivalente:
a 2-a cale- folosind tabele de adevăr:
selectați liniile în care formula ia valoarea 0;
compunem o conjuncție de disjuncții, cu condiția ca dacă variabila este inclusă în disjuncție cu valoarea 0, atunci scriem această variabilă, dacă cu valoarea 1, atunci negația ei. Primim SKNF.
Exemplul 1 Trasează funcțiile CNF.
Soluţie
Eliminați legătura „” folosind legile de transformare a variabilelor:
= /legile lui de Morgan și dubla negație/ =
/legi distributive/ =
Exemplul 2 Convertiți formula în DNF.
Soluţie
Exprimăm operațiile logice în termeni și:
= /Relaționați negația de variabile și reduceți negațiile duble/ =
= /legea distributivității/ .
Exemplul 3 Scrieți formula în DNF și SDNF.
Soluţie
Folosind legile logicii, reducem această formulă la o formă care conține doar disjuncții ale conjuncțiilor elementare. Formula rezultată va fi DNF dorită:
Pentru a construi SDNF, vom compila un tabel de adevăr pentru această formulă:
Marcam acele rânduri ale tabelului în care formula (ultima coloană) ia valoarea 1. Pentru fiecare astfel de rând, scriem formula care este adevărată pe setul de variabile ,, din acest rând:
linia 1: ;
linia 3: ;
linia 5: .
Disjuncția acestor trei formule va lua valoarea 1 numai pe seturile de variabile din rândurile 1, 3, 5 și, prin urmare, va fi forma normală disjunctivă perfectă necesară (PDNF):
Exemplul 4 Aduceți formula la SKNF în două moduri:
a) cu ajutorul transformărilor echivalente;
b) folosind un tabel de adevăr.
Soluţie:
Transformăm a doua disjuncție elementară:
Formula arată astfel:
b) alcătuiți un tabel de adevăr pentru această formulă:
Marcam acele rânduri ale tabelului în care formula (ultima coloană) ia valoarea 0. Pentru fiecare astfel de rând, scriem formula care este adevărată pe setul de variabile ,, din acest rând:
randul 2: ;
linia 6: .
Conjuncția acestor două formule va lua valoarea 0 numai pe seturile de variabile din liniile 2 și 6 și, prin urmare, va fi forma normală conjunctivă perfectă dorită (CKNF):
Întrebări și sarcini pentru soluții independente
1. Folosind transformări echivalente, aduceți formulele la DNF:
2. Folosind transformări echivalente, aduceți formulele la CNF:
3. Folosind a doua lege distributivă, convertiți DNF în CNF:
A) 
;
4. Convertiți DNF-urile date în SDNF-uri:
5. Convertiți CNF-ul dat în SKNF:
6. Pentru formulele logice date, construiți SDNF și SKNF în două moduri: folosind transformări echivalente și folosind tabelul de adevăr.
b) 
;
forma normala formula logică nu conține semne de implicare, echivalență și negație a formulelor neelementare.
Forma normală există în două forme:
forma normala conjunctiva (CNF)-- conjuncția mai multor disjuncții, de exemplu, $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;
forma normala disjuntiva (DNF)-- disjuncția mai multor conjuncții, de exemplu, $\left(A\wedge \overline(B)\wedge C\right)\vee \left(B\wedge C\right)$.
SKNF
Forma normală conjunctivă perfectă (SKNF) este un CNF care îndeplinește trei condiții:
nu conține disjuncții elementare identice;
niciuna dintre disjuncții nu conține aceleași variabile;
fiecare disjuncție elementară conține fiecare variabilă din CNF dat.
Orice formulă booleană care nu este identic adevărată poate fi reprezentată în SKNF.
Reguli pentru construirea SKNF conform tabelului de adevăr
Pentru fiecare set de variabile pentru care funcția este 0, se înregistrează suma, cu variabile care au valoarea 1 luate cu negație.
SDNF
Forma normală disjunctivă perfectă (PDNF) este un DNF care îndeplinește trei condiții:
nu conține conjuncții elementare identice;
nici una dintre conjuncții nu conține aceleași variabile;
fiecare conjuncție elementară conține fiecare variabilă din DNF dat, în plus, în aceeași ordine.
Orice formulă booleană care nu este identic falsă poate fi reprezentată în SDNF, în plus, într-un mod unic.
Reguli pentru construirea SDNF conform tabelului de adevăr
Pentru fiecare set de variabile în care funcția este egală cu 1, se scrie produsul, iar variabilele care au valoarea 0 sunt luate cu negație.
Exemple de găsire a SKNF și SDNF
Exemplul 1
Scrieți o funcție logică conform tabelului său de adevăr:
Poza 1.
Soluţie:
Să folosim regula pentru construirea SDNF:
Figura 2.
Primim SDNF:
Să folosim regula de construcție SKNF.
bază standard. Formulele elementare sunt literale. Conjuncție elementară (disjuncție). Forma normală disjunctivă (conjunctivă) și formă perfectă. Teoremă: orice funcție booleană, alta decât 0 (din 1) poate fi reprezentată ca SDNF (SKNF). Completitudinea bazei standard. Exemple de baze complete: baza lui Zhegalkin, lovitura lui Sheffer, săgeata lui Pierce.
Baza standard este un set de trei operații inițiale de algebră booleană: adunare (unire), înmulțire (intersecție) și negație.
Aici vom suna literal variabila x sau negația sa x și notăm xˆ. Intersecția booleană a mai multor literale definite de diferite variabile, de ex. expresie de forma X = xˆ 1 xˆ 2 . . . xˆ l, se numește conjuncție elementară . Cerința ca toate variabilele să fie diferite se datorează următoarelor. Dacă conjuncția include mai multe literale identice, atunci datorită comutativității, asociativității și idempotității conjuncției, trecând la o formulă echivalentă, putem lăsa doar un literal (de exemplu, x 1 x 1 = x 1). Dacă conjuncția include o variabilă și negația acesteia, atunci formula este echivalentă cu constanta 0, deoarece x x = 0 și pentru orice formulă Y avem Y x x = 0.
Se numește disjuncția mai multor conjuncții elementare forma normală disjunctivă , sau DNF . De exemplu,
x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .
Dacă compoziția variabilelor din fiecare conjuncție elementară a unui DNF dat este aceeași, atunci DNF se numește perfect . Exemplul dat este un DNF care nu este perfect. Dimpotrivă, formula
x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4
este forma perfecta.
Deoarece în algebra booleană adăugarea și înmulțirea sunt operații simetrice și se poate interpreta întotdeauna adunarea ca înmulțire și înmulțirea ca adunare, există și un concept dual - forma normală conjunctivă (KNF ), care este o conjuncție de disjuncții elementare și formă conjunctivă perfectă (SKNF ). Din principiul dualității pentru semiinele simetrice rezultă că orice afirmație despre DNF corespunde unei afirmații duale despre CNF, care se obține prin înlocuirea adunării (disjuncției) cu înmulțire, înmulțirii (conjuncției) prin adunare, constantă 0 cu constanta 1, constantă 1. prin constanta 0, relații de ordine prin dual (invers) în ordine. Prin urmare, în continuare ne vom concentra pe studierea doar a DNF.
Teorema 1.4. Orice funcție booleană, alta decât constanta 0, poate fi reprezentată ca un SDNF.
◀ Să fim de acord prin x σ să însemne formula x dacă σ = 1 și formula x dacă σ = 0. Fie funcția f(y 1 , . . . , y n) să ia valoarea 1 pe vector (t 1 ). , . . . , t n ) (un astfel de vector se numește unitate constitutivă ). Atunci conjuncția elementară ia și valoarea 1 pe această mulțime, dar dispare pe toți ceilalți vectori booleeni n-dimensionali. Luați în considerare formula
în care suma (uniunea) se extinde la toate acele mulțimi (t 1 , . . . . , t n) de valori argument pe care funcția dată ia valoarea 1. Rețineți că mulțimea unor astfel de mulțimi nu este goală, astfel încât suma conţine cel puţin un termen.
Este ușor de observat că formula Φ se transformă în 1 pentru acelea, și numai pentru acele valori ale variabilelor, pentru care funcția considerată se transformă în 1. Prin urmare, formula Ψ reprezintă funcția f.
Corolarul 1.1. Baza standard este completă.
◀ Într-adevăr, dacă o funcție nu este o constantă 0, atunci poate fi reprezentată fie ca un SDNF, care este o formulă pe o bază standard. Constanta 0 poate fi reprezentată, de exemplu, prin formula f(x 1 , x 2 ,..., x n) = x 1 x 1 .
Exemplul 1.2. Se consideră o funcție de trei variabile m(x 1 , x 2 , x 3) (Tabelul 1.4), numită functia majoritara ̆. Această funcție evaluează la 1 dacă mai mult de jumătate din argumentele sale au valoarea 1. Prin urmare, este adesea numită funcție de vot. Să construim un SDNF pentru el.
Completitudinea bazei standard permite selectarea altor sisteme complete de funcții. Completitudinea multimii F poate fi stabilita din urmatoarele consideratii. Să presupunem că fiecare dintre cele trei funcții buzzis standard este reprezentabilă printr-o formulă peste F . Atunci, în virtutea teoremei 1.3, alteritatea lui F va fi completă.
Exemplul 1.3. Se numește setul de operații modulo 2 adunare, înmulțire și constantă 1 baza Zhegalkin . Modulul 2 adunarea și înmulțirea sunt operațiile de bază ale inelului Z2, expresiile compuse cu ajutorul lor sunt polinoame peste inelul Z2. Constanta 1 în acest caz este necesară pentru a scrie membrul liber. Deoarece xx \u003d x, atunci toți factorii din polinom au gradul 1. Prin urmare, atunci când scrieți un polinom, puteți face fără conceptul de grad. Exemple de formule pe baza Zhegalkin:
xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.
Orice astfel de formulă se numește polinomul Zhegalkin. De fapt, polinomul Zhegalkin este un polinom peste inelul Z2.
Este ușor să construiți formule pe baza Zhegalkin, reprezentând operațiile de adăugare și negație a bazei standard (înmulțirea a două baze este comună):
x+y=x⊕y⊕xy, x=x⊕1.
Prin urmare, baza Zhegalkin este un set complet.
Se poate demonstra că pentru orice funcție booleană polinomul Zhegalkin este definit în mod unic
(mai precis, până la ordinea termenilor). Coeficienții polinomului Zhegalkin cu un număr mic de variabile pot fi găsiți prin metoda coeficienților nedeterminați.
Exemplul 1.4. Luați în considerare un set de o singură funcție - cursa Schaeffer*. Acest set este complet, care rezultă din următoarele identități ușor de verificat:
x=x|x, xy=x|y=(x|y)|(x|y), x+y=x |y=(x|x)|(y|y).
Exemplul 1.5. Baza constând dintr-o singură funcție, săgeata Pierce, este de asemenea completă. Verificarea acestui lucru este similară cu cazul primului Schaeffer. Totuși, această concluzie poate fi trasă și pe baza principiului dualității pentru semiinele simetrice.
*Lovitura lui Schaffer este o operație binară, dar nu una asociativă. Prin urmare, atunci când utilizați formularul infix, ar trebui să fiți atenți: rezultatul depinde de ordinea în care sunt efectuate operațiunile. În acest caz, se recomandă să specificați în mod explicit ordinea operațiilor folosind paranteze, de exemplu, scrieți (x | y) | z, nu x | y | z, deși ambele forme sunt echivalente.
