Boolean Algebra

• George Boole published the book “Mathematical Analysis of Logic” paving the way for a systematical and formal proof of finding the “truth”
• Truth Tables can be used to prove the properties of Boolean Algebra
• Transistors

  • Control flow of electrical signals
  • Takes “On” and “Off” as inputs
• George Boole attempted to formalize the proof of logical statements instead of being grounded on philosophy
• A Boolean Function is a way to express the logical relationship between binary variables and is evaluated by determining the consequent binary value of the expression for all possible values of the variables
• Properties of Boolean Algebra

  1. Postulate 1: 𝑥 + 0 = 𝑥, 𝑥 ⋅ 1 = 𝑥

  2. Postulate 2: 𝑥 + 𝑥′ = 1, 𝑥 ⋅ 𝑥′ = 0

  3. Postulate 3 (Commutative Prop.): 𝑥 + 𝑦 = 𝑦 + x, 𝑥 ⋅ 𝑦 = 𝑦 ⋅ x

  4. Postulate 4 (Distributive Prop.): 𝑥(𝑦 + 𝑧) = 𝑥𝑦 + 𝑥𝑧, 𝑥(𝑦𝑧) = (𝑥+𝑦)(𝑥𝑧)
• Properties of Boolean Algebra

  • Addition
  • Multiplication
• Computers mainly use transistors
• The properties of Boolean Algebra can be proven using traditional algebra using postulates as assumptions
• Logic Gates are used in Boolean functions
• A Boolean Function is a function expressed in terms of binary variables, the constants 0 and 1, and any of the logic operators (NOT / OR / AND)
• Boolean Algebra was developed by George Boole
• Boolean Algebra was designed as a mathematical study that uses truth values as inputs
• Transistors can be used with the same fundamentals as Boolean Algebra which uses only two values
• Boolean Algebra deals with binary numbers and logic operators
• Boolean Functions are represented using truth tables consisting of 2𝑛 rows considering all possible combinations of truth values for the 𝑛 variables
• Properties of Boolean Algebra

  1. Theorem 1: 𝑥 + 𝑥 = x, 𝑥 ⋅ 𝑥 = x

  2. Theorem 2: 𝑥 + 1 = 1, 𝑥 ⋅ 0 = 0

  3. Theorem 3 (Involution Prop.): (𝑥′)′ = 𝑥

  4. Theorem 4 (Associative Prop.): 𝑥 + (𝑦 + 𝑧) = (𝑥 + 𝑦) + z, 𝑥(𝑦𝑧) = (𝑥𝑦)z

  5. Theorem 5 (De Morgan’s Law): (𝑥 + 𝑦)′ = 𝑥′𝑦′, (𝑥𝑦)′ = 𝑥′ + 𝑦′

  6. Theorem 6 (Absorption Law): 𝑥 + 𝑥𝑦 = 𝑥, 𝑥(𝑥 + 𝑦) = 𝑥
• Duality


  • The dual of a Boolean expression is obtained by exchanging an OR by an AND (or vice versa) and a “1” by “0” (or vice versa)
  • The dual of any property of Boolean functions also holds
• Function Complements


  • The complement of a function is defined to be the function whose binary values are switched from “1” to “0” and vice versa
  • Algebraically, the complement of a function can commonly be obtained using DeMorgan’s Law
• Example

  • 𝐹1 = 𝑥 + 𝑦′z
• Logic Gates


  • Electronic circuits that operate on one or more input signals to produce an output signal
  • Can be expressed as a circuit diagram using logic gates
  • Graphically represented using appropriate symbols
• Boolean Algebra Properties

  • “literals” are the variables in a single term of a Boolean function, either in its complement or uncomplemented form
  • Simplification of functions with multiple literals can be simplified by methods that will be discussed later in the semester
• Examples of Duality


  • Commutative Property
  • Distributive Property
• Algebraic Manipulation

  • Boolean functions and their algebraic expressions are directly correlated to the complexity of an underlying circuit
  • The aim is to make a system (or a circuit) as simple as possible
  • Expressions can be manipulated to simplify them using known properties of Boolean functions
• Boolean Functions

  1. Represented using truth tables

  2. Consists of 2𝑛 rows

  3. Considers all possible combination of truth values for the 𝑛 variables
• Operation

  • Logic Gate
  • NOT
  • OR
  • AND