Boolean Expressions#

TODO

Definition: Literal

A literal in a boolean expression is either a variable or its negation.

Definition: Product Term

A product term is a conjunction of literals.

Example

\[ xy \qquad \overline{x}yz \qquad \overline{x}\overline{y} \]

Definition: Clause

A clause is a disjunction of literals.

Example

\[ x + y \qquad \overline{x}+y+z \qquad \overline{x}+\overline{y} \]

Definition: Minterm

Given \(n\) variables, a minterm is a conjunction in which each variable or its negation appears exactly once.

Example

If we have the variables \(x, y, z\), then \(x\overline{y}z\) and \(\overline{x}\overline{y}\overline{z}\) are minterms, but \(xy\) is not.

Notation

If we have \(n\) variables \(x_0, \dotsc, x_{n-1}\), we can give each minterm a unique label \(m_k\), where \(k\) is a non-negative integer which tells us what the minterm looks like. This is done by interpreting the minterm as a sequence of bits \(b_0\cdots b_{n-1}\), where \(b_i = 1\) if the minterm contains \(x_i\) and \(b_i = 0\) if it contains \(\neg x_i\).

Example

The minterm \(m_3\) is \(x_1x_0\), since \(3_{10} = 11_{2}\).

The minterm \(x_3 \overline{x_2} x_1 x_0\) has the label \(m_{11}\), since \(1011_{2} = 11_{10}\).

Definition: Maxterm

Given \(n\) variables, a maxterm is a disjunction in which each variable or its negation appears exactly once.

Example

If we have the variables \(x, y, z\), then \(x+\overline{y}+z\) and \(\overline{x}+\overline{y}+\overline{z}\) are maxterms, but \(x+y\) is not.

Notation

If we have \(n\) variables \(x_0, \dotsc, x_{n-1}\), we can give each maxterm a unique label \(M_k\), where \(k\) is a non-negative integer which tells us what the maxterm looks like. This is done by interpreting the maxterm as a sequence of bits \(b_0\cdots b_{n-1}\), where \(b_i = 1\) if the maxterm contains \(\neg x_i\) and \(b_i = 0\) if it contains \(x_i\).

Example

The maxterm \(M_3\) is \(\overline{x_1} + \overline{x_0}\), since \(3_{10} = 11_{2}\).

The maxterm \(\overline{x_3} + x_2 + \overline{x_1} + \overline{x_0}\) has the label \(M_{13}\), since \(1011_{2} = 11_{10}\).

Definition: Conjunctive Normal Form

A conjunctive normal form or product of sums is a conjunction of one or more clauses.

Example

\[ (x + y)(y + z)(z + w) \qquad (x + y + z)z \]

Definition: Disjunctive Normal Form

A conjunctive normal form or sum of products is a disjunction of one or more product terms.

Example

\[ xy + yz + zw \qquad xyz + z \]