E. Toman and L. Haviarová
Received: June 26, 2012; Revised: October 15, 2012; Accepted: January 4, 2013
Abstract. In the present paper we describe relations between the interval graph of a Boolean function, its abbreviated disjunctive normal form and its minimal disjunctive normal forms. The inteval graph of a Boolean function f has vertices corresponding to the maximal intervals of f and any two vertices are joined with an edge if the corresponding maximal intervals have nonempty intersection.
Keywords: Boolean function; interval graph; disjunctive normal form.
AMS Subject classification: Primary: 60C05, 05C80, 68R10
Version to read: PDF
ISSN 0862-9544 (Printed edition)
Faculty of Mathematics, Physics and Informatics
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
e-Mail: firstname.lastname@example.org Internet: www.iam.fmph.uniba.sk/amuc
© 2013, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE