0:17

This tool is Boolean Algebra, and is the topic of this lesson.

A Boolean algebra B is a set over which two

operations called Boolean sum and

Boolean product are defined and satisfy five postulates.

Our first postulate is that the Boolean sum and product are internal operations.

That means that if a and b are in B,

then their sum and their product are also in B.

It's what we meant when we said that

they are operations over the set B.

The second rule is that to each operation corresponds a neutral element.

That means that, given an element a of B, there exists an element 0,

always the same element, such that a plus 0 is equal to a.

1:31

And there exist within B an element 1 such that a times 1 is equal to a.

The next rule is that to each element corresponds also an inverse element,

that is to say, given any element a of B,

2:00

such that a plus not a is equal to 1 and

a times not a is equal to 0.

Next rule: both operations are commutative,

that is to say that a plus b is equal to b plus a,

and a times b is equal to b times a.

2:24

And finally, rule number five: both operations are distributive,

not only as in the case of the real numbers, that is to say, a times b plus c

is the same as a times b plus a times c,

but also, in a symmetric way, the sum is istributive with respect

to the product: a plus b times c is the same as a plus b times a plus c.

As a matter of fact, all rules are symmetric in Boolean algebra:

given some rule, if you interchange sum and

product, 0 and 1, you'll get another rule.

A first example of Boolean algebra is the set 0,1,

with the the operations defined in this table.

The product a times b is equal to

1 when a and b are equal to 1.

It's the so-called AND function whose implementation is

3:46

a 2-input AND gate.

The sum, the Boolean sum a plus b is equal to 1 if a or

b or both are equal to 1.

It is the so-called OR function, and

its implementation is a 2-input OR gate.

AND and OR.

4:19

Finally, the unary operation inversion is defined as follows:

If a is 0, not a is 1, and

if a is 1, not a is 0,

And its implementation is an inverter.

4:52

For example, let us check the distributivity of

the product with respect to the sum.

For that, we can consider all the combinations of values of a, b and c,

5:10

and compute for each combination the value of both member of this equality.

Let us compute first b plus c:

b plus c is equal to 1 if b or c are equal to 1,

so that b plus c is equal to one here, here, here.

In this case, it's equal to zero, one, one, one.

Then we multiply b plus c by a:

a is equal to 0 in the first

6:11

Let us compute now a times b:

a times b is equal to 1 if, and only if, both a and b are equal to 1.

So a times b is equal to 1 in this one and in this one.

The computation of a by c consists of

looking in which rows a and are equal to 1,

that is to say,

here (1,1) and here (1,1).

Then we compute the sum of a times b and a times c.

The sum is equal to 1 if a times b or a times c is equal to 1,

that is to say, in this one, this one, and this one.

And finally, it's only a matter of comparing

7:20

An important comment, from this property,

is that this circuit, that implements this expression, and

this other circuit that implements the other expression, are equivalent.

Equivalent: I mean that they implement the same Boolean function,

and obviously the second circuit is better than

the other one because it includes less logic gates.

8:18

We have seen a short example of Boolean function, of Boolean Algebra.

The set 0, 1 is a Boolean algebra

but, more generally, the set of n-variable switching functions,

functions that are defined by an application, an application or

mapping from the set of all n-component binary vectors to the set 0, 1,

this set of switching functions is also a Boolean Algebra.

Given two switching functions, let us say f and

g, then we can define f plus g, f times g, not f, in the following way:

we say that function f plus g, for

example, at point x0, x1, and so on,

is equal to the value of f at this point

plus the value of g at this same point.

The same in order to define the product of f by g, and

the same in order to define the complement or the inverse of f.

The neutral elements of this algebra are the constant functions 0 and 1.

Now, apart from the postulates, there are several properties that

can be demonstrated and used to minimize combinational circuits.

The first one says that the inverse or

the complement of 0 is 1 and the inverse of 1 is 0.

It is obvious as: 0 plus 1 is 1 and 0 times 1 is equal to 0.

The second property is the idempotency of the operations.

That means that adding a to a you get a, and

multiplying a by a you get the same value a.

We could try to demonstrate the idempotency of

the Boolean sum using the postulates.

10:48

We know that a is the same as a plus 0 (it's postulate number 2);

0 can be replaced by a times not a;

(it's postulate number three).

Then we use the distributivity law and

substitute a plus a times not a by a plus a times a plus not a.

But we know that a plus not a is equal to 1, so we get this new expression,

11:30

and we know that a plus a times 1 is the same as a plus a.

So, we have demonstrated that a is equal to a plus a.

Idempotency of the sum.

As an exercise you could try to demonstrate the other idempotency rule,

that is, a times a equal to a.

11:58

Actually, if you take the demonstration of the idempotency of the sum,

and just interchange sums and products, and 0 and 1,

you get the demonstration of the other idempotency law.

Let us continue with the useful properties.

Involution means that inverting twice an element, you get the same element.

Associativity is the same concept as in the case of the integer or

the real numbers.

12:38

You can check this property in the case of the 2-element

Boolean Algebra, for example with a table, as we did before,

including all the value combinations of a, b, and c and

check that a plus b plus c is the same as a plus b plus c, and

the same with the Boolean product.

Absorption law is very useful to minimize a Boolean expression.

It states that a plus a times b is equal to a.

You could say that a absorbs the product a times b,

And symmetrically a times a plus b is equal to a.

In this case, you could say that a absorbs the sum of a and b.

13:48

is the same as a plus b, or symmetrically that a times

not a plus b is the same as a times b.

As an exercise, let us try to demonstrate this property.

a plus not a times b could replaced by a plus a b

(absorption law) plus a times b.

14:30

This is 1.

So that finally this is equal to a plus b.

Finally, the de Morgan laws say that the inverse (or

the complement) of a sum is equal to the product of the inverses

and, symmetrically, that the inverse of a product is the sum of the inverses,

and this now can be generalized to any number of sum terms and product factors.

Now, a little quiz.

15:19

In this third section,

we are going to focus on the relation between Boolean expressions,

truth tables, and combinational circuits implemented with logic gates.

First point: given a Boolean expression, for example this one,

we can define an equivalent table that we can generate as follows:

consider all the combinations of values of a,

b, and c, and successively compute not c,

b times not c, not a, not a times b, and finally

the sum of b times not c and not a times b.

16:12

So that finally you get this function.

Conversely, given a truth table, can you generate an equivalent expression?

The answer is yes,

and for that we introduce first the concept of literal.

A literal is a variable or an inverted variable.

Another concept is that of n-variable minterm.

A product of n literals such that each variable appears only once is a minterm.

Here is an example.

If n is equal to 3, there are eight minterms, those ones.

You can see that in every expression,

there are three literals and they are all different.

Then, given a minterm, we can see that there is one and

only one set of variable values such that this minterm is equal to 1.

We assume that n is equal to 3 as before and

consider here the eight combinations of values of three variables a,

b, and c, so that you can define eight minterms,

and observe that the first one, this one, not a times not b times

not c is equal to 1 if, and only if, a, b, c is equal to 0, 0, 0.

The second one is equal to 1 if, and only if,, a, b, c,

is equal to 0, 0, 1, and so on.

18:01

So, to each minterm, and we'll call them m0, m1,

and so on up to m7, corresponds one value combination of a, b,

and c such that the corresponding minterm is equal to 1.

18:20

Question: how can we generate an expression

from a table?

A straightforward method is to look for the 1's of the function,

and associate, with those 1's, the corresponding minterm.

In this case, in this example, function f has three 1's.

To those three 1's correspond those minterms.

Minterms not a times b times not c.

Effectively, this product is equal to 1 if a is equal to 0,

b equal to 1, and c equal to 0.

To this one corresponds this product: not a times b times c,

and to this one corresponds the product: a times b times not c,

so that we can express f under this form,under the form

of the sum of three minterms: minterm m2, m3, and m6,

that is to say, under the form of this Boolean expression.

Actually, this is very like what we did before when we said something like that:

19:40

f is equal to 1 if, and then we write the following conditions:

a b c is equal to 010, or

a b c is equal to 011,

or a b c is equal to 110.

We could say that we have formalized in an algebraic way this kind of

condition. By the way, this type of representation, s a sum of minterms,

is called "canonical representation" of the function.

To summarize, assume that we have specified a combinational circuit by

means of some functional description,

for example, this very simple piece of program.

20:45

This description can be translated to a table by considering

all the value combinations of a, b, and c, and

executing, for each of those combinations, this piece of algorithm.

Then, from the table, you can generate the corresponding

canonical expression with as many minterms as 1's of the function,

in this case, three 1's to which correspond three minterms.

Then, using the rules and

properties of the Boolean Algebras, you can simplify the expression.

In this case, for example, you can see that

here you have not a, b, not c,

and here, not a, b, c, that can be replaced by not a,

b, times not c plus c, which is equal to 1,

so that, finally, you get this term,

and the same for the other one so that, finally, you get a simpler

expression to which you can associate

a circuit made up of AND gates and OR gates.

22:21

Let us go back, to conclude, to the 4-bit adder.

It has been defined as an hierarchical structure,

that is to say that the 4-bit adder is decomposed into four 1-bit adders,

so that it remains to synthesize the 1-bit adder.

Here is the truth table that defines the function generated by the 1-bit adder.

Observe that both c0 and

z have four minterms:

c0 is equal to not

x times y times ci

(it corresponds to this row),

plus x, not y, ci,

plus x y not ci plus x y ci.

24:01

That is to say, y ci.

And you can do the same with the other terms

(don't forget that the sum operation is idempotent);

you can add x y ci as many times as you want so

that finally the simplified expression is y ci plus x ci plus x y.

Then you can do the same for the z function.

In this case, there are no simplification.

Finally, you get those relations,

and from those relations, you can deduce the following circuit.

This circuit implements a 1-bit adder,

and the 4-bit adder: this could be the first hierarchical level,

25:06

Summary of this lesson:

We have seen what Boolean Algebra is, how it can be defined,

and which are the postulates and some of the main properties.

We have seen that Boolean functions can be represented by tables.

We introduced the concept of minterm and of canonical sum of product expression.

Finally, we have seen how a circuit can be generated from a

functional description. From the functional description, we deduced a table.