Boolean Algebra and Logic Gates PDF

UNIT 3: BOOLEAN ALGEBRA 1 INTRODUCTION  The Boolean Algebra is a convenient and systematic method of expressing and analyzing the operation of logic circuits.  It was introduced by an English mathematician George Boole in1850s....

UNIT 3: BOOLEAN ALGEBRA 1 INTRODUCTION  The Boolean Algebra is a convenient and systematic method of expressing and analyzing the operation of logic circuits.  It was introduced by an English mathematician George Boole in1850s.  Claude Shanon was the first person who worked on Boolean algebra to design switching circuits in 1930s that became the foundation of computer logic and design.  Boolean algebra provides operations and rules for working with only two values 0 and 1 (True and False).  As the Boolean algebra allows things to be mapped into bits and bytes, it has applications in Telephone switching circuits, Computer hardware and software and electronics. APPLICATIONS OF BOOLEAN ALGEBRA IN COMPUTER Digital Circuits (Logic Gates) Boolean algebra helps design digital circuits using logic gates like AND, OR, and NOT. 2. Simplifying Complex Circuits Boolean algebra is used to simplify complex logic circuits. This makes the circuits smaller, faster, and cheaper to build. 3. Binary Arithmetic Computers work with binary numbers (0s and 1s). Boolean algebra helps in designing circuits for operations like addition, subtraction, multiplication, etc. Example: A half-adder circuit adds two binary numbers (like 1 + 0). 4. Control Systems in Computers Boolean algebra is used to design control systems that direct how different parts of a computer work together (like memory, CPU, input/output). For example, it controls when to turn a system "on" or "off" based on certain conditions. 5. Memory & Storage In memory circuits (like RAM), Boolean algebra helps organize how data is stored and accessed. It’s also used to design flip-flops (basic memory units) that remember information like a 1 or 0. 6. Error Detection and Correction Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 2 Boolean algebra is used in parity checkers and error-correcting codes to detect and fix errors in data transmission. Example: Parity bits are used to check if the data has been transmitted correctly. 7. Multiplexers & Demultiplexers Multiplexers (MUX) use Boolean algebra to select one of many inputs and send it to the output. Demultiplexers (DEMUX) do the reverse, sending one input to one of many outputs. 8. Conditional Statements in Programming In programming, if-else statements can be seen as Boolean expressions. They check if a condition is true or false to decide what action to take. Example: if (x > 10) checks if the value of x is greater than 10. 9. Search Algorithms Boolean algebra is used in search algorithms to filter and find specific data. Example: Searching for items that match certain conditions (like AND search: find records where "age > 30" AND "location = NY"). 10. Building Efficient Software Boolean expressions help optimize code, reducing the number of conditions needed for tasks like decision-making and filtering data. BASIC CONCEPTS OF BOOLEAN ALGEBRA: Boolean Algebra is made up of:  Elements (Variables or Constants) with values either 0 or 1.  Operators (AND, OR and NOT)  Truth Table 1. BOOLEAN VARIABLE AND CONSTANT BOOLEAN VARIABLE: A Boolean variable is a symbol (capital letter A, B … or small letter a, b, x, y, z) used to represent a logical quantity. A Boolean variable can hold one of two values: true or false. It's used in programming to represent conditions or binary states, often in decision-making or control flow. CONSTANT: Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 3 Boolean constant is a single digit binary value 0 or 1. A Boolean constant represents a fixed value of true or false in programming. It is used directly in expressions or assignments to simplify code and clarify logic. COMPLEMENT: The complement is the inverse of variable, and it is indicated by a bar over the variable. If x=0, x’=1 If x=1, x’=0 2. TRUTH TABLE: The truth table is defined as the systematic listing of the values of dependent variables in terms of all possible values of independent variables. The truth table represents the condition of input and output circuits involving two or more variables. The number of columns in the table depends on the number of variables involved in the function. For n variables in function, there will be 2n possible combinations. 3. LOGICAL OPERATORS: Boolean operators are used to manipulate the values of Boolean variables. There are three fundamental logical operators: AND, OR & NOT Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 4 AND: This operation is represented by a dot “.” or absence of operator and this operator is the logical multiplication. It is defined as: “listing all possible combinations of independent variables lets say A and B and the resulting value of dependent variable C in the equation A.B=C” It is used to find commonality between two conditions. Symbol && or simply AND Example: In programming: if(a>b && b>c) printf(“a is largest number”); in real life: I will go for picnic if weather is sunny and I have a day off The AND operator only produces 1 when all independent variables values are 1, otherwise it produces 0. OR: This operator is represented by “+” and it is called logical addition. It is defined as: “listing all possible values of independent variables A and B and the resulting value of dependent variable C in the equation A+B=C” It is used to find inclusivity or flexibility between two conditions. Symbol II or OR Example: if (temperature < 0 || temperature > 40) printf("Warning: Temperature is out of the safe range.\n"); I will order pizza OR cook dinner (one condition must be true otherwise you will stay hungry. Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 5 The OR operator only produces 0 when the values of all independent variables are 0, otherwise it produces 1. NOT: The NOT operator is represented by a prime or bar over the variable and it is the logical negation or complement. It is used to negate a condition. Symbol ! or NOT Example: if (!(x > 10)) printf("x is not greater than 10.\n"); I will Not go outside if it rains. Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 6 BOOLEAN LAWS AND THEOREMS BOOLEAN EXPRESSION AXIOMS/LAW DESCRIPTION Identity law Sum (OR) of anything with 0 or product (AND) of anything with 1 is the same. Commutative The order in which variables are Ored or ANDed makes no difference. Order of variables can be reversed. Distributive law ORing two or more variables & ANDing the result with a single variable is equals to the ANDing the single variable with each of the two or more variables and then ORing the products. Complement law The sum of the Boolean variable with its complement or the product of Boolean variable with its complement results into identity. Idempotent law Sum or product of a Boolean variable with itself results the Boolean variable itself. Null element For any value of a Boolean variable, the sum of variable and 1 always results 1 and product of variable and 0 always results 0. Involution/ Complementing the variable twice or any Double negation even number of times always results the law variable itself. Associative law When ORing or ANDing more than two variables, the result is same regardless of grouping of variables. Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 7 DE MORGAN’S THEOREM: Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 8 LOGIC GATES: A logic gate is a hardware component that acts as a building block for digital circuit. It performs basic logic functions. There are seven logic gates:  AND  OR  NOT  NAND  NOR  XOR  XNOR Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 9 Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 10 XNOR Gate (Exclusive NOR) A⊙B=AB+A’B’ Operation: The output is 1 if both inputs are the same (either both 0 or both 1). It is the negation of the XOR gate. Summary of Logic Gate Functions: AND: True if both inputs are true. OR: True if at least one input is true. NOT: Inverts the input. NAND: True unless both inputs are true (negation of AND). NOR: True only if both inputs are false (negation of OR). XOR: True if inputs are different. XNOR: True if inputs are the same (negation of XOR). Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 11 Applications of Logic Gates: Combinational Logic Circuits: Used to design circuits like adders, multiplexers, and arithmetic logic units (ALUs). Control Systems: Used in digital systems for controlling logic flow. Microprocessors and Memory: Logic gates form the basis of arithmetic and logic operations in CPUs and other processing units. By combining these basic gates in various ways, more complex operations can be implemented, which form the core of digital electronics and computation. Boolean Expression Definition A Boolean expression is a mathematical expression that uses Boolean variables, constants, and operators to describe a logical relationship. The variables in a Boolean expression can only take one of two values: true (1) or false (0). Boolean expressions are the foundation of digital logic, which is used in computer systems, circuits, and logic design. Boolean expressions can be represented in following different forms: SOP (Sum of Products): SOP is a Boolean expression written as an OR (sum) of multiple ANDed terms (products). Each product term is a combination of variables, either in their normal or complemented form, and corresponds to rows in the truth table where the output is 1. In an SOP expression, you combine multiple AND terms (called "products") together using the OR operator (called "sum"). Each AND term is formed by variables or their complements. These terms correspond to rows in the truth table where the output of the function is 1. Example: If the output of the Boolean function is 1 in a certain row of the truth table, then the corresponding AND term for that row is included in the sum of products (SOP) expression. When a Boolean expression is expressed in SOP form then each term of the expression is called minterm. A product term where all the variables appear in their true or complemented form, representing one specific combination of inputs where the output is 1 is called a minterms and are represented as mi where 1=0 to 2n-1. Where n is the no. of variables. For 2 variables there will be 22-1=4 minterms m0, m1, m2, m3. Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 12 A B 0 0 0 1 1 0 1 1 m0=A’B’, m1=A’B, m2=AB’, m3=AB POS (Product of Sums): POS is a Boolean expression written as an AND (product) of multiple ORed terms (sums). Each sum term is a combination of variables, either in their normal or complemented form, and corresponds to rows in the truth table where the output is 0. Explanation: In a POS expression, you combine multiple OR terms (called "sums") together using the AND operator (called "product"). Each OR term is made from variables or their complements, and these terms correspond to rows in the truth table where the output is 0. Example: If the output is 0 in a certain row of the truth table, then the corresponding OR term for that row is included in the product of sums (POS) expression. When the Boolean expression is in standard POS form then each term is called a maxterm. A sum term where all the variables appear in true or complemented form representing one specific combination of inputs where the output is 0 then the term is called a Maxterm represented by Mi. A B 0 0 0 1 1 0 1 1 M0=A+B, M1=A+B’, M2=A’+B, M3-A’+B’ Amna Vighio | 12/10/2024  UNIT 3: BOOLEAN ALGEBRA 13 KARNAUGH MAP: A Karnaugh map or K map is a simple table used to simplify Boolean algebra expressions. It makes complex equations easier and reduces the logic gates needed in the circuit design. The number of cells in k-map is equal to 2n where the n is the number of variables involved in the map. Suppose F=A’B+AB A B A’ A’B AB F=A’B+AB 0 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 0 1 1 Filling the k-map in cells where F=1, mark 1 , where F=0, mark 0 B 0 1 A 0 1 0 1 0 1 The group represents B=1, as B is the same in both rows and A doesn’t matter there. Therefore F=B. The same expression can be simplified the boolean laws as: F=A’B+AB F=B(A’+A) From identity law we have A’+A=1 Therefore F=B*1 F=B Amna Vighio | 12/10/2024