Algebraic approach to logical inference implementation

1310

B. Kulik, A. Fridman, A. Zuenko

4.2 Correspondence between N-tuple Algebra and Predicate Calculus

In trivial case (when individual attributes do not correspond to multiplace rela-

tions), an n-tuple corresponds to conjunction of one-place predicates with different

variables. For example, a C-n-tuple P [XY Z] = [P

1

P

2

P

3

] where P

1

⊆ X; P

2

⊆ Y ;

P

3

⊆ Z corresponds to a logical formula H = P

1

(x) ∧ P

2

(y) ∧ P

3

(z).

A D-n-tuple P =

P

1

P

2

P

3

corresponds to the negation of the formula H

(disjunction of one-place predicates) ¬H = ¬P

1

(x) ∨ ¬P

2

(y) ∨ ¬P

3

(z).

An elementary n-tuple that is a part of a non-empty NTA object corresponds

to a satisfying substitution in a logical formula.

An empty NTA object corresponds to an identically false formula.

An NTA object that equals any particular universe corresponds to a valid for-

mula, or a tautology.

A non-empty NTA object corresponds to a satisfiable formula.

In NTA, attribute domains can be any arbitrary sets that are not necessarily

equal to each other. This means that NTA structures correspond to formulas of

many-sorted predicate calculus.

Now let us consider quantifiers in NTA.

If a dummy attribute is added to a C-n-tuple or a C-system, the procedure

corresponds to the derivation rule of predicate calculus called generalization rule. For

example, if an NTA object G[XZ] =

{a, c}

∗

{a, c, d}

{b, c}

corresponds to a formula

F (x, z) of predicate calculus, by adding a dummy attribute Y into this NTA object

we get an NTA object G

1

[XY Z] = +Y (G[XZ]) =

{a, c}

∗

∗

{a, c, d}

∗

{b, c}

which

corresponds to the formula ∀yF (x, z) derived from the formula F (x, z) according

to generalization rule. This relation is obvious for C-n-tuples and C-systems, but

needs to be proved for D-n-tuples and D-systems.

Theorem 13. Adding a new dummy attribute to a D-n-tuple or a D-system cor-

responds to the formula ∀y(P ).

Proof. Let a D-n-tuple P [X

1

X

2

. . . X

n

] = ]P

1

P

2

. . . P

n

[ be given. If we add a dummy

attribute Y to it, we get Q[Y X

1

X

2

. . . X

n

] = ]ØP

1

P

2

. . . P

n

[. Transforming this NTA

objects into C-systems, we have

P =











P

1

∗

. . .

∗

∗

P

2

. . .

∗

. . .

. . .

. . .

. . .

∗

∗

. . .

P

n











;

Q =











∗

P

1

∗

. . .

∗

∗

∗

P

2

. . .

∗

. . .

. . .

. . .

. . .

. . .

∗

∗

∗

. . .

P

n











Hence, Q = +Y (P ) = ∀y(P ).

2

Suppose that a D-system R[X

1

X

2

. . . X

n

] is given. Let R

1

= +Y (R) = R

1

[Y X

1

X

2

. . . X

n

]. In the D-system R

1

, “Ø” are components of the attribute Y in all D-n-

tuples. After transforming this D-system into a C-system according to Theorem 9,

---

Algebraic Approach to Logical Inference Implementation

1311

the results in projection [X

1

X

2

. . . X

n

] are the same as in transformation of the D-

system R into a C-system, and dummy components “*” are now components of the

attribute Y in the C-system R

1

. Therefore, R

1

= +Y (R) = ∀y(R).

The two theorems that follow define the semantics of the operation -Attr.

Theorem 14. Let R[. . . X . . .] be a C-system that has no C-n-tuples with empty

components in the X attribute. Then for the predicate P (. . . , x, . . .) that corre-

sponds to this C-system, the formula −X(R) corresponds to the formula ∃x(P ).

Proof. Let R be a C-n-tuple. Then under the conditions of the theorem corre-

spondence −X(R) ⇔ ∃x(P ) is evident. Let R be a C-system that contains C-

n-tuples R

1

, R

2

, . . . , R

n

. This means that R = R

1

∪ R

2

∪ . . . ∪ R

n

. Formula

P = P

1

∨ P

2

∨ . . . ∨ P

n

, where P

i

are formulae that correspond to C-n-tuples R

i

corresponds to this formula in predicate calculus. Applying −X operation to R, we

get −X(R) = −X(R

1

) ∪ −X(R

2

) ∪ . . . − X(R

n

).

A formula of predicate calculus ∃x(P

1

) ∨ ∃x(P

2

) ∨ . . . ∨ ∃x(P

n

) corresponds to the

right part of the above equality. According to the rules of equivalent transformations

in mathematical logic, the formula equals to a formula ∃x(P

1

∨ P

2

∨ . . . ∨ P

n

), which

is ∃x(P ) after substitution.

2

Theorem 15. Let R[. . . X . . .] be a D-system that has no D-n-tuples with compo-

nents “*” in the X attribute. Then for a predicate P (. . . , x, . . .) corresponding to

this D-system, formula −X(R) corresponds to the formula ∀x(P ).

Proof. The formula ∀x(P ) is known to be equal to ¬(∃x(¬P )). A C-system R that

equals to the complement of the D-system R corresponds to the expression ¬P .

Q = −X(R) corresponds to the formula ∃x(¬P ) since satisfies the conditions of

Theorem 14. Then ¬(∃x(¬P )) is an NTA object that equals a D-system all of whose

components equal the complements of corresponding components of Q. Therefore,

Q = −X(R) as the attribute X has been eliminated from the C-system R.

2

Hence, if an attribute (e.g. X) is eliminated from a C-system, it means that

the quantifier ∃x is applied to this object, and if this attribute is eliminated from

a D-system, it means that the quantifier ∀x is applied to this object. For example,

let a C-system and its complement expressed as a D-system be given:

Q[XY Z] =

{a, b, d}

{f, h}

{b}

{b, c}

∗

{a, c}

and

Q[XY Z] =

{c}

{g}

{a, c}

{a, d}

Ø

{b}

.

Then

∃x(Q[XY Z]) =

{f, h}

{b}

∗

{a, c}

---