> **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?

\$$\mathbf{Bool}\$$ is isomorphic to [Boolean algebra](https://en.wikipedia.org/wiki/Boolean_algebra). We can relabel \$$\mathbf{Bool}\$$ as \$$\{0,1\}\$$ where \$$\text{True} = 1\$$ and \$$\text{False} = 0\$$. The meet of \$$\mathbf{Bool}\$$ is the same as multiplication \$$\cdot\$$ such that \$$0 \cdot 0 = 0\$$, \$$1 \cdot 0 = 0\$$, \$$0 \cdot 1 = 0\$$, and \$$1 \cdot 1 = 1\$$. Logically, this means \$$xy\$$ is asking if both \$$x\$$ and \$$y\$$ are true (i.e., the operation AND). The join of \$$\mathbf{Bool}\$$ becomes the same as addition \$$0 + 0 = 0\$$, \$$1 + 0 = 1\$$, \$$0 + 1 = 1\$$, and \$$1 + 1 = 1\$$. Logically, this means \$$x + y\$$ is asking whether either or both \$$x\$$ and \$$y\$$ are true (i.e., the operation OR).

Let \$$A_{yx} = \Phi(x,y)\$$, \$$B_{zy} = \Psi(y,z) \$$, and \$$C_{zx} = (\Psi\Phi)(x,z) \$$ where \$$A, B\$$, and \$$C\$$ are matrices whose entries are either 0 or 1. Thus the formula

$(\Psi\Phi)(x,z) = \bigvee_{y \in Y} \Phi(x,y) \wedge \Psi(y,z)$

is isomorphic to matrix multiplication in Boolean algebra:

$C_{zx} = \sum_y B_{zy} A_{yx}$

Logically, this formula states that \$$C_{zx}\$$ is true if for at least one \$$y\$$, \$$\Phi(x,y)\$$ and \$$\Psi(y,z)\$$ are true.