Zhegalkin polinom - polinom peste inelul, care este un polinom cu coeficienți în formă de 0 și 1, în cazul în care produsul este luat conjuncție. și, ca adaos - exclusiv sau. Polinomial a fost propusă în 1927 de către Ivan Zhegalkin ca un mijloc convenabil de a reprezenta funcții booleene. În literatura străină, reprezentarea sub forma unui Zhegalkin polinom numit de obicei forma normală algebric (ANF).
Teorema Zhegalkin - afirmarea existenței și unicitatea reprezentării oricărei funcții booleene ca Zhegalkin polinom.
Zhegalkin polinom este suma modulo două lucrări de variabile non-răsturnate, precum și (dacă este necesar) 1. Formal Zhegalkin polinom constantă poate fi scrisă ca
sau într-o mai formalizata ca:
Exemple de polinoame Zhegalkin:
Cerințe preliminare
Conform teoremei lui Post. sistemul de funcții booleene este completă, este necesar ca există:
- Cel puțin o funcție, nu salvați 0.
- Cel puțin o funcție, nu salvați unul.
- cel puțin o funcție neliniară.
- Cel puțin o funcție non-monotonă.
- Cel puțin o funcție nesamodvoystvennaya.
Această cerință corespunde sistemului de funcții. Pe baza sa, și polinoame Zhegalkin construit.
Cuschestvovanie și unicitatea prezentării
Prin Teorema Zhegalkin orice funcție booleană poate fi reprezentat în mod unic ca Zhegalkin polinom. Teorema poate fi demonstrată după cum urmează. Rețineți că diferite funcții booleene de piese de n variabile. În această formă se conjuncþii exact 2 n. din cauza n factori posibili sau fiecare parte a conjuncției sau nu. În polinomul în fiecare astfel de conjuncții în valoare 0 sau 1, adică există o diferite polinoame Zhegalkin de n variabile. Acum este suficient pentru a dovedi că diferitele polinoame implementa diverse funcții. Să presupunem contrariul. Apoi, echivalând două polinomial diferite și se deplasează unul dintre ei la cealaltă parte a ecuației, obținem polinomul identic zero, și având coeficienți nenuli. Apoi, ia în considerare termenul cu un singur coeficient de cea mai mică lungime, care este, cu cel mai mic număr de variabile implicate în ea (oricare, în cazul în care există mai multe). Substituind unitate la locul acestor variabile, și zerouri în locurile rămase, constatăm că acest set este doar un termen are o singură valoare care este zero, pe una dintre seturile este setat la 1, o contradicție. Prin urmare, orice funcție booleană implementată de un Zhegalkin polinom unic.
Reprezentarea funcției ca Zhegalkin polinom
Folosind transformări echivalente DNF
Comparativ cu un DNF în polinomul Zhegalkin nici o operație SAU și NU. Astfel, Zhegalkin polinom poate fi obținut din DNP, operații SAU NU și operațiuni care exprimă prin modulo doi, iar constanta 1. În acest scop, se aplică următoarele relații:
Mai jos este un exemplu de transformare în polinomului Zhegalkin DNP:
Atunci când transformările utilizate raportul:
Folosind transformări echivalente PDNF
PDNF are proprietatea că pentru toate valorile variabilelor de intrare în unitatea nu ocupă mai mult de un membru al expresiei. Pentru o astfel de operațiune este echivalentă cu disjunctiile funcționare expresii plus modulo doi.
Când se face conversia PDNF în polinomial Zhegalkin, înlocuiți toate disjuncției este suficientă pentru operațiunile modulo doi și a scăpa de inversiuni folosind transformare echivalentă
Folosiți harta Karnaugh
Conversia hartă Karnaugh în Zhegalkin polinomial
Funcția logică a trei variabile, reprezentată ca o hartă Karnaugh. Acesta este transformat într-un polinom Zhegalkin următorii pași:
- Considerăm că toate celulele harta Karnaugh în ordine crescătoare a numărului de unități în codurile lor. Pentru funcția de trei variabile, secvența de celule este 000-100 - 010-001 - 110-101 - 011-111. Fiecare celulă Karnaugh maps membru asociat Zhegalkin polinomială în funcție de poziția codului în care unitățile sunt. De exemplu, celula 111 corespunde unui membru al ABC, celula 101 - membru al CA, celula 010 - membru B, celulă 000-1 membru.
- Dacă în celula dată este 0, du-te la celula următoare.
- În cazul în care celula în cauză este 1, se adaugă termenul corespunzător în polinomial Zhegalkin, inversează harta Karnaugh în toate celulele, în cazul în care acest termen este egal cu 1 și du-te la celula următoare. De exemplu, atunci când se analizează celula 110 există o unitate, polinomului Zhegalkin adăugat membru AB și invertit toată celula harta Karnaugh, unde A = 1 și B = 1. Dacă o celulă este egală cu 000, polinomul este adăugat membru Zhegalkin 1 și răsturnată întreaga hartă a Carnot.
- Procesul de conversie poate fi considerată completă atunci când toate celulele harta Karnaugh devine zero, după următoarea inversiune.
Triangle Metoda [1]
transformare Exemplu adevăr tabel Zhegalkin funcție polinomială de trei variabile
Triangle Metoda codifică tabelul de adevăr în Zhegalkin polinom prin construirea unui tabel de sprijin triunghiular, în conformitate cu următoarele reguli:
- Construiți un tabel complet de adevăr, în care rândurile sunt în ordinea crescătoare a codurilor binare de la 000 ... 00-111 ... 11.
- Construirea matrice triunghiular auxiliar, în care prima coloană aceeași ca și coloana din valorile din tabelul de adevăr.
- Cell în fiecare coloană ulterioară se obține prin modulo 2 a două celule ale coloanei anterioare - stând în aceeași linie și linia de mai jos.
- Coloane tabel auxiliar codurile binare sunt numerotate în același mod ca și rândurile din tabelul de adevăr.
- Fiecare cod binar este asociat cu unul dintre membrii polinomului Zhegalkin în funcție de poziția codului în care unitățile sunt. De exemplu, celula 111 corespunde unui membru al ABC, celula 101 - membru al CA, celula 010 - membru B, celulă 000-1 membru, etc ...
- Dacă linia superioară a unei coloane este una, termenul corespunzător este prezent în polinomial Zhegalkin.
literatură
Vezi ce „zhegalkin polinom“ în alte dicționare:
Polinomul Zhegalkin - zhegalkin polinom polinom peste Z2, adică un polinom cu coeficienți în formă de 0 și 1, în cazul în care produsul este luat conjuncție, și exclusive sau ca adaos. Polinomial a fost propusă în 1927 de către I. Zhegalkin ca un mijloc convenabil ... Wikipedia
Funcția boolean - Acest articol sau secțiune este o listă de surse sau legături externe, dar surse individuale declarații rămân neclare din cauza lipsei de note de subsol ... Wikipedia
expresii booleene - Teoria sistemelor funcționale discrete ale funcției booleene se numește o funcție de tip. în cazul în care un set Boolean și n întreg nenegativ, care se numește aritatea funcției sau de teren. Elementele 1 (unu) și 0 (zero) este interpretat ca standard ... ... Wikipedia
O funcție liniară - Exemple de funcții liniare. Funcția liniară a funcției de formă (pentru funcțiile unei variabile). Proprietatea principală a funcțiilor liniare: creșterea funcției f ... Wikipedia
- polinomul Zhegalkin. Dzhessi Rassel. Această carte va fi făcută în conformitate cu comanda pe tehnologia de imprimare Tehnologie-on-Demand. Conținutul de calitate înaltă prin articole wikipedia! Zhegalkin polinomul - polinom peste inelul, care este ... Citeste mai mult Vand pentru 870 de ruble