Boolean Logic and Circuits Slides PDF

Boolean Logic, Circuits, and Compound Conditions Mark Polak Binary Number and Boolean Values Computers are digital devices, meaning they operate with discrete and finite values. Computer circuits are built using transistors that have two states: on and off. Computers are based...

Boolean Logic, Circuits, and Compound Conditions Mark Polak Binary Number and Boolean Values Computers are digital devices, meaning they operate with discrete and finite values. Computer circuits are built using transistors that have two states: on and off. Computers are based on the binary number system, which uses only two digits: 0 and 1. In digital electronics, 0 is typically represented by 0 Volts (off), and 1 by +5 Volts (on). 0 and 1 can also be associated with Boolean values of False and True. Binary numbers map perfectly to these states, with 0 representing off and 1 representing on. This binary representation enables the design and construction of digital circuits. With only two digits, it is easier to distinguish between on/off states, reducing errors and noise interference. Binary Number and Logic Gates By utilizing these binary values and manipulating voltage levels, digital circuits enable the processing and transmission of information with high accuracy, reliability, and efficiency, forming the foundation of modern computing systems. Circuits are collections of logical gates. Logic gates are fundamental building blocks of digital circuits. They are electronic devices that operate on binary inputs (0s and 1s) to produce a binary output. They enable the processing and manipulation of binary information. Notation 0 and 1: These notations are commonly used in digital electronics and computer science contexts to represent binary values. "0" typically represents a logical low or false state, while "1" represents a logical high or true state. False and True: These notations are commonly used in programming languages and Boolean logic to represent logical values. "False" represents a false or negative state, while "True" represents a true or positive state. LOW and HIGH: These notations are often used in electronics and microcontroller programming. "LOW" typically corresponds to a voltage level close to 0V or a logical low state, while "HIGH" corresponds to a voltage level close to the supply voltage (e.g., 5V or 3.3V) or a logical high state. Fundamental (or Basic) Logic Gates The fundamental logic gates are: AND gate: The output is HIGH (+5 volts) or 1 only if both inputs are HIGH (1). OR gate: The output is HIGH (1) if at least one of the inputs is HIGH (1). NOT gate (also known as an inverter): The output is the opposite of the input. If the input is HIGH (1), the output is LOW (0), and vice versa. Note: All other logic gates can be created with these 3 basic gates. Representing Logic Statements or Circuits We have 3 different representations: Formula (ex. using and, or, not…) Circuit Diagram: Made up of gates. Truth Table: Defines the output for all possible input values. AND Both inputs A and B must be True for the output of A and B to be True. If either input is False, the output will be False. Formula: A and B , A ∧ B, A*B Gate representation: Truth Table: A B Q A B A and B 0 0 0 False False False 0 1 0 False True False 1 0 0 True False False 1 1 1 True True True OR If at least one of the inputs is True, the output of A or B will be True. Formula: A or B , A ∨ B, A+B Gate representation: Truth Table: A B Q A B A and B 0 0 0 False False False 0 1 1 False True True 1 0 1 True False True 1 1 1 True True True NOT The NOT operator inverts the input. If input is False, the output will be True. If input is True, the output will be False. Formula: not A , ~A , A’, Gate representation: Truth Table: A Q A NOT A 0 1 False True 1 0 True False Exclusive OR (XOR) The XOR tests for inequality. When both inputs are the same, the output is False. When the inputs are different, the output is True. Formula: A XOR B, P⊕Q Gate representation: Truth Table: A B Q A B A and B 0 0 0 False False False 0 1 1 False True True 1 0 1 True False True 1 1 0 True True False Exclusive OR (XOR) Is XOR a fundamental logic gate? XOR implemented with AND, OR, and NOT gates: Properties of Boolean Operators Commutativity: Both the AND and OR operators are commutative, meaning the order of inputs does not affect the result. A AND B is the same as B AND A ; A OR B is the same as B OR A A*B = B*A ; A+B = B+A Associativity: Both the AND and OR operators are associative, meaning the grouping of inputs does not affect the result. (A AND B) AND C is the same as A AND (B AND C) (A*B)*C = A*(B*C) Distributivity: The AND and OR operators follow the distributive property, allowing simplification of complex expressions. A AND (B OR C) is the same as (A AND B) OR (A AND C)) A*(B+C) = (A*B) + (A*C) Precedence of Logical Operators The precedence of logical operators determines the order in which they are evaluated in an expression. In general, the precedence of logical operators is as follows: 1. NOT (highest precedence) 2. AND 3. OR (lowest precedence) This means that NOT is evaluated first, followed by AND, and then OR. However, it's recommended to use parentheses to explicitly specify the desired order of evaluation to avoid any ambiguity. De Morgan's Laws De Morgan's Laws state that the negation of a logical expression involving AND or OR can be obtained by negating the individual terms and changing the operator. NOT (A AND B) is equivalent to (NOT A) OR (NOT B) NOT(A OR B) is equivalent to (NOT A) AND (NOTB) How can we prove that De Morgan’s laws are true? How can we see if two circuits or Boolean expressions are equivalent? Answer: Truth Tables  Proof by Truth Table NOT (A AND B) is equivalent to (NOT A) OR (NOT B) A B A AND B NOT(A AND B) A B NOT A NOT B (NOT A) OR False False False True (NOT B) False True False True False False True True True True False False True False True True False True True True True False True False False True True True True False False False Same outputs for all possible inputs…so equivalent. Sum of Products Given a truth table, what is the Boolean function? To create a sum of products expression, follow these steps: 1. Start with a truth table that describes the desired behavior of the Boolean function, listing all possible input combinations and their corresponding outputs. 2. Identify the rows of the truth table where the output is “True" (1). 3. For each of these rows, create a logical AND term by combining the input variables with their corresponding values. Invert False (0) values with the NOT operator. 4. Find the product for each row using the AND operator. 5. Combine all the logical AND terms using the logical OR operator, representing the function as the sum of these terms. Sum of Products Example: Find the Boolean function from this truth table. A B F False False False Rows where output is True False True True True False True True True False A B F NOT A AND B False True True F = (NOT A AND B) OR (A AND NOT B) True False True A AND NOT B Logic Operators in Python Compound conditions in Python are used to evaluate multiple conditions together using logical operators. The logical operators used for combining conditions are and, or, and not. Using the “and” operator: x > 5 and y < 10 Using the “or” operator: age >= 18 or has_permission Using the not operator: not has_permission More complex conditions: (x > 5 and y < 10) or (z == 0 and not is_valid) Compound Condition Example: AND Instead of nested if statements… num = int(input()) if num > 10: if num % 2 == 0: print(num, "is even and greater than 10.") …can use logical AND num = int(input()) if num > 10 and num % 2 == 0: print(num, "is even and greater than 10.") Compound Condition Example: OR Instead of multiple if statements… num = int(input()) if num > 10: print(num, "is greater than 10.") if num % 2 == 0: print(num, "is even.") …can use logical OR num = int(input()) if num > 10 or num % 2 == 0: print(num, "is even or is greater than 10.") Extra Reading This lecture covered: Sections 7.1 – 7.7 in the e-text