Boolean Algebra Help

Boolean Algebra provides a basic logic for operations on binary numbers 0, 1. Since computers are based on binary system, this branch of Mathematics is found to be useful for the internal working of various computers.

The application of Boolean algebra to electronic devices such as computers, lies in the restriction of the variable to two possible condition 'On and Off' or 'True or False' or numerically '1 or 0'. The electric circuits carry out the Boolean logic.

In practice, electronic engineers use the language of logic as follows.

They use the symbol '1' to refer the values of the signals produced by an electronic switch as 'On' or 'True'.

They use the symbol '0' to refer the values of the signals produced by an electronic switch as 'Off' or 'False'. The symbols 0 and 1 are called bits.

Logical OR operation
Logical AND operation
Logical NOT operation

We associate two logical operations 'AND' and 'OR' operations with switching circuits in 'series' and 'parallel' respectively.

Let us refer to a circuit consisting of two switches p and q connected in series with a lamp and battery as shown in figure.

The lamp will glow, only if switch p and switch q are closed. If we replace the word 'closed' by T and 'open' by F, the switch will glow only if p = T and q = T. In binary language, we say the switch will glow if p = 1 and q = 1.

Table 1, Table 2 and Table 3 describes all possible states of the switches for the series connection.

Switching In Series

Table 1

Table 2 - Truth Table for P and Q

The 'AND' operation can be defined on the set of bits {0, 1} as follows

1 . 1 = 1, 1 . 0 = 0, 0.1 = 0, 0.0 = 0

Table 3 -

It is clear that 'AND' operation stipulated that with two input variables, the output is true only when both the inputs are true.

Let us refer to a circuit consisting of two switches p and q connected in parallel with a lamp and battery as shown in figure.

In this case, the lamp will glow if and only if at least one of the switches is closed. In binary language we say the switch will glow if at least one of the values of p and q is 1.

Table 4, Table 5 and Table 6 describe all possibles states of the switches for the 'OR' operation.

The 'OR' operation can be defined as the set of bits {0, 1} as follows:

1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0

Switches in parallel

Truth Table for p or q

In terms of bits

The tables such as 3 and 6 are called input/output table with all possible values of inputs in bits and the corresponding possible output in bits.

The OR operation stipulates that with two binary input variables, the output is true if either or both the inputs are true.

The logical NOT operation is right associative and although it would produce the same result using either left or right associative property because it is a unary operator having only a single operand.

This operation has one input and one output. Table 7 represents truth table for NOT operation.

Note that the 'NOT' operation is a unary operator, whereas 'AND' and 'OR' operators are binary operators.

We have already discussed what a Boolean function is. Here is a formal definition for Boolean expression and Boolean function.

Let (B, +, ., ', 0, 1) be a Boolean algebra where B is a non-empty set, '+' and '.' are binary operations, ' is a unary operation with two special elements 0 (Zero element) and 1 (unit element). Let x₁, x₂, x₃ ….x_n are in B. Then Boolean expression in x₁, x₂, x₃ …. x_n are defined recursively as follows:

I)

0, 1, x₁, x₂, x₃ …. x_n are Boolean expressions.

II)

If x and y are Boolean expressions, then

(a) x'

(b) x + y (x v y)

(c) x . y (x y)

are also Boolean expressions.

Function which can be obtained from Boolean expressions are called Boolean functions.

Note: In the above definition, the symbols 0 and 1 do not necessarily represent the numbers 0 and 1.
We can construct an input/output table for a given Boolean function. We can also construct a Boolean function from an input/output table.

Below are some examples

Example 1: Construct an input/output table for the Boolean function.

f(x₁, x₂,x₃) = (x₁.x₂') + x₃

The input/output table is given as follows:

Input/output Table for (x1 . x2') + x3 - Table 8

Example 2: Write the Boolean expression and the Boolean function given by the input/output table as given below:

Construct the required function as follows:

Step 1: Identify all rows of the table where the output is 1. Note that 1^st, 2^nd, 3^rd and the last row has output 1.

Step 2: Form the combination (x₁, x₂, x₃) for the rows identified in step 1.

Put x_i if x_i = 1

x_i if x_i = 0

For the

1^st row, the expression is x₁.x₂.x₃

2^nd row, the expression is x₁.x₂.x₃'

3^rd row, the expression is x₁, x₂'.x₃

Last row, the expression is x₁'.x₂'.x₃'

Step 3: Applying OR to all the combinations obtained in step 3, we have the expression

x₁ x₂ x₃ + x₁ x₂ x₃' + x₁ x₂' x₃ + x₁' x₂' x₃'

Step 4: The Boolean function can be written as:

f(x₁, x₂, x₃) = x₁ x₂ x₃ + x₁ x₂ x₃' + x₁ x₂' x₃ + x₁' x₂' x₃'

Since the following is represented by a Boolean expression, it is a Boolean function.

• A Boolean algebra is a set B with two distinct elements, along with the binary operations '+' and '.' and a unary operation (') which satisfy closure property, commutative property, existence of unit element, distributive property for both the binary operations. Moreover, for all xB, there exists x' such that x + x' = 1 and x . x' = 0.

If B = {0, 1} in the above definition, B is a Boolean algebra.

• A simple proposition (statement) is a sentence which in a given content can said to be either true or false.

Truth value of proposition is taken as either true or false.

• Compound proposition is a combination of two or more simple propositions connected by the connectivity 'AND', 'OR', 'if then' and 'if and only if'.

• Conditional proposition pq is false only when p is true and q is false. In other cases, it is true.

If pq, then the contrapositive of this proposition is -q -p.

• The biconditional pq is true only when both p and q are true or both p and q are false.

• A compound proposition which is always true for all combination of truth values of its components is called a tautology.

• A compound proposition which is always false for all combination of truth values of its components is called a contradiction.

• A Boolean expression consists of variables x, y, z …etc where these variables take the values 0 or 1. They may be connected by ' . ', '+' or ' operation.