{"ad_unit_id":"App_Resource_Sidebar_Upper","width":300,"height":250,"rtype":"MindMap","rmode":"canonical","sizes":"[[[0, 0], [[300, 250]]]]","custom":[{"key":"env","value":"production"},{"key":"rtype","value":"MindMap"},{"key":"rmode","value":"canonical"},{"key":"uauth","value":"f"},{"key":"ulang","value":"en_us"}]}

{"ad_unit_id":"App_Resource_Sidebar_Lower","width":300,"height":250,"rtype":"MindMap","rmode":"canonical","sizes":"[[[0, 0], [[300, 250]]]]","custom":[{"key":"env","value":"production"},{"key":"rtype","value":"MindMap"},{"key":"rmode","value":"canonical"},{"key":"uauth","value":"f"},{"key":"ulang","value":"en_us"}]}

Register for free tools and resources

- Build free Mind Maps, Flashcards, Quizzes and Notes
- Create, discover and share resources
- Print & Pin great learning resources

2437766

{"ad_unit_id":"App_Resource_Leaderboard","width":728,"height":90,"rtype":"MindMap","rmode":"canonical","placement":1,"sizes":"[[[1200, 0], [[728, 90]]], [[0, 0], [[468, 60], [234, 60], [336, 280], [300, 250]]]]","custom":[{"key":"env","value":"production"},{"key":"rtype","value":"MindMap"},{"key":"rmode","value":"canonical"},{"key":"placement","value":1},{"key":"uauth","value":"f"},{"key":"ulang","value":"en_us"}]}

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

1.1.2.1 Two expressions are called
equivalent if their values in a truth
table are the same.

1.1.2.2 Two expressions are equivalent
if you can reach one from the
other via rules of inference

1.1.2.2.1 This can be used to simplify
expressions

1.1.2.2.2 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)

1.1.3.1 Modus Ponens

1.1.3.1.1 Affirms by Affirming

1.1.3.1.2 p is true, and p -> q,
then q MUST be true

1.1.3.2 Modus tollens

1.1.3.2.1 Denies by denying

1.1.3.2.2 If q is false, and p->q
then p MUST NOT be true

1.1.3.3 Hypothetical Syllogism

1.1.3.3.1 Things follow from each
other

1.1.3.3.2 If p->q is true, and q->r is true,
then p->r MUST be true

1.1.3.4 Disjunct Syllogism

1.1.3.4.1 If p or q is true and p is not true,
then q MUST be true

1.1.3.4.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.

1.1.3.4.3 Elimination (a big truth
composed of a true v false
components)

1.1.3.5 Addition

1.1.3.5.1 If p is true, then
p v q MUST be
true.

1.1.3.6 Simplification

1.1.3.6.1 If two things are both true,
then one of them MUST be
true.

1.1.3.6.2 Two truths are separable

1.1.3.7 Conjunction

1.1.3.7.1 p is true, q is true,
then p and q MUSt
be true

1.1.3.8 Resolution

1.1.3.8.1 My house is either red or it is blue

1.1.3.8.1.1 My house is not red or it is yelow

1.1.3.8.1.1.1 My house MUST be either blue or yellow

1.1.3.8.2 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

1.1.4.1 Negation

1.1.4.1.1 !p

1.1.4.1.2 "not p"

1.1.4.1.3 "it is not the
case that p"

1.1.4.2 Conjunction

1.1.4.2.1 "p and q"

1.1.4.2.2 "p but q"

1.1.4.3 Disjunction (Inclusive
OR)

1.1.4.3.1 "p or q, or both"

1.1.4.3.2 "p unless q"

1.1.4.4 Disjunction
(Exclusive OR)

1.1.4.4.1 Watch out, vague and depends on context

1.1.4.4.2 "Either p or q"

1.1.4.4.3 "p or q, but not both"

1.1.4.5 Biconditional Implication (iff)

1.1.4.5.1 p <-> q

1.1.4.5.2 "p is necessary and
sufficient for q"

1.1.4.6 One-way Implication (if)

1.1.4.6.1 p -> q

1.1.4.6.1.1 p is called the
hypothesis or
premise

1.1.4.6.1.2 q is called the
conclusion or
consequence

1.1.4.6.1.3 p and q are both
called conditions or
operands

1.1.4.6.2 "p implies q"

1.1.4.6.3 "If p then q"

1.1.4.6.4 "p only if q"

1.1.4.6.5 "q follows from p"

1.1.4.6.6 Sufficient ->
Necessary <-

1.1.4.6.6.1 That is to say, if p->q (if p
implies q) is definitely true ...

1.1.4.6.6.1.1 p is a SUFFICIENT (NOT a must) reason to
conclude that q is true

1.1.4.6.6.1.2 q is a necessary reason (it MUST be
true) to conclude that p is true

1.1.4.6.7 "q if p"

1.1.4.6.7.1 "q unless not p"
(grammatical double
negation)

1.1.4.6.8 "q whenever p"

1.1.5 Truth trees

1.1.5.1 Used for...

1.1.5.1.1 Finding disjunctive normal forms

1.1.5.1.1.1 A DNF is an OR of ANDs
(sum of products)

1.1.5.1.2 Consistency

1.1.5.1.3 Tautologies (true in every universe)

1.1.5.1.3.1 A statement that
is ALWAYS true

1.1.5.1.3.2 If p=q is a tautology, then p and q
are equivalent

1.1.5.1.4 Checking validity of arguments

1.1.5.1.4.1 An argument is valid if the
conjunction of the hypothesis ->
conclusion of argument is a tautology
in every universe...

1.1.5.2 Method...

1.1.5.2.1 See Ch1 Expansion

1.1.5.3 Theory...

1.2 Proofs (5 Main Ways)

1.2.1 Direct

1.2.2 By cases

1.2.2.1 Knights and knaves

1.2.2.1.1 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)

2.1.1.1 f(a)=f(b) implies a=b

2.1.1.2 Never assigns
the same value
to two domain
elements

2.1.1.3 Examples

2.1.1.3.1 x^2 is not
one-to-one
because
(-2)^2 and
(2)^2 both
give 4

2.1.2 Bijective

2.1.2.1 Inverse functions

2.1.2.2 Both one-to-one and
onto

2.1.3 Surjective (onto)

2.1.3.1 Every element
in output is
"reachable"
via function

2.1.3.1.1 For every b in B,
there's an a in A
such that f(a)=b

2.1.4 Compostions

2.1.4.1 f(g(a))

2.1.5 F from A to B means...

2.1.5.1 An assignment of one
element of B to each
element of A

2.1.5.2 A is the domain and B is the codomain

2.2 Sets

2.2.1 Operations

2.2.1.1 Cartesian
Product

2.2.1.2 Union: A ∪ B

2.2.1.2.1 A union of sets: a set that
contains elements that are at
least in one of the sets

2.2.1.3 Intersection: A ∩ B

2.2.1.3.1 Note: Disjoint sets are sets whose
intersection is the empty set

2.2.1.3.2 An intersection of sets: a set that
contains elements that are
members of all sets

2.2.1.4 Difference: A - B

2.2.1.5 Complement: ~A

2.2.1.6 Roughly corresponds to
logical/boolean equivalences
(see ch2 expansion)

2.2.1.7 De Morgan's for sets

2.2.2 important types of sets

2.2.2.1 Powersets

2.2.2.1.1 A set containing all
subsets of a given set

2.2.2.2 Empty
set

2.2.2.2.1 Contains only the
empty set itself

2.2.2.3 Infinite sets

2.2.2.3.1 N, Z, Q, R, C

2.2.2.4 Finite sets

2.2.3 Principles

2.2.3.1 Equality

2.2.3.2 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

3.1.1.1 Set of all b in A for which a R b stands

3.1.2 Partitions

3.1.2.1 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.

3.2.1.1 Examples...

3.2.1.1.1 A relationship between
a positive integer and
one it divides

3.2.1.1.2 A relationship between a
real number x and a the
value f(x)

3.2.1.2 Binary operation

3.2.1.2.1 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

3.3.1.1 Every PAIR in the relation has a "converse" pair

3.3.2 Reflexivity

3.3.2.1 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.

4.1.1.1 or at least ceil(N/k)
ways to put N objects
into k boxes

4.1.2 Associated theorms

4.1.2.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

4.2 Combination and
Permutation

4.2.1 Permutations are ordered arrangements of objects

4.2.1.1 n!/(n-r)!

4.2.2 Combinations are arrangements
of objects inwhich the order does
not matter

4.2.2.1 n!/r!(n-r)!

4.2.2.2 C(n, n-r) = C(n, r)

4.3 3 Rules

4.3.1 Product rule

4.3.1.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.

4.3.2 Sum rule

4.3.2.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.

4.3.3 Subtraction rule

4.3.3.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.4 Binomial Coefficients and Binomial Theorm

5 Ch5: Induction and Recursion

5.1 Simple/weak

5.1.1 TODO: EXPAND THIS FROM "INDUCTION RUNDOWN" IN NOTES

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)

{"ad_unit_id":"App_Resource_Leaderboard","width":728,"height":90,"rtype":"MindMap","rmode":"canonical","placement":2,"sizes":"[[[0, 0], [[970, 250], [970, 90], [728, 90]]]]","custom":[{"key":"env","value":"production"},{"key":"rtype","value":"MindMap"},{"key":"rmode","value":"canonical"},{"key":"placement","value":2},{"key":"uauth","value":"f"},{"key":"ulang","value":"en_us"}]}