Exclusive and essential sets of implicates of Boolean functions

Endre Boros, Ondřej Čepek, Alexander Kogan, Petr Kučera

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

In this paper we study relationships between CNF representations of a given Boolean function f and certain sets of implicates of f. We introduce two definitions of sets of implicates which are both based on the properties of resolution. The first type of sets, called exclusive sets of implicates, is shown to have a functional property useful for decompositions. The second type of sets, called essential sets of implicates, is proved to possess an orthogonality property, which implies that every CNF representation and every essential set must intersect. The latter property then leads to an interesting question, to which we give an affirmative answer for some special subclasses of Horn Boolean functions.

Original languageEnglish (US)
Pages (from-to)81-96
Number of pages16
JournalDiscrete Applied Mathematics
Volume158
Issue number2
DOIs
StatePublished - Jan 28 2010

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Boolean minimization
  • Essential sets
  • Exclusive sets
  • Horn functions

Fingerprint Dive into the research topics of 'Exclusive and essential sets of implicates of Boolean functions'. Together they form a unique fingerprint.

Cite this