Zhegalkin polinom - az
Zhegalkin polinom - polinom át a gyűrűt, hogy egy polinom együtthatók formájában 0 és 1, ha a terméket a összefüggésben. és kívül - kizárólagos vagy. Polinom javasolta 1927-ben Ivan Zhegalkin mint egy kényelmes eszköz, hogy képviselje Boole-függvények. A külföldi szakirodalom, képviselet formájában polinom Zhegalkin nevén algebrai normál forma (ANF).
Tétel Zhegalkin - állítása létezésének és egyediségét a képviselet minden Boole-függvény egy többtagú Zhegalkin.
Zhegalkin polinomot összege modulo két mű nem fordított változók, valamint (ha szükséges) 1. Formálisan Zhegalkin állandó polinom felírható
vagy egy hivatalosabb, mint:
Példák a polinomok Zhegalkin:
előfeltételek
Szerint a posta tétel. A rendszer logikai függvények befejeződött, az szükséges, hogy létezik:
- Legalább egy funkció, nem menti 0.
- Legalább egy funkciót, ne kivéve egyet.
- Legalább egy nem-lineáris függvény.
- Legalább egy nem-monoton függvény.
- Legalább egy nesamodvoystvennaya funkciót.
Ez a követelmény megfelel a rendszer funkcióit. Ennek alapján, és polinomok Zhegalkin épült.
Cuschestvovanie és egyediségét bemutatása
By tétel Zhegalkin minden Boole-függvény leírható egyedileg mint Zhegalkin polinom. Tétel bizonyítható az alábbiak szerint. Vegye figyelembe, hogy a különböző logikai függvények n-változós darab. Ebben a formában van Kötőszavak pontosan 2 n. azért, mert a lehetséges n faktorok vagy minden egyes részét az összefüggésben, vagy sem. A polinom minden ilyen kötőszók ér 0 vagy 1, azaz van egy másik Zhegalkin polinomok n változók. Most elegendő annak bizonyítására, csak az, hogy a különböző polinomok végre a különböző funkciókat. Tegyük fel az ellenkezőjét. Ezután egyenlővé két különböző polinom és mozgó egyikük a másik oldalon az egyenlet, megkapjuk a polinom azonosan nulla, és amelynek nem nulla együtthatók. Akkor úgy a kifejezés egyetlen tényező a legkisebb hossz, azaz a legkevesebb bevont változók benne (bármelyike, ha több is van). Behelyettesítve egység helyén ezeket a változókat, és nullák a fennmaradó helyekre, azt találjuk, hogy ez a halmaz csak egy kifejezés kerül egyetlen érték, amely nulla az egyik készletek értéke 1, ami ellentmondás. Ezért minden Boole-függvény által megvalósított polinom Zhegalkin egyedülálló.
Képviselete a függvény egy többtagú Zhegalkin
Ekvivalens átalakítások DNF
Összehasonlítva a DNF a polinom Zhegalkin nem működik, vagy nem is. Így Zhegalkin polinom lehet beszerezni a DNP, kifejező műveletek VAGY és NEM műveletek modulo-kettő, és az állandó 1. E célból, a következő összefüggéseket kell alkalmazni:
Az alábbiakban egy példát alakulás polinom Zhegalkin DNP:
Amikor transzformációk használt az arány:
Ekvivalens átalakítások PDNF
PDNF megvan az a tulajdonsága, hogy minden értéket a bemeneti változók az egységben kezeli legfeljebb egy tagja a kifejezés. Az ilyen művelet egyenértékű diszjunkcióját kifejezések működés mellett modulo két.
Amikor konvertáló PDNF polinomiális Zhegalkin, cserélje ki az összes diszjunkció elegendő műveletet modulo két és megszabadulni inverzió ekvivalens transzformáció
A következő Karnaugh térkép
Konvertálása Karnaugh térkép Zhegalkin polinom
A logikai függvény három változót kapunk, mely Karnaugh térképet. Ez alakítjuk polinom Zhegalkin a következő lépéseket:
- Úgy véljük, minden Karnaugh térkép sejtek növekvő sorrendben az egységek száma a kódokat. A funkció három változó, a szekvenciája sejtek 000-100 - 010-001 - 110-101 - 011-111. Minden sejt Karnaugh térképek társult tagja Zhegalkin polinom helyzetétől függően a kódját, amelyen az egységek. Például, a sejt 111 megfelel egy tagja az ABC, sejt 101 - tagja az AC, a sejt 010 - tagja a B, sejt-000-1 tagja.
- Ha az adott cellában 0, folytassa a következő cellában.
- Ha a cella megfontolás alatt 1, adjuk hozzá a megfelelő kifejezést a polinom Zhegalkin, fordítsa meg a Karnaugh térkép minden sejtben, ahol ez a kifejezés értéke 1, és menj a következő cellába. Például, ha figyelembe vesszük a sejt a 110 van egy egység, a polinom Zhegalkin hozzáadott AB tagja, és felfordítva az összes Karnaugh térképen sejt, ahol A = 1 és B = 1. Ha az egyik cella egyenlő 000, a polinom hozzáadjuk Zhegalkin tag 1 és fordított a teljes térképet Carnot.
- Az átalakítási folyamat befejezettnek tekinthető, ha az összes térképet Karnaugh sejtek már nulla után a következő inverzió.
Triangle módszer [1]
Példa igazság táblázat transzformációs Zhegalkin polinom függvény három változót
Triangle eljárás kódolja igazság táblázatában Zhegalkin polinom építve egy háromszög alátámasztó asztalon megfelelően az alábbi szabályokat:
- Építeni egy teljes igazság táblázat, amelyben a sorok szerint növekvő sorrendben bináris kódok 000 ... 00-111 ... 11.
- Construct a kiegészítő háromszög alakú tömb, ahol az első oszlopban ugyanaz, mint az oszlop az értékeket az igazság táblázat.
- Cell minden következő oszlop elő modulo-2 két sejtek az előző oszlop - állt ugyanabban a sorban, és a vonal alatti.
- Oszlopok segédtáblázatot bináris kódok számozása azonos módon, mint a sorok az igazság táblázat.
- Mindegyik bináris kód van társítva egyik tagja a polinom Zhegalkin helyzetétől függően a kódját, amelyen az egységek. Például, a sejt 111 megfelel egy tagja az ABC, sejt 101 - tagja az AC, a sejt 010 - tagja a B, sejt-000-1 tagja, stb ...
- Ha a felső sorban egy oszlop egy, a megfelelő kifejezés van jelen a polinom Zhegalkin.
irodalom
Nézze meg, mit „zhegalkin polinom” más szótárak:
A polinom Zhegalkin - zhegalkin polinom polinom fölött Z2, azaz egy polinom együtthatók formájában 0 és 1, ha a terméket a összefüggésben, és a kizáró vagy kiegészítésként. Polinom javasolta 1927-ben I. Zhegalkin, mint egy kényelmes eszköz ... Wikipedia
Boole-függvény - Ez a cikk vagy szakasz egy listát a források vagy külső linkek, de az egyes állítások források továbbra is tisztázatlan, mivel hiányzik a lábjegyzetek ... Wikipedia
Logikai kifejezések - Az elmélet a diszkrét funkcionális rendszerek a Boole-függvény nevezzük függvényében típusú. ahol egy logikai sor, és n nem negatív egész, amely az úgynevezett argumentumainak száma a funkció vagy terepen. Elements 1 (egy) és 0 (nulla) értelmezi a szabvány ... ... Wikipedia
A lineáris függvény - Példák lineáris függvények. Lineáris függvénye formájában funkciót (függvények egy változó). A fő tulajdonsága lineáris függvénnyel növekmény az f függvény ... Wikipedia
- Zhegalkin polinom. Dzhessi Rassel. Ez a könyv lesz összhangban a rendelését Technology Print-on-Demand technológiát. High Quality Content Wikipedia cikket! Zhegalkin polinom - polinom át a gyűrűt, ami ... Tovább Vásárlás 870 rubelt