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!!!