Publikace na Matematicko-fyzikální fakulta |
2011
Abstrakt
V článku studujeme třídu CQ hornovských funkcí zavedenou Boros a kol. (2010). Dokážeme, že maximální počet vzájemně disjunktních esenciálních množin implikantů funkce f tvoří těsnou dolní mez pro velikost (jako počet klauzulí) nějaké CNF reprezentace f