Transcript A(B + C)
CSIS-110 Introduction to Computer Science Dr. Meg Fryling “Dr. Meg” Fall 2012 @SienaDrMeg #csis110 CSIS-110 Lecture Nine Agenda • Questions? • Assignments • CSI Chapter 5 - Gates and Circuits – Homework 2 – Part I – Lab 4 CSIS-110 Assignments • Readings: See course scheduled on syllabus – The textbook readings are going to help you with homeworks AND labs • Homework 2 – Due Wednesday, October 10th at BEGINNING of class – Coming to class late does NOT extend your due date/time • Lab 3 – Due at START of lab 4 – Coming to lab late does NOT extend your due date/time CSIS-110 What do I like about this? CSIS-110 Chapter 5 Gates and Circuits CSIS-110 DeMorgan's Law • 9/26/12 Worksheet - Question 1c • Misspoke when I said (B OR C)' is the same as (B' OR C'). NOT TRUE! • If you try a few examples you'll see it doesn't work! • Should have said (B OR C)' is the same as (B' AND C'). – This is known as DeMorgan's Law. – It is also true that (B AND C)' is the same as (B' OR C')! • See last slide from Wednesday’s lecture on properties of Boolean algebra. • So the answer for 1c is (A’ AND B) OR (B OR C)’ – (A’ AND B) OR (B’ AND C’) CSIS-110 Gates with More Inputs • Gates can be designed to accept three or more input values • A three-input AND gate, for example, produces an output of 1 only if all input values are 1 Figure 4.7 Various representations of a three-input AND gate 7 CSIS-110 Constructing Gates • Transistor is a device that acts either as a wire that conducts electricity or as a resistor that blocks the flow of electricity, depending on the voltage level of an input signal – It’s a switch!! – It is made of a semiconductor material, which is neither a particularly good conductor of electricity, such as copper, nor a particularly good insulator, such as rubber 8 CSIS-110 Example 1 • Consider the circuit diagram below: • What is the corresponding Boolean expression? Homework 2: Part I – A CSIS-110 Example 1 - Truth Table Boolean Expression: (AB) + (A + B) What is the corresponding truth table? A B AB A+B (AB)+(A+B) CSIS-110 Combinational Circuits • Gates are combined into circuits by using the output of one gate as the input for another – What is the Boolean expression for this circuit? – What is the truth table for this circuit? Question 7 13 CSIS-110 Truth Table Boolean expression is (AB + AC) A B C AB AC AB+AC CSIS-110 Combinational Circuits • Three inputs require eight rows to describe all possible input combinations (2n, where n is the number of inputs) • This same circuit using a Boolean expression is (AB + AC) 15 CSIS-110 Example 2 • Consider the following Boolean expression: – A’B+(B+C)’ • Draw a circuit diagram Homework 2: Part I – A CSIS-110 Example 2 - Circuit CSIS-110 Example 2 - Truth Table • Boolean expression: A’B+(B+C)’ • Draw the corresponding truth table A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 A’ A’B (B+C) (B+C)’ A’B+(B+C)’ CSIS-110 Now let’s go the other way • Consider the following Boolean expression: A(B + C) a. What does the circuit look like? b. What does the truth table look like? Question 8 20 CSIS-110 Circuit 21 CSIS-110 Truth Table Boolean expression is (AB + AC) A B C B+C A(B+C) CSIS-110 Truth Table Compare this truth table with the previous question. Notice anything? 23 CSIS-110 Wow, it produces the same results! … do they both behave the same way? … if so, which is better? 24 CSIS-110 Combinational Circuits • We have therefore just demonstrated circuit equivalence – That is, both circuits produce the exact same output for each input value combination • Boolean algebra allows us to apply provable mathematical principles to help us design logical circuits • A(B + C) = AB + BC (distributive law) so circuits must be equivalent 25 CSIS-110 Properties of Boolean Algebra 26 CSIS-110 Truth Table -> Circuit Design • Sum-of-Products Algorithm – Step 1. Start with a truth table – Step 2. Identify rows with a 1 output, and make a product (AND) of the input variables – Step 3. Negate each variable that is zero in its row – Step 4: Create the Boolean expression by creating their sum (OR) – Step 5. Produce the circuit diagram! Homework 2: Part I – D & E CSIS-110 Sum-of-Products Algorithm Step 1. Start with a truth table Step 2. Identify rows with a 1 output, and make a product (AND) of the input variables A B output 0 0 1 0 1 0 1 1 0 1 1 1 CSIS-110 Sum-of-Products Algorithm Step 3. Negate each variable that is zero in its row A 0 0 1 1 B 0 1 0 1 output 1 1 0 1 AB AB AB CSIS-110 Sum-of-Products Algorithm Step 4: Create the Boolean expression by creating their sum (OR) A 0 0 1 1 B 0 1 0 1 output 1 1 0 1 A’B’ A’B AB CSIS-110 Sum-of-Products Algorithm • A’B’ + A’B + AB • Step 5. Produce the corresponding circuit diagram! CSIS-110