Tud Intuit, előadás, egyenértékű képleteket és szokásos formák
polinomok Zhegalkin
Zhegalkin polinom másik érdekes alosztály képletek megengedik, hogy képviselje logikai funkciókat.
Definíció 4.4. Polinomok Zhegalkin fent megnevezett Formula beállított funkciók FJ =<0, 1, *, +> (Ahol a * - van egy másik szimbólumot az összefüggésben).
Így minden Zhegalkin polinom (esetleg tágulás után zárójelben és a „vezetési” hasonló kifejezések) jelentése a sum (modulo 2) pozitív (monoton) elemi kötőszavak (azaz az elemi kötőszók nélkül negatívok). Mivel a + és * csak a jogszabályok asszociatív. elhagyjuk a konzolok, kivéve, hogy a érvek erősebbek linkek * rögzítésekor Zhegalkin polinom, mint +
Ez könnyen ellenőrizhető, hogy mi a következő ekvivalencia:
Ezekből ekvivalencia és 4.1 Tétel könnyen kap az első része a következő állítás.
Tétel 4.3. Bármely Boole-függvény által megadott polinom ott Zhegalkin. Ő egyedülálló akár permutáció kifejezések és változók sorrendjében összefüggésben.
Az igazolás megléte ilyen polinom abból a tényből következik, hogy minden olyan CNF vagy DNF használatával mondta polinom azonos lelet ekvivalencia Zhegalkin. (J1) - (J3) lehetővé teszi, hogy minden előfordulás helyén a + és *. és (J4) - szaporodnak a kapott polinomok után az ilyen csere.
Annak bizonyítására, egyediségét a képviselet kiszámítjuk a számos különböző polinomok Zhegalkin változók. Minden pozitív elemi összefüggésben néz Xi1 *. * Xik. ahol 1 <= i1 <. ahol minden egyes együtthatók értéke 0 vagy 1. Következésképpen a száma polinomok Zhegalkin egyenlő, azaz a Között Boole-függvények n-változós. Ezért minden meg van adva pontosan egy polinom Zhegalkin. Példa 4.3. Legyen az f (X1, X2, X3) kap egy DNF. Keressünk egy polinom Zhegalkin. ami szintén meghatározza a funkciót. Először helyébe *. majd a egyenértékűség (J1), megszünteti a tagadás és kap: Megszorozzuk a szabályokat (J4), megkapjuk: Ekvivalencia (J3) megszünteti Ismét segítségével (J4), megszorozzuk az első két zárójelben, és megszünteti a kiújulás változók kötőszavak: Leegyszerűsítjük ezt az összeget az egyenértékűség és. Ennek eredményeképpen kapunk egy polinom Zhegalkin egyenértékű az eredeti DNF Ha az f függvény (X1. Xn) táblázatos formában, az építési végrehajtási Zhegalkin polinom lehet használni a módszert a meghatározatlan együtthatók. Társult i -edik értékhatárrendszere táblázatban felsorolt változók pozitív összefüggésben változó egyenlő 1 a készletben. Különösen K1 - üres összefüggésben. K2 = Xn. K3 = Xn-1. K4 = (Xn * Xn-1). stb Ezután, hogy megkapjuk a kívánt polinom Zhegalkin elegendő meghatározni minden együttható az expressziós Behelyettesítve ebben az egyenletben a változók értéke a beállított, akkor kap 2 n lineáris egyenletrendszer n 2 ismeretlen együtthatók. Megoldása ez a rendszer, megkapjuk a szükséges polinom Zhegalkin. Ez a rendszer háromszög, és könnyen megoldható „felülről lefelé”: az egyes határozza meg az értékeket az egyenlet megfelelő készlet. Példa 4.4. Tekintsük példaként az f (X1. Xn). mivel a következő táblázat tartalmazza.
Kapcsolódó cikkek