Algoritmusok építésére polinom Zhegalkin

Úgy véljük, algoritmusok építésére polinom Zhegalkin Boole-függvény adott különböző módon, nevezetesen: egy tökéletes DNF DNF önkényes képlet, és az igazság asztalra.

Egy algoritmust szerkesztett polinom Zhegalkin SovDNF (az igazolást a tétel a létezését polinom Zhegalkin).

Kezdeni. Állítsa tökéletes DNF f (x1. ..., xn).

1. lépés: Cserélje minden karaktert a karakter diszjunkcióját diszjunkció kivételével.

2. lépés Lecseréljük minden változó x inverziójával egyenértékű képlet x 1.

3. lépés: Kinyitjuk a zárójelben.

4. lépéssel képlet hagyni a megfelelő párt a szempontból.

Vége. Zhegalkin kapott polinom függvény f (x1. ..., xn).

Példa. Keressünk egy polinom Zhegalkin többsége logikai funkció tökéletes DNF.

Egy algoritmust szerkesztett polinom Zhegalkin DNP (az egyenértékűség K1 K2 = K1 K2 K1 K2).

Kezdeni. DNF adott egy tetszőleges függvény f (x1. ..., xn).

1. lépés: Osszuk a DNP párosított kötőszavak, előnyösen ortogonális (ha páratlan számú kötőszavak, egyikük marad pár).

2. lépés: Cserélje mindegyik pár diszjunkcióját összetalálkozások képletű K1 K2 K1 K2 vagy K1 K2 képletű K1 K2. ha K1 és K2 ortogonális.

3. lépés: A kapott formula találni egy másik diszjunkciót A1, A2 és cserélje ki a képlet A1 A2 A1 A2. Ismételje a 3. lépést, amíg csak lehetséges.

4. lépés Cserélje minden változó x inverziójával egyenértékű képlet x 1.

5. lépés: Kinyitjuk a zárójelben.

6. lépés törlődnek a képlet egy pár azonos kifejezések.

Vége. Zhegalkin kapott polinom függvény f (x1. ..., xn).

Példa. Keressünk egy polinom függvény Zhegalkin többsége DNF.

Megjegyezzük, hogy a többség polinom függvény kapott az utolsó két példa ugyanaz fel a rendelést kötőszavak, és ez természetes (egyediségét tétel Zhegalkin polinom).