You are here
Homelattice polynomial
Primary tabs
lattice polynomial
A lattice polynomial, informally, is an expression involving a finite number of variables $x,y,z,\ldots$, two symbols $\vee,\wedge$, and sometimes the parentheses $(,)$ in a meaningful manner. Loosely speaking, whenever $p$ and $q$ are lattice polynomials, the only lattice polynomials that can be formed from $p,q,\vee,\wedge$ are $p\vee q$ and $p\wedge q$. We will explain formally what meaningful manner is a little later. Some examples of lattice polynomials are $x\vee(x\vee x)$, $(y\wedge x)\vee x$, and $(x\vee y)\wedge(y\vee z)\wedge(z\vee x)$, while $\vee\wedge x$, $xy\wedge yz$, $z\vee)($ 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 $V=\{x,y,z,\ldots\}$, a set of binary function symbols $F=\{\vee,\wedge\}$. We define pairwise disjoint sets $S_{0},S_{1},\ldots,S_{n},\ldots$ recursively, as follows:

$S_{0}=V$,

$S_{{k+1}}=\{(p\vee q),(p\wedge q)\mid p,q\in S_{k}\}\cup S_{k}$.
Then we set $S=\bigcup_{{i=0}}^{{\infty}}S_{i}$. An element of $S$ is called a lattice polynomial.
Note that in the above definition, $((x\vee y)\vee z)$ is a lattice polynomial while $(x\vee y\vee z)$ is not, for any variables $x,y,z\in V$. To reduce the number of parentheses in a lattice polynomial, we typically identify $(p\vee q)$ with $p\vee q$ and $(p\wedge q)$ with $p\wedge q$. 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 $(p\vee(q\vee r))$ and $((p\vee q)\vee r)$ with $p\vee q\vee r$, and $(p\wedge(q\wedge r))$ and $((p\wedge q)\wedge r)$ with $p\wedge q\wedge r$.
Another thing that can be said about the above construction of is that any given lattice polynomial can be constructed from $S_{0}$ in a finite number of steps. If $p\in S_{n}S_{{n1}}$, $n\geq 1$, then $p$ can be constructed in exactly $n$ steps. The minimum number of variables (in $S_{0}$) that is required to construct $p$ is called the arity of $p$. For example, if $p=((x\vee y)\wedge x)$ then the arity of $p$ is $2$. If an $n$ary lattice polynomial $p$ can be constructed from $x_{1},\ldots,x_{n}$, we often write $p=p(x_{1},\ldots,x_{n})$.
One more important number associated with a lattice polynomial $p$ is its weight, defined recursively as $w(p)=1$ if $p\in S_{0}$, and $w(p\vee q)=w(p\wedge q)=w(p)+w(q)$.
Given any $n$ary lattice polynomial $p$ and any lattice $L$, we can associate $p$ with an $m$ary lattice polynomial function $f:L^{m}\to L$ defined by
$f(a_{1},\ldots,a_{m}):=p(a_{1},\ldots,a_{n}),\mbox{ where }m\geq n\mbox{ and }% a_{i}\in L.$ 
The expression $p(a_{1},\ldots,a_{n})$ is the evaluation of $p$ at $(a_{1},\ldots,a_{n})$. That is, we substitute each $x_{i}$ for $a_{i}$, and we interpret $\vee$ and $\wedge$ in $p$ as the join and meet operations in $L$.
Two lattice polynomials $p,q$ of arities $m,n$, where $m\geq n$, are said to be equivalent if their corresponding $m$ary lattice polynomial functions evaluate to the same values in any lattice. For example, $x\vee y$ and $y\vee x$ are equivalent. Similarly, $x$, $x\vee x$, $x\wedge x$, and $x\vee(y\wedge x)$ are equivalent lattice polynomials.
Remark. Similarly, one can define a Boolean polynomial by enlarging the set $F$ of function symbols to include the unary operator ${}^{{\prime}}$, and $S_{{k+1}}=\{(p\vee q),(p\wedge q),(p^{{\prime}})\mid p,q\in S_{k}\}\cup S_{k}$. Then a Boolean polynomial is just an element of $S=\cup_{{i=0}}^{{\infty}}S_{i}$. The weight of a Boolean polynomial is similarly defined, with the additional $w(p^{{\prime}})=w(p)$.
Mathematics Subject Classification
06B25 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections