Discrete Mathematics(II) Spring 2012 Lecture 12 Term. Formula and formation Tree Lecturer. yil 1 Overview In the last lecture, predicates, variables, constants, functions and quantifiers are introduced to enhance the capability of logic to express much rich sentences. In this lecture, we will discuss the form of predicate logic in the view of point of syntax 2 Term Term has been defined in the last lecture. It includes constant. variable and function. As function can be nested, a very complicated term could be constructed 3 Formula Formula is a sequence of symbols of predicated language formed following a specific rules. Similar to proposition logic, we here also introduce subformula to further investigate formula Definition 1(Subformula). A subformula of a formula p is a consecutive sequence of symbols from o which is itself a formula Consider the following example Example 1. Given an formula(((Va)(p(a)vo(a, D))-(x)o(a)) 1. Is((Varo(a)) a subfor milla 2. Is o(r a subformula? 3.((Va)(p(a)vo(a, y)),(x)o()), p(),o(a, y), and o(z) all are subformulas Here, we should pay attention to consecutive. Otherwise, we could take some subsequence wrong as a subformula. Obviously, the first one is not a subformula for it is not a consecutive sub-sequence of the given formula. However, the second one is something special, which depends how rigorous you apply definition Let's consider the following examples Example 2. Given the following formulas 1.((x)y(x,y)A(x)v(x)Discrete Mathematics (II) Spring 2012 Lecture 12: Term, Formula and Formation Tree Lecturer: Yi Li 1 Overview In the last lecture, predicates, variables, constants, functions and quantifiers are introduced to enhance the capability of logic to express much rich sentences. In this lecture, we will discuss the form of predicate logic in the view of point of syntax. 2 Term Term has been defined in the last lecture. It includes constant, variable, and function. As function can be nested, a very complicated term could be constructed. 3 Formula Formula is a sequence of symbols of predicated language formed following a specific rules. Similar to proposition logic, we here also introduce subformula to further investigate formula. Definition 1 (Subformula). A subformula of a formula ϕ is a consecutive sequence of symbols from ϕ which is itself a formula. Consider the following example. Example 1. 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. Here, we should pay attention to consecutive. Otherwise, we could take some subsequence wrong as a subformula. Obviously, the first one is not a subformula for it is not a consecutive sub-sequence of the given formula. However, the second one is something special, which depends how rigorous you apply definition. Let’s consider the following examples. Example 2. Given the following formulas: 1. (((∀x)ϕ(x, y)) ∧ ((∃x)ψ(x))) 1