Can every order-preserving function $\mathbb{B}^n \rightarrow \mathbb{B}$ be represented using only {AND, OR, TRUE, FALSE}?

70 Views Asked by At

Write $\mathbb{B} = \{0,1\}$ for the Boolean domain. Then those functions $\mathbb{B}^n \rightarrow \mathbb{B}$ representable by an expression in the language of bounded distributive lattices are necessarily order-preserving.

Does the converse hold?

Just to be completely explicit, I want to know: can every order-preserving function $\mathbb{B}^n \rightarrow \mathbb{B}$ be represented by an expression involving only the operators {AND, OR, TRUE, FALSE}?

1

There are 1 best solutions below

6
On BEST ANSWER

Yes. For every collection of variables that when set to 1 cause the function to return 1, form a clause that is the AND of all these variables, and then take the OR of all these clauses.

Clearly, every input that should return 1 does return 1. Every input that should return 0 by the order-preserving property necessarily does not contain among its 1-valued variables any subset that cause the function to return 1, so it does not satisfy any of the clauses of the OR I gave.