You should look at the syllabus and find out what it's all about, but traditionally this course has got a funny history. Discrete math is a hodge podge of different topics. If you talk to professors in the last ten years they have different opinions. They feel like, well we shouldn't have a course in discrete math because we have a course in logic, and we have a course in combinatorics, and we have a course in graph theory, and we have a course in analysis of algorithms, and what are you doing?
You're doing little bits of all those courses and calling it discrete math. And this was kind of a popular argument, and some schools did not develop a discrete math course because of that. As the years went on, even those kind of diehard people with those arguments kind of gave in and said, well, you know what?
All these techniques kind of lead toward things that come up in computer science, and it does make sense to put them all together under one rubric and call it discrete math. And there is something in common with all these different areas, graph theory, combinatorics, logic, number theory. Something in common with all of them.
I'd say the thing that's in common with them the most is that the course is about counting. It's about counting things. Counting things is usually pretty easy. I can count the number of people in this class.
You're 36 people. That's simple. But there's hard things.
to count. And counting comes up as a separate topic in this class in about a week or so. We talk in lots of detail about it. There are two main things that are clever about counting.
One is noticing when two things are the same. counting things that seem like they're separate, but they're really the same. And then the other part is developing all sorts of clever tools to count stuff that just doesn't seem easy to count.
And we'll get to those things. So what's an example of discrete math, an example of counting? Say you have 36 people in a room. And you have 36 people in a room.
And there's a job I need to get done. Like Xerox these lecture notes. Every day we're going to Xerox lecture notes, but say we need two people to do it.
I don't know why two people walked out before. Well, you need two people to do it. And every day I need to send a different two because I don't want to show any favorites. So how many different ways can I choose a pair of people to go xerox my notes out of 36? That's a question of counting.
We have to count that. It's more than 36, and we'll figure out a way. We'll figure out a way today. We'll do it in a few minutes.
Another question. Say I go to a bowling alley. That's what the pins look like in a normal bowling alley. But in a baby bowling alley, it looks like this. So the kids can actually knock all the pins down.
And in an extra super bowling alley, for people who get 300s regularly, they do it like that. Now you can knock down 15 pins. So this is called the one lane, the two lane, the four lane, the five lane, because it's got five rows. So how many pins are in the lane that's numbered five or numbered? n.
How do you count those? So these two problems are the same. If I went to the 36th lane and I counted the number of pins in the 36th lane, that would be the number of pairs of people I could throw out of this room in different ways. It's not too hard to see that these problems are the same, and we're going to see it in just a few minutes, so we'll get back to it. But I want to give you an example of a problem of counting which is much, much harder to see the connection between, which you won't see it until much later in the course.
And you'll think about it a lot and try to see a connection. Here you might even figure it out before I get to it, but the harder one is trickier. Here's a harder one. In scheme, you guys learned about binary trees, right?
Did you? Tell me you did. All right, so here's a binary tree with three nodes, right? Here's another one with three nodes. Are there more?
Right. Any more than that? No, right? I think that's it. Well, the directions matter.
So we count these are different. Oh, yeah, good. Good. Do we get 5?
5 is the right number for 3 nodes. If you add another node, you get a lot more trees. And in fact, well, why is it useful to know how many binary trees there are with n nodes? Because you might give a project to somebody who's trying to figure out, say, a minimum spanning tree of a graph. a tree that's going to go over a graph and have the least weight on all its edges.
It's a very common problem. You'll study it in algorithms. And let's say somebody's idea of a good algorithm is, well, I'll just try all the trees and pick the one that has the minimum weight. Okay, that's an idiot algorithm.
because the number of trees for n nodes is something on the order of 4 to the n. It's huge. The minute you get up to a hundred nodes, this algorithm will take a few centuries to run.
So it's no good. You need to know how to count the trees because you need to know sometimes what not to do. There's other reasons why you might want to count binary trees.
Number of binary trees on n nodes. Here's a different problem from linear algebra back two months ago. If I'm multiplying three matrices together, let's assume they're square matrices, so they all can multiply one by the other. How many different ways are there to multiply them?
Well, you've got to multiply them left to right, right? But you can either do it this way, and then the last one, right? How else could you do it? Good. Good, Michael.
Right? If I put another one in, if I put another array in, there'd be even more ways. Okay?
It turns out that, well... If there are three arrays, it corresponds to the number of ways there are of having two node binary trees. Four arrays, three node binary trees.
Five arrays, four node binary trees. There's a relationship. They're the same. This connection is not obvious at all. You might get some intuition.
Maybe it makes some sense, but it's not obvious. And you're going to see why this is true much later in the course when we talk about combinatorics. But this is an introduction. This is what people who do discrete math care about.
They care about problems like this. They don't care about what's the best way to build a jet fighter airplane so that I minimize the resistance on the air wings. That's a continuous math problem. what's the ratio of height to width of a cylinder that has the most volume. That's a Campbell's soup production problem.
That's a continuous problem. It's not discrete math. Discrete math deals with stuff you can count, things you can get your hands on.
And ironically, sometimes getting your hands on something makes it actually even a little more difficult. Things you can count sometimes are really, really deep and tricky. Okay, questions about all this stuff? In doing discrete math, you're going to be doing proofs. Some of you have never done proofs before.
Some of you have. So we need to talk about what a proof is. It's a little tricky.
In reality, a proof is no more than just convincing somebody else that something's true. But mathematically, you'd like to be able to be a little more rigorous than that. I am not going to teach you this month how to be mathematicians.
I'm going to teach you about discrete math. So when I ask you to prove something, the definition that I want to use for a proof is you have convinced me or the TA or one of your colleagues, according to the standards of our class, that we believe that what you just said is true. It's a very vague definition, but we're not going to have you write formal, formal, formal proofs. It'll come close, but ask yourself whether you've been convincing.
Real proofs can be done at the bottom level, turning everything into logic, which we'll talk about later today. And nobody ever writes a proof like that because it's incomprehensible. The way you really explain a proof is you do interactively.
I give you some intuition. I do examples. Now then, if you want to... to write the proof up, what would you do? You would cover up all your tracks of how you discovered the theorem because there'd be all these dead ends.
You'd clean it all up. You'd present it from the very beginning to the very end in a nice, beautiful way. Lemma, lemma, theorem, corollary, conclusion. and the person who would read it on a desert island all by themselves could reconstruct your result because you've been completely rigorous and careful, even though they would take much, much longer to understand it than if you just sat with them for 10 minutes explaining your idea. So the best thing is to have a combination of both.
In class, I'm going to be explaining to you how things work. When I write proofs on the board and I explain it, they are not meant to be publishable. They're not meant to be reconstructed.
If you want to see good proofs for things, look in the textbook. That's where people have... have really written it out in detail so that if you were by yourself, you could read it and figure it out. There needs to be an understanding and an interaction when I'm explaining it, and that is always true. And you should always try to do your proofs, not by deciding what I'm going to write down next step, but by thinking of the idea and writing an English paragraph.
Just being communicative, and you'll get it right. All right, so in order to explain this, I'm going to do examples of two proofs. Really cool proofs are proofs by contradiction. Here's the first one. I'll explain what a proof by contradiction is as I go through these.
This proof is originally due to Aristotle, as far as anyone knows, and it's been copied many times and attributed to lots of other people, but he was the first one, I think, to actually write the argument down. A rational number is a number that can be written as a fraction, A over B, like two-thirds is a ratio. rational number.
1.4 is a rational number because it's 14 tenths. An irrational number is a number that can't be written as a fraction. So you need to know if there are any numbers that can't be written as fractions, and the square root of 2 is one of those numbers.
So here's a proof that the square root of 2 can't be written as a fraction. And it's a very clever proof because trying every fraction and seeing that it doesn't work is not a good proof, right? You do that forever.
So you need a better proof. So here's how the proof works. It's really clever.
The proof says, look, let's assume for the moment that the square root of 2 can be written as a fraction. And I'm going to show you something very strange happens. I'm going to convince you that if you can write the square root of 2 as a fraction, then the top and the bottom of that fraction both have to be even.
Well, that's a very strange fraction. Is there any fraction that the top and the bottom have to be even? I can just turn this into 2 over 1. Now the top and the bottom aren't even.
But I'm going to convince you that no matter what you do, when you're all done giving me the fraction, the top and the bottom have to be even. There is no fraction in the whole world where the top and the bottom have to be even. You can always turn it into a fraction where the top and the bottom aren't even. So I'm going to assume... that this will give us a horrible contradiction, and I'm going to prove to you that the top and bottom have to be even.
Another way to look at it, the way some people say it is, let's assume the square root of 2 equals a over b, where a over b has already been put into lowest terms. okay, you think you've got a fraction you come back to me and say, shy, I've got a fraction I go, well do me a favor, put it into lowest terms before I start my argument, and you go, okay so now it's in lowest terms, the top and the bottom can't be even, and now I'm going to convince you they have to be even that proves that you lied that proves that the square root of 2 is really irrational that it can't be equal to any fraction alright, so let's do it here's how the method goes, it's really a very straightforward proof and it's magical in a lot of ways let's square both sides of the equation I should tell you that when I say it's an easy proof and it's magical, I could make a proof that I would be doing this and we're all friendly together, and there would be a very subtle flaw somewhere in the middle, and everybody would miss it. So never believe anything I say.
In this case, it really works, but there are proofs that have subtle flaws. And one of your problem sets, I ask you to find subtle flaws in these following proofs, and you'll have to find them. 2 equals a squared over b squared, and now 2b squared equals a squared. All right, so what does that tell you about a squared?
It tells you that a squared has to be an even number because it's twice something. In fact, we can even use that as a definition of an even number. An even number is anything you can write as 2 times something. There's other definitions, but that's one. So this implies that a squared is even.
And now we need a little theorem, or sometimes what's called a lemma, a helper theorem, something that helps us along the way. If a squared is even, we want to know what a is. I'd like to get the fact that a is even.
So is that true? If a number squared is even, does the number have to be even? Let's do some examples. 16 is even.
Does that mean 4 is even? 36 is even. 6 is even. Is it always true? Do you believe it's true?
Why do you think it's true? Okay, yeah, 2 can't be broken into 2 parts. I guess we'd have to argue, but that's one way to look at it. Good.
Another way to look at it is, well, what else could it be if it wasn't even? It could be odd, right? If an odd number got squared...
That would have to be odd. That's odd, yes. You can prove that an odd number squared is odd.
Take any odd number. It's something that looks like this. And square it out using the algebra that you learned.
And you'll find out that it equals 2 times something plus 1. I'm not going to do the details because I asked you to do it in a problem, so you'll do it later. But this implies that A is even. And I'll put a little star here.
That's based on the lemma that if a number squared is even, then the number is even. So now we've got that A is even. And if A is even, I'm going to write it as 2 times some number.
So I get 2B squared equals 2 times some number squared. A equals 2K. Does everybody see what comes next?
2b squared is 4k squared. b squared is 2k squared. And now by the same argument as before, b squared is even, and then b is even.
And the world explodes because you lied. You told me you had a lowest terms fraction equal to the square root of 2, and I just convinced you that a is even and b is even. So what you claimed isn't true.
Therefore, there's no way anybody could ever get a fraction equal to the square root of 2. I just took any possible person's claim and debunked it. This is called a proof by contradiction. I assume it can be, and I derive it. derive a contradiction that I have a fraction where both halves have to be even, even though the fraction is in lowest terms.
That can't be. That contradicts the assumption. Other questions about this proof?
The next proof is about number theory, and I wanted to mention, besides graphs and combinatorics and logic and all the different pieces of this discrete math course, there's one really cool piece that we'll do toward the end that I think everybody will like. Number theory... has traditionally been one of the most elegant and abstract and just more beautiful areas of mathematics. One of the areas where if you were going to pick on an area of mathematics that have no application at all, it would be number theory. There was a famous number theorist, Hardy, who wrote a big paper at the end of his life, basically trying to, it was called A Mathematician's Theory of Number.
apology and it's all about how his life was worthwhile because he's an artist and he's not curing anybody from cancer but what he does is beautiful and it's beautiful in the same way that music is beautiful it's worth reading it's only about ten pages long it's reprinted in a lot of places I'm sure you could find it on the web. It's a very nice work, and in it he actually goes through this proof as an example of beautiful mathematics. The point of this is that it turns out serendipitously that number theory is at the complete heart of the most practical application that runs on the web. The thing that lets you send your credit card over to a company and have it be encrypted safely is based on three theorems in number theory, one called Fermat's Little Theorem, and one, the theorem about congruences. Stuff that was completely never expected to have an application ends up being the crux of public cryptography, where I can safely have somebody encode something and I can be the only one to decode it.
So we're going to go through the details of that and do the number theory behind it. That's one of the last topics we'll do. Right now I'm going to do the second most famous proof in math, that there's an infinite number of prime numbers. This proof is due to Euclid.
On the site, I have a link to Euclid's Elements. Euclid wrote a 14-volume masterpiece called The Elements. It's the heart of all Western mathematics ever since then.
It's the beginning of things. thinking of mathematics in a rigorous way with proofs. In his 14 volumes, he has a book on number theory, a book on geometry, a book on solid geometry, a book on arithmetic, etc. The way he structured his books is very much like a symphony.
He starts with definitions and postulates and works his way up through theorems, and the early theorems are very simple and trivial, and he works his way up, and he's got a climax theorem at the end. All right, so the climax theorem in the geometry book is the Pnythagorean theorem. The climax theorem in one of his number theory books is a theorem about perfect numbers.
And one of the climax theorems in one of the other books is that there's an infinite number of prime numbers. So this is a beautiful theorem. It's easy to explain. It's the same kind of proof.
It's a proof by contradiction. So I want to do a little preliminary before I explain this proof to make sure everybody's able to do this quickly. So, here Greg, easy question.
I'm putting you on the spot. Is that divisible by 2? Yes or no? No.
Too easy? 6 times 128,136 plus 1. Who knows if it's divisible by 2? It's not. Why is it not? Because this part's divisible by 2, and there's 1 left over.
2 times 3 to the 512th plus 1. No, it's not even, because this part's even, and you're adding 1. What if I have 3 times 859 plus 1? Is that divisible by 3, that number? No, because the first part's divisible by 3, and there's 1 left over.
I want this to seem obvious, because if I just wrote it up, it might not seem obvious, but I want to make sure you think this is obvious. Writing numbers like this is a sure way to know whether they're divisible by the number that's sitting out here. You can just look at this point. What if I change this to 2?
Is it divisible by 3? No. if I made this six? Is it divisible by three? You're smart. It's like, get on with it, you're saying.
Come on. All right, so here's Euclid's proof. Euclid says, look, there's not an infinite number of prime numbers. You come to me, you come back, you'll work really hard at night, and you go, I'm certain there's a finite number of prime numbers, and here they are.
So if that's what you claim, I claim you should list them for me. And I'm going to do this by example, but this works in complete generality. Here's your list. Your list starts with 2, 3, 5, 7, and it ends up at some point.
Let's say the last one you come up with is 31. We could call it n, but I think it'll be easier if I just write 31. Say that's your list of prime numbers. And here's what I'm going to do. I'm going to multiply all these numbers together, or Euclid will multiply all these numbers together, add 1 to them.
Is this number divisible by 2? No. Right?
Because this whole... The whole thing! You were smart up until the second one.
This part is divisible by 2, but when you add 1, it's no longer divisible by 2. Is it divisible by 3? This part is, because it's got a factor of 3, but you add 1, so it's not divisible by 3 anymore. In fact, it's not divisible by any of these prime numbers. You don't have to say prime numbers.
It's not divisible by any of those numbers, whether they are or not prime. But I just made a list of the prime numbers, so there are no other numbers. But you're right.
All right. So what? So what do you know about this number? You sure it's prime? Be really careful.
It's either prime itself, or it could have a factor, but if it does have a factor, it's not 2, 3, 5, 7, et cetera, up to 31. So it's pretty simple. is actually a little bit subtle. It's not that he has constructed a number for you that is definitely prime that's bigger than yours. He's constructed a number that either is prime, which shows that there's another one you missed, or has a factor which itself is a prime number different than all of these, which means you missed one. Everybody got those two possibilities?
I'm focusing on this because one of your problems in the problem set is write a scheme function. What kind of scheme function would you write to solve the following problem? You want to write a scheme function to figure out the smallest prime number for which this... ends up actually not being a prime itself.
Everyone understand what I mean? Sometimes this ends up being a prime number. Sometimes it ends up having a factor which is bigger than 31. What's the smallest number for which it's going to end up not being a prime?
Maybe it always ends up being prime, right? Well, it doesn't. but what's the smallest number?
What problem set does that fit into in last month's course? Streams, right. It's screaming out streams, because you want to make the stream of prime numbers and then construct the next one with the next part of the stream.
If you had just finished problem set 8, you could probably go back and do this in 10 minutes. By the time you do it, it'll be a week since you did problem set 8, so it'll take you half an hour to reconstruct it. But that's a cool problem to work on.
And I'm trying to connect up all the different threads of this year together. And I think that'll make a good little braid. So at first, when you see that, you think, well, it could be, or you could think, if you were thinking really hard, it could have as a factor some number that wasn't one of those primes, a non-prime number, right?
It's only when you think that all those non-primes break down into those primes that you... Well, I guess we have to prove beforehand that every number can be divided into factors that are prime numbers. So there's going to be one of those prime factors that isn't one of these numbers through 31. But yeah, you've got a point. There's more. I have to say, this theorem came after a bunch of other theorems that are necessary.
You're right, Chris. Other questions? If it was not directly a prime number, would it have to contain at least two prime numbers that were not in our list? No, but this way are a few.
Okay, But even if it did have to contain two, so, right, I mean, right, missing one or missing two, all we need is one to get to infinite, right? Because this could repeat itself, right? I mean, what if you took this prime number and added it to your list?
Maybe I should point this out. This is a completely general argument. If you take this prime number, now that I've pointed it out to you, and add it to your list and say, oh, I forgot that one, here's my new list.
I would just do, I wouldn't even come back into the room. I'd just say, well, why don't you replay that argument for yourself again, right, with a new number and add it to your list, and you just get another new number. The point is that this argument will work repeatedly forever, and you can never get them all. It would, but the subtlety is that the new number might not be at the end of the list. It might be less than.
It could be in the middle. Right. Absolutely. What's more, that idea of always recreating a new one is actually an idea that comes up in one of the most fundamental proofs in computer science. The proof that there are programs that can't actually, there are things that you'd like to program that can't actually be done, that don't have a program for that.
And the idea is you list all the possible programs and you prove that there's one program that's missing. And if you include that program in there. You list the programs again, and you can conclude that there's another program that's missing.
There's always things you want to do that there are no programs for. And it actually is a little reminiscent of this proof. That's called the halting problem. And you'll see it.
You'll see it in this course a little bit. You'll see it in the theory of computation course. You'll see it. But I'm going off on my tangent.
New thing. We're going to go back to that counting idea, the bowling pin stuff and the sending out pairs of people from this room. And I'm going to show you that those two.
two are the same. So how many pairs of people can you pick from a group of n? How many pairs from N?
If they have... Right, right. We're sending them out as a group.
We don't care which one gets to the door first. Right. Right, so if I send out Todd and Doug, it's the same as sending out Doug and Todd. That counts as one. All right?
We'll think of it as lunch dates. Right, we're not going to... Ooh.
All right. I'll just quit there. All right. Let's count this.
How many pairs are in? Here's one way to count it. There's a lot of ways to count things. One way to count this is just brute force. Here's what I'll do.
I'll include myself in the group. I get sent out, and I can go with every one of you. you people in this class?
So me and Michael, me and Sharon, me and Sam, etc. Now let's say there are n people in the class. I'm one of them. How many people can I go with? n minus 1. That's fine.
That takes care of me. I'm now out of the picture. So now we'll go down the list.
We'll go to Michael. Michael can go out with how many people? An additional n minus 2, because we already counted him going out with me, right? So he only gets to connect with the people that are left over, n minus 2. And then Sharon can go out with n minus 3. And sooner or later, we get all the way out to Brian over there in the corner.
And the only person that we haven't matched him with is Tara. So it ends up being plus 3, plus 2, plus 1. Okay? You add all these numbers up, you'll find out the number of pairs of things you can pull from n.
Now, this is also the number of bowling pins in the appropriate alley, right? 1, 2, 3, you can see it. So those two now are the same. You can see they're the same.
These kind of numbers are called triangle numbers because they look like triangles. You're already familiar with square numbers, right? 4, 9, 16. So these are triangle numbers. It would be nice to get a formula for the triangle numbers.
The formula for the square numbers is n squared. Right? The formula for triangle numbers is, well, I don't know. By the way, there are pentagonal numbers and hexagonal numbers also, and you can, that's what mathematicians do. You come up with a good idea, you generalize it, you connect it to other ideas, you go wild.
But we're just going to work on triangle numbers. Triangle numbers. We'll call the nth triangle number to be equal to this, 1 plus 2 all the way up to n minus 1. Okay, that's the nth triangle number.
It's the number of pairs you can choose from n people. It's the number of bowling pins in something with n minus 1 rows. Okay?
So let's get a formula for this. We are not going to prove this by induction, even though that's the most typical. example of showing a proof by induction.
A proof by induction is a very common proof, which I haven't showed you yet. I am going to show you a proof by induction later today. We're going to spend a whole day on induction later on in the course. But today I want to prove this in other methods.
Because just because you can prove something by induction doesn't mean it's the easiest way. Induction is one technique, and you'll learn when it's the best and when it's not the best. And we're going to stay away from proving this by induction. We're going to try to prove a formula for this in another method. And let's see.
I have two methods here. Let's see. Let's try this method.
Let's try the geometric method. I'll do an example and then we'll generalize the example. Here's a method where the number of numbers is even. Let's do a geometric method. Everybody see what I did?
I turned a triangle into a rectangle. Because I know it's an even number, so I can do that. It's going to be half. What's the dimensions of my rectangle here, if I did this for a general n?
If this was n, n dots, and it was a triangle, then when I turn it into a rectangle, what are the dimensions of my rectangle? Good, Chris, the side here is n over 2 because I've cut it in half. And what happens here on the bottom?
I get this one extra guy coming up. So if it's even, if n is even, n even, I get a formula that's equal to n over 2 times n plus 1. Let's take the same argument and check what happens when n is odd. Let's do an example. How do I do this with the rectangle argument?
I'm just going to take the top part, not including this. I don't have a middle spot, so I'll just go one above the middle, and I'll put it down over here. What's the dimensions of my new thing now? This is still going to be n, right? And what's this part going to be?
n plus 1 over 2. There's a proof. It's a geometric proof. Now, look at this bizarre formula.
I have two cases. This is for n is even. This is for n is odd.
You're coming out of ninth grade. Look at these formulas. Are they the same?
They're identical. So why do I need to write them twice? And you're thinking, well, you don't, and now I know you don't, and it's just because the proof does two cases and maybe it didn't need to.
But there's actually a much more subtle point here. Now I can put on my history of math hat for just 30 seconds. In the 13th century, in the 14th century, when people wrote theorems like this, theorem 32 was this theorem, and theorem 33 was this theorem.
And nobody thought that was redundant because there wasn't any algebra. wrote formulas like this. Nobody could glance and see visually that these two were the same.
This formula, this theorem reads like this. If you add up an even number of numbers from one, increasing by one as you get to the last number, that equals half the number of numbers times one plus the number of numbers you have. And the other theorem reads, if you have an odd number, blah, blah, blah, that equals the number of numbers you have plus one. It just reads differently. It doesn't look the same.
In English, these two don't look the same. In math, they... do look the same.
This is actually a simple example of something that's very important in math. Notation can give you intuition. Good notation for an idea can lead you to the next step.
Bad notation can obscure the next step so that you don't see it ever. So be really careful with notation. There's good choices for notation and you'll see a lot of notation in this class.
That's possible. I'm not sure they would all do it. Actually, the truth is they have three theorems for this.
But yeah, you might be able to... You can certainly do better than this, even without algebra. Next stage.
There's a folklore story. I think I told you this story. A folklore story about Gauss, one of the greatest mathematicians of all time in the early 1800s, and that a schoolteacher told him to add the numbers from 1 to 100 together because he was a little bored in class and hoped that would keep him busy, and he quickly blurted out the answer, and it's really just this problem, asking him what the 100th triangle number was. Add the numbers.
from 1 to 100. And he did this quickly. And what a lot of kids rediscover when you tell them this problem... is that they pair numbers up on the two ends. 1 and 100 equals 101. 2 and 99 equals 101. 3 and 98 equals 101. And how many times do you do this?
Half as many times as you have your list. So that gives you, like, the classic n plus 1 times n over 2. Right? n plus 1 is the sum of the two numbers on the n, and you do it half as many times as there are things in the list.
And that's another way to look at it. There's a lot of ways to look at this theorem. You should remember this formula for adding up the numbers 1 to n for the triangle formula. It comes up again and again.
Yeah, Donna? What if 0 is on your list? Like, if you start with 0 plus 1? Does that change your n? It would, but the way triangle numbers are defined is that you start from 1. If we define triangle numbers to start from 0, then we'd have to change the formula.
No, you're right. It would change it. It would change it.
But we don't include 0. All right. So you might wonder at this point, you know, what the sum of the squares are, what the sum of the cubes are, what the sum of the fourth powers are. All these things are part of discrete math, and we'll get to them in time.
All right, but now I'm going to switch to a cool problem that we will prove by induction. Here's a puzzle. Here's a pancake, and you want to cut it into pieces with a big sharp knife. I cut it into two pieces.
If I cut it again, how many pieces do I get? Here's the rules about the cuts. Every cut has to go through each of the other cuts in exactly one place, and you can't cut through the same spot here again. The next cut has to go here, for example.
That's the rules about the cuts in this game. So let's make a little chart. Number of cuts, number of pieces.
If I make one cut, how many pieces? Zero cuts, one piece. Two cuts, how many pieces? Three cuts.
Four cuts. Ooh. We've got to do four cuts really carefully. Wait, what are the rules again? You've got to cut through every other cut exactly once, and you can't go through any points that are already there.
So maybe I should rearrange my lines. Is it going to be hard to draw it? Can I do it?
Like right here? Will that go through all the other cuts once? How many pieces do I get now? Here's a discrete math problem. What goes there?
N. What goes there? Here's a big hint. I wouldn't leave you in the lurch here. I gave you a big hint.
Well, what did we just do? We just did triangle numbers. What are they? One. What are the triangle numbers?
Three. Triangle numbers? Pnlus one.
Tn plus one. Question mark. Are we lucky? Or is that true? It's true, but we're going to prove it's true.
And we're going to prove it's true by a method of proof called mathematical induction, which is a method of proof that concentrates in a particular style of thinking. And I want to give you that. idea and do it in detail here. Here's one of the neatest things about proofs by mathematical induction.
Sometimes you can discover a theorem like this, even though you don't have the slightest clue why it's true. And you can prove it by mathematical induction because you concentrate on the proofs. on a particular aspect of where this comes from, even though you still don't really understand why the whole thing works out. And that's the coolest thing about a proof by mathematical induction. You can kind of not only discover the truth and prove the truth, but still feel like somehow it's kind of magic.
And that's okay. Look at the second column and see if you see a pattern. And if you don't see a pattern, take successive differences and you will see a pattern.
That's a good way to do it. That's true. That's a good way to do it. Let's follow Sam's idea.
Let's look at how many pieces we get here and see what's happening as we go and see if we can convince ourselves that it's an accident or not an accident. How many new pieces do we get every single time I add a line? Let's do it again.
I add the first line. How many new pieces did I get? One new piece.
How many new pieces do I get when I add the next line? Two new pieces. How many new pieces do I get when I add the next line?
Three. Why? How come I got three new pieces when I cut through that third piece? How come?
The rules are I have to cut through this line, and I have to cut through this line, the two lines that are there. Every time I cut through a line, what happens? There used to be one piece here, right?
I cut through that line, I got a new piece. There used to be one piece here. I cut through this line, I get a new piece.
There used to be one piece here. I cut through that line. I get a new piece.
So what happens is, if I have to cut through two lines, how many new pieces do I get? Three new pieces. If I have to do the next step, how many new pieces would I expect? I have to cut here through three lines. I would expect four new pieces.
Is that what happens? 7 to 11? 4. Good.
So now we have not only a conjecture, we have something that's plainly obvious that we've just kind of proven by this argument. Here's what we've proven. Let's call this Pnn. We'll call the pieces that you get with n cuts.
We've proved that Pnn is equal to whatever you had before. Sorry. Erase this, make sure we have plenty of room. Pn of n equals the number of pieces we had before, right? Pnlus how many new ones?
We had n minus 1 lines before. If we cut through all of them, we get one extra piece. So all together, how many new pieces? N.
This is something we just proved. This is a recursive relationship, a recurrence relationship. We're going to talk about solving equations like this later in the class, not today. What we're going to do today is prove the following theorem, Pnn equals Tn plus 1. And one of the things we're going to use in proving this theorem is this relationship that we've just proven.
Okay? Did we prove it? I think we proved it. I think every new line has to cut through the number of lines that were there before, which is n minus 1, and you get one more piece.
So you get n new pieces every time you add a line. I think that's a good enough proof. I don't know. If you don't think so, then I have to prove it better.
No, really. Is it not rigorous enough? What do you think?
Just intuitively also, whenever you did a new line, you could actually... The number of pieces you're adding falls neatly on one side of the line, and the number of pieces that were there falls neatly on the other side of the line. On the other side of the line, right.
I agree. You buy that now? All right.
The measure of whether our proof is right is whether we vote on it and it works. So that means whoever gets to be president next is going to be right. All right.
It's okay. There's some democracy in math. reviews on papers. All right, well, let's get back to this. Let's prove this is true.
Here's the method of mathematical induction. Let me give you some intuition behind it and then I'll show you how it works because it will seem a little magical. The idea of mathematical induction is you want to prove something for an infinite amount of cases.
In this case, for n equals 1, for n equals 2, for n equals 3, for all these cases. So rather than come up with a general argument that works for all of them, which may be hard to do, sometimes it's easy, sometimes it's hard, instead, let's concentrate trait on convincing somebody that if it were true for, say, the case of three, I could convince you in general that it would work for four. Let's come up with a general argument that shows somebody why the truth of the next case is definitely valid, as long as the truth of the last case was valid. If I came up with a general argument like this, then all I'd have to do is show you that someplace at the beginning it's true, and you could use that argument repeatedly to show the truth of all the subsequent cases.
That's the idea. focusing on the general case, focus on the transition from one case to the next. Sometimes that transition implies a very deep idea about the general case that you're going to have a tough time getting a handle on, but you can focus right on the transition. And you're going to see dozens of examples of this in this class. It's the most commonly used proof in computer science.
This is going to be a very short one and a very simple one, but we're going to go through it in detail. Here's how it works mechanically. We assume that the theorem we're trying to prove is true for this case, and we have to come up with an argument to show that, therefore, it must be true for the next case. So let's write it this way.
We'll assume that Pn of n equals Tn plus 1. We want to prove that the next case is true. That p of n plus 1 equals tn plus 1 plus 1. We want to go from here to here. This is going to seem a little funny to some of you.
Here's what you can't do. You can't say, oh, if I'm assuming this is true, then I'll just put in n plus 1 for n, and that shows that's true. That's not allowed. You're only assuming that it's true for this particular n, not for any other n in the whole world except for this one. Can you go ahead and then show that it's true for the next step?
So we're going to have to use other ideas, and hopefully this will help us. So here's what we're going to do. We're going to work with this and try to prove it's true. At some point, if we need this assumption, we'll work with it.
We're going to throw Pnn plus 1 equals Tn plus 1 plus 1. What do we know about Pnn plus 1? What's the only thing we know about it? It's Pnn plus the additional cuts that risk by...
Good. We can use this formula on p n plus 1. This we know works in general. Let's use this formula on p n plus 1. What does p n plus 1 equal? It equals p n plus plus n plus 1. Now let's use this assumption.
Pnn is equal to Tn plus 1. So this equals Tn. Am I getting this right? Tn plus 1 plus n plus 1. Okay?
So first I use this theorem, and then I use this assumption. I got this on the left. I'm looking to get this on the right. Am I almost there?
Tn. I just moved them around. What is this?
Tn plus n plus 1. If you have a triangle number up to n and then you add the next number on, you get the? The next triangle number. Tn plus 1. Pnn plus 1 equals Tn plus 1 plus 1. Three steps.
One assumption here. One assumption there. There and the definition of a triangle number. Where does the other 1 go, the other plus 1? The m plus 1 here is the next number that we add on to the tnth triangle number, so that gives you tn plus 1. There's a lot of words here that I left out, and this proof is going to seem magical if you've never seen a proof by induction before.
And I cleaned everything up, because I created this proof to seem magical. So I didn't give you any motivation or where we were going, I just made it look magical. And it's somewhat on purpose.
I want you to see how elegant and swift induction proofs are. We're not, right. But what I want you to realize is that you still need an idea here. And the idea here is using this recursive relationship for Pnn and then showing that you can get from this step to the next step. All right, Sam's right.
You do need to show that this has a starting point. So we have to show that this is true for a particular n. So let's show that it's true for a particular n. Let's start with n equals 1. Pn of 1 equals 2. What does T of 1 equal? 1. So 2 equals 1 plus 1, and that's true.
So it does have a starting point. It does work. This general method of going from one step to the next works over and over again. Look at it on your own. Study it.
Make sure you get the idea behind it. You're going to see a lot of things. Lots and lots of examples of this, some of which will be much more intuitive, some will be less intuitive.
But that's a proof by induction. Pnrove the connecting step. Math is not just some egghead sitting at a desk coming up with formal proofs.
And I don't mean that in any kind of a general way. I mean it. it, what it really is, is a scientist. There's experimenting in that.
I gave you problem sets that you are going to have to learn to think like a mathematician really thinks, instead of how you think a mathematician thinks. A mathematician doesn't think, oh, I get it now and I'm just going to write the proof line by line. A mathematician struggles, they discover, they experiment, they try things.
A lot of the problem sets I gave you are going to force you to experiment and try things and write programs to generate more data. And when you see the pattern and you think you have the truth, only then do you go back and try to figure out, hey, now that I think it's really true, why is it really true? And you know what? By that time, you probably have a pretty good idea why.
I'm going to switch gears now. Let's move away from proofs and our intro. I'm going to start on what I decided would be the first topic in this class, logic.
And I decided on this because another way to write proofs is to turn them all into logic formulas, where everything is represented by some variable, and we connect things by logical connectives, and we can actually turn it into a mechanical process. And there's a big area in computer science called automated theorem proving, and you do just that. You take statements, you turn them into mechanical strings, you write a proof. a program that can manipulate them in some logical way, and you come up with new statements. And one of the neat things the theorem prover once came up with, in geometry, for example, is a proof that if you have an isosceles triangle, these two angles are the same.
There's a lot of ways to doing this. The way most kids do it in high school, or whenever it is to put a little perpendicular bisector here and fold it on itself, that's one way, and do side, angle, who knows. what or hypotenuse, I forget, hypotenuse leg theorem. But this theorem prover came up with the following clever proof that actually makes you think twice. It said, well, triangle ABC is congruent to triangle ACB.
It took the triangle itself and it said it was congruent to the mirror image. And it got the result that way. And it didn't do it because it was clever.
It did it because the random collections of mechanized rule implications actually came up with a cool proof. It's true. You've got to look through 5,000 idiot proofs to come up with this.
But machines can come up with clever things as long as you don't mind looking at the unclever things. What I want to do now, though, is give you the basics of logic, the basics of Boolean algebra, the basics of representing things in logic, and this stuff is not... not only useful in proofs, but that's what mathematicians think about.
It's useful in computer science because it's the foundation for building circuits in a computer. It's the foundation for algorithms because the most difficult algorithm in the whole world is figuring out whether a particular Boolean formula has any set of values that makes it true. That's the first NPn-complete problem. You'll hear about that.
Actually, if you go to the talk later tonight at Harvard, he'll talk about that. It's useful in computer science because it's a way to model almost every kind of of computational problem. So you'll see this in a million ways. I'm going to start off with really, really basics of this, and here's the way it will work.
We'll consider variables to have some meaning, like w is it's wet outside, or this tie is colorful. I mean, something that has a value true or false. Either it's wet outside or it's not wet outside. And every variable in this Boolean world is going to have a 0 or a 1, a true or a false.
1 is usually true, 0 is usually false. And we can connect them in various logical ways. So, w is wet outside, r is it's raining. Let's put some words and things together. It's raining, and it's wet outside.
That looks like this. It looks like this. It looks like this. Thank This symbol, the up arrow, this symbol, the word and, and just multiplication used without anything, are all synonyms for and. This and this are both true.
You can check whether this formula is true by checking whether both R and W are true. It's raining outside and it's wet, only if both of those are true. This is what logicians use, this is what circuit developers use, and this is what you'll see in a lot of computer science books. Our book uses all three in different places, depending on what chapter you're in.
So keep in mind. So one connective is and. Another connective is or. Or is the word or, the symbol plus, or the upside down of the and.
I talked about notation before. There's a reason why people use this notation. Mechanically, we are going to be able to manipulate logical formulas the same way multiplication and addition manipulate.
There's a distributive property for multiplication and addition. It works the same for ands and ors. So there's a reason people use that notation.
Are there questions about this? Yes? It just looks slightly confusing that you've got the plus sign to mean or. So I should say what or means before you finish your question.
Or means that either this is true or that's true or both of them are true. It doesn't mean exclusive or, which is a different logical connective, meaning that either one or the other but not both. It means that one or the other or both.
Okay, but your question is why should they use plus for or? That seems like it should be and to you. It's just you get a bit of dissonance between the and. Because you think of plus as being an and because you're adding.
Yes, you know what? You're going to have to go into your mind and take that neuron that's used to that and twiddle it the other way. Think about it in terms of binary numbers.
Zero and one. Zero if... Well, actually, wait a minute.
No, if you added two trues to ones, you'd get a zero. That doesn't work. Well, you're all jumping right ahead in what I hope I can actually finish today.
The issue of Boolean operations is... is at the heart of doing binary addition, which is at the heart of building a circuit that does addition. And we're going to show that that actually does connect. And plus does correspond to addition in binary. You'll see soon.
What is the symbol for exclusive order? A plus sign with a circle around it. All right, the other basic connective that we'll start with is a connective that doesn't connect two Boolean things, but just works on one, called not.
So not W means it's not wet outside. Sometimes that's written like this. Sometimes it's written like this. Three sets of notations.
When you think of these things not from circuit point of view, but in terms of logic point of view, here's a very common thing that you'll see. This means if it's raining outside, then it's wet outside. Okay, implication.
It's the way we argue. It's the way we think. It's the way proofs go from one step to another.
Now everybody thinks they know what this means, but what I want to do is make sure that we all have the same agreement. And the way I want to do it is, I want to actually write out a table. And this writing out a table, I'll do it here, r and w.
It's called a truth table. Just to show you how it works, we'll do r and w. Here's what a truth table does.
You put all the possible true and false values here for r and w. I'll use zeros and ones. Zero for false, one for true. There's four possibilities. Who can fill this in for me?
0, 0, 0, 1. 0, 0, 0, 1. Good. It's only 1 when both of them are 1. Now let's fill in r or w. That's going to be 0, 1, 1, 1. And now let's go over here and we'll fill in r implies w. And let's be really careful because we actually have to decide what this means. What does it mean for something to imply something else?
It means that if the... 1 over here on the left side is true, then this has to be true. Let's put that in.
If this is true, this is true, that means that's a 1 there. What about when this is true and that's false? That means 0. What about these two? Here's the convention.
The convention is that when the left side is false, we don't care what's on the right side, we still consider the implication to be true. If I say if it's raining outside, then it's wet. Then if it's not raining, regardless of whether it's wet or not, my statement of the implication would still hold.
So if the left side is not true, then the right side can be anything we want, and we still say the implication's true. That's a logical decision, which generally makes sense, and we go with that. So this is the...
This is a by definition. This is what we mean by R implies W. And it corresponds to what we mean logically as well. All right. Questions about this?
What I want to show you is that this is... Pnarticular formula, R implies W, could be rewritten in terms of ands, ors, and nots without a new symbol. And what you should know is that any Boolean formula can be written in terms of ands, ors, and nots.
Always. And sometimes we say that therefore the set of operators and or not is a complete set. It can get any function you want in the whole world.
And I'm going to convince you of this in just a minute that it can be done in general. But first I want to do it just for this. R implies W. Okay, questions. So here's how we're going to do it.
My convincing is going to be done by rewriting this table just for... r implies w. It reads 1, 1, 0, 1. And what I'm going to do here could be done in general for any Boolean truth table or function at all.
where I list all the possibilities and I tell you what the output should be. What I'm going to do now could work for anything, and I'm going to come up with a formula that just uses ands, ors, and nots. Okay, so let's look at my method. And it's very, very, it's very logical. There's nothing tricky here.
I want to come up with a formula that's going to have a 1 here, a 1 here, a 1 here. So I'm going to concentrate on those three rows. And let's ask ourselves, when should this formula be true?
It should be true here, here, and here. What makes this row true? What has to happen for this to be true?
Not r and not w. What has to happen for this possibility to be true? Not r and w, but it's... This possibility, or this possibility, or this possibility. So, not R and W.
Or, what's the last possibility? R and W. Let me go through this again. We take the three rows that have ones in them. Or if there were more than that, look at all the rows with ones in them.
Take it a row at a time. We're going to OR the possibilities together, because this formula will be true if either this is true, or this is true, or this is true. Either this condition, or this condition, or this condition.
condition. These conditions, for them to be true, each have to have both variables satisfying a particular condition. Namely, both have to be false.
Not R, not W. I can do it here. I can do it here. I OR them together. I get a connection.
of things that have nots, ands, and ors, no other connectives, and I get a final formula equal to r implies w. And I could do this for any formula. I didn't even have to give you a name for it. I could just list a whole bunch of variables, put ones and zeros in here any way I wanted, and do it the same way. That's a proof that ands, ors, and nots together make a complete set.
You can go to the RadioShack, buy a box of and gates, or gates, and not gates, and put them together, and build any Boolean function out of circuits. All right. Yeah, question. Can you also do that by doing a not for the third one?
So it would be like not R, not W? I don't know. Instead of doing those three, can you also do it as? Is this the same I think you're asking as not R or W?
Or you're asking something like this. This is what I wanted to say next anyway, so I'm jumping on your shoulders. Michael's question is, is there another formula that would be equivalent to this? Or could I do it in an ad hoc way that isn't mechanical? The answer is yes and yes.
This mechanical way you could make a computer do. You could write a scheme function to print out these functions. But it's true that there's a much simpler equivalence to R implies W. And you can check it yourself.
Check not R or W. Make a truth table for not R or W. You'll find out it's the same.
Same as 1, 1, 0, 1. So not R or W. It's the same as this. You'd probably want to go build this circuit instead of that circuit.
This one takes more gates. This one has more wires. Is there a general rule for always coming up with a minimum one?
The answer is kind of. Building minimal size circuits is a hard problem, and it's more of an art than a science. There are some techniques.
You'll study it next month a little more. Instead of focusing on... You need the parenter, right? The order of operation, is it defined like intersect?
No, and is commutative. I just put the parens to show that the ors go last. I mean, I didn't want you to do not y or not r.
Yeah, but I mean, is the order, is not... The order between the... The order of operation. If you didn't have the parent... Oh, if I didn't have the parent...
We can do that by definition first... If you always do nots first and... ands next, and then ors, then you'll be okay. Isn't that like the... It is.
It is, but I never said that, so I just put the parentheses in. But you're right, right. Baruch is right that if I don't put parentheses in, the implication is do ands first, because that's like multiplication.
Do, sorry, do nots first. That's like negative signs. Do ands next, that's like multiplication. And then do ors, that's like addition. So if you don't see parentheses, you assume that that's the right order.
Baruch's 100% right. Yeah, Chris. Just real quick again. What's the loss behind if r then w equaling 1, 1, 0? Back in the truth table?
You mean here and here? Yeah, what's the... It's like, how about this? Let's say I say, if I'm 10 feet tall, okay, then you're a genius. Alright?
Is that true or not? If I'm 10 feet tall, then you're a genius. I'm just trying to see whether or not that is true according to the conditions I got. Right.
Is that implication true? on the condition. Since I'm not 10 feet tall, I could say if I'm 10 feet tall, then you're a 75-year-old lady, and that implication is still true because there's nothing to contradict it.
Since I'm not 10 feet tall, we can't even test it. So we consider the implication true. if the thing on the left is always false.
Does that help a little? I think that's a subtle point. I kind of went over it quickly because I don't want to get into a long discussion about it because if you get it quickly, it's good, and if you don't, you get it later.
And I didn't want it to be a fussy thing. But yes, a good question. In making your three-part equivalent, you were focusing on the ones on the right side.
Right. Since there's only one zero, focus on the zeros and then put a not in front of it. That's what I'm saying.
Wow. Who's got problem set one, number seven? It's a problem set question. I'm not answering it.
You answer it. Here are two formulas, two Boolean formulas. This means it's raining or it's wet outside, and it's not true that it's both raining and it's wet outside.
This means it's not raining and it's wet, or it's not wet and it's raining. That's how you read it. You can take English sentences and turn them into these formulas.
You can take these formulas, turn them into English sentences. Most importantly, you can determine whether one formula is, wow, there's some chalk. One formula is equivalent logically to the other.
There are two basic ways to do this. One way is a brute form. method that you can already figure out in your own. Make a truth table for this, for R and W. Make a truth table for this, for R and W, and see that they're the same.
Therefore, these formulas will agree on any inputs of true or false to R and W. Let's do it quickly. R, W, 0, 0, 0, 1, 1, 0, 1, 1. Pnut in 0, 0 into this formula and calculate the result. Seth, I'm picking on the big guy. Okay.
Zero. That's this one. Can you do the next one for me, too? Pnut zero, one in there? Not the next equation.
The next zero, one for this. Also false? Zero or one?
is going to end up being 1, and then 0 and 1 is going to be false, 0, and then not that is going to be 1. So we get 1 and the not of this whole thing. So it's 1. Good. What are the rest?
Somebody do it while I'm stalling with Seth? One zero. What happens with this one? It should be the same.
Both these functions are equivalent to something that I mentioned a minute ago. R or W, but not both. R or W and not. Both of them.
Here it looks just like I said it in English. R or W and not both of them. That happens to be equivalent, not obviously, but it's equivalent to not the first one or the second one, or else not the second one or the first one. Can't have both of them being true or false. This is sometimes written as R exclusive or W.
Exclusive or is a very common combination. I'm going to go on a complete side thing here for those of you who just like little puzzles that happen to connect to exclusive OR There's a, it's a cool puzzle. That's right.
Here's a good puzzle. You learned about variables in Scheme. Some of you programmed in other languages that have variables.
One thing that you typically see in a programming language is you need to switch the value of two variables. A's got to get the value of B, and B's got to get the value of A. You actually hardly do that in Scheme.
But in other languages, it's like you do it on the second day. Here's how it's typically done. Say you want to switch values of A and B, you do this. You have a temperature.
temporary variable, temp equals a, b gets the value of a. Did I do this right? Sorry.
a gets the value of b, and b gets the value of temp. Now, why don't you just do a equals b and b equals a? Because you'll lose the value of the first one before you copied it over to the value of the second.
So you do these three steps. You see these in every book. If you open a Java book, just open up to, I don't know, page 80 on the sort routine, you'll see this. It's called a swap routine.
If you use exclusive or, then you can do this without a temporary variable. So I'll leave that as a puzzle. You can swap A and B using exclusive OR without any temporary variables.
So think about that. It relates to a circuit problem too, but whoosh! Back to here.
That's the other way of showing two formulas are equivalent. One is checking all the truth and false possibilities, and one is manipulating them algebraically to make them look like one another. And that second way of doing it is from an area called Boolean algebra.
So let me give you some of the basic rules in Boolean algebra. You can look these up in the notes or the book. And all these rules could be proved by truth tables. Here's one that we've already done.
R implies W is equivalent to not R or W. That's worth knowing. Here are some more basic ones. Not, not R What's that equivalent to?
R All right. So just what you'd think. R, W, do it this way. R or W and C and S. You can use the distributive law.
R or W and S is the same as R or... Good. Here's where Boolean algebra is better than regular algebra. In regular algebra, the distributive property doesn't work the other way, right?
If you do r times w plus s, does it equal r times s plus w times s? Did I do that right? No, I didn't do it right.
Does it equal r plus s times... Does that work in real arithmetic? No. In fact, they bang you on the head in fourth grade, and that does work, that doesn't work.
And nobody ever remembers this. You know, they just end up doing r plus w times s. So you've got to remind kids, and sooner or later they get this.
If they ever did this, the teacher would say that they're silly. But this is true in Boolean algebra. This distributive property works.
It's perfectly, perfectly symmetrical. You can distribute ands through ors and distribute ors through ands. Looking at it in this notation, it's really ugly.
That's about the worst notation you can use to show the distributive property, because you're so used to thinking of this as not distributing. So if you want to look at the distributive property a little better, maybe it's better to do it this way. R and W or S equals R or S and W or S. You're not so used to these symbols, so they don't stick the wrong idea in your head, and this really is true.
You could show these two things are true through truth tables. You can distribute either ands through ors or ors through ands. Questions?
All right. There's two other main rules. Yeah? Tn? Yeah?
For the XOR, could you do, say, an A and B? Uh-huh. E equals XOR A, B. A equals XOR A, B. B equals XOR A, B. But what's x? Oh, x or. Just x or.
Yeah, you give me the answer to my question. Yeah. Yes.
Right. Can you repeat the question? Oh, the question was, how do you swap two variables without a temporary value? And you can do it using x or.
Actually, the hard way to ask that question is to ask it without the big hint that it uses x or. And the follow-up to the... Well, all right.
I got... Oh, there's so much to do in this class, I can't go off on my gazillion... tangents, but I need to move on here. Two more rules. This is called the distributive rules.
The next rules are called, there's also the normal rules, commutative rules, associative rules, and is commutative, or is commutative. They're all associative. I'm not going to write them down.
You can look them up. But here's rules that aren't as obvious. They're called De Morgan's laws.
And they come up in other contexts too, like in sets that we'll do soon. Here's De Morgan's laws. It relates not to ands and ors. Not A and B, not A or B.
Here's the general idea. If you have a not sign in front of a collection of things that are anded together, you can kind of push that not sign through, just like you push a negative sign through. But when you do it, the operators change from and to or. So this is the same as not A or not B.
Let's think about that logically. If it's not true that both these things are true, if it's not true that A and B are true, that means either the first one isn't true or the second one isn't true. It's very logical. Same thing here.
This equals not A and not B. That's called De Morgan's laws. That's the way to push not signs through formulas.
And that's what lets you do Sam's idea before of concentrating on the zeros and putting a not in front of the whole thing. It'll switch all the ands to ors and all the ors to ands, and you'll get a nice result. Does this mean that either and or orally can explain for a list of primitives?
Mike? Not an and? Chris is asking whether not an and alone, those two operators are a complete set.
Can we get rid of or based on this? What do you think? I'm going to leave you with that question.
This does relate nots and ands to ors. The question is, I think in order to prove what you're trying to prove, you need to show how to take any a and b and rewrite it in terms of ors. This doesn't do that exactly.
If you could do that, if you could take any a and b and write it just in terms of knots and ors, then I could take any formula with ands, nots, and ors in it, pull out the places where there are ands, and replace them with ors and nots. But this doesn't let you do that, because there's a not in front of this. So it only lets you replace things with nots. But you put a not on the right and an additional not on the left.
And an additional not on the right. Right. You do not of nots.
So I'll leave it as a... It's a very good thing to think about, but I'm going to let you guys answer it and come with me next class and tell me the answer. But it's a perfect question because it's what I'm going to talk about next.
It's like having shills in the audience. I can look at it like, you said you'd ask your question now. All right, one little thing before we quit.
Hmm. All right, one example, and then we'll quit. I wanted to talk about these complete things, but I won't have time.
Let's do a mechanical example to show that these two things are completely equivalent, that the two exclusive OR formulas are equivalent. Yes, this means... Yes, this means not...
That's what it means, Seth. It means do R and W and it's not that whole thing. Or I could put the not in front of it too, but it would look like a minus sign. I didn't want to do that.
I know you knew it. How do we show that this and this are equivalent? Mechanically.
We're going to use the rules of distributive and De Morgan's laws and logical rules to mechanically manipulate this syntactically to look like that. Every step... of the way using things that change it into stuff that are logically equivalent.
And this is really kind of what theorem provers do in their own twisted way. All right, so here's my first step. It's a really kind of a strange thing to do.
Guys, there we go. What did I do in this step? What's the justification for this step? Which? You put a negative sign over both of those parentheses?
Yes. So what did I do in this step? I distributed the r and the w over this term.
Okay, that's the distributive rule for addition over multiplication. What do I do next? I'm trying to get it to look like this.
Experiment. What do we do next? I'm going to push this not sign through here.
What do I get when I push the not sign through there? Not r or not w. Pnlus?
Same thing here, not r or not w. Now what? I'm still not quite like that, but I'm getting really close.
Now what? Now distribute out the multiplication over the addition. r, r, oh, the yellow's good. This is quality chalk.
Here's what I get. I can rearrange these terms because community, commutativity, and associativity. But what about these extra terms? I mean, these two match there.
That's fine. I could, you know, turn them around and make a match. But these two are extra.
What about them? Are and are not. Can that ever be?
No, that can never be. This is false. This is false. That's one of the rules, one of the basic rules, that are and The negative of r are always false.
What about something or false? A or false. What's that the same as?
A. Right? In other words, a false doesn't affect it at all for an or. What about a and false?
Okay? Very symmetric here. What about a and true? That's the same as A.
What about A or true? It's so beautifully symmetrical, Boolean algebra. Distribution works both ways. True and false rules are just the inverses of each other. Everything is just the perfect circle.
It's so nice. George Boole discovered this stuff a hundred years ago. with no notion that it would be at the heart of building computers, which is what it's primarily used for by electrical engineers. So these two things are the same. Now you know how to show two formulas are true by truth tables.
You know how to show two formulas are true by truth tables. true by algebraic manipulation. You know the idea of a complete set. You know that any formula can be written with ands, ors, and nots, and therefore they're a complete set. And you have a notion of what a proof is and how to do a mathematical induction proof.
And all you need now is 25 days of intense practice and we'll move on. All right, so we're going to continue with this stuff next time. Tara today is going to do another proof by induction.
And before that, she and I are going to do this magic trick, which I told you there's a problem set about. So get ready for a little entertainment.