1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

It seems to me that your construction should work.

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$.

$\endgroup$
  • $\begingroup$ I have one question though, from your argument, does that mean every $x$ is comparable bit-wise with $y$ ? $\endgroup$ – some1fromhell Aug 17 '17 at 4:29
  • $\begingroup$ @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. $\endgroup$ – user181407 Aug 17 '17 at 5:21
  • $\begingroup$ 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$ $\endgroup$ – some1fromhell Aug 17 '17 at 5:24
  • $\begingroup$ 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$. $\endgroup$ – user181407 Aug 17 '17 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.