Report

Review of Mathematical Notation / Terminology Sets, Venn Diagrams, Sequences, Tuples, Functions, Relations, Graphs, Strings, Languages, Boolean Logic Sets • Order doesn’t matter – {7, 6, 5} and {5, 6, 7} are the same. • In a set, repeats are “not allowed” – {7, 7} is really {7}, i.e., they describe the same set. • In a multiset, repeats are allowed – {7, 7} and {7} are different Sets • • • • • Empty set notation? Union Intersection Compliment Set Difference? Venn Diagrams • Starts with… • Ends with.. • Contains… • Questions… Sequences • Like sets, but the order matters and repeats are “allowed” • (5, 4, 7) is a different sequence than (4, 5, 7), but they would be the same set. • (5, 5, 5, 6) is a different sequence than (5, 5, 6) but they are the same set. Tuples • Its just another way of describing sequences. – 2-tuple is a pair – 3-tuple is a trio • Question: If A = {1,2} and B= {x,y,z} what is A X B? – X is the Cartesian product. – Note: This will create a set of pairs, 2-tuples, or sequences of size 2. Power Set • A = {0, 1, 2} • Power set of A is • { {}, {0}, {1}, {2}, {0,1}, {1,2}, {2,0}, {0,1,2}} • “Power Sequence” of A is • { (), (0), (1), (2), (0,1), (1,0), (1,2), (2,1)… (0,1,2), (1,2,0), (2,0,1), (2,1,0), …) • Question: What is the size of the set above? Functions • f(a) = b • Also called a mapping • Function: Domain Range – Abs: Z Z – Add: Z X Z Z – Division: Z X Z Rational Numbers • Question: Example 0.8, 0.9, and 0.10 Relation • Function whose Range is {TRUE, FALSE} is called a Predicate • Predicate whose Domain is a tuple is called a Relation. • If the Domain is a 2-tuple or pair, then its called a Binary Relation • Example: Equality of two numbers – – – – Java: a == b or a.equals(b) f(a,b) = true if a equals b, otherwise false aRb, where R is the equality Relation F: Z X Z {TRUE, FALSE} Equivalence Relation • Satisfies three conditions 1. Reflexive: xRx is always true 2. Symmetric: if xRy is true, then yRx is true 3. Transitive: if xRy and yRz are true, then xRz is true. • Problems: Are the following Relations equivalence relations: – Equality x == y – Less-than x < y – F(x,y) = true if x+y is even, otherwise false Graphs • • • • • • • Directed vs. undirected Nodes/vertices Edges Degree Labeled graph Sub-graph Path • • • • • • Cycle Simple cycle Tree Root node Leaf nodes Strongly connected directed graphs Languages • • • • • • Alphabet notation No quotes Empty string Substring Concatenation Lexiographic ordering Boolean Logic • • • • • And Or Not XOR Distributive law