Wifs The wffs of f are defined inductively by the following formation rules If t1, ... tn are terms and pn is an n-ary redicate variable or constant then pn (t1, .. tr )is a wff. Also each propositional variable or constant is wff.(Wffs of these forms are called atomic wffs) 2. If A is a wff, so is( 3. If A and B are wffs, So is(AV B 4. f a is a wff and is an individual variable then (Va A)is a wff. (wff A is the scope of va) Q: Formulate the definition of the set of wffs Q: Principle of Induction the Construction of ar wffee-p.6/23
Wffs The wffs of F are defined inductively by the following formation rules: 1. If t1, · · · ,tn are terms and Pn is an n-ary predicate variable or constant, then Pn(t1, · · · ,tn) is a wff. Also each propositional variable or constant is wff. (Wffs of these forms are called atomic wffs) 2. If A is a wff, so is (∼ A) 3. If A and B are wffs, so is (A ∨ B) 4. If A is a wff and x is an individual variable, then (∀xA) is a wff. (wff A is the scope of ∀x) Q: Formulate the definition of the set of wffs. Q: Principle of Induction the Construction of a wff. Logic in Computer Science – p.6/23
abbreviations 彐 A stands for~Wx~A (Va E S)A stands for Va (s(a2 a (丑c∈S) A stands for3x(S(x)∧A) Logic in Computer Science - p 7/23
Abbreviations • ∃xA stands fo r ∼ ∀ x ∼ A • ( ∀ x ∈ S ) A stands fo r ∀ x ( S ( x ) ⊃ A ) • ( ∃ x ∈ S ) A stands fo r ∃ x ( S ( x ) ∧ A ) Logic in Computer Science – p.7/23
Free and bound 1. The well formed(wf) parts of b are the consecutive subformulas of B(including B itself) Which are wffs 2. An occurrence of a variable x in a wff b is bound iff it is in a wf part of b of the form VaC. otherwise it is free 3. The bound/ free varibles of a wff are those which have bound/ free occurrences in a wff (at different occurrences) 4. a wff without free individual variables is said to be a closed wff 5. A sentence is a wff without free variables of any type Logic in Computer Science -p 8/23
Free and Bound 1. The well formed(wf) parts of B are the consecutive subformulas of B(including B itself) which are wffs. 2. An occurrence of a variable x in a wff B is bound iff it is in a wf part of B of the form ∀xC; otherwise, it is free. 3. The bound / free varibles of a wff are those which have bound / free occurrences in a wff (at different occurrences). 4. A wff without free individual variables is said to be a closed wff. 5. A sentence is a wff without free variables of any type. Logic in Computer Science – p.8/23