Lecture 01 – Introduction

(1)

CS 207m: Discrete Structures (Minor)

Instructor : S. Akshay

Jan 05, 2018

Lecture 01 – Introduction

(2)

Logistics

Course hours: Slot 5;

Wed 09:30-11:00, Fri 09:30-11:00 Office hours: By prior appointment Evaluation

I Quizzes: 30%

I Midsem: 25%

I Endsem: 40%

I Other (pop quizzes, participation, assignments): 5%

Course material, references will be posted at

I http://www.cse.iitb.ac.in/~akshayss/teaching.html

I piazza (will be set up by TAs soon)

(3)

Logistics

Course hours: Slot 5;

Wed 09:30-11:00, Fri 09:30-11:00 Office hours: By prior appointment Evaluation

I Quizzes: 30%

I Midsem: 25%

I Endsem: 40%

I Other (pop quizzes, participation, assignments): 5%

Course material, references will be posted at

I http://www.cse.iitb.ac.in/~akshayss/teaching.html

I piazza (will be set up by TAs soon)

(4)

Goal

First things first...

I What are discrete structures?

I Why are we interested in them?

(5)

Course Outline

What we will broadly cover in this course

1. Mathematical reasoning: proofs and structures 2. Counting and combinatorics

3. Elements of graph theory

4. Introduction to abstract algebra & number theory

What we don’t cover 1. Discrete probability 2. Algorithms

3. Logic and Finite automata

4. Details and applications of everything above – rest of your (minor) life!

(6)

Course Outline

What we will broadly cover in this course

4. Introduction to abstract algebra & number theory

What we don’t cover 1. Discrete probability 2. Algorithms

3. Logic and Finite automata

4. Details and applications of everything above – rest of your (minor) life!

(7)

Course Outline

What we will cover in this course

4. Introduction to abstract algebra and number theory

Textbooks

I Discrete Mathematics and its Applications with

Combinatorics and Graph Theory, by Kenneth H Rosen.

I Discrete Mathematics by Norman Biggs.

I Introduction to Graph theory by Douglas B West.

I More will be listed on webpage as we go along.

(8)

More lofty aims of the course

1. Introducemathematical backgroundneeded in various branches of computer science (and in other sciences!) 2. (New and old) techniques for problem solving: how to

attack problems that you have never seen before.

3. Towrite proofsand convey your ideas formally.

4. Todevelop skills to read/understand/solve new material in the future.

(9)

Chapter 1: Proofs and Structures

Outline of next few classes

I Propositions, statements

I What/why of proofs and some generic proof strategies

I Mathematical induction

I Notions and properties of sets, functions, relations

(10)

Propositions

What is a proposition?

I It is raining

I 1 + 1 = 2

I every odd number is a prime

I 2⁶⁷−1 is a prime

I (n+ 1)(n−1) = (n²−1) for any integern

(11)

Propositions

I It is raining

I 1 + 1 = 2

I (n+ 1)(n−1) = (n²−1) for any integern What is common between these statements?

(12)

Propositions

I It is raining

I 1 + 1 = 2

Aproposition is a statement that is either true or false (but not both).

(13)

Propositions

I It is raining

I 1 + 1 = 2

Give an example of a statement that is not a proposition.

(14)

Propositions

I It is raining

I 1 + 1 = 2

Give an example of a statement that is not a proposition.

I x+ 1 = 8

(15)

Propositional calculus

Figure: Aristotle (384 – 322 BCE)

I propositions are statements that are either true or false.

I Just as we use variablesx, y, . . .for numbers, we will use variables p, q, . . .for propositions.

I “ifit is raining,it will be wet” : p→q

(16)

Propositional calculus

Combining propositions

Ifp, q are propositions, then so are:

I ¬p - not every prime number is odd

I p∨q - either it is raining or it will be wet

I p∧q - it is raining and it is wet

I p→q

I p iff q

Can all mathematical statements be written this way?

(17)

Propositional calculus

I p→q

I p iff q

(18)

Propositional calculus

I p→q

I p iff q

(19)

Propositional calculus

I p→q

I p iffq

(20)

Propositional calculus

I p→q

I p iffq

(21)

Predicates and quantifiers

Consider again...

I ∀n

∈N

(n+ 1)(n−1) = (n²−1)

I ∀x,∃y,

x, y∈Z

x=y+ 8

I ∀n stands for all values ofnin a given domain

I ∃n stands for existsn

I ∈ is the “element of” symbol

I N stands for all natural numbers

I Z stands for all integers

I R,Q, ...

Some propositions are not so easy to “determine”... – e.g., 2⁶⁷−1 is not a prime.

(22)

Predicates and quantifiers

Consider again...

I ∀n

∈N

(n+ 1)(n−1) = (n²−1)

I ∀x,∃y,

x, y∈Z

x=y+ 8

I R,Q, ...

Some propositions are not so easy to “determine”... – e.g., 2⁶⁷−1 is not a prime.

(23)

Predicates and quantifiers

Consider again...

I ∀n∈N(n+ 1)(n−1) = (n²−1)

I ∀x,∃y, x, y∈Z x=y+ 8

I R,Q, ...

Some propositions are not so easy to “determine”...

– e.g., 2⁶⁷−1 is not a prime.

(24)

Theorems and proofs

A theorem is a proposition which can be shown true

Classwork: Prove the following theorems.

1. If mand n are perfect squares of integers, thenmn is also a perfect square.

2. If 6 is prime, then 6² = 30.

3. Let xbe an integer. Then, x is even iffx+x²−x³ is even.

4. There are infinitely many prime numbers.

5. There exist irrational numbersx, y such thatx^y is rational.

6. For alln∈N,n!≤nⁿ.

7. There does not exist a (input-free) C-program which will always determine whether an arbitrary (input-free)

(25)

Theorems and proofs

Contrapositive and converse

I The contrapositiveof “if A thenB” is “if¬B then ¬A”.

I A statement islogically equivalent to its contrapositive, i.e., it suffices to show one to imply the other.

I To show A iffB, you have to show Aimplies B and conversely,B impliesA.

I Note the difference between contrapositive and converse.

(26)

Proof by contradiction

Theorem 4.: There are infinitely many primes.

Proof by contradiction:

I Suppose there are only finitely many primes, say p1< p2< . . . < pr.

I Letk= (p1∗p2∗. . .∗pr) + 1. Thenk when divided by any pi has remainder 1. Sopi6 | kfor all i∈ {1, . . . , r}.

I But k >1 andk is not prime, sok can be written as a product of primes (why?)

I Fundamental theorem of arithmetic: any natural number

>1 can be written as a unique product of primes.

I Now let p|k. Butp6∈ {p₁, . . . , p_r}, so this is a contradiction.

(27)

Proof by contradiction

I Suppose there are only finitely many primes, say p1 < p2< . . . < pr.

I Letk= (p1∗p2∗. . .∗pr) + 1. Thenk when divided by any pi has remainder 1. Sopi6 | kfor all i∈ {1, . . . , r}.

(28)

Proof by contradiction

I Letk= (p1∗p2∗. . .∗pr) + 1. Thenk when divided by any p_i has remainder 1. Sop_i6 | kfor all i∈ {1, . . . , r}.

(29)

Proof by contradiction

(30)

Proof by contradiction

(31)

Proof by contradiction

I Now letp|k. Butp6∈ {p₁, . . . , p_r}, so this is a contradiction.

(32)

A Non-constructive proof

Theorem 5.: There exist irrational numbersx and y such that x^y is rational.

Proof:

I Consider √

2. First show that √

2 is irrational.

I Let x=y=√

2 and considerz=√ 2

√ 2.

I Case 1: If z is rational, we are done (why?)

I Case 2: Elsez is irrational.

I Then considerz

√2= (√ 2

√2

)

√2= (√

2)²= 2.

I Thus we have found two irrationalsx=z, y=√

2 such that x^y= 2 is rational.

Indeed, note that the above proof is not constructive!

(H.W): Find a constructive proof of this theorem.

(33)

A Non-constructive proof

Proof:

I Consider √

2 is irrational.

I Let x=y=√

√ 2.

I Then considerz

√2= (√ 2

√2

)

√2= (√

2)²= 2.

(34)

A Non-constructive proof

Proof:

I Consider √

2 is irrational.

I Let x=y=√

√ 2.

I Then considerz

√2= (√ 2

√2

)

√2= (√

2)²= 2.

(35)

A Non-constructive proof

Proof:

I Consider √

2 is irrational.

I Let x=y=√

√ 2.

I Then considerz

√2= (√ 2

√2

)

√2= (√

2)²= 2.

(36)

A Non-constructive proof

Proof:

I Consider √

2 is irrational.

I Let x=y=√

√ 2.

I Then considerz

√2= (√ 2

√2

)

√2= (√

2)²= 2.

(37)

A Non-constructive proof

Proof:

I Consider √

2 is irrational.

I Let x=y=√

√ 2.

I Then considerz

√2= (√ 2

√2

)

√2= (√

2)²= 2.

(38)

A Non-constructive proof

Proof:

I Consider √

2 is irrational.

I Let x=y=√

√ 2.

I Then considerz

√2= (√ 2

√2

)

√2= (√

2)²= 2.

(39)

A Non-constructive proof

Proof:

I Consider √

2 is irrational.

I Let x=y=√

√ 2.

I Then considerz

√2= (√ 2

√2

)

√2= (√

2)²= 2.

(40)

Types of proofs

1. If mand n are perfect squares of integers, thenmn is also a perfect square.

– Direct proof

2. If 6 is prime, then 6² = 30.

–Vacuous/trivial proof

3. Let xbe an integer. Then, x is even iffx+x²−x³ is even.

–Both directions, by contrapositive (A→B=¬B→ ¬A)

4. There are infinitely many prime numbers.

– Proof by contradiction

5. There exist irrational numbersx, y such thatx^y is rational.

–Non-constructive proof

6. For alln∈N,n!≤nⁿ.

7. There does not exist a (input-free) C-program which will always determine whether an arbitrary (input-free) C-program will halt.

(41)

Types of proofs

1. If mand n are perfect squares of integers, thenmn is also

a perfect square. – Direct proof

2. If 6 is prime, then 6² = 30. –Vacuous/trivial proof 3. Let xbe an integer. Then, x is even iffx+x²−x³ is even.

–Both directions, by contrapositive (A→B=¬B→ ¬A) 4. There are infinitely many prime numbers.

– Proof by contradiction 5. There exist irrational numbersx, y such thatx^y is rational.

–Non-constructive proof 6. For alln∈N,n!≤nⁿ.

7. There does not exist a (input-free) C-program which will always determine whether an arbitrary (input-free) C-program will halt.