On the orthogonalization of arbitrary Boolean formulae

DOI10.1155/JAMDS.2005.61MaRDI QIDQ930767zbMATH OpenFDO

Authors Renato Bruni

Publication date 1 July 2008

Published in Journal of Applied Mathematics and Decision Sciences (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/129276

zbMATH Keywords

randomly generated Boolean formulae

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Analysis of algorithms and problem complexity (68Q25)

Review text

Summary: The orthogonal conjunctive normal form of a Boolean function is a conjunctive 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, for example, 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.

Recommendations

• Boolean Normal Forms, Shellability, and Reliability Computations
• scientific article; zbMATH DE number 3877101
• Minimization of Boolean functions in the basis OR-NOT (AND-NOT)
• scientific article; zbMATH DE number 5852793
• System of transformations of certain representations of Boolean functions

Cited in

(4)

• Disjointed sum of products by a novel technique of orthogonalizing ORing
• A new calculation for Boolean derivative using Cheng product
• Orthogonality and Boolean Algebras for Deduction Modulo
• Boolean Normal Forms, Shellability, and Reliability Computations

This page was built for publication: On the orthogonalization of arbitrary Boolean formulae

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q930767)