Six Concepts of Discrete Mathematics MAT1348

Ch1: Logic and Proofs
1. Logic (5 Main Ideas)
  1. Truth tables
  2. Equivalences
    1. Two expressions are called equivalent if their values in a truth table are the same.
    2. Two expressions are equivalent if you can reach one from the other via rules of inference
      1. This can be used to simplify expressions
      2. Or to find truthfulness of statements (if we can prove it equivalent to something we already know is true)
  3. The 8 Rules of Inference (The 8 Musts)
    1. Modus Ponens
      1. Affirms by Affirming
      2. p is true, and p -> q, then q MUST be true
    2. Modus tollens
      1. Denies by denying
      2. If q is false, and p->q then p MUST NOT be true
    3. Hypothetical Syllogism
      1. Things follow from each other
      2. If p->q is true, and q->r is true, then p->r MUST be true
    4. Disjunct Syllogism
      1. If p or q is true and p is not true, then q MUST be true
      2. 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.
      3. Elimination (a big truth composed of a true v false components)
    5. Addition
      1. If p is true, then p v q MUST be true.
    6. Simplification
      1. If two things are both true, then one of them MUST be true.
      2. Two truths are separable
    7. Conjunction
      1. p is true, q is true, then p and q MUSt be true
    8. Resolution
      1. 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
      2. If a p v q is true, and ~p v r is true, then q v r must be true
  4. Six operators and their translations
    1. Negation
      1. !p
      2. "not p"
      3. "it is not the case that p"
    2. Conjunction
      1. "p and q"
      2. "p but q"
    3. Disjunction (Inclusive OR)
      1. "p or q, or both"
      2. "p unless q"
    4. Disjunction (Exclusive OR)
      1. Watch out, vague and depends on context
      2. "Either p or q"
      3. "p or q, but not both"
    5. Biconditional Implication (iff)
      1. p <-> q
      2. "p is necessary and sufficient for q"
    6. One-way Implication (if)
      1. 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
      2. "p implies q"
      3. "If p then q"
      4. "p only if q"
      5. "q follows from p"
      6. 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
      7. "q if p"
        "q unless not p" (grammatical double negation)
      8. "q whenever p"
  5. Truth trees
    1. Used for...
      1. Finding disjunctive normal forms
        A DNF is an OR of ANDs (sum of products)
      2. Consistency
      3. Tautologies (true in every universe)
        A statement that is ALWAYS true
        If p=q is a tautology, then p and q are equivalent
      4. Checking validity of arguments
        An argument is valid if the conjunction of the hypothesis -> conclusion of argument is a tautology in every universe...
    2. Method...
      1. See Ch1 Expansion
    3. Theory...
2. Proofs (5 Main Ways)
  1. Direct
  2. By cases
    1. Knights and knaves
      1. Usually proof by cases to validate truthfulness of statements
  3. Induction
  4. Indirect
  5. Contradiction
Ch2: Sets, Functions, Sequences, Sums
1. Functions (mappings, transformations)
  1. Injective (one-to-one)
    1. f(a)=f(b) implies a=b
    2. Never assigns the same value to two domain elements
    3. Examples
      1. x^2 is not one-to-one because (-2)^2 and (2)^2 both give 4
  2. Bijective
    1. Inverse functions
    2. Both one-to-one and onto
  3. Surjective (onto)
    1. Every element in output is "reachable" via function
      1. For every b in B, there's an a in A such that f(a)=b
  4. Compostions
    1. f(g(a))
  5. F from A to B means...
    1. An assignment of one element of B to each element of A
    2. A is the domain and B is the codomain
2. Sets
  1. Operations
    1. Cartesian Product
    2. Union: A ∪ B
      1. A union of sets: a set that contains elements that are at least in one of the sets
    3. Intersection: A ∩ B
      1. Note: Disjoint sets are sets whose intersection is the empty set
      2. An intersection of sets: a set that contains elements that are members of all sets
    4. Difference: A - B
    5. Complement: ~A
    6. Roughly corresponds to logical/boolean equivalences (see ch2 expansion)
    7. De Morgan's for sets
  2. important types of sets
    1. Powersets
      1. A set containing all subsets of a given set
    2. Empty set
      1. Contains only the empty set itself
    3. Infinite sets
      1. N, Z, Q, R, C
    4. Finite sets
  3. Principles
    1. Equality
    2. Comprehension
  4. Any collection of elements (either specified, or satisfying a property)
Ch9: Relations
1. Equivalence relations
  1. Classes
    1. Set of all b in A for which a R b stands
  2. Partitions
    1. Disjoint sets whose union is the original set
  3. An equivalence relation is any relation which is reflexive, symmetric and transitive.
2. Definition + Notations
  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.
    1. Examples...
      1. A relationship between a positive integer and one it divides
      2. A relationship between a real number x and a the value f(x)
    2. Binary operation
      1. Let A and B be sets: A binary relation from A to B is a subset of A x B (Cartesian product)
  2. In its most intuitive form, a relationship exists between two elements of sets.
  3. We use the notation a R b to say that (a,b) belong to the set/relation R
  4. We can also say a is related to b by R
3. Properties
  1. Symmetry
    1. Every PAIR in the relation has a "converse" pair
  2. Reflexivity
    1. Every element in the SET is related to itself
  3. Transitivity
Ch6: Counting
1. Pigeon hole principle
  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.
    1. or at least ceil(N/k) ways to put N objects into k boxes
  2. Associated theorms
    1. Theorem 3: Every sequence n^2 + 1 distinct real numbers contains a subsequence of length n+1 is either strictly increasing or strictly decreasing
2. Combination and Permutation
  1. Permutations are ordered arrangements of objects
    1. n!/(n-r)!
  2. Combinations are arrangements of objects inwhich the order does not matter
    1. n!/r!(n-r)!
    2. C(n, n-r) = C(n, r)
3. 3 Rules
  1. Product rule
    1. 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.
  2. Sum rule
    1. 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.
  3. Subtraction rule
    1. 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. Binomial Coefficients and Binomial Theorm
Ch5: Induction and Recursion
1. Simple/weak
  1. TODO: EXPAND THIS FROM "INDUCTION RUNDOWN" IN NOTES
Ch10: Graphs
1. Isomorphism
2. Cycles
3. Trees
4. Directed graphs
5. Simple graphs
6. Bipartite graphs (multiple colors, dimensions, etc)

Next up

Six Concepts of Discrete Mathematics MAT1348

Description

Resource summary

Similar

	Created by gargantua about 9 years ago