Discrete mathematics Software school Fudan University May14,2013
. . Discrete Mathematics Yi Li Software School Fudan University May 14, 2013 Yi Li (Fudan University) Discrete Mathematics May 14, 2013 1 / 30
Review o Limits of pl o Predicates and quantifiers
Review Limits of PL Predicates and quantifiers Yi Li (Fudan University) Discrete Mathematics May 14, 2013 2 / 30
utline o Terms Formuals Formation tree
Outline Terms Formuals Formation tree Yi Li (Fudan University) Discrete Mathematics May 14, 2013 3 / 30
Predicates and Quantifiers o predicates variables constants o functions o 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 14, 2013 4 / 30
Formula Definition(Subformula) A subformula of a formula p is a consecutive sequence of symbols from yp which is itself a formula Xam le Given an formula (x)(y=(x)Vo(x,y)→(日z)a(z) O Is((x)p(x))a subformula? o ls o(x)a subformula? (x)((x)∨叭(x,y).(z)a(z),y(x),叭(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 14, 2013 5 / 30
Occurrence amp dle Consider the following examples o(x)y(x,y)∧(x)/(x) (x)y(x,y)∧v(x) Definition(Occurrence) An occurrence of a variable v in a formula p is bound if there is a subformula b of p containing that occurrence of v such that a begins with((Vv)or(v).An occurrence of v in o 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 14, 2013 6 / 30
Free Occurrence amp dle Consider the following examples Q(三y)(x)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 14, 2013 7 / 30
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 ot 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 14, 2013 8 / 30
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)) O 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 14, 2013 9 / 30
Substitution Definition(Substitution(Instantiation). If y is a formula and v a variable, we write p(v)to denote the fact that v occurs free in p o If t is a term, then p(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 plt)an instance of yp o If p(t) contains no free variables, we call it a ground instance of
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 14, 2013 10 / 30