Boolean Algebra

Boolean Algebra

• binary algebra
• operations
  • • = multiplication
    • 0 • 1 = 0
    • 0 • 0 = 0
    • 1 • 1 = 1
  • • = addition
      • 1 + 1 = 1
      • 1 + 0 = 1
  • complement (reversion)
    • 
  • = –> used to denotate logical equivalence
    • 
      • 
      • de morgan's law can be used to eliminate addition operations
  • is functionally complete if any Boolean function can be expressed using only operations from the set.
    • set
• order of operations
  • 

Boolean Functions

• 
• boolean expressions
  • 
  • going from output to function
    • 
    • the result from the function is an example of a boolean expression
• duality principle
  • 
• literal
  • a Boolean variable or the complement of a Boolean variable (for example, x or x).
    • 
• minterm
  • the product of n literals, with exactly one literal per variable.
  • can't repeat the variables
  • In a Boolean function whose input variables are v1, v2,...,vk, a minterm is a product of literals u1u2...uk such that each uj is either vj or v`j
    • xyz and xyz are examples of minterms for a Boolean function with input variables x, y, and z. However, yz is not a minterm because variable x is missing from the term.
• maxterm
  • the sum of n literals, with exactly one literal per variable
  • can't repeat the varibles

Disjunctive/Conjunctive Normal Forms

• just to standardadize
• disjunctive normal form (DNF)
  • if x +(or) y +(or) z are true = true
  • a sum of products of literals
    • 
    • In a DNF expression, multiplication can only be applied to literals
    • A term in a DNF expression can be a single literal
      • 
    • more than one expression can correspond to the same function
      • 
• conjunctive normal form (CNF)
  • if a x(and) b x(and) c are true -> true
  • a product of sums of literals
    • 
  • each term in the product that is a sum of literals is called a clause
    • 
  • addition can only be applied to literals
  • can not contain an expression of the form xy + z because xy is not a literal.

Functional Completeness

• A set of operations is functionally complete if any Boolean function can be expressed using only operations from the set
  • set
• if addition/multiplication is hard to implement in the hardware, we can express the function using only
  • 1- set
  • 2- set
  • can't have one with complement tho(x' cant be computed)
  • through De Morgan's law
    • 
    • 
    • (taking out the + or x)
    • while still having the function be complete
• NAND/NOR are functionally complete, while only being one operation
  • NAND = not and, symbol ↑.
    • 
    • getting complement
      • 
      • 
  • NOR = not or, symbol ↓.
    • 
    • (x↓y)' = x + y
    • a' = a↓a
    • getting complement
      • 0↓0 = 1
      • 1↓1 = 0
      • x↓x = x'
      • x + y = (x↓y)↓(x↓y)

Boolean Satisfiability

• The Boolean satisfiability problem (called SAT for short)
  • can be used on a bunch of subjects, where you only need to find one solution
    • schedule of classes (where they conflict with each other) -> only need to find one possible schedule, and when its in a university level, needs an algorithm to solve it
      • an algorithm that only evaluates to 1 when the variables correspond to a valid schedule with no conflicts
• if an expression never evaluates to 1, with any input variables -> unsatisfiable
  • if theres at least 1 set of inputs that evaluate to 1, its satisfiable
  • 
• in DNF form ( xyz + yz + xzz')
  • The formula is satisfiable if and only if there is a term that does not contain a variable and its negation
    • 
      • theres not second w,x,y or z with a '
• in CNF form ((x+y+z)(x+z))
  • all the clauses () have to be satisfied, not only one like in the DNF (much more difficult to prove)
    • 
• making an expression to model the scheduling problem
  • CNF that checks if all classes are present and if no conflicts happen
    • 
  • 
    • first term gives false if class B is not assigned
    • second term gives false if class b is assigned to both periods
  • 
    • if B and E are assigned to the same period -> false

Gates and Circuits

• circuits used in eletronic devices are built from eletrical devices called gates.
• gates receives x boolean input values and gives an output based on that
  • gates = implement a simple boolean function
    • 
  • AND gate = multiplication
    • 
  • OR gate = addition
    • 
  • inverter = complement
    • 
  • classes of circuits
    • combinatorial
      • can't store information over time
      • computes a boolean function
        • can find a boolean expression from it
          • 
        • and vice-versa
          • 
  • designing circuits
    • 1- build input/output table with desired output for each combination of inputs
    • 2- write boolean expression for the table's function
    • 3- construct the digital circuit
      • not the most efficient circuit most of the times