Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests - Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests -
× DOWNLOAD NOW

Representation of Boolean Functions

We can represent a boolean function using an algebraic expression that consists of constants such as 1 and 0, binary variables, and also logic operation symbols. Here is an example of a Boolean function: f(x, y, z) = x y – z. We implement these functions with the logic gates.

In this article, we will take a look at the Representation of Boolean Functions according to the GATE Syllabus for CSE (Computer Science Engineering). Read ahead to learn more.

Table of Contents

Representation of Boolean Functions

We describe a Boolean Function by an algebraic expression that contains the logic operation symbols +, ., ‘, binary variables, and the constants 1 and 0. For any set of the binary variable values involved, a boolean function may have a value of 1 or 0. For instance, we can define the boolean function F = x’y + z in terms of 3 binary variables x, y, z. The function would be equal to 1 in case x = 0 and y = 1 or z = 1.

We can express a boolean function by an algebraic expression, just like the one mentioned here, or in terms of the Truth Table. We can express a function through various algebraic expressions on account of all of these being logically equivalent. But remember, there is just one unique truth table for all the functions.

We can transform a Boolean function from an algebraic one into a circuit diagram that consists of logic gates connected that are in a particular structure. Here is a circuit diagram for F:

Canonical and Standard Forms

A binary variable can easily take one of the two forms, x or x’. We can express a boolean function in terms of n number of binary variables. In case we combine all the binary variables together with the help of the AND operation, there would be a total of 2n combinations. It is because every variable would be able to take two forms.

Every combination here is known as a standard product or a minterm. We represent a minterm by mᵢ where i refers to the decimal equivalent of that binary number to which the minterm is designated.

Important Note – Minterm

In the case of a minterm, the binary variable would be un-primed in case the variable is 1. On the other hand, it would be primed in case the variable is 0. It means that in case the minterm is xy’, then that means x = 1 and y = 0.

For instance, for the boolean functions in two variables, all the minterms would be:

m₀ = x’y’ , m₁= x’y , m₂ = xy’ , m₃ = xy

In a similar manner, in case the variables are combined with the OR operation, the term obtained would be known as a standard sum or a maxterm. We can represent a maxterm by Mᵢ where i refers to the decimal equivalent of that binary number to which the maxterm has been designated.

Important Note – Maxterm

In the case of a maxterm, the binary variable would be un-primed in case the variable is 0. On the other hand, it would be primed in case the variable is 1. It means that in case the maxterm is x’ + y then that means x’ = 1 and y = 0.

For instance, for the boolean function in the given two variables, the maxterms would be–

M₀ = x + y , M₁= x + y’ , M₂ = x’ +y , M₃ = x’ + y’

Here are the Maxterms and Minterms for the function in three variables –

Relation between Maxterms and Minterms

Every minterm would be the complement of their corresponding maxterm.

For instance, for any boolean function that is in two variables –

m₀ = x’y’

(m₀)’ = (x’y’)’

(m₀)’ = (x’)’ + (y’)’

(m₀)’ = x + y = M₀

In general, mᵢ = (Mᵢ)’ or Mᵢ = (mᵢ)’

Constructing Boolean Functions

Once we know what maxterms and minterms are, we can then use them for the construction of the boolean expressions.

“We can express a Boolean function algebraically from a truth table when we perform a minterm for every combination of those variables that produce 1 in the function, and then we take the OR of all of these terms.”

For instance, consider two functions f₁ and f₂ with the truth tables given below:

The function f₁ would be 1 for these combinations of x, y, z – 001, 100, 111

Here, the corresponding minterms would be – x’y’z, xy’z’, xyz.

Thus, the algebraic expression of f₁ would be:

f₁ (x, y, z) = x’y’z + xy’z’ + xyz

f₁ (x, y, z) = m₁ + m₄ + m₇

Similarly, the algebraic expression of f₂ would be:

f₂ (x, y, z) = m₃ + m₅ + m₆ + m₇

Here, in case we use the De Morgan’s Law on f₁ and f₂ then all the Is would become 0 and then all the 0s would become 1. Thus, here, we get:

f₁ (x, y, z)’ = m₀ + m₂ + m₃ + m₅ + m₆

f₂ (x, y, z)’ = m₀ + m₁ + m₂ + m₄

Once we use the De Morgan’s Law again:

f₁ (x, y, z) = (m₀ + m₂ + m₃ + m₅ + m₆)’

f₁ (x, y, z) = m’₀.m’₂.m’₃.m’₅.m’₆

f₁ (x, y, z) = M’₀.M’₂.M’₃.M’₅.M’₆

and

f₂ (x, y, z) = (m₀ + m₁ + m₂ + m₄)’

f₂ (x, y, z) = m₀.m₁.m₂.m₄

f₂ (x, y, z) = M₀.M₁.M₂.M₄

It can be concluded from this information that we can express the boolean functions as the product of maxterms and the sum of minterms.

“We can express Boolean functions as the product of maxterms or the sum of minterms that are in a canonical form.”

Example –

Let us express the boolean expression given below in both SOP and POS forms:

F = x + y’z

Solution:

We can transform the expression into the SOP form when we add the missing variables in every term by multiplying by k + k’ = 1, where k refers to the missing variable.

We can follow this from the fact that -1.x = x.1 = x

F = x(y + y’) + y’z

F = xy + xy’ + y’z

F = xy(z + z’) + xy’(z + z’) + (x + x’)y’z

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

Once we rearrange the minterms in ascending order, then it would go like this:

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

F = m₁ + m₄ + m₅ + m₆ + m₇

In case one wants the POS form, then they can double negate an SOP form, as we have stated above. This way, we will get –

F = M₀.M₂.M₃

The POS form and SOP form have a short notation that can be represented as follows:

F(x, y, z) = ∑ (1, 4, 5, 6, 7)

F(x, y, z) = П(0, 2, 3)

Standard Forms

The canonical forms are the basic forms that can be obtained from the truth table of functions. We do not usually use these forms to represent the given functions as these are cumbersome to write. Also, it is preferable that we represent the given function in as few literals as possible.

There are basically two different types of standard forms. They are:

1. SOP (Sum of Products) – Any boolean expression that involves AND terms along with one literal or more each, OR’ed together.

2. POS (Product of Sum) – Any boolean expression that involves OR terms along with one literal or more each, AND’ed together.

Here are a few examples:

SOP – x’ + xy + yz’

POS – (x’).(x + y).(y + z’)

Note – The expressions given above are not at all equivalent. Instead, these are just examples.

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.

Also Explore,

Comments

Leave a Comment

Your Mobile number and Email id will not be published.

*

*