re **Puzzle 181**:

> Suppose that \$$\Phi : X \nrightarrow Y, \Psi : Y \nrightarrow Z\$$ are feasibility relations between preorders. Prove that
>
> $(\Psi\Phi)(x,z) = \bigvee_{y \in Y} \Phi(x,y) \wedge \Psi(y,z)$
>
> where \$$\wedge\$$ is the meet in the poset \$$\textbf{Bool}\$$, and \$$\bigvee\$$ is the join.
>
> How is this formula related to matrix multiplication?

If \$$(\Psi\Phi)(x,z) = \text{true}\$$, then by definition we must have \$$\Phi(x,y) \wedge \Psi(y,z) = \text{true}\$$ for at least one \$$y\in Y\$$, so the join of all \$$\Phi(x,y) \wedge \Psi(y,z)\$$ must be \$$\text{true}\$$.

If \$$(\Psi\Phi)(x,z) = \text{false}\$$, then we must have \$$\Phi(x,y) \wedge \Psi(y,z) = \text{false}\$$ for all \$$y\in Y\$$, so the join of all \$$\Phi(x,y) \wedge \Psi(y,z)\$$ will be \$$\text{false}\$$.

We can think of this join-of-meets as a sum-of-products, and specifically as the product of the "row vector" \$$(\Psi(y_0,z)\ \Psi(y_1,z)\ \Psi(y_2,z)...)\$$ with the "column vector" \$$(\Phi(x,y_0)\ \Phi(x,y_1)\ \Phi(x,y_2)...)^\textbf{T}\$$. This suggests the following construction:

Given any feasibility relation \$$\Phi : X \nrightarrow Y\$$ we construct a matrix \$$\text{M}(\Phi)\$$ with \$$|X|\$$ columns, \$$|Y|\$$ rows, and the boolean \$$\Phi(x, y)\$$ at position \$$(y, x)\$$.

Then what we've just proved amounts to \$$\text{M}(\Psi\Phi) = \text{M}(\Psi)\text{M}(\Phi)\$$.