# Propositional Independence: Formula-Variable Independence And Forgetting

LANG@IRIT_FR
LIBERATO@DIS. UNIRO MA 1. IT
MARQUIS@CRIL. UNIV-ARTOIS.FR

## Abstract

Independence - the study of what is relevant to a given problem of reasoning - has received an increasing attention from the AI community. In this paper, we consider two basic forms of independence, namely, a syntactic one and a semantic one. We show features and drawbacks of them. In particular, while the syntactic form of independence is computationally easy to check, there are cases in which things that intuitively are not relevant are not recognized as such. We also consider the problem of forgetting, i.e., distilling from a knowledge base only the part that is relevant to the set of queries constructed from a subset of the alphabet. While such process is computationally hard, it allows for a simplification of subsequent reasoning, and can thus be viewed as a form of compilation: once the relevant part of a knowledge base has been extracted, all reasoning tasks to be performed can be simplified.

## 1. Introduction

We successively present some motivations, the scope of the paper, and the contribution and the organization of the paper.

## 1.1 Motivations

In many situations of everyday life, we are confronted with the problem of determining what is relevant. Especially, as a preliminary step to various intelligent tasks (e.g., planning, decision making, reasoning), it is natural and reasonable to discard everything but what is relevant to achieve them efficiently. For instance, before starting to write this paper, we had to consider the relevant literature on the topic, and only it; gathering on our desks all the papers about relevance that we have at hand led us to set away our favourite cook books, because they are of no help to the task of writing this paper. The ability to focus on what is relevant (or dually to discard what is not) can be considered as a central, characteristic feature of intelligence; it is believed that over 90% of the neuronal connections of our brains Jérôme Lang IRIT-UPS, 118 route de Narbonne 31062 Toulouse Cedex, France Paolo Liberatore Dipartimento di Informatica e Sistemistica Universita di Roma "La Sapienza" via Salaria 113, 00198 Roma, Italy Pierre Marquis CRIL-CNRS/Université d'Artois rue de l'Université S.P. 16, 62307 Lens Cedex, France