Calculation of Conditional Contributions

In this chapter we will investigate whether it is possible to constructively define a function $\gcalc$ as described in section 3.1, i.e. a function which calculates the CS $\gamma(\kb)$ of knowledge base $\kb$ from the numbers of different types of ground atoms of $\kb$ .

We will restrict the investigation to the calculation of conditional contributions of atomic conditionals, i.e. to atomic knowledge bases which only include a single conditional.

Although many different types of conditionals have been investigated whether their conditional contribution can be calculated or not, we only came up with a subset of atomic conditionals, for which this is possible. This subset are atomic conditionals which don’t include non-local instantiation restrictions, i.e. which either free of instantiation restrictions at all or only include local instantiation restrictions, as defined in section 4.9

The following chapters will show that the calculation for c-, ca- and cc-conditionals varies quite substantially. It also has the drawback that the resulting conditional contribution is decoupled from the possible worlds of the related conditional. Therefore it is also not possible to derive the equivalence classes of possible worlds from the calculated conditional contributions. These issues are discussed in the the last section of this chapter.

6.1 Calculation of Conditional Contributions of C-Conditionals

In this section we show how to calculate the conditional contribution of a c-conditional which is free of non-local instantiation restrictions.

The following proposition states that the conditional impact of a c-conditional is the MOS of the admissible ground atoms of the conclusion predicate of the conditional.

Proposition 13 (Maximum Ordered Sum of a C-Conditional)

Let $\Rc = \big<\big(~C(V_1,\cdots,V_v)~|~\top~\big),~\xi~\big>\in \kb$ be a c-conditional, where $\xi$ is free of any non-local instantiation restrictions.

Then the conditional impact of $\Rc$ is $\gamma(\Rc) = [|\cat(\Rc)|]$ .

Proof

The proof is the same as the proof of proposition 12, we just need to interpret $\top$ as a canonical a-segment. This is a valid interpretation as the semantic meaning of the $\top$ symbol is that it is always true. It therefore counts in every possible world. The canonical a-segments were introduced in a way that they only count when the related ground atoms are set to true.□

Example 35 (Maximum Ordered Sum of a C-Conditional)

Let $s=\{~a,~b,~c~\}$ be a sort, $V$ be a variable ranging over $s$ and ${\Rc = \big<\big(C(V)|\top\big)\big>}$ be a c-conditional.

Table 6.1 shows the vf truth table of $\Rc$ , from which we can see that the counting functions for the individual possible worlds result in vf-pairs which are all part of the MOS $[3]$ . It also shows that $\Omega(\Rc)$ covers the complete set of vf-pairs which are included in $[3]$ .

Table 6.1
$\Omega(\Rc)$	$C(a)$	$C(b)$	$C(c)$	$\vf_{\Rc}(\omega_{(i_1,\cdots,i_k)})$
$\omega_{()}$	$0$	$0$	$0$	$(0,~3)$	[3]
$\omega_{(1)}$	$0$	$0$	$1$	$(1,~2)$
$\omega_{(2)}$	$0$	$1$	$0$	$(1,~2)$
$\omega_{(1,2)}$	$0$	$1$	$1$	$(2,~1)$
$\omega_{(3)}$	$1$	$0$	$0$	$(1,~2)$
$\omega_{(1,3)}$	$1$	$0$	$1$	$(2,~1)$
$\omega_{(2,3)}$	$1$	$1$	$0$	$(2,~1)$
$\omega_{(1,2,3)}$	$1$	$1$	$1$	$(3,~0)$

Table 6.1: vf truth table of

R^c

of Example 35

6.2 Calculation of Conditional Contributions of CA-Conditionals

In this section we will show how to calculate the conditional contribution of a ca-conditional which is free of non-local instantiation restrictions.

Proposition 14 (Maximum Ordered Sum of a CA-Conditional)

Let $\Rca$ be a ca-conditional which if free of any non-local instantiation restrictions.

Let $n = |\cat(\Rca)|$ and $m = |\aat(\Rca)|$ .

The conditional contribution of $\Rca$ is

\gamma(\Rca) = \{~[0],~[n],~2[n],~\cdots,~m[n]~\}

Proof

Let $a_t\in\aat(\Rca)$ be an a-atom of $\Rca$ and let $t$ be the index of $a_t$ .

As there are only non-local instantiation restrictions and as $C \neq A$ it holds based on proposition 8 that the counting functions are not influenced by the instantiation restrictions. Due to proposition 12 it holds for every canonical a-atom $a_{t}$ of $\Rca$ that $a_t$ contributes the MOS $[|\acountsc(\Rca,~a_t)|]$ to $\gamma(\Rca)$ . Therefore every canonical a-segment counts all c-atoms, i.e. it is $|\acountsc(\Rca,~a_t)| = n$ . With this it follows that all canonical a-segments of $\Rca$ contribute the same MOS $[n]$ .

Let $\omega^c\in\OmegaC(\Rca)$ be a c-segment of $\Rca$ and let $\omega^a_{(j_1,~\cdots,~j_l)}\in\OmegaA(\Rca)$ be a composed a-segment of $\Rca$ .

Due to proposition 9 it holds that every vf-pair $\vfa_{\Rca}(\omega^c,~\omega^a_{(j_1,~\cdots,~j_l)})$ is the sum of the vf-pairs generated by $\omega^c$ together with the canonical a-segments $\omega^a_{(j_1)},~\cdots,~\omega^a_{(j_l)}$ .

As the canonical a-segments all contribute the same vf-pairs for a given c-segment $\omega^c$ it follows that any vf-pair $\vfa_{\Rca}(\omega^c,~\omega^a_{(j_1,~\cdots,~j_l)})$ is the $l$ -multiple of the vf-pair counted by any of the canonical a-segments $\omega^a_{(j_1)},~\cdots,~\omega^a_{(j_l)}$ .

It follows that the set of all vf-pairs which are generated by an a-segment $\omega^a_{(j_1,~\cdots,~j_l)}$ for all c-segments of $\OmegaC(\Rca)$ is the $l$ -multiple of the MOS $[n]$ , with $0 \leq l \leq m$ . Note that this also holds for canonical a-segments as well as for $\omega^a_{()}$ .

As the CS $\Rca$ is the set of all vf-pairs contributed by the a-segments of $\Rca$ it follows that

\gamma(\Rca) = \{~[0],~[n],~2[n],~\cdots,~m[n]~\}.

□

We explain the proof of proposition 14 by looking at the reduced vf truth table in table 5.2.

Example 36 (Maximum Ordered Sum of a CA-Conditional)

Continuing from example 31.

It is $\Rca$ a ca-conditional without instantiation restrictions. Therefore proposition 14 applies to it.

For $\Rca$ we get $|\cat(\Rca)|=2=n$ and $|\cat(\Rca)| = 2 = m$ .

The middle section of the table lists the vf-pairs as counted by the two canonical a-segments. For any given c-segment these vf-pairs are identical (e.g. in line two they are both $(1,~1)$ . Based on proposition 12 each canonical a-segment contributes a MOS to $\gamma(\Rca)$ , which we can see in the last line of the table, underneath each canonical a-segment.

The last column represents the composed a-segment $\omega^a_{(1,2)}$ , for which the composed vf-pairs can be calculated as the sums of the vf-pairs of the canonical a-segments $\omega^a_{(1)}$ and $\omega^a_{(2)}$ , due to proposition 11.

We know already that the conditional contribution of $\Rca$ can be read from the last line in the vf truth table, so that it holds that

\gamma(\Rca) = \{~(~[0],~[2],~2[2]~)~\} = \{~(~0[2],~1[2],~2[2]~)~\} = \{~(~0[n],~1[n],~\cdots,~m[n]~)~\}.

6.3 Calculation from CC-Conditionals and CAC-Conditionals

The calculation of the conditional contribution of cc-conditional is unfortunately not straight forward. In fact we were only able to come up with a rule that covers the very simple case where there are no instantiation restrictions at all, i.e. there are not even local instantiation restrictions allowed.

Proposition 15 (Maximum Ordered Sum of a CC-Conditional)

Let $\Rcc = \big<\big(~C(V_1,\cdots,V_v)~|~C(W_1,\cdots,W_v)~\big),~\emptyset~\big>\in \kb$ a cc-conditional which is free of any instantiation restrictions.

Let $n = |\cat(\Rcc)| = |\aat(\Rcc)|$ .

The conditional contribution of $\Rcc$ is

\gamma(\Rcc) = \{~(0,~0),~(1,~|n|-1),~2\cdot(2,~|n|-2), \cdots,(|n|-1)\cdot(|n|-1,~1),~|n|\cdot(|n|,~0)~\}

Proof

As $\Rcc$ is a cc-conditional it holds that $C = A$ . As there are no instantiation restrictions in $\Rcc$ it holds that $\OmegaC(\Rcc) = \OmegaA(\Rcc)$ and therefore it is $\Omega(\Rcc)=\OmegaC(\Rcc)=\OmegaA(\Rcc)$ .

For $\omega=\omega^c_{()}$ there is neither an a-atom nor a c-atom verified and we get the vf-pair $(0,0)$ .

We look at the case where $\omega=\omega^c_{(t)}$ , i.e. the possible world where only one ground atom $a_t$ is verified. As there are no instantiation restrictions it holds that the related canonical a-segment $\omega^a_{(t)}$ counts exactly one verified c-atom $a_t$ , all other ground atoms are falsified and we get the vf-pair $(1,~|n|-1)$ .

For all possible worlds which verify $k$ a-atoms it then follows that $k$ canonical a-segments count not only their own verified ground atom, but all $k$ verified ground atoms as verified. It follows that if several ground atoms $g_{t_1}, \cdots, g_{t_k}$ are verified within a possible world then the related canonical a-segments $\omega^a_{(t_1)}, \cdots, \omega^a_{(t_k)}$ do not count individually, i.e. they do not contribute their canonical vf-pairs to the conditional contribution, but only commonly, i.e. only the composed a-segment $\omega^a_{(t_1,\cdots,t_k)}$ contributes its vf-pair to the conditional contribution of $\Rcc$ .□

It is important to note that the above proposition only applies if there are no instantiation restrictions at all, neither non-local nor local ones. This shows that the calculation of the conditional contribution of cc-conditionals does not cover enough cases to be practical. We therefore leave this proposition without further example.

6.4 Summary

One of the goals of this thesis as described in section 3.1 was to find a method for the calculation of CSs, which we named $\gcalc$ . In this chapter we tried to find a constructive definition of $\gcalc$ for the calculation of conditional contributions (i.e. not the full CS) of atomic conditionals. But these restrictions were not sufficient - in practice we needed to drop most of the cc-conditionals and avoid all non-local instantiation restrictions within ca-conditionals. We see these limitations as too restrictive to regard the method introduced as useful in any practical case.

But the calculation of conditional contributions holds also another, maybe even bigger problem. Due to its nature it does not correlate the calculated vf-pairs and conditional impacts to any possible world or equivalence class of possible worlds. Due to the limitations shown in chapter 3 and also due to the importance of the equivalence classes of possible worlds for e.g. the GIS algorithm as defined in [5] it seems currently unlikely that a calculation which results in only a conditional contribution with no relation to the possible worlds will be helpful in practical cases.

Nevertheless, the theoretical tools which were developed in order to investigate the calculation of conditional structures brought up an alternative possible method for efficient generation of CSs, which we will introduce in the upcoming chapters and which avoids at least some of the downsides of the pure calculation method.

6.5 Excursion: Addition of Maximum Ordered Sums

In this section we will show that the sums of maximum ordered sums cannot be calculated in a straight forward way.

In the reduced vf truth table of example 31 the sum for $\omega^a_{(1,2)}$ as shown in the last column can be calculated by adding up the MOSs of the two a-segments, so that $[2] + [2] = 2[2]$ . It is tempting to assume that this additivity of the MOSs of atomic conditionals would hold in general for any type of ca-conditionals.

On the other hand we see in the reduced vf truth table in example 33 that the summation of the canonical a-segments is not as straight forward as expected. For example when looking at the composed a-segment $\omega^a_{(1,2)}$ , the sum of its canonical a-segments $\omega^a_{(1)}$ and $\omega_{(2)}$ results in $[1] + [1] = [2]$ , which is the same for the composed a-segments $\omega^a_{(1,3)}$ and $\omega^a_{(2,3)}$ . But this does not hold for the composed a-segment $\omega^a_{(1,2,3)}$ where $[1] + [1] + [2] = 2[2]$ .

This behavior is found in many examples. It is clear that the different types of sums occur due to the different types of instantiation restrictions. Therefore a straight-forward method for summing up MOSs therefore seems not to exist.

Nevertheless we can state a finding for the case where no non-local instantiation restrictions are involved.

Proposition 16 (Addition of Maximum Ordered Sums for CA-Conditionals Without Non-Local Instantiation Restrictions)

Let $\Rca$ be a ca-conditional which is free of non-local instantiation restrictions.

Let $\omega^a_{(i_1,\cdots,i_l)}$ with $l>1$ be an a-segment of $\Rca$ , which is not a canonical a-segment of $\Rca$ . Let $[\omega^a_{(i_1,\cdots,i_l)}]$ be the MOS of $\omega^a_{(i_1,\cdots,i_l)}$ . Let $[\omega^a_{(1)}]$ be the MOS generated by a canonical a-segment of $\Rca$ .

It is $[\omega^a_{(i_1,\cdots,i_l)}] = l\cdot [\omega^a_{(1)}]$ .

Proof

The proposition follows immediately from the proof of proposition 14.□

For the rest of this thesis we will not further try to find rules for the addition of MOSs.