Power Logics

When we don’t know what things mean

Jan Jaspars Easter, 1999

Abstract

Modeling human reasoning requires representation of underspecified information, i.e., information which cannot precisely be specified by a single logical description. The question arises what the underlying logic is of multiple logical interpretations. Power logics! But how? I discuss and investigate different possibilities (happy ending included).

Contents

1 Introduction 2 2 Quantified power logics 3 3 Partial power logics 4 4 Conclusions and reflections 6

1 Introduction

The interpretation of human reasoning requires representation of information which may have no precise logical meaning. Many formalisms in artificial intelligence and linguistics “postpone” this problem by using an interlingua between the actual information and its logical interpretation. The inevitable consequence of this approach in combination of the expressivity of human reasoning is that such theories focus merely on the representation task and how we can resolve the different possible logical readings once such representation has been stipulated.

¿From the logical point of view the question arises how we can define inferential structure for such representation languages, which would reflect the reasoning of agents accustomed to underspecified information. A first step towards the implementation of such logical structure is to find an appropriate setting for reasoning with multiple propositions, i.e., a logical structure over the powerset of standard logical languages: power logics. In this essay we investigate such logics without incorporating representation languages.

Minimal desiderata What are the properties which we may expect from a power logic representing the reading sets of underspecified information? The most obvious requirement is that a power logic restricted to singletons should be the same as the base logic that we impose the power construction on. Moreover, a power logic should preserve the basic structure of the base logic, i.e., the general rules of the base logic which do not depend on specific syntactic constructions.

But which properties should we hold on to when we consider the additional structure of sets that we obtain by the power construction? A simple requirement is that if we have a disjunction ∨ in the base logic available, and φ and ψ are two formulas of this languages, then {φ, ψ} ⊢ {φ ∨ ψ} should at least be valid. The converse of this property is certainly something unwanted, and shows that defining underspecification as a disjunction of readings is not correct. On the other hand, the conjunction of readings of an expression should be sufficient to derive the set of readings.

These two properties for sets of formulas can be described without connectives by means of the following rules:

\frac{Θ ⊢ Φ Θ ⊢ Ψ}{Θ ⊢ Φ ∪ Ψ}  \frac{Φ ⊢ Θ Ψ ⊢ Θ}{Φ ∪ Ψ ⊢ Θ}

We call them ambiguation rules, since in the conclusion sets are extended.

Conventions A serious limitation in this essay, is that we only show logics for the finite part of power logics, i.e., the logic of finite sets of formulas (fsfs). The reason is merely technical, since the inheritance of metatheoretical properties depends on this restriction.

In the remainder of this essay we use the following notation. Roman capitals A, B, … printed in boldface represent sets of fsfs, Greek capitals Φ, Ψ, Θ, … represent fsfs, and small Greek letters φ, ψ, … represent formulas of the base logic.

We presume that the base logic has a well-defined semantics, and a standard Tarskian notion of validity. For every formula φ there exists a class of models [φ], and φ ⊧ ψ whenever [φ] ⊆ [ψ], with a standard generalization for sets of formulae Γ ⊧ Δ iff ⋂_{γ∈Γ}[γ] ⊆ ⋃_{δ∈Δ}[δ]. Moreover, we assume that the base logic has a complete Gentzen style axiomatization B: Φ ⊢_{B} Ψ iff Φ ⊧ Ψ. Furthermore, we only accept base logics which contains the normal structural rules.

The first two desiderata mentioned above, entails that a power logic inherits the base logic for singletons and contains the normal structural rules as displayed in Table 1.

2 Quantified power logics

A quantified power logic is a logic whose entailment is defined by the quantity of individual entailments between the readings sets of ambiguous premise and conclusion.^{1}The safest and most simple candidate is to take this quantity universal: Φ ⊧_{∀} Ψ iff ∀φ ∈ Φ∀ψ ∈ Ψ : φ ⊧ ψ. This logic can be completely axiomatized (given the completeness of the underlying logic) by means of the ambiguation rules as given in Section 1. The problem is that one important structural rule is lost: start, that is, the logic is no longer reflexive: Φ |̸=_{∀} Φ.

Structural quantified power logics Quantified power logics which preserve structural rules can be obtained by mixing universal and existantial quantification. Such powerlifting techniques originate from domain theory, where power constructions are used as a semantics of nondeterministic computation. The three important definitions are the so-called Hoare-, Smythe- and Plotkinconstruction. In Table 2 complete axiomatizations are given for those structural power logics.

Implementation of the first would take a conclusion to be valid if for every reading of the premises a reading of the conclusion can be given such that it holds in the base logic: Φ ⊧_{H} Ψ iff ∀φ ∈ Φ∃ψ ∈ Ψ : φ ⊧ ψ. This logic is structural and obeys the ambiguation rules. But, it is too strong, we obtain an additional extension rule for conclusions: Φ ⊢_{H} Ψ ⇒ Φ ⊢_{H} Ψ ∪ Ψ′. This rule

Table 1: Standard rules for power logics is intuitively incorrect since Ψ ∪ Ψ′ is less stable as a conclusion then Ψ. For example, {φ} ⊢_{H} {φ, ψ}.

1For a systematic linguistic discussion of these quantified logics, see [3].

\frac{A ∩ B ≠ ∅}{A ⊢ B} start \frac{A, Φ ⊢ B A′ ⊢ Φ, B′}{A, A′ ⊢ B, B′}  cut \frac{A ⊢ B}{A, A′ ⊢ B} l-mon  \frac{A ⊢ B}{A ⊢ B, B′}  r-mon

The Smythe construction is defined by switching conclusion and premise in the Hoare construction. Every reading of the conclusion is entailed by some reading of the premise. Again we obtain all the minimal desiderata, but in this case we have free extensions of sets on the premise side: Φ ⊢_{S} Ψ ⇒ Φ∪Φ′ ⊢_{S} Ψ, which is again too strong.

The most interesting is the Plotkin construction, the conjunction of the two others. Again it meets our minimal desiderata, but still we get more than we want: Φ ⊢_{P} Ψ & Φ′ ⊢_{P} Ψ′ ⇒ Φ ∪ Φ′ ⊢_{P} Ψ ∪ Ψ′. But does it hurt? Yes, it does: the left hand side may mean something in Φ and the right hand side may mean something in Ψ′, and therefore could be incorrect.

Completeness of the quantified power logics The quantified power logics are very closely connected to their base logics. If the base logic is complete, then addition of the structural rules and the rules given in Table 2 yield complete axiomatization for these different definitions of power entailment.

As an illustration, consider P, and say that Φ ⊧_{P} Ψ, which means, in combination with the completeness of the base logic, that for all φ ∈ Φ and ψ ∈ Ψ there exists φ′ ∈ Φ and ψ′ ∈ Ψ such that {φ} ⊢_{P} {ψ′} and {φ′} ⊢_{P} {ψ}. From the former, by a number (#Φ) of applications of the rule lr-amb, we derive Φ ⊢_{P} Ψ′ for some subset Ψ′ of Ψ, while from the latter we obtain in the same manner Φ′ ⊢_{P} Ψ for certain Φ′ ⊆ Φ. Yet a final application of lr-amb of these two results establishes Φ ⊢_{P} Ψ.

3 Partial power logics

Another approach to settle a notion of valid reasoning over sets of readings is to assign meaning (models) to such sets in a partial fashion,^{2}. If the members of a set agree on truth-values with respect to a given model, we assign this value

Table 2: Additional rules for structural quantified power logics

2For an extensive discussion on the use of partial logic in the context of representation of underspecified information, see [10]. The partial evaluation chosen here originates from [1].

H  \frac{A, Φ ⊢ B}{A, Φ ∪ Ψ ⊢ B}  l-ext \frac{A ⊢ Φ, B A′ ⊢ Ψ, B′}{A, A′ ⊢ Φ ∪ Ψ, B, B′} r-amb

S \frac{A, Φ ⊢ B A′, Ψ ⊢ B′}{A, A′, Φ ∪ Ψ ⊢ B, B′} l-amb  \frac{A ⊢ Φ, B}{A ⊢ Φ ∪ Ψ, B}  r-ext

P  \frac{A, Φ ⊢ Ψ, B A, Φ′ ⊢ Ψ′, B′}{A, A′, Φ ∪ Φ′ ⊢ Ψ ∪ Ψ′, B, B′} lr-amb

\frac{A, Φ ∪ Ψ ⊢ B A′ ⊢ Φ′ ∪ Ψ′, B′}{A, A′, Φ ∪ −Ψ′ ⊢ Φ′ ∪ −Ψ, B, B′} lr − with Ψ, Ψ not empty
\frac{A, Φ ⊢ B}{A − −Φ ⊢ B}  l −− \frac{A, Φ ⊢ B}{A ⊢ − − Φ, B} r −−

Table 3: Additional rules for the double barreled power logic Q2

to the full set:[Φ] = ⋂_{φ∈Φ}[φ]. A straightforward copy of standard entailment ([Φ] ⊆ [Ψ]) would then treat a set of readings as their conjunction.

Double barreled power logic In order to circumvent this problem we need to strengthen the entailment relation. A possible candidate is to consider the negative interpretation of a fsf Φ as well, that is, the models which do not support any of its readings: [Φ]^{−} = ⋂_{φ∈Φ}[φ]^{−}, with [φ]^{−} being the complement of [φ]. A standard strengthening of straight entailment of partial logic is the double barreled entailment. In sequential format this entailment relation looks as follows.

A ⊧_{2} B ⇔ ⋂_{Φ∈A}[Φ] ⊆ ⋃_{Ψ∈B}[Ψ] and ⋂_{Ψ∈B}[Ψ]^{−} ⊆ ⋃_{Φ∈A}[Φ]^{−}

The logic satisfies the minimal desiderata and violates the extension rules which we have seen for quantified power logics.^{3} But again, we need additional strength. In this case not only logical rules have to be added, but also additional expressivity is needed: negative interpretation in the double barreled definition requires explicit syntactic means to establish completeness. If we define [−Φ] = [Φ]^{−} and [−Φ]^{−} = [Φ],^{4} then a complete calculus, Q2, can be obtained by means of the rules in Table 3 together with the rules of the logic P.

Besides the earlier obligation against the rule lr amb, lr − is also problematic. One can derive from this rules that Φ ∪ −Φ ⊢_{Q2} Ψ ∪ −Ψ, which represents the fact that every expression with mutually contradictory readings, entails every other expression of this form.

On the other hand, negative interpretation cannot be used as a plain negation, since Φ ∪ Ψ, −Φ ⊬_{Q2} Ψ. In other words, the status of negative interpretation, dominantly present in the calculus, is pretty unclear.

Context-dependent partial power logics The double barreled technique is not needed if we take the interpretation of underspecified information to be context-sensitive. Instead of taking all readings into account we use situations or contexts in which certain readings may be eliminated.^{5}

3For an extensive survey on double barreled power logic, see [4].

4Additional to this interpretation we need to specify the meaning of ∪ again: [Φ ∪ Ψ] = [Φ]∩[Ψ] and [Φ∪Ψ]^{−} = [Φ]^{−} ∩[Ψ]^{−}. This means that ∪ coincides with Blamey’s interjunction in partial logic [2].

5The difference with the definition of stage in [6] is that here only disambiguation is contextdependent. In [6] also entailment is taken to be context-sensitive. The original idea to define

\frac{A_{1}, \{φ_{1}\} ⊢ B_{1} … A_{n}, \{φ_{n}\} ⊢ B_{n}}{A_{1}, …, A_{n}, \{φ_{1}, …, φ_{n}\} ⊢ B_{1}, …, B_{n}} n > 0  l-amb-sing
\frac{A_{1} ⊢ \{φ_{1}\}, B_{1} … A_{n} ⊢ \{φ_{n}\}, B_{n}}{A_{1}, …, A_{n} ⊢ \{φ_{1}, …, φ_{n}\}, B_{1}, …, B_{n}} n ≥ 0  r-amb-sing

Table 4: Ambiguation rules for singletons

A partial disambiguation is a function d from fsfs to fsfs such that d(Φ) ⊆ Φ and d(Φ) = ∅ if and only if Φ = ∅ for all fsfs Φ. The relative interpretation [Φ] of a fsf Φ is {⟨M, d⟩ | M ∈ [φ] for all φ ∈ d(Φ)}. The standard notion of entailment yields a logic Q whose additional rules are displayed in Table 4. It comes quite close to the minimal requirements of Section 1. The ambiguation rules are not universally valid, but hold for ambiguation of singletons.

It is not very hard to find appropriate restrictions on the class of partial disambiguations to regain the ambiguation rules, without getting additional unwanted rules.

A partial disambiguation d is called left-monotonic iff d(Φ) ⊆ d(Φ ∪ Ψ) or d(Ψ) ⊆ d(Φ ∪ Ψ) for all fsfs Φ and Ψ. A partial disambiguation d is rightmonotonic iff d(Φ ∪ Ψ) ⊆ d(Φ) ∪ d(Ψ) for all fsfs Φ and Ψ. Left-monotonicity can be axiomatized by adding l-amb to the system above, whereas rightmonotonicity corresponds in the same manner to r-amb. Moreover, the combination of the two gives a logic which exactly corresponds to the logic of Section 1.

The requirements of monotonicity are quite intuitive. They represent structure on the process of getting more certain about the meaning of an ambiguous expression. The left variant tells us that if we seperate two reading sets that at least one of these sets should count as a further specification. Right monotonicity says that if an expression is partially disambiguated then the result is better (or the same) as when partial disambiguation takes place after the expression has been assigned two possible readings in the original language with ambiguous information.^{6}

4 Conclusions and reflections

Starting from ordinary logic, the first step towards direct deduction on underspecified information requires logics for sets of formulas. In this short survey we have shown how a minimal calculus can be defined for a power logic which contains ordinary structural rules, straightforward ambiguation rules, and which is completeness preserving when we combine it with the base logic as the logic of the singletons of the power logic.

It may be argued that an underspecification representation language not always have full expressivity over finite sets. Nevertheless, it can be proven that most of the results can be obtained for any such language describing a limited range of finite reading sets [7].

entailment relative to disambiguation stems from [11].

6In [8] the reader finds some additional strengthenings of partial disambiguations and corresponding rules. The completeness proof for these calculi and Q2 can be found there.

Recently, different authors have suggested to use a ‘double logical’ approach to underspecification (see for example [9], this volume). In this approach the specifications of the base logic are the models of the underspecified descriptions. The ∪-rules in this survey correspond to the rules for a disjunction in the underspecification language. If such a disjunction is not present we need to use the techniques as explained in [7].

Additional structure on partial disambiguations may be used for interpretation of more informative underspecification representations. A very interesting enrichment is preferential structure [5], that is ordered sets of readings rather than plain sets. Yet another important enrichment is to consider the process of increasing disambigation by distinguishing states with an associated partial disambiguation. An approach which would bring us into the direction of dynamic power logics. Last but not least, additional epistemic structure is an important direction. In the setting of the logic Q, partial disambiguations represent states of knowledge, but evaluation is still related to a total outer world, while permission of uncertainty on this level, for example, by introducing multiple possible worlds, may lead to more ‘realistic’ logics.

References

[1] H. Alshawi and R. Crouch. Monotonic semantic interpretation. In Proc. of the 30-th ACL, pages 32–38, Kyoto, 1992.

[2] S. Blamey. Partial logic. In Handbook of Philosophical Logic, part 3, pages 1–70, Dordrecht, 1986. Reidel.

[3] K. van Deemter. Towards a logic of ambiguous expressions. In Semantic Ambiguity and Underspecification, pages 203–238, Stanford, 1995. CSLI.

[4] J. van Eijck and J. Jaspars. Ambiguity and reasoning. Technical Report CS-9616, CWI, 1996.

[5] T. Fernando. Non-monotonic consequences of preferential disambiguation. In Proc. of the 10th Amsterdam Colloquium, pages 243–262. ILLC, 1996.

[6] T. Fernando. A modal logic for non-deterministic disambiguation. In Proc. of the 11th Amsterdam Colloquium, pages 121–126. ILLC, 1997.

[7] J. Jaspars. Structural logics for reasoning with underspecified representations. Extended

    abstract, available from: http://www.wins.uva.nl/~ jaspars/sb/.

[8] J. Jaspars. Minimal logics for reasoning with ambiguous expressions. Technical Report 94, University of Saarland, 1997.

[9] R. Muskens. Talking about trees and truth-conditions. In This volume. ILLC, 1999.

[10] M. Pinkal. Logic and Lexicon: The Semantics of the Indefinite. Kluwer, Dordrecht, 1995.

[11] U. Reyle. On reasoning with ambiguities. In Proc. of the EACL, Dublin, 1995.