Boolean Algebra and Logic Gates

Boolean Algebra & Logic Gates

• Boolean algebra deals with binary numbers and variables.
• It is also known as Binary Algebra or Logical Algebra.
• George Boole developed this algebra in 1854.
• Variables in Boolean algebra are called Boolean variables.
• Primary goal of digital circuits: simplify complex logical expressions while maintaining results under all conditions.
• Simplified expressions lead to smaller circuits, which saves costs, reduces gate needs, power, and space.
• Boolean algebra serves as a tool to reduce logical expressions.
• Boolean algebra rules are simple, straightforward, and applicable to any logical expression.
• Resulting expressions can be tested for validity using a Truth Table.
• Boolean algebra is an algebraic structure defined with a set of elements B(1,0) and two binary operators (+, .).

Boolean Algebra Rules

• Closure with respect to operator +: x+y=z, where z belongs to B.
• Closure with respect to operator (.): x.y=z, where z belongs to B.
• Identity element for + is 0: x+0 = 0+x = x.
• Identity element for (.) is 1: x.1 = 1.x = x.
• Commutative law for +: x+y = y+x.
• Commutative law for (.): x.y = y.x.
• Distributive over (+): x.(y+z) = x.y + x.z.
• Distributive over (.): x+(y.z) = (x+y).(x+z).
• Complement law: For every x in B, there exists x' such that x.x' = 0 and x + x' = 1.
• There exist at least two elements x, y belonging to B such that x ≠ y.
• Two-valued Boolean algebra is defined on a set B={0,1} with operators (+) and (.).

Truth Tables Explained

• The result of each operation in the tables is either 0 or 1; 1 and 0 belong to set B.
• From the truth table, the identity element for (+) is 0, and the identity element for (.) is 1.
• Commutative law is evident from the symmetry of the binary operators table.
• Distributive Law: x.(y+z) = x.y + x.z.
• Complementing Table: x + x' = 1 (i.e., 1+0=1) and x . x' = 0 (i.e., 1.0=0).

Boolean Postulates

• Considers binary numbers 0 and 1, Boolean variable x, and its complement x'.
• A literal is either a Boolean variable or its complement.
• Four possible logical OR operations with literals and binary numbers:
  • x+0=x
  • x+1=1
  • x+x=x
  • x + x' = 1
• Four possible logical AND operations with literals and binary numbers:
  • x.1 = x
  • x.0 = 0
  • x.x = x
  • x.x' = 0
• These postulates can be verified by substituting the Boolean variable with '0' or '1'.
• Double Negation: The double complement of a Boolean variable equals the variable itself (x" = x).

Basic Laws & Properties

• Annulment law: A variable ANDed with 0 is 0; a variable ORed with 1 is 1.
  • A.0 = 0
  • A+1 = 1
• Identity law: A variable remains unchanged when ORed with '0' or ANDed with '1'.
  • A.1 = A
  • A+0 = A
• Idempotent law: A variable remains unchanged when ORed or ANDed with itself.
  • A+A = A
  • A.A = A
• Complement law: Adding a complement to a variable gives one; multiplying gives '0'.
  • A + A' = 1
  • A.A' = 0
• Double negation law: a variable with two negations cancels out resulting in the original variable ((A)')'=A
• Commutative law: Variable order doesn't matter.
  • A+B = B+A
  • A.B = B.A
• Associative law: Operation order doesn't matter for same-priority variables.
  • A+(B+C) = (A+B)+C
  • A.(B.C) = (A.B).C
• Distributive law governs opening up brackets.
  • A.(B+C) = (A.B)+(A.C)
  • A+(B.C) = (A+B).(A+C)
• Absorption law: Involves absorbing similar variables.
  • A.(A+B) = A
  • A + AB = A
• De Morgan's law: AND/OR logic circuit operation is unchanged if inputs are inverted, operator changes from AND to OR, output inverts.
  • (A.B)' = A' + B'
  • (A+B)' = A'.B'

Theorems

• Principle of Duality: if operators and identity elements are interchanged, an algebraic expression remains valid, changing AND(.) to OR(+), OR(+) to AND(.), and 1's to 0's, and vice versa.
• 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: Associate Law (a) (A + B) + C = A + (B + C), (b) (A B) C = A (B C)
• Postulate 4: Distributive Law (a) A (B + C) = A B + A C, (b) A + (B C) = (A + B) (A + C)
• Theorem 5: De Morgan's Theorem (a) (A+B)'= A'B', (b) (AB)'= A'+ B'
• Theorem 6: Absorption (a) A + A B = A, (b) A (A + B) = A

Theorem Proofs

• Theorem 1(a): x + x = x
  • Justification uses identity element and complement properties.
• Theorem 1(b): x.x = x
  • Justification utilizes identity element and complement properties.
• Theorem 2(a) : x+1=x
  • Justification applies the distributive law and complement properties.
• Theorem 2(b): x.0=0
  • Justification applies the complement and identity postulates.
• Theorem 6 (a): x+xy=x
  • Justification applies the distributive law and identity postulates.
• Theorem 6 (b): x(x+y)=x
  • Justification applies the distributive law and identity postulates.

De Morgan's Theorem

• Proposed by De Morgan, plays a key role in Boolean algebra.
• Verifies the equivalence 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 of the variables.
• The complement of two or more ANDed variables equals te 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 of the variables.
• The complement of two or more ORed variables equals the AND of the complements of the individual variables.
• Formula: (X + Y)'=(XY)'

Boolean Functions

• Operations of binary variables described using mathematical functions called Boolean functions.
• Boolean function maps set of binary input values to output values.
• It comprises binary variables, AND, OR and NOT operator.
• Boolean function f(x1,x2,x3,……,xn)=y maps input combinations to binary value y.
• A function with n input variables operates on 2n distinct values.
• The function can be described using a 2n rows and n columns truth table.
• Function f representing x.y is f(x,y)=xy, meaning f=1 if x=1 and y=1, else f=0.
• Table rows have function value equal to 1 or 0.
• Function 'f' equals the sum of all rows having a value of 1.
• A Boolean function transforms from an algebraic expression into a logic diagram composed of AND, OR, and NOT gates.
• When implemented with logic gates, each literal designates an input to a gate, and each term is implemented with a logic gate.

Other Information

• Additional laws such as AND Gate, OR Gate, NOR Gate, NAND Gate and associated exercises are ommitted as per the instructions in the prompt.