TAOCP 7.1.1 Exercise 97
For $n=2$ with $w_1=w_2=1$, the function in (81) has the form
Exercise 97. [10] What median/majority functions arise in (81) when $n = 2$, $w_1 = w_2 = 1$, and $t = -1, 0, 1, 2, 3,$ or $4$?
Verified: yes
Solve time: 1m05s
For $n=2$ with $w_1=w_2=1$, the function in (81) has the form
\begin{cases} 1 & \text{if } x_1+x_2 \ge t,\ 0 & \text{otherwise.} \end{cases}$$ Since $x_1,x_2 \in {0,1}$, the possible values of $x_1+x_2$ are $0,1,2$. For $t=-1$, $0$, or $1$, the inequality $x_1+x_2 \ge t$ holds for all $(x_1,x_2)$ except that for $t=1$ it excludes $(0,0)$. Thus $t=-1$ and $t=0$ both give the constant function $1$, i.e., $\top$, while $t=1$ gives $x_1 \vee x_2$. For $t=2$, the condition holds only when $x_1=x_2=1$, so the function is $x_1 \wedge x_2$. For $t=3$ or $t=4$, no pair satisfies $x_1+x_2 \ge t$, so the function is the constant $0$, i.e., $\bot$. Thus the median/majority functions obtained are $\top$ for $t=-1,0$, disjunction $x_1 \vee x_2$ for $t=1$, conjunction $x_1 \wedge x_2$ for $t=2$, and $\bot$ for $t=3,4$. This completes the classification. ∎