Posted onEdited onInComputer Science Symbols count in article: 31kReading time ≈28 mins.
Notes of COSI 29A
Discrete
Mathematics: An Open Introduction Notes
Mathematical Statements Ch 0.2
A statement is any declarative sentence which is either true or
false
A statement is atomic if it cannot be divided into smaller
statements, otherwise it is called molecular
Logical connective: connect simpler statements to build more
complicated one
Binary connective: used to connect two statements, and,
or, if then, if and only if
Uniary connective: used for only one statement,
not
Priority: not > and > or > xor > implies > iff
Truth value
true, false
The truth value of a molecular statement is determined on the truth
of its atomic statements and the connectives
Propositional variable(aka sentential variable), used to stand
for(usually atomic) statements
The content of the statement does not matter, only the truth value
matters
Notation: P, Q, R
More notations
Conjunction: P and Q,
Disjunction: P or Q,
Implication/Condition: if P then Q/P only if Q, , P is
hypothesis/antecedent, Q is conclusion/consequent
Biocondition: P if and only if Q,
Negation: not P,
Truth conditions
: if P is true,
then true if Q is true, otherwise false; if P is false, then true for
always. Another way, if Q is true, then always true
If a and b are legs of a right triangle with hypotenuse c, then
Converse and Contrapositive
Conver of is
, the converse and
the original statement can have different truth values
Contrapositive statement of is , the contrapositive and the original statement have the
same truth value
Implication Equivalence
A implies B
A only if B
if A then B
B if A
B when A
A is sufficient for B
B is necessary for A
Predicates and Quantifiers
A boolean function with one or more variables is not a statement, it
is ap predicate
Two quantifiers: existential and universal
Existential: , there
exists/there is,
means there is a number that is less than 0
Universal: , for
all/every,
means every number that is greater than or equal to 0
Negation:
is
equivalent to
is
equivalent to
Implications quantifiers: in order for a predicate to become a
statement, we implicitly assume the variable is universally
quantified
Propositional Logic Ch 3.1
A proposition is a statement, propositional logic studies the ways
statements can interact with each other
We can use truth table to determine the truth value of a
proposition
Logically equivalence: if both statements are both true or both
false(they have the same truth value), then they are logically
equivalent
De Morgan's Laws
is equivalent
to
is equivalent
to
Implications are disjunctions: is equivalent to
Double negation: is
equivalent to P
Negation of an implication: is equivalent to
Decutsion: given a set of true premises, the conclusion should be
true
Predicate logic extends propositional logic
Proofs Ch 3.2
Proof by contradiction
Proof is an argument. The argument is valid so conclusion must be
true if premises are true
To prove P is true, we prove is true, where Q is false, this implies P is
true
Direct Proof
Proof by contrapositive: prove using
Pigeonhole Principle: If more than n pigeons fly into n pigeon
holes, then at least one pigeon hole will contain at least two
pigeons
Proof by (counter) example
For existential statement, we can prove by finding one example
In order for a statement to be not valid, find an example where its
negation is true
Proof by cases: the statement is true for all cases
Sets Ch 0.3
Introduction
A set is an unordered collection of objects
Two sets are equal if they contain the same elements
Notation
A is the set containing the elements 1, 2 and 3:
a is an element of set A:
a is not an element of set A:
even numbers:
The notation is often called the set builder notation
Special Sets
empty set:
universal set:
natural numbers:
integers:
rational numbers:
real numbers:
complex numbers:
power set of A:
Set notation
,
,
,
, ,
Venn Diagrams
Functions Ch 0.4
Introduction
A function is a rule that assigns each input exactly one output, the
output is the image of the input, the set of inputs is called the
domain, the set of all allowable outputs is called the codomain, the set
of actual outputs is called the range
Notation: ,
the function with name , domain
, and codomain
Describing functions
Rule of four: each function can be described in four ways,
algebracially(a formula), numerically(a table), graphically, or in
words
Using an explicit formula to calculate the image of any element in
the domain is a great way to describe a function, and these explicit
rules are closed formulas for the function
Surjections, Injecetions, and Bijections
Surjection: the function is onto or the function maps the domain
onto the codomain, the codomain is just the range
Injection: for one element in the codomain, it can be the image of
at most one element in the domain, then the function is one-to-one or
injective
Bijection: if a function is both onto and injective, then it is
called bijective function or bijection
Image and Inverse Image
Image of A: \(f(A) = \f(a) \in Y: a \in
A{\}\)
Inverse image of B:
Notice: is the
complete inverse image of under
, it is not the image of under , because may not exist
Some results
if is injective: then
f is injective. if is
surjective, then g is surjective
if , we can prove
for every , there is
, then
Consider , then f is not surjective, g is not
injective
if f and g are injective/surjective/bijective, so is
Generally, ,
when f is injective, we have
Generally, we don't know . If f is injective, , if f is surjective, , if f is bijective,
The two sets are equal when f is injective
Proper subset example:
The two sets are equal when f is surjective
Proper subset example:
Additive and Multiplicative Principles Ch 1.1
Additive principle: if event A can occur in m ways, and event B can
occur in n disjoint ways, then the event A or B can occur in m + n
ways
Multiplicative principle: if event A can occur in m ways, and each
possibility for A allows for exactly n ways for event B, then the event
A and B can occur in m * n ways
Additive principle with sets: Given two sets A and B, if , then
Cartesian Product: Givens sets A and B, we can form the set
Multiplicative principle with sets: Given two sets A and B, we have
Cardinality of two-set union:
Cardinality of three-set union
Binomial Coefficients Ch 1.2
Power set:
Big Strings
Bit is short for binary digit
A n-bit string is a bit string of length n. That is, it's a string
containing n symbols, each of which is a bit, either 0 or 1
The weight of a bit string is the number of 1's in it
is the set of all n-bit
strings
is the set of all
n-bit strings of weight k
Obviously:
Lattice Paths
The integer lattice is the set of all points in the Cartesian plane
for which both the x and y coordinates are integers
A lattice path is one of the shortest possible paths connecting two
points on the lattice, moving only horizontally and vertically
Binomial Coefficients
Binomial coefficients are the coefficients in the expanded version
of a binomial
For each integer and
integer k with
there is a number ,
reads n choose k
is the number of
subsets of a set of size n each with cardinality k
is the number of
lattice paths of length n containing k steps to the right
is the coefficient
of in the expansion of
is the numebr of
ways to select k objects from a total of n objects
Pascal's Triangle
Combinations and Permutations Ch 1.3
Permutation is a possible rearrangement of objects
There are permutations of n(distinct)
elements
k-permutation of n elements: , the number of ways to arrange k objects chosen from n
distinct objects:
Closed formula for :
Combinatorial Proofs Ch 1.4
Binomial identity
Combinatorial proof
Find a counting problem you will be able to answer in two ways.
Explain why one answer to the counting problem is A
Explain why the other answer to the counting problem is B
Since both A and B are the answers to the same question, we must
have A = B
Sequences
Describing Sequences Ch 2.1
A sequence is simply an ordered list of numbers
Notation: . If we omit ,
then the sequence is . n is called index
Closed formula: a closed formula for is a formula for
using a fixed finite number of
operations on n
Recursive definition: a recursive definition(sometimes called an
inductive definition) for a sequence consists of a
recurrence relation: an equation relating a term of the sequence to
previous terms and an initial condition: a list of a few terms of the
sequence
Common sequences
Square numbers:
Triangle numbers:
The fibonacci numbers: with
Arithmetic and Geometric Sequences Ch 2.2
If the terms of a sequence differ by a constant, we say the sequence
is arithmetic. If the initial term of the sequence is a and the common
difference is d, then we have recursive definition: with , closed formula:
A sequence is called geometric if the ratio between successive terms
is constant. Suppose the initial term is an the common ratio is r, then we
have recursive definition: with , closed formula:
Summing arithmetic sequences: reverse and add
Formula:
Summing geometric sequences: multiply, shift and subtract
Formula:
Polynomial Fitting Ch 2.3
Difference
For sequence ,
its first difference is , its second difference is
If the order difference of
a sequence is constant, then we say a sequence is a -constant sequence
If a sequence is arithmetic, then it is -constant
Finite difference
The closed formula for a sequence will be a degree polynomial if and only if the sequence
is -constant
You can try differencing the sequence for some degrees, if the
difference consequence is constant, then you can use polynomial fitting
to find the closed form for the sequence
Solving Recurrence Relations Ch 2.4
Characteristic equations: Suppose , its characteristic equation
is
If and are two distinct roots of the
characteristic eqution, then the solution to the recurrence relation is
, where a and b are constants determined by the
initial conditions
If there is only one solution to the characteristic equation,
then the solution to the recurrence relation is , where
a and b are constants determined by the initial conditions
Induction Ch 2.5
Induction Proof Structure: Let be the statement, to prove is true for all , you must prove two facts:
Base case: Prove that is
true, you do this directly, this is often easy
Inductive case: Prove that for all . This is the proof of an if-then statement, so you can assume
(it's called the inductive
hypothesis) is true, you must then explain why is also true, given that
assumption
Then by the principle of mathematical induction, the statement is true for all
Strong induction proof structure: Let be the statement, to prove is true for all , you must prove two facts:
Base case: Prove that is
true
Inductive case: Assume is
true, for all , prove that
is true
Some results
Consider the Riemann zeta function:
We have
Graph Definition Ch 4.1
Definition: a graph is an ordered pair consisting of a nonempty set V (called the vertices)
adn a set E (called the edges) of two-element subsets of V
Isomorphic Graphs: a isomorphism between two graphs and is a bijection between the
vertices of the graphs such that is an edge in iff
is an edge in
. Two graphs are isomorphic if
there is an isomorphism between them. In this case we write
Subgraphs: is a subgraph of
, and write , provided and . is a induced
subgraph of , provided
and every edge
in E whose vertices are in
is also an edge in
Simple graph: no pairs of vertices is connected more thant once, and
no vertex is connected to itself. Other graphs are multigraphs
Connected graph: there is a path between any two vertices
Complete graph: if every pair of vertices are connected by a edge,
then the graph is complete
Degree of a vertex: number of edges emanating from a given vertex
Handshake Lemma: in any graph, the sum of the degrees of vertices in
the graph is always twice the number of edges, i.e.
Proposition: in any graph, the number of vertices with odd degree
must be even
Mathematics for Computer
Science Notes
Logical Formulas Ch 3.1
Java uses && for and , || for
or
P xor Q notation:
Negation of P: , or
Validity: a valid formula is one which is always true
Satisfiability: a satisfiable formula is one which can sometimes be
true
A statement P is satisfiable iff its negation NOT(P) is not
valid
Distributive Law of And over OR:
Distributive Law of OR over AND:
Proving Equivalences:
Approach 1: use truth table, there are situations for variables
Approach 2: use algebra to prove equivalence
SAT problem: the genereal problem of deciding whether a proposition
is satisfiable is called SAT
Inference Rules Ch 3.4
Predicate Formulas Ch 3.6
General syntax:
Quantifiers
ALways true
For all is
true
is true for every
Sometimes true
There is an s.t. is true
is true for some
is true for at least one
Universal quantification: an assertion that a predicate is always
true
Existential quantification: an assertion that a predicate is
sometimes true
Mixing Quantifiers
For every even integer n greater that 2, there exists primes p and q
such that n = p +q
Order of quantifiers: swapping the order of different quantifiers
usually changes the meaning of a proposition
Variables over the domain
Simplification:
The unnamed nonempty set that x and y range over is called the
domain of discourse, or just domain
Negating quantifiers
Equivalence:
Equivalence:
Validity for Predicate Formulas
In order for a predicate formula to be valid, it should be true all
across its domain
Valid assertion:
Not valid assertion: (This is
invalid because x and y may be related, so there is no such universal
x)
What is a Proof Ch 1
Logical Deductions
Example: a proof of P and a proof P implies Q is a proof of Q.
Antecedents: P, P implies Q, Conclusion/consequent: Q
Rule
P implies Q, and Q implies R => P implies R
NOT(P) implies NOT(Q) => Q implies P
Proving an implication: P implies Q
Method 1: assume P is true, then Q logically follows
Method 2: we prove the contrapositive, then use method 1 with the
contrapositive
Proving an if and only if
Method 1: prove each statement implies the other
Method 2: construct a chain of iffs
Proof by Cases
Proof by contradiction/ indirect proof: show that if a proposition
were false, then some flse fact would be true
In order to prove P: we use proof by contradiction, supopose P is
false, deduce something false, then there is a contradiction, then P
must be true
Sets Ch 4.1
Introduction: informally, a set is a bunch of elements
Some popular sets:
Comparing and combining sets
: subset, : strict subset
Proving set equalities: to prove , we need to prove
Sequences Ch 4.2
A list of ordered eleemnts are called sequence
Use for empty
sequence
Functions Ch 4.3
A function assigns an element of one set, called the domain, to an
element of another set, called the codomain
Functions are often defined by formulas
Functions can be defined using tables
Image of set S under f:
range of f:
Function Composition: for and , the composition of g and f is
Binary Relations Ch 4.4
Binary relations define relations between two objects
Definition: a binary relation R, consists of a set A called the
domain of R, and a set B called the codomain of R, and a subset of A*B
called the graph of R. R is said between A and B, or from A to B
Relation can be function, surjective, total, injective, or
bijective
Image:
Inverse relation: ,
Inverse image:
Finite Cardinality Ch 4.5
If A is a finite set, the cardinality of A, written , is the number of elements in A
Definition
there is a surjective function from A to B
there is a injective function from A to B
there is a bijective function from A to B
Theorem: For finite sets A, B
For a finite with n elements, there are subsets
Cardinality Rule Ch 14
Counting One Thing by Counting Another Ch 14.1
Bijection Rule: if there is a bijection between two things, then
they have the same size
Counting Sequences Ch 14.2
Product rule: if are finite sets, then
Sum rule: if
are disjoint finite sets, then
Generalized Product Rule Ch 14.3
Generalized Product Rule: Let S be a set of length-k sequences. If
there are possible for first
entries, possible second
entries for each first entry, ..., possible kth entries for each
sequence of first k - 1 entries, then:
Permutations
A permutation of a set S is a sequence that contains every element
of S excatly once
There are a total of
permutations of an n-element set
Stirling's formula:
From the above formula, we have
Division rule Ch 14.4
k-to-1 function: maps exactly k elements of the domain to every
element of the codomain
Division Rule: if is k-to-1, then
Round Table Problem: arrange n knights at a round table, there is a
n-to-1 function, so there are arrangements
Counting subsets Ch 14.5
n choose k: , it
can denote the number of k-element subsets of an n-element set
Subset Rule: the number of k-element subsets of an n-element set is
Bit Sequences: the number of n-bit sequences with exactly k ones is
Sequences with repetitions Ch 14.6
Split subsets: let A be an n-element set and be nonnegative integers
whose sum is n. A -split of A is an
sequence where
are disjoint subsets of A and
for
Multinomial coefficient: for , s.t.
, define the
multinomial coefficient
Subset split rule: the number of -split of an n-element
set is
Bookkeeper rule: let be distince elements. The
amount of sequences s with
occurrences of , , and occurrences of is
The binomial theorem:
Multinomial theorem: for all
Counting practice: poker hands Ch 14.7
Poker cards have 4 suits (club, diamond, heart, spade) and 13
ranks(ace, 2, ...,10, jack, queen, king). The 2 jokers are not taken
into consideration
Hands with a four-of-a-kind: draw 5 cards, with 4 of the one rank
Answer:
Hands with a full house: draw 5 cards, with 3 of one rank and 2 of
another rank
Answer:
Hands wit two pairs: draw 5 cards, with 2 cards of one rank, 2 cards
of another rank, and 1 card of a third rank
Answer:
Hands with every suit: at least one card from every suit
Answer:
The pigeonhole Principle Ch 14.8
Pigeonhole principle: if there are more pigeons than holes they
occupy, then at least two pigeons must be in the same hole
Pigeonhole Principle
Total function: a function that is defined on all elements of its
domain is called a total function
If , then for every
total function ,
there are two different elements in A mapped to the same element in
B
Generalized pigeohole Principle: if , then every total function maps at least k + 1
different elements of A to the same element of B
Inclusion-Exclusion Ch 14.9
Union of two sets
Union of three sets
Inclusion-Exclusion:
Inclusion-Exclusion-II:
Combinatorial Proof Ch 14.10
Pascal's triangle identity:
Giving a combinatorial proof
Define a set S
Show that by counting
one way
Show that by counting
another way
Conclude that
Equality
Induction Ch 5
Ordinary induction Ch 5.1
The Induction Principle: Let P be a predicate on nonnegative
integers. If P(0) is true, and P(n) implies P(n + 1) for all nonnegative
integers n, then P(m) is true for all nonnegative integers, m
A template for induction proofs
State that the proof uses induction
Define an appropriate predicate P(n)
Prove that P(0) is true
Prove that P(n) implies P(n + 1) for every nonnegative integer
n
Invoke induction
Strong induction Ch 5.2
Principle of Strong Induction: Let P be a predicate on nonnegative
integers. If P(0) is true, and for all , P(0), P(1),..., P(n) together imply P(n + 1), then
P(m) is true for all
Events and probability space
The four step method Ch 16.2
Step 1: Find the sample space
Step 2: Define the events of interest
Step 3: Determine outcome probabilities
Step 4: Compute event probabilities
The birthday principle Ch 16.4
There are d days in a year, and there are n students, then the
probability that all students have different birthdays are
The birthday principle: if there are d days in a year, and people in a room, then the
probability that two share a birthday is about
Set theory and probability
Probability space
A countable sample space S is a nonempty countable set. an element
is called an outcome,
a ubset of S is called an event
A probability function on a sample space S is a total function s.t.
, for
all
A sample space together with a probability function is called a
probability space. For any event , the probability of E is defined to be the sum of the
probabilities of the outcome in E:
Uniform probability spaces
A finite probability space, S, is said to be uniform if is the same for every
outcome
For any event ,
Probability space can be infinite
Conditional Probability
Definition and notation Ch 17.2
The expression
denotes the probability of event X, given that event Y happens
Let X and Y be events where Y has nonzero probability. Then
Why tree diagrams work Ch 17.4
Conditional probability product rule:
Conditional probability product rule:
Bayes's rule:
The law of total probability Ch 17.5
Law to total probability on single event:
Law of total probability on 3 events, if and are disjoint and ,
then
Bayes's rule on 3 events:
Independence Ch 17.7
Definition: an event with probability 0 is defined to be independent
of every event(including itself). If , then event A is
independent of event B
A is independent of B
A set of events
is k-way independent every set of k of these
events is mutually independent. The set is pairwise independent it is 2-way
independent
Binary Relations Ch 4.4
Binary relations define relations between two objects
Definition: a binary relation, R, consists of a set, A, called the
domain of R, a set, B, called the codomain of R, and a subset of A * B
called the graph of R. R is called between A and B or from A to B. For
functions, we write
The standard properties of a relation can be visualized in terms of
a diagram: write if
and and a is associated with b in
R
arrow property: every
point in the domain column has at most one arrow coming out of it
A binary relation, R, is
a function when it has the arrow out property
surjective when it has the arrow in property
total when it has the
arrow out property
injective when it has the arrow in property
bijective when it has both the arrow out and the
arrow in property
Relational images
Definition: the image of a set Y, under a relation R, written , is the set of elements of the
codomain, B, of R that are related to some element in Y. In terms of the
relation diagram, is the set
of points with an arrow coming in that starts from some point in Y
Inverse relations
Definition: the inverse ,
or a relation ,
is the relation from B to A defined by the rule
Inverse images
Definition: the image of a set under the relation, , is called the inverse image of
the set. That is, the inverse image of a set, X, under the relation, R,
is defined to be
Inference
A formula of the predicate calculus is in prenex normal form (PNF)
if it is written as a string of quantifiers and bound variables, called
the prefix, followed by a quantifier-free part, called the matrix
Conversion to PNF
Conjunction and disjunction: when x is not a free variable of
Two examples
does
not mean
Negation
Implication: when the variable quantified in one sub-formula does
not appear free in the other sub-formula
A formula of first-order logic is in Skolem normal form if it is in
prenex normal form with only universal first-order quantifiers
Truth trees for predicate logic
Negate the conclusion
Replace each existential variable with a point to set up the domain,
if there the domain is empty(meaning there is no existential variable in
the statements), just make one, this step is called skolemization
Use points in the domain to determine if there are contradictions
If there are contradiction on each branch, then the negation of the
conclusion is wrong and then the conclusion itself is correct
If the tree has infinite branches and we cannot find a contradiction
for each branch(sometimes even the tree has infinite branches, we can
logically find a contradiction on each branch), then we cannot prove or
disprove the conclusion
Gödel's incompleteness theorems
The first theorem: Any consistent formal system F within which a
certain amount of elementary arithmetic can be carried out is
incomplete; i.e., there are statements of the language of F which can
neither be proved nor disproved in F.
The second theorem: Assume F is a consistent formalized system which
contains elementary arithmetic. Then