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
2.(x)y(x,y)A(x) We have observed that some variable a has relation with a quantifier(V) or r) In order to discuss the relation between variables and quantifiers, we have the following definition Definition 2(Occurrence). An occurrence of a variable v in a formula p is bound if there a subformula y of p containing that occurrence of u such that v begins with((Vu)or(v). An occurrence of v in p is free if it is not bound Here, we should pay attention to each occurrence in the definition. Definition3.A variable v is said to occur free in p if it has at least one free occurrence there. However, if we say a variable is free if it take place free once Consider the following examples Example 3. Given a formula 1.((y(a)(a, u))Av(r)) It is obvious that z is free for the first occurrence is bound and the second is free We have some special formulas. Consider the following example Example 4. Please observe the following formulas (y)((V)p(a, y))A(Va)(a) 2.((Va)(((yR(,u))v(yT(a, y)) 3.g(c0,c1) We can find a common feature that there is no free occurrence of any variable Definition 4. A sentence of predicate logic is a formula with no free occurrences of any variable In the most of cases, we only discuss sentences Contrary to sentence, we have another form of special formulas Definition 5. An open formula is a formula without quantifiers Consider the following example Example 5 All atomic formulas: o(a), R(, y) 2.(R(r, y)vo(a) 3.R(c0,c)
2. (((∀x)ϕ(x, y)) ∧ ψ(x)) We have observed that some variable x has relation with a quantifier (∀x) or (∃x). In order to discuss the relation between variables and quantifiers, we have the following definition. Definition 2 (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. Here, we should pay attention to each occurrence in the definition. Definition 3. A variable v is said to occur free in ϕ if it has at least one free occurrence there. However, if we say a variable is free if it take place free once. Consider the following examples: Example 3. Given a formula: 1. ((∃y)((∀x)ϕ(x, y)) ∧ ψ(x)) It is obvious that x is free for the first occurrence is bound and the second is free. We have some special formulas. Consider the following example. Example 4. Please observe the following formulas: 1. ((∃y)((∀x)ϕ(x, y)) ∧ (∀z)ψ(z)) 2. ((∀x)(((∀y)R(x, y)) ∨ ((∃y)T(x, y))). 3. ϕ(c0, c1) We can find a common feature that there is no free occurrence of any variable. Definition 4. A sentence of predicate logic is a formula with no free occurrences of any variable. In the most of cases, we only discuss sentences. Contrary to sentence, we have another form of special formulas. Definition 5. An open formula is a formula without quantifiers . Consider the following example. Example 5. 1. All atomic formulas: φ(x), R(x, y) .... 2. (R(x, y) ∨ φ(x)). 3. R(c0, c1). 2
In some case, we may substitute a variable with another term Definition 6(Substitution(Instantiation)). If p is a formula and v a variable, we write p(u)to denote the fact that v occurs free in p 1. Ift is a term, then o(t), or if we wish to be more explicit, p(u/t), is the result of substituting C or instantiating) t for all free occurrences of v in e. We call o(t) an instance of p 2. If p(t) contains no free variables, we call it a ground instance of y Consider the following example Example 6. Given a formula((vr(e, y))v(yS(a, y) 1. t is (a/s, y/t)=((Va)R(a, t))v((y)S(s, y)) 3. (a/c,y/d)=((v)R(r, c)V(y)S(s, d)) Generally, we have the following rules Example 7. The recursive definition of p(a/t) with substitution to. The recursive definition of to 1. t is a constant, t[r/tol ta/tol 3.t=g(t1,t2,…,tk), t[a/to]= g(t1[/to], t2[c/to],., tk[/to]) 4. p(a, y) is an atomic formula, p/to= p(to, y) 5.9==v/,p{/tol=-{/tol 6. p=9102, p/to]=p1a/to op2(c/to 7. p(a, y)=Q2v(, 3, 2), pr/tol Q2(v{/to),x≠ Consider the following substitution Example 8. Given a formula p (a)=y(a+y=0) and s(a)=r+l. Consider the substitution (/s(y)). We just assume that both variables are integers
In some case, we may substitute a variable with another term. Definition 6 (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 ϕ. Consider the following example. Example 6. Given a formula ((∀x)R(x, y)) ∨ ((∃y)S(x, y)), 1. It is denoted as ϕ(x, y). 2. ϕ(x/s, y/t) = ((∀x)R(x, t)) ∨ ((∃y)S(s, y)). 3. ϕ(x/c, y/d) = ((∀x)R(x, c)) ∨ ((∃y)S(s, d)). Generally, we have the following rules. Example 7. The recursive definition of ϕ(x/t) with substitution t0. The recursive definition of t0 to x in t. 1. t is a constant, t[x/t0] = t 2. t is a variable, t[x/t0] = ( t0 if t = x t o.w. (t 6= x) 3. t = g(t1, t2, . . . , tk), t[x/t0] = g(t1[x/t0], t2[x/t0], . . . , tk[x/t0]) 4. ϕ(x, y) is an atomic formula, ϕ[x/t0] = ϕ(t0, y) 5. ϕ = ¬ψ, ϕ[x/t0] = ¬ψ[x/t0] 6. ϕ = ϕ1ϕ2, ϕ[x/t0] = ϕ1[x/t0]ϕ2[x/t0] 7. ϕ(x, y) = Qzψ(x, y, z), ϕ[x/t0] = ( ϕ, x = z Qz(ψ[x/t0]), x 6= z Consider the following substitution. Example 8. Given a formula ϕ(x) = (∃y)(x + y = 0) and s(x) = x + 1. Consider the substitution ϕ(x/s(y)). We just assume that both variables are integers. 3
It is obvious that it is wrong after substitution However, some substitution is not correct in the point of view of semantic. We have the followin definition Definition 7. If the term t contains an occurrence of some variable a(which is necessarily free in t)we say that t is substitutable for the free variable v in (v) if all occurrences of a in t remain free in p (u/t) onsager the following example Example 9. Let p(a)=((yR(, u))V((Vz)Q(a, a)) 1. Ift= f(w, u), then we have p(t)=p(a/t)=(((yR((w, u),y))V((Va)Q(f(w, u), a))) 2. If t= gy, 8(y)), it is not substitutable for a in p(a) Proposition 8. If a term s is an initial segment of a term t, sCt, thens=t Theorem 9(Unique readability for terms). Every term s is either a variable or constant symbol or of the form f(s1, in which case f, n and the si for 1 er, the relevant forms: an atomic formula, (a B), (o,B), (a +B), (a),( aV B). Moreover, the relevant 4 Formation tree Definition 12. 1. Term formation trees are ordered, finitely branching tree T labeled with terms satisfying the following conditions (a) The leaves of T are labeled with variables of constant symbols (b) Each nonleaf node of T is labeled with a term of the form f(ti, ...,tn) (c) A node of t that is labeled with a term of the form f(t1, .. tn) has exactly n immediate successors in the tree. They are labeled in (lexicographic) order with t1,..., tn 2. A term formation tree is associated with the term with which its root node is labeled Proposition 13. Every term t has a unique formation tree associated with it Proposition 14. The ground terms are those terms whose formation trees have no variables on their leaves Definition 15. The atomic formula auxiliary formation trees are the branching trees of depth one whose root node is labeled with an atomic formula. If the root node of such a tree is labeled with an n-ary relation R(t1,., tn), then it has n immediate successor which are labeled in order with the terms t
It is obvious that it is wrong after substitution. However, some substitution is not correct in the point of view of semantic. We have the following definition. Definition 7. If the term t contains an occurrence of some variable x (which is necessarily free in t) we say that t is substitutable for the free variable v in ϕ(v) if all occurrences of x in t remain free in ϕ(v/t). Consider the following example. Example 9. Let ϕ(x) = (((∃y)R(x, y)) ∨ ((∀z)¬Q(x, z))). 1. If t = f(w, u), then we have ϕ(t) = ϕ(x/t) = (((∃y)R(f(w, u), y)) ∨ ((∀z)¬Q(f(w, u), z))). 2. If t = g(y, s(y)), it is not substitutable for x in ϕ(x). Proposition 8. If a term s is an initial segment of a term t, s ⊆ t, then s = t. Theorem 9 (Unique readability for terms). Every term s is either a variable or constant symbol or of the form f(s1, . . . , sn) in which case f, n and the si for 1 ≤ i ≤ n are all unique determined. Proposition 10. If a formula α is an initial segment of a formula γ, α ⊂ γ, then α = γ. Theorem 11 (Unique readability for formulas). Each formula φ is a precisely one of the following forms: an atomic formula, (α ∧ β),(α → β),(α ↔ β),(¬α),(α ∨ β). Moreover, the relevant ”components” of φ as displayed in each of these formula are uniquely determined. 4 Formation tree Definition 12. 1. Term formation trees are ordered, finitely branching tree T labeled with terms satisfying the following conditions: (a) The leaves of T are labeled with variables of constant symbols. (b) Each nonleaf node of T is labeled with a term of the form f(t1, . . . , tn). (c) A node of T that is labeled with a term of the form f(t1, . . . , tn) has exactly n immediate successors in the tree. They are labeled in (lexicographic) order with t1, . . . , tn. 2. A term formation tree is associated with the term with which its root node is labeled. Proposition 13. Every term t has a unique formation tree associated with it. Proposition 14. The ground terms are those terms whose formation trees have no variables on their leaves. Definition 15. The atomic formula auxiliary formation trees are the labeled , ordered, finitely branching trees of depth one whose root node is labeled with an atomic formula. If the root node of such a tree is labeled with an n-ary relation R(t1, . . . , tn), then it has n immediate successor which are labeled in order with the terms t1, . . . , tn. 4
Definition 16. The atomic formula formation trees are the finitely branching, labeled, ordered trees gotten from the auxiliary trees by attaching at each leaf labeled with a term the rest of the formation tree associated wnith t. Such a tree is associated with the atomic formula with which its root is labeled Proposition 17. Every atomic formula is associated with a unique formation tree Definition 18. The formula auxiliary formation trees are the labeled, ordered, binary branching trees T such that 1. The leaves of T are labeled with atomic formulas. 2. If o is a nonleaf node of f with one immediate successor o Ao labeled with a formula then g is labeled with n, u, or Vu for some variable v 3. If o is a nonleaf node with two immediate successors, o A0 and o A l labeled with formulas sp and y, then g is labeled withφ∧v,φVv,φ→,φ分v Definition 19. 1. The formula formation trees are the ordered, labeled trees gotten from the auziliary ones by attaching to each leaf labeled with an atomic formula the rest of its associated formation tree. Each such tree is again associated with the formula with which its root labeled 2. The depth of a formula is the depth of the associated auciliary formation tree Proposition 20. Every formula is associated with a unique(auciliary) formation tree. Proposition 21. The subformulas of a formula p are the labels of the nodes of e auxiliary formation tree associated with p Proposition 22. 1. The occurrences of a variable v in a formula p are in one-one correspon dence with the leaves of the associated formation tree that are labeled with u. We may also refer to the appropriate leaf labeled with v as the occurrence of v in 2. An occurrence of the variable v in p is bound if there is a formula o beginning with((Vu)or(v) which is the label of a node above the corresponding leaf of the formation tree for p labeled wuth u Proposition 23. If p is a formula and v a variable, then p(u/t) is the formula associated with the formation tree gotten by replacing each leaf in the tree for p(u) which is labeled with a free ccurrence of v with the formation tree associated with t and propagating this change through the Proposition 24. The term t is substitutable for v in (u) if all occurrences of ar in t remain free in (t), i.e., any leaf in the formation tree for t which is a free occurrence of a variable a remains in every location in which it appears in the formation tree described in Definition 3.8 5 Parsing algorithm With help of formation tree, we could parse a formula in a relative way. As the definition is an expansion of definition of proposition by introducing variable, function, predicates, and quantifiers
Definition 16. The atomic formula formation trees are the finitely branching, labeled, ordered trees gotten from the auxiliary trees by attaching at each leaf labeled with a term the rest of the formation tree associated with t. Such a tree is associated with the atomic formula with which its root is labeled. Proposition 17. Every atomic formula is associated with a unique formation tree. Definition 18. The formula auxiliary formation trees are the labeled, ordered, binary branching trees T such that 1. The leaves of T are labeled with atomic formulas. 2. If σ is a nonleaf node of T with one immediate successor σ ∧ 0 labeled with a formula ϕ, then σ is labeled with ¬ϕ, ∃vϕ, or ∀vϕ for some variable v. 3. If σ is a nonleaf node with two immediate successors, σ ∧ 0 and σ ∧ 1 labeled with formulas ϕ and ψ, then σ is labeled with ϕ ∧ ψ, ϕ ∨ ψ, ϕ → ψ, ϕ ↔ ψ. Definition 19. 1. The formula formation trees are the ordered, labeled trees gotten from the auxiliary ones by attaching to each leaf labeled with an atomic formula the rest of its associated formation tree. Each such tree is again associated with the formula with which its root is labeled. 2. The depth of a formula is the depth of the associated auxiliary formation tree. Proposition 20. Every formula is associated with a unique(auxiliary) formation tree. Proposition 21. The subformulas of a formula ϕ are the labels of the nodes of the auxiliary formation tree associated with ϕ. Proposition 22. 1. The occurrences of a variable v in a formula ϕ are in one-one correspondence with the leaves of the associated formation tree that are labeled with v. We may also refer to the appropriate leaf labeled with v as the occurrence of v in ϕ. 2. An occurrence of the variable v in ϕ is bound if there is a formula φ beginning with ((∀v) or ((∃v) which is the label of a node above the corresponding leaf of the formation tree for ϕ labeled with v. Proposition 23. If ϕ is a formula and v a variable, then ϕ(v/t) is the formula associated with the formation tree gotten by replacing each leaf in the tree for ϕ(v) which is labeled with a free occurrence of v with the formation tree associated with t and propagating this change through the tree. Proposition 24. The term t is substitutable for v in ϕ(v) if all occurrences of x in t remain free in ϕ(t), i.e., any leaf in the formation tree for t which is a free occurrence of a variable x remains in every location in which it appears in the formation tree described in Definition 3.8. 5 Parsing Algorithm With help of formation tree, we could parse a formula in a relative way. As the definition is an expansion of definition of proposition by introducing variable, function, predicates, and quantifiers. 5
Correspondingly, we can also extend parsing algorithm of proposition to recognize a formula in a direct approach. We first introduce a parsing subroutine for a general term and a atomic formula in the same way. And we then extend proposition's parsing algorithm to recognize a general formula which is left as an exercise Exercises 1. Given formulas in Ex 2(c),(e), (f)on page 88. Which occurrences of variables are free? Which are bound? 2. Ex 5(b, c)/ page 88 3. Ex 2(d, e)/ page 94 4. Ex 13/ page 95 5. Augment parsing algorithm for proposition logic to recognize a formula of predicate lo Here, we assume that predicates, functions, variables, and constants are represented by a sIn
Correspondingly, we can also extend parsing algorithm of proposition to recognize a formula in a direct approach. We first introduce a parsing subroutine for a general term and a atomic formula in the same way. And we then extend proposition’s parsing algorithm to recognize a general formula, which is left as an exercise. Exercises 1. Given formulas in Ex 2 (c),(e),(f) on page 88. Which occurrences of variables are free? Which are bound? 2. Ex 5(b, c)/ page 88. 3. Ex 2(d, e)/ page 94. 4. Ex 13/ page 95. 5. Augment parsing algorithm for proposition logic to recognize a formula of predicate logic. Here, we assume that predicates, functions, variables, and constants are represented by a single symbol. 6