Disjunction

Definition: Disjunction

The disjunction function is the Boolean function $\mathrm{OR}:\{0,1{\}}^n\to \{0,1\}$ defined in the following way:

$$\mathrm{OR}(x_1,\dots ,x_n)\stackrel{\text{def}}{=}\{\begin{array}{l}0\text{if }{x}_1=\cdots =x_n=0\\ 1\text{otherwise}\end{array}$$

NOTATION

It is much more common to write $\mathrm{OR}(x,y)$ in one of the following ways:

$$x\vee yx+y$$

Definition: Maxterm

A logical connective $f:\{0,1{\}}^n\to \{0,1\}$ is a maxterm if it can be expressed as the disjunction of a combination of $n$ negations and identity functions

$$f(x_1,\dots ,x_n)=\mathrm{OR}(x_1^{\prime },\dots ,x_n^{\prime }),$$

where $x_k^{\prime }$ is either equal to $x_k$ or to its negation $\neg x_k$.

Theorem: Commutativity of Conjunction

The disjunction $\mathrm{OR}:\{0,1{\}}^n\to \{0,1\}$ is commutative - if $y_1,\dots ,y_n$ is any permutation of $x_1,\dots ,x_n$, then

$$\mathrm{OR}(y_1,\dots ,y_n)=\mathrm{OR}(x_1,\dots ,x_n)$$

Tip: Binary Disjunction

In particular, we have:

$$x_1\vee x_2=x_2\vee x_1$$

PROOF

TODO

Theorem: Associativity of Conjunction

The disjunction $\mathrm{OR}:\{0,1{\}}^2\to \{0,1\}$ is associative:

$$(x\vee y)\vee z=x\vee (y\vee z)$$

PROOF

TODO

Theorem: General Disjunction from Binary Disjunction

Any disjunction $\mathrm{OR}:\{0,1{\}}^n\to \{0,1\}$ can be obtained via composition of binary disjunctions $\mathrm{OR}:\{0,1{\}}^2\to \{0,1\}$:

$$\mathrm{OR}(x_1,\dots ,x_n)=\mathrm{OR}(x_1,\mathrm{OR}(x_2,\mathrm{OR}(\cdots )))$$

PROOF

TODO

Disjunctive Normal Form

Theorem: Disjunctive Normal Form (DNF)

Every non-contradictory Boolean operator can be uniquely expressed as a disjunction of minterms.

Definition: Disjunctive Normal Form

This expression is known as a disjunctive normal form (DNF).

PROOF

TODO

Algorithm: Finding DNFs

We are given a Boolean operator $f:\{0,1{\}}^n\to \{0,1\}$:

$$f(x_1,\dots ,x_n)$$

1. Identify the on-set $F$ of $f$.

2. For each $(x_1^{\ast },\dots ,x_n^{\ast })\in F$ construct the minterm $\mathrm{AND}(x_1^{\prime },\dots ,x_n^{\prime })$, where

• $x_k^{\prime }=x_k$ if $x_k^{\ast }=1$;

• $x_k^{\prime }=\neg x_k$ if $x_k^{\ast }=0$.

3. The disjunctive normal form of $f$ is the disjunction of all the minterms from step 2.

EXAMPLE

The easiest way is to use the truth table of $f$. Suppose $f(x_1,x_2,x_3)$ has the following truth table:

$x_1$	$x_2$	$x_3$	$f(x_1,x_2,x_3)$
$0$	$0$	$0$	$0$
$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$0$	$1$	$0$
$1$	$1$	$0$	$1$
$1$	$1$	$1$	$0$

The on-set of $f$ is easily determined by looking at the rows which contain $1$ in the column for $f(x_1,x_2,x_3)$. In this example, these rows are $2$, $3$, $4$, and $7$.

On row $2$ we see that $x_1$ and $x_2$ are both $0$, while $x_3$ is $1$. We therefore construct the minterm $\neg x_1\wedge \neg x_2\wedge x_3$.

On row $3$ we see that $x_1$ and $x_3$ are both $0$, while $x_2$ is $1$. We therefore construct the minterm $\neg x_1\wedge x_2\wedge \neg x_3$.

On row $4$ we see that $x_1$ is $0$, while $x_2$ and $x_3$ are both $1$. We therefore construct the minterm $\neg x_1\wedge x_2\wedge x_3$.

On row $7$, we see that $x_1$ and $x_2$ are both $1$, while $x_3$ is $0$. We therefore construct the minterm $x_1\wedge x_2\wedge \neg x_3$.

Finally, we build the disjunction of all minterms:

$$f(x_1,x_2,x_3)=(\neg x_1\wedge \neg x_2\wedge x_3)\vee (\neg x_1\wedge x_2\wedge \neg x_3)\vee (\neg x_1\wedge x_2\wedge x_3)\vee (x_1\wedge x_2\wedge \neg x_3)$$