In this document, we consider a median-based calculus to represent monotone Boolean functions efficiently. We study an equational specification of median forms and extend it from the domain of monotone Boolean functions to the domain of polynomial functions over distributive lattices. This specification is sound and complete. We illustrate its usefulness when simplifying median formulas algebraically. Furthermore, we propose a definition of median normal forms (MNF), that are thought of as minimal median formulas with respect to a structural ordering of expressions. We investigate related complexity issues and show that the problem of deciding whether a formula is in MNF, that is the problem of minimizing the median form of a monotone Boolean function, is in ∑₂ ^P. Moreover, we show that it still holds for arbitrary Boolean functions, not necessarily monotone.

In this document, we consider a median-based calculus for efficiently representing polynomial functions over distributive lattices. We extend an equational specification of median forms from the domain of Boolean functions to the domain of lattice polynomials. We show that it is sound and complete, and we illustrate its usefulness when simplifying median formulas algebraically. Furthermore, we propose a definition of median normal forms (MNF), that are thought of as minimal median formulas with respect to a structural ordering of expressions. We also investigate related complexity issues and show that the problem of deciding whether a formula is in MNF is in Σ^P₂. Moreover, we explore polynomial approximations of solutions to this problem through a sound term rewriting system extracted from the proposed equational specification.