复旦大学：《离散数学 Discrete Mathematics》英文讲稿_11 Terms Formuals Formation tree

Discrete mathematics Yi li Software school Fudan University May22,2012

Discrete Mathematics Yi Li Software School Fudan University May 22, 2012 Yi Li (Fudan University) Discrete Mathematics May 22, 2012 1 / 1

Review o Limits of pl o Predicates and quantifiers

Review Limits of PL Predicates and quantifiers Yi Li (Fudan University) Discrete Mathematics May 22, 2012 2 / 1

utline Terms o Formuals o Formation tree

Outline Terms Formuals Formation tree Yi Li (Fudan University) Discrete Mathematics May 22, 2012 3 / 1

Predicates and Quantifiers predicates variables constants o functions universal quantifier: V, "for all o existential quantifier: 3, there exists

Predicates and Quantifiers predicates variables constants functions universal quantifier: ∀, ”for all”. existential quantifier: ∃, there exists Yi Li (Fudan University) Discrete Mathematics May 22, 2012 4 / 1

Formula Definition(Subformula) A subformula of a formula p is a consecutive sequence of symbols from y which is itself a formula Xample Given an formula ((x)(p(x)vo(x, y))->(z)o(z))) o Is((vxp(x)) a subformula? o Is o(x) a subformula? (x)(y(x)Vo(x,y),(z)u(z),y(x),o(x,y) and o(z) all are subformulas

Formula Definition (Subformula) A subformula of a formula ϕ is a consecutive sequence of symbols from ϕ which is itself a formula. Example Given an formula (((∀x)(ϕ(x) ∨ φ(x, y))) → ((∃z)σ(z))). 1 Is ((∀x)ϕ(x)) a subformula? 2 Is σ(x) a subformula? 3 ((∀x)(ϕ(x) ∨ φ(x, y))), ((∃z)σ(z)),ϕ(x), φ(x, y), and σ(z) all are subformulas. Yi Li (Fudan University) Discrete Mathematics May 22, 2012 5 / 1

Occurrence amp dle Consider the following examples o(x)y(x,y)∧(x)(x) (x)42(x,y)Av(x) Definition(Occurrence) An occurrence of a variable v in a formula p is bound if there is a subformula yb of yp containing that occurrence of v such that y/ begins with((v)or(v).An occurrence of v in p is free if it is not bound

Occurrence Example Consider the following examples: 1 (((∀x)ϕ(x, y)) ∧ ((∃x)ψ(x))) 2 (((∀x)ϕ(x, y)) ∧ ψ(x)) Definition (Occurrence) An occurrence of a variable v in a formula ϕ is bound if there is a subformula ψ of ϕ containing that occurrence of v such that ψ begins with ((∀v) or ((∃v). An occurrence of v in ϕ is free if it is not bound. Yi Li (Fudan University) Discrete Mathematics May 22, 2012 6 / 1

Free Occurrence amp dle Consider the following examples Q(三y)(×)(x,y)∧v(x) Definition A variable v is said to occur free in p if it has at least one free occurrence there

Free Occurrence Example Consider the following examples: 1 ((∃y)((∀x)ϕ(x, y)) ∧ ψ(x)) Definition A variable v is said to occur free in ϕ if it has at least one free occurrence there. Yi Li (Fudan University) Discrete Mathematics May 22, 2012 7 / 1

Sentence amp dle Consider the following examples Q(三y)(x)y(x,y)∧(vz)u(z)) O((VX(((yR(x,y))V(yT(x, y)) o (co, C1 Definition A sentence of predicate logic is a formula with no free occurrences of any variable

Sentence Example Consider the following examples: 1 ((∃y)((∀x)ϕ(x, y)) ∧ (∀z)ψ(z)) 2 ((∀x)(((∀y)R(x, y)) ∨ ((∃y)T(x, y))). 3 ϕ(c0, c1) Definition A sentence of predicate logic is a formula with no free occurrences of any variable. Yi Li (Fudan University) Discrete Mathematics May 22, 2012 8 / 1

Open Formula Definition An open formula is a formula without quantifiers E〉 xample O All atomic formulas: o(x), R(x,y) O(R(, y)Vo(x)) R(Co, C1)

Open Formula Definition An open formula is a formula without quantifiers . Example 1 All atomic formulas: φ(x), R(x, y) .... 2 (R(x, y) ∨ φ(x)). 3 R(c0, c1). Yi Li (Fudan University) Discrete Mathematics May 22, 2012 9 / 1

Substitution Definition(Substitution(Instantiation). If p is a formula and v a variable, we write pv)to denote the fact that v occurs free in p o If t is a term, then o(t), or if we wish to be more explicit, (v/t), is the result of substituting(or instantiating) t for all free occurrences of v in p We call p(t) an instance of p o If p(t)contains no free variables, we call it a ground instance ofφp

Substitution Definition (Substitution(Instantiation)) If ϕ is a formula and v a variable, we write ϕ(v) to denote the fact that v occurs free in ϕ. 1 If t is a term, then ϕ(t), or if we wish to be more explicit, ϕ(v/t), is the result of substituting ( or instantiating) t for all free occurrences of v in ϕ. We call ϕ(t) an instance of ϕ. 2 If ϕ(t) contains no free variables, we call it a ground instance of ϕ. Yi Li (Fudan University) Discrete Mathematics May 22, 2012 10 / 1