### GUHA - theory 2

```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 a2a1, d2d1,

a1
b1

a2
b2
c1c2, b1b2. 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, a2d2a1d1>b1c1b2c2.
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 a2a1 n, b1b2,
then a2b1a1b2 , 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 a2a1, b1b2.
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 a1d1c1b1
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 22 be elementary associations. We say that  results from 22 by
specification if either  and 22 are identical or there is an ED 0 disjoint from 1
such that 2 and 01 are logically equivalent (i.e. have always the same truth value)
and  is logically equivalent to 20. [We say also:  despecifies to 22]
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 22 by reduction [or  dereduces to
22] 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 22 by successive reduction and specification,
22
i.e. there is a ED 3 (a sub-ED of 2 ) such that 1 despecifies to 23
and 23 dereduces to 22.
Example. [P1P3 P5]  [P2P4] despecifies to [P1 P5]  [P2P3P4] and
[P1 P5]  [P2P3P4] dereduces to [P1 P5]  [P2P3P4P6P7] Thus, we
have an SpRd-rule
[P1P3 P5]  [P2P4]
[P1 P5]  [P2P3P4P6P7]
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 ( ) (22 ) [i.e. is a tautology].
22
Theorem 5. SpRd-rules are transitive, that is, if  and
22 then 1
22
33
33
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
```