Boolean Algebra: Concepts and Rules

Boolean Algebra Basics

• Boolean algebra deals with binary numbers and variables and is also known as Binary Algebra or logical Algebra
• George Boole developed this algebra in 1854
• Variables in Boolean algebra are called Boolean variables
• Boolean algebra helps simplify digital circuits by reducing complex logical expressions
• The simplified expressions can be tested using a Truth Table
• An algebraic structure defined on a set of elements B(1,0) with two binary operators (+, .)

Rules of Boolean Algebra

• Closure with respect to operators + and .:
  • x+y=z; where z belongs to set B
  • x.y=z; where z belongs to set B
• Identity Element:
  • With respect to +: x+0=0+x=x
  • With respect to .: x.1=1.x=x
• Commutative Law:
  • With respect to +: x+y=y+x
  • With respect to .: x.y=y.x
• Distributive Law:
  • Over (+): x.(y+z) = x.y + x.z
  • Over (.): x+(y.z) = (x+y).(x+z)
• Complement Law: For every element x, there exists a complement x' such that:
  • x.x' = 0
  • x+x' = 1
• There are at least two elements x and y belonging to set B where x≠y
• Two-valued Boolean algebra is defined on a set B={0,1} with binary operators (+) and (.)

Boolean Algebra Properties

• Annulment Law:
  • A variable ANDed with 0 is 0: A.0 = 0
  • A variable ORed with 1 is 1: A+1 = 1
• Identity Law:
  • A variable ORed with 0 remains unchanged: A+0 = A
  • A variable ANDed with 1 remains unchanged: A.1 = A
• Idempotent Law:
  • A variable ORed with itself remains unchanged: A+A = A
  • A variable ANDed with itself remains unchanged: A.A = A
• Complement Law:
  • A variable ORed with its complement is 1: A+A' = 1
  • A variable ANDed with its complement is 0: A.A' = 0
• Double Negation Law: A variable with two negations equals the original variable: ((A)')' = A
• Commutative Law:
  • Order of variables does not matter: A+B = B+A and A.B = B.A
• Associative Law:
  • Order of operations does not matter for same priority variables: A+(B+C) = (A+B)+C and A.(B.C) = (A.B).C
• Distributive Law:
  • A.(B+C) = (A.B)+(A.C)
  • A+(B.C) = (A+B).(A+C)
• Absorption Law:
  • A.(A+B) = A
  • A + AB = A
• De Morgan's Law:
  • The complement of an AND is the OR of complements: (A.B)' = A' + B'
  • The complement of an OR is the AND of complements: (A+B)' = A'.B'

Duality Principle

• The principle of duality states that every algebraic expression in Boolean algebra remains valid if operators and identity elements are interchanged
• Change every AND(.) to OR(+), every OR(+) to AND(.), and all 1s to 0s and vice versa to obtain the dual of an expression

Laws and Theorems

• Postulate 2: (a) 0 + A = A; (b) 1.A = A
• Postulate 5: (a) A + A' = 1; (b) A.A' = 0
• Theorem 1 (Identity Law): (a) A + A = A; (b) A.A = A
• Theorem 2: (a) 1 + A = 1; (b) 0.A = 0
• Theorem 3 (Involution): A'' = A
• Postulate 3 (Commutative Law): (a) A + B = B + A; (b) A.B = B.A
• Theorem 4 (Associative Law): (a) (A + B) + C = A + (B + C); (b) (A.B).C = A.(B.C)
• Postulate 4 (Distributive Law): (a) A(B + C) = AB + AC; (b) A + (BC) = (A + B)(A + C)
• Theorem 5 (De Morgan's Theorem): (a) (A + B)' = A'B'; (b) (AB)' = A' + B'
• Theorem 6 (Absorption): (a) A + AB = A; (b) A(A + B) = A

De Morgan's Theorems

• Proposed by De Morgan, a mathematician familiar with Boole
• Important for Boolean algebra
• It provides mathematical verification of equivalency of NAND/negative-OR gates and NOR/negative-AND gates
• First Theorem: The complement of a product of variables equals the sum of the complements
  • The complement of two or more ANDed variables is equivalent to the OR of the complements of the individual variables.
  • Formula: (XY)' = X' + Y'
• Second Theorem: The complement of a sum of variables equals the product of the complements
  • The complement of two or more ORed variables is equivalent to the AND of the complements of the individual variables
  • Formula: (X + Y)' = X'Y'

Boolean Function

• Operations of binary variables described by mathematical functions
• Boolean function defines a mapping from binary input values to output values
• A Boolean function consists of binary variables, AND/OR operators, and the NOT operator
• A function with n input variables can operate on 2^n distinct values
• Any such function can be described by using a truth table consisting of 2n rows and n columns.
• When a Boolean function is implemented with logic gates, each literal in the function designates an input to a gate and each term is implemented with a logic gate.