COMPUTER ARCHITECTURE

A Boolean Algebra is an algebra(set, operations, elements) consisting of a set B with >=2 elements, together with three operations- the **AND** operation(Boolean Product), the **OR** operation(Boolean Sum), and the **NOT** operation(Complement) - defined on the set, such that for any element a, b, c…. of set B, a*b, a+b and a' are in B.

**For Example:**

- Consider the four-element Boolean algebra
**B4 = ( {0, x, y, 1}; *, +, '; 0, 1)**. The**AND**,**OR**and**NOT**operations are described by the following tables: - Consider the two-element Boolean algebra
**B2 = ({0,1}; *, +, '; 0, 1)**. The three operations***(AND)**,**+(OR)**and**'(NOT)**are defined as follows:

Here are some key terms of the Boolean Algebra with a brief description about them:

Boolean algebra is a switching algebra that deals with binary variables and logic operations. The variables are designated by letters such as A, B, x, and y. The three basic logic operations are AND, OR and NOT. A Boolean function can be expressed algebraically with binary variables, the logic operation symbols, parentheses and equal sign. For a given combination of values of the variables, the Boolean function can be either 1 or 0. Consider for example, the Boolean Function:

F = x + y'z

The Function F is equal to 1 if x is 1 or if both y' and z are equal to 1; F is equal to 0 otherwise.

The relationship between a function and its binary variables can be represented in a truth table. To represent a function in a truth table we need a list of the **2 ^{n}** combinations of the n binary variables.

A Boolean function can be transformed from an algebraic expression into a logic diagram composed of AND, OR and NOT gates.

The purpose of Boolean algebra is to facilitate the analysis and design of digital circuits. It provides a convenient tool to:

- Express in algebraic form a truth table relationship between binary variables.
- Express in algebraic for the input-output relationship of logic diagrams.
- Find simpler circuits for the same function.

A Boolean function specified by a truth table can be expressed algebraically in many different ways. Two ways of forming Boolean expressions are **Canonical** and **Non-Canonical** forms.

It expresses all binary variables in every product(AND) or sum(OR) term of the Boolean function. To determine the canonical sum-of-products form for a Boolean function **F(A, B, C) = A'B + C' + ABC**, which is in **non-canonical form**, the following steps are used:

F = A'B + C' + ABC = A'B(C + C') + (A + A')(B + B')C' + ABC

where **x + x' = 1** is a basic identity of Boolean algebra

= A'BC + A'BC' + ABC' + AB'C' + A'BC' + A'B'C' + ABC = A'BC + A'BC' + ABC' + AB'C' + A'B'C' + ABC

By manipulating a Boolean expression according to Boolean algebra rules, one may obtain a simpler expression that will require fewer gates.

The below table lists the most basic identities of Boolean algebra. All the identities in the table can be proven by means of truth tables.