Are boolean operations unique?

106 Views Asked by At

Are the well known operations of logic sum and logic product (defined by their two truth tables) the unique couple of operations (defined on a two elements set) that realize the axioms of: associativity, commutativity, absorption, identity, distributivity, complements?

(The axioms are reported here in section "definition")

1

There are 1 best solutions below

0
On BEST ANSWER

Welcome to Math.SE!

The usual truth value operations (disjunction, conjunction, negation, false, true) constitute the only structure $(\vee, \wedge, \neg, 0, 1)$ that realizes the properties of absorption, complements, commutativity and identity on a two-element set $\{0,1\}$. We show this by proving that the axioms determine the truth tables of $\neg, \vee, \wedge$.

First, observe that by complements $x \vee \neg x = 1$, and by absorption $x \vee 0 = 0$. Thus, if we had $\neg 0 = 0$, we could set $x$ to $0$ and obtain $0 = 0 \vee 0 = 0 \vee \neg 0 = 1$, a contradiction. Similarly, we get $\neg 1 \neq 1$. Thus $\neg$ has to coincide with the usual negation.

By the identity $x \wedge 1 = x$ and commutativity we have $0 \wedge 1 = 1 \wedge 0 = 0$, and $1 \wedge 1 = 1$.

By the identity $x \vee 0 = x$ and commutativity, we have $0 \vee 0 = 0$ and $0 \vee 1 = 1 \vee 0 = 1$.

From here on, we get $0 \wedge 0 = 0 \wedge (0 \vee 0) = 0$ by absorption $x \wedge (x \vee y) = x$, and similarly $1 \vee 1 = 1 \vee (1 \wedge 1) = 1$ by absorption $x \vee (x \wedge y) = x$.

Having determined all values of the functions $\neg, \vee, \wedge$ on $\{0,1\}$, we see that they coincide with the usual truth value operations, as we claimed.