Report

We will now study some special kinds of non-standard quantifiers. Definition 4. Let (x), (x) be two fixed formulae of a language Ln such that x is the only free variable in both of them and they don’t have common predicates. Let M and N be two models. Then we have the following two four-fold tables: We define: N is associational M non- N non- better than M if a2a1, d2d1, a1 b1 a2 b2 c1c2, b1b2. Moreover, non- c1 d1 non- c2 d2 a binary quantifier is associational if, for all formulae (x) and (x), all models M, N: if vM((x)(x)) = TRUE, N associational better than M, then vN((x)(x)) = TRUE. Obviously, the quantifier of simple association is associational: this follows by the fact that, under the given circumstances, a2d2a1d1>b1c1b2c2. Church quantifier of implication is associational, too. Indeed, given a model M such that vM((x) =>C(x)) = TRUE, the corresponding four-fold table has a form M non- a1 c1 non- 0 d1 N non- a2 c2 non- 0 d2 Thus, any model N that is associational better than M has a form Thus, vN((x) =>C(x)) = TRUE. Quantifiers of founded p-implication are associational: if a2a1 n, b1b2, then a2b1a1b2 , therefore a2a1+ a2b1 a2a1+ a1b2 and finally, a2 a2 b2 a1 a 1 b1 p (Today called : Basic implication) I Definition 5. Let (x) , (x) be two fixed formulae of a language Ln such that x is the only free variable in both of them and they don’t have common predicates. Let M and N be two models. Then we have the following two four-fold tables: M non- a1 c1 non- b1 d1 N non- a2 c2 non- b2 d2 We define: N is implicational better than M if a2a1, b1b2. Moreover, a binary quantifier is implicational if, for all formulae (x) and (x), all models M, N: if vM((x)(x)) = TRUE, N implicational better than M, then vN((x)(x)) = TRUE. Church quantifier of implication is implicational, quantifiers of founded p-implication are implicational [proof: by a similar argument that they are associational]. However, quantifier of simple association is NOT implicational: consider the following counter example: Clearly, N is implicational better than M, and a1d1c1b1 thus, vM((x)~(x)) = TRUE. However, a2d2<c2b2, thus M non- vN((x)~(x)) = FALSE. Therefore ~ is not implicational. non- a1 = 1 c1 = 1 b1 = 1 d1 = 2 N non- a2 = 1 c2 = 2 non- b2 = 1 d2 = 1 Lemma. Let be an implicational quantifier. Then is associational. Proof. Let be implicational and vM((x)(x)) = TRUE If N is associational better than M, then N is clearly also implicational better than M, so vN((x)(x)) = TRUE. Therefore is associational, too. Theorem 2. Let (x), (x), (x) be formulae, Proof. Let M be a model such that and let be an implicational quantifier. Then vM((x) (x)) = TRUE and (x) (x) M non- (x) [(x)(x)] a1 b1 is a sound rule of inference. non- c1 d1 In the proof we used an obvious fact: for all implicational quantifiers , if We realise that a1 = #{x | vM((x)) = vM((x)) = TRUE} vM((x) (x)) = TRUE and #{x | vM((x)(x)) = vM((x))=TRUE} M non- = a2 and a1 b1 b1 = #{x | vM((x)) = vM((x)) = TRUE } #{x | vM((x) (x)) = vM((x)) = TRUE} non- c1 d1 Then, for any other formulae *(x), = #{x | vM(((x)(x))) = vM((x)) = TRUE }. Thus, we have *(x) such that M * non-* * a2 >= a1 c2 non-* b1 >= b2 d2 we have vM(*(x) *(x)) = TRUE, too. We will use this fact in the next Theorem, too. M non- -OR- a2 >= a1 c2 non-(OR) b1 >= b2 d2 Since is implicational we conclude that vM((x) [(x)(x)]) = TRUE, too. Theorem 3. Let (x), (x), (x) be formulae, Proof. Let M be a model such that and let be an implicational quantifier. Then vM( ([(x) (x)] (x)) = TRUE and [(x) (x)] (x) M non- (x) [(x)(x)] and non- a1 b1 is a sound rule of inference. non- or Theorem 4. Let (x) and (x) be formulae, and let ~ be the simple association quantifier. Then (x) ~ (x) SYM (x) ~ (x) and (x) ~ (x) NEG (x) ~ (x) are sound rules of inference. Exercises 13. Prove Theorem 4. 14. Prove that Theorem 4 does not hold for founded p-implication quantifiers. c1 d1 We realise that a1 = #{x | vM((x)(x))) = vM((x)) = TRUE} #{x | vM((x)(x))) = vM((x)) = TRUE} = a2 and b1 = #{x | vM((x)(x))) = vM((x)) = TRUE} = #{x | vM((x)) = vM((x) (x)))= TRUE } = #{x | vM((x)) = vM(((x)(x)))= TRUE } = b1. Thus, we have in the model M M non- OR a2 >= a1 c2 non-( OR ) b1 >= b2 d2 Since is implicational we conclude that vM((x) [(x)(x)]) = TRUE, too.• We have introduced deduction rules (i.e. sound rules of inference) mainly to minimise the amount tautologies, called hypothesis i.e. outputs in practical GUHA data mining tasks. For example, Theorem 1 says that if is an implicational quantifier and (x) (x) is true in a given model M, so is (x) [(x)(x)] true. Thus, we do not have to print (x) [(x)(x)] as a data mining result. Next we will study some other useful deduction rules. Consider elementary conjunctions EC and elementary disjunctions ED, i.e. open formulae of a form P1(x) ... kPk(x) and P1(x)... kPk(x), where i:s are either ‘’ or empty sign. For example, P1(x)P5(x) and P1(x)P3(x) P5(x) are EC’s P2(x)P3(x)P4(x) and P2(x)P4(x) are ED’s. Denote EC’s or T by symbols , 2, 3,… (maybe empty) and denote ED’s or by symbols , 2, 3,… (maybe empty). Definition 6. An elementary association is a sentence of the form , where is a quantifier and , are disjoint, i.e. have no common predicates. Let and 22 be elementary associations. We say that results from 22 by specification if either and 22 are identical or there is an ED 0 disjoint from 1 such that 2 and 01 are logically equivalent (i.e. have always the same truth value) and is logically equivalent to 20. [We say also: despecifies to 22] Example. P1(x)P3(x) P5(x) P2(x)P4(x) results from P1(x)P5(x) P2(x)P3(x)P4(x) by specification [indeed, 0 = P3(x)] Moreover, we say that results from 22 by reduction [or dereduces to 22] if is 2 and 1 is a subdisjunction of 2 Example.[P1(x) P5(x)] [P2(x) P3(x)P4(x)] results from [P1(x)P5(x)] [P2(x)P3(x)P4(x)P6(x)P7(x)] by reduction [indeed, 2 = P6(x)P7(x)]. We introduce the despecifying-dereduction rules (SpRd-rules); they are of the form where results from 22 by successive reduction and specification, 22 i.e. there is a ED 3 (a sub-ED of 2 ) such that 1 despecifies to 23 and 23 dereduces to 22. Example. [P1P3 P5] [P2P4] despecifies to [P1 P5] [P2P3P4] and [P1 P5] [P2P3P4] dereduces to [P1 P5] [P2P3P4P6P7] Thus, we have an SpRd-rule [P1P3 P5] [P2P4] [P1 P5] [P2P3P4P6P7] Theorem 5. For any implicational quantifier , SpRd-rules are sound rules of inference. Proof. In a same manner than Theorem 4 and Theorem 5.ž Remark. Theorem 5 can be reformulated in the following way: whenever is a SpRd-rule, then ( ) (22 ) [i.e. is a tautology]. 22 Theorem 5. SpRd-rules are transitive, that is, if and 22 then 1 22 33 33 Proof. The result is obvious as soon as we realise that the order of despecification and dereduction can be reverted, i.e. ( 2 ) ( 2 ) (2 ) dereduces to despecifies to despecifies to ( 2 ) dereduces to We introduce two more types of quantifiers: p- equivalence quantifiers, where 0 < p 1. (today: Basic equivalence) For any model M, v(x ((x) p (x))) = TRUE iff (a+d) p(a+b+c+d), I in particular, in a model M such that M non- 0 c non- b 0 b+c > 0, v(x ((x) p (x))) = FALSE (2 2 ) p- equivalence quantifiers, also called -double quantifiers, where 0 < p 1. (Basic double implication) For any model M, v(x ((x) p(x))) = TRUE iff a p(a+b+c), I in particular, in a model M such that M non- 0 0 non- 0 d d > 0, v(x ((x) p (x))) = FALSE Exercises. Prove that 15. p- equivalence quantifiers and 16. p - equivalence quantifiers are associational