Six Concepts of Discrete Mathematics MAT1348

Six Concepts of Discrete Mathematics MAT1348

1. Ch1: Logic and Proofs

   • Logic (5 Main Ideas)
     • Truth tables
     • 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)
     • 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
     • 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"
     • 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...
   • Proofs (5 Main Ways)
     • Direct
     • By cases
       • Knights and knaves
         • Usually proof by cases to validate truthfulness of statements
     • Induction
     • Indirect
     • Contradiction

2. Ch2: Sets, Functions, Sequences, Sums

   • Functions (mappings, transformations)
     • 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
     • Bijective
       • Inverse functions
       • Both one-to-one and onto
     • 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
     • Compostions
       • f(g(a))
     • 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
   • Sets
     • 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
     • 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
     • Principles
       • Equality
       • Comprehension
     • Any collection of elements (either specified, or satisfying a property)

3. Ch9: Relations

   • Equivalence relations
     • Classes
       • Set of all b in A for which a R b stands
     • Partitions
       • Disjoint sets whose union is the original set
     • An equivalence relation is any relation which is reflexive, symmetric and transitive.
   • Definition + Notations
     • 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)
     • In its most intuitive form, a relationship exists between two elements of sets.
     • We use the notation a R b to say that (a,b) belong to the set/relation R
     • We can also say a is related to b by R
   • Properties
     • Symmetry
       • Every PAIR in the relation has a "converse" pair
     • Reflexivity
       • Every element in the SET is related to itself
     • Transitivity

4. Ch6: Counting

   • Pigeon hole principle
     • 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
     • 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
   • Combination and Permutation
     • Permutations are ordered arrangements of objects
       • n!/(n-r)!
     • Combinations are arrangements of objects inwhich the order does not matter
       • n!/r!(n-r)!
       • C(n, n-r) = C(n, r)
   • 3 Rules
     • 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.
     • 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.
     • 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
   • Binomial Coefficients and Binomial Theorm

5. Ch5: Induction and Recursion

   • Simple/weak
     • TODO: EXPAND THIS FROM "INDUCTION RUNDOWN" IN NOTES

6. Ch10: Graphs

   • Isomorphism
   • Cycles
   • Trees
   • Directed graphs
   • Simple graphs
   • Bipartite graphs (multiple colors, dimensions, etc)