◀ ▲ ▶Branches / Logic / Proof

Proof

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

Proof for Minterms

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

Proof for Maxterms

• 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.
    ∎

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

Github:

References

Bibliography

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