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