[MUSIC] Hi, in this lecture, we're going to start studying mathematical logic. It is a whole, big branch of mathematics. But in this particular video, I will tell you about some basic constructions of mathematical logic. And we will start with the most common logical operations. Negation, logical and and or, and if-then statements, let's start with negation. Suppose we have some statement like, all swans are white. Then the negation of the statement is that not all swans are white, the opposite of the statement. Another way to state a negation of the statement is that, there are swans that are not white. Another statement for which we will find a negation is the following. There exist three positive integers, a, b, and c, such that a to the power of 3 + b to the power of 3 = c to the power of 3. And when we're thinking about negation, doesn't matter whether the statement is true or not. We're just formally trying to find the opposite statement, and again, there are two ways to formulate it. One is, there are no such positive integers a, b and c that a cubed + b cubed = c cubed. Or another way to say the same is that for any positive integers a, b, and c, a cubed + b cubed is not equal to c cubed. Two more examples is, first we have statement, 4 equals 2 + 2. Then the negation of this statement is 4 is not equal = 2 + 2. And another example is 5 = 2 + 2, the negation is that 5 is not equal to 2 + 2. So, you see that it doesn't matter which statement is true, which statement is wrong. We just apply simple rules to make a negation from a statement, and then always, either the statement is true, or its negation is true. In the first case, the statement is true, 4 = 2 + 2. And the second case the statement is wrong, 5 is not equal to 2 + 2, so the negation of the statement is true, 5 is not equal to 2 + 2. Negation is true if and only if the initial statement is wrong, and vice versa, this is by definition of the negation. Next construction is logical and operation. An example is on the slide, 4 = 2 + 2 and 4 = 2 times 2. The logical and of two statements is true in the case when both statements are true, and otherwise it is false. So if we write these four applications of logical and, then only the first one of them is true, because both 4 = 2 + 2 and 4 = 2 times 2 are true. And so the logical and of two true statements is true. The second statement is false, because 5 is not equal to 2 times 2, so the second statement is false. And the logical and is only true when both statements are true, so the right statement is false, logical and is also false. And the last two statements are also false, because the last part is false. 5 = 2 + 2 is false, and it is common in the last two statements, and so logical and is false. Similar construction is logical or, for example, 4 = 2 + 2 or 5 = 2 + 2. And the logical or of the statements is true if at least one of them is true. So in this case, it is true because 4 = 2 + 2, and it doesn't matter whether 5 = 2 + 2 or not, the or statement is already true. And here is a similar example with or, so the first three statements are true and the last statement is false. So the first two statements are true because 4 = 2 + 2 is true, and so it doesn't matter whether the second statement is true or not. In the first case if it is true, the second case it is false, but still the or is true. And in the third line, third statement, the right part, 4 = 2 times 2, and this is also sufficient for logical or to be true. It doesn't matter that the left part, 5 = 2+2 is false, still or is true. In the last line, both left part and the right part are false, 5 is not equal to 2 + 2, 5 is not equal to 2 times 2, so the logical or is false. Venn diagram is a way to visualize these abrasions, logical not, logical or, logical and. Also, in mathematics, logical not is often denoted by the sign on the slide, just to make notation shorter. Logical and also has its own sign like that, and logical or has the sign which is upside down from logical and. And on the three pictures below, we see the illustration of logical and on the left, logical or in the middle, and logical not on the right. So on the left, we have a big rectangle, which is all possibilities. And the circle, denoted by x, is the circle of all possibilities where statement x is true. And the circle denoted by y is the circle of all possibilities where the statement y Is true. And then the set of possibilities where x and y is true is the intersection of those circles. Because for logical and to be true, we need both x and y to be true, and that's why I need to take the intersection. On the picture in the center, we have similar illustration for logical or. I have two circles for x and y, and for logical or to be true, we need x to be true or y to be true. But just one of them is enough, so we take the union of the circles. Anything inside circle x makes or true, anything inside circle y makes or true, and anything in intersection also makes the or true. But everything outside both circles makes logical or false. And in the last picture, we see the illustration of the negation of x. So if the circle for x is everything, all the possibilities where x is true, then the negation of x is true on all possibilities but for this. So the red area is everything but for the possibilities inside the circle for x, and this is where the negation of x is true. Now, let's study negation of and and or, so negation of and is the or of negations. For example, a negation of statement like A and B, A is not A or not B. For example, negation of statement that 4 = 2 + 2 and 4 = 2 times 2 is the statement, that either 4 is not equal to 2 + 2 or 4 is not equal to 2 times 2. Negation of or is symmetric, negation of or is and of negations. So negation of statement a or b is not a and not b. For example, the negation of 4 = 2 + 2 or 5 = 2 + 2 is, 4 is not equal to 2 + 2, and 5 is not equal to 2 + 2. Now the most interesting part is if-then statements. We are always using them actually, for all the theorems, but how to define them formally? Consider a promise, if there is an elephant in your refrigerator, then I will give you $100, now there are the following cases. If there is indeed an elephant in the refrigerator, and I indeed give you $100 for that, I keep my promise, and so the statement is true. If there is no elephant in your refrigerator and I didn't give you $100, I still kept the promise, because there was no elephant. So I don't need to give you $100, so this statement's also true. If there is an elephant in the refrigerator, but I don't give you $100, then I don't keep my promise, so this statement becomes false. And the interesting case is, what if there is no elephant in the refrigerator, but for some reason I still give you $100 anyway, did I keep my promise or not? Well in the technical sciences we consider it as a kept promise. So although there was no elephant, I still gave you $100. That doesn't break any promises, so this statement is considered true. Now in the general case phrase, if P then Q, for some statements P and Q is true whenever either Q is true or P is false. The interesting quirk in this is that if P is false, then every statement of the form, if P then something will be true, disregarding whether Q is false or true or anything. So this is sometimes what confuses people, but formally this is always the case. Examples, if n is = 6, then n is even. This is true, because if we take n, which is equal to 6, and the statement is true, then n is also even. And so, the q the second statement, the then statement, is true. If n is not equal to 6, then the if part is false, and as we know, as soon as if part is false, the whole statement if-then is true. The second statement, if n = 5 then n is even is false, because if we take n = 5, then the if part will be true, but the then part will be false. And this is the only case where the if-then actually becomes a false statement. Now the interesting parts are for example, if 1 = 2, then 2 = 3, this is a true statement. Why, because 1 is not equal to 2, so the left, the if part, is false. And then whatever we write on the right part, the statement is true. For example, if 1 = 2, then I am an elephant, is a completely true statement from a mathematical point of view. because 1 is not equal to 2, so the if part is false. And then the statement that I am an elephant, doesn't matter whether it's true or false. The if then statement is true in this case. [MUSIC]