Non PHYS 2020
Popular in Course
Popular in Physics (Mtsu And Rodp)
This 12 page Class Notes was uploaded by Gilda Wisozk on Wednesday September 23, 2015. The Class Notes belongs to PHYS 2020 at Middle Tennessee State University taught by Staff in Fall. Since its upload, it has received 31 views. For similar materials see /class/213136/phys-2020-middle-tennessee-state-university in Physics (Mtsu And Rodp) at Middle Tennessee State University.
Reviews for Non
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/23/15
L23 Introduction to Boolean Algebra L23 Boolean Algebra You are already familiar with regular algebra in which variables are used to represent quantities which at least a priori can take on any real or even complex value You have also seen in the previous lecture that variables can be assigned to logic statements and that these statements and therefore the associated variables can take on values However the difference between the algebraic variables and the variables we use to represent statements in logic is that the logic variables can only take on one of two possible values 1 representing logical true and 0 representing logical false lit should therefore come as no huge surprise to nd out that we need a different kind of algebra to deal with these variables which can only take on these two simple values Such an algebra was worked out by the English mathematician and logician George Boole 1815 1864 In this lecture we will be introduced to some of the basics of Boolean algebra In the next lecture we will nally be introduced to some digital electronics circuit symbols and start seeing how the formalism we ve worked so hard on is used in the realm of digital electronics laHnHmfun prlnnhvc7n7nn pnhlrpCT lQT 74 QI39snrlv l1 hh nl Page 1 of 1 767009 Review Page 1 of 2 A Logic Review We here overview some of the results in logic that we have obtained so far We also take this opportunity to introduce a bit of terminology that we have not yet seen This overview will get us ready to tackle some laws of logic in the next section We use capital letters as variables to represent logic statements A B etc We have also seen that these variables can take on the binary values 1 or 0 Compound statements can be formed from simple statements with the use of logic operators or logic functions The three logic functions that we ll be dealing with are AND OR and NOT which are represented by the symbols and a bar placed over the variable symbol respectively l Boolean Notation Logical Notation l l 1 II T true 0 r false I lt H AND I l II OR I E I NOT A If you read about logic in other texts you may nd that the notation differs from what is given here There are a number of different notation schemes used in the literature The one that we use in this course is consistent with most electronics data books There are three properties of Boolean algebra and also of regular algebra with which we must be familiar before we tackle the logic theorems in the next section These are the associative distributive and commutative properties The associative property says basically that the order in which multiple applications of the same logic function are performed doesn t make any difference More precisely the associative properties for the AND and OR logic functions can be stated as follows Associative Property for AND X Y Z X Y Z 231 Associative Property for OR X Y Z X Y Z 232 The distributive property addresses a combination of AND and OR logic functions and will be somewhat familiar from regular algebra Caution Be careful not to think of the as multiplication and the as addition the Distributive Property 2 below will make no sense if you do hffnllmfcn pd11nhm n39nT pnhn pcT lCLT 74H QPPVipxxrhnrlv rpvipur lofml 71470 Review Page 2 of 2 Distributive Property 1 X Y Z X Y X Z 233 Distributive Property 2 X Y Z X Y X Z 234 Finally the commutative property says that it doesn t matter in which order a single operation is performed that is it s the same backwards as it is forwards Commutative Property for AND X Y Y X 235 Commutative Property for OR X Y Y X 236 For those going on in mathematics the associative and commutative properties satis ed by Boolean algebra means that this logical algebra forms an abelian group If you re not going on in mathematics forget I even mentioned this As with any relations we ll be discussing in our study of Boolean algebra you can always sit down and prove them with truth tables if you don t believe them We ll demonstrate this in the coming sections hHnJmfcn nAnNnero397n7nT pnhwpcT 1C OQT QDpvinnIkn v rpvipur hfml quotHA7an Logic Theorems Page 1 of 3 Some Logic Theorems We will be stating and discussing several logic theorems below We will then simply state a number of other logic theorems There will be a total of 15 theorems These other theorems will then either be proved in examples or else you will be proving them in the homework Note You will certainly not have to memorize these theorems They will be supplied to you on tests or quizzes if you should need them However as always you must be familiar with how to use or in this case prove them Theoreml AA A Basically we will be proving these theorems by simply applying the de nition of the logic functions AND OR or NOT or by working out a truth table to show explicitly that the two sides of the theorem are the same or we will be using theorems that we ve already proven or any combination of these This theorem is most easily proved by building its truth table Note that there is only one input so there will only be two rows in the truth table I Proof of Theorem 1 I 51 An examination of the truth table shows us that indeed for all of the possible values of A all two of theml whatever the value of A the quantity A A must have the same value Therefore A A A and the theorem is proved Make sure that you can understand and duplicate this reasoning IE Theorem 2 A A A The proof of this theorem is left for the homework Theorem3 A 1 1 This theorem is particularly easy to prove The proof comes directly from the de nition of the OR function The OR operation of anything with 1 is always equal to 1 by de nition of the OR operator The theorem is thus proved Theorem 4 A 1 A H omewark Theorems A O A lamallmi39nn QA nk yo n nn nnhnnnT 101 7 QT nrn39n Tkpnrnmoknrlv lnnir fknnrnma 11f 76 an Logic Theorems Page 2 of 3 Homework Theorem 6 A O 0 Homework Theorem 7 A 31 1 We ll kind of use a truth table for this proof but without actually writing out the truth table explicitly Instead we ll just use words in our argument Remember that from the de nition of the OR operator if I is one of the components of the statement then the OR function will give us a I It then follows that if A 1 then A anything 1 and if A z 0 then NOT A l and again anything 1 1 Thus the theorem is proved no matter what the value of A Do you understand this argument If not just write out the full truth table to prove it to yourself Theorem 8 923 2 0 Homework Thenrem9 A or NOTNOI AA This is again most easily proved with a truth table Remember that you can always prove relations in Boolean algebra with a truth table See if you can follow the various entries in the table below We introduce the variable B just for convenience to help us keep track of what we re talking about it is not necessary to do this i Proof of Theorem 9 i A BK Ef 0 H 1 u o I l 1 H 0 H 1 I Since NOT NOT A the last column in the table is the same as A the rst column in the table for each possible value of A the theorem is proved Theorem 10 A A B A We will prove this theorem in Example 231 Theorem 11 A A B A kHnImi39nn nAnk mquotn nT nnfnrooT 10T 7 2 nnin Thonrnmckn v lnnin H39Innrnmc hf 040009 Logic Theorems Homework Theorem 12 A 3 AB A EB A E A B 0AB AB The theorem is thus proved Theorem 13 A E B A 13 Homework Theorem 14 53 A B 351 13 Homework Theorem 15 E h B if E Homework by 232 Dismbuzz39ve Proper3y by Theorem 8 by Mewem 5 kHrsJmfan nAwInkrc nqnT nnhnncT 10T OR 2 nahquot Thnnromon n v 1nnr H Ipnrnmo 11139 Page 3 of 3 OROHHQ EX 231 Solution Page 1 of 1 Solution to Example 231 Prove Theorem 10 from the previous section Theorem 10 A A B A To prove this theorem we will use a couple of the theorems already proved or that you will prove in the homework along with a bit of extra logic We rst note that since A and B can only have the values 1 or O whatever the value of B is it is either equal to A or else equal to NOT A We will consider each of these possibilities below Case 1 B A In this case we get that A A A A A by Theorem 2 A by Theorem 1 Case 2 B NOT A In this case we get that AAEAU by eoremc 13 by ame 5 Since the answer we get is A no matter what the value of B is the theorem is proved It should once again be pointed out that there are always a number of ways to prove a theorem We are simply exposing you to some different methods of approach and ways of thinking in the proofs that are presented in this lecture LeanIN Jul L m n nT onfiIVnnT 1O TOE139 QTJV 2 1UV 2 1 innh39nnknrlu av 1 1 quotUKQan DeMorgan Page 1 of l DeMorgan39s Theorems There are two nal theorems with which we must acquaint ourselves in order to complete our introduction to logic These theorems are collectively called DeMorgan s Theorems or DeMorgan s Laws after the English mathematician and logician and contemporary of George Boole Augustus DeMorgan 1806 1871 These theorems can be stated in words as follows conjunction The negation of the of two statements disjunction disquot nation J of the 139 s iagica y equivalent to the conjuncaon negations of those twa statemnts In the sentence above the top word in one bracket should be read with the top word in the other the same for the bottom words This just keeps us from having to write the sentence twice More elegantly and certainly more concisely these two theorems can be stated symbolically as follows Theorem 1 AB EE 23 and Theorem 2 A B K E 238 DeMorgan s theorems were very useful in the early development of digital electronics in that a consequence of these theorems is that all logical operations even those which we have not discussed in this class such as NAND NOR XOR XNOR etc can be reduced to combinations of NOT and AND functions or combinations of NOT and OR functions This means that with only the three mctions we have de ned and discussed AND OR and NOT we can work out every type of logic operation DeMorgan s rst theorem above will be proved in the next example You will prove the second theorem possibly using the results of the rst theorem in the homework L44 lmn AA L mononn nn11vnnn 10 T OEIT QMQRlnrnnnknrlu Anmnvnn Lfm ogonno EX 232 Solution Page 1 of 2 Solution to Example 232 Prove DeMorgan s rst theorem Theorem 1 AB EE 237 We shall prove this theorem with a truth table Again you can approach the proof of any theorem in digital logic with a truth table if you want to There may be other more elegant proofs using other theorems that have already been proved but a truth table is always a viable option In this case we will break one big tmth table up into two smaller ones just to help us visualize more easily what s going on The rst truth table will use A and B as inputs and the left hand side of DeMorgan s rst theorem as the output The second table will also have A and B as inputs but will have the righthand Side of DeMorgan s rst theorem as the output The theorem will be proved when we see that the table columns of the two outputs are identical Table 1 The LeftHand Side of DeMorgan s First Theorem A II B HABll ml 1 ll 0 ll 0 H 1 l l 1 ll 0 ll 0 H 1 I l 0 1 ll 0 H 1 l l 1 ll 1 ll 1 H 0 l IAHBHIIIEHEEI lollollllllllll IIIIOHOIIHII lolllllllollll IIHIHOHOHOI Note in the two tables above that the columns under the inputs A and B are the same as they must be if we wish to compare the output columns As advertised the last columns of output values in the two tables above are identical thus proving DeMorgan s rst theorem LHuImfnn aAnln1nm n nT onhn ncT 1CLT ltT va Q GREY Q 7 QATHHAnknriv AV 1 7 OKOHDQ EX 232 Solution Page 2 of 2 You will be proving DeMorgan s second theorem in the homework To do this you may either construct a truth table or a pair of truth tables as we have done here or you can try a more elegant approach using theorems that we have already proved including DeMorgan s rst theorem above Have fun Lkulmlnn mA1vn1a rnqn nTnnhirncn107T 74T QDY Q OFY Q 7 innh39nnknr t 13v 1 OIKOan Sample Quiz 23 Page 1 of 1 Sample Quiz 23 1 The algebra that is used to work with variables that can have only one of two values is called a Algerian algebra b Mathematical algebra c Pythagorean algebra d Boolean algebra e Roman algebra 2 The logical statement E F is an example of an a multiplication b conjunction c negation d disjunction e election 3 Boolean algebra is named after a George Aftermath b George Forge 0 George Boole 1 George Washington e George Smith 4 The Associative Property for disjunction can be written A B C aD bQ cABC dAB eCAB 5 In digital logic I 1 a 0 b l c 2 d 3 e 12 An ewe rs LM mn11 aAnn1um T onhvpooT 10 T 0R QQn llknrln nn 1am QIKO nQ SQ23Ans Page 1 of 1 Answers to Sample Quiz 23 1d 2b 40 5b anHmfon n nn11vc 7n nT pnfnrncn 1017 7 QQnQQQn YZAnckn v cn rzanc kfm OKl 7an
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'