Disjunktní esenciální množiny implikantů pro CQ Hornovské funkce

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

Klíčová slova

• Disjunktní esenciální množiny
• CQ funkce