p. 191 - 200 Properties of the interval graph of a Boolean function 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 PDF Compressed Postscript Version to read ISSN 0862-9544 (Printed edition) Faculty of Mathematics, Physics and Informatics Comenius University 842 48 Bratislava, Slovak Republic Telephone: + 421-2-60295111 Fax: + 421-2-65425882 e-Mail: amuc@fmph.uniba.sk Internet: www.iam.fmph.uniba.sk/amuc © 2013, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE |