Polinomul Zhegalkin

Polinomul Zhegalkin  este un polinom peste câmpul , adică un polinom cu coeficienți de forma 0 și 1, unde conjuncția este luată ca produs și exclusivul sau este luat ca adunare . Polinomul a fost propus în 1927 de Ivan Zhegalkin ca mijloc convenabil de reprezentare a funcțiilor logice booleene . În literatura străină, reprezentarea sub forma unui polinom Zhegalkin este de obicei numită formă normală algebrică (ANF).

Teorema lui Zhegalkin  este o afirmație despre existența și unicitatea reprezentării oricărei funcții booleene sub forma unui polinom Zhegalkin [1] .

Polinomul Zhegalkin este suma modulo doi a produselor distincte perechi ale variabilelor neinversate, unde nicio variabilă nu apare de mai multe ori în orice produs și, de asemenea, (dacă este necesar) constanta 1 [1] . Formal, polinomul Zhegalkin poate fi reprezentat ca

sau mai formalizat ca

Exemple de polinoame Zhegalkin:

Fundal

Conform teoremei lui Post , pentru ca un sistem de funcții booleene să fie complet, este necesar ca acesta să conțină:

  1. Cel puțin o funcție care nu stochează 0.
  2. Cel puțin o funcție care nu păstrează 1.
  3. Cel puțin o funcție neliniară.
  4. Cel puțin o funcție nemonotonă.
  5. Cel puțin o funcție non-duală.

Această cerință este îndeplinită, în special, de sistemul de funcții (conjuncție, adiție modulo doi, constantă 1). Pe baza ei, sunt construite polinoamele Zhegalkin.

Existența și unicitatea unei reprezentări

Prin teorema lui Zhegalkin, fiecare funcție booleană este reprezentată în mod unic ca un polinom Zhegalkin. Teorema se demonstrează după cum urmează. Rețineți că există n funcții booleene variabile . În acest caz, există exact 2 n conjuncții , deoarece fiecare dintre cei n factori posibili fie intră în conjuncție, fie nu. Într-un polinom, fiecare astfel de conjuncție are 0 sau 1, adică există polinoame Zhegalkin diferite în n variabile. Acum este suficient să demonstrăm că polinoamele diferite realizează funcții diferite. Să presupunem contrariul. Apoi, echivalând două polinoame diferite și transferând unul dintre ele în cealaltă parte a egalității, obținem un polinom care este identic egal cu zero și are coeficienți nenuli. Apoi luați în considerare un termen cu un coeficient unitar de cea mai mică lungime, adică cu cel mai mic număr de variabile incluse în el (oricare, dacă sunt mai multe). Înlocuind cu unii în locurile acestor variabile și cu zerourile în locurile restului, obținem că pe această mulțime doar acest termen capătă o valoare unitară, adică funcția zero de pe una dintre mulțimi ia valoarea 1. A contradicţie. Aceasta înseamnă că fiecare funcție booleană este realizată de polinomul Zhegalkin într-un mod unic.

Reprezentarea unei funcții sub forma unui polinom Zhegalkin

Cu transformări echivalente DNF

În comparație cu DNF , nu există operații SAU și NU în polinomul Zhegalkin. Astfel, polinomul Zhegalkin poate fi obținut din DNF exprimând operațiile OR și NOT prin operațiile de adunare modulo doi și constanta 1. Pentru aceasta se aplică următoarele relații:

Mai jos este un exemplu de conversie a unui DNF într-un polinom Zhegalkin:

Transformările se bazează pe relații

Cu ajutorul transformărilor echivalente ale SDNF

SDNF are proprietatea că, pentru orice valoare a variabilelor de intrare, nu mai mult de un membru al expresiei se transformă în unitate. Pentru astfel de expresii, operația de disjuncție este echivalentă cu operația de adunare modulo doi .

Când transformați un SDNF într-un polinom Zhegalkin, este suficient să înlocuiți toate disjuncțiile cu operații modulo doi adăugare și să scăpați de inversiuni folosind transformarea echivalentă

Cu harta Carnot

Funcția logică a trei variabile , reprezentată ca o hartă Carnot , este convertită într-un polinom Zhegalkin în următorii pași:

Metoda triunghiului

Metoda triunghiului (numită adesea metoda triunghiului lui Pascal) vă permite să convertiți tabelul de adevăr într-un polinom Zhegalkin prin construirea unui tabel triunghiular auxiliar în conformitate cu următoarele reguli:

Metoda triunghiului se bazează pe o teoremă propusă de V.P. Suprun, care nu este direct legată de triunghiul lui Pascal. În 1985, metoda triunghiului binar a fost propusă pentru a transforma un vector de valori ale unei forme normale disjunctive perfecte într-un vector de coeficienți polinomi Zhegalkin pentru o funcție booleană simetrică arbitrară. În 1987, metoda a fost extinsă la o funcție booleană arbitrară. Rețineți că metoda triunghiului permite construirea polinomului Reed-Muller cu polarizare negativă atât pentru funcții simetrice, cât și pentru funcții arbitrare. .

Metoda FFT

Cea mai economică din punct de vedere al numărului de calcule și potrivită pentru construirea manuală a polinomului Zhegalkin este metoda Fast Fourier Transform (FFT).

Construim un tabel format din 2 N coloane și N  + 1 rânduri, unde N  este numărul de variabile din funcție. În rândul de sus al tabelului plasăm vectorul valorilor funcției, adică ultima coloană a tabelului de adevăr.

Împărțim fiecare rând al tabelului rezultat în blocuri (linii negre din figură). În primul rând, un bloc ocupă o celulă, în al doilea rând, două, în al treilea, patru, în al patrulea, opt și așa mai departe. Fiecare bloc dintr-un rând, pe care îl vom numi „blocul de jos”, corespunde întotdeauna exact două blocuri din linia anterioară. Să le numim „bloc din stânga sus” și „bloc din dreapta sus”.

Construcția începe de la a doua linie. Conținutul blocurilor din stânga sus este transferat fără modificări în celulele corespunzătoare din blocul inferior (săgețile verzi din figură). Apoi, operația „modulo two addition” se realizează bit cu bit peste blocurile din dreapta sus și din stânga sus, iar rezultatul obținut este transferat în celulele corespunzătoare din partea dreaptă a blocului inferior (săgeți roșii din figură). Această operație se efectuează cu toate liniile de sus în jos și cu toate blocurile din fiecare linie. După finalizarea construcției, linia de jos conține un șir de numere, care sunt coeficienții polinomului Zhegalkin, scrise în aceeași succesiune ca și în metoda triunghiului descrisă mai sus.

Metoda însumării

Folosind tabelul de adevăr, este ușor să calculați coeficienții individuali ai polinomului Zhegalkin. Pentru a face acest lucru, trebuie să însumați modulo 2 valorile funcției din acele rânduri ale tabelului în care variabilele care nu sunt în conjuncție iau valori zero.

Să presupunem, de exemplu, că trebuie să găsiți coeficientul la conjuncția xz pentru o funcție a trei variabile f ( x ,  y ,  z ). Nu există o variabilă y în această conjuncție . Să găsim seturile de intrare în care variabila y ia valoare zero. Acestea sunt seturile 0, 1, 4, 5 (000, 001, 100, 101). Atunci coeficientul de la conjuncția xz este egal cu

Deoarece nu există variabile în membrul liber, atunci

Pentru un membru care include toate variabilele, suma include toate valorile funcției:

Să reprezentăm grafic coeficienții polinomului Zhegalkin ca sumă modulo 2 a valorilor funcțiilor în anumite puncte. Pentru a face acest lucru, construim un tabel pătrat, în care fiecare coloană reprezintă valoarea funcției la unul dintre puncte, iar rândul este coeficientul polinomului Zhegalkin. Un punct la intersecția unei anumite coloane și rânduri înseamnă că valoarea funcției într-un punct dat este inclusă în suma pentru un coeficient polinomial dat (vezi figura). Să numim acest tabel T N , unde N  este numărul de variabile ale funcției.

Există un model care vă permite să obțineți un tabel pentru o funcție de N variabile, având un tabel pentru o funcție de N  - 1 variabile. Noul tabel T N +1 este aranjat ca o matrice 2 × 2 de tabele T N , cu blocul din dreapta sus al matricei șters.

Vezi și

Note

  1. ↑ 1 2 Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Prelegeri despre matematică discretă. - SPb., BHV-Petersburg, 2004. - ISBN 5-94157-546-7 , p. 110-111.
  2. ↑ V. P. Suprun. Metoda tabelară de extindere polinomială a funcțiilor booleene // Cibernetică. - 1987. - Nr. 1 . - S. 116-117 .
  3. ↑ V. P. Suprun. Fundamentele teoriei funcțiilor booleene. — M.: Lenand / URSS. - 2017. - 208 p.

Literatură