CS代考计算机代写 algorithm Boolean Algebra and Circuits

Boolean Algebra and Circuits

COMP273 McGill
á Truth Tables
á BooleanFunctions
á Logic Gates
á CombinatorialCircuits á AppendixC
Overview

Truth Table

COMP273 McGill
Boolean Operations á Considerbinaryvariables,A,B
± Possible values are 0 (FALSE) and 1 (TRUE)
ABC
á Differentpossibleinputswithnoperands=2n ± 2 binary operands: 22 = 4 different possible inputs ± 4 binary operands: 24 = 16 different possible inputs
Ï2 Ï2 Ï2 Ï2 Ï2 Ì2 Ï2 Ì2 Ï2 Ï2 Ì2 Ì2 Ì2 Ï2 2Ï Ì2 Ï2 Ì2 Ì2 Ì2 Ï2 Ì2 Ì2 Ì2
AAB
000 101 10 11

COMP273 McGill
Boolean Operations
á ABooleanFunctionisanalgebraicexpressionconsistingof binary variables and the logic operation symbols
á Any Boolean function can be written in terms of AND, OR, and NOT
á Truth table defines all possible outcomes
AB|A+B 0000 0101 1001 1111

COMP273 McGill
Note on Notation
OR(A,B) AND(A,B) NOT(A) A+B |
A|B A&B ~A
A || B A && B !A AvB A^B ¬A
AB [ When do we use which?

COMP273 McGill
Boolean Algebra
á Rulescapturelogicalreasoning
á Allowformanipulationofexpressions

||[=||[=||[ [ | ~ | [ = | [
COMP273 McGill
Boolean Algebra
Are two boolean functions equivalent?ent? Prove it, or find values to show that they are not!

Boolean Expression

COMP273 McGill
Derive Boolean Expression
á Consider a logic function with three inputs, A, B, and C, and three outputs, D, E, and F.
± D is true if at least one input is true
± E is true if exactly two inputs are true ± F is true only if all three inputs are true
á Find the Boolean expression for D, E, and F.

COMP273 McGill
Ï2 Ï2 Ï2 Ï2 Ï2 Ì2 Ï2 Ì2 Ï2 Ï2 Ì2 Ì2 Ì2 Ï2 2Ï Ì2 Ï2 Ì2 Ì2 Ì2 Ï2 Ì2 Ì2 Ì2
Derive Boolean Expression
Find the truth table! D is true if at least one input is true ABCD

COMP273 McGill
Derive Boolean Expression
Find the truth table! E is true if exactly two inputs are true
ABCDE
Ï2 Ï2 Ï2 0 Ï2 Ï2 Ì2 1 Ï2 Ì2 Ï2 1 Ï2 Ì2 Ì2 1 Ì2 Ï2 Ï2 1 Ì2 Ï2 Ì2 1 Ì2 Ì2 Ï2 1 Ì2 Ì2 Ì2 1

COMP273 McGill
Derive Boolean Expression
Find the truth table! F is true only if all three inputs are true
ABCDEF
Ï2 Ï2 Ï2 0 0 Ï2 Ï2 Ì2 1 0 Ï2 Ì2 Ï2 1 0 Ï2 Ì2 Ì2 1 1 Ì2 Ï2 Ï2 1 0 Ì2 Ï2 Ì2 1 1 Ì2 Ì2 Ï2 1 1 Ì2 Ì2 Ì2 1 0

COMP273 McGill
Derive Boolean Expression
What are the Boolean expressions for outputs D, E, and F?

COMP273 McGill
Derive Boolean Expression
D is true if at least one input is true D=

COMP273 McGill
Derive Boolean Expression
F is true only if all three inputs are true F=

COMP273 McGill
Derive Boolean Expression
E is true if exactly two inputs are true E=

COMP273 McGill
Sum of Products, Product of Sums
á Canonical form for any logic function
± Only two levels of gates, one AND, the other OR ± Possible inversion on the final output.
A ~ | | [ = ~ | | [ = ~ | | [ Sum-of-Product A ~[=[= | ~[=[= | ~[=[= Product-of-sum
á Why? Permits an easy/direct/naïve implementation of any Boolean function in hardware

Circuits

COMP273 McGill
± NAND: Not And ±NOR:NotOR
± XOR: Exclusive OR
A B NAND NOR XOR 00110 01101 10101 11000
Common Binary Operations
á Three other very common operations:
á Using AND, OR, NOT, how would you write expressions for each of these functions?

COMP273 McGill
Combinational Circuits
á A combinatorial circuit is a circuit that implements a Boolean function
á å¡öZ]åμ]ö(}åzA~[=

COMP273 McGill
á Canput>2inputs onanANDorandORgate
á Allowed because of the associative law
Multiple Inputs
á Commutative law of Boolean algebra: the ordering of the wires into a AND and OR gates doesn’t matter
á Example:3inputANDgate(thesefunctionsaresymmetric)

COMP273 McGill
Questions
á HowmanydifferenttwoinputBooleanfunctionsexist?
± How many of these functions are symmetric? ~]XXU öZ }åå }( öZ ]vâμöê }êv[ö uööå
á HowmanydifferentthreeinputBooleanfunctionsexist?

Don’t Care!

COMP273 McGill
}v[ö å
á Situations where we do not care about the value of an output ± Because another output is true
e.g., If A is true, then A + B is true. We don’t need to check B
± Because a subset of the input combinations determines the outputs e.g., if A is false, then A and B is false. We don’t need to check B

COMP273 McGill
}v[ö å á Can be easier to specify the truth table
á Writethetruthtable,markingX(}å^}v[öå_
± Inputs S, A, B
±OutputC 0000
SABC
± If S is true, output is A ± If S is false, output is B
0x00 0011 0x11 0100 0x00 0111 0x11 1000 10×0 1010 10×0 1101 11×1 1111 11×1
0x00 0x11 10×0 11×1
SABC SABC

COMP273 McGill
If A or C is true, then output D is true, whatever the value of B. If A or B is true, then output E is true, whatever the value of C.
}v[ö å
Output F ]ê öåμ ]( Æöo« }v }( öZ ]vâμöê ]ê öåμU μö ¡ }v[ö å }μö öZ ¿oμ of F, whenever D and E are both true.

COMP273 McGill
Circuit Minimization
á Theproblemofobtainingthesmallestlogiccircuit(Boolean formula) that represents a given Boolean function or truth table.
á The problem is believed to be hard, but there are effective heuristics (Karnaugh maps, the QuinetMcCluskey algorithm).
á «}vöZê}â}(öZ]ê}μåêY
± See Randy H. Katz, “Contemporary Logic Design”

COMP273 McGill
á TruthTables
á BooleanFunctions
á Logic Gates
á Combinatorial Circuits
Review and more information
á The best thing about a Boolean function is that even if you are wrong, you are only off by a bit
á This class covers topics in textbook ± Appendix C of 4th edition
± Appendix B of 5th edition

Related Posts