| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6872590 | Discrete Applied Mathematics | 2012 | 18 Pages |
Abstract
⺠We study certain lower bounds for a CNF size (number of clauses) of a Boolean function. ⺠The lower bound is given by the maximum number of disjoint essential sets of implicates. ⺠Boolean functions for which this lower bound is tight are called coverable. ⺠Non-coverable functions exist and the gap may be arbitrarily large. ⺠Complexity of computing the lower bound under different conditions is investigated.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
OndÅej Äepek, Petr KuÄera, Petr Savický,