(related to Lemma: Unique Valuation of Minterms and Maxterms)

Let $x_1,\ldots,x_n$ be Boolean variables, $I$ be an interpretation and $[[]]_I$ be the corresponding valuation function in the semantics of propositional logic.

- Let $m=(\neg)x_1\wedge\ldots\wedge(\neg)x_n$ be a minterm.
- We first show by construction the existence of an $n$-tuple of truth values $([[x_1]]_I,\ldots,[[x_n]]_I)\in\mathbb B^n$ such that $[[m]]_I=1:$
- If the literal $(\neg)x_i$ denotes $x_i$, valuate $x_i$ as true: $[[x_i]]_I=1.$
- If the literal $(\neg)x_i$ denotes $\neg x_i$, valuate $x_i$ as false: $[[x_i]]_I=0.$
- Then, from the definition of negation it follows that $[[\neg x_i]]_I=1.$
- Since all literals in $m$ are connected using a conjunction "$\wedge$" and since all are true, it follows that $m$ is valuated true: $[[m]]_I=1,$ by construction.

- We now show that this $n$-tuple is unique by contradiction.
- Assume $(a_1,\ldots,a_n)$ and $(b_1,\ldots,b_n)$ are two different $n$-touples of valutions of $x_1,\ldots,x_n$ for which $[[m]]_I=1.$
- Then there is at least one literal $(\neg)x_i$ valued true: $[[(\neg)x_i]]_I=1$ for which $[[x_i]]_I=a_i$ and $[[x_i]]_I=b_i$ and $a_i\neq b_i$.
- But a proposition cannot be both, true and false.
- Since this is a contradiction, the $n$-tuple of valutions of $x_1,\ldots,x_n$ for which $[[m]]_I=1$ is unique.

- Let $M=(\neg)x_1\vee\ldots\vee(\neg)x_n$ be a maxterm.
- We first show by construction the existence of an $n$-tuple of truth values $([[x_1]]_I,\ldots,[[x_n]]_I)\in\mathbb B^n$ such that $[[M]]_I=0:$
- If the literal $(\neg)x_i$ denotes $x_i$, valuate $x_i$ as false: $[[x_i]]_I=0.$
- If the literal $(\neg)x_i$ denotes $\neg x_i$, valuate $x_i$ as true: $[[x_i]]_I=1.$
- Then, from the definition of negation it follows that $[[\neg x_i]]_I=0.$
- Since all literals in $M$ are connected using a disjunction "$\vee$" and since all are false, it follows that $M$ is valuated false: $[[M]]_I=0,$ by construction.

- We now show that this $n$-tuple is unique by contradiction.
- Assume $(a_1,\ldots,a_n)$ and $(b_1,\ldots,b_n)$ are two different $n$-touples of valutions of $x_1,\ldots,x_n$ for which $[[M]]_I=0.$
- Then there is at least one literal $(\neg)x_i$ valued false: $[[(\neg)x_i]]_I=0$ for which $[[x_i]]_I=a_i$ and $[[x_i]]_I=b_i$ and $a_i\neq b_i$.
- But a proposition cannot be both, true and false.
- Since this is a contradiction, the $n$-tuple of valutions of $x_1,\ldots,x_n$ for which $[[M]]_I=0$ is unique.∎

**Mendelson Elliott**: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982**Hoffmann, Dirk**: "Theoretische Informatik, 3. Auflage", Hanser, 2015