Objectives and Initial Findings

In this chapter we will first outline the basic objectives of this thesis in section 3.1. In sections 2.3 and 2.4 we will show that some of the initial assumptions (or hopes) about the relationship between CSs and FOPCL knowledge base do not hold. Especially it is not possible to read from a CS whether the related knowledge base is parametrically uniform or not - at least not for the case of imbalanced usage of ground atoms.

3.1 Objectives

This thesis investigates relationships between the characteristic of parametric uniformity of a FOPCL knowledge base $\kb$ and its related CS $\gamma(\kb)$ . In this section we introduce a number of new functions, which on a formal level represent some of these specific relations. The main question of this thesis will then be to find out whether some of these functions can be defined in a constructive way.

We start off with some terminology definitions.

Definition 16 (Construction, Calculation and Generation of CS)

Let $\kb$ be an FOPCL knowledge base.

We say that the CS $\gamma(\kb)$ can be

constructed if an algorithm exists by which the CS can be derived from $\kb$ ;
calculated if an algorithm exists by which the CS can be calculated by the numbers of different types of ground atoms (e.g. those of the antecedence and those of the conclusion) of $\kb$ ;
generated if an algorithm exists by which the CS can be constructed from a reduced set of possible worlds of $\kb$ .

We will use the above definitions to clearly distinguish the different cases we want to investigate and describe.

Relation Diagram for PU and CS of a Knowledge Base K\mathcal {K}K — Figure 3.1 Relation Diagram for PU and CS of a Knowledge Base $\mathcal {K}$

Figure 3.1 shows the possible relationships, which are investigated by this thesis, whereby

$tr_R$ signifies the transformation rules which transform $\kb$ into its parametrically uniform version $\mathcal{PU}(\kb)$ by manipulating the conditionals. These transformation rules are defined in [8] and are shown in table 2.1. We therefore know already that they can be defined in a constructive way.
$\gfull$ signifies the common method, i.e. the function which constructs the conditional structure $\gamma(\kb)$ from the full set of possible worlds derived from $\kb$ . We have seen in section 2.3 that $\gfull(\kb)$ can be defined in a constructive way.
$\gcalc$ signifies a possible method to construct the conditional structure $\gamma(\kb)$ of knowledge base $\kb$ by calculating it from the numbers of different types of ground atoms of $\kb$ . In chapter 5 and chapter 6 we will show that it is indeed possible to calculate the CS of some specific types of knowledge bases and conditionals.
$\gred$ signifies a possible method to construct the conditional structure $\gamma(\kb)$ of a knowledge base $\kb$ by generating it from a reduced set of possible worlds derived from $\kb$ . In chapter 7 to 9 we define the mechanism of reduced c-segments, which is a more efficient way to generate the related CS of single conditionals than using $\gfull(\kb)$ . Unfortunately the efficiency of this method will not be better than that of $\gfull$ if it generates the full CS of a knowledge base.
$\ginv$ signifies a possible method to transform a conditional structure back to a FOPCL knowledge base. The results in section 3.2 will show that different knowledge bases generate the same CSs and therefore such a transformation is generally not possible.
$tr_{CS}$ signifies a possible method to transform a conditional structure of a non-parametrically uniform knowledge base directly into the conditional structure of the related parametrically uniform version of that knowledge base, i.e. the transformation is performed without further knowledge of the conditionals of the knowledge base. In chapter 11 we will look at a very specific case, for which such transformation works on CS-level. Nevertheless, the restrictions of this case are so limiting that such method would be useful in practical cases. Besides for this specific case, no such transformation rules were found. Also the results of section 3.2 make it clear that even if more such transformation rules exist, they will never cover all cases which are covered with by the $\PU$ transformation rules as described in section 2.2.
$\gci$ and $\ggi$ signify possible methods to calculate immediately ( $ci$ ) or generate immediately ( $gi$ ) the parametrically uniform version of the CS of a knowledge base out of the non-parametrically uniform version of that knowledge base. With what was already said in the bullets above it seems not possible to do so and all investigations into this direction were unfruitful.

Besides that we are also interested whether it is possible to read from a given CS whether the CS is balanced or not. We will see already in section 3.3 that this is not possible for the case of imbalanced usage of ground atoms. In chapter 10 we will therefore look into CSs which are balanced with respect to sharing and will see that the CS of two conditionals, which are balanced with respect to the usage of ground atoms show certain patterns.

A further objective is to generate the equivalence classes of possible worlds for a given knowledge base, as defined by definition 15. We have seen that this is straight forward for the common method, but it will turn out difficult for other methods $\gcalc$ and $\gred$ .

3.2 Different Knowledge Bases Creating Same Conditional Structure

In this section we will investigate whether it is possible to constructively define a function $\ginv$ as described in section 3.1, i.e. a function which allows the re-construction of the details of a knowledge base purely from a given CS.

We start out with a proposition that states that no constructive definition can be made for $\ginv$ , as there exists no one-to-one relationship between knowledge bases and CSs More specifically: several knowledge bases can have the same CS.

Proposition 1 (No One-to-One Relation Between Conditional Structures and Knowledge Bases)

The function $\gamma: \allR \Rightarrow \allCS$ is not injective and therefore also not bijective.

Therefore the function $\ginv$ does not exist.

Example 11 shows two knowledge bases which have the same CS. Note that we do not show the full vf truth tables in order to save some space.¹

Example 11 (No One-to-One Relation Between Conditional Structures and Knowledge Bases)

Let $s=\{~a,~b~\}$ and $s_2=\{~k,~l,~m,~n~\}$ be two sorts and let $P_1$ and $P_2$ be predicates, $V_1$ and $V_2$ be variables over sort $s_1$ and let $V$ be a variable over $s_2$ .

Let ${R_1=\big<\big(P_1(V_1,V_2)\big)\big>}$ and ${R_2=\big<\big(P_2(V)\big)\big>}$ , two conditionals and ${\kb_1 = \{~\R_1~\},}$ ${\kb_2 = \{~\R_2~\}}$ be two FOPCL knowledge bases.

Then we have

${\herbrand(R_1) = \{~P_1(a,a),~P_1(a,b),~P_1(b,a),~P_1(b,b)~\}}$ and
${\herbrand(R_2)=\{~P_2(k),~P_2(l),~P_2(m),~P_2(n)~\}}$ .

The CSs of $\kb_1$ and $\kb_2$ are then

\gamma(R_1) = \gamma(R_2) = \{~(0,~4),~(1,~3),~(2,~2),~(3,~1),~(4,~0)~\}.

We can now proof proposition 1.

Proof

Example 11 shows that $\gamma$ results in the same CS for different knowledge bases. Therefore $\gamma$ is not injective and due to that also not bijective. This means that $\gamma$ cannot be inverted, i.e. $\ginv$ does not exist.□

Although this result shows that different knowledge bases can have the same CS, it seems still possible that a certain equivalence between knowledge bases which share the same CS could exist. We will show in section 3.3 that such an equivalence does not exist with respect to parametric uniformity.

3.3 Imbalanced Usage Cannot be Determined from a Conditional Structure

In this section we will show that two knowledge bases, one of them balanced and one of them imbalanced with respect to the usage of ground atoms, can have the same knowledge base. As such CSs cannot be distinguished from each other it is therefore not possible whether for a given CS the related knowledge base (from which it was constructed) is balanced or imbalanced with respect to the usage of ground atoms.

Proposition 2 (Imbalanced Usage Cannot be Determined from CS)

It cannot be determined from the CS $\gamma(\R)$ of a conditional $\R$ whether it holds that $\isBU(\R)$ or $\neg\isBU(\R)$ .

Example 12 (Imbalanced Usage Cannot be Determined from CS)

Let $s_1=\{~a,~b,~c~\}$ and $s_2=\{~x,~y~\}$ be two sorts. Let $C_1, C_2$ and $A$ be predicates and let $V_1, V_2, W$ be variables over sort $s_1$ and let $X$ be a variable over sort $s_2$ .

Let

$\R_1 = \big<\big(~C_1(V_1,V_2)~|~A(W)~\big),~V_1 \neq W,~V_2 \neq W~\big>$ ;
$\R_2 = \big<\big(~C_2(V_1,V_2,X)~|~A(W)~\big),~V_1 \neq V_2,~V_1 \neq W, V_2 \neq W~\big>$ ;
$\kb_1=\{~R_1~\}$ ; and
$\kb_2=\{~R_2~\}$ .

The groundings of $\R_1$ are

$r_1 =$	$\big<\big(~C_1(b,b)~\big\|~A(a)~\big)\big>$	$~~~~~~~$	$r_2 =$	$\big<\big(~C_1(b,c)~\big\|~A(a)~\big)\big>$
$r_3 =$	$\big<\big(~C_1(c,b)~\big\|~A(a)~\big)\big>$		$r_4 =$	$\big<\big(~C_1(c,c)~\big\|~A(a)~\big)\big>$
$r_5 =$	$\big<\big(~C_1(a,a)~\big\|~A(b)~\big)\big>$		$r_6 =$	$\big<\big(~C_1(a,c)~\big\|~A(b)~\big)\big>$
$r_7 =$	$\big<\big(~C_1(c,a)~\big\|~A(b)~\big)\big>$		$r_8 =$	$\big<\big(~C_1(c,c)~\big\|~A(b)~\big)\big>$
$r_9 =$	$\big<\big(~C_1(a,a)~\big\|~A(c)~\big)\big>$		$r_{10} =$	$\big<\big(~C_1(a,b)~\big\|~A(c)~\big)\big>$
$r_{11} =$	$\big<\big(~C_1(b,a)~\big\|~A(c)~\big)\big>$		$r_{12} =$	$\big<\big(~C_1(b,b)~\big\|~A(c)~\big)\big>.$

It holds that $|C(b,b)|_{\gnd(\R_1)} = 2 > |C(b,c)|_{\gnd(\R_1)} = 1$ and it follows with definition 5 that $\neg\isBU(\R_1)$ . Therefore it holds that $\neg\isPU(\kb_1)$ .

The groundings of $\R_2$ are

$r_1 =$	$\big<\big(~C_2(b,c,x)~\big\|~A(a)~\big)\big>$	$~~~~~~~$	$r_2 =$	$\big<\big(~C_2(c,b,x)~\big\|~A(a)~\big)\big>$
$r_3 =$	$\big<\big(~C_2(a,c,x)~\big\|~A(b)~\big)\big>$		$r_4 =$	$\big<\big(~C_2(c,a,x)~\big\|~A(b)~\big)\big>$
$r_5 =$	$\big<\big(~C_2(a,b,x)~\big\|~A(c)~\big)\big>$		$r_6 =$	$\big<\big(~C_2(b,a,x)~\big\|~A(c)~\big)\big>.$

As each ground atom of $C_2$ appears exactly once in the groundings of $\R_2$ and every grounding of $A$ appears exactly twice in the groundings of $\R_2$ it follows with definition 5 that $\isBU(\R_1)$ . Therefore it holds that $\isPU(\kb_2)$ .

The CSs of $\kb_1$ and $\kb_2$ are

$\gamma(\kb_1) =$
$\gamma(\kb_2) = \{$	$(0,~0),$
	$(0,~4), ~(1,~3), ~(2,~2), ~(3,~1), ~(4,~0),$
	$(0,~8), ~(1,~7), ~(2,~6), ~(3,~5), ~(4,~4), ~(5,~3), ~(6,~2), ~(7,~1), ~(8,~0),$
	$(0,~12), ~(1,~11) ~(2,~10), ~(3,~9), ~(4,~8), ~(5,~7),$
	$(6,~6), ~(7,~5), ~(8,~4), ~(9,~3), ~(10,~2), ~(11,~1), ~(12,~0)$	$\}.$

Example 12 proofs proposition 2.

This is unfortunately a rather unsatisfying result. It means that the capability of parametric uniformity cannot be determined simply from a given CS, without further information of the conditionals from which the CS is derived from.

The results of this and the previous section show that CSs do not reflect full information about the parametric uniformity of the underlaying knowledge base. In order to work on the level of CSs we therefore will always have to know certain details about the conditionals the CS was constructed from.

As we can’t derive whether a CS is balanced or not (at least with respect to the usage of ground atoms) it seems not likely that it is possible to come up with a function $tr_{CS}$ which allows the transformation of a non-balanced knowledge base into its balanced version simply on the level of the related CS. Still, there might be very different ways to transform a CS of a non-parametrically knowledge base into the CS of the parametrically uniform version of the knowledge base, but such transformation would then not be related to the $\mathcal{PU}$ transformation rules as introduced in section 2.2. Nevertheless we think that this highly unlikely, as already one of the most important characteristics of a parametrically uniform knowledge bases, i.e. the characteristic of holding a balanced usage or not, cannot be read from the CS. We therefore come up with the following assumption.

Assumption 1 (PU-Transformation on CS-Level Not Possible).

The function $tr_{CS}$ cannot be constructively defined.

3.4 Summary and Discussion

In section 3.1 we defined a set of methods or functions which we used to describe the objectives of this thesis. These functions describe the relationships between FOPCL knowledge bases and their related CS. We then showed in section 3.2 that different knowledge bases can generate the same CS, which lead us to the conclusion that the inverse function $\gamma^{-1}$ does not exist, i.e. it is not possible to go generate from a given CS the FOPCL knowledge base to which it relates. Based on the results of section 3.3 we then showed that it is very unlikely that the transformation function $tr_{CS}$ can be constructively defined.

These results are not very promising, as so far it was hoped that there would be a stronger relationship between a FOPCL knowledge base and its CS.

In the upcoming chapters we will now investigate in more detail how CSs can be constructed from specific types of FOPCL knowledge bases. The gained results will give us a better view on how CSs are structured. We then will come back in the last two chapters and have another look at the issue of PU transformation on CS-level.

In chapter 10 we will see that it might be possible to determine on CS-level whether two conditionals hold an imbalanced sharing. And in chapter 11 we will see that for very restricted cases even the transformation of a CS into a parametrically uniform version is possible. Based on the results of this section we will nevertheless not investigate any further details about the relationship of an imbalanced usage of ground atoms on CS-level.

Notes

All conditional structures within this chapter have been constructed by the common method $\gamma_{tab}$ as defined in section 2.3, mostly by making use of the KReator tool as introduced in section 2.4.