Conjunction

Definition: Conjunction

A conjunction function is a Boolean operator $\mathrm{AND}:\{0,1{\}}^n\to \{0,1\}$ defined in the following way:

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

NOTATION

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

$$x\wedge yx\cdot yxy$$

Definition: Minterm

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

$$f(x_1,\dots ,x_n)=\mathrm{AND}(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 conjunction $\mathrm{AND}:\{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{AND}(y_1,\dots ,y_n)=\mathrm{AND}(x_1,\dots ,x_n)$$

Tip: Binary Conjunction

In particular, we have:

$$x_1\wedge x_2=x_2\wedge x_1$$

PROOF

TODO

Theorem: Associativity of Conjunction

The conjunction $\mathrm{AND}:\{0,1{\}}^2\to \{0,1\}$ is associative:

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

PROOF

TODO

Theorem: General Conjunction from Binary Conjunction

Any conjunction $\mathrm{AND}:\{0,1{\}}^n\to \{0,1\}$ can be obtained via composition of binary conjunctions $\mathrm{AND}:\{0,1{\}}^2\to \{0,1\}$:

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

PROOF

TODO

Conjunctive Normal Form

Theorem: Conjunctive Normal Form

Every non-tautological Boolean operator can be uniquely expressed as a conjunction of maxterms.

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 off-set $F$ of $f$.

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

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

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

3. The conjunctive normal form of $f$ is the conjunction of all the maxterms 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 off-set of $f$ is easily determined by looking at the rows which contain $0$ in the column for $f(x_1,x_2,x_3)$. In this example, these rows are $1$, $5$, $6$, and $8$.

On row $1$ we see that $x_1$, $x_2$ and $x_3$ are all $0$. We therefore construct the maxterm $x_1\vee x_2\vee x_3$.

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

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

On row $6$ we see that $x_1$, $x_2$ and $x_3$ are all $1$. We therefore construct the maxterm $\neg x_1\vee \neg x_2\neg \vee x_3$.

Finally, we build the conjunction of all maxterms:

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