CPT107-Discrete Mathematics and Statistics 课程笔记

2024-01-27 15:48

本文主要是介绍CPT107-Discrete Mathematics and Statistics 课程笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. The most basic datatypes
    • 1.1 The Natural Numbers
    • 1.2 The Integers
    • 1.3 The Rational Numbers
    • 1.4 The Real Numbers
  • 2. Proof Techniques
    • 2.1 Finding a counter-example
    • 2.2 Proof by contradiction
    • 2.3 Proof by induction
  • 3. Set Theory
    • 3.1 Notation
    • 3.2 The algebra of sets
    • 3.3 Cardinality of sets
    • 3.4 Ordered pairs
  • 4. Relations
    • 4.1 Unary Relation
    • 4.2 Binary Relation
      • 4.2.1 Directed Graphs (有向图)
      • 4.2.2 Matrices (邻接矩阵)
      • 4.2.3 Transitive Closure (传递闭包)
      • 4.2.4 Equivalence Relations
      • 4.2.5 Partition of a set
      • 4.2.6 Partial orders
      • 4.2.7 Hasse Diagram
      • 4.2.8 Total orders
  • 5. Overview of functions and PHP
  • 6. Propositional Logic
    • 6.1 Formulas
    • 6.2 Truth Values
    • 6.3 Tautology
    • 6.4 Contradiction
    • 6.5 Semantic consequence
    • 6.5 Logical equivalence
  • 7. Predicate Logic
    • 7.1 The Language of Predicate Logic
    • 7.2 Syntax of predicate logic
  • 8. Combinatorics
    • 8.1 Discrete Probability
    • 8.2 Conditional Probability
    • 8.3 Independence
    • 8.4 A random variable
    • 8.5 Expectation




1. The most basic datatypes

1.1 The Natural Numbers

N = { 0 , 1 , 2 , 3 , … } \Bbb{N}=\{0, 1, 2, 3,\dots\} N={0,1,2,3,}
We say that N \Bbb{N} N is closed under addition because if you take any two numbers in N \Bbb{N} N and add them, you always get another number in N \Bbb{N} N.

Key property : Any natural number can be obtained from 0 0 0 by applying the operation S ( n ) = n + 1 S(n)=n+1 S(n)=n+1 some number times.

Examples : S ( 0 ) = 1 , S ( S ( 0 ) ) = 2 , S ( S ( S ( 0 ) ) ) = 3 S(0)=1,\ \ S(S(0))=2,\ \ S(S(S(0)))=3 S(0)=1,  S(S(0))=2,  S(S(S(0)))=3


1.2 The Integers

Z = { 0 , 1 , 2 , 3 , … } \Bbb{Z}=\{0, 1, 2, 3,\dots\} Z={0,1,2,3,}
And the positive integers:
Z + = { 0 , 1 , 2 , 3 , … } \Bbb{Z}^+=\{0, 1, 2, 3,\dots\} Z+={0,1,2,3,}

1.3 The Rational Numbers

Q \Bbb{Q} Q is the set of all numbers that can be written as x y \frac{x}{y} yx where x x x and y y y are integers and y y y is not 0 0 0.


1.4 The Real Numbers

R \Bbb{R} R is the set of all numbers ---- distances to points on a number line.
A real number that is not rational is called irrational.



2. Proof Techniques

2.1 Finding a counter-example

e.g.
statement : Let f ( n ) = n 2 + n + 41 f(n)=n^2+n+41 f(n)=n2+n+41. For every natural number n n n, f ( n ) f(n) f(n) is prime.
counter-example : f ( 40 ) f(40) f(40)


2.2 Proof by contradiction

e.g.
statement : 2 \sqrt{2} 2 is not a rational number
Proof by contradiction :

  1. If 2 \sqrt2 2 were rational then we could write it as 2 = x y \sqrt2=\frac xy 2 =yx where x x x and y y y are integers and y y y is not 0 0 0
  2. By repeatedly cancelling common factors, we can make sure that x x x and y y y have no common factors so they are not both even
  3. Then 2 = x 2 y 2 2=\frac{x^2}{y^2} 2=y2x2 so x 2 = 2 y 2 x^2=2y^2 x2=2y2 so x 2 x^2 x2 is even. This means x x x is even, because the square of any odd number is odd
  4. Let x = 2 w x=2w x=2w for some integer w w w
  5. Then x 2 = 4 w 2 x^2=4w^2 x2=4w2 so 2 w 2 = y 2 2w^2=y^2 2w2=y2, so y 2 y^2 y2 is even so y y y is even
  6. This contradicts the fact that x x x and y y y are not both even, so our original assumption must have been wrong

2.3 Proof by induction

e.g.
statement : For every integer n ≥ 3 n\ge3 n3, n 2 ≥ 3 n n^2\ge3n n23n
Proof by Induction :

  1. Base Case : Take n = 3 n=3 n=3. Then 3 2 ≥ 3 × 3 3^2\ge3\times3 323×3
  2. Inductive Step : Assume that the statement is true for n = m n=m n=m for m ≥ 3 m\ge3 m3 so m 2 ≥ 3 m m^2\ge3m m23m. Now consider n = m + 1 n=m+1 n=m+1. We must show that ( m + 1 ) 2 ≥ 3 ( m + 1 ) (m+1)^2\ge3(m+1) (m+1)23(m+1).
  3. ( m + 1 ) 2 = m 2 + 2 m + 1 ≥ 3 m + 2 m + 1 (m+1)^2=m^2+2m+1\ge3m+2m+1 (m+1)2=m2+2m+13m+2m+1 and since m ≥ 1 m\ge1 m1, 3 m + 2 m + 1 ≥ 3 ( m + 1 ) 3m+2m+1\ge3(m+1) 3m+2m+13(m+1)


3. Set Theory

3.1 Notation

The union of two sets:

A ∪ B = { x ∣ x ∈ A or  x ∈ B } A\cup B=\{x|x\in A~\text{or}~x\in B\} AB={xxA or xB}
在这里插入图片描述
The intersection of two sets

A ∩ B = { x ∣ x ∈ A and  x ∈ B } A \cap B=\{x|x\in A~\text{and}~x\in B\} AB={xxA and xB}
在这里插入图片描述
The relative complement

A − B = { x ∣ x ∈ A and  x ∉ B } A-B=\{x|x\in A~\text{and}~x\notin B\} AB={xxA and x/B}
在这里插入图片描述
The complement

∼ A = { x ∣ x ∉ A } = U − A \sim A=\{x|x\notin A\}=U-A A={xx/A}=UA
在这里插入图片描述
The symmetric difference

A Δ B = { x ∣ ( x ∈ A and  x ∉ B ) or  ( x ∉ A and  x ∈ B ) } A\Delta B=\{x|(x\in A~\text{and}~x\notin B)~\text{or}~(x\notin A~\text{and}~x\in B)\} AΔB={x(xA and x/B) or (x/A and xB)}
在这里插入图片描述

3.2 The algebra of sets

A ∪ B = B ∪ A A\cup B=B\cup A AB=BA
A ∩ B = B ∩ A A\cap B=B\cap A AB=BA
A ∪ ( B ∪ C ) = ( A ∪ B ) ∪ C A\cup(B\cup C)=(A\cup B)\cup C A(BC)=(AB)C
A ∩ ( B ∩ C ) = ( A ∩ B ) ∩ C A\cap(B\cap C)=(A\cap B)\cap C A(BC)=(AB)C
A ∪ ∅ = A A\cup\empty=A A=A
A ∩ ∅ = ∅ A\cap\empty=\empty A=
A ∪ U = U A\cup U=U AU=U
A ∩ U = A A\cap U=A AU=A
A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C ) A\cap(B\cup C)=(A\cap B)\cup(A\cap C) A(BC)=(AB)(AC)
A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C ) A\cup(B\cap C)=(A\cup B)\cap(A\cup C) A(BC)=(AB)(AC)
A ∪ ∼ A = U A\cup\sim A=U AA=U
A ∩ ∼ A = ∅ A\cap\sim A=\empty AA=
∼ U = ∅ \sim U=\empty U=
∼ ∅ = U \sim\empty=U =U
∼ ( ∼ A ) = A \sim(\sim A)=A (A)=A
∼ ( A ∪ B ) = ∼ A ∩ ∼ B \sim(A\cup B)=\sim A\cap\sim B (AB)=AB
∼ ( A ∩ B ) = ∼ A ∪ ∼ B \sim(A\cap B)=\sim A\cup\sim B (AB)=AB

The following statements hold

  • ∅ ∈ { ∅ } \empty\in\{\empty\} {} but ∅ ∉ ∅ \empty\notin\empty /
  • ∅ ⊆ { 5 } \empty\subseteq\{5\} {5}
  • { 2 } ⊈ { { 2 } } \{2\}\nsubseteq\{\{2\}\} {2}{{2}} but { 2 } ∈ { { 2 } } \{2\}\in\{\{2\}\} {2}{{2}}
  • { 3 , { 3 } } ≠ { 3 } \{3,~\{3\}\}\ne\{3\} {3, {3}}={3}

The Power Set

The power set P o w ( A ) Pow(A) Pow(A) of a set A A A is the set of all subsets of A
P o w ( A ) = { C ∣ C ⊆ A } Pow(A)=\{C|C\subseteq A\} Pow(A)={CCA}

P o w ( A ∩ B ) = P o w ( A ) ∩ P o w ( B ) Pow(A\cap B)=Pow(A)\cap Pow(B) Pow(AB)=Pow(A)Pow(B)
P o w ( A ∪ B ) ≠ P o w ( A ) ∪ P o w ( B ) Pow(A\cup B)\ne Pow(A)\cup Pow(B) Pow(AB)=Pow(A)Pow(B)


3.3 Cardinality of sets

The cardinality of a finite set S is the number of elements in S, and is denoted by |S|

∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ |A\cup B|=|A|+|B|-|A\cap B| AB=A+BAB


3.4 Ordered pairs

In discussing sets, the order in which elements are listed is unimportant. In order to handle ordered lists of objects we first introduce :
The cartesian product A × B A\times B A×B of sets A A A and B B B is the set consisting of all pairs ( a , b ) (a, b) (a,b) with a ∈ A a\in A aA and b ∈ B b\in B bB
A × B = { ( a , b ) ∣ a ∈ A and  b ∈ B } A\times B=\{(a,b)|a\in A~\text{and}~b\in B\} A×B={(a,b)aA and bB}
The cartesian product A 1 × A 2 × ⋯ × A n A_1\times A_2\times\cdots\times A_n A1×A2××An is :
A 1 × A 2 × ⋯ × A n = { ( a 1 , … , a n ) ∣ a 1 ∈ A 1 , … , a n ∈ A n } A_1\times A_2\times\cdots\times A_n=\{(a_1,\dots,a_n)|a_1\in A_1,\dots,a_n\in A_n\} A1×A2××An={(a1,,an)a1A1,,anAn}

( a , b ) = ( c , d ) (a,b)=(c,d) (a,b)=(c,d) iff a = c and  b = d a=c~\text{and}~b=d a=c and b=d
{ 1 , 2 } = { 2 , 1 } \{1,2\}=\{2,1\} {1,2}={2,1} but ( 1 , 2 ) ≠ ( 2 , 1 ) (1,2)\ne(2,1) (1,2)=(2,1)

e,g,
Let A = { 1 , 2 } A=\{1,2\} A={1,2} and B = { a , b , c } B=\{a,b,c\} B={a,b,c}. Then
A × B = { ( 1 , a ) , ( 2 , a ) , ( 1 , b ) , ( 2 , b ) , ( 1 , c ) , ( 2 , c ) } A\times B=\{(1,a),~(2,a),~(1,b),~(2,b),~(1,c),~(2,c)\} A×B={(1,a), (2,a), (1,b), (2,b), (1,c), (2,c)}


Cartesian plane
The set R × R \Bbb R\times\Bbb R R×R, or R 2 \Bbb{R^2} R2 consists of all pairs of real numbers ( x , y ) (x,y) (x,y), R 2 \Bbb{R^2} R2 is called the Cartesian plane
在这里插入图片描述
Bit strings of length n

Let B = { 0 , 1 } B=\{0,1\} B={0,1}, B n B^n Bn consists of all lists of zeros and ones of length n n n. These are called bit strings of length n.

Bit strings can be used to represent the subsets of a set.
Suppose we have a set S = { s 1 , … , s n } S=\{s_1,\dots,s_n\} S={s1,,sn}, if we have a subset A ⊆ S A\subseteq S AS, the characteristic vector of A A A is the n-bit string ( b 1 , … , b n ) ∈ B n (b_1,\dots,b_n)\in B^n (b1,,bn)Bn where b i = { 1 if  s i ∈ A 0 if  s i ∉ A b_i=\begin{cases}1&\text{if}~s_i\in A\\0&\text{if}~s_i\notin A\end{cases} bi={10if siAif si/A



4. Relations

4.1 Unary Relation

Unary relation is a relation in one set (actually it is just a subset of a set)

A binary relation is that it is a relation between two sets.

And there is ternary relations (relations between three sets)


4.2 Binary Relation

Binary relation : A binary relation between two sets A A A and B B B is a subset R R R of the Cartesian product A × B A\times B A×B. If A = B A=B A=B, then R R R is called a binary relation on A A A

Properties

A binary relation R R R on a set A A A is

  • Reflexive when x R x xRx xRx for all x ∈ A x\in A xA (有向图 A A A 内的所有节点都有自环)
  • Symmetric when x R y xRy xRy implies y R x yRx yRx for all x , y ∈ A x,y\in A x,yA ( A A A 是无向图)
  • Antisymmetric : when x R y xRy xRy and y R x yRx yRx imply x = y x=y x=y for all x , y ∈ A x,y\in A x,yA (有向图 A A A 内不存在双向边)
  • Transitive when x R y xRy xRy and y R z yRz yRz imply x R z xRz xRz for all x , y , z ∈ A x,y,z\in A x,y,zA (传递性)

4.2.1 Directed Graphs (有向图)

Directed graph is a representation of binary relations. Assume that R R R is a binary relation between A A A and B B B. We represent the elements of these two sets as vertices of a graph, for each ( a , b ) ∈ R (a,b)\in R (a,b)R, we draw an arrow linking the related elements. This is called the directed graph (or digraph) of R R R.

4.2.2 Matrices (邻接矩阵)

A way of representing a binary relation between finite sets uses an matrix. M ( i , j ) = { T if  ( a i , b j ) ∈ R F if  ( a i , b j ) ∉ R M(i,j)=\begin{cases}T&\text{if }(a_i,b_j)\in R\\F&\text{if }(a_i,b_j)\notin R\end{cases} M(i,j)={TFif (ai,bj)Rif (ai,bj)/R

4.2.3 Transitive Closure (传递闭包)

Given a binary relation R R R on a set A A A, the transitive closure R ∗ R^∗ R of R R R is the (uniquely determined) relation on A A A with the following properties:

  • R ∗ R^* R is transitive
  • R ⊆ R ∗ R\subseteq R^* RR
  • If S S S is a transitive relation on A A A and R ⊆ S R\subseteq S RS, then R ∗ ⊆ S R^*\subseteq S RS

传递闭包的意义

邻接矩阵是显示两点的直接关系,如 a a a 直接能到 b b b,就为1。而传递闭包显示的是传递关系,如 a a a 不能直接到 c c c,却可以通过 a a a b b b d d d 再到 c c c,因此 a a a c c c 为1。


代码实现计算传递闭包

E E E 为原邻接矩阵,只需要对 Floyed 算法进行一点点改动:

for (int k = 1; k <= n; ++k)for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)if (E[i][k] && E[k][j])E[i][j] = 1;

4.2.4 Equivalence Relations

A binary relation R R R on a set A A A is called an equivalence relation if it is reflexive, transitive, and symmetric.
The equivalence class E x E_x Ex of any x ∈ A x\in A xA is defined by E x = { y ∣ y R x } E_x=\{y~|~yRx\} Ex={y  yRx}

仅满足自反、对称的二元关系,称为相容关系

4.2.5 Partition of a set

A partition of a set A A A is a collection of non-empty subsets A 1 , ⋯ , A n A_1,\cdots,~A_n A1,, An of A satisfying

  • A = A 1 ∪ A 2 ∪ ⋯ ∪ A n A=A_1\cup A_2\cup\cdots\cup A_n A=A1A2An
  • A i ∩ A j = ∅ A_i\cap A_j=\empty AiAj= for i ≠ j i\ne j i=j
    在这里插入图片描述
    A i A_i Ai are called the blocks of the partition

Theorems

  • Let R R R be an equivalence relation on a non-empty set A A A. Then the equivalence classes { E x ∣ x ∈ A } \{E_x~|~x\in A\} {Ex  xA} form a partition of A.
  • Suppose that A 1 , ⋯ , A n A_1,\cdots,A_n A1,,An is a partition of A A A. Define a relation R R R on A A A by setting: x R y xRy xRy if and only if there exists i i i such that 1 ≤ i ≤ n 1\le i\le n 1in and x , y ∈ A i x,y\in A_i x,yAi. Then R R R is an equivalence relation.

4.2.6 Partial orders

A binary relation R R R on a set A A A which is reflexive, transitive and antisymmetric is called a partial order

Partial orders are important in situations where we wish to characterise precedence.

Predecessor: If R R R is a partial order on a set A A A and x R y xRy xRy, x ≠ y x\ne y x=y, we call x x x is a predecessor of y y y.
If x x x is a predecessor of y y y and there is no z ∉ { x , y } z\notin\{x,y\} z/{x,y} for which x R z xRz xRz and z R y zRy zRy, we call x x x an immediate predecessor of y y y

4.2.7 Hasse Diagram

The Hasse Diagram of a partial order is a digraph. The vertices of the digraph are the elements of the partial order, and the edges of the digraph are given by the “immediate predecessor” relation

4.2.8 Total orders

A binary relation R R R on a set A A A is a total order if it is a partial order such that any x , y ∈ A , x R y x,y\in A,~xRy x,yA, xRy or y R x yRx yRx

全序关系的哈斯图是一条链。



5. Overview of functions and PHP

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
**Inverse Sets**
For a subset y y y of B B B, the inverse of y : = f − 1 ( y ) = { x in  A ∣ f ( x ) in  y } y:=f^{-1}(y)=\{x~\text{in}~A|f(x)~\text{in}~y\} y:=f1(y)={x in Af(x) in y}

There is an inverse function for f f f if and only if f f f is a bijection

在这里插入图片描述
Pigeonhole Principle

A function from a larger set to a smaller set cannot be injective.



6. Propositional Logic

Propositional logic is concerned with

  • The truth and falsity of simple (declarative) statements.
  • The question: when does a statement follow from a set of statements?
  • Algorithms which decide whether a statement follows from a set of statements.

6.1 Formulas

A formula is defined “syntactically”, you build a formula following rules. This has nothing to do with what the formula means (which is called “semantics”). “Parsing” the formula means determining how the formula is built, following the rules.

atomic formulas
The simplest formulas are “propositional variables” which we write using letters such as p p p, q q q or r r r or using indexed letters such as p 0 , p 1 , p 2 , … p_0,~p_1,~p_2,~\dots p0, p1, p2, 
Propositional variables are called atomic formulas.

The alphabet of propositional logic consists of

  • An infinite set p , q , r , p 0 , p 1 , … p,~q,~r,~p_0,~p_1,~\dots p, q, r, p0, p1,  of atomic formulas.
  • The logical connectives ¬ ( n o t ) , ∧ ( a n d ) , ∨ ( o r ) \lnot(not),~\land(and),~\lor(or) ¬(not), (and), (or)
  • Brackets

The set P P P of all formulas of propositional logic is defined inductively:

  • All atomic formulas are formulas
  • If P P P is a formula, then ¬ P \lnot P ¬P is a formula
  • If P P P and Q Q Q are formulas, then ( P ∧ Q ) (P\land Q) (PQ) is a formula
  • If P P P and Q Q Q are formulas, then ( P ∨ Q ) (P\lor Q) (PQ) is a formula
  • Nothing else is a formula

Parse Trees
A parse tree is a tree representation of how the formula is constructed

  • The parse tree of an atomic formula has one node, labelled with the formula.
  • The parse tree of a formula ¬ P \lnot P ¬P haa a root labelled ¬ \lnot ¬. The child of the root is the parse tree for the formula P P P.
  • The parse tree of a formula P ∧ Q P\land Q PQ has a root labelled ∧ \land . The left child of the root is the parse tree fo the formula P P P. The right child of the root is the parse tree for the formula Q Q Q.

Formulas are just strings over a certain alphabet without truth values or meaning.


6.2 Truth Values

An interpretation I I I is a function which assigns to any atomic formula p i p_i pi a truth value. I ( p i ) ∈ { 0 , 1 } I(p_i)\in\{0,1\} I(pi){0,1}

  • If I ( p i ) = 1 I(p_i)=1 I(pi)=1, then p i p_i pi is called true under the interpretation I I I.
  • If I ( p i ) = 0 I(p_i)=0 I(pi)=0, then p i p_i pi is called false under the interpretation I I I.

Given an assignment I we can compute the truth value of compound formulas step by step using so-called truth tables

Truth Tables

e.g. negation:

I ( ¬ P ) = { 0 if  I ( P ) = 1 1 if  I ( P ) = 0 I(\lnot P)=\begin{cases}0&\text{if}~I(P)=1\\1&\text{if}~I(P)=0\end{cases} I(¬P)={01if I(P)=1if I(P)=0

The corresponding truth table is:
在这里插入图片描述

6.3 Tautology

A tautology is a formula which is true under all interpretations.

⊤ : = ( p 1 ∨ ¬ p 1 ) \top:=(p_1\lor\lnot p_1) :=(p1¬p1)

6.4 Contradiction

A contradiction is a formula which is false under all interpretations.

⊥ : = ( p 1 ∧ ¬ p 1 ) \bot:=(p_1\land\lnot p_1) :=(p1¬p1)

6.5 Semantic consequence

Suppose Γ \Gamma Γ is a finite set of formulas and P P P is a formula. Then P P P follows from Γ \Gamma Γ (or is a semantic consequence of Γ \Gamma Γ) if the following implication holds for every interpretation I I I: if  I ( Q ) = 1 for all  Q ∈ Γ , then  I ( P ) = 1 \text{if}~I(Q)=1~\text{for all}~Q\in\Gamma,~\text{then}~I(P)=1 if I(Q)=1 for all QΓ, then I(P)=1This is denoted by Γ ⊨ P \Gamma\vDash P ΓP
P 不一定在集合 Γ \Gamma Γ

The following conditions are equivalent:

  • { P } ⊨ Q \{P\}\vDash Q {P}Q
  • ( P → Q ) (P\rightarrow Q) (PQ) is a tautology
  • ( P ∧ ¬ Q ) (P\land\lnot Q) (P¬Q) is a contradiction

6.5 Logical equivalence

Two formulas P P P and Q Q Q are called equivalent if they have the same truth value under every possible interpretation. In other words, P P P and Q Q Q are equivalent if I ( P ) = I ( Q ) I(P) = I(Q) I(P)=I(Q) for every interpretation I I I. This is denoted by P ≡ Q P\equiv Q PQ

Laws for equivalences

  • Associative laws: ( P ∨ ( Q ∨ R ) ) ≡ ( ( P ∨ Q ) ∨ R ) (P\lor(Q\lor R))\equiv((P\lor Q)\lor R) (P(QR))((PQ)R)
  • Commutative laws: ( P ∨ Q ) ≡ ( Q ∨ P ) (P\lor Q)\equiv(Q\lor P) (PQ)(QP)
  • Identity laws: ( P ∨ ⊤ ) ≡ P (P\lor\top)\equiv P (P)P
  • Distributive laws: ( P ∧ ( Q ∨ R ) ) ≡ ( ( P ∧ Q ) ∨ ( P ∧ R ) ) (P\land(Q\lor R))\equiv((P\land Q)\lor(P\land R)) (P(QR))((PQ)(PR))
  • Complement laws: P ∨ ¬ P ≡ ⊤ P\lor\lnot P\equiv\top P¬P
  • De Morgan’s laws: ¬ ( P ∨ Q ) ≡ ( ¬ P ∧ ¬ Q ) \lnot(P\lor Q)\equiv(\lnot P\land\lnot Q) ¬(PQ)(¬P¬Q)

The relation ≡ \equiv is an equivalence relation on P P P



7. Predicate Logic


Limitations of Propositional Logic

Propositional logic is good for dealing with statements built from basic propositions using and, or, not, if … But more complex statements cannot be expressed naturally in propositional logic.

So we need to extend propositional logic. Numerous extensions have been developed, among them:

  • Modal Logic: Adds elements to reason about necessity
  • Temporal Logic: Adds elements to reason about time.
  • Predicate Logic: Adds elements to reason about properties of objects

Quantifiers

  • ∀ \forall : for all, Universal quantification
  • ∃ \exists : there exists an, Existential quantification

e,g,
Every student is younger than some instructor.

this statement can be written symbolically using predicates, variables, and quantifiers:

∀ x ( S t u d e n t ( x ) → ∃ y ( Y o u n g e r ( x , y ) ∧ I n s t r u c t o r ( y ) ) ) \forall x(Student(x)\rightarrow\exists y(Younger(x,y)\land Instructor(y))) x(Student(x)y(Younger(x,y)Instructor(y)))

This is a typical formula in predicate logic

Predicate logic has two additional features:

  1. Equality: allows to express that individuals are equal or not
  2. function symbols: allows to express functional dependencies between individuals

Function symbols can often be “simulated” by predicates, so they are not really necessary. But function symbols lead to more natural descriptions


7.1 The Language of Predicate Logic

Predicate logic allows us to express statements about

  • objects
  • their properties and relations to each other

Some terminologies :

  • Domain : a non-empty set of objects
  • Constants : concrete objects in the domain
  • Functions : takes objects in the domain as arguments and returns an object of the domain
  • Predicates : takes objects in the domain as arguments and returns true or false. They describe properties of objects or relationships between objects
  • Variables : placeholders for concrete objects in the domain
  • Quantifiers : for how many objects in the domain is the statement true

7.2 Syntax of predicate logic

Signatures

A signature defines the “vocabulary” relative to which formulae can be expressed

A signature is a set consisting of :

  • predicate symbols, each with an associated arity
  • function symbols, each with an associated arity
  • constant symbols


8. Combinatorics

Special Case for sums and products

∑ i ∈ ∅ f ( i ) = 0 \sum\limits_{i\in\empty}f(i)=0 if(i)=0
∏ i ∈ ∅ f ( i ) = 1 \prod\limits_{i\in\empty}f(i)=1 if(i)=1

permutations

A n m = n ! ( n − k ) ! A^m_n=\frac{n!}{(n-k)!} Anm=(nk)!n!

subsets

C n m = n ! ( n − k ) ! k ! C^m_n=\frac{n!}{(n-k)!k!} Cnm=(nk)!k!n!

The quantity which gives the number of size-k subsets of a set of size n, is called a binomial coefficient
It is writen an ( k n ) (^n_k) (kn) and pronounced “n choose k”


8.1 Discrete Probability

The sample space Ω \Omega Ω is the set of all possible outcomes. Every element x x x of Ω \Omega Ω has a probability P r ( x ) ∈ [ 0 , 1 ] Pr(x)\in[0,1] Pr(x)[0,1] ∑ x ∈ Ω P r ( x ) = 1 \sum\limits_{x\in\Omega}Pr(x)=1 xΩPr(x)=1

Events

An event is a subset X ⊆ Ω X\subseteq\Omega XΩ. The probability of the event is given by P r ( X ) = ∑ x ∈ X P r ( x ) Pr(X)=\sum_{x\in X}Pr(x) Pr(X)=xXPr(x)

P r ( ∅ ) = 0 Pr(\empty)=0 Pr()=0
P r ( Ω ) = 1 Pr(\Omega)=1 Pr(Ω)=1

P r ( X ∪ Y ) = P r ( X ) + P r ( Y ) − P r ( X ∩ Y ) Pr(X\cup Y)=Pr(X)+Pr(Y)-Pr(X\cap Y) Pr(XY)=Pr(X)+Pr(Y)Pr(XY)


8.2 Conditional Probability

P r ( X ∣ Y ) = P r ( X ∩ Y ) P r ( Y ) Pr(X|Y)=\frac{Pr(X\cap Y)}{Pr(Y)} Pr(XY)=Pr(Y)Pr(XY)


8.3 Independence

Suppose that P r ( X ) ≠ 0 Pr(X)\ne0 Pr(X)=0 and P r ( Y ) ≠ 0 Pr(Y)\ne0 Pr(Y)=0. We say that events X X X and Y Y Y, are independent if P r ( X ∩ Y ) = P r ( X ) P r ( Y ) Pr(X\cap Y)=Pr(X)Pr(Y) Pr(XY)=Pr(X)Pr(Y)

that is, P r ( X ∣ Y ) = P r ( X ) Pr(X|Y)=Pr(X) Pr(XY)=Pr(X)


8.4 A random variable

A random variable is a function with domain Ω \Omega Ω


8.5 Expectation

The expected value of a random variable f is defined as follows E [ f ] = ∑ x ∈ Ω f ( x ) P r ( x ) E[f]=\sum_{x\in\Omega}f(x)Pr(x) E[f]=xΩf(x)Pr(x)

This is sometimes called the expectation of f f f or the mean of f f f. It is the value that you expect to get if you pick x x x randomly from Ω \Omega Ω and then compute f ( x ) f(x) f(x)

If you repeatedly pick x x x randomly from Ω \Omega Ω and compute f ( x ) f(x) f(x) and you compute the average of the f ( x ) f(x) f(x) values, this tends towards E [ f ] E[f] E[f].

Linearity of expectation

If f and g are two random variables, then E [ f + g ] = E [ f ] + E [ g ] E[f+g]=E[f]+E[g] E[f+g]=E[f]+E[g]

If g ( x ) = c f ( x ) g(x)=cf(x) g(x)=cf(x), then E [ g ] = c E [ f ] E[g]=cE[f] E[g]=cE[f]

But E [ f × g ] = E [ f ] × E [ g ] E[f\times g]=E[f]\times E[g] E[f×g]=E[f]×E[g] is not always true

这篇关于CPT107-Discrete Mathematics and Statistics 课程笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/650720

相关文章

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

查看提交历史 —— Git 学习笔记 11

查看提交历史 查看提交历史 不带任何选项的git log-p选项--stat 选项--pretty=oneline选项--pretty=format选项git log常用选项列表参考资料 在提交了若干更新,又或者克隆了某个项目之后,你也许想回顾下提交历史。 完成这个任务最简单而又有效的 工具是 git log 命令。 接下来的例子会用一个用于演示的 simplegit

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪(un-tracking)文件重新跟踪(re-tracking)文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法,现在我们已经有了一个仓库,并从这个仓

忽略某些文件 —— Git 学习笔记 05

忽略某些文件 忽略某些文件 通过.gitignore文件其他规则源如何选择规则源参考资料 对于某些文件,我们不希望把它们纳入 Git 的管理,也不希望它们总出现在未跟踪文件列表。通常它们都是些自动生成的文件,比如日志文件、编译过程中创建的临时文件等。 通过.gitignore文件 假设我们要忽略 lib.a 文件,那我们可以在 lib.a 所在目录下创建一个名为 .gi

取得 Git 仓库 —— Git 学习笔记 04

取得 Git 仓库 —— Git 学习笔记 04 我认为, Git 的学习分为两大块:一是工作区、索引、本地版本库之间的交互;二是本地版本库和远程版本库之间的交互。第一块是基础,第二块是难点。 下面,我们就围绕着第一部分内容来学习,先不考虑远程仓库,只考虑本地仓库。 怎样取得项目的 Git 仓库? 有两种取得 Git 项目仓库的方法。第一种是在本地创建一个新的仓库,第二种是把其他地方的某个

Git 的特点—— Git 学习笔记 02

文章目录 Git 简史Git 的特点直接记录快照,而非差异比较近乎所有操作都是本地执行保证完整性一般只添加数据 参考资料 Git 简史 众所周知,Linux 内核开源项目有着为数众多的参与者。这么多人在世界各地为 Linux 编写代码,那Linux 的代码是如何管理的呢?事实是在 2002 年以前,世界各地的开发者把源代码通过 diff 的方式发给 Linus,然后由 Linus