Boolean Operators

Definition: Boolean Operator

A Boolean operator is a Boolean function of the following form for some $n\in \mathbb{N}$:

$$f:\{0,1{\}}^n\to \{0,1\}$$

Definition: Off-Set

The off-set of $f$ is the set of all inputs for which $f$ outputs $0$:

$$\overline{F}\stackrel{\text{def}}{=}\{x\in \{0,1{\}}^n\mid f(x)=0\}$$

Definition: On-Set

The on-set of $f$ is the set of all inputs for which $f$ outputs $1$:

$$F\stackrel{\text{def}}{=}\{x\in \{0,1{\}}^n\mid f(x)=1\}$$

Definition: Shannon Cofactors

The positive Shannon cofactor of $f$ with respect to the $i$-th variable is the restriction of $f$ to $\{(x_1,\dots ,x_{i-1},1,x_{i+1},\dots ,x_n)\mid x_k\in \{0,1\}\}$.

NOTATION

$$f_{x_i}$$

The negative Shannon cofactor of $f$ with respect to the $i$-th variable is the restriction of $f$ to $\{(x_1,\dots ,x_{i-1},0,x_{i+1},\dots ,x_n)\mid x_k\in \{0,1\}\}$.

NOTATION

$$f_{\overline{x_i}}$$

Definition: Contradiction

A logical connective $f:\{0,1{\}}^n\to \{0,1\}$ is a contradiction or contradictory when $f(x)=0$ for all $x\in \{0,1{\}}^n$.

Definition: Tautology

A logical connective $f:\{0,1{\}}^n\to \{0,1\}$ is a tautology or tautological when $f(x)=1$ for all $x\in \{0,1{\}}^n$.

Theorem: Cofactor Substitution

The Shannon cofactors of a logical connective $f:\{0,1{\}}^n\to \{0,1\}$ obey the following rules:

$$\begin{array}{rl}{x}_i\wedge f& =x_i\wedge f_{x_i}\\ \overline{x_i}\wedge f& =\overline{x_i}\wedge f_{\overline{x_i}}\\ x_i\vee f& =x_i\vee f_{\overline{x_i}}\\ \overline{x_i}\vee f& =\overline{x_i}\vee f_{x_i}\end{array}$$

PROOF

We need to prove four things:

• (1) $x_i\wedge f=x_i\wedge f_{x_i}$.
• (2) $\overline{x_i}\wedge f=\overline{x_i}\wedge f_{\overline{x_i}}$.
• (3) $x_i\vee f=x_i\vee f_{\overline{x_i}}$.
• (4) $\overline{x_i}\vee f=\overline{x_i}\vee f_{x_i}$.

Proof of (1):

If $x_i=0$, then the left-hand side is $x_i\wedge f=0\wedge f=0$. Similarly, the right-hand side is $x_i\wedge f_{x_i}=0\wedge f_{x_i}=0$. The left-hand side and right-hand side are therefore equal when $x_i=0$.

If $x_i=1$, then the left-hand side is $x_i\wedge f=1\wedge f=f$. Similarly, the right-hand side is $x_i\wedge f_{x_i}=1\wedge f_{x_i}=f_{x_i}$. However, in this case, $f$ and $f_{x_i}$ are the same by definition. The left-hand side and right-hand side are therefore equal when $x_i=1$.

We have thus shown that the law holds for all possible values of $x_i$, i.e. it holds in general.

Proof of (2):

If $x_i=0$, then the left-hand side is $\overline{x_i}\wedge f=1\wedge f=f$. Similarly, the right-hand side is $\overline{x_i}\wedge f_{\overline{x_i}}=\overline{0}\wedge f_{\overline{x_i}}=1\wedge f_{\overline{x_i}}=f_{\overline{x_i}}$. However, in this case, $f$ and $f_{\overline{x_i}}$ are the same by definition. The left-hand side and right-hand side are therefore equal when $x_i=1$. The left-hand side and right-hand side are therefore equal when $x_i=0$.

If $x_i=1$, then the left-hand side is $\overline{x_i}\wedge f=\overline{1}\wedge f=0\wedge f=0$. Similarly, the right-hand side is $\overline{x_i}\wedge f_{\overline{x_i}}=\overline{1}\wedge f_{\overline{x_i}}=0\wedge f_{\overline{x_i}}=0$. The left-hand side and right-hand side are therefore equal when $x_i=1$.

We have thus shown that the law holds for all possible values of $x_i$, i.e. it holds in general.

Proof of (3):

Analogous.

Proof of (4):

Analogous.

Boole's Expansion Theorem

If $f_{x_i}$ and $f_{\overline{x_i}}$ are the Shannon cofactors of a logical connective $f:\{0,1{\}}^n\to \{0,1\}$ with respect to the $i$-th variable, then:

$$f=(x_i\wedge f_{x_i})\vee (\overline{x_i}\wedge f_{\overline{x_i}})=(x_i\vee f_{\overline{x_i}})\wedge (\overline{x_i}\vee f_{x_i})$$

PROOF

We need to prove two things:

• (1) $f=(x_i\wedge f_{x_i})\vee (\overline{x_i}\wedge f_{\overline{x_i}})$.
• (2) $f=(x_i\vee f_{\overline{x_i}})\wedge (\overline{x_i}\vee f_{x_i})$.

Proof of (1): The following proof was generated by AI and has not been human-verified. As such, it may contain mistakes.

If $x_i=1$:

• The LHS becomes $f(x_1,\dots ,1,\dots ,x_n)$, which by definition is the cofactor $f_{x_i}$.
• The RHS becomes $(1\wedge f_{x_i})\vee (\overline{1}\wedge f_{\overline{x_i}})$.
• Since $\overline{1}=0$, this simplifies to $(1\wedge f_{x_i})\vee (0\wedge f_{\overline{x_i}})$.
• Using the identities $1\wedge A=A$ and $0\wedge B=0$, we get $f_{x_i}\vee 0$.
• Using the identity $A\vee 0=A$, the RHS simplifies to $f_{x_i}$.
• Thus, for $x_i=1$, LHS = RHS.

If $x_i=0$:

• The LHS becomes $f(x_1,\dots ,0,\dots ,x_n)$, which by definition is the cofactor $f_{\overline{x_i}}$.
• The RHS becomes $(0\wedge f_{x_i})\vee (\overline{0}\wedge f_{\overline{x_i}})$.
• Since $\overline{0}=1$, this simplifies to $(0\wedge f_{x_i})\vee (1\wedge f_{\overline{x_i}})$.
• Using the identities $0\wedge A=0$ and $1\wedge B=B$, we get $0\vee f_{\overline{x_i}}$.
• Using the identity $0\vee B=B$, the RHS simplifies to $f_{\overline{x_i}}$.
• Thus, for $x_i=0$, LHS = RHS.

Since the equality holds for both possible values of $x_i$, the identity is proven true for all inputs.

Proof of (2): The following proof was generated by AI and has not been human-verified. As such, it may contain mistakes..

If $x_i=1$:

• The LHS is again $f(x_1,\dots ,1,\dots ,x_n)=f_{x_i}$.
• The RHS becomes $(1\vee f_{\overline{x_i}})\wedge (\overline{1}\vee f_{x_i})$.
• Since $\overline{1}=0$, this simplifies to $(1\vee f_{\overline{x_i}})\wedge (0\vee f_{x_i})$.
• Using the identities $1\vee A=1$ and $0\vee B=B$, we get $1\wedge f_{x_i}$.
• Using the identity $1\wedge A=A$, the RHS simplifies to $f_{x_i}$.
• Thus, for $x_i=1$, LHS = RHS.

If $x_i=0$:

• The LHS is again $f(x_1,\dots ,0,\dots ,x_n)=f_{\overline{x_i}}$.
• The RHS becomes $(0\vee f_{\overline{x_i}})\wedge (\overline{0}\vee f_{x_i})$.
• Since $\overline{0}=1$, this simplifies to $(0\vee f_{\overline{x_i}})\wedge (1\vee f_{x_i})$.
• Using the identities $0\vee A=A$ and $1\vee B=1$, we get $f_{\overline{x_i}}\wedge 1$.
• Using the identity $A\wedge 1=A$, the RHS simplifies to $f_{\overline{x_i}}$.
• Thus, for $x_i=0$, LHS = RHS.

Logic Laws

Notation: Precedence

Typically, the precedence of logical connectives decreases in the following order: negation, conjunction, disjunction.

EXAMPLE

$$\neg x\wedge y=(\neg x)\wedge y\neg x\vee y=(\neg x)\vee y$$

Theorem: Associativity Laws

Conjunction and disjunction are assosiative:

$$\begin{array}{rl}(A\wedge B)\wedge C& =A\wedge (B\wedge C)\\ (A\vee B)\vee C& =A\vee (B\vee C)\end{array}$$

PROOF

We need to prove two things:

• (1) $(A\wedge B)\wedge C=A\wedge (B\wedge C)$.
• (2) $(A\vee B)\vee C=A\vee (B\vee C)$.

Proof of (1):

$$(A\wedge B)\wedge C=1⟺(A\wedge B)=1\text{ and }C=1⟺A=1\text{ and }B=1\text{ and }C=1$$ $$A\wedge (B\wedge C)=1⟺A=1\text{ and }(B\wedge C)=1⟺A=1\text{ and }B=1\text{ and }C=1$$

Proof of (2):

$$(A\vee B)\vee C=0⟺(A\vee B)=0\text{ and }C=0⟺A=0\text{ and }B=0\text{ and }C=0$$ $$A\vee (B\vee C)⟺A=0\text{ and }(B\vee C)=0⟺A=0\text{ and }B=0\text{ and }C=0$$

Theorem: Distributivity Laws

Conjunction and disjunction are distributive over one another:

$$\begin{array}{rl}x\wedge (y\vee z)& =(x\wedge y)\vee (x\wedge z)\\ x\vee (y\wedge z)& =(x\vee y)\wedge (x\vee z)\end{array}$$

PROOF

We need to prove two things:

• (1) $x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)$.
• (2) $x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)$.

Proof of (1):

If $x=1$, then the left-hand side is $x\wedge (y\vee z)=1\wedge (y\vee z)=y\vee z$. Furthermore, the right-hand side is $(x\wedge y)\vee (x\wedge z)=(1\wedge y)\vee (1\wedge z)=y\vee z$. The left-hand side and right-hand side are therefore equal when $x=1$.

If $x=0$, then the left-hand side is $x\wedge (y\vee z)=0\wedge (y\vee z)=0$. Furthermore, the right-hand side is $(x\wedge y)\vee (x\wedge z)=(0\wedge y)\vee (0\wedge z)=0\vee 0=0$. The left-hand side and right-hand side are therefore equal when $x=0$.

We have thus shown that the law holds for all possible values of $x$, i.e. it holds in general.

Proof of (2):

If $x=1$, then the left-hand is $x\vee (y\wedge z)=1\vee (y\wedge z)=1$. Furthermore, the right-hand side is $(x\vee y)\wedge (x\vee z)=(1\vee y)\wedge (1\vee z)=1\vee 1=1$. The left-hand side and right-hand side are therefore equal when $x=1$.

If $x=0$, then the left-hand is $x\vee (y\wedge z)=y\wedge z$. Furthermore, the right-hand side is $(x\vee y)\wedge (x\vee z)=(0\vee y)\wedge (0\vee z)=y\wedge z$. The left-hand side and right-hand side are therefore equal when $x=0$.

We have thus shown that the law holds for all possible values of $x$, i.e. it holds in general.

Theorem: De Morgan's Laws

Negation, conjunction and disjunction are related by the following laws:

$$\begin{array}{rl}\overline{x\wedge y}& =\overline{x}\vee \overline{y}\\ \overline{x\vee y}& =\overline{x}\wedge \overline{y}\end{array}$$

PROOF

We need to prove two things:

• (1) $\overline{x\wedge y}=\overline{x}\vee \overline{y}$.
• (2) $\overline{x\vee y}=\overline{x}\wedge \overline{y}$.

Proof of (1):

If $x=1$, then the left-hand side is $\overline{x\wedge y}=\overline{1\wedge y}=\overline{y}$. Furthermore, the right-hand side is $\overline{x}\vee \overline{y}=\overline{1}\vee \overline{y}=0\vee \overline{y}=\overline{y}$. The left-hand side and right-hand side are therefore equal when $x=1$.

If $x=0$, then the left-hand side is $\overline{x\wedge y}=\overline{0\wedge y}=\overline{0}=1$. Furthermore, the right-hand side is $\overline{x}\vee \overline{y}=\overline{0}\vee \overline{y}=1\vee \overline{y}=1$. The left-hand side and right-hand side are therefore equal when $x=0$.

We have thus shown that the law holds for all possible values of $x$, i.e. it holds in general.

Proof of (2):

If $x=1$, then the left-hand side is $\overline{x\vee y}=\overline{1\vee y}=\overline{1}=0$. Furthermore, the right-hand side is $\overline{x}\wedge \overline{y}=\overline{1}\wedge \overline{y}=0\wedge \overline{y}=0$. The left-hand side and right-hand side are therefore equal when $x=1$.

If $x=0$, then the left-hand side is $\overline{x\vee y}=\overline{0\vee y}=\overline{y}$. Furthermore, the right-hand side is $\overline{x}\wedge \overline{y}=\overline{0}\wedge \overline{y}=1\wedge \overline{y}=\overline{y}$. The left-hand side and right-hand side are therefore equal when $x=0$.

We have thus shown that the law holds for all possible values of $x$, i.e. it holds in general.

Theorem: Absorption Laws

Conjunction and disjunction have the following properties:

$$\begin{array}{rl}A\vee (A\wedge B)& =A\\ A\wedge (A\vee B)& =A\end{array}$$

PROOF

We need to prove two things:

• (1) $A\vee (A\wedge B)=A$.
• (2) $A\wedge (A\vee B)=A$.

Proof of (1):

If $A=1$, then the left-hand side is $A\vee (A\wedge B)=1\vee (1\wedge B)=1$. Furthermore, the right-hand side is just $1$. The left-hand side and right-hand side are therefore equal when $A=1$.

If $A=0$, then the left-hand side is $A\vee (A\wedge B)=0\vee (0\wedge B)=0\vee 0=0$. Furthermore, the right-hand side is just $0$. The left-hand side and right-hand side are therefore equal when $A=0$.

We have thus shown that the law holds for all possible values of $A$, i.e. it holds in general.

Proof of (2):

If $A=1$, then the left-hand side is $A\wedge (A\vee B)=1\wedge (1\vee B)=1\wedge 1=1$. Furthermore, the right-hand side is just $1$. The left-hand side and right-hand side are therefore equal when $A=1$.

If $A=0$, then the left-hand side is $A\wedge (A\vee B)=0\wedge (0\vee B)=0\wedge B=0$. Furthermore, the right-hand side is just $0$. The left-hand side and right-hand side are therefore equal when $A=0$.

We have thus shown that the law holds for all possible values of $A$, i.e. it holds in general.

Theorem: Resolution Laws

Negation, conjunction and disjunction have the following properties:

$$\begin{array}{rl}(X\wedge A)\vee (\overline{X}\wedge B)& =(X\wedge A)\vee (\overline{X}\wedge B)\vee (A\wedge B)\\ (X\vee A)\wedge (\overline{X}\vee B)& =(X\vee A)\wedge (\overline{X}\vee B)\wedge (A\vee B)\end{array}$$

PROOF

We need to prove two things:

• (1) $(X\wedge A)\vee (\overline{X}\wedge B)=(X\wedge A)\vee (\overline{X}\wedge B)\vee (A\wedge B)$.
• (2) $(X\vee A)\wedge (\overline{X}\vee B)=(X\vee A)\wedge (\overline{X}\vee B)\wedge (A\vee B)$.

Proof of (1):

If $X=1$, then the left-hand side is $(X\wedge A)\vee (\overline{X}\wedge B)=(1\wedge A)\vee (\overline{1}\wedge B)=A\vee (0\wedge B)=A\vee 0=A$. Furthermore, the right-hand side is $(X\wedge A)\vee (\overline{X}\wedge B)\vee (A\wedge B)=(1\wedge A)\vee (\overline{1}\wedge B)\vee (A\wedge B)=A\vee (0\wedge B)\vee (A\wedge B)=A\vee 0\vee (A\wedge B)=A\vee (A\wedge B)$. By the absorption law, $A\vee (A\wedge B)=A$. The left-hand side and right-hand side are therefore equal when $X=1$.

If $X=0$, then the left-hand side is $(X\wedge A)\vee (\overline{X}\wedge B)=(0\wedge A)\vee (\overline{0}\wedge B)=0\vee (1\wedge B)=0\vee B=B$. Furthermore, the right-hand side is $(X\wedge A)\vee (\overline{X}\wedge B)\vee (A\wedge B)=(0\wedge A)\vee (\overline{0}\wedge B)\vee (A\wedge B)=0\vee (1\wedge B)\vee (A\wedge B)=0\vee B\vee (A\wedge B)=B\vee (A\wedge B)$. By the absorption law, $B\vee (A\wedge B)=B$. The left-hand side and right-hand side are therefore equal when $X=0$.

We have thus shown that the law holds for all possible values of $A$, i.e. it holds in general.

Proof of (2):

If $X=1$, then the left-hand side is $(X\vee A)\wedge (\overline{X}\vee B)=(1\vee A)\wedge (\overline{1}\vee B)=1\wedge (0\vee B)=1\wedge B=B$. Furthermore, the right-hand side is $(X\vee A)\wedge (\overline{X}\vee B)\wedge (A\vee B)=(1\vee A)\wedge (\overline{1}\vee B)\wedge (A\vee B)=1\wedge (0\vee B)\wedge (A\vee B)=1\wedge B\wedge (A\vee B)=B\wedge (A\vee B)$. By the absorption law, $B\wedge (A\vee B)=B$. The left-hand side and right-hand side are therefore equal when $1=0$.

If $X=0$, then the left-hand side is $(X\vee A)\wedge (\overline{X}\vee B)=(0\vee A)\wedge (\overline{0}\vee B)=A\wedge (1\vee B)=A\wedge 1=A$. Furthermore, the right-hand side is $(X\vee A)\wedge (\overline{X}\vee B)\wedge (A\vee B)=(0\vee A)\wedge (\overline{0}\vee B)\wedge (A\vee B)=A\wedge (1\vee B)\wedge (A\vee B)=A\wedge 1\wedge (A\vee B)=A\wedge (A\vee B)$. By the absorption law, $A\wedge (A\vee B)=A$. The left-hand side and right-hand side are therefore equal when $1=0$.

We have thus shown that the law holds for all possible values of $A$, i.e. it holds in general.

Theorem: Boolean Expansion of Negation

If $f_{x_i}$ and $f_{\overline{x_i}}$ are the Shannon cofactors of a logical connective $f:\{0,1{\}}^n\to \{0,1\}$ with respect to the $i$-th variable, then the negation of $f$ can be express in the following ways:

$$\overline{f}=(\overline{x_i}\wedge \overline{f_{\overline{x_i}}})\vee (x_i\wedge \overline{f_{x_i}})=(\overline{x_i}\vee \overline{f_{x_i}})\wedge (x_i\vee \overline{f_{\overline{x_i}}})$$

PROOF

We need to prove two things:

• (1) $\overline{f}=(\overline{x_i}\wedge \overline{f_{\overline{x_i}}})\vee (x_i\wedge \overline{f_{x_i}})$.
• (2) $\overline{f}=(\overline{x_i}\vee \overline{f_{x_i}})\wedge (x_i\vee \overline{f_{\overline{x_i}}})$.

Proof of (1): The following proof was generated by AI and has not been human-verified. As such, it may contain mistakes.

This identity is derived by applying the Shannon expansion theorem directly to the function $\overline{f}$. The Shannon expansion of any function $g$ with respect to a variable $x_i$ is:

$$g=(\overline{x_i}\wedge g_{\overline{x_i}})\vee (x_i\wedge g_{x_i})$$

Let’s set $g=\overline{f}$. This gives us:

$$\overline{f}=(\overline{x_i}\wedge (\overline{f}{)}_{\overline{x_i}})\vee (x_i\wedge (\overline{f}{)}_{x_i})$$

Now, we evaluate the cofactors of $\overline{f}$. The cofactor $(\overline{f}{)}_{\overline{x_i}}$ is the function $\overline{f}$ evaluated with $x_i=0$. This is equivalent to first evaluating $f$ with $x_i=0$ (which is $f_{\overline{x_i}}$) and then negating the result. Therefore:

$$(\overline{f}{)}_{\overline{x_i}}=\overline{f_{\overline{x_i}}}$$

Similarly, for the cofactor with respect to $x_i=1$:

$$(\overline{f}{)}_{x_i}=\overline{f_{x_i}}$$

Substituting these back into the expansion for $\overline{f}$, we get the desired identity:

$$\overline{f}=(\overline{x_i}\wedge \overline{f_{\overline{x_i}}})\vee (x_i\wedge \overline{f_{x_i}})$$

Proof of (2): The following proof was generated by AI and has not been human-verified. As such, it may contain mistakes.

This identity is derived by starting with the standard Shannon expansion of the original function $f$ and applying De Morgan’s laws.

The Shannon expansion of $f$ is:

$$f=(\overline{x_i}\wedge f_{\overline{x_i}})\vee (x_i\wedge f_{x_i})$$

Now, we negate both sides of the equation:

$$\overline{f}=\overline{(\overline{x_i}\wedge f_{\overline{x_i}})\vee (x_i\wedge f_{x_i})}$$

Using De Morgan’s law ($\overline{A\vee B}=\overline{A}\wedge \overline{B}$), we get:

$$\overline{f}=\overline{(\overline{x_i}\wedge f_{\overline{x_i}})}\wedge \overline{(x_i\wedge f_{x_i})}$$

Next, we apply De Morgan’s law again to each term ($\overline{A\wedge B}=\overline{A}\vee \overline{B}$):

$$\overline{f}=(\overline{\overline{x_i}}\vee \overline{f_{\overline{x_i}}})\wedge (\overline{x_i}\vee \overline{f_{x_i}})$$

Finally, using the law of double negation ($\overline{\overline{A}}=A$) on the term $\overline{\overline{x_i}}$, we arrive at the identity:

$$\overline{f}=(x_i\vee \overline{f_{\overline{x_i}}})\wedge (\overline{x_i}\vee \overline{f_{x_i}})$$

By the commutative property of conjunction, this is equivalent to:

$$\overline{f}=(\overline{x_i}\vee \overline{f_{x_i}})\wedge (x_i\vee \overline{f_{\overline{x_i}}})$$