Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Degrees
Certificates

Explore all of Coursera

Browse
Search
For Enterprise
Log In
Join for Free

Counterexamples

Loading...

Mathematical Thinking in Computer Science

University of California San Diego

4.4 (540 ratings) | 29K Students Enrolled

Course 1 of 5 in the Introduction to Discrete Mathematics for Computer Science Specialization

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.

Skills You'll Learn

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

Reviews

4.4 (540 ratings)

5 stars
350 ratings
4 stars
120 ratings
3 stars
45 ratings
2 stars
12 ratings
1 star
13 ratings

KL

Nov 29, 2018

The course is excellent and most stuff is being taught in a nicely presented way. The main disappointment is 15-puzzle, because it's too difficult to understand without proper material.

DG

Jun 30, 2018

Love the quality of thought that goes into each lesson. The professors speak with acute clarity and really demonstrate and empathy for the student to truly understand the topics!

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

Taught By

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Vladimir Podolskii
Associate Professor

Transcript

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.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates