About Boolean Algebra (ABA)

Boolean algebra is one of the algebras related to binary variables and logical operations. The variables in Boolean algebra are expressed by letters such as: A, B, C, ..., X, Y, Z. While in Boolean algebra there are 3 basic logical operations, namely: AND, OR and NOT (Complement).

The Inventor of Boolean Algebra

A Boolean function is an algebraic expression formed with binary variables, logical operation symbols, parentheses and the "=" sign. For a given value of the variable, a Boolean function can be either 1 or 0.

Examples of Boolean functions:

f = X + Y'.Z

• The function f is equal to 1 if X = 1 or if both values ​​Y' and Z = 1.
• f = 0 in other cases.

But we can also state that if Y' = 1, then Y = 0, because Y' is the complement of Y. Equivalently we can state that:

f = 1, jika X = 1  atau  Y.Z = 0.1

The relationship between a function and its binary variables can be presented in the form of a Truth Table. To present a function in a truth table, we need a list of 2n combinations of 1 and 0 from n binary variables.

Example:  

f   =   X + Y' . Z
∑ variabel = 3 (X, Y' dan Z)
2n  =   23   =   8  kombinasi 0 dan 1.

So the truth table is as follows:

| X | Y | Y’ | Z | Y‘.Z | f =   X + Y’ . Z |
|---|---|----|---|------|------------------|
| 0 | 0 | 1  | 0 | 0    | 0                |
| 0 | 0 | 1  | 1 | 1    | 1                |
| 0 | 1 | 0  | 0 | 0    | 0                |
| 0 | 1 | 0  | 1 | 0    | 0                |
| 1 | 0 | 1  | 0 | 0    | 1                |
| 1 | 0 | 1  | 1 | 1    | 1                |
| 1 | 1 | 0  | 0 | 0    | 1                |
| 1 | 1 | 0  | 1 | 0    | 1                |

A Boolean function can be converted into a logic diagram consisting of logic gates.

Example: 

f = X + Y' . Z

The logic diagram:

The use of Boolean algebra is to provide writing facilities in digital circuit design. Boolean algebra provides tools to create:

• Expressing in algebraic form a truth table which is the relationship between variables,
• Expressing in algebraic form the relationship between input and output of a logic diagram,
• Get simpler circuits for the same function.

Basic Relations of Boolean Algebra

| 1.  X + 0 = X | 7.    X + X’ = X        | 13.   X.(Y+Z) = X.Y + X.Z     |
|---------------|-------------------------|-------------------------------|
| 2.  X + 1 = 1 | 8.    X . X’ = 0        | 14.   X + Y.Z = (X+Y) . (X+Z) |
| 3.  X . 0 = 0 | 9.    X + Y = Y + X     | 15.   (X + Y)’ = X’ . Y’      |
| 4.  X . 1 = X | 10.  X . Y = Y . X      | 16.   (X.Y)’ = X’ + Y’        |
| 5.  X + X = X | 11.   X+(Y+Z) = (X+Y)+Z | 17.   (X’)’ = X               |
| 6.  X . X = X | 12.  X.(Y.Z) = (X.Y).Z  | 18.   X.(X+Y) = X             |
|               |                         | 19.   X + (X.Y) = X           |

Information:

• The relations (1), (2), (3) and (4) are called the Law of Interconnection with Constants.
• Relations (5) and (6) are called the laws of expansion.
• The relation (7) and (8) is called the Law of complementation.
• Relations (9) and (10) are called Commutative Laws.
• The relations (11) and (12) are called associative laws.
• Relations (13) and (14) are called distributive laws.
• Relation (14) cannot be used in ordinary algebra, but it is very useful in manipulating Boolean algebra expressions.
• Relations (15) and (16) are called de Morgan's Theorem.
• Relation (17) states that if a variable is complemented twice, the original value of the variable will be obtained.
• The relation (18) and (19) is called the law of absorption.

Definition of Boolean Algebra

Algebra is an algebraic system on a set S with two operations, namely addition ( + ) and multiplication ( . ) which are defined on the set.

Suppose there are:

• Two binary operators: + and ⋅
• A unary operator: '. 
• B : the set defined by the operators +, ⋅, and ' 
• 0 and 1 are two different elements of B.

Clues:

(B, +, ⋅, ’)

So, it is called Boolean Algebra if for every a, b, c ∈ B the following axioms or Huntington's postulates or laws apply:

Laws of Boolean Algebra

1. Closure:

• (i) a + b ∈ B
• (ii) a ⋅ b ∈ B

2. Identity:

• (i) a + 0 = a
• (ii) a ⋅ 1 = a

3. Idempotent:

• (i) a + a = a
• (ii) a ⋅ a = a

4. Complement:

• (i) a + a' = 1
• (ii) aa' = 0

5. Dominance:

• (i) a ⋅ 0 = 0
• (ii) a + 1 = 1

6. Involution:

• (i) (a')' = a

7. Absorption:

• (i) a + ab = a
• (ii) a(a + b) = a

8. Commutative:

• (i) a + b = b + a
• (ii) ab = ba

9. Associative:

• (i) a + (b + c) = (a + b) + c 
• (ii) a (bc) = (ab) c

10 Distributive:

• (i) a + (bc) = (a + b) (a + c)
• (ii) a (b + c) = ab + ac

11. De Morgan: 

• (i) (a + b)' = a'b'
• (ii) (ab)' = a' + b'

12. Law of 0/1:

• (i) 0' = 1
• (ii) 1' = 0

Example:

Prove (i) a + a'b = a + b and (ii) a(a' + b) = ab

Solution:

(i) a + a'b = (a + ab) + a'b (Absorption)
                 = a + (ab + a'b) (Associative)
                 = a + (a + a')b (Distributive)
                 = a + 1 - b (Complement)
                 = a + b (Identity)

(ii) is the dual of (i)

The Principle of Duality

If a Boolean algebraic equality B is true then the dual of B , obtained by replacing each + with . or vice versa and replacing each 1 with 0 or vice versa, is also true.

Boolean Algebra Applications

A. Switching Network

Switch, which is an object that has two states; open and closed. The three simplest forms of gates:

1. Output b exists only if and only if x is opened ⇒ x

2. Output b exists only if and only if x and y are opened ⇒ xy

3. Output c exists only if and only if x or y is opened ⇒ x + y

B. Switching circuit in an electrical circuit:

1. Switches in SERIES connection: AND logic

2. Switches in PARALLEL connection: OR logic

Boolean Algebra Problem Discussion & Solution

Subject:

1. Stating Boolean Functions in SOP & POS Forms
2. Conversion Between Canonical Forms
3. Standard Form
4. Karnaugh Map Minimization Technique

1. Stating Boolean Functions in SOP & POS Forms 

To express a Boolean function in SOP or POS form, you can do the following:

• Completing the literal
• Forming minterm/maxterm from its truth table

Example:

Express the Boolean function f(x, y, z) = x + y'z in canonical form SOP and POS!

Method 1

f(x, y, z) = x + y'z

(a) SOP

x   = x(y + y')
    = xy + xy'
    = xy (z + z') + xy'(z + z')
    = xyz + xyz' + xy'z + xy'z'

y'z = y'z (x + x')
    = xy'z + x'y'z

So,

f(x, y, z)  = x + y'z
            = xyz + xyz' + xy'z + xy'z' + xy'z + x'y'z
            = x'y'z + xy'z' + xy'z + xyz' + xyz

or

f(x, y, z)  = m1 + m4 + m5 + m6 + m7
            = S (1,4,5,6,7)

(b) POS

f(x, y, z) = x + y'z
           = (x + y')(x + z)
            (Hk Distributif)

x + y' = x + y' + zz'
       = (x + y' + z)(x + y' + z')

x + z   = x + z + yy'
        = (x + y + z)(x + y' + z)

So,

f(x,y,z)  =  (x +y'+ z) (x +y'+ z') (x + y + z) (x + y' + z)
          =  (x +y+ z) (x +y' + z) (x + y' + z')

or

f(x, y, z) = M0M2M3
           = Õ(0, 2, 3)

2. Conversion Between Canonical Forms

Suppose f(x, y, z) = S (1, 4, 5, 6, 7) and f ' is the complement function of f,

f'(x, y, z) = S(0, 2, 3) = m0+ m2 + m3

Using De Morgan's law, we can obtain a function f in POS form:

f '(x, y, z) = (f '(x, y, z))' = (m0 + m2 + m3)'
               = m0' . m2' . m3'
               = (x'y'z')' (x'y z')' (x'y z)'
               = (x + y + z) (x + y' + z) (x + y' + z')
               = M0 M2 M3
               = Õ(0,2,3)

Jadi,  f(x, y, z) = S (1, 4, 5, 6, 7) = Õ (0,2,3).

Kesimpulan: mj' = Mj

3. Standard Form

The standard form of a boolean function does not have to contain complete literals.

For example;

f(x, y, z) = y' + xy + x'yz           (bentuk baku SOP)
f(x, y, z) = x(y' + z)(x' + y + z')   (bentuk baku POS)

Karnaugh Map Minimization Technique

Boolean function minimization technique with Karnaugh maps:

• Merge adjacent boxes.
• Opposite squares are considered as adjacent squares.

Karnaugh Map 1

Form a RECTANGLE so that it includes as many 1s as possible, but the number of 1s must be 2n, such as 1, 2, 4, 8, 16, 32, and so on.

Karnaugh Map 2

Karnaugh Map 3

Karnaugh Map 4

Example:

Determine the simple form of a Boolean function that represents the Truth table in SOP and POS form!

Standard Form of SOP: Group 1 f(x,y,z) = x'z + xz'

POS Standard Form: Group 0 f(x,y,z) = (x+z)(x'+z')

How to Simplify Boolean Functions

Boolean functions are sometimes too complex, so they need to be simplified. There are 3 methods of simplifying boolean functions:

1. Algebraic method is not recommended because it is trial and error.
2. Karnaugh Map Method.
3. Quine Mc Cluskey Method

1. Karnaugh Map Method

Graphical Method to Simplify Boolean Functions. Discovered by Maurice Karnaugh in 1953. Karnaugh map is described as an arrangement of 2n squares (n=number of variables). Each square represents a minterm and each square is said to be adjacent if its minterms differ by 1 literal.

With the Karnaugh map method, the function value that is logical 1 is depicted on the map. Placing the number 1 on the map follows the input state in the truth table. After being drawn on the map, the adjacent (neighboring) numbers 1 are grouped into one with the number of group members 2n (as many as possible). This group is named with the input that does not experience a change in state in each group member.

Karnaugh Map with Two Variables

Karnaugh map with three variables

4 variable Karnaugh map

The technique of simplifying Boolean functions with Karnaugh maps is done by combining boxes that have a value of 1 and are adjacent to each other (neighbors). Groups of boxes that have a value of 1 can form:

1. Couple (two)
2. Quad (four)
3. Octet (eight)

1. Pair: two pieces, one next to the other 

2. Quad: four adjacent pieces

Or,

3. Octet: eight adjacent 1s

Example 1

Simplify the Boolean function that has the characteristics as in the following table!

| x | y | z | f |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |

Before being simplified,  f = x'.y'.z' + x'.y.z + x.y'.z' + x.y.z (SOP form) was obtained

From the table above, a Karnaugh map can be made:

So that the function is obtained: f = y'.z' + y.z

Example 2

Given a truth table, draw a Karnaugh Map.

Discussion of Boolean Function Questions

As is known, in a function there is always a set of origin (domain) and a set of results (range). A Boolean function is a function that involves operations in Boolean algebra, in addition the domain and range come from the set S.

Boolean Figure

Function Form

Boolean functions sometimes have different forms, but are actually the same. One effort to compare, the function is brought to a standard form. This standard form of a boolean function is known as CANONIC. There are two types of canonical forms:

1. SOP (Sum Of Product) / Sum of the results of the multiplication

In this form, the function is expressed by the sum of the results of the multiplication of the function's literals. Each term that is added is called a minterm. In writing, the minterm is symbolized by a lowercase letter m given a numeric index that indicates the multiplication of the literals it represents. For example: f(x,y)= x'.y' + xy' can be written as m0 + m2. The term x'.y' is written with an index of 0 because if the literal is complemented it means it shows the number 0, so x'.y'= 00 in binary, in decimal it is written as 0. The term xy' shows the number 10 in binary, so its index is 2 because 10 in binary is the same as 2 in decimal. And so on, this kind of rule also applies to more literals.

2. POS (Product Of Sum) form / Multiplication of the total result

In this form, the function is expressed by multiplying the results of the addition of the function's literals. Each factor that is multiplied is called a maxterm. In writing, the maxterm is symbolized by the capital letter M given a numeric index that indicates the addition of the literals it represents. For example: f(x,y)= (x+y).( x'+y) can be written as M0 . M2. The factor x+y is written with an index of 0 because if the literal is not complemented it means it shows the number 0, so x+y = 00 binary, in decimal it is written as 0. The factor x'+y shows the number 10 binary, so its index is 2 because 10 in binary is the same as 2 in decimal. And so on, this kind of rule also applies to more literals.

Example:

1. SOP

f(x, y, z) = x'y'z + xy'z' + xyz

(Each term is called a minterm)

2. POS

g(x, y, z) = (x + y + z)(x + y' + z)(x + y' + z')
           = (x' + y + z')(x' + y' + z)

(Each term is called a maxterm)

Note: Each minterm or maxterm contains a complete literal.

Minterm & Maxterm Boolean Functions of Two Variables

| x | y | Minterm |         | Maxterm |         |
|---|---|---------|---------|---------|---------|
|   |   | Suku    | Lambang | Suku    | Lambang |
| 0 | 0 | x’y’    | m0      | x + y   | M0      |
| 0 | 1 | x’y     | m1      | x + y’  | M1      |
| 1 | 0 | x y’    | m2      | x’ + y  | M2      |
| 1 | 1 | x y     | m3      | x’ + y’ | M3      |

Minterm & Maxterm of Three Variable Boolean Functions

| x | y | z | Minterm |         | Maxterm    |         |
|---|---|---|---------|---------|------------|---------|
|   |   |   | Suku    | Lambang | Suku       | Lambang |
| 0 | 0 | 0 | x’y’z’  | m0      | x + y + z  | M0      |
| 0 | 0 | 1 | x’y’z   | m1      | x + y + z’ | M1      |
| 1 | 1 | 0 | x‘y z’  | m2      | x + y’+z   | M2      |
| 1 | 1 | 1 | x’y z   | m3      | x + y’+z’  | M3      |
| 0 | 0 | 0 | x y’z’  | m4      | x’+ y + z  | M4      |
| 0 | 0 | 1 | x y’z   | m5      | x’+ y + z’ | M5      |
| 1 | 1 | 0 | x y z’  | m6      | x’+ y’+ z  | M6      |
| 1 | 1 | 1 | x y z   | m7      | x’+ y’+ z’ | M7      |

SOP and POS 

• A Boolean function can be formed algebraically from a known truth table by forming minterms/maxterms from each combination.
• To form an SOP, review the combination of variables that result in a value of 1. 
• To form a POS, review the combinations of variables that result in a value of 0.

For more details, please see the examples below:

Question 1

f(x,y) = x.y + x' Ubahlah fungsi ini ke bentuk standard SOP maupun POS!

Solution 1

The first thing we do is create a truth table for the function with 2n rows, where n is the number of variables.

| x | y | No Indeks | x.y | x’ | f(x,y) |
|---|---|-----------|-----|----|--------|
| 0 | 0 | 0         | 0   | 1  | 1      |
| 0 | 1 | 1         | 0   | 1  | 1      |
| 1 | 0 | 2         | 0   | 0  | 0      |
| 1 | 1 | 3         | 1   | 0  | 1      |

To get the SOP form, take the function row that has a value of 1, based on the table above then:

f(x,y) = x'y' + xy' + xy
       = m0 + m2 + m3
       = Σ (0, 1, 3)

For the POS form, the function row that has a value of 0 is selected, based on the table, the POS form of the function is:

f(x,y) = (x' + y)
       = M2
       = Π(2)

Question 2

Express the truth table below in canonical form SOP and POS.

| x | y | z | f(x, y, z) |
|---|---|---|------------|
| 0 | 0 | 0 | 0          |
| 0 | 0 | 1 | 1          |
| 0 | 1 | 0 | 0          |
| 0 | 1 | 1 | 0          |
| 1 | 0 | 0 | 1          |
| 1 | 0 | 1 | 0          |
| 1 | 1 | 0 | 0          |
| 1 | 1 | 1 | 1          |

Solution 2

1. SOP

The combination of variable values ​​that produce a function value equal to 1 is 001, 100, and 111.

The Boolean function in SOP canonical form is:

f(x, y, z) =  x'y'z + xy'z' + xyz

Or by using the symbol (minterm):

f(x, y, z) =  m1 + m4 + m7 = Σ (1, 4, 7)

Illustration

| x | y | z | f(x, y, z) |
|---|---|---|------------|
| 0 | 0 | 0 | 0          |
| 0 | 0 | 1 | 1          |
| 0 | 1 | 0 | 0          |
| 0 | 1 | 1 | 0          |
| 1 | 0 | 0 | 1          |
| 1 | 0 | 1 | 0          |
| 1 | 1 | 0 | 0          |
| 1 | 1 | 1 | 1          |

2. POS 

The combination of variable values ​​that produce a function value equal to 0 is 000, 010, 011, 101, and 110.

Its Boolean function in POS canonical form is:

f(x, y, z)  =  (x + y + z)(x + y'+ z)(x + y'+ z')
            = (x'+ y + z')(x'+ y'+ z)

Or by using the symbol (maxterm):

f(x, y, z) =  M0 M2 M3 M5 M6 = Π(0, 2, 3, 5, 6)

Illustration

| x | y | z | f(x, y, z) |
|---|---|---|------------|
| 0 | 0 | 0 | 0          |
| 0 | 0 | 1 | 1          |
| 0 | 1 | 0 | 0          |
| 0 | 1 | 1 | 0          |
| 1 | 0 | 0 | 1          |
| 1 | 0 | 1 | 0          |
| 1 | 1 | 0 | 0          |
| 1 | 1 | 1 | 1          |

Complement Function

The complement of a function can be obtained in two ways:

1. Applying De Morgan's law
2. Using the principle of duality, with the following steps:

• Look for dual function forms.
• Complement each literal.

Example:

Determine the complement of F = x.(y'.z' + y.z) !

Method 1

F   = x.(y'.z' + y.z)

F'  = [x.(y'.z' + y.z)]'
    = x' + (y'.z' + y.z)'
    = x' + (y'.z')'.(y.z)'
    = x' + (y+z).(y'+z')

Method 2

F  = x.(y'.z' + y.z)
Dual = x + (y'+z').( y+z)
F'  = x' + (y+z).(y'+z')

Netizens

Q1:  MUHAMMAD BAGUS 16 Jan 2017, 23:10:00 = The minterm in solution 1 does not match the table.

A1:  Hii MUHAMMAD BAGUS, thanks for the correction, good job!

Boolean Algebra Functions & Boolean Laws

Boolean algebra can be used to analyze a logic circuit and express it mathematically, the most important application in boolean algebra is the simplification of logic circuits, if the boolean expression for a logic circuit has been obtained then usually to simplify/summarize it again is by using boolean laws. The simplified boolean expression must be equivalent/the same as the original.

Substance:

1. CASE STUDY
2. Demorgan's Theorem
3. Demorgan's Law
4. Boolean Laws Having a Single Variable
5. Boolean laws that have more than 1 variable
6. Proof of Boolean Laws of Equation

1. Case Study

A logic circuit that has an output is:

So, draw the logic circuit and simplify the equation!!

Solution:

2. Demorgan's Theorem

A mathematician named Demorgan named two theorems/rules of Boolean algebra. These rules are useful for simplifying a Boolean expression of the product or sum of inverted variables.

When using Demorgan's rules remember that A and B represent single variables or expressions.

3. Demorgan's Law

4. Bolean's Law Which Has a Single Variable

5. Boolean laws that have multiple variables

a. Commutative Law

b. Associative Law

c. Distributive Law

Proof

(A+B) * (A+C) = AA + AC + AB + BC
                          = A (1 + C + B) + BC
                          = A(1) + BC
                          = A + BC

A + AB = A

A + AB = A (1+B)
                 = A (1)
                 = A

Properties of Boolean Algebra

Table 2.1 summarizes some of the properties of Boolean algebra that can be applied to Boolean logical expressions. The postulates (known as Huntington's postulates) are the basic axioms of Boolean algebra and do not require proof. Theorems can be proved from the postulates. Every relation in the table has AND and OR forms as a result of the principle of dualism. This dualism allows the AND form to be transformed into OR and the OR form to be transformed into AND.

The commutative property states that the order in which two variables appear in the AND and OR functions does not produce different results. By the principle of dualism, the commutative property has the form AND (AB = BA) and the form OR (A + B = B + A). The distributive property shows how the variables are distributed through the AND operation. Because of the principle of dualism, there is also a distributive property for OR.

The identity property shows that a variable that is ANDed with 1 or ORed with 0, produces the value of the variable itself. The complement property results in a variable that is ANDed with its complement, producing a value of 0 (because at least 1 operand must have a value of 0), and a variable that is ORed with its complement, producing a value of 1 (because there must be a value of 1 in its operand).

Figure 2.12: Proof of DeMorgan's theorem for 2 variables

The zero and one theorem states that an AND operation between a variable and 0 will produce 0 and an OR operation between a variable and 1 will produce 1. The idempotent theorem states that an AND or OR operation between a variable and itself produces the value of the variable itself.

The associative theorem states that the order of AND or OR operations does not produce different results. The involution theorem states that the complement of the complement of a variable is the variable itself.

DeMorgan's theorem, consensus theorem, and absorption theorem are not so obvious that we need to prove them. DeMorgan's theorem can be proven by induction, namely by listing all possible values ​​of 2 variables A and B and the function being proved as in Figure 2.12. The left and right sides of DeMorgan's expression have the same value, this is the proof. For the consensus and absorption theorems, please try them yourself for practice.

Not all logic gates are discussed in depth because based on 3 sets of logic gates, namely {AND, OR, NOT}, {NAND}, and {NOR}, one set can be composed of gates in other sets.

For example, the implementation of OR using the {NAND} set. DeMorgan's theorem can be used to construct an OR gate from NAND gates as in Figures 2.13 and 2.14. The explanation is as follows:

To get the inversion (NOT) of the NAND gate the explanation is:

Figure 2.13: Arranging NAND into OR

Figure 2.14: Implementation of inversion with NAND

The AND function in {NAND} (Figure 2.15) is explained as follows:

Figure 2.15: Arranging NAND into AND

Equivalence among logic functions becomes important in practice, because one type of logic gate may have better characteristics than another.