5. Logic and Boolean Algebra.pdf

Mathematical Concepts For Computing AQ010-3-1 (Version E) LOGIC AND BOOLEAN ALGEBRA  TOPIC LEARNING OUTCOMES At the end of this topic, You should be able to Determine truth values of a proposition. Understand...

Mathematical Concepts For Computing AQ010-3-1 (Version E) LOGIC AND BOOLEAN ALGEBRA  TOPIC LEARNING OUTCOMES At the end of this topic, You should be able to Determine truth values of a proposition. Understand logical and Boolean operators. Construct the truth table for logical expressions and Boolean functions. Translate the logical expressions into English sentences and vice versa. Construct logic circuits and determine the output of the logic circuits. Simplify the Boolean expressions using Boolean Identities. Represent the Boolean functions in sum of products and product of sums expressions. Simplify Sum of products expression using K-Map. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 2  Contents & Structure Logic Algebra Boolean Algebra Proposition Boolean Operators Logical operators Boolean Identities Translating English sentences into Boolean truth table construction logical expressions and vice versa. Representing Boolean Functions Precedence of Connectives Karnaugh Maps Logic truth table construction Logical equivalence, Tautology, Contradiction, Indeterminant Logic circuits AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 3  Introduction-Logic Logic is the basis of all mathematical reasoning, and of all automated reasoning. Automated reasoning is an area of computer science (involves knowledge representation and reasoning) The rules of logic specify the precise meanings of mathematical statements. These rules are used to distinguish between valid and invalid mathematical arguments. Example: “For every positive integer n, the sum of the positive integers not exceeding n is “ n(n + 1) 2 AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 4  Introduction-Logic To understand mathematics, we must understand what makes up a correct mathematical argument, that is, a proof. Once we prove a mathematical statement is true, we call it a theorem. It is the basis of the correct mathematical arguments, that is, the proofs. Logic defines a formal language for representing knowledge and for making logical inferences. It helps us to understand how to construct a valid argument. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 5  Introduction-Logic Everyone knows that proofs are important throughout mathematics, but many people find it surprising how important proofs are in computer science. In fact, proofs are used to verify that computer programs produce the correct output for all possible input values, to show that algorithms always produce the correct result, to establish the security of a system, and to create artificial intelligence. Furthermore, automated reasoning systems have been created to allow computers to construct their own proof. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 6  Logic – Some applications ✓ to the design of computer circuits/ machines, ✓ to the specification of systems, ✓ to artificial intelligence, ✓ to computer programming, ✓ to programming languages, ✓ to verify that computer programs produce the correct output for all possible input values, ✓ to show algorithms always produce the correct results, ✓ and to other areas of computer science, as well as to many other fields of study. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 7  Propositional Logic A proposition is a declarative sentence (that is , a sentence that declares a fact) that is either true or false, but not both. Notation: Variables are used to represent propositions. The conventional letters used for propositional variables are p, q, r, s,….. The truth value of a proposition is ✓ true, denoted by T if it is a true proposition and ✓ false, denoted by F, if it is a false proposition. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 8  Propositional Logic Example 1: a) “Listen!" is b) "What time is it?" is c) "x + 2 = 2 and x + y = z" is d) Read this carefully e) "x + 2 = x*2 when x = 2" is a f) 2 is a prime number. is a g) She is very talented. h) How are you? AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 9  Propositional Logic Example 1: a) “Listen!" is not a proposition. b) "What time is it?" is not a proposition. c) "x + 2 = 2 and x + y = z" is not a proposition. d) Read this carefully is not a proposition. e) "x + 2 = x*2 when x = 2" is a proposition. f) 2 is a prime number. is a proposition. g) She is very talented. is not a proposition. h) How are you? is not a proposition. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 10  Quick Review Question 1 Which of these sentences are propositions? What are the truth values of those that are propositions? Kuala Lumpur is the capital of Malaysia. 2+3=4 Washington D.C. is the capital of the United States of America. Read this carefully. Cat is an insect. 2+3=5 5 + 7=10 x + 2 = 11 Answer this question. What time is it? AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 11  Composite/ Compound statements Many mathematical statements are constructed by combing one or more propositions. New propositions, called compound propositions, are formed from existing propositions using logical operators. Example 2: Proposition A: It rains outside Proposition B: We will watch a movie A new (combined) proposition: If it rains outside then we will watch a movie. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 12  Logical Operation Logical operations include comparisons of two data. The result of the comparison will be either true or false. It can be represented using truth table (T or 1 represents true, and F or 0 represents false). The number of rows to the table is determined by all the possible values taken by the propositions involved in the statement. If a compound statement contains n proposition variables, there will need to be 2n rows in the truth table. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 13  Logical Connectives More complex propositional statements can be built from elementary statements using logical connectives. Logical connectives: 1. Negation 2. Conjunction 3. Disjunction 4. Exclusive or 5. Implication 6. Biconditional A truth table displays the relationships between the truth values of propositions. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 14  Logical Connectives Connectives Symbol Name not ~ negation and ⋀ conjunction or ⋁ disjunction exclusive or ⨁ exclusive disjunction(xor) if…then…. → Implication/conditional if and only if biconditional AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 15  Negation Let p be a proposition. The negation of p, denoted by ¬𝑝 (also denoted by ҧ is the statement “ It is not the case that p.” 𝑝), The proposition ¬𝑝 is read “not p”. The truth value of the negation of p, ¬𝑝 is the opposite of truth value of p. Truth table p ﹁p T F F T AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 16  Example 3 : Negation Find the negation of the following proposition and express in simple English. 1. “Today is Friday.” “Today is not Friday.“ or “It is not Friday today.” 2. "At least 10 inches of rain fell today in Miami.“ "Less than 10 inches of rain fell today in Miami.“ 3. “2 is a prime number.” “ 2 is not a prime number”. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 17  Quick Review Question 2 What is the negation of each of these propositions? It is raining 1+1=2 Lion cannot fly “Michael’s PC runs Linux” “Vandana’s smartphone has at least 32GB of memory” 1 + 2 = 3 or 2 + 1 = 3 The product of two negative numbers is a positive number. I will study hard, or I will not pass this course “There is a pollution in Kuala Lumpur”. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 18  Conjunction Let p and q be propositions. The proposition "p and q" denoted by p  q , is true when both p and q are true and is false otherwise. The proposition p  q is called the conjunction of p and q. Note that in logic the word "but" sometimes is used instead of "and" in a conjunction. Truth table p q p q T T T T F F F T F F F F AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 19  Example 4: Conjunction Find the conjunction of these propositions p and q where p is the proposition “Today is Friday” and q is the proposition “ It is raining today.” p  q: “Today is Friday and it is raining today.” Some other examples: 1. It is raining today and 2 is a prime number. 2. 2 is a prime number and 5 + 2 ≠ 8. 3. 13 is a perfect square and 9 is a prime. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 20  Disjunction Let p and q be propositions. The proposition "p or q" denoted by p  q , is false when both p and q are false and is true otherwise. The proposition p  q is called the disjunction of p and q. Truth table p q pq T T T T F T F T T F F F AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 21  Example 5: Disjunction Find the disjunction of these propositions p and q where p is the proposition “Today is Friday” and q is the proposition “ It is raining today.” p  q: “Today is Friday or it is raining today.” Some other Examples: It is raining today or 2 is a prime number. 2 is a prime number or 5 + 2 ≠ 8. 13 is a perfect square or 9 is a prime. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 22  Exclusive or Let p and q be propositions. The proposition "p exclusive or q" denoted by p ⊕ q , is true when exactly one of p and q is true and it is false otherwise. Truth table p q p ⊕ q T T F T F T F T T F F F AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 23  Example 6: Exclusive OR p : "Today is Friday q : " It’s raining today p ⊕ q : "Either today is Friday or it’s raining today, but not both.“ Some other examples: 1. The room has two light switches controlling one light bulb. If both switches are ON, the light is off. If one is ON, the light is on, if none is ON, the light is off. 2. Think of it like telling a child they can have candy, or ice cream. But they can't have both! 3. A simple real life example is magnetic pole. Like poles repel while unlike poles attract. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 24  Implication (Conditional Statement) Let p and q be propositions. The proposition "p implies q" denoted by p → q is called implication. It is false when p is true, and q is false and is true otherwise. In p → q , p is called the hypothesis and q is called the conclusion. Truth table Some of the more common ways p q p→q of expressing implication are : T T T (1) if p, then q T F F (2) p is sufficient for q F T T (3) p implies q F F T (4) q is necessary for p (5) p only if q (6) q whenever p (7) q, if p AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 25  Example 7: Implication Let p be the statement “Maria learns discrete mathematics” and q is the statement “Maria will find a good job.” Express the statement p → q as statement in English. There are many ways to represent the conditional statements in English. 1. “If Maria learns discrete mathematics, then she will find a good job”. 2. “ Maria will find a good job when she learns discrete mathematics.” 3. “For Maria to get a good job, it is sufficient for her to learn discrete mathematics.” AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 26  Example 8: Implication “ If you get 100% in the final, then you will get an A.” Explanation: If you manage to get a 100% on the final, then you would expect to receive an A. If you don’t get 100% you may or may not receive an A depending on other factors. However, if you do get 100%, but the professor does not give you an A, you feel cheated. Some other examples: 1. “ If I am elected, then I will lower the taxes.” 2. “if it rains, then I take an umbrella.” 3. A: Crashed, B: Reboot C: 𝑨 → 𝑩 : Script is working AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 27  Biconditional Let p and q be propositions. The biconditional p q (read p if and only if q), is true when p and q have the same truth values and is false otherwise. Truth table Some of the more common p q p→q q→p p q ways of expressing implication are : T T T T T 1. “p if and only if q” T F F T F 2. “p iff q ” 3. “If p then q , and F T T F F conversely.” F F T T T 4. ”p is necessary and sufficient for q” Note: The truth values always agree. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 28  Biconditional (Cont..) p only if q (if ~q, then ~p which equivalent to if p then q) p is sufficient for q (in order to get q, it is sufficient to get p) equivalent to (to get q, (if) get p) q is necessary for p (in order to get p, it is necessary to get q) equivalent to (get p only if get q) (if not get q, then not get p) q whenever p (whenever get p, get q) equivalent to (if get p then get q) AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 29  Example 9: Biconditional The flight attendant says, “You can take the flight if and only if you buy a ticket.” If you buy ticket (True), you can take the flight (True). The statement is TRUE. If you do not buy ticket (False), you cannot take the flight (False). The statement is TRUE. If you do not buy ticket (False) but you can take the flight (True), this statement is FALSE. If you buy ticket (True) but cannot take flight (False), this statement is FALSE. Some other examples: A student gets A in MCFC if and only if his weighted total marks is ≥ 80%. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 30  Quick Review Question 3 AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 31  System Specifications Translating sentences in natural language (such as English) into logical expressions is an essential part of specifying both hardware and software systems. System and software engineers take requirements in natural language and produce precise and unambiguous specifications that can be used as the basis for system development. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 32  Translating English Sentences into Logical Expression Example 10 : How can the following English sentence be translated into a logical expression ? “You can access the Internet from campus only if you are a computer science major or you are not a freshman. ” Sol : p : “You can access the Internet from campus.” q : “You are a computer science major.” r : “You are a freshman.” AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 33  Translating English Sentences into Logical Expression Example 11 : You cannot ride the roller coaster if and only if you are under 4 feet tall and you are not older than 16 years old. Sol : q : “ You can ride the roller coaster. “ r : “ You are under 4 feet tall. “ r s : “ You are older than 16 years old. “ AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 34  Translating logical formulas to English sentences Example 12: p: Alice is smart. q: Alice is honest 1. ¬p ∧ q: Alice is not smart but honest. 2. p ∨ (¬p ∧ q): Either Alice is smart, or she is not smart but honest. 3. p → ¬q: If Alice is smart, then she is not honest. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 35  Quick Review Question 4 Express the specification “The automated reply cannot be sent when the file system is full” using logical connectives. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 36  Precedence of Operators Example: ¬ p ∧ q means (¬ p) ∧ q p ∧ q → r means (p ∧ q) → r AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 37  Logical Equivalence Two statements are logically equivalent provided that they have exactly the same truth values in all possible cases. A statement is a tautology provided that its truth value in all possible cases is true. A statement is a contradiction provided that its truth value in all possible cases is false. A contingency/ indeterminant is a formula which has both some true and some false values for every value of its propositional variables. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 38  Proving Equivalence via Truth Tables Example 13: Prove that pq ≡ ~(~p  ~q). p q pÚ q ~p ~q ~p Ù ~q ~(~p Ù ~q) F F F T T T F F T T T F F T T F T F T F T T T T F F F T AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 39  Quick Review Question 5 Construct a truth table for each of the following compound proposition and state whether it is tautology, contradiction or contingency. 1. (A∨B)∧[(¬A)∧(¬B)] 2. [( A → B ) ∧ A] → B 3. (A ∨ B) ∧ (¬ A) AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 40  Boolean Algebra Computers represent information using bits. A bit is a symbol with two possible values, namely,0 (zero) and 1 (one). The meaning of the word bit comes from binary digit, because zeros and ones are the digits used in binary representations of numbers. The rules of logic are used to design circuits and form the basis for Boolean algebra. Boolean algebra is a deductive mathematical system closed over the values zero and one (false and true) A binary operator accepts a pair of Boolean inputs and produces a single Boolean value. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 41  Boolean Algebra Boolean algebra deals with - set of 2 elements {0, 1} - binary operators: OR ( /  +), AND( /.) - unary operator NOT { / ‘ } Truth table: OR AND p q  / + p q /. NOT 0 0 0 0 0 0 0 1 1 p / ‘ 0 1 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 1 1  Boolean Algebra Rules of precedence are: 1) Parentheses/ brackets, 2) complement(NOT), 3) product (AND), 4) sum(OR) Example 14 AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 43  Logic Gates Boolean algebra is used to model the circuitry of electronic devices. The basic elements of circuits are called gates. Boolean functions or expressions are typically implemented through the use of a collection of logic gates, which are the basic building blocks of logic circuits. In real world, logic gates are used in almost all the electronic devices such as phones, computers, washing machines, lifts etc. Whenever a decision needs to be taken based on some inputs, a logic gate can be designed and used. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 44  NOT gate The NOT gate is an electronic circuit that produces an inverted version of the input at its output. It is also known as an inverter. If the input variable is A, the inverted output is known as NOT A. This is also shown as A', or A with a bar over the top, as shown at the outputs. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 45  AND gate The AND gate is an electronic circuit that gives a high output (1) only if all its inputs are high. A dot (.) is used to show the AND operation i.e. A.B. Bear in mind that this dot is sometimes omitted i.e. AB AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 46  OR gate The OR gate is an electronic circuit that gives a high output (1) if one or more of its inputs are high. A plus (+) is used to show the OR operation. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 47  NAND gate This is a NOT-AND gate which is equal to an AND gate followed by a NOT gate. The outputs of all NAND gates are high if any of the inputs are low. The symbol is an AND gate with a small circle on the output. The small circle represents inversion. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 48  NOR gate This is a NOT-OR gate which is equal to an OR gate followed by a NOT gate. The outputs of all NOR gates are low if any of the inputs are high. The symbol is an OR gate with a small circle on the output. The small circle represents inversion. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 49  XOR gate The 'Exclusive-OR' gate is a circuit which will give a high output if either, but not both, of its two inputs are high. An encircled plus sign ⊕ is used to show the EOR operation. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 50  Example 15 Draw a logic circuit for the following. 1. (A + B)C 2. A + BC + D’ AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 51  Example 16 What is the final output of the given logical circuit?  ( AB + C )D AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 52  Quick Review Question 6 What is the final output of the given logical circuit? AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 53  Boolean Identities Identity Name (x')' = x Involution Law x + x' = 1 Complementarity Laws x x' = 0 x+x=x Idempotent Laws x x=x x+0=x Identity Laws x 1=x x+1=1 Dominance Laws x 0=0 x+y=y+x Commutative Laws xy = yx AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 54  Boolean Identities Identity Name x + (y + z) = (x + y) + z Associative Laws x(yz) = (xy)z x + yz = (x + y)(x + z) Distributive Laws x(y + z) = xy + xz (xy)' = x' + y‘ De Morgans’ Laws (x + y)' = x'y' x + (xy) = x Absorption Laws x(x + y) = x x + x'y = x + y Redundancy Laws x(x' + y) = xy xy + x'z + yz = xy + x'z Consensus Laws (x+y)(x'+z)(y+z) = (x+y)(x'+z) AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 55  Example 17 A+A·B=A (Absorption Theorem) Proof Steps Justification A+A·B =A·1+A·B Identity law = A · ( 1 + B) Distributive =A·1 Dominance =A Identity law Our primary reason for doing proofs is to learn: – Careful and efficient use of the identities and theorems of Boolean algebra, and – How to choose the appropriate identity or theorem to apply to make forward progress AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 56  Example 18 AB + AC + BC = AB + AC (Consensus Laws) Proof Steps Justification = AB + AC + BC = AB + AC + 1 · BC Identity element = AB + AC + (A + A) · BC Complement = AB + AC + ABC + ABC Distributive = AB + ABC + AC + ACB Commutative = AB · 1 + ABC + AC · 1 + ACB Identity element = AB (1+C) + AC (1 + B) Distributive = AB. 1 + AC. 1 Dominance = AB + AC Logic and Boolean Algebra Identity element AQ010-3-1-MCFC SLIDE 57  Example 19 (A + B) (A + B’) (AC’)’ = (A + B) (A + B’) (A’ + C) Involution & DeMorgan’s Law = (AA + AB’ + AB + B’B) (A’ + C) Distributive = ((A + BB’) + A(B + B’)) (A’ + C) Commutative& Distributive = ((A + 0) + A(1)) (A’ + C) Complementarity = A (A’ + C) Idempotent = AC Redundancy Use DeMorgan's Theorem: 1. Interchange AND and OR operators 2. Complement each constant and literal AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 58  Quick Review Question 7 Simplify the following expression : (a) F = C + BC (b) F = AB(A + B)(B+ B) (c) F = ( A + C )( AD + AD) + AC + C AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 59  Representing Boolean Functions In the design of digital systems, there are some standards that are regularly applied to combinational logic. This chapter outlines two standard representations of combinational logic: Sum-of-Products and Product-of-Sums. Any Boolean expression may be expressed in terms of either minterms or maxterms. A literal is a single variable within a term which may or may not be complemented. For an expression with N variables, minterms and maxterms are defined as follows – A minterm is the product of N distinct literals where each literal occurs exactly once. (SOP) – A maxterm is the sum of N distinct literals where each literal occurs exactly once. (POS) AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 60  Example 20 F(x, y, z) = xy’ + z is a Boolean function where xy’ + z is a Boolean expression. The truth table for F(x, y, z) = xy’ + z is x y z y’ xy’ xy’+z 0 0 0 1 0 0 The NOT operator has highest priority, 0 0 1 1 0 1 followed by AND 0 1 0 0 0 0 and then OR. 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 1  Quick Review Question 8 Use a truth table to express the values of each of these Boolean function. 𝑓 𝑥, 𝑦, 𝑧 = 𝑥(𝑦𝑧 + 𝑦 ′ 𝑧 ′ ) AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 62 AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 63  Sum-of-Products/minterm (SOP) Example 21: Sum-of- Products/ minterm (SOP) canonical form: Sum of products/ minterms of entries that evaluate to ‘1’ x y z F Minterm 0 0 0 0 0 0 1 1 xyz Focus on 0 1 0 0 the ‘1’ 0 1 1 0 1 0 0 0 entries 1 0 1 0 1 1 0 1 xyz 1 1 1 1 xyz xyz+xyz+xyz AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 64  Product-of-Sums/ Maxterm (POS) Example 22: Product-of-Sum/Maxterm (POS) canonical form: Product of sum/ maxterms of entries that evaluate to ‘0’ x y z F Maxterm 0 0 0 1 0 0 1 1 Focus on 0 1 0 0 (x + y + z) 0 1 1 1 the ‘0’ 1 0 0 0 (x + y + z) entries 1 0 1 1 1 1 0 0 (x + y + z) 1 1 1 1 (x+y+z) (x+y+z) (x+y+z) AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 65  Example 23 There are four 1s ◼ There are four 0s in A B C F in the output and the output and the 0 0 0 0 0 1 0 0 SOP POS the corresponding binary value are 011, 100, 110, and corresponding binary value are 000, 001, 010, and 101. 0 1 0 0 111. 0 1 1 1 011 → A BC 000 → A + B + C 100 → AB C 001 → A + B + C 1 0 0 1 110 → ABC 010 → A + B + C 1 0 1 0 101 → A + B + C 111 → ABC 1 1 0 1 1 1 1 1 SOP = ABC + ABC + ABC + ABC POS = (A + B +C)(A + B +C)(A + B +C)(A + B + C) AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 66  Example 24 Find the sum of products expansion for the function F(A, B, C) = (A + B)C’ by using truth table A B C A+B C’ (A+B)C’’ Three 1s in the 1 1 1 1 0 0 output. (110, 100, 1 1 0 1 1 1 and 010). 1 0 1 1 0 0 1 0 0 1 1 1 SOP = ABC + ABC + ABC 0 1 1 1 0 0 Five 0s in the output 0 1 0 1 1 1 (111, 101, 011, 001, 0 0 1 0 0 0 and 000). 0 0 0 0 1 0 POS=(A+B+C)(A+B+C)(A+B+C)(A+B+C)(A+B+C) AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 67  Karnaugh Map Karnaugh Maps (K-Maps) are a graphical method of visualizing the 0’s and 1’s of a Boolean function. K-Maps are very useful for performing Boolean minimization – SOP expansions. Karnaugh maps can be easier to use than Boolean equation minimization once you get used to it. 1 is placed in the square representing a minterm if the minterm is present in the expansion. The goal is to identify the largest blocks of 1s in the map and to cover all the 1s using the fewest blocks needed, using the largest blocks first. Must group 1s in either 1, 2, 4, 8, or 16 and must be adjacent. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 68  Karnaugh Map A K-map has a square for each ‘1’ or ‘0’ of a Boolean function. ✓ Two variable K-map has 22 =4 squares ✓ Three variable K-map has 23 = 8 squares ✓ Four variable K-map has 24 = 16 squares Will work on 2 and 3variable K-Maps in this class. 2 variable 3 variable 4 variable AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 69  Plotting Functions on K-Maps Two-variable map Ex: A’B’ + A’B + AB  Plotting Functions on K-Maps Two-variable map Ex: A’B’ + A’B + AB A A’ B 1 1 0 B’ 1  Plotting Functions on K-Maps On a two-variable map, look for a pair of 1's that are either in the same row or Two-variable map column. If we find such a pair, we record the common Ex: A’B’ + A’B + AB variable. A A’ B 1 1 0 B’ 1 = B + A’  Rule: 1 A group of four will have one common variable. A pair must have two common variables. In the examples below, the common variable for the left map is C’ and the common variable for the right group is B. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 73  Rule: 2 In the examples below, the left pair has the common variables BC, while the right pair has the common variables AB’. A solo / single 1 must have all 3 variables. AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 74  Rule: 3 The map "wraps around" from the left edge to the right The common variables for the pair on the left are B’C’, while the group of four on the right has the common variable B’. Rules in detail http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karrules.html AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 75 Plotting Functions on K-Maps Three-variable map Ex: X’Y’Z’ + X’YZ + XYZ’ + XY’Z + XYZ + X’YZ’ XY XY’ X’Y’ X’Y Z Z’ Plotting Functions on K-Maps Three-variable map Ex: X’Y’Z’ + X’YZ + XYZ’ + XY’Z + XYZ + X’YZ’ XY XY’ X’Y’ X’Y Z 1 1 1 Z’ 1 1 1 Plotting Functions on K-Maps Three-variable map Ex: X’Y’Z’ + X’YZ + XYZ’ + XY’Z + XYZ + X’YZ’ XY XY’ X’Y’ X’Y Z 1 1 1 Z’ 1 1 1 = Y + XZ + X’Z’  Summary / Recap of Main Points Logic Algebra Boolean Algebra Proposition Boolean Operators Logical operators Boolean Identities Translating English sentences into Boolean truth table construction logical expressions and vice versa. Representing Boolean Functions Precedence of Connectives Karnaugh Maps Logic truth table construction Logical equivalence, Tautology, Contradiction, Indeterminant Logic circuits AQ010-3-1-MCFC Logic and Boolean Algebra SLIDE 79