Discrete Math Concepts: Algorithms, Number Representations, Boolean Logic

Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/

Todays topics Final review A few words about the final Concluding remarks

What did we learn? Concepts Proof techniques Basic algorithms Number representations Boolean logic Sets Functions Relations Modular arithmetic Direct Contraposition Contradiction Cases Induction Strong induction Analyzing and proving properties of all the new concepts that we learned, using the various proof techniques

CONCEPTS

Basic algorithms 1. Russian peasant multiplication 2. Fast powering 3. Casting out 9s 4. Euclid s algorithm Main questions: Do they always terminate? Do they return the correct answer? How fast?

Number representations Representation integers in different bases Converting between bases Addition, subtraction

Boolean logic Propositional logic Truth tables, formulas, DeMorgan laws Predicate logic Free variables Quantified variables

Propositional logic: basic connectives Basic connectives on 1 and 2 bits: NOT AND OR XOR IMPLIES IFF Representation of these basic connectives as truth tables

Propositional logic: general formulas More complicated predicates: Representation as a truth table Representation as a formula using the basic connectives Converting between these representations: formula truth table Truth table formula (in fact, DNF) Special cases: tautology, contradiction

Propositional logic: negation Negation: How to negate a truth table How to negate a Boolean formula: 1. Converting formula to use only AND,OR,NOT 2. DeMorgan laws

Predicate logic Propositions can have inputs Eg P(x)= x is even Variables can be free or quantified , Converting from English to predicate logic, and back Nested quantifies Negation

Simplifying formulas Either propositional logic or predicate logic Simplification rules (eg ? ~? = ?) Derivation rules Implication, what it means, contrapositive form Converse error Contradictions

Sets Definition of sets Two basic operations: Being a member of a set: ? ? Being a subset of a set: ? ? Relation between them: ? ? ?,? ? ? ? Basic operations on sets: Union: A ? = {?:? ? ? ?} Intersection: A ? = {?:? ? ? ?} Difference: A\? = {?:? ? ? ?} Complement: ??= ?\A Empty set: = {}

Sets Representations of sets: Algebraic / symbolic Venn diagrams More operations: Power set: ? ? = {?:? ?} Cartesian product: ? ? = { ?,? :? ?,? ?}

Sets Important sets of integers = integers = natural numbers = {1,2,3,4, } ? ?:?,? ,? 0 = rational numbers = = real numbers

Functions Basic definition ?:? ? Examples Properties of functions: One-to-one / injective Onto / surjective Bijective (both one-to-one and onto) Inverse Pigeonhole principle

Relations Relation R on universe U: ? ? ? Notation: ??? means ?,? ? Examples, viewing relations as graphs Properties: Reflexive: ? ?,??? Symmetric: ?,? ?,??? Transitive: ?,?,? ?, ??? ??? ??? ???

Equivalence relations Relations which are reflexive, symmetric, transitive Examples Equivalent definition: partition the universe to equivalence classes Important example: modular arithmetic

Modular arithmetic Definition of modular classes Addition Multiplication Subtraction Division (when possible) Examples of applications

Order relations New property of relations: Anti-symmetric: ? ?,~(??? ???) Order relation : reflexive, anti-symmetric, transitive Partial order, total order Maximal, maximum, minimal, minimum

PROOF STRATEGIES

Direct proof To prove ? ? Assume p WTS q Show that q follows logically from p using Logic Axioms Arithmetics

Contrapositive proof To prove ? ? Deduce contrapositive form ~? ~? Assume ~q WTS ~p Show that ~p follows logically from ~q using Logic Axioms Arithmetics

Proof by contradiction To prove ? ? Assume p,~q WTS contradiction Show that if we assume that both p and ~q hold, we can derive a contradiction to either an assumption we made (eg p or ~q), or a basic mathemtical law (eg 0=1)

Proof by cases To prove ? ? Assume p WTS q Break the proof into several cases Show that cases cover all options Show that in each case, q follows from p and the assumptions in the specific case

Proof by induction To prove ? 1,?(?) Prove: Base case: ? 1 Inductive claim: ? 1,? ? ?(? + 1) The proof of the inductive claim can be in any of the proof techniques that we learned (direct, contrapositive, contradiction, cases)

Proof by strong induction To prove ? 1,?(?) Prove: Base case: ? 1 Inductive claim: ? 1,(? 1 ? ? ) ?(? + 1) The proof of the inductive claim can be in any of the proof techniques that we learned (direct, contrapositive, contradiction, cases) Useful when several previous cases are needed in order to establish the next step

PROOFS FOR CONCEPTS

Proofs for algorithms We proved that all the algorithms that we learned Terminate Return the correct answer Analyzed their time complexity (how fast do they terminate) We proved various properties of them loop invariants

Proofs for sets We proved various properties of sets Inclusion-exclusion: ? ? + ? ? = ? + ? Size of power set: If ? = ? then ? ? = 2? Closure properties: assuming that the integers are closed under addition and multiplication (which we take as an axiom), we proved that the rationals are also closed under addition and multiplication

Proofs for functions We proved relations between properties of functions and the relative sizes of the domain and co-domain (which we assumed are finite sets) If ?:? ? is one-to-one then ? |?| If ?:? ? is onto then ? |?| So, we can prove ? |?| by either finding a one-to-one function from X to Y, or an onto function from Y to X Pigeonhole principle

Proofs for relations Proved that the two definitions of equivalence relations are indeed equivalent: 1. Reflexive, symmetric, transitive 2. Partitions the universe to equivalence classes Modular arithmetic: Given by equivalence classes (a mod m) Proved that is allows for addition, subtraction, multiplication and division (whenever possible) Used it to prove theorems about numbers

Arithmetic proofs Relations between even/odd integers Eg: if x,y are odd then x*y is odd Sums, products: Eg: 1 + 2 + + ? =? ?+1 2 Rational/irrational numbers Eg: 2 is not rational Factorization to primes, division Eg: ? ,2 ?2 4 ?2

FINAL

The final Monday 3/16, 3-6pm, in class Bring only a pen, no other material is allowed Material: everything we learned, except for the last week (eg no Knights & Knaves, no infinite sets) Questions: 6 questions 1 bonus question Level: similar to the midterms

How to prepare? Go over all the lectures, make sure that you understand everything. Make sure that you can prove for yourself all the problems we discussed in class Go over homework. Make sure that you can solve all the questions. Review questions: same

How to prepare? Proofs: go over solutions of homeworks, midterms, review questions Make sure that you know that difference between good proofs and bad proofs If some of your proofs in homework/midterm were not good, make sure that you know why, and know not to repeat the same mistake again

CONCLUDING REMARKS

Concluding remarks I enjoyed teaching you the class; I hope that you enjoyed taking it, and that you learned some new concepts, and some new ways of rational thinking I want to keep improving the class, so that students next year will have an even better experience, so: Please fill in your CAPEs today. I want to know all that is good and bad about the class. I will send a survey after the final, with various questions on the class. Please take the time to fill it in. If you feel comfortable, I appreciate any feedback Please try to make constructive comments

Thanks, and good luck in your finals !