Branches History Index

Proof

(related to Proposition: Associativity of Conjunction)

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

$[[x]]_I$	$[[y]]_I$	$[[z]]_I$	$[[x \wedge y]]_I$	$[[y \wedge z]]_I$	$[[(x \wedge y)\wedge z]]_I$	$[[x\wedge (y \wedge z)]]_I$
$1$	$1$	$1$	$1$	$1$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$0$	$0$
$1$	$0$	$1$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$1$	$0$	$0$	$0$
$0$	$1$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$0$	$0$	$0$	$0$	$0$
$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 conjunction operation is associative, i.e. $(x\wedge y) \wedge z =x\wedge (y \wedge 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