Galois Theory for Minors of Finite Functions

Document Type



Mathematics (HMC)

Publication Date



The motivating example for our work is given by sets of Boolean functions closed under taking minors. A Boolean function f is a minor of a Boolean function g if f is obtained from g by substituting an argument of f, the complement of an argument of f, or a Boolean constant for each argument of g. The theory of minors has been used to study threshold functions (also known as linearly separable functions) and their generalization to functions of bounded order (where the degree of the separating polynomial is bounded, but may be greater than one). We construct a Galois theory for sets of Boolean functions closed under taking minors, as well as for a number of generalizations of this situation. In this Galois theory we take as the dual objects certain pairs of relations that we call “constraints”, and we explicitly determine the closure conditions on sets of constraints.

Rights Information

© 2002 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.