0%

COSI 29A Discrete Structure

Notes of COSI 29A

Discrete Mathematics: An Open Introduction Notes

  1. 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, PQ
        • Disjunction: P or Q, PQ
        • Implication/Condition: if P then Q/P only if Q, PQ, P is hypothesis/antecedent, Q is conclusion/consequent
        • Biocondition: P if and only if Q, PQ
        • Negation: not P, ¬P
      • Truth conditions
        • PQ: 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 a2+b2=c2
      • Converse and Contrapositive
        • Conver of PQ is QP, the converse and the original statement can have different truth values
        • Contrapositive statement of PQ is ¬Q¬P, 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, x(x<0) means there is a number that is less than 0
          • Universal: , for all/every, x(x0) means every number that is greater than or equal to 0
          • Negation:
            • ¬x(P(x)) is equivalent to x(¬P(x))
            • ¬x(P(x)) is equivalent to x(¬P(x))
          • Implications quantifiers: in order for a predicate to become a statement, we implicitly assume the variable is universally quantified
  2. 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
      • ¬(PQ) is equivalent to ¬P¬Q
      • ¬(PQ) is equivalent to ¬P¬Q
    • Implications are disjunctions: PQ is equivalent to ¬PQ
    • Double negation: ¬¬P is equivalent to P
    • Negation of an implication: ¬(PQ) is equivalent to P¬Q
    • Decutsion: given a set of true premises, the conclusion should be true
    • Predicate logic extends propositional logic
  3. 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 ¬PQ is true, where Q is false, this implies P is true
    • Direct Proof
    • Proof by contrapositive: prove PQ using ¬Q¬P
    • 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
  4. 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={1,2,3}
      • a is an element of set A: aA
      • a is not an element of set A: aA
      • even numbers: A={0,2,4,6,}={xN:nN(x=2n)}={xN:x is even}
      • The notation is often called the set builder notation
    • Special Sets
      • empty set:
      • universal set: U
      • natural numbers: N={0,1,2,3,}
      • integers: Z={,2,1,0,1,2,}
      • rational numbers: Q
      • real numbers: R
      • complex numbers: C
      • power set of A: P(A)
    • Set notation
      • aA, aA
      • AB, AB
      • AB, AB
      • A×B, AB, AB
      • A¯
      • |A|
    • Venn Diagrams
  5. 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: f:XY, the function with name f, domain x, and codomain Y
    • 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
        • yY,xX,s.t.y=f(x)
      • 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
        • x1X,x2X,if f(x1)=f(x2),then x1=x2
        • x1X,x2X,if f(x1)f(x2),then x1x2
      • Bijection: if a function is both onto and injective, then it is called bijective function or bijection
    • Image and Inverse Image
      • f:XY,letAX and BY
        • Image of A: \(f(A) = \f(a) \in Y: a \in A{\}\)
        • Inverse image of B: f1(B)={aX:f(a)B}
      • Notice: f1(y) is the complete inverse image of y under f, it is not the image of y under f1, because f1 may not exist
    • Some results
      • if gf is injective: then f is injective. if gf is surjective, then g is surjective
        • if x1=x2,andf(x1)=f(x2), we can prove x1=x2
        • for every zC, there is xA, then y=f(x)B
        • Consider A={1},B={1,2},C={1},f(1)=1,g(1)=g(2)=1, then f is not surjective, g is not injective
      • if f and g are injective/surjective/bijective, so is gf
      • Generally, |A||f(A)|, when f is injective, we have |A|=|f(A)|
      • Generally, we don't know |B|and|f1(B)|. If f is injective, |B||f1(B)|, if f is surjective, |B||f1(B)|, if f is bijective, |B|=|f1(B)|
      • Af1(f(A))
        • The two sets are equal when f is injective
        • Proper subset example: f:{1,2}{1},f(1)=f(2)=1
      • f(f1(B))B
        • The two sets are equal when f is surjective
        • Proper subset example: f:{1,2}{1,2,3},f(1)=1,f(2)=2
      • f(AB)=f(A)f(B)
      • f1(AB)=f1(A)f1(B)
      • f(AB)f(A)f(B)
        • f:{0,1}{0,1},f(0)=f(1)=1
      • f1(AB)=f1(A)f1(B)
  6. 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 AB=, then |AB|=|A|+|B|
    • Cartesian Product: Givens sets A and B, we can form the set A×B={(x,y):x A and yB}
    • Multiplicative principle with sets: Given two sets A and B, we have |AB|=|A||B|
    • Cardinality of two-set union: |AB|=|A|+|B||AB|
    • Cardinality of three-set union |ABC|=|A|+|B|+|C||AB||AC||BC|+|ABC|
  7. Binomial Coefficients Ch 1.2
    • Power set: |P(A)|=2|A|
    • 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
      • Bn is the set of all n-bit strings
      • Bkn is the set of all n-bit strings of weight k
      • Obviously: |Bkn|=|Bk1n1|+|Bkn1|
    • 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 n0 and integer k with 0kn there is a number (nk), reads n choose k
        • (nk)=|Bkn|
        • (nk) is the number of subsets of a set of size n each with cardinality k
        • (nk) is the number of lattice paths of length n containing k steps to the right
        • (nk) is the coefficient of xkynk in the expansion of (x+y)k
        • (nk) is the numebr of ways to select k objects from a total of n objects
      • Pascal's Triangle
  8. Combinations and Permutations Ch 1.3
    • Permutation is a possible rearrangement of objects
    • There are n!=n(n1)(n2)21 permutations of n(distinct) elements
    • k-permutation of n elements: P(n,k), the number of ways to arrange k objects chosen from n distinct objects: P(n,k)=n!(nk)!=n(n1)(n(k1))
    • Closed formula for (nk): (nk)=n!(nk)!k!=n(n(k1))k1
  9. Combinatorial Proofs Ch 1.4
    • Binomial identity
      • (n0)=(nn)=1
      • (nk)=(n1k1)+(n1k)
      • (nk)=(nnk)
      • (n0)++(nn)=2n
    • 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
  10. Sequences
    • Describing Sequences Ch 2.1
      • A sequence is simply an ordered list of numbers
      • Notation: a0,a1,, or (an)nN or (an)n0 or simply (an). If we omit a0, then the sequence is (an)n1. n is called index
      • Closed formula: a closed formula for (an)nN is a formula for an using a fixed finite number of operations on n
      • Recursive definition: a recursive definition(sometimes called an inductive definition) for a sequence (an)nN 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: an=n2
        • Triangle numbers: an=n(n+1)2
        • The fibonacci numbers: Fn=Fn1+Fn2 with F1=F2=1
    • 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 a0 of the sequence is a and the common difference is d, then we have recursive definition: an=an1+d with a0=a, closed formula: an=a+dn
      • A sequence is called geometric if the ratio between successive terms is constant. Suppose the initial term a0 is an the common ratio is r, then we have recursive definition: an=ran1 with a0=a, closed formula: an=arn
      • Summing arithmetic sequences: reverse and add
        • Formula: k=0n1(a+kd)=n2(2a+(n1)d)
      • Summing geometric sequences: multiply, shift and subtract
        • Formula: k=0n1(ark)=a1rn1r
    • Polynomial Fitting Ch 2.3
      • Difference
        • For sequence (an)n0, its first difference is (anan1)n1, its second difference is ((anan1)(an1an2))n2
        • If the kth order difference of a sequence is constant, then we say a sequence is a Δk-constant sequence
          • If a sequence is arithmetic, then it is Δ1-constant
      • Finite difference
        • The closed formula for a sequence will be a degree k polynomial if and only if the sequence is Δk-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 an+αan1+βan2=0, its characteristic equation is x2+αx+β=0
        • If γ1 and γ2 are two distinct roots of the characteristic eqution, then the solution to the recurrence relation is an=aγ1n+bγ2n, 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 an=aγn+bnγn, where a and b are constants determined by the initial conditions
    • Induction Ch 2.5
      • Induction Proof Structure: Let P(n) be the statement, to prove P(n) is true for all n0, you must prove two facts:
        • Base case: Prove that P(0) is true, you do this directly, this is often easy
        • Inductive case: Prove that P(k)P(k+1) for all k0. This is the proof of an if-then statement, so you can assume P(k)(it's called the inductive hypothesis) is true, you must then explain why P(k+1) is also true, given that assumption
        • Then by the principle of mathematical induction, the statement P(n) is true for all n0
      • Strong induction proof structure: Let P(n) be the statement, to prove P(n) is true for all n0, you must prove two facts:
        • Base case: Prove that P(0) is true
        • Inductive case: Assume P(k) is true, for all K<n, prove that P(k) is true
      • Some results
        • 1++n=n(n+1)2
        • 12++n2=n(n+1)(2n+1)6
        • 13++n3=(n(n+2)2)2
        • Consider the Riemann zeta function: ζ(s)=n=11ns
          • We have ζ(s)Γ(s)=0xs1ex1dx
          • ζ(1)=112,ζ(0)=12,ζ(1)=,ζ(2)=π26,ζ(4)=π490
  11. Graph Definition Ch 4.1
    • Definition: a graph is an ordered pair G=(V,E) 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 G1 and G2 is a bijection f:V1V2 between the vertices of the graphs such that {a,b} is an edge in G1 iff {f(a),f(b)} is an edge in G2. Two graphs are isomorphic if there is an isomorphism between them. In this case we write G1G2
    • Subgraphs: G=(V,E) is a subgraph of G=(V,E), and write GG, provided VV and EE. G=(V,E) is a induced subgraph of G=(V,E), provided VV and every edge in E whose vertices are in V is also an edge in E
    • 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. vVd(v)=2e
      • Proposition: in any graph, the number of vertices with odd degree must be even

Mathematics for Computer Science Notes

  1. Logical Formulas Ch 3.1
    • Java uses && for and , || for or
    • P xor Q notation: PQ
    • Negation of P: P¯, or ¬P
    • 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: A(BC)=(AB)(AC)
    • Distributive Law of OR over AND: A(BC)=(AB)(AC)
    • Proving Equivalences:
      • Approach 1: use truth table, there are 2N situations for N variables
      • Approach 2: use algebra to prove equivalence
    • SAT problem: the genereal problem of deciding whether a proposition is satisfiable is called SAT
  2. Inference Rules Ch 3.4
    • (AB)C(AC)(BC)
    • (AB)C(AC)(BC)
    • (AB)(BA)
    • (AB)CA(BC)
    • TrueAA
    • FalseAFalse
    • AAA
    • A¬AFalse
    • A(¬A)True
    • ¬(AB)¬A¬B
    • ¬(AB)¬A¬B
  3. Predicate Formulas Ch 3.6
    • General syntax: condition x1, condition x2,,condition xNP(x1,x2,,xN)
    • Quantifiers
      • ALways true
        • For all xD,P(x) is true
        • P(x) is true for every xD
      • Sometimes true
        • There is an xD s.t. P(x) is true
        • P(x) is true for some xD
        • P(x) is true for at least one xD
      • 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: x,y,Q(x,y)
      • The unnamed nonempty set that x and y range over is called the domain of discourse, or just domain
    • Negating quantifiers
      • Equivalence: ¬(x.P(x))x(¬P(x))
      • Equivalence: ¬(x.P(x))x(¬P(x))
    • Validity for Predicate Formulas
      • In order for a predicate formula to be valid, it should be true all across its domain
      • Valid assertion: x,y.P(x,y)y,x.P(x,y)
      • Not valid assertion: y,x.P(x,y)x,y.P(x,y) (This is invalid because x and y may be related, so there is no such universal x)
  4. 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
  5. Sets Ch 4.1
    • Introduction: informally, a set is a bunch of elements
    • Some popular sets: ,N,Z,Q,R,C
    • Comparing and combining sets
      • : subset, : strict subset
      • xABxA or xB
      • xABxA and xB
      • xABxA and xB
      • BP(A)BA
    • Proving set equalities: to prove A=B, we need to prove AB and BA
  6. Sequences Ch 4.2
    • A list of ordered eleemnts are called sequence
    • Use λ for empty sequence
  7. 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: f(S)={f(x):xS}
    • range of f: range(f)=f(domain of f)
    • Function Composition: for f:AB and g:BC, the composition of g and f is (gf):AC|(gf)(x)=g(f(x))
  8. 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: R(A)
    • Inverse relation: R1, bR1aaRb
    • Inverse image: R1(B)
  9. Finite Cardinality Ch 4.5
    • If A is a finite set, the cardinality of A, written |A|, is the number of elements in A
    • Definition
      • A surj B there is a surjective function from A to B
      • A inj B there is a injective function from A to B
      • A bij B there is a bijective function from A to B
    • Theorem: For finite sets A, B
      • A surj B|A||B|
      • A inj B|A||B|
      • A bij B|A|=|B|
    • For a finite with n elements, there are 2n subsets
  10. 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 P1,P2,,Pn are finite sets, then |P1P2Pn|=|P1||P2||Pn|
      • Sum rule: if P1,P2,,Pn are disjoint finite sets, then |P1P2Pn|=|P1|+|P2|++|Pn|
    • Generalized Product Rule Ch 14.3
      • Generalized Product Rule: Let S be a set of length-k sequences. If there are n1 possible for first entries, n2 possible second entries for each first entry, ..., nk possible kth entries for each sequence of first k - 1 entries, then: |S|=n1n2nk
      • Permutations
        • A permutation of a set S is a sequence that contains every element of S excatly once
        • There are a total of n! permutations of an n-element set
        • Stirling's formula: n!2πn(ne)n
        • From the above formula, we have log(n!)nlog(n)
    • 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 f:AB is k-to-1, then |A|=k|B|
      • Round Table Problem: arrange n knights at a round table, there is a n-to-1 function, so there are (n1)! arrangements
    • Counting subsets Ch 14.5
      • n choose k: (nk), 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 (nk)=n!k!(nk)!
      • Bit Sequences: the number of n-bit sequences with exactly k ones is (nk)
    • Sequences with repetitions Ch 14.6
      • Split subsets: let A be an n-element set and k1,k2,,km be nonnegative integers whose sum is n. A (k1,k2,,km)-split of A is an sequence (A1,A2,,Am) where Ai are disjoint subsets of A and |Ai|=ki for i=1,,m
      • Multinomial coefficient: for n,k1,k2,,kmN, s.t. k1+k2++km=n, define the multinomial coefficient (nk1,k1,,km)=n!k1!k2!km!
      • Subset split rule: the number of (k1,k2,,km)-split of an n-element set is (nk1,k1,,km)
      • Bookkeeper rule: let l1,,lm be distince elements. The amount of sequences s with k1 occurrences of l1, , and km occurrences of lm is (k1++kmk1,,km)
      • The binomial theorem: (a+b)n=k=0n(nk)akbnk
      • Multinomial theorem: for all nN,(z1++zm)n=k1,,kmNk1++km=n(nk1,,km)z1k1zmkm
    • 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: Prob=(131)(44)(121)(41)(525)
      • Hands with a full house: draw 5 cards, with 3 of one rank and 2 of another rank
        • Answer: Prob=(131)(43)(121)(42)(525)
      • 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: Prob=(132)(42)(42)(111)(41)(525)
      • Hands with every suit: at least one card from every suit
        • Answer: Prob=(131)(131)(131)(131)(41)(121)(525)
    • 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 |A|>|B|, then for every total function f:AB, there are two different elements in A mapped to the same element in B
        • Generalized pigeohole Principle: if |A|>k|B|, then every total function f:AB maps at least k + 1 different elements of A to the same element of B
    • Inclusion-Exclusion Ch 14.9
      • Union of two sets |AB|=|A|+|B||AB|
      • Union of three sets |ABC|=|A|+|B|+|C||AB||AC||BC|+|ABC|
      • Inclusion-Exclusion: |i=1nSi|=i=1n|Si|1ijn|SiSj|+1ijkn|SiSjSk|++(1)n|i=1nSi|
      • Inclusion-Exclusion-II: |i=1nSI|=I{1,,n}(1)|I|+1|iSi|
    • Combinatorial Proof Ch 14.10
      • Pascal's triangle identity: (nk)=(n1k1)+(n1k)
      • Giving a combinatorial proof
        • Define a set S
        • Show that |S|=n by counting one way
        • Show that |S|=m by counting another way
        • Conclude that n=m
      • Equality r=0n(nr)(2nnr)=(3nn)
  11. 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 nN, P(0), P(1),..., P(n) together imply P(n + 1), then P(m) is true for all
  12. 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 prob=d(d1)(d(n1))dn<en(n1)2d
      • The birthday principle: if there are d days in a year, and 2d people in a room, then the probability that two share a birthday is about 11e0.632
    • Set theory and probability
      • Probability space
        • A countable sample space S is a nonempty countable set. an element ωS is called an outcome, a ubset of S is called an event
        • A probability function on a sample space S is a total function Pr:SR s.t.
          • Pr(ω)0, for all ωS
          • ωSPr(ω)=1
        • A sample space together with a probability function is called a probability space. For any event ES, the probability of E is defined to be the sum of the probabilities of the outcome in E: Pr(E)::=ωEPr(ω)
        • Uniform probability spaces
          • A finite probability space, S, is said to be uniform if Pr(ω) is the same for every outcome ωS
          • For any event ES, Pr(E)=|E||S|
          • Probability space can be infinite
  13. Conditional Probability
    • Definition and notation Ch 17.2
      • The expression Pr(X|Y) denotes the probability of event X, given that event Y happens
      • Let X and Y be events where Y has nonzero probability. Then Pr(X|Y)=Pr(XY)Pr(Y)
    • Why tree diagrams work Ch 17.4
      • Conditional probability product rule: Pr(E1E2)=Pr(E1)Pr(E2|E1)
      • Conditional probability product rule: Pr(E1E2E3)=Pr(E1)Pr(E2|E1)Pr(E3|E1E2)
      • Bayes's rule: Pr(B|A)=Pr(A|B)Pr(B)Pr(A)
    • The law of total probability Ch 17.5
      • Law to total probability on single event: Pr(A)=Pr(A|E)Pr(E)+Pr(A|E¯)Pr(E¯)
      • Law of total probability on 3 events, if E1,E2, and E3 are disjoint and Pr(E1E2E3)=1, then Pr(A)=Pr(A|E1)Pr(E1)+Pr(A|E2)Pr(E2)+Pr(A|E3)Pr(E3)
      • Bayes's rule on 3 events: Pr(E1|A)=Pr(A|E1)Pr(E1)Pr(A|E1)Pr(E1)+Pr(A|E2)Pr(E2)+Pr(A|E3)Pr(E3)
    • Independence Ch 17.7
      • Definition: an event with probability 0 is defined to be independent of every event(including itself). If Pr(B)0, then event A is independent of event B Pr(A|B)=Pr(A)
      • A is independent of B Pr(AB)=Pr(A)Pr(B)
      • A set A1,A2, 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
  14. 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 R:AB
    • The standard properties of a relation can be visualized in terms of a diagram: write ab if aA and bB and a is associated with b in R
    • 1 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 1 arrow out property
      • surjective when it has the 1 arrow in property
      • total when it has the 1 arrow out property
      • injective when it has the 1 arrow in property
      • bijective when it has both the =1 arrow out and the =1 arrow in property
    • Relational images
      • Definition: the image of a set Y, under a relation R, written R(Y), 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, R(Y) is the set of points with an arrow coming in that starts from some point in Y
    • Inverse relations
      • Definition: the inverse R1, or a relation R:AB, is the relation from B to A defined by the rule bR1aaRb
    • Inverse images
      • Definition: the image of a set under the relation, R1, 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 R1(X)

Inference

  1. 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 ψ
        • (xϕ)ψx(ϕψ)
        • (xϕ)ψx(ϕψ)
        • (xϕ)ψx(ϕψ)
        • (xϕ)ψx(ϕψ)
      • Two examples
        • ((x2=1)(0=y))x(x2=10=y)
        • ((x2=1)(0=x)) does not mean x(x2=10=y)
      • Negation
        • ¬xϕx¬ϕ
        • ¬xϕx¬ϕ
      • Implication: when the variable quantified in one sub-formula does not appear free in the other sub-formula
        • (xϕ)ψx(ϕψ)
        • (xϕ)ψx(ϕψ)
        • ϕ(xψ)x(ϕψ)
        • ϕ(xψ)x(ϕψ)
  2. A formula of first-order logic is in Skolem normal form if it is in prenex normal form with only universal first-order quantifiers
  3. 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
      • x,y,f(x,y)y,f(a,y)
      • x,y,f(x,y)x,f(x,g(x))
    • 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
  4. 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 FCons(F)