Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
DAN GARCIA
And welcome back. Now let's look at some of the laws of Boolean algebra. What are some of the rules we'll use?
What are some of the principles, properties, identities we're going to use for Boolean algebra? I love this.
Let's go one by one to take it really slow to make sure you understand how each one works. So there's kind of a parallel set of laws that are actually interesting in this way.
So there's a beautiful duality that comes to the front when we're talking about Boolean algebra.
The duality is parallel universes, yin-yang, good versus evil, dark side and the light side of the force. You have here 0 and 1, AND and OR.
Okay, so a lot of times you're seeing even these rules have kind of one side versus the other side of that. So let's take a look. The first is the law of complementarity.
This says x and it's complement. What is the property when you multiply them or when you add them? Can you ever have a case where you can be both true and false?
I can believe both x and not x at the same time? Never happens. So that's 0.
Contrast that with what happens — I'll be happy if I have a burrito for dinner or if I don't have a burrito. Well, guess what, you're always going to be happy.
Because one of those is going to be true. If either one is going to be true, either one is going to be there, x or not x. Yep, that's always 1.
So that's actually kind of neat. So we can actually match that to here. Law of 1's and 0's.
x and 0 is 0. I have to be x and false. It can never be — the false kind of cancels it in a way. So x and 0 is definitely 0.
x or 1 is 1. x or always true. Well, that's true. In fact, I've actually written code where I was testing some loop, some test, x.
And I wanted to go and make sure you hit this test and go in there. I would literally write, in my code, I had my test, x, and then I would say, or 1.
And I know if it's or 1, meaning or true, it's going to go into that piece of code.
And if I have a piece of code that isn't x, I never want it to go, I would say and 0.
So I actually used these a lot in my coding to have it either always go in the loop to there or always get out of the way.
And I'll make a note to say, take this out later when production code is out there.
But if I just want to, really quick, make — rather than delete the x and write true, I'll actually say and 1 or I'll say and 0 or or 1 to either never have to go in the loop or, yes, always go in the loop.
Kind of cool. This one is from math. Nothing I need to tell you about there. Identity — identity of multiplication is 1, which is and.
And is true. The identity of or, or addition, is 0. So it's like saying x or false is still x. So the identity of or is false.
The identity of and is true. That's kind of neat. So if I have this big and, like the accumulator was adding things together, the identity of addition is 0.
So I initialize it to 0. If I'm going to and things together, what do you initialize it with? Right there, you initialize it with true.
If you initialize with 0, I don't care what else you have here, it's 0.
I've got this one.
And this one is fun. I'm going to play this song for you. Let me play. Ready?
Here we go. 3, 2, 1.
VIRTUAL ASSISTANT
Idempotent.
DAN GARCIA
Let me play this here for you. This is kind of a fun thing.
VIRTUAL ASSISTANT
Idempotent.
DAN GARCIA
You hear that? Idempotent. Okay, this just basically says x and x is not two x's. x times x would be x squared in some other world.
But this is x and x is just x. It's going to be x and also x. Well, there was no new information there. x or x, same thing.
No new information. Idempotent says this just replaces anything of the same with itself. This is the commutative law. I've shared that before.
That's a principle now. It isn't necessarily true, but it is true in the Boolean algebra — it's true in mathematics, it's also true here. I showed you that.
We have associativity. We have this. This is the same. It doesn't matter how you parenthesize things.
Also doesn't matter how you parenthesize the addition. That's not new and not special. All right, distribution is kind of cool.
This means that I can take x and distribute x to both y and z, and I can also reverse-distribute. I have a common x.
I can pull the x out to have the x in the front. Now, this is the weird — what's the equivalent on the other side? It's this rule.
Look at this rule. This is a really interesting rule, which I can prove for the other terms. Let's actually take a look deep at this rule. Well, I start over here, x this.
Let's do the FOIL method. This is xx plus xy plus that's outside, right, xz, plus yz.
Okay, let's start using some rules. I don't know, what do you see? Anybody see the idempotent rule? x times x, that's just x.
How about x or xy? Anybody see this rule before? Where's the x or xy? Actually that's this one.
That's the uniting theorem. We can get to that in a second. Here is y and z. I'm trying to get to x plus yz.
So this is x or. Okay, I'm going to skip. I'm skipping to the uniting theorem.
Here we go, uniting theorem, which says xy or x is just x. So meaning — it says, okay, it's true when x is true. It's also true if x and y is true.
But you knew it was true when x was true already. So this is no new information. The y doesn't help at all. That's just the same as x.
So if you add this xy term, it's just x. If I take that, this is x or xy or xz. This, because of the uniting theorem, just becomes x.
Therefore, this distribution law, x plus yz, is just x plus yz. So you kind of need the uniting theorem to simplify that side of the distribution.
And similarly, this uniting theorem on the right side says — so let's do it, okay — x or y times x. What is that?
This means x and some other thing that has an x in there. Well, why is that the same as just saying x?
Why can I just drop that off and write a 1 there, or even just cancel it?
Why can I just cancel this term and write a 0, and why can I cancel this term and write a 1? Because x times 1 is x. Why?
Well, let's do it. Let's distribute this out. This becomes xx or xy. Actually, it becomes yx.
I can do this right. Well, yx is the same as xy. That's this term. That's the commutative law here.
Okay, so I got that away. This becomes xy. xx becomes x. What's that?
Idempotent, idempotent. And x or xy is just x. That's this guy. That's the uniting theorem.
Therefore, this kind of is used to prove that guy. So the summary of these is that you probably saw that before, you saw it before, you saw it before.
This is new, this is new. You probably didn't know that one. Now you know this one. This is kind of cool.
If you ever have an x term or something else that has an x in it as well, cancel it out.
If I have an x term times something that has an addition of x terms, I can cancel it out as well. You just get x. That's kind of cool.
The last one is really powerful, and you're going to see this a lot in logic. DeMorgan's law. This is a kind of neat thing.
This says — you know what this gate is, by the way, right here? Watch this. This gate is a NAND gate. Do you get this?
This says — I first take x times y, x and y. This is an AND. And then I put a bubble at the end. That's the bubble at the end.
So this is the same as — watch this — an OR gate in which the bubble is on the input. x and y, and here's the output.
Here's how to memorize this. It's pretty cool. You can prove this in logic, but here's a way to memorize this. It's kind of fun.
I take my inversion and I distribute it to all three terms.
So I had this x and y. And I invert everybody. If I invert everybody, this becomes not x. x becomes not x. And becomes or.
And y becomes not y. The same thing on this side I had x or y. And I invert the whole thing. Again, this is the same as a NOR gate.
And it's the same as an AND that has x and y inverted on the inputs. I can draw here the same idea. So this is the AND.
This is the same as — here's my this with that. These are the same. Why? I take my NOT, and I apply it to every term, including the operator.
So this becomes not x. I invert addition to be multiplication. I invert y to be not y. That's the way to memorize that.
It's pretty cool, DeMorgan's law. So let's do an example. Here we go. y is ab or a or c. Is that simplest form?
Let's see. Well, look at this. Wow, I can now take this and remove the a. I can distribute — I call it reverse distribution.
Do reverse distribution there. This a — by the way, this silently was a times 1. Now I have a times b plus a times 1. I can take the a's away.
That's both distribution and identity, because a is really a times 1. The law of 1's says that a times 1 is just — I'm sorry, b plus 1.
I'm sorry, let's go back. b plus 1 is just 1. b or 1 is 1. We kind of said that that was the law of 1's. And a times 1 is a.
That's kind of — remember that. So there's only a couple of you need to memorize from the slide before.
If you go back here, the law of 0's and 1's is — remember that one? Probably idempotent, you probably need to memorize that one.
You know this one, you know this one, you know this one. This one you might need to remember, complementarity. Maybe you didn't know that before. Distribution, you probably know this one.
You probably didn't know this one. So you need to know that one. Uniting theorem, also need to know. So know that one, that one.
And DeMorgan's law is just really cool. So there's some new ones you need to know from this as you go forward. Yielding this guy.
I think of this as dipping your hands in massage oil, and you massage — you're working through. You play some nice music. Let's cue the music.
And you hear, (GENTLY) welcome to my massage clinic. I'd like to give you — and work all the kinks out of your muscles. I see your muscles are very, very, very tight.
Let me try to work those out. [MUSIC PLAYING] Hours later, look at you. You walk away as just a plus c. Do you feel better?
Thank you. I'm so happy. Please leave a tip in the tip jar. Wonderful.
Okay? So that's the idea. If you can, use. That's why we use it.
Okay, pretty cool. That's it. Next lecture is on canonical forms. We'll see you there.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.