lattice polynomial
A lattice polynomial, informally, is an expression involving a finite number of variables $x,y,z,\mathrm{\dots}$, 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,\mathrm{\dots}\}$, a set of binary function symbols $F=\{\vee ,\wedge \}$. We define pairwise disjoint sets ${S}_{0},{S}_{1},\mathrm{\dots},{S}_{n},\mathrm{\dots}$ 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}^{\mathrm{\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\ge 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},\mathrm{\dots},{x}_{n}$, we often write $p=p({x}_{1},\mathrm{\dots},{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},\mathrm{\dots},{a}_{m}):=p({a}_{1},\mathrm{\dots},{a}_{n}),\text{where}m\ge n\text{and}{a}_{i}\in L.$$ 
The expression $p({a}_{1},\mathrm{\dots},{a}_{n})$ is the evaluation of $p$ at $({a}_{1},\mathrm{\dots},{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\ge 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}^{\mathrm{\infty}}{S}_{i}$. The weight of a Boolean polynomial is similarly defined, with the additional $w({p}^{\prime})=w(p)$.
Title  lattice polynomial 

Canonical name  LatticePolynomial 
Date of creation  20130322 16:30:53 
Last modified on  20130322 16:30:53 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  9 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 06B25 
Defines  lattice polynomial function 
Defines  equivalent lattice polynomials 
Defines  weight of a lattice polynomial 
Defines  arity of a lattice polynomial 
Defines  Boolean polynomial 