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