[Tutorial] Introduction to Boolean Algebra, Part III

[Acid_Snake]

MINTERMS AND MAXTERMS
In this part of the tutorial I will introduce three new concepts: minterms, maxterms and truth table

The idea behind minterms and maxterms is to study which values for the different variables make the function F return 1 and which make it return 0. The values for which F returns 1 are called minterms, while the values that make F return 0 are called maxterms.
Minterms are represented as a summation of numbers, in maths the symbol for summation is Σ (sigma), so a well represented array of minterms for a function would be as an example: Σ(1,2,3,4,5,...), but my keyboard doesn't have the Σ in it so for now on I will represent them as S(1,2,3,4,5,...), same goes for maxterms, they are multiplication of numbers, in math the symbol for multiplication is Π, so the maxterms of a function are represented as Π(1,2,3,4,5,...), but I will represent them as P(1,2,3,4,5,...). Just remember that on paper, you must use Σ and Π.

A truth table is a table (duh) that holds all possible values the variables can have and the respective output of the function, the tables will have this structure:

Code: Select all

|Values of the variables| value of F|
|---------------------------|------------|
|blablabla                    |blablabla |
|---------------------------|-----------|

As a very nice feature, you don't need to obtain the minterms, maxterms and truth table separately, you obtain them all at the same time. But, depending on the type of function, you will need to obtain either the minterms or maxterms first.
As we know there are two types of functions: summation of products or product of sums.
- Summation of products: functions that have the type AB+C, you have to obtain minterms first.
- Product of sums: functions that have the type (A+B)*C, you must obtain the maxterms first.


Obtaining the minterms of the function AB'+C
This function we know is a summation of products, so we need to obtain the minsterms first.
We also know that this function has three variables: A, B and C, and the function has two products: AB' and C.
With this we know we have to make two truth tables, one for AB and another one for C.
The first thing we do is write these truth tables using three X's as we have three variables:

Code: Select all

XXX    XXX

now we replace the variables that we know for each product, in the first product we have A and we have B', so we replace the X's in the correct order:

Code: Select all

AB'X    XXX

on the second product we only have C, so we replace the X on the position of C:

Code: Select all

AB'X    XXC

Remember that variables MUST be in the correct order: ABCD, A3A2A1A0, etc
Now that we have this, we must write all possible combinations that the X's can have, let's start with the first one:
AB'X, it has only one X so the only possible combinations are 0 and 1, so I write that bellow the X, leaving space for the known variables:

Code: Select all

AB'X
    0
    1

Now, the easy part, for the variables that exists (A and B), we write 1 if they are not negated and 0 if they are negated, A is not negated to we write 1, and B is negated so we write 0:

Code: Select all

AB'X
100
101

Now we have the truth table for AB', now we have to get the truth table for C:

Code: Select all

XXC

first we write all possible combinations of the X's. There are two X's, so the possible combinations are: 00, 01, 10, 11.
We write that:

Code: Select all

XXC
00
01
10
11

Now, the C is not negated, so we fill its spot with 1's:

Code: Select all

XXC
001
011
101
111

now we have the truth tables for the entire function:

Code: Select all

AB'X        XXC
100        001
101        011
             101
             111

now, we convert each minterm to a decimal number:

Code: Select all

AB'X           XXC
100|4        001|1
101|5        011|3
                 101|5
                 111|7

we could see that both AB' and C share one number: 5, so we remove one of them:

Code: Select all

AB'X           XXC
100|4        001|1
101|5        011|3
                 111|7

now we finally have the minterms for AB'+C:

Code: Select all

S(1,3,4,5,7)

What this tells us is that the function F(A,B,C)=AB'+C will return 1 for the combinations of ABC that represent the numbers 1,3,4,5,7.
Now, onto the maxterms, obtaining the maxterms means obtaining the numbers that make F return 0, those numbers, obviously, are the ones that aren't on the minterms, you can do this directly and we get that:

Code: Select all

P(0,2,6)

But if you can't see this at first glance, then simply make a truth table of all possible values that ABC can have:

Code: Select all

ABC
000|0
001|1
010|2
011|3
100|4
101|5
110|6
111|7

now we remove the minterms, which we already know:

Code: Select all

ABC
000|0
010|2
110|6

and what's left are the maxterms.


Obtaining the maxterms of the function: (A+B')*(C+B)
This function is the exact opposite type of the previous one, it's a product of sums rather than a sum of products, this means that we need to obtain the maxterms for this one first. It also means that, when doing the truth table, a negated variable will be equal 1 and a variable that is not negated will be equal 0, the opposite of the previous function, but the truth table is done in a similar manner. First we see that we have two sums: A+B' and C+B, and we have three variables: A, B and C, so the truth table will look like this:

Code: Select all

XXX    XXX

Now we replace the first set of X's with the first sum: A+B':

Code: Select all

AB'X    XXX

and the second one with C+B:

Code: Select all

AB'X    XBC

remember that variables must be in order, so instead of just filling it with C+B we fill it with B+C (we apply the commutative property). Now, just like we did before, we down all possible combinations of the X's

Code: Select all

AB'X    XBC
    0    0
    1    1

Now, all negated variables will be 1, and not negated variables will be 0:

Code: Select all

AB'X    XBC
010    000
011    100

and we obtain the decimal representation of those combinations:

Code: Select all

AB'X       XBC
010|2    000|0
011|3    100|4

we now have the maxterms of this function:

Code: Select all

P(0,2,3,4)

and of course, we implicitly also have the minterms:

Code: Select all

S(1,5,6,7)

Usage
Minterms and maxterms are used in conjunction with Karnaugh maps (we'll see them in the next lesson) to do one of the following:
- Simplify the original function to the max.
- Given only the minterms or maxterms, you can obtain a simplified version of the original function.


Exercise
As a learning exercise, I want you obtain the minterms and maxterms for the following functions:

Code: Select all

F = BD + BC'(AD' + A'D)

Code: Select all

G = AB'C'D + AC'D' + AB + A'BD + AB'C

Code: Select all

H = (B + E)*(C + D' + E)*(B' + C + D')*(C + E')

Previous: viewtopic.php?f=37&t=33507
Next: viewtopic.php?f=37&t=33704

Advertising

[pspfanMOHH]

Code: Select all

F(ABCD) = BD + BC'(AD' + A'D) = BD + (ABC'D' + A'BC'D) = BD + ABC'D' +ABC'D

xBxD            ABC'D                   ABC'D'
0101 = 5       1101 = 13             1100 = 12   
0111 = 7                                        
1101 = 13
1111 = 15

S(5,7,12,13,15)
P(0,1,2,3,4,6,8,9,10,11,14)


G(ABCD) = AB'C'D + AC'D' + AB + A'BD + AB'C

AB'C'D             AxC'D'           ABxx              A'BxD                   AB'Cx                         
1001 = 9         1000 = 8       1100 = 12       0101 = 5              1010 = 10                             
                     1100 = 12      1101 = 13       0111 =   7            1011 = 11
                                         1110 = 14
                                         1111 = 15


S(5,7,8,9,10,11,12,13,14,15)
P(0,1,2,3,4,6,)     



H(BCDE) = (B + E)*(C + D' + E)*(B' + C + D')*(C + E')


BxxE                           xCD'E                 B'CD'x             xCxE'
0000 = 0                     0010 = 2            1010 = 10        0001 = 1                                                                                   
0010 = 2                     1010 = 10          1011 = 11        0011 = 3                                                                                 
0100 = 4                                                                    1001 = 9
0110 = 6                                                                    1011 = 11
                                                                  
                                                                                                       
P(0,1,2,3,4,6,9,10,11)
S(5,7,8,12,13,14,15)

Truth table is similar to sets and numbers in regular algebra

Advertising

[Acid_Snake]

The first one is wrong because you have this:

Code: Select all

BDxx            ABC'D

I have stated twice that you have to place variables in order: ABCD
The way you placed them you had: BDAC
and that's incorrect, you should have done:

Code: Select all

xBxD            ABC'D

and this of course makes the minterms come out incorrectly (even though you correctly did the procedure)

On the second one, I don't know what you did to simplify it, but you shouldn't have done anything to it, it was already in standard form so we can work with it directly, please don't simplify functions, we got karnaugh for that, the only reason we use boolean algebra properties is to make functions look canonical/standard, but this one was already in the standard form, you could have just taken the function directly and grab the minterms. Btw, I did karnaugh maps on this function after getting the minterms directly out of it, and the simplified form looks like this: A+BCD'

On the third one it's the same thing, don't simplify a function, you just want to make it standard and this one was already standard, the only real challenge in that function was (C+E')', which is a NOR gate that we haven't seen yet but that was just an error on my part.

[pspfanMOHH]

Code: Select all

F(ABCD) = BD + BC'(AD' + A'D) = BD + (ABC'D' + A'BC'D) = BD + ABC'D' +ABC'D

xBxD            ABC'D                   ABC'D'
0101 = 5       1101 = 13             1100 = 12   
0111 = 7                                        
1101 = 13
1111 = 15

S(5,7,12,13,15)
P(0,1,2,3,4,6,8,9,10,11,14)


G(ABCD) = AB'C'D + AC'D' + AB + A'BD + AB'C

AB'C'D             AxC'D'           ABxx              A'BxD                   AB'Cx                         
1001 = 9         1000 = 8       1100 = 12       0101 = 5              1010 = 10                             
                     1100 = 12      1101 = 13       0111 =   7            1011 = 11
                                         1110 = 14
                                         1111 = 15


S(5,7,8,9,10,11,12,13,14,15)
P(0,1,2,3,4,6,)     



H(BCDE) = (B + E)*(C + D' + E)*(B' + C + D')*(C + E')


BxxE                           xCD'E                 B'CD'x             xCxE'
0000 = 0                     0010 = 2            1010 = 10        0001 = 1                                                                                   
0010 = 2                     1010 = 10          1011 = 11        0011 = 3                                                                                 
0100 = 4                                                                    1001 = 9
0110 = 6                                                                    1011 = 11
                                                                  
                                                                                                       
P(0,1,2,3,4,6,9,10,11)
S(5,7,8,12,13,14,15)

Confused regular algebra concept of simplifying with boolean.

[Acid_Snake]

Alright, first things first:
- the first function is correct, but you miss one minterm: number 12. When you use distributive property on the function, you end up with: BD + BC'AD' + BC'A'D, you missed BC'AD' (ABC'D') which gives you the number 12 minterm, but other than that, everything else is correct.
- the second function is correct
- the last function has an error: the variable A is nowhere to be seen in the actual function, yet you assume it's there, which is highly incorrect. Not only you are doing the exact opposite of simplifying by adding a variable that doesn't exists, but you are also adding maxterms and minterms that don't exist. Unless it is explicitly stated, or the circumstances obey you to use a variable that the end function won't use, just ignore the variable as t doesn't exists. Also, in the truth table for xxCD'E, you have:
xxCD'E
00010 = 2
01010 = 10
10010 = 18
11010 = 26
lease remember that this function is a multiplication of sums, it has the following looks: (A+B)*(B+C)
so you have to grab the maxterms first, this you have done and is correct, but you incorrectly give C the value 1, D' the value 0 and E the value 1. It's the other way around for maxterms: C=0 as it's not negated, D'=1 as it's negated, E=0 as it's not negated. I assume it was a lapsus on your part as you did it correctly for the first truth table (xBxxE) and the third and forth ones (xB'CD' and xxCxE') but not on the second one.

[pspfanMOHH]

Code: Select all

F(ABCD) =     S(5,7,12,13,15)
                             P(0,1,2,3,4,6,8,9,10,11,14)


H(BCDE) = (B + E)*(C + D' + E)*(B' + C + D')*(C + E')


BxxE                           xCD'E                 B'CD'x             xCxE'
0000 = 0                     0010 = 2            1010 = 10        0001 = 1                                                                                   
0010 = 2                     1010 = 10          1011 = 11        0011 = 3                                                                                 
0100 = 4                                                                    1001 = 9
0110 = 6                                                                    1011 = 11
                                                                  
                                                                                                       
P(0,1,2,3,4,6,9,10,11)
S(5,7,8,12,13,14,15)

The part about not replacing x for variable undefined is not stated in the tutorial.
Learned something new outside the tutorial
After staring at the screen with some many numbers and still typing I felt kind of dizzy and just kept typing

[Xian Nox]

I have to ask if you tried on purpose to come up with the hardest imaginable way to make a truth table.
At least I find it much easier to just make a Veitch diagram first, make a proper-looking truth table next, and just get the values from the diagram.

Code: Select all

f = ab' + c

      b b       a b c | f
.+-+-+-+-+   0) 0 0 0 | 0
.| |1|1| |   1) 0 0 1 | 1
.+-+-+-+-+   2) 0 1 0 | 0 
a|1|1|1| |   3) 0 1 1 | 1
.+-+-+-+-+   4) 1 0 0 | 1
    c c      5) 1 0 1 | 1
             6) 1 1 0 | 0
             7) 1 1 1 | 1