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