A lattice polynomial, informally, is an expression involving a finite number of variables , two symbols , and sometimes the parentheses in a meaningful manner. Loosely speaking, whenever and are lattice polynomials, the only lattice polynomials that can be formed from are and . We will explain formally what meaningful manner is a little later. Some examples of lattice polynomials are , , and , while , , are not lattice polynomials.
To formally define what a lattice polynomial is, we resort to model theory. To begin with, we have a countable set of variables , a set of binary function symbols . We define pairwise disjoint sets recursively, as follows:
Then we set . An element of is called a lattice polynomial.
Note that in the above definition, is a lattice polynomial while is not, for any variables . To reduce the number of parentheses in a lattice polynomial, we typically identify with and with . In addition, since the meet and join operations are associative in any lattice, it is a common practice to further reduce the number of parentheses in a lattice polynomial by identifying both and with , and and with .
Another thing that can be said about the above construction of is that any given lattice polynomial can be constructed from in a finite number of steps. If , , then can be constructed in exactly steps. The minimum number of variables (in ) that is required to construct is called the arity of . For example, if then the arity of is . If an -ary lattice polynomial can be constructed from , we often write .
One more important number associated with a lattice polynomial is its weight, defined recursively as if , and .
Given any -ary lattice polynomial and any lattice , we can associate with an -ary lattice polynomial function defined by
The expression is the evaluation of at . That is, we substitute each for , and we interpret and in as the join and meet operations in .
Two lattice polynomials of arities , where , are said to be equivalent if their corresponding -ary lattice polynomial functions evaluate to the same values in any lattice. For example, and are equivalent. Similarly, , , , and are equivalent lattice polynomials.
Remark. Similarly, one can define a Boolean polynomial by enlarging the set of function symbols to include the unary operator , and . Then a Boolean polynomial is just an element of . The weight of a Boolean polynomial is similarly defined, with the additional .
|Date of creation||2013-03-22 16:30:53|
|Last modified on||2013-03-22 16:30:53|
|Last modified by||CWoo (3771)|
|Defines||lattice polynomial function|
|Defines||equivalent lattice polynomials|
|Defines||weight of a lattice polynomial|
|Defines||arity of a lattice polynomial|