Branches History Index

Proof

(related to Proposition: Associativity of Disjunction)

Let $x,y,z$ be propositions and let $I$ be an interpretation with the valuation function $[[]]_I$.
Based on the truth table of disjunction, we can construct a truth table for $(x\vee y) \vee z$ and $x\vee (y \vee z)$ independently for all possible semantics of $x,y,z$:

$[[x]]_I$	$[[y]]_I$	$[[z]]_I$	$[[x \vee y]]_I$	$[[y \vee z]]_I$	$[[(x \vee y)\vee z]]_I$	$[[x\vee (y \vee z)]]_I$
$1$	$1$	$1$	$1$	$1$	$1$	$1$
$0$	$1$	$1$	$1$	$1$	$1$	$1$
$1$	$0$	$1$	$1$	$1$	$1$	$1$
$0$	$0$	$1$	$0$	$1$	$1$	$1$
$1$	$1$	$0$	$1$	$1$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$1$	$0$	$1$	$1$
$0$	$0$	$0$	$0$	$0$	$0$	$0$

Since the values in both columns to the right of the table are equal, it follows that the disjunction operation is associative, i.e. $(x\vee y) \vee z =x\vee (y \vee z)$.
∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

Mendelson Elliott: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982