[CS61C FA20] Lecture 16.4 - Combinational Logic: Laws of Boolean Algebra — Transcript

Full transcript

1. 0:00and welcome back now let's look at some
2. 0:02of the
3. 0:03laws of boolean algebra what are some of
4. 0:05the rules we'll use what are some of the
5. 0:07the principles properties identities
6. 0:09we're going to use
7. 0:10for boolean algebra i love this let's go
8. 0:13one by one to take it really slow to
9. 0:15make sure you understand how each one
10. 0:17works
11. 0:18so there's a kind of a parallel set of
12. 0:21laws that are actually interesting in
13. 0:22this way
14. 0:23so there's like it's okay there's a
15. 0:26beautiful duality
16. 0:27that comes kind of comes to the front
17. 0:29when we're talking about building
18. 0:30algebra
19. 0:31the duality is peril universes yin yang
20. 0:34good versus evil dark side and the light
21. 0:37side of the force
22. 0:39you have here zero and one
23. 0:43and an or okay so a lot of times you're
24. 0:45seeing these
25. 0:46your team these even these rules have
26. 0:48kind of one side versus the other side
27. 0:50of that so
28. 0:51let's take a look the first is the law
29. 0:53of complementarity
30. 0:55this says x
31. 0:59and its complement what is the property
32. 1:02when you multiply them or when you add
33. 1:05them where
34. 1:06can you ever have a case where it can be
35. 1:08both true
36. 1:10and false i can both both x and not x at
37. 1:13the same time
38. 1:14never happens so that's zero
39. 1:18contrast that with what happens
40. 1:22i'll be happy if i have know a burrito
41. 1:25for dinner
42. 1:26or if i don't have a burrito well guess
43. 1:28what you're always going to be happy
44. 1:29because one of those is going to be true
45. 1:30if either one is going to be true either
46. 1:32one is going to be
47. 1:32there x or not x yep that's always 1.
48. 1:36so that's actually kind of neat so we
49. 1:37can actually match that to here
50. 1:39law of ones and zeros x and one is
51. 1:43x and zero is zero i have to be x
52. 1:46and false it can never be the false kind
53. 1:49of cancels it in a way
54. 1:51so x and zero is definitely x
55. 1:54or 1 is 1. you know x or
56. 1:57always true well that's true in fact
57. 1:59i've actually written code where i
58. 2:00wanted to
59. 2:01i was testing some loop some test x okay
60. 2:03and i wanted to go and make sure you hit
61. 2:05this test and go in there
62. 2:06i would write i would literally write in
63. 2:08my code i had my test
64. 2:09x and i would say or one
65. 2:13and i know if it's or one meaning or
66. 2:15true it's going to go into that piece of
67. 2:17code
68. 2:17and if i want if i have a piece of code
69. 2:19as an x i i never wanted to go i would
70. 2:20say
71. 2:21and zero so i actually use these a lot
72. 2:24in my coding
73. 2:25to have it either always go in the loops
74. 2:27or there or always get out of the but
75. 2:28i'll make a note to say take this out
76. 2:29later when the production code is out
77. 2:31there
78. 2:31but if i just want to really quick
79. 2:33rather than delete the x and write true
80. 2:35i'll actually say and one or i'll say
81. 2:37i'll say and zero or
82. 2:39one to either never have to go in the
83. 2:40loop or yes always go in the loop kind
84. 2:42of cool
85. 2:44this one is from math nothing i need to
86. 2:45tell you about there identity the
87. 2:46identity of multiplication is one they
88. 2:48did it which is
89. 2:49and and is true the identity of or
90. 2:52or addition is zero so uh it's like
91. 2:55saying
92. 2:56x or false is still x
93. 2:59so the identity of or is false identity
94. 3:02of
95. 3:02and is true that's kind of neat so if i
96. 3:04have this big and
97. 3:06like the accumulator was adding things
98. 3:07together the identity of
99. 3:09of of addition is zero so i initialize
100. 3:11it to zero if i'm going to and things
101. 3:13together
102. 3:14what do you initialize it with right
103. 3:16there you initialize it with true
104. 3:18if you know that with zero i don't care
105. 3:19what else you have here it's zero
106. 3:22okay i've got this one
107. 3:28and this one is fun i'm going to play
108. 3:30this song for you let me play it ready
109. 3:31here we go three two one
110. 3:32item potent let me play this here for
111. 3:34you this is kind of a fun thing
112. 3:35item pose you hear that do you hear that
113. 3:38item potent
114. 3:39okay this just basically says
115. 3:42x and x it's not two x's i mean x
116. 3:46x times x would be x squared in some
117. 3:47other world but this is x and x it's
118. 3:49just
119. 3:49x it's gonna be x and also x well
120. 3:52nothing happened nothing
121. 3:53there was no new information there x or
122. 3:56x same thing
123. 3:57no new information item potent says this
124. 3:59just replace anything of the same
125. 4:01uh with itself this is a commutative law
126. 4:05i've
127. 4:05shared that before that's that's a
128. 4:07principle now it isn't necessarily true
129. 4:09but it is true in the boolean algebra
130. 4:11and it's true in mathematics it's also
131. 4:12true here showed you that we have
132. 4:14associativity
133. 4:16we have this this is the same doesn't
134. 4:17matter how you parenthesize things
135. 4:20also doesn't matter how you parenthesize
136. 4:21the addition that's not new
137. 4:23and not special all right distribution
138. 4:26is kind of cool
139. 4:28this means that i can take x and
140. 4:29distribute x to both y and z
141. 4:32and i can also reverse distribute if i
142. 4:34have a common x
143. 4:35i can pull the x out to have the x in
144. 4:36the front now
145. 4:38this is the width what's the equivalent
146. 4:39on the other side it's this
147. 4:42rule look at this rule this is a really
148. 4:45interesting rule which i can prove for
149. 4:46the other terms
150. 4:48let's actually take a look at the deeper
151. 4:49this rule well i'll start over here okay
152. 4:51x this let's do the foil method right
153. 4:54this is x
154. 4:55x plus x y
155. 4:59plus that's outside right x z
156. 5:02plus y z okay
157. 5:05let's start some using some rules i
158. 5:07don't know what do you see you might see
159. 5:09the the item potent rule
160. 5:11x times x that's just x okay
161. 5:14how about x or x y
162. 5:18anybody see this rule before where's the
163. 5:20x or
164. 5:21x y actually that's this one that's this
165. 5:24that's the uniting theorem we can get to
166. 5:25that in a second
167. 5:26um here is um
168. 5:30y and z i'm trying to get to x plus y z
169. 5:33so
170. 5:34this is x or okay i'm gonna skip
171. 5:38i'm skipping to the uniting theorem okay
172. 5:41i'm skipping to the uniting theorem
173. 5:43here we go uniting theorem which says
174. 5:47x y or x is just
175. 5:51x so meaning it says like it says okay
176. 5:53it's true when x is true
177. 5:55it's also true if x and y is true but
178. 5:57you knew it was true when x is two
179. 5:58already
180. 5:59so this is no new information the y
181. 6:01doesn't help at all that's just the same
182. 6:02as x
183. 6:03so if you add this x y term it's just x
184. 6:07if i take that this is x or x y
185. 6:10or xz this because of the uniting
186. 6:13theorem
187. 6:14just becomes x therefore this
188. 6:17distribution law
189. 6:18x plus y z is just
190. 6:21x plus y z so you kind of need the
191. 6:23uniting theorem to simplify that side of
192. 6:25the distribution
193. 6:26okay and similarly this uniting theorem
194. 6:29on the right side
195. 6:30says so let's do it okay x or y
196. 6:33times x what is that which means x and
197. 6:37some other thing that has an x in there
198. 6:39well why does that the same as just
199. 6:40saying x why can't i just drop that off
200. 6:42and write a 1 there or just even just
201. 6:44cancel it why can i just cancel this
202. 6:46term and write a 0
203. 6:47and why can't i can't determine write a
204. 6:48one because x times one is x
205. 6:50why well let's do it let's distribute
206. 6:52this out this becomes x
207. 6:53x or x y actually becomes y
208. 6:56x i do this right well y x is the same
209. 6:59as x y
210. 7:00that's this term that's the commutative
211. 7:02law here okay
212. 7:03so i got that away this is this becomes
213. 7:06x y
214. 7:07x x becomes x what's that item potent
215. 7:10item potent and x or x y
216. 7:14is just x that's this guy that's the
217. 7:16uniting theorem therefore
218. 7:18this is also this kind of is used to
219. 7:20prove that guy so
220. 7:21the summary of these is that you
221. 7:24probably saw that before you saw it
222. 7:25before you saw it before
223. 7:26this is new this is new you probably
224. 7:29didn't know that one now you know this
225. 7:31one
226. 7:31this is kind of cool if you ever have an
227. 7:34x term
228. 7:35or something else that has an x in it as
229. 7:37well cancel it out
230. 7:39if i have an x term times something that
231. 7:42has an addition of x terms i can cancel
232. 7:44out as well
233. 7:44you just get x that's kind of cool the
234. 7:47last one is really powerful and you're
235. 7:49going to see this
236. 7:50a lot in logic de morgan's law this is a
237. 7:53kind of neat thing
238. 7:54this says what this says you know this
239. 7:57gate is right by the way right here
240. 7:58watch this
241. 7:59this gate is a nand gate do you get this
242. 8:04this says it's an i first take
243. 8:07x times y x and y this is an and
244. 8:10and then i put a bubble at the end
245. 8:12that's the bubble at the end
246. 8:14so this is the same as watch this
247. 8:17an or gate in which the bubble
248. 8:21is in the on the input okay x
249. 8:24and y and here's the output
250. 8:28here's how to memorize this it's pretty
251. 8:30cool you can prove this in logic but
252. 8:31here's a way to memorize this
253. 8:33it's kind of fun i take my inversion
254. 8:37and i distribute it to all
255. 8:40three terms
256. 8:44so i had this x and y and i i invert
257. 8:47everybody
258. 8:48if i invert everybody this
259. 8:52becomes not x x becomes not x
260. 8:55and becomes or and
261. 8:59y becomes not y the same thing on this
262. 9:02side
263. 9:02i had x or y and i invert the whole
264. 9:05thing again this is the same as a nor
265. 9:06gate
266. 9:07and i can it's the same as an and that
267. 9:09has x and y inverted on the inputs so i
268. 9:11can draw here same idea
269. 9:12so this is the and this is the same as
270. 9:16here's my this with that these are the
271. 9:18same
272. 9:20why i take my not and i apply it to
273. 9:23every term including the operator so
274. 9:27this becomes not x this becomes i invert
275. 9:30addition to b multiplication i invert y
276. 9:33to b not y
277. 9:34that's the way to memorize that it's
278. 9:35pretty cool de morgan's law
279. 9:38so let's do an example here we go y is
280. 9:41a b or a or c is that simplest form
281. 9:45let's see well look at this wow i can
282. 9:48now
283. 9:49take this and remove the a
284. 9:52i can distribute i call it reverse
285. 9:54distribution reverse distribution there
286. 9:56take that this a all right by the way
287. 9:58this silently was a times one
288. 10:01okay now i have a times b plus a times 1
289. 10:04i can take the a's away
290. 10:05that's both distribution and identity
291. 10:07because a is really a times 1.
292. 10:09the law of ones says that a times 1
293. 10:12is just i'm sorry b plus 1 i'm sorry
294. 10:15let's go back b plus one is just one
295. 10:19b or one is one we kind of saw that that
296. 10:22was the law of ones
297. 10:23and a times one is a that's kind of
298. 10:25remember that so there's only a coupling
299. 10:27to memorize from the slide before
300. 10:28if you go back here the law of zeros and
301. 10:31ones is
302. 10:32remember that one probably i item potent
303. 10:34you probably need to memorize that one
304. 10:36you know this one you know this one
305. 10:37you know this one this one you might
306. 10:39need to remember complementarity maybe
307. 10:41you didn't know that before
308. 10:42distribution you probably know this one
309. 10:44you probably didn't know this one so you
310. 10:46need to know that one
311. 10:48uniting theorem also need to know so
312. 10:50know that one that one and de morgan's
313. 10:51laws it's really cool so there's some
314. 10:52new ones you need to know
315. 10:53from this as you go forward yielding
316. 10:57this guy i i think of this as like
317. 10:59dipping your hands in massage oil and
318. 11:01you massage
319. 11:02you you're working through you probably
320. 11:04some nice music let's cue the music
321. 11:07welcome to my massage clinic i'd like to
322. 11:10give you
323. 11:10and make you work all the kinks out of
324. 11:12your muscles
325. 11:13i see your muscles are very very very
326. 11:16tight
327. 11:17let me try to work those out hours later
328. 11:20look at you you walk away at just a plus
329. 11:22c do you feel better
330. 11:24thank you i'm so happy please leave a
331. 11:26tip in the tip chart wonderful
332. 11:28okay so that's the idea if you can use
333. 11:31that's why we use it okay pretty cool
334. 11:33that's it
335. 11:34uh next lecture is on canonical forms
336. 11:36we'll see you there