Disjoint essential sets of implicates of a CQ Horn function |
| |
Authors: | Ond?ej ?epek Petr Ku?era |
| |
Affiliation: | 1.Department of Theoretical Computer Science and Mathematical Logic,Charles University,Praha 1,Czech Republic;2.Institute of Finance and Administration - V?FS,Praha 10,Czech Republic |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|