0000127

TkiltRDZlNIC 0.1.2

Kaźdoeu składnikowi (Iloczynowi) sumy logicznej, ota-ncwięccj mlnleiolnę formułę alternutywnę funkcji oono-tonlcznoj, odpowlado wzojemnio Jodnoznocznle woktor ■lnisolny toj funkcji. (Odpowiedniość te Joet okroś-lone w ton epooób, źo zmicnnya wyetępujęcya w Iloczynie odpowiadaję jodynkowe okładowe wektora elnlmelne-go, a pozostałe okładowe eę równe O.

Dowód i

Zouwożmy, żo Żaden okładnik (iloczyn) mfo nie jeet czyn -niklom (częśclę) innego iloczynu tej nfa. Gdyby bowiem tak było, to stosujęc równość (0.1.5) możno by było zredukować to wy-rożonle, o mfa ject wyrażeniem nleredukowolnym w ten eposób (mo nojmniejszę ilość okłudników cumy). Zouwożmy również, że żadne dwa wektory minimolno nie tę zo oobę w relacji —J . Wynika to bozpośrcdnio z dofinicji funkcji monotonlczneJ i wektora minimalnego.

Odpowiodniość określona w tezie twierdzonlo przyporządkowuje różnym składnikom eifo wektory, a różnym woktoroo elnlmalrlya różne iloczyny. Wyetorczy zatem wykazać, że wektor przyporzęd-kowony okłodnikowl mfo Joot wektorem minimalnym, a iloczyn przyporządkowany woktorowl minimalnomu jeet składnikiem mfa.

woźmy pod uwagę dowolny iloczyn z mfo oroz woktor x^ⁿ), którogo jedynkowyml okładowymi będę wyłącznie składowe odpowie-oojęco zmiennym wyotępujęcym w tym iloczynie. Przy tym wektorze * wybrany iloczyn ma wartość 1, o wszystkie pozostałe iloczyny muszę mieć wortość O, ponieważ w każdym z nich występuje przynajmniej Jedna zmionno różno od zmionnych w wybranym iloczynie 1 aktualnie przy woktorze x^ⁿ^ ma wortość O . Gednocześnie f(*(ⁿ)) > i, ponieważ mfo Jeet alternatywę omawianych iloczy -nów. Wszystkie wektory poprzedzojęco woktor    i różne od

tego wektora, maję przynajmniej jedna zorowę skłodowę ze zbioru jedynkowych składowych woktora x'ⁿ^ i zeruję vfybrany ilo -czyn, o tym eomym funkcję f. Zatem wektor x^ⁿ' jest, zgodnie z definicję, wektorem minimalnym funkcji f. Wykazaliśmy, źo każdemu okłodnikowl mfo jest przyporządkowany, w omewleny sposób, woktor minlmolny. Niech toraz x'ⁿ^ będzie dowolnym wek •

torom minimalnym funkcji f. .Zgodnie z definicjo f(j^ⁿ^) • 1. to znoczy przynojmnloj jodon zo okładników mfo ma wortoóć 1. Skłodnik ton Joot iloczynom nioktórych zmlonnych. odpowiodojo-cych Jedynkowym okłodor/ym woktora ⁿ ), Muai on Jodnok zawlo-roć wozyotklo zmlonno odpowiadajoco jodynkowym układowym nok - ¹ toro X*"), poniowoż zomlano w woktorzo minimalnym dowolno). JodynkówoJ~ okłodowoj no zorowp powoduje, to funkcjo przyjmują wortoóć 0. Wynika z togo, to dlo kożdogo woktore oinimalnogo iotniojo w mfo oklodnik ( iloczyn) aojęcy źędono ,*ostuć. Kończy to dowód twlordzonle 0.1.2.

Korzyotojoc z twierdzenia 0.1.2 można w atoounkowo lotny opooób wyznoczyć zbiór woktorów minimalnych dowolnoj funkcji monotonicznoj, okroólonoj za pomocQ eumoiloczynu boolowokiogo. co Joot ozoroko wykorzyatywono w różnych algorytmach tooril grafów. Wyutorczy bowiom wyroźonio boolowakio, okroólojęce dong funkcjv» przekoztolcić (zrodukować) do postaci mfa.