Fiecare formulă are un număr finit de variabile. Sub apariția unei variabile se înțelege locul pe care variabila îl ocupă în formulă. Problema este că pentru o funcție booleană dată f găsiți un DNP care reprezintă această funcție și are cel mai mic număr de apariții de variabile.
Dacă x este o variabilă logică, și σ∈, atunci expresie
¬x dacă σ = 0
numit litera. Un conjunct este o conjuncție de litere. De exemplu, formulele XYZ și XYXX sunt conjuncte. Un produs elementar este un conjunct în care orice variabilă nu intră mai mult decât o singură dată (fie ea însăși, fie negarea ei).
Formula f1 se numește implicantul formulei f dacă f1 este un produs elementar și f1f = f1, adică pentru formulele de funcție corespunzătoare f1≤f este valabilă. Un implicit f1 al formulei f este considerat a fi simplu dacă, după ce a fost eliminată orice literă de la f1, nu se obține o formulă care este implicată cu formula f.
Un exemplu. Noi găsim toți implicanții și implicanții simpli pentru formula f = X → Y. În total, există 8 produse elementare cu variabilele X și Y. Mai jos, pentru claritate, sunt prezentate tabelele lor de adevăr.
Un număr minim de implicați simpli este selectat în blocul DNF, a cărui disjuncție păstrează toate elementele componente ale unității, adică fiecare coloană a matricei Quine conține un asterisc la intersecția cu rândul corespunzător unuia dintre implicanții aleși. Ca DNF minim, se alege un blocaj, care are cel mai mic număr de apariții ale variabilelor.
În exemplul anterior, folosind matricea Quine, constatăm că DNF minimă a unei funcții date este ¬X¬YvXZ.
Notă. Pentru a construi un CNF minimal al unei funcții f, este suficient să construim un DNF minim pentru o funcție f, și apoi să folosim legile f = β (β) și de Morgan.
Trimiteți-le prietenilor: