Horn functions and their DNFs

Peter L. Hammer, Alexander Kogan

Research output: Contribution to journalArticlepeer-review

39 Scopus citations

Abstract

In this paper we introduce the concept of Horn functions and investigate the structure of their disjunctive normal forms. Horn functions arise in a variety of applications, including in particular the analysis of production rule knowledge bases of propositional expert systems. The goal of this paper is to reduce the study of the irredundant prime disjunctive normal forms of Horn functions to the study of the irredundant prime disjunctive normal forms of pure Horn functions. This reduction is achieved by proving that every prime irredundant disjunctive normal form of a Horn function consists of a prime irredundant disjunctive normal form of its "pure Horn component", and of a "positive restriction" of the function. We provide a constructive characterization of all the positive restrictions, and present an efficient algorithm for decomposing any Horn function into its pure Horn component and its positive restriction. Finally, we reduce in quadratic time the minimization of a Horn function to the minimization of its pure Horn component.

Original languageEnglish (US)
Pages (from-to)23-29
Number of pages7
JournalInformation Processing Letters
Volume44
Issue number1
DOIs
StatePublished - Nov 9 1992

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Boolean functions
  • Combinatorial problems
  • Horn formulae
  • computational complexity
  • disjunctive normal forms
  • knowledge bases

Fingerprint Dive into the research topics of 'Horn functions and their DNFs'. Together they form a unique fingerprint.

Cite this