Discrete Mathematics Essentials
Explore the essential concepts covered in a Discrete Mathematics course for Computer Science, including Boolean logic, data representation, proofs, and number theory algorithms. Learn about translating English to logic, connectives, quantifiers, and more.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE 20: Discrete Mathematics for Computer Science Prof. Shachar Lovett
2 Final review
3 What did we study? Boolean logic: propositions, predicates, formulas, truth tables, CNFs, DNFs Data representation: graphs, sets, functions, relations, equivalence relations Proofs: direct, contrapositive, contradiction, cases, induction, strong induction Number theory: factorization to primes, GCD, basis representation, modular arithmetics Number theory algorithms: div-mod, fast exponentiation, casting out 9s
4 What did we really study? Language of mathematics Expressing intuitive (or not so much) ideas in a formal language Giving formal proofs for mathematical theorems
5 Boolean logic
6 Propositional logic What is a proposition? How to translate from English to logic, and vice versa Connectives Truth tables CNFs, DNFs Equivalence rules
7 Propositional logic You should know: Translating English from/to logic Negating / De-Morgan laws Computing truth tables from formulas Computing CNFs / DNFs from truth table Equivalence rules, derivation rules
8 Predicate logic Universal / existential quantifiers Multiple quantifiers Negation / De-Morgan laws The importance of the domain
9 Predicate logic You should know: Translating English from/to logic Negating / De-Morgan laws Equivalence rules, derivation rules Deciding if a quantified formula is true/false in a specific domain
10 Data representation
11 Graphs What do graphs represent? Examples.. Terminology: vertices, edges, degree Directed / undirected graphs (Eulerian graphs not for final)
12 Sets Definition, notations, examples Operations: union, intersection, complement, difference, power set, Cartesian product Expressing sets (eg primes) using set builder notation Venn diagrams, algebraic / symbolic proofs Set sizes, and how these change under the above operations Infinite sets
13 Relations What do they represent? Examples.. Connection to graphs Types: reflexive, symmetric, transitive How to prove / disprove that a relation is reflexive / symmetric / transitive
14 Equivalence relations Definition How to prove/disprove Important example: modular arithmetics (equivalent MOD m)
15 Functions Definition, examples Injective, surjective, bijective Inverse function Proving properties of set sizes using functions
16 Proofs
17 Direct proof To prove p q Assume p, plug in definitions, derive q
18 Contrapositive proof To prove p q Prove instead ~q ~p Assume ~q, plug in definitions, derive ~p
19 Proof by contradiction To prove p q Assume p,~q and derive a contradiction (either to one of the assumptions, or to a basic axiom)
20 Proof by cases To prove p q Partition assumption p into cases Prove each case individually, using any of the previous proof techniques
21 Induction Useful to prove theorems of the form: for all n>=1, some P(n) holds Base: n=1 (say) Basic induction: assume true for n-1, prove for n Strong induction: assume true for all k=1, ,n-1, prove for n
22 Number theory + algorithms
23 Primes Definition of primes / composites Every integer has a unique factorization as a product of prime numbers If p is prime, p|xy p|x or p|y Hard to factor a number to primes basis for RSA encryption
24 GCD Greatest common divisor of 2 numbers Can find efficiently using Euclid s algorithm
25 Modular arithmetics Definitions x MOD m Addition, multiplication Inversion when m is prime
26 Number theory algorithms DIV-MOD: Divide a by b, get quotient q and reminder r: a=bp+r Fast exponentiation: compute ab using only ~log(b) multiplications Casting out 9s: check if a number is divisible by 9
27 Review questions
28 Question 1 Let ?:? ? be given by ? ? = ?2 Is it A. Injective B. Surjective C. Both D. Neither
29 Question 2 Let X,Y be finite sets, and let ?:? ? be an injective function Is it necessarily true that A. |X|<|Y| B. |X| |Y| C. |X|>|Y| D. |X| |Y|
30 Question 3 Let G be an undirected graph with n vertices and no loops. What is the maximal possible number of edges in G? A. n B. n2 C. n(n-1)/2 D. n2/2
31 Question 4 Which of the following is a CNF A. ? ? ? ? (? ?) ? ? ? ? (? ?) B. C. D.
32 Question 5 Let A,B be finite sets, which of the following is the inclusion-exclusion principle ? ? ? + |?| ? ? = ? + ? |? ?| ? ? = ? + ? + |? ?| ? ? = ? + ? + |? ?| A. B. C. D.
33 Question 6 Which prices can you pay using only 2- cent and 4-cent coins? A. Any price ? 1 B. Any price ? 2 C. Any even price ? 2 D. Any odd price ? 2
34 Some words for conclusion I enjoyed teaching you, I hope that you enjoyed the class as well I hope that it opened your mind to the wonderful world of mathematics, and its many applications in computer science; this was just the first step Good luck in the final!
