Tökéletes polinom normál forma
Legyen a függvény képviselt PDNF. hol. más. Szerint egyenlet (4.22). Azonban a összefüggésben két különböző összetevőinek az egység és a értéke 0 ettől. legalább egy. majd ennek következtében. így . Ebből a képletből következik, hogy a művelet lehet cserélni PDNF diszjunkciót művelet összege modulo 2 Ez a forma az úgynevezett tökéletes polinom normál forma (SPNF).
Példa. Get SPNF funkciót.
A SPNF képviseli a funkció PDNF:
Ezután SPNF funkció felírható a következőképpen:
Ha egy tetszőleges formula algebra Zhegalkin nyissa meg a zárójelben a szabály szerint (4,18), és az összes lehetséges egyszerűsítését kapcsolatok (4.19) és (4.20), megkapjuk a képletet, amely formájában a szorzatok összege, vagyis a polinom mod 2. Ez a képlet az úgynevezett polinom Zhegalkin . Zhegalkin polinom formában van
Példa. Get Zhegalkin polinom függvény.
1. SPNF funkció képviseletében a következők szerint (lásd. Az előző példa). Megszabadulni negatívok felhasználva a (4.21)
.
Eltávolítása a konzolok és képletének alkalmazásával (4,19) és (4.20), megkapjuk
2. A (4.22) és (4.21), megkapjuk
Eltávolítása a konzolok, és a készítmény alkalmazása (4.19) és (4.20), megkapjuk
Bármely polinomja az első készítmény tipikusan felépítve több ekvivalens általános képletű szalagok. majd ezekből előállított polinom.
Példa. Get Zhegalkin polinom függvény.
A meghatározás az elemi függvények (. 4.6 táblázat), azt kapjuk SKNF kihatással :. Ezután kap egy polinom :.
Ha Zhegalkin polinom függvény formájában
,
akkor a függvény az úgynevezett lineáris.
Példa 4.5. Határozza meg, hogy a lineáris függvény:
Így a polinom függvény nem együtt változó, így a függvény lineáris. Az előző példában a polinom függvény részt vett az összefüggésben változó. azaz - a nem-lineáris függvény.
Tétel 4.3. Ha bármilyen logikai függvény létezik olyan polinom Zhegalkin, és csak egy.
Bizonyítás: A létezés egy polinom bebizonyosodott. Annak bizonyítására, egyediségét, azt mutatják, hogy a készlet minden funkció az egyes változók között, és a készlet minden polinomok Zhegalkin egy levelezés. A számos különböző tagállamok (azaz kötőszó változók) polinomok a változók számával megegyező összes részhalmazainak elemek, azaz (üres részhalmaza megfelel egy tag 1). A számos különböző polinomok, amelyek képezhetők ezek a kötőszók, egyenlő a száma az összes részhalmazainak kötőszavak, azaz (üres részhalmaza kötőszók megfelelő polinom 0). Így a több Zhegalkin polinomok a változók számával megegyező összes funkcióját a változók. Mivel a különböző funkciók megfelelnek a különböző polinomok (egy és ugyanazon általános képletű nem képviseli két különböző funkciók), ez ezáltal sorozatok között a funkciók és a polinomok egy levelezés, ami azt bizonyítja, polinom egyediségét az egyes funkciók. Ez azt bizonyítja, a tétel.
A Tétel 4.3 egyenértékűség ellenőrizheti képletek. Ebből a célból minden képletben alakítjuk Zhegalkin polinom, és összehasonlítjuk a polinomok.