Six Concepts of Discrete Mathematics MAT1348

Mind Map by gargantua, updated more than 1 year ago
Created by gargantua almost 5 years ago


finals mat1348 Mind Map on Six Concepts of Discrete Mathematics MAT1348, created by gargantua on 04/05/2015.

Resource summary

Six Concepts of Discrete Mathematics MAT1348
1 Ch1: Logic and Proofs
1.1 Logic (5 Main Ideas)
1.1.1 Truth tables
1.1.2 Equivalences Two expressions are called equivalent if their values in a truth table are the same. Two expressions are equivalent if you can reach one from the other via rules of inference This can be used to simplify expressions Or to find truthfulness of statements (if we can prove it equivalent to something we already know is true)
1.1.3 The 8 Rules of Inference (The 8 Musts) Modus Ponens Affirms by Affirming p is true, and p -> q, then q MUST be true Modus tollens Denies by denying If q is false, and p->q then p MUST NOT be true Hypothetical Syllogism Things follow from each other If p->q is true, and q->r is true, then p->r MUST be true Disjunct Syllogism If p or q is true and p is not true, then q MUST be true If one of two things is definitely true, and one of those two things is definitely false, then the other must be the true one. Elimination (a big truth composed of a true v false components) Addition If p is true, then p v q MUST be true. Simplification If two things are both true, then one of them MUST be true. Two truths are separable Conjunction p is true, q is true, then p and q MUSt be true Resolution My house is either red or it is blue My house is not red or it is yelow My house MUST be either blue or yellow If a p v q is true, and ~p v r is true, then q v r must be true
1.1.4 Six operators and their translations Negation !p "not p" "it is not the case that p" Conjunction "p and q" "p but q" Disjunction (Inclusive OR) "p or q, or both" "p unless q" Disjunction (Exclusive OR) Watch out, vague and depends on context "Either p or q" "p or q, but not both" Biconditional Implication (iff) p <-> q "p is necessary and sufficient for q" One-way Implication (if) p -> q p is called the hypothesis or premise q is called the conclusion or consequence p and q are both called conditions or operands "p implies q" "If p then q" "p only if q" "q follows from p" Sufficient -> Necessary <- That is to say, if p->q (if p implies q) is definitely true ... p is a SUFFICIENT (NOT a must) reason to conclude that q is true q is a necessary reason (it MUST be true) to conclude that p is true "q if p" "q unless not p" (grammatical double negation) "q whenever p"
1.1.5 Truth trees Used for... Finding disjunctive normal forms A DNF is an OR of ANDs (sum of products) Consistency Tautologies (true in every universe) A statement that is ALWAYS true If p=q is a tautology, then p and q are equivalent Checking validity of arguments An argument is valid if the conjunction of the hypothesis -> conclusion of argument is a tautology in every universe... Method... See Ch1 Expansion Theory...
1.2 Proofs (5 Main Ways)
1.2.1 Direct
1.2.2 By cases Knights and knaves Usually proof by cases to validate truthfulness of statements
1.2.3 Induction
1.2.4 Indirect
1.2.5 Contradiction
2 Ch2: Sets, Functions, Sequences, Sums
2.1 Functions (mappings, transformations)
2.1.1 Injective (one-to-one) f(a)=f(b) implies a=b Never assigns the same value to two domain elements Examples x^2 is not one-to-one because (-2)^2 and (2)^2 both give 4
2.1.2 Bijective Inverse functions Both one-to-one and onto
2.1.3 Surjective (onto) Every element in output is "reachable" via function For every b in B, there's an a in A such that f(a)=b
2.1.4 Compostions f(g(a))
2.1.5 F from A to B means... An assignment of one element of B to each element of A A is the domain and B is the codomain
2.2 Sets
2.2.1 Operations Cartesian Product Union: A ∪ B A union of sets: a set that contains elements that are at least in one of the sets Intersection: A ∩ B Note: Disjoint sets are sets whose intersection is the empty set An intersection of sets: a set that contains elements that are members of all sets Difference: A - B Complement: ~A Roughly corresponds to logical/boolean equivalences (see ch2 expansion) De Morgan's for sets
2.2.2 important types of sets Powersets A set containing all subsets of a given set Empty set Contains only the empty set itself Infinite sets N, Z, Q, R, C Finite sets
2.2.3 Principles Equality Comprehension
2.2.4 Any collection of elements (either specified, or satisfying a property)
3 Ch9: Relations
3.1 Equivalence relations
3.1.1 Classes Set of all b in A for which a R b stands
3.1.2 Partitions Disjoint sets whose union is the original set
3.1.3 An equivalence relation is any relation which is reflexive, symmetric and transitive.
3.2 Definition + Notations
3.2.1 The most basic expression of relationships mathematically is built by using ordered pairs called binary operations -- A relation is a set of such ordered pairs. Examples... A relationship between a positive integer and one it divides A relationship between a real number x and a the value f(x) Binary operation Let A and B be sets: A binary relation from A to B is a subset of A x B (Cartesian product)
3.2.2 In its most intuitive form, a relationship exists between two elements of sets.
3.2.3 We use the notation a R b to say that (a,b) belong to the set/relation R
3.2.4 We can also say a is related to b by R
3.3 Properties
3.3.1 Symmetry Every PAIR in the relation has a "converse" pair
3.3.2 Reflexivity Every element in the SET is related to itself
3.3.3 Transitivity
4 Ch6: Counting
4.1 Pigeon hole principle
4.1.1 If an association is to be made between members of set N (pigeons) and set K (box) (where N>K) then there is at least ceil(N/k) repeat connections. or at least ceil(N/k) ways to put N objects into k boxes
4.1.2 Associated theorms Theorem 3: Every sequence n^2 + 1 distinct real numbers contains a subsequence of length n+1 is either strictly increasing or strictly decreasing
4.2 Combination and Permutation
4.2.1 Permutations are ordered arrangements of objects n!/(n-r)!
4.2.2 Combinations are arrangements of objects inwhich the order does not matter n!/r!(n-r)! C(n, n-r) = C(n, r)
4.3 3 Rules
4.3.1 Product rule If a procedure can be broken down into a sequence of two tasks, one of which can be done in N ways and the second in M ways, then there are NM ways to do the procedure.
4.3.2 Sum rule If a task can be done in ONE of n ways or ONE of m ways (exclusive or), where none of the set of N ways is the same as any of the set M ways, then there are N+M ways to do the task.
4.3.3 Subtraction rule If a task can be done in either n ways or m ways -- then the number of ways to do the task is n+m minus the number of ways to do the task that are common to the two different ways
4.4 Binomial Coefficients and Binomial Theorm
5 Ch5: Induction and Recursion
5.1 Simple/weak
6 Ch10: Graphs
6.1 Isomorphism
6.2 Cycles
6.3 Trees
6.4 Directed graphs
6.5 Simple graphs
6.6 Bipartite graphs (multiple colors, dimensions, etc)
Show full summary Hide full summary


B7: Further Biology
Matthew Law
Joomla Extension
Santi Sounsri
Biology -B2
Computing Hardware - CPU and Memory
Unit 2 flashcards
yog thapa
New GCSE Maths required formulae
Sarah Egan
What are they doing?
Tamara Urzhumova
1PR101 1. test - 2. část
Nikola Truong
Specific topic 7.6 Timber (processes)
T Andrews