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
Version to read:
PDF
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 |