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