<p>U radu je razmatran problem dizajna i minimizacije rekurzivne<br />Bulove formule konstruisane za proizvoljnu Bulovu funkciju y:BN<br />→B.<br />U cilju rešavanja ovog problema, predstavljene su dve algoritamske<br />heuristike za minimizaciju rekurzivne Bulove formule. Minimizacija<br />rekurzivne Bulove formule vrši se korišćenjem regularnih poredaka<br />pozitivnih proizvod termova. U disertaciji je dokazano kako je ova<br />regularnost poredaka zapravo potreban i dovoljan uslov da željena<br />Bulova funcija y bude korektno predstavljena rekurzivnom Bulovom<br />formulom konstruisanom na osnovu tih poredaka. Pokazano je i kako<br />predstavljeni algoritmi daju bolje rezultate za veći broj instanci<br />problema u poređenju sa algoritmima dostupnim u literaturi.</p> / <p>In this thesis, the problem of design and minimization of recursive Boolean<br />formula, based on an arbitrary Boolean function y:BN<br />→B , is considered. As a<br />solution of a problem, two heuristic algorithms that minimize the length of<br />recursive Boolean formula, were presented. Minimization, itself, is done by<br />using regular orders of positive product terms. In the thesis it was proved that<br />the regularity of orders represents necessary and sufficient condition for<br />correct representation of Boolean function y by recursive Boolean formula<br />based on such regular order. Developed algorithms are compared with other<br />heuristic algorithms for recursive Boolean formula minimization, available in<br />the literature, and it is shown how algorithms proposed in this thesis provide<br />better results for more problem instances.</p>
Identifer | oai:union.ndltd.org:uns.ac.rs/oai:CRISUNS:(BISIS)86541 |
Date | 02 July 2014 |
Creators | Teodorović Predrag |
Contributors | Malbaša Veljko, Živanov Ljiljana, Dautović Staniša, Struharik Rastislav, Milutinović Veljko |
Publisher | Univerzitet u Novom Sadu, Fakultet tehničkih nauka u Novom Sadu, University of Novi Sad, Faculty of Technical Sciences at Novi Sad |
Source Sets | University of Novi Sad |
Language | Serbian |
Detected Language | English |
Type | PhD thesis |
Page generated in 0.0015 seconds