|
|
Topološki model Bulove funkcije
Uspostavljamo 1-1 korespondenciju temena n-kuba sa termima KDNF: Izaberemo koordinatni sistem za jedinični n-kub sa koordinatam X1,X2,...,Xn. Svakom temenu takvog n-kuba pridružujemo term čiji je binarni zapis α 1 α2, ..., α n. Dekadni broj odredjen ovim binarnim zapisom zovemo temeni broj. k-kub(k <_ (manje i jednako) n) sadržan u n-kubu sadrži 2 k temena ,odnosno 2 k terma KDNF. S obzirom da termi koji odgovaraju temenima k-kuba,nakon sparivanja odredjuju term sa (n-k) promenljivih, k-kub možemo shvatiti kao model terma koji sadrži (n-k) promenjljivih. Za dati m-kub (m Teorem o identičnosti po zbiru: Potreban,dovoljan uslov da dva k-kuba ,sadržana u n-kubu(n _> (vece i jednako)k_> (vece i jednako)1 ) i čije odgovarajuće 1-grane imaju iste pravce,budu identična ,je jednakost zbirova njihovih naspramnih temenih brojeva. Svakoj minimalnoj formi g funkcije f ,odgovara skup koji obuhvata temene brojeve funkcije f.Takav skup kubova zovemo minimalni pokrivač. Sistem baznih kubova : Bazni kub je svaki kub kompleksa kubova date Bulove funkcije, koji nije grana nekog drugog kuba tog kompleksa. Svaki minimalni pokrivač sastoji se od baznih kubova. Skup baznih kubova koji pokriva temene brojeve date Bulove funkcije je nesuvišni pokrivač P, ako pri udaljavanju bar jednog baznog kuba neklo teme ostaje nepokriveno. Svaki minimalan pokrivač je nesuvišan. Bazna zvezda temena je skup baznih kubova koji ulaze u kompleks kubova date funkcije i sadrže to teme. Bazna zvezda je suštinska ako ne sadrži neku drugu baznu zvezdu. Teme koje pripada suštinskoj zvezdi zove se suštinsko teme. Nesuvišni pokrivač skupa suštinskih temena date funkcije ima svojstvo: ako iz njega isključimo neki bazni kub, onda će ostati nepokriveno neko suštinsko teme. Vezu suštinskih zvezda sa nesuvišnim pokrivačem sistema baznih kubova daje sledeća teorema: Neka je P φ-skup svih nesuvišnih pokrivača suštinskih temena funkcije f i Pr-skup svih nesuvišnih pokrivača temena funkcije f, onda je P φ= Pr .