On connected Boolean functions (Q1961460)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On connected Boolean functions |
scientific article |
Statements
On connected Boolean functions (English)
0 references
14 February 2000
0 references
Various classes of Boolean functions are introduced: connected, strongly connected, geodetic, convex, strongly convex and concordant. They are characterized by some properties of the subgraph of the Boolean hypercube induced by the (false) true points of a function. The relationships between these properties and the DNF representation of a Boolean function as well as the inclusions between these classes are studied.
0 references
computational complexity
0 references
Boolean function
0 references
monotone
0 references
unate
0 references
geodetic
0 references
subgraph of the Boolean hypercube
0 references
DNF representation
0 references