Counterexamples

Loading...

From the course by University of California San Diego

Mathematical Thinking in Computer Science

264 ratings

University of California San Diego

Mathematical Thinking in Computer Science

264 ratings

Course 1 of 5 in the 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.

From the lesson

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

Meet the Instructors

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

Hi. In the previous video we talked about examples. In this video,

we will study counterexamples,

examples which prove that something is actually incorrect.

Sometimes, just one counterexample is sufficient to disprove a whole statement.

If we want to prove that all swans are white,

just showing one black swan is sufficient to disprove the statement.

However, it is often hard to find such counterexamples.

Let's start with this theorem.

All rectangles are squares.

Here, it is easy to find a counterexample,

because a rectangle with sides one and two is not a square,

because a square must have all the sides equal.

And so, this is a counterexample for the theorem,

and so this theorem is wrong.

Now, let's consider another theorem.

All squares are rectangles.

In this case, there is no counterexample.

And the theorem is true, because square is by definition a rectangle with equal sides,

and so any square is actually a rectangle.

And you cannot come up with a counterexample to disprove this theorem,

because the theorem is true.

Now, let's move on to more complex theories.

Euler is a famous mathematician.

And he proved a lot of facts,

but also he made some conjectures,

which he didn't prove.

And one of his conjectures is a generalization of Fermat's Last Theorem.

When Euler lived, Fermat's last theorem wasn't proved.

But he still came up with even a generalization of this theorem,

and he wanted to prove that for any positive integer n bigger than 2,

it is not only impossible to solve

equation a to the nth plus b to the nth equal to c to the nth.

It is also impossible for nth power of

a positive integer to be represented as a sum of n-1 numbers,

which are nth powers of positive integers.

For n=3, It is the same as Fermat's Last Theorem for n=3.

It is impossible that a to

the power of plus b to the power of 3 is equal to c to the power of 3.

And so, for n=3,

this conjecture is true,

because we know now that Fermat's Last Theorem is true.

It was proved in 1995.

So, for a particular case of the smallest n,

Euler's hypothesis is true.

However, for bigger values of n,

this is not true.

And in 1966, Lander found the following counterexample for n=5.

And the counterexample is on the slide,

and it already disproves the whole conjecture.

However, it still leaves some room for questions.

For example, what about n=4?

For n=3 we know that the conjecture is correct.

For n=5 we now know that the conjecture is incorrect. What about n=4?

Actually, in 1986, Elkies found another counterexample,

and it was for n=4.

And you see that this counterexample is huge.

And so, it turned out that this is not the smallest possible counterexample.

And the smallest possible counterexample was found in 1988.

And actually, you've already seen

this counterexample as an example in the previous video.

And, of course, this is often the case.

Something can be an example and the counterexample at the same time,

but it is just example for sum statement,

and it is a counterexample for the negation,

for the opposite of that statement.

And depending on what you want to prove,

you can either make an example to prove

the positive statement or make a counterexample to disprove a negative statement.

And also, a reminder that in the previous week,

when we started induction,

we were trying to prove that it is impossible to cut

an obtuse triangle into smaller acute triangles.

And then at some point when had already thought that we proved it,

we came up with a example on here. It is on the slide.

And so, this is another counter example,

which disproves this statement.

In this case, it is possible to cut the obtuse triangle into acute triangles like this.

So, now, we are acquainted with examples and counterexamples.

And in the next lecture,

we're going to discuss more general things,

the basic mathematical logic constructions.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play