Fie funcția reprezentată în PDNF. în cazul în care. diferite. Conform ecuației (4.22). Cu toate acestea, conjuncția a două elemente constitutive diferite ale unității și egal cu 0 atunci. cel puțin unul. și apoi, în consecință. astfel . Din această formulă rezultă că operațiunea poate fi înlocuită PDNF operațiune disjuncție suma modulo 2. Această formă se numește perfectă formă normală polinomul (SPNF).
Exemplu. Obțineți funcția SPNF.
Pentru SPNF reprezintă funcția în PDNF:
Apoi, funcția SPNF poate fi scris după cum urmează:
Dacă o formulă de algebră arbitrară Zhegalkin deschide parantezele conform regulii (4.18) și să facă tot posibilul simplificarea relațiilor (4.19) și (4.20), obținem o formulă având forma unei sume de produse, adică, polinomul mod 2. Această formulă se numește polinomul Zhegalkin . polinomul Zhegalkin are forma
Exemplu. Obțineți funcția polinomială Zhegalkin.
1. Funcția SPNF este reprezentată după cum urmează (vezi. Exemplul anterior). Rid de negative folosind relația (4.21)
.
Îndepărtarea parantezele și aplicarea formulei (4.19) și (4.20), obținem
2. Utilizarea (4.22) și (4.21), obținem
Scoaterea suporturilor și aplicarea formulei (4.19) și (4.20), obținem
Pentru orice polinom al primei formule este confecționat în mod obișnuit dintr-o multitudine de ligamente formule echivalente. și apoi preparate din acestea polinom.
Exemplu. Obțineți funcția polinomială Zhegalkin.
Folosind definiția funcțiilor elementare (. Tabelul 4.6), obținem SKNF implicare :. În continuare vom obține un polinom :.
Dacă funcția polinomială Zhegalkin are forma
,
atunci funcția se numește liniară.
Exemplul 4.5. Se determină dacă funcția liniară:
Astfel, în funcția polinomială nu conjuncție de variabile, astfel încât funcția este liniară. In exemplul anterior, în funcție polinomială participat conjuncția variabile. și anume - funcția neliniară.
Teorema 4.3. Pentru orice funcție logică există o Zhegalkin polinomial, și numai unul.
Dovada: Existența unui polinom a fost dovedit. Pentru a demonstra unicitatea, ne arată că mulțimea tuturor funcțiilor între variabilele și mulțimea tuturor polinoamelor în Zhegalkin o corespondență. Numărul de state membre diferite (de exemplu, conjunctii de variabile) polinoame în variabilele egal cu numărul tuturor subseturi ale elementelor, adică (subgrup gol corespunde unui membru 1). Numărul de diferite polinoame, care pot fi formate din aceste conjuncții, egal cu numărul tuturor subseturi de conjuncțiilor, adică (conjuncții gol subsetul corespunzător polinomială 0). Astfel, numărul de polinoame Zhegalkin în variabilele egal cu numărul tuturor funcțiilor variabilelor. Deoarece diferitele funcții corespund diferitelor polinoame (una și aceeași formulă nu poate reprezenta două caracteristici distincte), se astfel între seturile de funcții și polinoame într-o singură corespondență, ceea ce demonstrează unicitatea polinomial pentru fiecare funcție. Acest lucru dovedește teorema.
Prin Teorema 4.3 echivalență poate verifica formule. În acest scop, în fiecare formulă este convertit Zhegalkin polinomul și face compararea polinoamelor.