Boolean functions and Logic gates#

Boolean operation#

Binary logic consists of binary variables and a set of logical operations.

The variables are designated by letters of the alphabet, such as $A$, $B$, $C$, $x$, $y$, $z$, etc, with each variable having two and only two distinct possible values: $1$ and $0$.

Truth table#

A truth table of a Boolean function lists the output values for every possible input value combination in tabular form.

There are three basic logical operations: AND, OR, and NOT.

NOT#

Truth Table :

AND#

Truth Table :

OR#

Truth Table :

Logic gates#

Basic logic gate#

• Logic gates are basic logic elements of a circuit
• They implement Boolean logic (use voltage to represent logic value)
• NOT gate, AND gate, OR gate implement the three basic logic operations

Other logic gate#

Logic function#

We have three different ways to describe a logic function:

1. English language description (specification).
2. Logic equation (Boolean equation).
3. Truth table.

For simplicity, we will use logic equation to describe.

Notation#

• AND - $\And$ or $\land$ or •
• OR - $|$ or $\lor$ or +
• NOT - $\neg X$ or $X'$ or ~$X$ or $!X$ or $\bar X$

Boolean Algebra#

Boolean algebra has applications in set theory, mathematical logic, digital system design.

Algebra over :

• two elements: $0$ and $1$
• two binary operations: $+$ and •
• a complement operation: $'$

Terminology#

• Variable : a symbol that may take on the value 0 or 1.
• Literal : the use of a variable or its complement in an expression.
• Term : an expression formed by literals and operation at one level.

For example:

$$F = xy+xy'z+x'yz$$

The above boolean algebra has :

• 3 variables $(x, y, z)$
• 8 literals $(x, y, x, y', z, x', y, z)$
• 4 terms $(and(x, y), and(x, y', z), and(x', y, z), or(xy, xy'z, x'yz))$

Axiom#

• Axiom: a set of mathematical statement asserted to be true

• If we start with the following axioms (virtually stating the definitions of AND, OR, NOT with a set of math statements), then everything else in Boolean algebra can be derived from them. Info:

• Identity: $1 ‧ x = x$ $0 + x = x$

• Annihilation: $1 + x = 1$ $0 ‧ x = 0$

• Negation: $0’ = 1$ $1’ = 0$

Theorem#

• Theorems are logical consequences of the axioms

• Some useful theorems for logic simplification: Info:

• Commutative

$xy=yx$ $x+y=y+x$

• Associative

$x(yz)=(xy)z$ $x+(y+z)=(x+y)+z$

• Distributive $x(y+z)=xy+xz$ $x+(yz)=(x+y)(x+z)$

• Idempotence $xx=x$ $x+x=x$

• Complementation $x\bar x = 0$ $x+\bar x = 1$

• Absorption $x(x+y)=x$ $x+(xy)=x$

• Combining $(xy) + (x\bar y) = x$ $(x + y)(x + \bar y) = x$

• DeMorgan’s $\overline{(xy)} = \bar x + \bar y$ $\overline{(x+y)} = \bar x \bar y$

• Involution $\overline{(\bar x)} = x$

• Consensus

= (xy) + (\bar xz)$$ $$(x + y)(\bar x + z)(y + z) = (x + y)(\bar x + z)$$ ### Duality - The dual is obtained by **interchanging OR and AND operations, interchanging 0 and 1** - Duality holds in the axioms, and all of the Boolean algebra derived from them, and the dual of any true statement is also a true statement #### Example 01

(X + Y) + Z = X + (Y + Z)

$$Using Duality$$

(X Y) Z = X (Y Z)

#### Example 02

X + 1 = 1

$$Using Duality$$

X\bullet 0 = 0

### Proof of boolean properties 1. By using axioms or known theorems/Boolean properties. 2. By checking their validity for all possible combinations of variables. ■ Simply with truth table ■ Mathematicians call this proof technique **perfect induction** ### Example: Simplify Logic Expression using Boolean Properties

\begin{align} f(a,b,c) &= (a ∧ c) ∨ (a ∧ b ∧ c) ∨ (¬ a ∧ b ∧ c) ∨ (a ∧ b ∧ ¬ c) \ &= (a ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (¬ a ∧ b ∧ c) ∨ (a ∧ b ∧ ¬ c) \ &= (a ∧ c) ∨ (¬ a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ b ∧ ¬ c) ∨ (a ∧ b ∧ c)\ &= (a ∧ c) ∨ ((b ∧ c)∧(¬ a ∨ a)) ∨ ((a ∧ b)∧(¬ c ∨ c)) \ &= (a ∧ c) ∨ ((b ∧ c)∧ 1) ∨ ((a ∧ b)∧1)\ &= (a ∧ c) ∨ (b ∧ c) ∨ (a ∧ b) \end{align}

### NAND Gate and NOR Gate

(xy)‘=x’+y’

$$ NAND gate can be transformed into NOT gate and OR gate.$$

(x+y)‘=x’y’

 Similarly, NOR gate can be transformed into NOT gate and AND gate. ## Arbitrary fuction presentation A Boolean function can be expressed by : - a truth table - **sum of minterms** that produces output 1 (**Canonical form**) - **product of maxterms** that produces output 0 (**Canonical form**)  ### Minterms (standard products) **Info:** An AND term consisting of all literals in their normal form or in their complement form. ### Maxterms (standard sums) **Info:** An OR term consisting of all literals in their normal form or in their complement form. ### Example

f_1 = x’y’z + xy’z’ + xyz

$$According to the definition of minterms, we have :$$

f_1 = m_1+m_4+m_7 = \Sigma m(1, 4, 7)

Consider the compliment of $f_1$, we have :

f_1’ = m_0 +m_2 +m_3 +m_5 +m_6

And we know $f_1 = (f_1')'$, thus by DeMorgan's Law :

\begin{align} f_1 =& m_0’m_2’m_3’m_5’m_6’\ =& M_0M_2M_3M_5M_6 = \Pi M(0, 2, 3, 5, 6) \end{align}

Finally, we have the method to converse between two Canonical Forms : **Success:** Interchange the symbols $\Sigma$ and $\Pi$ and list those numbers missing from the original form.

f_1 = \Sigma m(1, 4, 7) = \Pi M(0, 2, 3, 5, 6)

### Standard Form Two kinds of Standard forms : - Sum of products (**SOP**) form e.g. $f = xy + x’y + y’z$ - Product of sums (**POS**) form e.g. $g = x(y'+z)(x'+y+z'+w)$ - SOP/POS form of a function is **not unique**. - Sum of Minterm/Product of Maxterm form of a function is **unique**. (**Canonical form**) ### Transforming to Canonical Form Any logic expression can be transformed to Canonical form by factoring about each input variable using the identity : **Info:**

f(x_1, …, x_i, …, x_n) = (x_i\land f(x_1, .., 1, .., x_n)\lor (\overline x_i\land f(x_1, …, 0, …, x_n)))

For example, $f(a,b,c) = (a ∧ c) ∨ (b ∧ c) ∨ (a ∧ b)$, say we want to substitude $a$ :

\begin{align} f(a, b, c) =& (a ∧ f(1, b, c)) ∨ (a’ ∧ f(0, b, c))\ =& (a ∧ (c ∨ (b ∧ c) ∨ b)) ∨ (a’ ∧ (b ∧ c))\ =& (a ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ b) ∨ (a’ ∧ b ∧ c)\ \end{align}

$$Thus, we have :$$

(b ∧ c) = (a ∧ b ∧ c) ∨ (a’ ∧ b ∧ c)

$$Then we can substitude the function :$$

\begin{align} f(a, b, c) =& (a ∧ c) ∨ (b ∧ c) ∨ (a ∧ b)\ =&(b ∧ a ∧ c) ∨ (b’ ∧ a ∧ c) ∨ (a ∧ b ∧ c) ∨ (a’ ∧ b ∧ c) ∨ (c ∧ a ∧ b) ∨ (c’ ∧ a ∧ b)\ =& m_7+m_5+m_7+m_3+m_7+m_6\ =& \Sigma m(3, 5, 6, 7) \end{align}

## Implementation with Logic Gates Cosider the following logic function :

F = X\bar Y + \bar XZ

$$We can draw a circuit (called **schematic**) like this :  If a logic function becomes very compound, how can we simplify it ? For example, actually, the following logic function is the same as the above one.$$

F = \bar X\bar Y Z+\bar X Y Z+X\bar Y

As we learned above, we just need to use the strategy above to shorten our equation, then we can make our schematic smaller. ###### tags: `Logic Design EECS1010`