If-Then Generalization, Quantification

Loading...

Из курса от партнера University of California San Diego

Mathematical Thinking in Computer Science

456 оценки

University of California San Diego

Mathematical Thinking in Computer Science

456 оценки

Курс 1 из 5 — Specialization Introduction to Discrete Mathematics for Computer Science

Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In the course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.

Из урока

Logic

We have already invoked mathematical logic when we discussed how to make convincing arguments by giving examples. This week we will turn mathematical logic full on. We will discuss its basic operations and rules. We will see how logic can play a crucial and indispensable role in creating convincing arguments. We will discuss how to construct a negation to the statement, and you will see how to win an argument by showing your opponent is wrong with just one example called counterexample!. We will see tricky and seemingly counterintuitive, but yet (an unintentional pun) logical aspects of mathematical logic. We will see one of the oldest approaches to making convincing arguments: Reductio ad Absurdum.

Counterexamples4:59

Basic Logic Constructs10:59

If-Then Generalization, Quantification8:10

Познакомьтесь с преподавателями

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

Now we want to generalize a bit, because typically we see statements like this.

If n is divisible by 4, then n is divisible by 2.

What it actually means is that for all integers n, if n is divisible by 4,

then n is divisible by 2.

And this statement is actually true, how do we check it?

For any number n either it is divisible by 4, and so the if part is true.

But then it's also divisible by 2, because It is divisible by 4, if we divided by 4,

we get an integer number.

But then if we divided by 2, we get twice that integer number, so

it is also an integer.

So n is divisible by 2 whenever it is divisible by 4.

So both the if pats and the then parts are true, and so

the statement is true in this case.

And the second case is that n is not divisible by 4, then the if part is false.

But then, if the if part is false, then the if-then statement is always true.

It doesn't matter whether n is divisible by 2 or not.

So this general statement, if n is divisible by 4,

then n is divisible by 2 is true.

Here, we changed if and then part, we switch them and

write, if n is divisible by 2, then n is divisible by 4.

This statement is false, because for a particular n = 2,

it is divisible by 2, but it is not divisible by 4.

If we divide 2 by 4, we'll get 0.5, which is not an integer.

So the if part is true, but the then part is false,

so the if-then statement is false.

Actually, we can call the first statement, if n is divisible by 4,

then n is divisible by 2, the direct statement.

When we switch the if and then parts,

we call it the converse statement to the initial direct statement.

So if n is divisible by 2, then n is divisible by 4 is a converse statement.

And sometimes both direct statement and

converse statements are true, this is not true in this case.

Because the direct statement is true, but the converse statement is false.

But sometimes, both direct statement, if P then Q, and converse statement,

if Q then P, are true.

And in this case we arrive that they're equivalent like this,P if and only if Q.

This means that whenever P is true,

Q is also true, whenever Q is true, P is also true, they're equivalent.

Now, let's apply negation to the if-then statements.

The negation of the phrase, if P then Q, is actually P and not Q.

And you check for yourself, that this is

true whenever the corresponding if-then statement is false, and vice versa.

So just check, that by definition of negation,

P and not Q is actually the negation of the phrase, if P then Q.

A few more definitions, universal quantification is actually,

I think that we've already routinely used for some time.

Statements like, all swans are white, all integers ending with digit 2 are even, for

all n, 2 times n equals n plus n, are examples of universal quantification.

Fermat's last theorem states that for all integer n more than 3,

equation a to the power of n plus b to the power of n equals to c to the power of n

does not have solutions, with positive integers a, b, and c.

Thus, as it starts with the phrase for

all n, it is also an example of universal quantification.

Another quantification is existential, and we've also used it

routinely in the previous lectures, statements like, there are black swans.

There is a way to get a change of 12 cents with 4-cents and 5-cents coins.

There exist such positive integers, a, b, and c, that a to the fourth plus

b to the fourth plus c to the fourth, is equal to d to the fourth.

And there is a power of 2 starting with 65,

are all examples of existential quantification.

Any statements that state that something can be done,

something exists, is an example of existential quantification.

Now, we can make combinations of quantifiers, and

most mathematical statements are usually combinations of universal and

existential quantifications, in some combination.

Here is a corollary from Fermat's last theorem.

There exists such integer m, that for

any integer n which is bigger than m, equation a to the n plus b to the n

is equal to c to the n has no solutions with positive integers a, b, and c.

Why is this a corollary from Fermat's last theorem?

Well, because if we take m = 2, and then it follows from Fermat's last

theorem..It goes, we just change m to 2 in this statement.

And again, there exists an integer 2 such that for

any integer n bigger than 2, the equation a to the n plus b to the n

equals c to the n has no solutions, and this is exactly Fermat's last theorem.

So this is a particular case of Fermat's last theorem.

And so, we found that this is

a corollary from Fermat's last theorem, because of the existential quantification.

We found an example of m for which the existential quantification is true.

And the statement itself is a combination of existential quantifier, there exists

such an integer, and universal quantifier, for any integer n bigger than m.

Now what do we do if we need to negate some quantification?

Negation of universal quantification is a corresponding existential quantification,

and vice versa.

For example, negation of, for all n, statement A is true,

the negation of it is there exists such n that statement A is false, and vice versa.

Reverse hypothesis is a combination of two universal quantifications.

For any n bigger than 3, for any positive integer a,

it is impossible to represent a to the power of n

as a sum of exactly n- 1 numbers which are also nth powers of positive integers.

This negation of Euler's hypothesis is a statement that there exists such

n integer bigger than 3, and such positive integer a, that a to the power of n can

be represented as a sum of n- 1 numbers, which are nth powers of positive integers.

And I'll show you an example which proves this negation, so

Euler's hypothesis is actually false.

Negation of combinations, things like all positive integers are either even or odd,

is, there exists such a positive integer that is not even and not odd.

So to negate, we switch universal quantification to existential,

and vice versa, and we switch or to and, and vice versa.

And examples and the counterexamples, for example,

counterexample for Euler's hypothesis that we saw earlier,

is an example for the negation of Euler's hypothesis.

So examples and counterexamples are also dual as and and

or, universal and existential.

Examples and counterexamples are dual, by proving negation of Euler's hypothesis.

By showing an example to it, we prove that Euler's hypothesis itself is false,

and this example is just a counterexample to the initial Euler's hypothesis.

And one popular way of proving mathematical statements is called reductio

ad absurdum.

Basically, proving that the negation of the initial statement is false, and so

the statement itself is true.

And you will learn this proof principle in the next lecture.

In conclusion, in this lesson, we studied examples, counterexamples, and

when just one example or counterexample is enough.

We started basic logical operations, negation, logical and,

logical or, and if-then statements.

We also studied universal and existential qualifications, and

we learned how to negate different combination of logical operations.

And in the next lecture, you will study reductio ad absurdum principle,

which is based on these constructions.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play