# Show that any monotone boolean function can be realize by the following connectives.

Let the following be the set of connectives involving {$\top,\ \bot,\ \land,\ \lor$}.

Set $F \leq T$

Show that any monotone Boolean function $f$ can be realize by a wff (well-form formula) using only the above set of connectives.

My attempt is to mimic the prove for the theorem:

"Let $G$ be an $n$-th place Boolean function, we can find a wff $\alpha$ that realizes $G$"

Attempt:

Case I: ran($f$) = {$F$}, then clearly $f$ can be realize by the constant $\bot$.

Case II: ran($f$) = {$F, T$}.

Mimicking the prove for the theorem, we can look at the $k$ points at which $f$ has the value $T$ and put in a matrix/grid

<$X_{11},...,X_{1n}$ >

....

<$X_{k1},....,X_{kn}$>

For some $k\in \mathbb{N}$

Define $\beta_{ij} = \begin{cases} A_{j}, & \text{if}\ X_{ij}=T \\ A_j\ \lor\ \top, & \text{if}\ X_{ij} = F \end{cases}$

Define $\gamma_i = \beta_{i1} \land...\land \ \beta_{in}$

Define $\alpha = \gamma_1 \lor......\lor\ \gamma_k$, $\alpha$ realizes $f$.

Although the proof is similary, I can help but feel that I did something wrong here, mainly becuse I didnt make use of the fact that $f$ is mono-tone.

If I did make a mistake kindly point it out and perhaps point me in the right direction.

Let $\mathbf{x}_1,\ldots,\mathbf{x}_k$ be such that $f(\mathbf{x}_i) = T$ and $\mathbf{y}_1,\ldots,\mathbf{y}_l$ the remaining vectors such that $f(\mathbf{y}_j) = F$. We will say that $\mathbf{x}_i = \langle x_{i1},\ldots,x_{in} \rangle$ and similarly for the $\mathbf{y}_j$'s.
To show to your formula realizes $f$, we need to show that it works on all the $\mathbf{x}_i$'s as well as the $\mathbf{y}_j$'s. It's pretty clear that $\gamma_i(\mathbf{x}_i) = T$ and so $\alpha(\mathbf{x}_i) = T$ for any $i$, as is desired.
To prove correctness w.r.t the $\mathbf{y}_j$'s on the other hand does require monotonicity. Fix $\mathbf{y}_j$ and let $\mathbf{x}_i$ be arbitrary. By monotonicity, $\mathbf{x}_i \not\leq \mathbf{y}_j$ and so there is a $p$ such that $x_{ip} = T$ and $y_{jp} = F$. $A_{p}$ must then appear as a conjunct in $\gamma_i$. Thus, $\gamma_i(\mathbf{y}_j) = F$, and since $i$ was arbitrary, this holds for every disjunct in $\alpha$. Thus, $\alpha(\mathbf{y}_j) = F$.
• I have one question though, from your argument, does that mean every $x$ is comparable bit-wise with $y$ ? – some1fromhell Aug 17 '17 at 4:29
• @some1fromhell not sure I understand your question. Are you asking what $\mathbf{x} \leq \mathbf{x'}$ means for $\mathbf{x}, \mathbf{x'}$ vectors of length $n$? In that case yes we are comparing them bitwise. See product order. – user181407 Aug 17 '17 at 5:21
• Because the $x_i$ we pick is arbitrary, then you say by monotonicity $x_i \nleq y_j$. So are we assuming any arbitrary $x_i$ is comparable to this fixed $y_j$ (bit-wise) ? My concern is what if we pick an incomparable $x_i$ with $y_j$ – some1fromhell Aug 17 '17 at 5:24
• If $\mathbf{x}_i \leq \mathbf{y}_j$ then by monotonicity of $f$, $T = f(\mathbf{x}_i) \leq f(\mathbf{y}_j) = F$, a contradiction. Thus, $\mathbf{x}_i \not\leq \mathbf{y}_j$. Recall that $x_i$ is an arbitrary vector such that $f(\mathbf{x}_i) = T$. – user181407 Aug 17 '17 at 5:31