0:00

[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.

Â 2:37

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.

Â 3:57

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.

Â 4:44

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.

Â 6:25

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.

Â 8:24

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.

Â 8:55

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.

Â 10:13

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]

Â