MathDB

Put

\mathbb{A}=\{ \mathrm{yes}, \mathrm{no} \}

. A function

f\colon \mathbb{A}^n\rightarrow \mathbb{A}

is called a decision function if (a) the value of the function changes if we change all of its arguments; and (b) the values does not change if we replace any of the arguments by the function value. A function

d\colon \mathbb{A}^n \rightarrow \mathbb{A}

is called a dictatoric function, if there is an index

i

such that the value of the function equals its

i

th argument. The democratic function is the function

m\colon \mathbb{A}^3 \rightarrow \mathbb{A}

that outputs the majority of its arguments. Prove that any decision function is a composition of dictatoric and democratic functions.

Problem Statement