Publikace na Matematicko-fyzikální fakulta |
2009
Abstrakt
V tomto článku zkoumáme třídu CQ Hornovských funkcí představenou v [5]. Hlavním výsledkem je důkaz, že pro libovolnou CQ Hornovskou funkci f platí rovnost mezi maximálním počtem po dvou disjunktních esenciálních množin implikátů funkce f a minimálním počtem klauzulí v jakékoli CNF reprezentaci funkce f.