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_{{n-1}}$, $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

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)$.