Skip to main content

Boolean Algebra


Amu_Ke_Fundye

Boolean Algebra


Boolean algebra is an algebric structure defined on a set of elements together with two binary operators (+) and (.)
  • A variable is a symbol, for example Î‘,used to represent a logical quantity, whose value can be 0 or 1.
  • The complement of a variable is the inverse of a variable and is represented by an over bar, for example image001.
  • A literal is a variable or the complement of a variable.

Closure: For any x and y in the alphabet A, x + y and x.y are also in A.

Boolean Value

The value of Boolean variable can be either 1 or 0.

Boolean Operators

There are four Boolean operators
  1. AND (∙) operator (A.B)
  2. OR (+) operator (A + B)
  3. NOT image002 operator
  4. XOR (⊕) operator image003

Operator Precedence

The operator for evaluating Boolean expression is
  1. Paranthesis
  2. NOT
  3. AND
  4. OR.

Duality

If an expression contains only the operations AND, OR and NOT. Then, the dual of that expression is obtained by replacing each AND by OR, each OR by AND, all occurrences of 1 by 0, and all occurrences of 0 by 1. Principle of duality is useful in determining the complement of a function.
Logic expression: (x •y’ •z) + (x •y •z’ ) + (y •z) + 0 ,
Duality of above logic expression is: (x + y’ + z) • (x + y + z’ ) • (y + z) • 1

Boolean Function

  • Any Boolean functions can be formed from binary variables and the Boolean operators •, +, and ‘ (for AND, OR, and NOT, respectively).
  • For a given value of variable, the function can take only one value either 0 or 1.
  • A Boolean function can be shown by a truth table. To show a function in a truth table we need a list of the 2n combinations of 1’s and 0’s of the n binary variables and a column showing the combinations for which the function is equal to 1 or 0. So, the table will have 2n rows and columns for each input variable and tile final output.
  • A function can be specified or represented in any of the following ways:
    • A truth table
    • A circuit
    • A Boolean expression
    • SOP (Sum Of Products)
    • POS (Product of Sums)
    • Canonical SOP
    • Canonical POS
  • Important Boolean operations over Boolean values:
image004

Table of Some Basic Theorems

image005

Important Theorems used in Simplification

  • NOT-Operation theorem: image006
  • AND-Operation theorem: image007
  • OR-Operation theorem: image008
  • Distribution theorem: A + BC = A (A + B)(A + C)
Note:
image009
  • Demorgan’s Theorem: image010image011
  • Transposition Theorem: (A + B) (A + C) = A + BC
  • Consensus Theorem: This theorem is used to eliminate redundant term. It is applicable only when if a boolean function contains three variables. Each variable used two times. Only one variable is complemented or uncomplemented. Then the related terms so that complemented or uncomplemented variable is the answer.
image012
Regards 
Amrut Jagdish Gupta
Labels:

Comments

Post a Comment

Popular posts from this blog

Instruction Pipelining

Amu_Ke_Fundye Instruction Pipelining Parallel processing provides simultaneous data processing tasks for the purpose of increasing the computational speed of a computer system rather than each instruction is processed sequentially, a parallel processing system is able to perform concurrent data processing to achieve faster execution time and increase throughput. There are more advantages with parallel processing but it has some issues also. Due to parallel processing, the amount of hardware increases and the cost of system increases. Parallel processing is established by distributing the data among the multiple functional units. Flynn’s Classification Flynn introduced the parallel processing classification. This classification considers the organisation of a computer system by the number of instructions and data items that are manipulated simultaneously. The sequence of instructions read from the memory constitutes an instruction stream. The operations perfo...
Post a Comment
Read more

ALU and Data Path

Amu_Ke_Fundye ALU and Data Path The CPU can be divided into a data section and a control section. The   data section , which is also called the   datapath. Datapath The registers, the ALU, and the interconnecting bus are collectively referred to as the datapath.  Each bit in datapath is functionally identical.  The datapath is capable of performing certain operations on data items. The  control section  is basically the  control unit ,  which issues control signals to the datapath . Bus : A Bus is a collection of wires or distinct lines meant to carry data, address and control information. Data Bus : it is used for transmission of data. The number of data lines corresponds to the number of bits in a word. Address Bus : it carries the address of the main memory location from where the data can be accessed. Control Bus : it is used to indicate the direction of data transfer and to coordinate the timing of ...
Post a Comment
Read more

Undecidability

Amu_Ke_Fundye Undecidability Decidable Problem If there is a Turing machine that decides the problem, called as Decidable problem. A decision problem that can be solved by an algorithm that halts on all inputs in a finite number of steps. A problem is decidable, if there is an algorithm that can answer either yes or no. A language for which membership can be decided by an algorithm that halts on all inputs in a finite number of steps. Decidable problem is also called as totally decidable problem, algorithmically solvable, recursively solvable. Undecidable Problem A problem that cannot be solved for all cases by any algorithm whatsoever. Equivalent Language cannot be recognized by a Turing machine that halts for all inputs. The following problems are undecidable problems: Halting Problem:  A halting problem is undecidable problem. There is no general method or algorithm which can solve the halting problem for all possible inputs. Emptyness Problem:...
Post a Comment
Read more