Paper Info
Title
On the orthogonalization of arbitrary Boolean formulae
Abstract
The Orthogonal conjunctive normal form of a Boolean function is a con- junctive normal form in which any two clauses contain at least a pair of complementary literals. Orthogonal disjunctive normal form is defined similarly. Orthogonalization is the process of transforming the normal form of a Boolean function to orthogonal normal form. The problem is of great relevance in several applications, e.g. in the reliability theory. Moreover, such problem is strongly connected with the well-known propositional satisfiability problem. Therefore, important complexity issues are involved. A general procedure for transforming an arbitrary CNF or DNF to an orthogonal one is proposed. Such procedure is tested on randomly generated Boolean formulae.
Year
DOI
Venue
2005
10.1155/JAMDS.2005.61
JAMDS
Keywords
Field
DocType
boolean functions,np-completeness,reliability.,normal form,conjunctive normal form,boolean function,disjunctive normal form
Boolean function,Maximum satisfiability problem,Discrete mathematics,Canonical normal form,Combinatorics,Negation normal form,Parity function,Disjunctive normal form,Conjunctive normal form,Boolean expression,Mathematics
Journal
Volume
Issue
Citations 
9
2
1
PageRank 
References 
Authors
0.39
7
1
Name
Order
Citations
PageRank
Renato Bruni112715.79