polinoame Zhegalkin
Zhegalkin polinoame sunt inca interesante formule subclasă permit să reprezinte funcții booleene.
Definiția 4.4. Polinoamele Zhegalkin numit mai sus funcții Formula set FJ =<0, 1, *, +> (În cazul în care * - este un alt simbol al conjuncției).
Astfel, fiecare polinom Zhegalkin (eventual după paranteze expansiune și „de conducere“ termeni similari) reprezintă suma (modulo 2) pozitive (monotone) conjuncții elementare (adică conjunctiile elementare fără negative). Deoarece + si * sunt doar legile asociativitatea. vom omite paranteze, cu excepția faptului că argumentele mai puternice link-uri * la înregistrarea Zhegalkin polinomul decât +
Este ușor de verificat că avem următoarea echivalență:
Din aceste echivalențe, și Teorema 4.1 este ușor pentru a obține prima parte a următoarea afirmație.
Teorema 4.3. Pentru orice funcție booleană specificată de polinom acolo Zhegalkin. El este unic până la permutarea termenilor și ordinea variabilelor în conjuncție.
Dovada existenței unei astfel de polinom rezultă din faptul că pentru orice CNF sau DNF prin utilizarea a spus găsi echivalentul polinomială echivalentele Zhegalkin. (J1) - (J3) vă permite să înlocuiască toate aparițiile pe + și *. și (J4) - se multiplica polinoamele rezultate în urma acestei înlocuiri.
Pentru a demonstra unicitatea reprezentării vom calcula numărul de diferite polinoame Zhegalkin variabilelor. Fiecare conjuncție elementară pozitivă arată Xi1 *. * Xik. în cazul în care 1 <= i1 <. în care fiecare dintre coeficienții este 0 sau 1. Prin urmare, numărul de polinoame Zhegalkin egal, adică Dintre toate funcțiile booleene de n variabile. Prin urmare, fiecare funcție este dat exact un polinom Zhegalkin. Exemplul 4.3. Să se dă un DNF funcția f (X1, X2, X3). Să ne găsim un Zhegalkin polinom. care definește, de asemenea, funcția. În primul rând se înlocuiește cu *. și apoi, folosind echivalența (J1), vom elimina negarea și a obține: Înmulțind cu regulile (J4), obținem: EchivalenŃă (J3) elimină Din nou, folosind (J4), se înmulțește primele două console și elimină variabilele recurență în conjunctions: Noi simplifica această sumă folosind echivalența și. Ca rezultat, vom obține un polinom Zhegalkin echivalent cu DNF originală Dacă funcția f (X1. Xn) este dată în formă de tabel, pentru construirea de implementare polinom Zhegalkin poate folosi metoda coeficienților nedeterminat. Asociat i -lea set de valori ale variabilelor din tabelul coroborat pozitiv variabilă egală cu 1 în acest set. În special, K1 - coroborat gol. K2 = Xn. K3 = Xn-1. K4 = (Xn * Xn-1). etc. Apoi, pentru a obține Zhegalkin polinomial dorit suficient pentru a determina toți coeficienții din expresia Substituind în această ecuație valorile variabilelor din setul, obținem 2 n ecuații liniare în n 2 coeficienți necunoscuți. Rezolvarea acestui sistem, vom obține Zhegalkin polinomul necesar. Acest sistem este triunghiular și este ușor de rezolvat prin „sus-jos“: fiecare este determinată de valorile ecuației corespunzătoare setului. Exemplul 4.4. Să considerăm, de exemplu, funcția f (X1. Xn). având în tabelul de mai jos.articole similare