Disjoint essential sets of implicates of a CQ Horn function

Autor:	Petr Kučera, Ondřej Čepek
Rok vydání:	2011
Předmět:	Discrete mathematics Combinatorics Class (set theory) Artificial Intelligence French horn Computer Science::Logic in Computer Science Applied Mathematics Disjoint sets Circuit minimization for Boolean functions Upper and lower bounds Horn function Mathematics
Zdroj:	Annals of Mathematics and Artificial Intelligence. 61:231-244
ISSN:	1573-7470 1012-2443
DOI:	10.1007/s10472-011-9263-9
Popis:	In this paper we study a class of CQ Horn functions introduced in Boros et al. (Ann Math Artif Intell 57(3---4):249---291, 2010). We prove that given a CQ Horn function f, the maximal number of pairwise disjoint essential sets of implicates of f equals the minimum number of clauses in a CNF representing f. In other words, we prove that the maximum number of pairwise disjoint essential sets of implicates of f constitutes a tight lower bound on the size (the number of clauses) of any CNF representation of f.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::352a0bc0f46d69137924b783e147ac38 https://doi.org/10.1007/s10472-011-9263-9 Zobrazit plný text záznamu Full text from SpringerLink