Boolean Algebra - Canonical Form

A literal is a variable or a complemented variable in Boolean algebra. A fundamental product or fundamental sum is a literal of a product or sum of two or more literals in which no two literals involve in the same variable. With the help of fundamental product or fundamental sum representing any Boolean known as Canonical form.

In a Boolean algebra, a Boolean function that is composed of standard logical operators can be expressed in a canonical form using the dual concepts of a minterms and maxterms.

In Boolean algebra, any Boolean function can be expressed in a canonical form using the dual concepts of minterms and maxterms. All logical functions are expressible in canonical form, both as a "sum of minterms" and as a "product of maxterms". This allows for greater analysis into the simplification of these functions, which is of great importance in the minimization of digital circuits.

A Boolean function expressed as a (OR) of minterms is commonly known as a "sum of products" or "SoP". Thus it is a disjunctive normal form in which only minterms are allowed as summands. Its De Morgan dual is a "product of sums" or "PoS" , which is a function expressed as a (AND) of maxterms.

Canonical and Standard forms 

Boolean functions are commonly expressed using the following forms:

• Canonical forms:
• Sum of minterms
• Product of maxterms
• Standard forms:
• • Sum of products
  • Product of sums

Represented as a sum of minterms only : f = Σ(minterms)

Represented as a product of maxterms only : f= π(maxterms)

Mineterm : A minterm is a special product of literals, in which each input variable appears exactly once. A sum of minterms corresponding to the input combination of the truth table for which the function produces a “1” output.

Maxterm : A maxterm is a sum of literals, in which each input variable appears exactly once. A product of maxterms corresponding to the input combination of the truth table for which the function produces a “0” output.

Karnaugh Map is developed by Maurice Karnaugh, an electrical engineer at Bell Labs, USA. Karnaugh Map is a Row and Column representation of a Boolean expression to reduce a term.

Pair: A pair is a group of two’s may be horizontally, vertically adjacent or end-to-end in the same row or column. The end-to-end 1’s are obtained by rolling a map.

Quad: A quad is a group of four's may be horizontally, vertically adjacent or end-to-end in the same row or column. The end-to-end 1’s are obtained by rolling a map.

Octet : A octet is a group of eight’s may be horizontally, vertically adjacent or end-to-end in the same row or column.

Overlapping Groups : If two or more groups use the same 1’s, such groups are called overlapping groups.

Redundant Groups : A redundant group whose 1’s are already used by other groups.

Rules for grouping :

1. Groups only contain only 1’s for SOP and 0's for POS.
2. No diagonals.
3. Only power of 2 number of cells in each group.
4. Groups should be as large as possible.
5. Every one must be in at least one group.
6. Groups can overlap.
7. Wrap around allowed.
8. Fewest number of groups possible.
9. Use don’t care conditions when you can and if given but group cannot made out of only don’t care conditions.

Truth Table for three literals
x	y	z	minterms (SoP)	maxterm(PoS)
0	0	0	x'y'z'	xyz
0	0	1	x'y'z	xyz'
0	1	0	x'yz'	xy'z
0	1	1	x'yz	xy'z'
1	0	0	xy'z'	x'yz
1	0	1	xy'z	x'yz'
1	1	0	xyz'	x'y'z

Rules : How to group in Karnaugh Map

Two literals Karnaugh Map

Three literals Karnaugh Map

Four literals Karnaugh Map

Grouping Rules (Two Literals)
Grouping Rules (Three Literals)
Grouping Rules    &	Map Rolling
Grouping Rules

Next time I will give some solved problems for minterms and maxterms. Also for my engineering student I will give some tips for solving the same with Quine & Mclusky methods also known as Tabulation Methods.

!!!Wish you enjoying your winter with a support of a few extra warm clothes, A Merry X'Mas and wish a Wonderful New year.!!!

Boolean Algebra and Propositional Logic

The reason of Boolean algebra is to simplify the design of a digital circuit  that designed to performs a function, this helped to minimize the number of gates or to minimize the time of the function. We already discussed the Booleans laws and some theorems for this purpose, I will give some examples.
Simplification (Using Boolean Laws)
Example 1		Example 2		Example 3
X.Y + X.Z + X.Y.Z =XY +XYZ + XZ =XY(1+Z) +XZ =XY + X =X(Y+Z)	[1+Z=1]	X.Y(X.Y+YZ) = (XY). (XY) + (XY).(YZ)  = XY + XYZ = XY(1+Z) = XY.1 = XY	[Distributive Law] [ X.X = X] [ 1 + X = 1]	= X’YZ + XY’Z’ + XY’Z + XYZ' +XYZ = X’YZ + XY’ + XY = X’YZ + X = X + YZ	[xy’ + xy = x]
Proof (Using Boolean Laws)
Example 1		Example 2		Example 3
.XY + YZ + Y'Z = XY + Z =XY + YZ + Y'Z = XY + Z(Y + Y') = XY + 1.Z = XY + Z	[ AB +AC = A(B+C)] [ A + A' = 1]  [ 1.A = A]	(X+Y)(X+Z) = X + YZ =XX + XZ + XY + YZ =X+XZ+XY+YZ =X.1 + XY + XZ + YZ =X(1+Y) + XZ + YZ =X + XZ + YZ =X(1+Z) + YZ =X+YZ	[A.(B+C)=AB + AC] [A.A = 1] [X.1 = X] [1 + A = 1] [1 + A = 1]	(X+Y)(Y+Z)(X+Z)=XY+XZ+YZ (XY + XZ + YY + YZ) (X+Z) (XY + XZ + Y (1 + Z)(X + Z) (XY + XZ + Y)(X + Z) XXY + XYZ + XXZ + XZZ + XY + YZ XY(1 + Z) + XZ + XZ + XY + YZ XY + XZ + YZ	[A(B+C) = AB + AC] [ 1 + A = 1] [ A. A = A] [ A. A = A] [ 1 + A = 1]

Proof (Using Boolean Laws)
XY + YZ + Y'Z = XY + Z										(X+Y)(X+Z) = X + YZ
X	Y	Z	Y'	XY	YZ	Y'Z	XY+YZ+Y'Z	XY+Z			X	Y	Z	X+Y	X+Z	YZ	(X+Y)(X+Z)	X+YZ
0	0	0	1	0	0	0	0	0			0	0	0	0	0	0	0	0
0	0	1	1	0	0	1	1	1			0	0	1	0	1	0	0	0
0	1	0	0	0	0	0	0	0			0	1	0	1	0	0	0	0
0	1	1	0	0	1	0	1	1			0	1	1	1	1	1	1	1
1	0	0	1	0	0	0	0	0			1	0	0	1	1	0	1	1
1	0	1	1	0	0	1	1	1			1	0	1	1	1	0	1	1
1	1	0	0	1	0	0	1	1			1	1	0	1	1	0	1	1
1	1	1	0	1	1	0	1	1			1	1	1	1	1	1	1	1

Propositional Logic
Propositional Logic are concerned with propositional (or sentential) operators which may be applied to one or more propositions giving new propositions. Propositional logic is a propositional logic whose interpretation limits the truth values of its propositions to two, usually true and false that denoted by 1 and 0.
1. NOT Operation (Inverter)		2. OR Operation (Disjunction)			3. AND Operation (Conjunction)
~p ≡ "Today is not Sunday"		Today is Sunday Or a Holiday (p ۷ q)			Today is Sunday and a Holiday (p ۸ q)
Truth Table		Truth Table			Truth Table
p	~p	p	q	p + q	p	q	p . q
T	F	T	T	T	T	T	T
F	T	T	F	T	T	F	F
		F	T	T	F	T	F
		F	F	F	F	F	F

4. IF - THEN (Conditional) Operation				4. IF AND ONLY IF (Bi-conditional) Operation
“If today is Sunday, then today is my Birthday”				“If and only if today is Sunday, then today is my Birthday”
p ≡ If today is Sunday q ≡ then today is my Birthday  If p THEN q p → q				p ≡ If and only if today is Sunday q ≡ then today is my Birthday  If  and only if p THEN q   p ↔ q
Therefore p → q ≡ p' + q				Therefore p ↔ q ≡ p . q + p' . q'
p	p'	q	p→q [ p' + q ]	p	p'	q	q'	p . q	p' . q'	p . q + p' . q'
T	F	T	T	T	F	T	F	T	F	T
T	F	F	F	T	F	F	T	F	T	F
F	T	T	T	F	T	T	F	F	T	F
F	T	F	T	F	T	F	T	F	T	T

Tautology is a statement that is always true p ۷ ~q will always be True (Negation Law) Contradiction is a statement that is always false p ۸ ~p will always be False (Negation Law)			A logical equivalence means that the two sides always have the same truth values p → q and ~q → ~p  is Logically equivalence
p	p ۷ ~q	p ۸ ~p	p	q	p ≡ q
T	T	F	F	F	T
F	T	F	F	T	T
			T	T	F
			T	T	T

Inversion: "If something is not a bird, then it is not an animal." Unlike the contrapositive, the inversion's truth value is not dependent upon whether the original proposition is true, as evidenced here. The inverse, here, is clearly not true.

Conversion: "If something is an animal, then it is a bird." The conversion is actually the contrapositive of the inversion and always has the same truth value as the inversion, which is not necessarily the same as that of the original proposition.

Contradiction: "There exists a bird that is not an animal. " If the contradiction is true, then the original proposition and, by extension, the contrapositive are untrue. Here, of course, the contradiction is untrue.

!!!Coming back with Maurice Karnaugh, I mean more with Boolean
Algebra and Karnaugh Map!!!

Logic Gates, this one total Universal.

Expressing my apology for not posting the notes in time, but it is very difficult to prepare the note in HTML format with so many diagrams. We already discussed about logic gates in previous blog and given you the idea of drawing as well as Boolean laws and theorems. Today we will look at the universal gates NAND and NOR. Any logic circuit can be built using only NAND gates, or only NOR gates. They are the only logic gate needed to build a circuit. Before that I am giving one small example of drawing logic gate
Draw a Logic diagram for following Boolean expression (x.y’)+(y’.z)	Truth Table
	x	y	z	xy'	y'z	(x.y’)+(y’.z)
	0	0	0	0	0	0
	0	0	1	0	1	1
	0	1	0	0	0	0
	0	1	1	0	0	0
	1	0	0	1	0	1
	1	0	1	1	1	1
	1	1	0	0	0	0
	1	1	1	0	0	0

Different Logic Gates using NAND and NOR Gates.
NOT using NAND :
OR using NAND
AND using NAND
NOR using NAND
NOT using NOR
OR using NOR
AND using NOR
NAND using NOR

Drawing these diagrams are very painful experience, if you find any error please inform me. My Next blog will be also about Boolean laws and algebra.

!!!Wish you all A Very Very Happy and prosperous Diwali!!!

Boolean Laws and Teorems - Go by the rule

Sorry, could not post the notes as scheduled, was little busy with other thing. Today giving some Boolean Laws and Theorems. Boolean logic was developed by an English mathematician George Boole, used to construct and solve Boolean algebra and helped to design the electrical circuits. The basic laws of Boolean algebra:
Proof (Using Truth Table)
A + A.B = A						A( A + B) = A
A	B	A.B	A+A.B				A		B	A+B	A.(A+B
0	0	0	0				0		0	0	0
0	1	0	0				0		1	1	0
1	0	0	1				1		0	1	1
1	1	1	1				1		1	1	1
Proof (Using Postulate)
If A and B  are elements of a Boolean algebra
A+A.B = A								A( A + B) = A
A.1+A.B				A.1 = A				A.A + A.B		Distributive Law
A(1 + B)				Distributive Law				A + A.B		Idempotent law
A.1				Law on the property of 1				A.1 + A.B		A.1 = A
A				A.1 = A				A(1 +  B)		A.1
								A		A
Now just tell you about principle of duality. Principle of Duality The dual of any statement in a Boolean algebra is the statement obtained by interchanging OR with AND, and simultaneously inter-changing the elements 0 and 1 in the statement.

IdentityBoolean								Dual
A + 0 = A								A.1 = A
A + 1 = 1								A.0 = 0
A + A = A								A.A=A
A + A’ = 1								A.A’ = 0
A + B = B + A								A . B = B . A
A+ B.C = (A + B)(A + C)								A(B + C) = A . B + A. C
A( A + B) = A								A+A.B=A
A + AB = A + B								A.(A+B) = A
(A+ B)’ = A’.B’								(AB)’=A’ + B’
DeMorgan’s theorems provide mathematical verification of: : 1. The equivalency of the NAND and negative-OR gates 2. The equivalency of the NOR and negative-AND gates.
(A.B)'    =		A'+B'						(A + B)'       =			A'.B'
**Change the sign and break the line.
(A.B)' = A'+B'								(A + B)' = A'.B'
A	B	A.B	(A.B)'	A'	B'	A'+B'		A	B	A+B	(A+B)'	A'	B'	A'.B'
0	0	0	1	1	1	1		0	0	0	1	1	1	1
0	1	0	1	1	0	1		0	1	1	0	1	0	0
1	0	0	1	0	1	1		1	0	1	0	0	1	0
1	1	1	0	0	0	0		1	1	1	0	0	0	0
Next time it will be time for Logic circuits using Logic Gates.
!!!Wish all of you a Shuvo Vijaya Dashami / Happy Dussera!!!

Some Logical Moments With Logic Gates

Sorry for this long break as I was away, could not post the required notes as schedule d, today we will go through basic logic gates. Logic Gates: A logic gate is an elementary digital circuit. Logic gates process signals which represent true or false. Normally the positive supply voltage +Vs represents true or high and 0V represents false or low. Truth Table: Truth tables are used to help show the function of a logic gate. Number of terms depend upon the number of Input. It will be always 2n,where 'N' is the numbers of Inputs. AND gate The AND gate is an electronic circuit that gives a high output(1) if all its inputs are high. A dot (.) is used to show the AND operation i.e. A.B.
Truth Table				AND Gate
A	B	A.B
0	0	0
0	1	0
1	0	0
1	1	1
OR Gate The output is true if one of input is true or both of them are true. An OR gate can have two or more inputs.
Truth Table				OR Gate
A	B	A+B
0	0	0
0	1	1
1	0	1
1	1	1
NOT gate (inverter) The output is true when the input A is NOT true, the output is the inverse of the input. A NOT gate can only have one input. A NOT gate is also called an inverter.
Truth Table				NOT Gate
	A	Ā
	0	1
	1	0
NAND Gate: The NAND gate operates as an AND with NOT gate to follow. It acts in the manner of the logical operation AND followed by negation. The output is false if both inputs are true. Otherwise, the output is true.
Truth Table				NAND Gate
A	B	(A.B)'
0	0	1
0	1	1
1	0	1
1	1	0
NOR Gate: The NOR gate operates as an OR with NOT gate to follow. It acts in the manner of the logical operation Or followed by negation. The output is true if both inputs are false, otherwise, the output is false.
Truth Table				NOR Gate
A	B	(A+B)'
0	0	0
0	1	0
1	0	0
1	1	1
XOR Gate: The 'Exclusive-OR' gate is a circuit which will give a high output if either, but no t both, of its two inputs are high. While writing the truth table using more than three input remember when numbers of 1 is odd in input values then output will be 1. An encircled plus sign Å is used to show the XOR operation. The Boolean Expression : A'B + B'A
Truth Table				XOR Gate
A	B	A'B + B'A
0	0	0
0	1	1
1	0	1
1	1	0
		Diagram Using Logic Gates
XNOR Gate: The XNOR [Exclusive-NOR] gate is a XOR gate followed by an inverter. Its output is true if the inputs are the same, and false if the inputs are different. The Boolean Expression : (A'B + B'A)'
Truth Table				XNOR Gate
A	B	(A'B + B'A)'
0	0	1
0	1	0
1	0	0
1	1	1

Next time I will come up with Boolean Laws and Theorems.

!!!Time to say Bye, today we move to Karnataka and say Hogibitt Barthene Or Olleyadu Matthe Siguva.!!!

Addition & Subtraction - Other Number System

Subtraction of Octal number, Hexadecimal and Decimal can be done using compliments too. Therefore, a few examples are given below for Octal - 7 and 8 compliment, Hexadecimal - 15 and 16 compliments and for Decimal - 9 and 10 compliments.

---

Octal Number

Example : Using 7 Compliments

(1546)₈ - (467)₈


Minuend : 1546 and Subtrahend : 467. Minuend contain 4 digits where Subtrahend having 3, so add a leading 0 to Subtrahend 0467. Now 7'th compliment mean subtract the Subtrahend from 7's.


  7 7 7 7
  0 4 6 7
-------------
  7 3 1 0
-------------

Now add the Subtrahend to the minuend

   1
   1 5 4 6
+ 7 3 1 0
-------------
1 1 0 5 6         (Discard the Carry [1])
-------------
    1 0 5 6
            1  ( Adding Carry digits [Refer to Binary subtraction])
-------------
    1 0 5 7

Result of : (1546)₈ - (467)₈ = (1057)₈

---

Example : Using 8 Compliments

(1546)₈ - (467)₈

Minuend : 1546 and Subtrahend : 467. Minuend contain 4 digits where Subtrahend having 3, so add a leading 0 to Subtrahend 0467. Now 7'th compliment mean <> subtract the Subtrahend from 7's.

  7 7 7 7
  0 4 6 7
-------------
  7 3 1 0
+        1     (Add one to the 7 compliment)
-------------
  7 3 1 1    Now add the Subtrahend to the minuend
-------------  

           1
   1 5 4 6
+ 7 3 1 1
-------------
1  1 0 5 7  (discard the Carry digits)
-------------

Result of : (1546)₈ - (467)₈ = (1057)₈

---

Hexadecimal Number

Subtraction of Hexadecimal number can be done with with 15 or 16 compliments

Example : Using 15 Compliments

(15CB)₁₆ - (2BC)₁₆ = 1 5 12 11 - 2 11 12

Minuend : 15CB and Subtrahend : 2BC Minuend contain 4 digits where Subtrahend having 3, so add a leading 0 to Subtrahend 0 2 11 12. Now 15'th compliment mean  subtract the Subtrahend from 15's.

15 15 15 15
  0   2 11 12
-------------
 15 13  4  3    Now add the Subtrahend to the minuend
-------------

1 1
   1  5 12  11
 15 13   4   3
---------------
1 1 3 0 14
              1 ( Remove the extra carry digits and add it to the remainder)
-------------
1 3 0 15 = 130F

Result of : (15CB)₁₆ - (2BC)₁₆ = (130F)₁₆

---

Example : Using 16 Compliments

(15CB)₁₆ - (2BC)₁₆ = 1 5 12 11 - 2 11 12

Minuend : 15CB and Subtrahend : 2BC Minuend contain 4 digits where Subtrahend having 3, so add a leading 0 to Subtrahend 0 2 11 12. Now 15'th compliment mean subtract the Subtrahend from 15's.

15 15 15 15
  0   2 11  12
---------------
 15 13  4   3
+               1 (Add 1 [16 Compliment])
---------------
 15 13  4  4  Now add the Subtrahend to the minuend
---------------
  1   1
  1   5 12 11
15 13  4    4
--------------
1 1  3   0  15 ( Discard the Carry digit)
--------------
1 3 0 15 = 130F

Result of : (15CB)₁₆ - (2BC)₁₆ = (130F)₁₆

---

Decimal Number

We can do it for our (yes our) Decimal number system too. Subtraction of decimal number can be done with with 9 or 10 compliments

Example : Using 9 Compliments

(1497)₁₀ - (879)₁₀

Minuend : 1497 and Subtrahend : 879 Minuend contain 4 digits where Subtrahend having 3, so add a leading 0 to Subtrahend 0879 . Now 9'th compliment mean subtract the Subtrahend from 9's.

 9 9 9 9
 0 8 7 9
----------
 9 1 2 0                 Now add the Subtrahend to the minuend
----------
     1
 1  4  9  7
 9  1  2  0
--------------
1 0 6 1 7
            1      ( Remove the extra carry digits and add it to the remainder) +1
---------------
6 1 8

Result of : (1497)₁₀ - (879)₁₀=(618)₁₀

---

Example : Using 10 Compliments

(1497)₁₀ - (879)₁₀

Minuend : 1497 and Subtrahend : 879 Minuend contain 4 digits where Subtrahend having 3, so add a leading 0 to Subtrahend 0879 . Now 9'th compliment mean subtract the Subtrahend from 9's.

  9 9 9 9
  0 8 7 9
----------
  9 1 2 0       (add 1 to make it 10 compliment)
        + 1
----------
  9 1 2 1        Now add the Subtrahend to the minuend
----------

      1
   1 4 9 7
   9 1 2 1
--------------
1 0 6 1 8      (Discard the carry digits)
-------------
      6 1 8 
-------------

Result of : (1497)₁₀ - (879)₁₀= (618)₁₀

---

We yet to finish with number system, but promise you, next one will be the last
in these series!.