Max and Min Operations are Distributive over Each Other

From ProofWiki
Jump to navigation Jump to search

Theorem

The Max and Min operations are distributive over each other:

$\max \set {x, \min \set {y, z} } = \min \set {\max \set {x, y}, \max \set {x, z} }$
$\max \set {\min \set {x, y}, z} = \min \set {\max \set {x, z}, \max \set {y, z} }$
$\min \set {x, \max \set {y, z} } = \max \set {\min \set {x, y}, \min \set {x, z} }$
$\min \set {\max \set {x, y}, z} = \max \set {\min \set {x, z}, \min \set {y, z} }$


Proof

To simplify our notation, let $\max \set {x, y}$ be (temporarily) denoted $x \overline \wedge y$, and let $\min \set {x, y}$ be (temporarily) denoted $x \underline \vee y$.

Note that, once we have proved:

$x \overline \wedge \paren {y \underline \vee z} = \paren {x \overline \wedge y} \underline \vee \paren {x \overline \wedge z}$
$x \underline \vee \paren {y \overline \wedge z} = \paren {x \underline \vee y} \overline \wedge \paren {x \underline \vee z}$

then the other results follow immediately by the fact that Min and Max are commutative.


There are the following cases to consider:

$(1): \quad x \le y \le z$
$(2): \quad x \le z \le y$
$(3): \quad y \le x \le z$
$(4): \quad y \le z \le x$
$(5): \quad z \le x \le y$
$(6): \quad z \le y \le x$


$(1): \quad $ Let $x \le y \le z$.

Then:

\(\displaystyle x \overline \wedge \paren {y \underline \vee z}\) \(=\) \(\displaystyle x \overline \wedge y = y\)
\(\displaystyle \paren {x \overline \wedge y} \underline \vee \paren {x \overline \wedge z}\) \(=\) \(\displaystyle y \underline \vee z = y\)
\(\displaystyle \) \(\) \(\displaystyle \)
\(\displaystyle x \underline \vee \paren {y \overline \wedge z}\) \(=\) \(\displaystyle x \underline \vee z = x\)
\(\displaystyle \paren {x \underline \vee y} \overline \wedge \paren {x \underline \vee z}\) \(=\) \(\displaystyle x \overline \wedge x = x\)


$(2): \quad $ Let $x \le z \le y$.

Then:

\(\displaystyle x \overline \wedge \paren {y \underline \vee z}\) \(=\) \(\displaystyle x \overline \wedge z = z\)
\(\displaystyle \paren {x \overline \wedge y} \underline \vee \paren {x \overline \wedge z}\) \(=\) \(\displaystyle y \underline \vee z = z\)
\(\displaystyle \) \(\) \(\displaystyle \)
\(\displaystyle x \underline \vee \paren {y \overline \wedge z}\) \(=\) \(\displaystyle x \underline \vee y = x\)
\(\displaystyle \paren {x \underline \vee y} \overline \wedge \paren {x \underline \vee z}\) \(=\) \(\displaystyle x \overline \wedge x = x\)


$(3): \quad $ Let $y \le x \le z$.

Then:

\(\displaystyle x \overline \wedge \paren {y \underline \vee z}\) \(=\) \(\displaystyle x \overline \wedge y = x\)
\(\displaystyle \paren {x \overline \wedge y} \underline \vee \paren {x \overline \wedge z}\) \(=\) \(\displaystyle x \underline \vee z = x\)
\(\displaystyle \) \(\) \(\displaystyle \)
\(\displaystyle x \underline \vee \paren {y \overline \wedge z}\) \(=\) \(\displaystyle x \underline \vee z = x\)
\(\displaystyle \paren {x \underline \vee y} \overline \wedge \paren {x \underline \vee z}\) \(=\) \(\displaystyle y \overline \wedge x = x\)


$(4): \quad $ Let $y \le z \le x$.

Then:

\(\displaystyle x \overline \wedge \paren {y \underline \vee z}\) \(=\) \(\displaystyle x \overline \wedge y = x\)
\(\displaystyle \paren {x \overline \wedge y} \underline \vee \paren {x \overline \wedge z}\) \(=\) \(\displaystyle x \underline \vee x = x\)
\(\displaystyle \) \(\) \(\displaystyle \)
\(\displaystyle x \underline \vee \paren {y \overline \wedge z}\) \(=\) \(\displaystyle x \underline \vee z = z\)
\(\displaystyle \paren {x \underline \vee y} \overline \wedge \paren {x \underline \vee z}\) \(=\) \(\displaystyle y \overline \wedge z = z\)


$(5): \quad $ Let $z \le x \le y$.

Then:

\(\displaystyle x \overline \wedge \paren {y \underline \vee z}\) \(=\) \(\displaystyle x \overline \wedge z = x\)
\(\displaystyle \paren {x \overline \wedge y} \underline \vee \paren {x \overline \wedge z}\) \(=\) \(\displaystyle y \underline \vee x = x\)
\(\displaystyle \) \(\) \(\displaystyle \)
\(\displaystyle x \underline \vee \paren {y \overline \wedge z}\) \(=\) \(\displaystyle x \underline \vee y = x\)
\(\displaystyle \paren {x \underline \vee y} \overline \wedge \paren {x \underline \vee z}\) \(=\) \(\displaystyle x \overline \wedge z = x\)


$(6): \quad $ Let $z \le y \le x$.

Then:

\(\displaystyle x \overline \wedge \paren {y \underline \vee z}\) \(=\) \(\displaystyle x \overline \wedge z = x\)
\(\displaystyle \paren {x \overline \wedge y} \underline \vee \paren {x \overline \wedge z}\) \(=\) \(\displaystyle x \underline \vee x = x\)
\(\displaystyle \) \(\) \(\displaystyle \)
\(\displaystyle x \underline \vee \paren {y \overline \wedge z}\) \(=\) \(\displaystyle x \underline \vee y = y\)
\(\displaystyle \paren {x \underline \vee y} \overline \wedge \paren {x \underline \vee z}\) \(=\) \(\displaystyle y \overline \wedge z = y\)


Thus in all cases it can be seen that the result holds.

$\blacksquare$