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

> \[ (\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.