Detail explaination about boolean algebra. Help student to learn different logic system
1
1. AMIE DELHI COACHING BY CHAHANA SHARMA COMPUTING AND INFORMATICS Chapter : Boolean algebra, logic circuit Boolean algebra Boolean algebra is a mathematical system for the manipulation of variables that can have one of two values. In formal logic, these values are "true" and "false." In digital systems, these values are "on" and "off," I and 0, or "high" a "low. ' Boolean expressions are created by performing operations on Boolean var• Common Boolean operators include AND, OR, and NOT. A Boolean operator can be completely described using a truth table The truth table for the Boolean operators AND and OR are show th The AND operator is also known as a Boolean product. The O o or s the Boolean sum. X ANDY X OR Y NOT X o o 1 1 o 1 o 1 o o 1 x o o 1 1 o 1 o 1 X+Y o 1 1 1 x O 1 1 The truth table for the Boolean The NOT operation is ten s by a prime mark ( a A Boolean fun on a . o ator is shown at the right. signated by an overbar. It is sometimes indicated olean variable, At st on t ast e Boolean operator, and st one input from the set {0, 1 }. t ces an output that is also a member of the set {0,1 }. r truth table for the Boolean function: is shown at the right. To make evaluation of the Boolean function easier, the truth table contains extra (shaded) columns to hold evaluations of subparts of the function.
2
As with common arithmetic, Boolean operations have rules o The NOT operator has highest priority, followed by AND d the This is how we chose the (shaded) function subparts i de R. Digit 1 re lt. p ers contain circuits that implement Boolean functions. rer that we can make a Boolean function, the smaller the circuit that will Simpler circuits are cheaper to build, consume less power, and run faster than complex circuits. With this in mind, we always want to reduce our Boolean functions to their simplest form. There are a number of Boolean identities that help us to do this. Most Boolean identities have an AND (product) form as well as an OR (sum) form. We give our identities using both forms. Our first group is rather intuitive:
3
AND F o cm N ame Identity Law Null Law Idempotent Law O ox AND Form o OR F o cm x x x Inverse Law Identity N ame Commutative Law Associative Law Distributive Law Identi ty N ame x 1 OR Form (xy) z x+yz = (x+y) (x+z) AND x plify the function: x+y = y+x (x+y)+z = x + (y + z) x(y+z) = xy+xz OR Fo rm Absorption Law DeMorgan's Law Double Complement Law We can use Boolean id ti to as follows: xx + xz o + xz xz x + xy x Idempotent Law (Rewriting) DeMorgan ' s Law Distributive Law Commutative & Distributive Laws Inverse Law Idempotent Law Distributive Law Inverse Law Idempotent Law Sometimes it is more economical to build a circuit using the complement of a function (and complementing its result) than it is to implement the function directly. DeMorgan's law provides an easy way of finding the complement of a Boolean function. Recall DeMorgan's law states:
4
DeMorgan's law can be extended to any number of variables. Replace each variable by its complement and change all ANDs to ORS and all ORS to ANDs. Thus, we find the the complement of: is: There are two canonical forms for Boolean exp essl m-of-products and product- of-sums. Recall the Boolean product is the OR operation. In the sum-of-products form, D v For example: F(x,y,z) o eration and the Boolean sum is the les are ORed together. xy + x z + y z In the product- -sum o , ORed variables are ANDed together: amp It is t onvert a function to sum-of-products form using its truth table. interested in the values of the variables that make the function true (=1). Ing the truth table, we list the values of the variables that result in a true function value. Each group of variables is then ORed together.
5
o o o 1 1 o o 1 o o o 1 o o 1 The sum-of-products form for our function is: 2. Logic Gates The three sim lest ates are the A X AND Y x o o 1 1 o 1 o 1 x O o 1 R an OT ates. NOT X Y X+Y O 1 o rrespond directly to their respective Boolean operations, as you can see by their tables. Another very useful gate is the exclusive OR (XOR) gate. The output of the XOR operation is true only when the values of the inputs differ.
6
x O I X XOR Y Y XO Y O O Note the special symbol C for the XOR operation. NAND and NOR are two very important gates. Their symbols and truth tables are shown at the right. X NAN D Y X NAND Y X NOR Y X NOR NAND and NOR are k manufacture and any o NOR gates. NOT x AND rsal gates because they are inexpensive to as u ction can be constructed using only NAND or only ea x X OR Y Gates can have multiple inputs and more than one output.
7
3. Digital Components • The main thing to remember is that combinations of gates implement Boolean functions. The circuit below implements the Boolean function: x z 4. o o o We have designed a circuit that implements the Boolean f X+fz ction: This circuit is an example of a combinatio Combinational logic circuits produce sp input values are applied. Combinational Circuits o ci uit. ied utput (almost) at the instant when Combinational logic circu• s give m ny useful devices. One of the simplest is t ad , which finds the sum of two bits. We can gain some i h s e construction of a half adder by looking at its truth table, shown I n pu t s Ou tpu t s x o o 1 1 operation. x o 1 O 1 S urn o 1 1 o o o o 1 As we see, the sum can be found using the XOR operation and the carry using the AND
8
We can change our half adder into to a full adder by including gates for processing the carry bit. The truth table for a full adder is shown at the right. I npu t s full adder. Carry Out Just as we combined h series. The carry bit "ripples' m Ou tpu t s I nputs Ou tpu ts s to make a full adder, full adders can connected in a e adder to the next; hence, this configuration is called a ripple- carry adder. 15 Carry Out 15 15 Carry In
Discussion
Copyright Infringement: All the contents displayed here are being uploaded by our members. If an user uploaded your copyrighted material to LearnPick without your permission, please submit a Takedown Request for removal.
Need a Tutor or Coaching Class?
Post an enquiry and get instant responses from qualified and experienced tutors.
If you have your own Study Notes which you think can benefit others, please upload on LearnPick. For each approved study note you will get 25 Credit Points and 25 Activity Score which will increase your profile visibility.