Boolean Logic

Value

True (T), False (F)

Operators

$\neg x(\text{or }\bar{x})$ , negation, not $x\wedge y$, conjunction, and $x\vee y$, disjunction, or $x\oplus y$, exclusive or, xor $x\to y$, material implication

• $(x\to y)=1⟺(x=0)\vee (y=1)$

Laws

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

De Morgan's Law

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

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

Normal forms

Any complex proposition can be represented by propositions that only include AND, OR as well as NOTs. Given a Boolean Function $f:\{0,1{\}}^n\to \{0,1\};(x_1,\cdots ,x_n)\to y$ For each line in its truth table

$$y=f(x_1,\cdots ,x_n),\text{where }y={\beta }_i;x_k={\alpha }_{ik},k\in [n]$$

Then we have

$$f=\underset{i:{\beta }_i=1}{\bigvee }\left(\underset{k}{\bigwedge }g(x_k)\right),\text{where }g(x_k)=\{\begin{array}{ll}{x}_k,& {\alpha }_{ik}=1\\ \overline{x_k},& {\alpha }_{ik}=0\end{array}$$

Disjunction Normal Form, DNF

Every $n$-variable proposition $F(x_1,x_2,\cdots ,x_n)$ can be represented by a disjunction normal form

$$F(x_1,x_2,\cdots ,x_n)=Q_1\vee Q_2\vee \cdots \vee Q_m$$

Conjunction Normal Form, CNF

Similarly, we have

$$f=\underset{i:{\beta }_i=0}{\bigwedge }\left(\underset{k}{\bigvee }g(x_k)\right),\text{where }g(x_k)=\{\begin{array}{ll}{x}_k,& {\alpha }_{ik}=0\\ \overline{x_k},& {\alpha }_{ik}=1\end{array}$$

e.g.

$$(x\oplus y)\to z=(x\vee \bar{y}\vee z)\wedge (\bar{x}\vee y\vee z)$$

This is a natural result of De Morgan's Law

Representation with Least Operators

One could use and only use

1. AND, NOT
2. OR, NOT
3. IMPLICATION to represent all Boolean expressions.