On the orthogonalization of arbitrary Boolean formulae
type: Item
instance of: scholarly article
title: On the orthogonalization of arbitrary Boolean formulae
zbMATH Open document ID: 1146.68377
DOI: 10.1155/JAMDS.2005.61
author: Renato Bruni
published in: Journal of Applied Mathematics and Decision Sciences
publication date: 2008-07-01T00:00:00Z
full work available at URL: https://eudml.org/doc/129276
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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T15
Mathematics Subject Classification ID: 03B35
zbMATH DE Number: 5295958
zbMATH Keywords: randomly generated Boolean formulae
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5295958