# Semantics for Possibilistic Disjunctive Programs ††thanks: This is a revised
and improved version of the papers _Semantics for Possibilistic Disjunctive
Programs_ appeared in C. Baral, G. Brewka and J. Schipf (Eds), Ninth
International Conference on Logic Programming and Nonmonotonic Reasoning
(LPNMR-07), LNAI 4483. _Semantics for Possibilistic Disjunctive Logic
programs_ which appears in S. Constantini and W. Watson (Eds), Answer Set
Programming: Advantage in Theory and Implementation.

JUAN CARLOS NIEVES
Universitat Politècnica de Catalunya
Software Department (LSI)
c/Jordi Girona 1-3  E-08034  Barcelona  Spain
<EMAIL_ADDRESS>MAURICIO OSORIO
Universidad de las Américas - Puebla
CENTIA
Sta. Catarina Mártir  Cholula  Puebla  72820 México
<EMAIL_ADDRESS>ULISES CORTÉS
Universitat Politècnica de Catalunya
Software Department (LSI)
c/Jordi Girona 1-3  E-08034  Barcelona  Spain
<EMAIL_ADDRESS>
(March 22, 2011; May 23, 2011)

###### Abstract

In this paper, a possibilistic disjunctive logic programming approach for
modeling uncertain, incomplete and inconsistent information is defined. This
approach introduces the use of possibilistic disjunctive clauses which are
able to capture incomplete information and incomplete states of a knowledge
base at the same time.

By considering a possibilistic logic program as a possibilistic logic theory,
a construction of a possibilistic logic programming semantic based on answer
sets and the proof theory of possibilistic logic is defined. It shows that
this possibilistic semantics for disjunctive logic programs can be
characterized by a fixed-point operator. It is also shown that the suggested
possibilistic semantics can be computed by a resolution algorithm and the
consideration of optimal refutations from a possibilistic logic theory.

In order to manage inconsistent possibilistic logic programs, a preference
criterion between inconsistent possibilistic models is defined; in addition,
the approach of cuts for restoring consistency of an inconsistent
possibilistic knowledge base is adopted. The approach is illustrated in a
medical scenario.

###### keywords:

Answer Set Programming, Uncertain Information, Possibilistic Reasoning.

##  1 Introduction

Answer Set Programming (ASP) is one of the most successful logic programming
approaches in Non-monotonic Reasoning and Artificial Intelligence applications
[Baral (2003), Gelfond (2008)]. In [Nicolas et al. (2006)], a possibilistic
framework for reasoning under uncertainty was proposed. This framework is a
combination between ASP and possibilistic logic [Dubois et al. (1994)].

Possibilistic Logic is based on possibilistic theory in which, at the
mathematical level, degrees of possibility and necessity are closely related
to fuzzy sets [Dubois et al. (1994)]. Due to the natural properties of
possibilistic logic and ASP, Nicolas et al.’s approach allows us to deal with
reasoning that is at the same time _non-monotonic_ and _uncertain_. Nicolas et
al.’s approach is based on the concept of _possibilistic stable model_ which
defines a semantics for _possibilistic normal logic programs_.

An important property of possibilistic logic is that it is _axiomatizable_ in
the necessity-valued case [Dubois et al. (1994)]. This means that there is a
formal system (a set of axioms and inferences rules) such that from any set of
possibilistic fomulæ ${\mathcal{}F}$ and for any possibilistic formula $\Phi$,
$\Phi$ is a logical consequence of ${\mathcal{}F}$ if and only if $\Phi$ is
derivable from ${\mathcal{}F}$ in this formal system. A result of this
property is that the inference in possibilistic logic can be managed by both a
syntactic approach (axioms and inference rules) and a possibilistic model
theory approach (interpretations and possibilistic distributions).

Equally important to consider is that the answer set semantics inference can
also be characterized as _a logic inference_ in terms of the proof theory of
intuitionistic logic and intermediate logics [Pearce (1999), Osorio et al.
(2004)]. This property suggests that one can explore extensions of the answer
set semantics by considering the inference of different logics.

Since in [Dubois et al. (1994)] an axiomatization of possibilistic logic has
been defined, in this paper we explore the characterization of a possibilistic
semantics for capturing possibilistic logic programs in terms of the proof
theory of possibilistic logic and the standard answer set semantics. A nice
feature of this characterization is that it is applicable to _disjunctive as
well as normal possibilistic logic programs_ , and, with minor modification,
to possibilistic logic programs containing a _strong negation operator_.

The use of possibilistic disjunctive logic programs allow us to capture
_incomplete information_ and _incomplete states of a knowledge base_ at the
same time. In order to illustrate the use of possibilistic disjunctive logic
programs, let us consider a scenario in which uncertain and incomplete
information is always present. This scenario can be observed in the process of
_human organ transplanting_. There are several factors that make this process
sophisticated and complex. For instance:

  * •

the transplant acceptance criteria vary ostensibly among transplant teams from
the same geographical area and substantially between more distant transplant
teams [López-Navidad et al. (1997)]. This means that the acceptance criteria
applied in one hospital could be invalid or at least questionable in another
hospital.

  * •

there are lots of factors that make the diagnosis of an organ donor’s disease
in the organ recipient unpredictable. For instance, if an organ donor $D$ has
hepatitis, then an organ recipient $R$ could be infected by an organ of $D$.
According to [López-Navidad and Caballero (2003)], there are cases in which
the infection can occur; however, the recipient can _spontaneously_ clear the
infection, for example hepatitis. This means that an organ donor’s infection
can be _present_ or _non-present_ in the organ recipient. Of course there are
infections which can be prevented by treating the organ recipient post-
transplant.

  * •

the clinical state of an organ recipient can be affected by several factors,
for example malfunctions of the graft. This means that the clinical state of
an organ recipient can be _stable_ or _unstable_ after the graft because the
graft can have _good graft functions_ , _delayed graft functions_ and
_terminal insufficient functions_ 111Usually, when a doctor says that an organ
has _terminally insufficient functions_ , it means that there are no clinical
treatments for improving the organ’s functions..

It is important to point out that the transplant acceptance criteria rely on
the kind of organ (kidney, heart, liver, _etc._) considered for transplant and
the clinical situation of the potential organ recipients.

Let us consider the particular case of a kind of kidney transplant with organ
donors who have a kind of infection, for example: endocarditis, hepatitis. As
already stated, the clinical situation of the potential organ recipients is
relevant in the organ transplant process. Hence the clinical situation of an
organ recipient is denoted by the predicate $cs(t,T)$, such that $t$ can be
_stable_ , _unstable_ , 0-_urgency_ and $T$ denotes a moment in time. Another
important factor, that is considered, is the state of the organ’s functions.
This factor is denoted by the predicate $o(t,T)$ such that $t$ can be
_terminal-insufficient functions_ , _good-graft functions_ , _delayed-graft
functions_ , _normal-graft functions_ and $T$ denotes a moment in time. Also,
the state of an infection in both the organ recipient and the organ donor are
considered, these states are denoted by the predicates $r\\_inf(present,T)$
and $d\\_inf(present,T)$ respectively so that $T$ denotes a moment in time.
The last predicate that is presented is $action(t,T)$ such that $t$ can be
_transplant_ , _wait_ , _post-transplant treatment_ and $T$ denotes a moment
in time. This predicate denotes the possible actions of a doctor. In Figure
1222This finite state automata was developed under the supervision of
Francisco Caballero M. D. Ph. D. from the Hospital de la Santa Creu I Sant
Pau, Barcelona, Spain., a finite state automata is presented. In this
automata, each node represents a possible situation where an organ recipient
can be found and the arrows represent the doctor’s possible actions. Observe
that we are assuming that in the initial state the organ recipient is
clinically stable and he does not have an infection; however, he has a kidney
whose functions are terminally insufficient. From the initial state, the
doctor’s actions would be either to perform a kidney transplantat or just
wait333In the automata of Figure 1, we are not considering the possibility
that there is a waiting list for organs. This waiting list has different
policies for assigning an organ to an organ recipient..

Figure 1: An automata of states and actions for considering infections in
kidney organ transplant.

According to Figure 1, an organ recipient could be found in different
situations after a graft. The organ recipient may require another graft and
the state of the infection could be unpredictable. This situation makes the
automata of Figure 1 nondeterministic. Let us consider a couple of extended
disjunctive clauses which describe some situations presented in Figure 1.

$r\\_inf(present,T2)\vee\lnot r\\_inf(present,T2)$ $\leftarrow$
$action(transplant,T),$
---
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}d\\_inf(present,T),T2=T+1.$
$o(good\\_graft\\_funct,T2)\vee o(delayed\\_graft\\_funct,T2)\vee$
$o(terminal\\_insufficient\\_funct,T2)\leftarrow action(transplant,T),T2=T+1.$

As syntactic clarification, we want to point out that $\lnot$ is regarded as a
_strong negation_ which is not exactly the negation in classical logic. In
fact, any atom negated by strong negation will be replaced by a new atom as it
is done in ASP. This means that $a\vee\lnot a$ cannot be regarded as a logic
tautology.

Continuing with our medical scenario, we can see that the intended meaning of
the first clause is that if the organ donor has an infection, then the
infection can be _present_ or _non-present_ in the organ recipient after the
graft, and the intended meaning of the second one is that the graft’s
functions can be: _good_ , _delayed_ and _terminal_ after the graft. Observe
that these clauses are not capturing the uncertainty that is involved in each
statement. For instance, w.r.t. the first clause, one can wish to attach an
degree of uncertainty in order to capture the uncertainty that is involved in
this statement — keeping in mind that the organ recipient can be infected by
the infection of the donor’s organ; however, the infection can be
_spontaneously_ cleared by the organ recipient as it is the case of hepatitis
[López-Navidad and Caballero (2003)].

In logic programming literature, one can find different approaches for
representing uncertain information [Kifer and Subrahmanian (1992), Ng and
Subrahmanian (1992), Lukasiewicz (1998), Kern-Isberner and Lukasiewicz (2004),
van Emden (1986), Rodríguez-Artalejo and Romero-Díaz (2008), Van-Nieuwenborgh
et al. (2007), Fitting (1991), Lakshmanan (1994), Baldwin (1987), Dubois et
al. (1991), Alsinet and Godo (2002), Alsinet and Godo (2000), Alsinet et al.
(2008), Nicolas et al. (2006)]. Basically, these approaches differ in the
underlying notion of uncertainty and how uncertainty values, associated with
clauses and facts, are managed. Usually the selection of an approach for
representing uncertain information relies on the kind of information which has
to be represented. In psychology literature, one can find significant
observations related to the presentation of uncertain information. For
instance, Tversky and Kahneman have observed in [Tversky and Kahneman (1982)]
that people commonly use statements such as “ _I think that_ $\dots$”, “
_chances are_ $\dots$”, “ _it is probable that_ $\dots$”, “ _it is plausible
that_ $\dots$”, _etc._ , for supporting their decisions. In fact, many times,
experts in a domain, such as medicine, appeal to their intuition by using
these kinds of statements [Fox and Das (2000), Fox and Modgil (2006)]. One can
observe that these statements have adjectives which quantify the information
as a common denominator. These adjectives are for example: _probable_ ,
_plausible_ , _etc_. This suggests that the consideration of labels for the
_syntactic representation of uncertain values_ could help represent uncertain
information pervaded by ambiguity.

Since possibilistic logic defines a proof theory in which the strength of a
conclusion is the strength of the weakest argument in its proof, the
consideration of an ordered set of labels for capturing incomplete states of a
knowledge base is feasible. The only formal requirement is that this set of
adjectives/labels must be a finite set. For instance, for the given medical
scenario, a transplant coordinator444A transplant coordinator is an expert in
all of the processes of transplants [López-Navidad et al. (1997)]. can suggest
a set of labels in order to quantify a medical knowledge base and, of course,
to define an order between those labels. By considering those labels, we can
have possibilistic clauses as:

probable: $r\\_inf(present,T2)\vee\lnot r\\_inf(present,T2)$ $\leftarrow$
$action(transplant,T),$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}d\\_inf(present,T),T2=T+1.$

Informally speaking, the reading of this clause is: _it is _probable_ that if
the organ donor has an infection, then the organ recipient can be infected or
not after a graft._

As we can see, possibilistic programs with _negation as failure_ represent a
rich class of logic programs which are especially adapted to automated
reasoning when the available information is pervaded by ambiguity.

In this paper, we extend the work of two earlier papers [Nieves et al.
(2007a), Nieves et al. (2007b)] in order to obtain a simple logic
characterization of a possibilistic logic programming semantics for capturing
possibilistic programs; this semantics is applicable to disjunctive as well as
normal logic programs. As we have already mentioned, the construction of the
possibilistic semantics is based on the proof theory of possibilistic logic.
Following this approach:

  * •

We define the inference $\Vvdash_{PL}$. This inference takes as references the
standard definition of the answer set semantics and the inference
$\vdash_{PL}$ which corresponds to the inference of possibilistic logic.

  * •

The possibilistic semantics is defined in terms of a syntactic reduction,
$\Vvdash_{PL}$ and the concept of _i-greatest set_.

  * •

Since the inference of possibilistic logic is computable by a generalization
of the classical resolution rule, it is shown that the defined possibilistic
semantics is computable by inferring optimal refutations.

  * •

By considering _the principle of partial evaluation_ , it is shown that the
given possibilistic semantics can be characterized by a possibilistic partial
evaluation operator.

  * •

Finally, since the possibilistic logic uses $\alpha$_-cuts_ to manage
inconsistent possibilistic knowledge bases, an approach of cuts for restoring
consistency of an inconsistent possibilistic knowledge base is adopted.

The rest of the paper is divided as follows: In §2 we give all the background
and necessary notation. In §3, the syntax of our possibilistic framework is
presented. In §4, the semantics for capturing the possibilistic logic programs
is defined. Also it is shown that this semantics is computable by considering
a possibilistic resolution rule and partial evaluation. In §5, some criteria
for managing inconsistent possibilistic logic programs are defined. In §6, we
present a small discussion w.r.t. related approaches to our work. Finally, in
the last section, we present our conclusions and future work.

##  2 Background

In this section we introduce the necessary terminology and relevant
definitions in order to have a self-contained document. We assume that the
reader is familiar with basic concepts of _classic logic_ , _logic
programming_ and _lattices_.

###  2.1 Lattices and order

We start by defining some fundamental definitions of lattice theory (see
[Davey and Priestly (2002)] for more details).

###### Definition 1

Let ${\mathcal{}Q}$ be a set. An order (or partial order) on ${\mathcal{}Q}$
is a binary relation $\leq$ on ${\mathcal{}Q}$ such that, for all
$x,y,z\in{\mathcal{}Q}$,

(i)

$x\leq x$

(ii)

$x\leq y$ and $y\leq x$ imply $x=y$

(iii)

$x\leq y$ and $y\leq z$ imply $x\leq z$

These conditions are referred to, respectively, as reflexivity, antisymmetry
and transitivity.

A set ${\mathcal{}Q}$ equipped with an order relation $\leq$ is said to be an
ordered set (or partial ordered set). It will be denoted by
(${\mathcal{}Q}$,$\leq$).

###### Definition 2

Let (${\mathcal{}Q}$,$\leq$) be an ordered set and let
$S\subseteq{\mathcal{}Q}$. An element $x\in{\mathcal{}Q}$ is an upper bound of
$S$ if $s\leq x$ for all $s\in S$. A lower bound is defined dually. The set of
all upper bounds of $S$ is denoted by $S^{u}$ (read as ‘$S$ upper’) and the
set of all lower bounds by $S^{l}$ (read as ‘$S$ lower’).

If $S^{u}$ has a minimum element $x$, then $x$ is called the least upper bound
(${\mathcal{}LUB}$) of $S$. Equivalently, $x$ is the least upper bound of $S$
if

(i)

$x$ is an upper bound of $S$, and

(ii)

$x\leq y$ for all upper bound $y$ of $S$.

The least upper bound of $S$ exists if and only if there exists
$x\in{\mathcal{}Q}$ such that

$(\forall y\in{\mathcal{}Q})[((\forall s\in S)s\leq y)\Longleftrightarrow
x\leq y],$

and this characterizes the ${\mathcal{}LUB}$ of $S$. Dually, if $S^{l}$ has a
greatest element, $x$, then $x$ is called the greatest lower bound
(${\mathcal{}GLB}$) of $S$. Since the least element and the greatest element
are unique, ${\mathcal{}LUB}$ and ${\mathcal{}GLB}$ are unique when they
exist.

The least upper bound of $S$ is called the supremum of $S$ and it is denoted
by $sup~{}S$; the greatest lower bound of S is called the infimum of S and it
is denoted by $inf~{}S.$

###### Definition 3

Let (${\mathcal{}Q}$,$\leq$) be a non-empty ordered set.

(i)

If $sup\\{x,y\\}$ and $inf\\{x,y\\}$ exist for all $x,y\in{\mathcal{}Q}$, then
${\mathcal{}Q}$ is called lattice.

(ii)

If $sup~{}S$ and $inf~{}S$ exist for all $S\subseteq{\mathcal{}Q}$, then
${\mathcal{}Q}$ is called a complete lattice.

###### Example 1

Let us consider the set of labels ${\mathcal{}Q}:=\\{Certain$, $Confirmed,$
$Probable,$ $Plausible,$ $Supported,$ $Open\\}$555This set of labels was taken
from [Fox and Modgil (2006)]. In that paper, the authors argue that we can
construct a set of labels (they call those: _modalities_) in a way that this
set provides a simple scale for ordering the claims of our beliefs. We will
use this kind of labels for quantifying the degree of uncertainty of a
statement. and let $\preceq$ be a partial order such that the following set of
relations holds: $\\{Open\preceq Supported$, $Supported\preceq Plausible$,
$Supported\preceq Probable$, $Probable\preceq Confirmed$, $Plausible\preceq
Confirmed$, $Confirmed\preceq Certain\\}$. A graphic representation of $S$
according to $\preceq$ is showed in Figure 2. It is not difficult to see that
$({\mathcal{}Q},\preceq)$ is a lattice and further it is a complete lattice.

Figure 2: A graphic representation of a lattice where the following relations
holds: $\\{Open\preceq Supported$, $Supported\preceq Plausible$
$Supported\preceq Probable$, $Probable\preceq Confirmed$, $Plausible\preceq
Confirmed$ , $Confirmed\preceq Certain\\}$.

###  2.2 Logic programs: Syntax

The language of a propositional logic has an alphabet consisting of

(i)

proposition symbols: $\bot,p_{0},p_{1},...$

(ii)

connectives : $\vee,\wedge,\leftarrow,\lnot,\;not$

(iii)

auxiliary symbols : ( , )

in which $\vee,\wedge,\leftarrow$ are binary-place connectives, $\lnot$, $not$
are unary-place connective and $\bot$ is zero-ary connective. The proposition
symbols and $\bot$ stand for the indecomposable propositions, which we call
atoms, or atomic propositions. Atoms negated by $\lnot$ will be called
_extended atoms_.

###### Remark 1

We will use the concept of atom without paying attention to whether it is an
extended atom or not.

The negation sign $\lnot$ is regarded as the so called _strong negation_ by
the ASP’s literature and the negation $not$ as the _negation as failure_. A
literal is an atom, $a$, or the negation of an atom $not\;a$. Given a set of
atoms $\\{a_{1},...,a_{n}\\}$, we write $not\;\\{a_{1},...,a_{n}\\}$ to denote
the set of literals $\\{not\;a_{1},...,not\;a_{n}\\}.$ An extended disjunctive
clause, C, is denoted:

$a_{1}\vee\ldots\vee a_{m}\leftarrow
a_{m+1},\dots,a_{j},not\;a_{j+1},\dots,not\;a_{n}$

in which $m\geq 0$, $n\geq 0$, $m+n>0$, each $a_{i}$ is an atom666Notice that
these atoms can be _extended atoms_.. When $n=0$ and $m>0$ the clause is an
abbreviation of $a_{1}\vee\ldots\vee a_{m}\leftarrow$; clauses of these forms
are some times written just as $a_{1}\vee\ldots\vee a_{m}$. When $m=0$ the
clause is an abbreviation of:

$\leftarrow a_{1},\dots,a_{j},not\;a_{j+1},\dots,not\;a_{n}$

Clauses of this form are called constraints (the rest, non-constraint
clauses). An extended disjunctive program $P$ is a finite set of extended
disjunctive clauses. By ${\mathcal{}L}_{P}$, we denote the set of atoms in the
language of $P$.

Sometimes we denote an extended disjunctive clause C by
${\mathcal{}A}\leftarrow{\mathcal{}B}^{+},\ not\;{\mathcal{}B}^{-}$,
${\mathcal{}A}$ contains all the head literals, ${\mathcal{}B}^{+}$ contains
all the positive body literals and ${\mathcal{}B}^{-}$ contains all the
negative body literals. When ${\mathcal{}B}^{-}=\emptyset$, the clause is
called positive disjunctive clause. A set of positive disjunctive clauses is
called a positive disjunctive logic program. When ${\mathcal{}A}$ is a
singleton set, the clause can be regarded as a normal clause. A normal logic
program is a finite set of normal clauses. Finally, when ${\mathcal{}A}$ is a
singleton set and ${\mathcal{}B}^{-}=\emptyset$, the clause can also be
regarded as a definite clause. A finite set of definite clauses is called a
definite logic program.

We will manage the strong negation ($\neg$), in our logic programs, as it is
done in ASP [Baral (2003)]. Basically, each extended atom $\neg a$ is replaced
by a new atom symbol $a^{\prime}$ which does not appear in the language of the
program. For instance, let $P$ be the normal program:

$a\leftarrow q$. |  |  $q$.
---|---|---
$\lnot q\leftarrow r$. |  |  $r$.

Then replacing each extended atom by a new atom symbol, we will have:

$a\leftarrow q$. |  |  $q$.
---|---|---
$q^{\prime}\leftarrow r$. |  |  $r$.

In order not to allow models with complementary atoms, that is $q$ and $\lnot
q$, a constraint of the form $\leftarrow q,q^{\prime}$ is usually added to the
logic program. In our approach, this constraint can be omitted in order to
allow models with complementary atoms. In fact, the user could add/omit this
constraint without losing generality.

Formulæ are constructed as usual in classic logic by the connectives:
$\vee,\wedge,\leftarrow,\sim,\bot$. A theory $T$ is a finite set of formulæ.
By ${\mathcal{}L}_{T}$, we denote the set of atoms that occur in _T_. When we
treat a logic program as a theory,

  * •

each negative literal $not\;a$ is replaced by $\sim a$ such that $\sim$ is
regarded as the negation in classic logic.

  * •

each constraint $\leftarrow a_{1},\dots,a_{j},not\;a_{j+1},\dots,not\;a_{n}$
is rewritten according to the formula $a_{1}\wedge\dots\wedge a_{j}\wedge\sim
a_{j+1}\wedge\dots\wedge\sim a_{n}\rightarrow\bot$.

Given a set of proposition symbols $S$ and a theory $\Gamma$ in a logic $X$.
If $\Gamma\vdash_{X}S$ if and only if $\forall s\in S$ $\Gamma\vdash_{X}s$.

###  2.3 Interpretations and models

In this section, we define some relevant concepts w.r.t. semantics. The first
basic concept that we introduce is _interpretation_.

###### Definition 4

Let $T$ be a theory, an interpretation $I$ is a mapping from
${\mathcal{}L}_{T}$ to $\\{0,1\\}$ meeting the conditions:

  1. 1.

$I(a\wedge b)=min\\{I(a),I(b)\\}$,

  2. 2.

$I(a\vee b)=max\\{I(a),I(b)\\}$,

  3. 3.

$I(a\leftarrow b)=0$ if and only if $I(b)=1$ and $I(a)=0$,

  4. 4.

$I(\sim a)=1-I(a)$,

  5. 5.

$I(\bot)=0$.

It is standard to provide interpretations only in terms of a mapping from
${\mathcal{}L}_{T}$ to $\\{0,1\\}$. Moreover, it is easy to prove that this
mapping is unique by virtue of the definition by recursion [van Dalen (1994)].
Also, it is standard to use sets of atoms to represent interpretations. The
set corresponds exactly to those atoms that evaluate to 1.

An interpretation $I$ is called a (2-valued) model of the logic program $P$ if
and only if for each clause $c\in P$, $I(c)=1$. A theory is consistent if it
admits a model, otherwise it is called inconsistent. Given a theory $T$ and a
formula $\varphi$, we say that $\varphi$ is a logical consequence of $T$,
denoted by $T\models\varphi$, if every model $I$ of $T$ holds that
$I(\varphi)=1$. It is a well known result that $T\models\varphi$ if and only
if $T\cup\\{\sim\varphi\\}$ is inconsistent [van Dalen (1994)].

We say that a model $I$ of a theory $T$ is a minimal model if a model
$I^{\prime}$ of $T$ different from $I$ such that $I^{\prime}\subset I$ does
not exist. Maximal models are defined in the analogous form.

###  2.4 Logic programming semantics

In this section, the _answer set semantics_ is presented. This semantics
represents a two-valued semantics approach.

####  2.4.1 Answer set semantics

By using ASP, it is possible to describe a computational problem as a logic
program whose answer sets correspond to the solutions of the given problem. It
represents one of the most successful approaches of non-monotonic reasoning of
the last two decades [Baral (2003)]. The number of applications of this
approach have increased due to the efficient implementations of the answer set
solvers that exist.

The answer set semantics was first defined in terms of the so called _Gelfond-
Lifschitz reduction_ [Gelfond and Lifschitz (1988)] and it is usually studied
in the context of syntax dependent transformations on programs. The following
definition of an answer set for extended disjunctive logic programs
generalizes the definition presented in [Gelfond and Lifschitz (1988)] and it
was presented in [Gelfond and Lifschitz (1991)]: Let _P_ be any extended
disjunctive logic program. For any set $S\subseteq{\mathcal{}L}_{P}$, let
$P^{S}$ be the positive program obtained from _P_ by deleting

(i)

each rule that has a formula $not\;a$ in its body with $a\in S$, and then

(ii)

all formulæ of the form $not\;a$ in the bodies of the remaining rules.

Clearly $P^{S}$ does not contain $not$ (this means that $P^{S}$ is either a
positive disjunctive logic program or a definite logic program), hence _S_ is
called an answer set of _P_ if and only if _S_ is a minimal model of $P^{S}$.
In order to illustrate this definition, let us consider the following example:

###### Example 2

Let us consider the set of atoms $S:=\\{b\\}$ and the following normal logic
program $P$:

$b\leftarrow not\;a$. |  $b$.
---|---
$c\leftarrow not\;b$. |  $c\leftarrow a$.

We can see that $P^{S}$ is:

$b$. |  $c\leftarrow a$.
---|---

Notice that this program has three models: $\\{b\\}$, $\\{b,c\\}$ and
$\\{a,b,c\\}$. Since the minimal model among these models is $\\{b\\}$, we can
say that $S$ is an answer set of $P$.

In the answer set definition, we will normally omit the restriction that if
$S$ has a pair of complementary literals then $S:={\mathcal{}L}_{P}$. This
means that we allow for the possibility that an answer set could have a pair
of complementary atoms. For instance, let us consider the program $P$:

$a$. |  |  $\lnot a$. |  |  $b$.
---|---|---|---|---

then, the only answer set of this program is : $\\{a,\lnot a,b\\}$. In Section
5, the inconsistency in possibilistic programs is discussed.

It is worth mentioning that in literature there are several forms for handling
an inconsistency program [Baral (2003)]. For instance, by applying the
original definition [Gelfond and Lifschitz (1991)] the only answer set of $P$
is: $\\{a,\lnot a,b,\lnot b\\}$. On the other hand, the DLV system [DLV
(1996)] returns no models if the program is inconsistent.

###  2.5 Possibilistic Logic

Since in our approach is based on the proof theory of possibilistic logic, in
this section, we present an axiomation of possibilistic logic for the case of
necessity-valued formulæ.

Possibilistic logic is a weighted logic introduced and developed in the
mid-1980s, in the setting of artificial intelligence, with the goal of
developing a simple yet rigorous approach to automated reasoning from
uncertain or prioritized incomplete information. Possibilistic logic is
especially adapted to automated reasoning when the available information is
pervaded by ambiguities. In fact, possibilistic logic is a natural extension
of classical logic in which the notion of total order/partial order is
embedded in the logic.

Possibilistic Logic is based on _possibility theory_. Possibilistic theory, as
its name implies, deals with the possible rather than probable values of a
variable with possibility being a matter of degree. One merit of possibilistic
theory is at one and the same time to represent imprecision (in the form of
fuzzy sets) and quantity uncertainty (through the pair of numbers that measure
_possibility_ and _necessity_).

Our study in possibilistic logic is devoted to a fragment of possibilistic
logic, in which knowledge bases are only _necessity-quantified_ statements. A
necessity-valued formula is a pair $(\varphi\;\alpha)$ in which $\varphi$ is a
classical logic formula and $\alpha\in(0,1]$ is a positive number. The pair
$(\varphi\;\alpha)$ expresses that the formula $\varphi$ is certain at least
to the level $\alpha$, that is $N(\varphi)\geq\alpha$, in which $N$ is a
necessity measure modeling our possibly incomplete state knowledge [Dubois et
al. (1994)]. $\alpha$ is not a probability (like it is in probability theory),
but it induces a certainty (or confidence) scale. This value is determined by
the expert providing the knowledge base. A necessity-valued knowledge base is
then defined as a finite set (that is to say a conjunction) of necessity-
valued formulæ.

The following properties hold w.r.t. necessity-valued formulæ:

$N(\varphi\wedge\psi)=min(\\{N(\varphi),N(\psi)\\})$ (1)

$N(\varphi\vee\psi)\geq max(\\{N(\varphi),N(\psi)\\})$ (2)

$\text{ if }\varphi\vdash\psi\text{ then }N(\psi)\geq N(\varphi)$ (3)

Dubois et al., in [Dubois et al. (1994)] introduced a formal system for
necessity-valued logic which is based on the following axioms schemata
(propositional case):

(A1)

$(\varphi\rightarrow(\psi\rightarrow\varphi)\;1)$

(A2)

$((\varphi\rightarrow(\psi\rightarrow\xi))\rightarrow((\varphi\rightarrow\psi)\rightarrow(\varphi\rightarrow\xi))\;1)$

(A3)

$((\neg\varphi\rightarrow\neg\psi)\rightarrow((\neg\varphi\rightarrow\psi)\rightarrow\varphi)\;1)$

Inference rules:

(GMP)

$(\varphi\;\alpha),(\varphi\rightarrow\psi\;\beta)\vdash(\psi\;min\\{\alpha,\beta\\})$

(S)

$(\varphi\;\alpha)\vdash(\varphi\;\beta)$ if $\beta\leq\alpha$

According to Dubois et al., in [Dubois et al. (1994)], basically we need a
complete lattice to express the levels of uncertainty in Possibilistic Logic.
Dubois et al.  extended the axioms schemata and the inference rules for
considering partially ordered sets. We shall denote by $\vdash_{PL}$ the
inference under Possibilistic Logic without paying attention to whether the
necessity-valued formulæ are using a totally ordered set or a partially
ordered set for expressing the levels of uncertainty.

The problem of inferring automatically the necessity-value of a classical
formula from a possibilistic base was solved by an extended version of
_resolution_ for possibilistic logic (see [Dubois et al. (1994)] for details).

One of the main principles of possibilistic logic is that:

###### Remark 2

The strength of a conclusion is the strength of the weakest argument used in
its proof.

According to Dubois and Prade [Dubois and Prade (2004)], the contribution of
possibilistic logic setting is to relate this principle (measuring the
validity of an inference chain by its weakest link) to fuzzy set-based
necessity measures in the framework of Zadeh’s possibilistic theory, since the
following pattern then holds:

$N(\sim p\vee q)\geq\alpha\textnormal{ and }N(p)\geq\beta\textnormal{ imply
}N(q)\geq min(\alpha,\beta)$

This interpretive setting provides a semantic justification to the claim that
the weight attached to a conclusion should be the weakest among the weights
attached to the formulæ involved in the derivation.

##  3 Syntax

In this section, the general syntax for possibilistic disjunctive logic
programs will be presented. This syntax is based on the standard syntax of
extended disjunctive logic programs (see Section 2.2).

We start by defining some concepts for managing the possibilistic values of a
possibilistic knowledge base777Some concepts presented in this section extend
some terms presented in [Nicolas et al. (2006)].. We want to point out that in
the whole document only finite lattices are considered. This assumption was
made based on the recognition that in real applications we will rarely have an
infinite set of labels for expressing the incomplete state of a knowledge
base.

A _possibilistic atom_ is a pair $p=(a,q)\in{\mathcal{}A}\times{\mathcal{}Q}$,
in which ${\mathcal{}A}$ is a finite set of atoms and $({\mathcal{}Q},\leq)$
is a lattice. The projection $*$ to a possibilistic atom $p$ is defined as
follows: $p^{*}=a$. Also given a set of possibilistic atoms $S$, $*$ over $S$
is defined as follows: $S^{*}=\\{p^{*}|p\in S\\}$.

Let $({\mathcal{}Q},\leq)$ be a lattice. A possibilistic disjunctive clause
$R$ is of the form:

$\alpha:{\mathcal{}A}\leftarrow{\mathcal{}B}^{+},\ not\;{\mathcal{}B}^{-}$

in which $\alpha\in{\mathcal{}Q}$ and
${\mathcal{}A}\leftarrow{\mathcal{}B}^{+},\ not\;{\mathcal{}B}^{-}$ is an
extended disjunctive clause as defined in Section 2.2. The projection $*$ for
a possibilistic clause is $R^{*}={\mathcal{}A}\leftarrow{\mathcal{}B}^{+},\
not\;{\mathcal{}B}^{-}$. On the other hand, the projection $n$ for a
possibilistic clause is $n(R)=\alpha$. This projection denotes the degree of
necessity captured by the certainty level of the information described by $R$.
A possibilistic constraint $C$ is of the form:

$\top_{\mathcal{}Q}:\;\;\;\leftarrow{\mathcal{}B}^{+},\
not\;{\mathcal{}B}^{-}$

in which $\top_{\mathcal{}Q}$ is the top of the lattice $({\mathcal{}Q},\leq)$
and $\leftarrow{\mathcal{}B}^{+},\ not\;{\mathcal{}B}^{-}$ is a constraint as
defined in Section 2.2. The projection $*$ for a possibilistic constraint $C$
is: $C^{*}=\;\;\leftarrow{\mathcal{}B}^{+},\ not\;{\mathcal{}B}^{-}$. Observe
that the possibilistic constraints have the top of the lattice
$({\mathcal{}Q},\leq)$ as an uncertain value, this assumption is due to the
fact that similar a constraint in standard ASP, the purpose of a possibilistic
constraint is to eliminate possibilistic models. Hence, it can be assumed that
there is no doubt about the veracity of the information captured by a
possibilistic constraint. However, as in standard ASP, one can define
possibilistic constraints of the form: $\alpha:x\leftarrow{\mathcal{}B}^{+},\
not\;{\mathcal{}B}^{-},\;not\;x$ such that $x$ is an atom which is not used in
any other possibilistic clause and $\alpha\in{\mathcal{}Q}$. This means that
the user can define possibilistic constraints with different levels of
certainty.

A possibilistic disjunctive logic program $P$ is a tuple of the form
$\langle({\mathcal{}Q},\leq),N\rangle$, in which $N$ is a finite set of
possibilistic disjunctive clauses and possibilistic constraints. The
generalization of $*$ over $P$ is as follows: $P^{*}=\\{r^{*}|r\in N\\}$.
Notice that $P^{*}$ is an extended disjunctive program. When $P^{*}$ is a
normal program, $P$ is called a possibilistic normal program. Also, when
$P^{*}$ is a positive disjunctive program, $P$ is called a possibilistic
positive logic program and so on. A given set of possibilistic disjunctive
clauses $\\{\gamma,\dots,\gamma\\}$ is also represented as
$\\{\gamma;\dots;\gamma\\}$ to avoid ambiguities with the use of the comma in
the body of the clauses.

Given a possibilistic disjunctive logic program
$P=\langle({\mathcal{}Q},\leq),N\rangle$, we define the _$\alpha$ -cut_ and
the _strict $\alpha$-cut_ of $P$, denoted respectively by $P_{\alpha}$ and
$P_{\overline{\alpha}}$, by

$P_{\alpha}=\langle({\mathcal{}Q},\leq),N_{\alpha}\rangle$ such that
$N_{\alpha}=\\{c|c\in N\text{ and }n(c)\geq\alpha\\}$

$P_{\overline{\alpha}}=\langle({\mathcal{}Q},\leq),N_{\overline{\alpha}}\rangle$
such that $N_{\overline{\alpha}}=\\{c|c\in N\text{ and }n(c)>\alpha\\}$

###### Example 3

In order to illustrate a possibilistic program, let us go back to our scenario
described in Section 1. Let $({\mathcal{}Q},\preceq)$ be the lattice of Figure
2 such that the relation $A\preceq B$ means that $A$ is less possible than
$B$. The possibilistic program $P:=\langle({\mathcal{}Q},\preceq),N\rangle$
will be the following set of possibilistic clauses:

It is probable that if the organ donor has an infection, then the organ
recipient can be infected or not after a graft:

probable: $r\\_inf(present,T2)\vee\lnot r\\_inf(present,T2)$ $\leftarrow$
$action(transplant,T),$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}d\\_inf(present,T),T2=T+1.$

It is confirmed that the organ’s functions can be: good, delayed and terminal
after a graft.

confirmed: $o(good\\_graft\\_funct,T2)\vee o(delayed\\_graft\\_funct,T2)\vee$
$o(terminal\\_insufficient\\_funct,T2)\leftarrow action(transplant,T),T2=T+1.$

It is confirmed that if the organ’s functions are terminally insufficient then
a transplanting is necessary.

confirmed: $action(transplant,T)\leftarrow$
$o(terminal\\_insufficient\\_funct,T)$.

It is plausible that the clinical situation of the organ recipient can be
stable if the functions of the graft are good.

plausible: $cs(stable,T)\leftarrow o(good\\_graft\\_funct,T)$.

It is plausible that the clinical situation of the organ recipient can be
unstable if the functions of the graft are delayed.

plausible: $cs(unstable,T)\leftarrow o(delayed\\_graft\\_funct,T)$.

It is plausible that the clinical situation of the organ recipient can be of
0-urgency if the functions of the graft are terminally insufficient after the
graft.

plausible: $cs($0-urgency$,T2)\leftarrow
o(terminal\\_insufficient\\_funct,T2),$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}action(transplant,T),T2=T+1$.

It is certain that the doctor cannot do two actions at the same time.

certain: $\;\;\leftarrow action(transplant,T),action(wait,T)$.

It is certain that a transplant cannot be done if the organ recipient is dead.

certain: $\;\;\leftarrow action(transplant,T),cs(dead,T)$.

The initial state of the automata of Figure 1 is captured by the following
possibilistic clauses:

certain: $d\\_inf(present,0)$.

certain: $\lnot r\\_inf(present,0)$.

certain: $o(terminal\\_insufficient\\_funct,0)$.

certain: $cs(stable,0)$.

##  4 Semantics

In §3, the syntax for any possibilistic disjunctive program was introduced,
Now, in this section, a semantics for capturing these programs is studied.
This semantics will be defined in terms of the standard definition of the
answer set semantics (§2.4.1) and the proof theory of possibilistic logic
(§2.5).

As sets of atoms are considered as interpretations, two basic operations
between sets of possibilistic atoms are defined; also a relation of order
between them is defined: Given a finite set of atoms ${\mathcal{}A}$ and a
lattice (${\mathcal{}Q}$,$\leq$),
${\mathcal{}PS^{\prime}}=2^{{\mathcal{}A}\times{\mathcal{}Q}}$ and

${\mathcal{}PS}={\mathcal{}PS^{\prime}}\setminus\\{A|A\in{\mathcal{}PS}\text{
such that }x\in{\mathcal{}A}\text{ and
}Cardinality(\\{(x,\alpha)|(x,\alpha)\in A\\})\geq 2\\}$

Observe that ${\mathcal{}PS^{\prime}}$ is the finite set of all the
possibilistic atom sets induced by ${\mathcal{}A}$ and $Q$. Informally
speaking, ${\mathcal{}PS}$ is the subset of ${\mathcal{}PS^{\prime}}$ such
that each set of ${\mathcal{}PS}$ has no atoms with different uncertain value.

###### Definition 5

Let ${\mathcal{}A}$ be a finite set of atoms and (${\mathcal{}Q}$,$\leq$) be a
lattice. $\forall A,B\in{\mathcal{}PS}$, we define.

$A\sqcap B$ | $=\\{(x,{\mathcal{}GLB}(\\{\alpha,\beta\\})|(x,\alpha)\in A\wedge(x,\beta)\in B\\}$
---|---
$A\sqcup B$ |  $=\\{(x,\alpha)|(x,\alpha)\in A\;and\;x\notin B^{*}\\}$ $\cup$
|  $\\{(x,\alpha)|x\notin A^{*}\;and\;(x,\alpha)\in B\\}$ $\cup$
|  $\\{(x,{\mathcal{}LUB}(\\{\alpha,\beta\\})|(x,\alpha)\in A\text{ and }$
$(x,\beta)\in B\\}$.
$A\sqsubseteq B$ |  $\Longleftrightarrow A^{*}\subseteq B^{*}$, and $\forall x,\alpha,\beta,(x,\alpha)\in A\wedge(x,\beta)\in B$
|  then $\alpha\leq\beta$.

This definition is almost the same as Definition 7 presented in [Nicolas et
al. (2006)]. The main difference is that in Definition 7 from [Nicolas et al.
(2006)] the operations $\sqcap$ and $\sqcup$ are defined in terms of the
operators _min_ and _max_ instead of the operators ${\mathcal{}GLB}$ and
${\mathcal{}LUB}$. Hence, the following proposition is a direct result of
Proposition 6 of [Nicolas et al. (2006)].

###### Proposition 1

$({\mathcal{}PS},\sqsubseteq)$ is a complete lattice.

Before moving on, let us define the concept of _i-greatest set_ w.r.t.
${\mathcal{}PS}$ as follows: Given $M\in{\mathcal{}PS}$, $M$ is an _i-greatest
set_ in ${\mathcal{}PS}$ iff $\nexists M^{\prime}\in{\mathcal{}PS}$ such that
$M\sqsubseteq M^{\prime}$. For instance, let
${\mathcal{}PS}=\\{\\{(a,1)\\},\\{(a,2)\\},\\{(a,2),(b,1)\\},\\{(a,2),(b,2)\\}\\}$.
One can see that ${\mathcal{}PS}$ has two i-greatest sets: $\\{(a,2)\\}$ and
$\\{(a,2),(b,2)\\}$. The concept of i-greatest set will play a key role in the
definition of possibilistic answer sets in order to infer possibilistic answer
sets with optimal certainty values.

###  4.1 Possibilistic answer set semantics

Similar to the definition of answer set semantics, the possibilistic answer
set semantics is defined in terms of a syntactic reduction. This reduction is
inspired by the Gelfond-Lifschitz reduction.

######  Definition 6 (Reduction $P_{M}$)

Let $P=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic disjunctive
logic program, M be a set of atoms. $P$ reduced by $M$ is the positive
possibilistic disjunctive logic program:

$P_{M}:=$ |  $\\{(n(r):{\mathcal{}A}\cap M\leftarrow{\mathcal{}B}^{+})|r\in N,{\mathcal{}A}\cap M\neq\emptyset,$ ${\mathcal{}B}^{-}\cap M=\emptyset,{\mathcal{}B}^{+}\subseteq M\\}$
---|---

in which $r^{*}$ is of the form ${\mathcal{}A}\leftarrow{\mathcal{}B}^{+},\
not\;{\mathcal{}B}^{-}$.

Notice that $(P^{*})_{M}$ is not exactly equal to the Gelfond-Lifschitz
reduction. For instance, let us consider the following programs:

$P:$ |  | $P_{\\{c,b\\}}:$ |  | $(P^{*})^{\\{c,b\\}}:$ |
---|---|---|---|---|---
|  $\alpha_{1}:a\vee b$. |  |  $\alpha_{1}:b$. |  |  $a\vee b$.
|  $\alpha_{2}:c\leftarrow\;not\;a$. |  |  $\alpha_{2}:c$. |  |  $c$.
|  $\alpha_{3}:c\leftarrow\;not\;b$. |  |  |  |

The program $P_{\\{c,b\\}}$ is obtained from $P$ and $\\{c,b\\}$ by applying
Definition 6 and the program $(P^{*})^{\\{c,b\\}}$ is obtained from $P^{*}$
and $\\{c,b\\}$ by applying the Gelfond-Lifschitz reduction. Observe that the
reduction of Definition 6 removes from the head of the possibilistic
disjunctive clauses any atom which does not belong to $M$. As we will see in
Section 4.2, this property will be helpful for characterizing the
possibilistic answer set in terms of a fixed-point operator. It is worth
mentioning that the reduction $(P^{*})_{M}$ also has a different effect from
the Gelfond-Lifschitz reduction in the class of normal programs. This
difference is illustrated in the following programs:

$P:$ |  | $P_{\\{a\\}}:$ |  | $(P^{*})^{\\{a\\}}:$ |
---|---|---|---|---|---
|  $\alpha_{1}:a\leftarrow\;not\;b$. |  |  $\alpha_{1}:a$. |  |  $a$.
|  $\alpha_{2}:a\leftarrow b$. |  |  |  |  $a\leftarrow b$.
|  $\alpha_{3}:b\leftarrow c$. |  |  |  |  $b\leftarrow c$.

###### Example 4

Continuing with our medical scenario described in the introduction, let $P$ be
a ground instance of the possibilistic program presented in Example 3:

probable: $r\\_inf(present,1)\vee no\\_r\\_inf(present,1)$ $\leftarrow$
$action(transplant,0),$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}d\\_inf(present,0).$
confirmed: $o(good\\_graft\\_funct,1)\vee o(delayed\\_graft\\_funct,1)\vee$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}o(terminal\\_insufficient\\_funct,1)\leftarrow
action(transplant,0).$
confirmed: $action(transplant,0)\leftarrow$
$o(terminal\\_insufficient\\_funct,0)$.
plausible: $cs(stable,1)\leftarrow o(good\\_graft\\_funct,1)$.
plausible: $cs(unstable,1)\leftarrow o(delayed\\_graft\\_funct,1)$.
plausible: $cs($0-urgency$,1)\leftarrow o(terminal\\_insufficient\\_funct,1),$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}action(transplant,0)$.
certain: $\;\;\leftarrow action(transplant,0),action(wait,0)$.
certain: $\;\;\leftarrow action(transplant,0),cs(dead,0)$.
certain: $d\\_inf(present,0)$.
certain: $no\\_r\\_inf(present,0)$.
certain: $o(terminal\\_insufficient\\_funct,0)$.
certain: $cs(stable,0)$.

Observe that the variables of time $T$ and $T2$ were instantiated with the
values $0$ and $1$ respectively; moreover, observe that the atoms $\lnot
r\\_inf(present,0)$ and $\lnot r\\_inf(present,1)$ were replaced by
$no\\_r\\_inf(present,0)$ and $no\\_r\\_inf(present,1)$ respectively. This
change was applied in order to manage the strong negation, $\lnot$ .

Now, let $S$ be the following possibilistic set:

$S=$ |  $\\{(d\\_inf(present,0),certain),$ $(no\\_r\\_inf(present,0),certain),$
---|---
|  $(o(terminal\\_insufficient\\_funct,0),certain),$ $(cs(stable,0),certain),$
|  $(action(transplant,0),confirmed),$
$(o(good\\_graft\\_funct,1),confirmed),$
|  $(cs(stable,1),plausible),$ $(no\\_r\\_inf(present,1),probable)\\}$.

One can see that $P_{S^{*}}$ is:

probable: $no\\_r\\_inf(present,1)$ $\leftarrow$
$action(transplant,0),d\\_inf(present,0).$
confirmed: $o(good\\_graft\\_funct,1)\leftarrow action(transplant,0).$
confirmed: $action(transplant,0)\leftarrow$
$o(terminal\\_insufficient\\_funct,0)$.
plausible: $cs(stable,1)\leftarrow o(good\\_graft\\_funct,1)$.
plausible: $cs(unstable,1)\leftarrow o(delayed\\_graft\\_funct,1)$.
plausible: $cs($0-urgency$,1)\leftarrow o(terminal\\_insufficient\\_funct,1),$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}action(transplant,0)$.
certain: $\;\;\leftarrow action(transplant,0),action(wait,0)$.
certain: $\;\;\leftarrow action(transplant,0),cs(dead,0)$.
certain: $d\\_inf(present,0)$.
certain: $no\\_r\\_inf(present,0)$.
certain: $o(terminal\\_insufficient\\_funct,0)$.
certain: $cs(stable,0)$.

Once a possibilistic logic program $P$ has been reduced by a set of
possibilistic atoms $M$, it is possible to test whether $M$ is a possibilistic
answer set of the program $P$. For this end, we consider a syntactic approach;
meaning that it is based on the proof theory of possibilistic logic. Let us
remember that the possibilistic logic is axiomatizable [Dubois et al. (1994)];
hence, the inference in possibilistic logic can be managed by both a syntactic
approach (axioms and inference rules) and a possibilistic model theory
approach (interpretations and possibilistic distributions).

Since the certainty value of a possibilistic disjunctive clause can belong to
a partially ordered set, the inference rules of possibilistic logic introduced
in Section 2.5 have to be generalized in terms of bounds. The generalization
of GMP and S is defined as follows:

(GMP*)

$(\varphi\;\alpha),(\varphi\rightarrow\psi\;\beta)\vdash(\psi\;GLB\\{\alpha,\beta\\})$

(S*)

$(\varphi\;\alpha),(\varphi\;\beta)\vdash(\varphi\;\gamma)$, where $\gamma\leq
GLB\\{\alpha,\beta\\}$

Observe that these inference rules are essentially the same as the inference
rules introduced in Section 2.5; however, they are defined in terms of $GLB$
to lead with certainty values which are not comparable (in Example 6 these
inference rules are illustrated).

Once we have defined $GMP^{*}$ and $S^{*}$, the inference $\Vvdash_{PL}$ is
defined as follows:

###### Definition 7

Let $P=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic disjunctive
logic program and $M\in{\mathcal{}PS}$.

  * •

We write $P\Vvdash_{PL}M$ when $M^{*}$ is an answer set of $P^{*}$ and
$P_{M^{*}}\vdash_{PL}M$.

One can see that $\Vvdash_{PL}$ is defining a joint inference between _the
answer set semantics_ and _the proof theory of possibilistic logic_. Let us
consider the following example.

###### Example 5

Let $P=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic disjunctive
logic program such that ${\mathcal{}Q}=\\{0.1,\dots,$ $0.9\\}$, $\leq$ denotes
the standard relation in real numbers and $N$ is the following set of
possibilistic clauses:

$0.6:a\vee b.$ |  | $0.4:a\leftarrow not\;b.$ |  | $0.8:b\leftarrow not\;a.$
---|---|---|---|---

It is easy to see that $P^{*}$ has two answer sets: $\\{a\\}$ and $\\{b\\}$.
On the other hand, one can see that $P_{\\{a\\}}\vdash_{PL}\\{(a,0.6)\\}$,
$P_{\\{a\\}}\vdash_{PL}\\{(a,0.4)\\}$, $P_{\\{b\\}}\vdash_{PL}\\{(b,0.6)\\}$
and $P_{\\{b\\}}\vdash_{PL}\\{(b,0.8)\\}$. This means that
$P\Vvdash_{PL}\\{(a,0.6)\\}$, $P\Vvdash_{PL}\\{(a,0.4)\\}$,
$P\Vvdash_{PL}\\{(b,0.6)\\}$ and $P\Vvdash_{PL}\\{(b,0.8)\\}$.

The basic idea of $\Vvdash_{PL}$ is to identify candidate sets of
possibilistic atoms in order to consider them as possibilistic answer sets.
The following proposition formalizes an important property of $\Vvdash_{PL}$.

###### Proposition 2

Let $P=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic disjunctive
logic program and $M_{1},M_{2}\in{\mathcal{}PS}$ such that
$M_{1}^{*}=M_{2}^{*}$. If $P\Vvdash_{PL}M1$ and $P\Vvdash_{PL}M2$, then
$P\Vvdash_{PL}M_{1}\sqcup M_{2}$.

In this proposition, since $M_{1}$ and $M_{2}$ are two sets of possibilistic
atoms, ${\mathcal{}LUB}$ is instantiated in terms of $\sqsubseteq$. By
considering $\Vvdash_{PL}$ and the concept of _i-greatest set_ , a
possibilistic answer set is defined as follows:

######  Definition 8 (A possibilistic answer set)

Let $P=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic disjunctive
logic program and $M$ be a set of possibilistic atoms such that $M^{*}$ is an
answer set of $P^{*}$. $M$ is a possibilistic answer set of $P$ iff $M$ is an
i-greatest set in ${\mathcal{}PS}$ such that $P\Vvdash_{PL}M$.

Essentially, a possibilistic answer set is an i-greatest set which is inferred
by $\Vvdash_{PL}$. In other words, a possibilistic answer set is an answer set
with _optimal certainty values_. For instance, in Example 5, we saw that
$P\Vvdash_{PL}\\{(a,0.6)\\}$, $P\Vvdash_{PL}\\{(a,0.4)\\}$,
$P\Vvdash_{PL}\\{(b,0.6)\\}$ and $P\Vvdash_{PL}\\{(b,0.8)\\}$; however,
$\\{(a,0.4)\\}$ and $\\{(b,0.6)\\}$ are not i-greatest sets. This means that
the possibilistic answer sets of the possibilistic program $P$ of Example 5
are: $\\{(a,0.6)\\}$ and $\\{(b,0.8)\\}$.

###### Example 6

Let $P$ be again the possibilistic program of Example 3 and $S$ be the
possibilistic set of atoms introduced in Example 4.

One can see that $S^{*}$ is an answer set of the extended disjunctive program
$P^{*}$. Hence, in order to prove that $P\Vvdash_{PL}S$, we have to verify
that $P_{S^{*}}\vdash_{PL}S$. This means that for each possibilistic atom
$p\in S$, $P_{S^{*}}\vdash_{PL}p$. It is clear that

$P_{S^{*}}\vdash_{PL}$ |  $\\{(d\\_inf(present,0),certain),$ $(no\\_r\\_inf(present,0),certain),$
---|---
| $(o(terminal\\_insufficient\\_funct,0),certain),$
| $(cs(stable,0),certain)\\}$

Now let us prove $(cs(stable,1),plausible)$ from $P_{S^{*}}$.

Premises from $P_{S^{*}}$ |
---|---
1\. $o(terminal\\_insufficient\\_funct,0)$ | $certain$
2\. $o(terminal\\_insufficient\\_funct,0)\rightarrow action(transplant,0)$ | $confirmed$
3\. $action(transplant,0)\rightarrow o(good\\_graft\\_funct,1)$ | $confirmed$
4\. $o(good\\_graft\\_funct,1)\rightarrow cs(stable,1)$ | $plausible$
From 1 and 2 by GMP* |
5\. $action(transplant,0)$ | $confirmed$
From 3 and 5 by GMP* |
6\. $o(good\\_graft\\_funct,1)$ | $confirmed$
From 4 and 6 by GMP* |
7\. $cs(stable,1)$. | $plausible$

In this proof, we can also see the inference of the possibilistic atom
$(action(transplant,0),$ $confirmed)$. The proof of the possibilistic atom
$(no\\_r\\_inf(present,1),probable)$ is similar to the proof of the
possibilistic atom $(cs(stable,1),plausible)$. Therefore,
$P_{S^{*}}\vdash_{PL}S$ is true. Notice that a possibilistic set $S^{\prime}$
such that $S^{\prime}\neq S$, $P_{(S^{\prime})^{*}}\vdash_{PL}S^{\prime}$ and
$S\sqsubseteq S^{\prime}$ does not exists; hence, $S$ is an i-greatest set.
Then, $S$ is a possibilistic answer set of $P$.

By considering the possibilistic answer set $S$, what can we conclude about
our medical scenario from $S$? We can conclude that if it is _confirmed_ that
a transplant is performed on a donor with an infection, it is _probable_ that
the recipient will not be infected after the transplant; moreover it is
_plausible_ that he will be stable. It is worth mentioning that this
_optimistic_ conclusion is just one of the possible scenarios that we can
infer from the program $P$. In fact, the program $P$ has six possibilistic
answer sets in which we can find pessimistic scenarios such as it is
_probable_ that the recipient will be infected by the organ donor’s infection
and; moreover, it is _confirmed_ that the recipient needs another transplant.

Now, let us identify some properties of the possibilistic answer set
semantics. First, observe that there is an important condition w.r.t. the
definition of a _possibilistic answer set_ which is introduced by
$\Vvdash_{PL}$: a possibilistic set $S$ cannot be a possibilistic answer set
of a possibilistic logic program $P$ if $S^{*}$ is not an answer set of the
extended logic program $P^{*}$. This condition guarantees that any clause of
$P^{*}$ is satisfied by $S^{*}$. For instance, let us consider the
possibilistic logic program $P$:

$0.4:a.$ |  | $0.6:b.$
---|---|---

and the possibilistic set $S=\\{(a,0.4)\\}$. We can see that
$P_{S^{*}}\vdash_{PL}S$; however, $S^{*}$ is not an answer set of $P^{*}$.
Therefore, $P\Vvdash_{PL}S$ is _false_. Then $S$ could not be a possibilistic
answer set of $P$. This suggests, a direct relationship between the
possibilistic answer semantics and the answer set semantics.

###### Proposition 3

Let $P$ be a possibilistic disjunctive logic program. If $M$ is a
possibilistic answer set of P then $M^{*}$ is an answer set of $P^{*}$.

When all the possibilistic clauses of a possibilistic program $P$ have the
same certainly level, the answer sets of $P^{*}$ can be directly generalized
to the possibilistic answer sets of $P$.

###### Proposition 4

Let $P=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic disjunctive
logic program and $\alpha$ be a fixed element of ${\mathcal{}Q}$. If $\forall
r\in P$, $n(r)=\alpha$ and $M^{\prime}$ is an answer set of $P^{*}$, then
$M:=\\{(a,\alpha)|a\in M^{\prime}\\}$ is a possibilistic answer set of $P$.

For the class of possibilistic normal logic programs which are defined with a
totally ordered set, our definition of possibilistic answer set is closely
related to the definition of a _possibilistic stable model_ presented in
[Nicolas et al. (2006)]. In fact, both semantics coincide.

###### Proposition 5

Let $P:=\langle(Q,\leq),N\rangle$ be a possibilistic normal program such that
$(Q,\leq)$ is a totally ordered set and ${\mathcal{}L}_{P}$ has no extended
atoms. $M$ is a possibilistic answer set of P if and only if $M$ is a
possibilistic stable model of $P$.

To prove that the possibilistic answer set semantics is computable, we will
present an algorithm for computing possibilistic answer sets. With this in
mind, let us remember that a classical resolvent is defined as follows: Assume
that $C$ and $D$ are two clauses in their disjunctive form such that $C=a\vee
l_{1}\vee\dots\vee l_{n}$ and $D=\sim a\vee ll_{1}\vee\dots\vee ll_{m}$. The
clause $l_{1}\vee\dots\vee l_{n}\vee ll_{1}\vee\dots\vee ll_{m}$ is called a
resolvent of $C$ and $D$ w.r.t. $a$. Thus clauses $C$ and $D$ have a resolvent
in case a literal $a$ exists such that $a$ appears in $C$ and $\sim a$ appears
in $D$ (or conversely).

Now, let us consider a straightforward generalization of the possibilistic
resolution rule introduced in [Dubois et al. (1994)]:

(R)

$(c_{1}\;\alpha_{1})(c_{2}\;\alpha_{2})\vdash(R(c_{1},c_{2})\;{\mathcal{}GLB}(\\{\alpha_{1},\alpha_{2}\\}))$

in which $R(c_{1},c_{2})$ is any classical resolvent of $c_{1}$ and $c_{2}$
such that $c_{1}$ and $c_{2}$ are disjunctions of literals. It is worth
mentioning that it is easy to transform any possibilistic disjunctive logic
program $P$ into a set of possibilistic disjunctions ${\mathcal{}C}$. Indeed,
${\mathcal{}C}$ can be obtained as follows:

${\mathcal{}C}:=\bigcup\\{(a_{1}\vee\ldots\vee a_{m}\vee\sim
a_{m+1}\vee\dots\vee\sim a_{j}\vee a_{j+1}\vee\dots,a_{n}\;\alpha)|$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\alpha:a_{1}\vee\ldots\vee
a_{m}\leftarrow a_{m+1},\dots,a_{j},not\;a_{j+1},\dots,not\;a_{n})\in P\\}$

Let us remember that whenever a possibilistic program is considered as a
possibilistic theory, each negative literal $not\;a$ is replaced by $\sim a$
such that $\sim$ is regarded as the negation in classic logic — in Example 7,
the transformation of a possibilistic program into a set of possibilistic
disjunctions is shown.

The following proposition shows that the resolution rule (R) is sound.

###### Proposition 6

Let ${\mathcal{}C}$ be a set of possibilistic disjunctions, and
$C=(c\;\alpha)$ be a possibilistic clause obtained by a finite number of
successive application of _(R)_ to ${\mathcal{}C}$; then
${\mathcal{}C}\vdash_{PL}C$.

Like the possibilistic rule introduced in [Dubois et al. (1994)], (R) is
complete for refutation. We will say that a possibilistic disjunctive program
$P$ is _consistent_ if $P$ has at least a possibilistic answer set. Otherwise
$P$ is said to be _inconsistent_. The degree of inconsistency of a
possibilistic logic program $P$ is
$Inc(P)={\mathcal{}GLB}(\\{\alpha|P_{\alpha}\text{ is consistent }\\})$.

###### Proposition 7

Let $P$ be a set of possibilistic clauses and ${\mathcal{}C}$ be the set of
possibilistic disjunctions obtained from $P$; then the valuation of the
optimal refutation by resolution from ${\mathcal{}C}$ is the inconsistent
degree of $P$.

The main implication of Proposition 6 and Proposition 7 is that (R) suggests a
method for inferring a possibilistic formula from a possibilistic knowledge
base.

###### Corollary 1

Let $P:=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic disjunctive
logic program, $\varphi$ be a literal and ${\mathcal{}C}$ be a set of
possibilistic disjunctions obtained from
$N\cup\\{(\sim\varphi\;\top_{\mathcal{}Q})\\}$; then the valuation of the
optimal refutation from ${\mathcal{}C}$ is $n(\varphi)$, that is
$P\vdash_{PL}(\varphi\;n(\varphi))$.

Based on the fact that the resolution rule (R) suggests a method for inferring
the necessity value of a possibilistic formula, we can define the following
function for computing the possibilistic answer sets of a possibilistic
program $P$. In this function, $\square$ denotes an empty clause.

Function $Poss\\_Answer\\_Sets(P)$

Let $ASP(P^{*})$ be a function that computes the answer set models of the
standard logic program $P^{*}$, for example DLV [DLV (1996)].

Poss-ASP $:=\emptyset$

For all $S\in ASP(P^{*})$

Let ${\mathcal{}C}$ be the set of possibilistic disjunctions obtained from
$P_{S}$.
$S^{\prime}:=\emptyset$
for all $a\in S$
$C^{\prime}:={\mathcal{}C}\cup\\{(\sim a\;\top_{\mathcal{}Q})\\}$
Search for a deduction of $(R(\square)\;\alpha)$ by applying repeatedly
the resolution rule (R) from $C^{\prime}$, with $\alpha$ maximal.
$S^{\prime}:=S^{\prime}\cup\\{(a\;\alpha)\\}$
endfor
Poss-ASP $:=$ Poss-ASP $\cup\;S^{\prime}$
endfor
return(Poss-ASP).

The following proposition proves that the function $Poss\\_Answer\\_Sets$
computes all the possibilistic answer sets of a possibilistic logic program.

###### Proposition 8

Let $P:=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic logic
program. The set Poss-ASP returned by $Poss\\_Answer\\_Sets(P)$ is the set of
all the possibilistic answer sets of $P$.

In order to illustrate this algorithm, let us consider the following example:

###### Example 7

Let $P:=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic program such
that ${\mathcal{}Q}:=\\{0,$ $0.1$, $\dots$, $0.9,$ $1\\}$, $\leq$ is the
standard relation between rational numbers and $N$ the following set of
possibilistic clauses:

$0.7:$ | $a\vee b$ | $\leftarrow not\;c.$
---|---|---
$0.6:$ | $c$ | $\leftarrow not\;a,not\;b.$
$0.8:$ | $a$ | $\leftarrow b.$
$0.9:$ | $e$ | $\leftarrow b.$
$0.6:$ | $b$ | $\leftarrow a.$
$0.5:$ | $b$ | $\leftarrow a.$

First of all, we can see that $P^{*}$ has two answer sets:
$S_{1}:=\\{a,b,e\\}$ and $S_{2}:=\\{c\\}$. This means that $P$ has two
possibilistic answer set models. Let us consider $S_{1}$ for our example.
Then, one can see that $P_{S_{1}}$ is:

$0.7:$ |  $a\vee b$. |
---|---|---
$0.8:$ | $a$ | $\leftarrow b.$
$0.9:$ | $e$ | $\leftarrow b.$
$0.6:$ | $b$ | $\leftarrow a.$
$0.5:$ | $b$ | $\leftarrow a.$

Then ${\mathcal{}C}:=\\{(a\vee b\;0.7),(a\vee\sim b\;0.8),(e\vee\sim
b\;0.9),(b\vee\sim a\;0.6),(b\vee\sim a\;0.5)\\}$. In order to infer the
necessity value of the atom $a$, we add $(\sim a\;1)$ to ${\mathcal{}C}$ and a
search for finding an optimal refutation is applied. As we can see in Figure
3, there are three refutations, however the optimal refutation is
$(\square\;0.7)$. This means that the best necessity value for the atom $a$ is
$0.7$.

Figure 3: Possibilistic resolution: Search for an _optimal refutation_ for the
atom $a$.

In Figure 4, we can see the optimal refutation search for the atom $b$. As we
can see the optimal refutation is $(\square\;0.6)$; hence the best necessity
value for the atom $b$ is $0.6$.

Figure 4: Possibilistic resolution: Search for an _optimal refutation_ for the
atom $b$.

In Figure 5, we can see that the best necessity value for the atom $e$ is
$0.6$.

Figure 5: Possibilistic resolution: Search for an _optimal refutation_ for the
atom $e$.

Thought the search, we can infer that a possibilistic answer set of the
program $P$ is : $\\{(a,0.7),(b,0.6),(e,0.6)\\}$.

###  4.2 Possibilistic answer sets based on partial evaluation

We have defined a possibilistic answer set semantics by considering the formal
proof theory of possibilistic logic. However, in standard logic programming
there are several frameworks for analyzing, defining and computing logic
programming semantics [Dix (1995a), Dix (1995b)]. One of these approaches is
based on program transformations, in fact there are many studies on this
approach, for example [Brass and Dix (1999), Brass and Dix (1997), Brass and
Dix (1998), Dix et al. (2001)]. For the case of disjunctive logic program, one
important transformation is _partial evaluation (also called unfolding)_
[Brass and Dix (1999)].

This section shows that it is also possible to define a possibilistic
disjunctive semantics based on an operator which is a combination between
partial evaluation for disjunctive logic programs and the infer rule $GMP^{*}$
of possibilistic logic. This semantics has the same behavior as the semantics
based on the proof theory of possibilistic logic.

This section starts by defining a version of the general principle of partial
evaluation (GPPE) for possibilistic positive disjunctive clauses.

######  Definition 9 (Grade-GPPE (G-GPPE))

Let $r_{1}$ be a possibilistic clause of the form
$\alpha:{\mathcal{}A}\leftarrow{\mathcal{}B}^{+}\cup\\{B\\}$ and $r_{2}$ a
possibilistic clause of the form $\alpha_{1}:{\mathcal{}A}_{1}$ such that
$B\in{\mathcal{}A}_{1}$ and $B\notin B^{+}$, then

$\text{G-GPPE}(r_{1},r_{2})=({\mathcal{}GLB}(\\{\alpha,\alpha_{1}\\}):{\mathcal{}A}\cup({\mathcal{}A}_{1}\setminus\\{B\\})\leftarrow{\mathcal{}B}^{+})$

Observe that one of the possibilistic clauses which is considered by G-GPPE
has an empty body. For instance, let us consider the following two
possibilistic clauses:

$r_{1}=\;0.7:a\vee b$.
$r_{2}=\;0.9:e\leftarrow b$.

Then G-GPPE$(r_{1},r_{2})=(0.7:e\vee a)$. Now, by considering G-GPPE, we will
define the operator ${\mathcal{}T}$.

###### Definition 10

Let $P$ be a possibilistic positive logic program. The operator
${\mathcal{}T}$ is defined as follows:

${\mathcal{}T}(P):=P\cup\\{\text{G-GPPE}(r_{1},r_{2})|r_{1},r_{2}\in P\\}$

In order to illustrate the operator ${\mathcal{}T}$, let us consider the
program $P_{S_{1}}$ of Example 7.

$0.7:$ |  $a\vee b$. |
---|---|---
$0.8:$ | $a$ | $\leftarrow b.$
$0.9:$ | $e$ | $\leftarrow b.$
$0.6:$ | $b$ | $\leftarrow a.$
$0.5:$ | $b$ | $\leftarrow a.$

Hence, ${\mathcal{}T}(P_{S_{1}})$ is:

$0.7:$ |  $a\vee b$. |  | $0.7:$ |  $a$.
---|---|---|---|---
$0.8:$ | $a\leftarrow b.$ |  | $0.7:$ |  $e\vee a$.
$0.9:$ | $e\leftarrow b.$ |  | $0.6:$ |  $b$.
$0.6:$ | $b\leftarrow a.$ |  | $0.5:$ |  $b$.
$0.5:$ | $b\leftarrow a.$ |  |  |

Notice that by considering the possibilistic clauses that were added to
$P^{S_{1}}$ by ${\mathcal{}T}$, one can reapply G-GPPE. For instance, if we
consider $0.6:b$ and $0.9:e\leftarrow b$ from ${\mathcal{}T}(P^{S_{1}})$,
G-GPPE infers $0.6:e$. Indeed, ${\mathcal{}T}({\mathcal{}T}(P_{S_{1}}))$ is:

$0.7:$ |  $a\vee b$. |  | $0.7:$ |  $a$. |  | $0.6:$ |  $a$.
---|---|---|---|---|---|---|---
$0.8:$ | $a\leftarrow b.$ |  | $0.7:$ |  $e\vee a$. |  | $0.5:$ |  $a$.
$0.9:$ | $e\leftarrow b.$ |  | $0.6:$ |  $b$. |  | $0.6:$ |  $e$.
$0.6:$ | $b\leftarrow a.$ |  | $0.5:$ |  $b$. |  | $0.5:$ |  $e$.
$0.5:$ | $b\leftarrow a.$ |  |  |  |  | $0.6:$ |  $b\vee e$.
|  |  |  |  |  | $0.5:$ |  $b\vee e$.

An important property of the operator ${\mathcal{}T}$ is that it always
reaches a fixed-point.

###### Proposition 9

Let $P$ be a possibilistic disjunctive logic program. If
$\Gamma_{0}:={\mathcal{}T}(P)$ and $\Gamma_{i}:={\mathcal{}T}(\Gamma_{i-1})$
such that $i\in{\mathcal{}N}$, then $\exists\;n\in{\mathcal{}N}$ such that
$\Gamma_{n}=\Gamma_{n-1}$. We denote $\Gamma_{n}$ by $\Pi(P)$.

Let us consider again the possibilistic program $P_{S_{1}}$. We can see that
$\Pi(P_{S_{1}})$ is:

$0.7:$ |  $a\vee b$. |  | $0.7:$ |  $a$. |  | $0.6:$ |  $a$. |  | $0.6$ | $a\vee e.$
---|---|---|---|---|---|---|---|---|---|---
$0.8:$ | $a\leftarrow b.$ |  | $0.7:$ |  $e\vee a$. |  | $0.5:$ |  $a$. |  | $0.5$ | $a\vee e.$
$0.9:$ | $e\leftarrow b.$ |  | $0.6:$ |  $b$. |  | $0.6:$ |  $e$. |  |  |
$0.6:$ | $b\leftarrow a.$ |  | $0.5:$ |  $b$. |  | $0.5:$ |  $e$. |  |  |
$0.5:$ | $b\leftarrow a.$ |  |  |  |  | $0.6:$ |  $b\vee e$. |  |  |
|  |  |  |  |  | $0.5:$ |  $b\vee e$. |  |  |

Observe that in $\Pi(P_{S_{1}})$ there are possibilistic facts (possibilistic
clauses with empty bodies and one atom in their heads) with different
necessity value. In order to infer the optimal necessity value of each
possibilistic fact, one can consider the _least upper bound_ of these values.
For instance, the optimal necessity value for the possibilistic atom $a$ is
${\mathcal{}LUB}(\\{0.7,0.6,0.5\\})=0.7$. Based on this idea, $Sem_{min}$ is
defined as follows.

###### Definition 11

Let $P$ be a possibilistic logic program and
$Facts(P,a):=\\{(\alpha:a)|(\alpha:a)\in P\\}$.
$Sem_{min}(P):=\\{(x,\alpha)|Facts(P,x)\neq\emptyset\text{ and }$
$\alpha:={\mathcal{}LUB}(\\{n(r)|{r\in Facts(P,x)}\\})\\}$ in which
$x\in{\mathcal{}L}_{P}$.

It is easy to see that $Sem_{min}(\Pi(P_{S_{1}}))$ is
$\\{(a,0.7),(b,0.6),(e,0.6)\\}$. Now by considering the operator
${\mathcal{}T}$ and $Sem_{min}$, we can define a semantics for possibilistic
disjunctive logic programs that will be called possibilistic-${\mathcal{}T}$
answer set semantics.

###### Definition 12

Let $P$ be a possibilistic disjunctive logic program and $M$ be a set of
possibilistic atoms such that $M^{*}$ is an answer set of $P^{*}$. $M$ is a
possibilistic-${\mathcal{}T}$ answer set of P if and only if
$M=Sem_{min}(\Pi(P_{M^{*}}))$.

In order to illustrate this definition, let us consider again the program $P$
of Example 7 and $S=\\{(a,0.7),(b,0.6),(e,0.6)\\}$. As commented in Example 7,
$S^{*}$ is an answer set of $P^{*}$. We have already seen that
$Sem_{min}(\Pi(P_{S_{1}}))$ is $\\{(a,0.7),(b,0.6),(e,0.6)\\}$, therefore we
can say that $S$ is a possibilistic-${\mathcal{}T}$ answer set of $P$. Observe
that the possibilistic-${\mathcal{}T}$ answer set semantics and the
possibilistic answer set semantics coincide. In fact, the following
proposition guarantees that both semantics are the same.

###### Proposition 10

Let $P$ be a possibilistic disjunctive logic program and $M$ a set of
possibilistic atoms. $M$ is a possibilistic answer set of $P$ if and only if
$M$ is a possibilistic-${\mathcal{}T}$ answer set of $P$.

##  5 Inconsistency in possibilistic logic programs

In the first part of this section, the relevance of considering inconsistent
possibilistic knowledge bases is introduced, and in the second part, some
criteria for managing inconsistent possibilistic logic programs are
introduced.

###  5.1 Relevance of inconsistent possibilistic logic programs

Inconsistent knowledge bases are usually regarded as an _epistemic hell_ that
have to be avoided at all costs. However, many times it is difficult or
impossible to stay away from managing inconsistent knowledge bases. There are
authors such as Octávio Bueno [Bueno (2006)] who argues that the consideration
of inconsistent systems is a useful device for a number of reasons: (1) it is
often the only way to explore inconsistent information without arbitrarily
rejecting precious data. (2) inconsistent systems are sometimes the only way
to obtain new information (particularly information that conflicts with deeply
entrenched theories). As a result, (3) inconsistent belief systems allow us to
make better _informed decisions_ regarding which bits of information to accept
or reject in the end.

In order to give a small example, in which exploring inconsistent information
can be important for making a better informed decision, we will continue with
the medical scenario described in Section 1. In Example 4, we have already
presented the grounded program $P_{infections}$ of our medical scenario:

probable: $r\\_inf(present,1)\vee no\\_r\\_inf(present,1)$ $\leftarrow$
$action(transplant,0),$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}d\\_inf(present,0).$
confirmed: $o(good\\_graft\\_funct,1)\vee o(delayed\\_graft\\_funct,1)\vee$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}o(terminal\\_insufficient\\_funct,1)\leftarrow
action(transplant,0).$
confirmed: $action(transplant,0)\leftarrow$
$o(terminal\\_insufficient\\_funct,0)$.
plausible: $cs(stable,1)\leftarrow o(good\\_graft\\_funct,1)$.
plausible: $cs(unstable,1)\leftarrow o(delayed\\_graft\\_funct,1)$.
plausible: $cs($0-urgency$,1)\leftarrow o(terminal\\_insufficient\\_funct,1),$
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}action(transplant,0)$.
certain: $\;\;\leftarrow action(transplant,0),action(wait,0)$.
certain: $\;\;\leftarrow action(transplant,0),cs(dead,0)$.
certain: $d\\_inf(present,0)$.
certain: $no\\_r\\_inf(present,0)$.
certain: $o(terminal\\_insufficient\\_funct,0)$.
certain: $cs(stable,0)$.

As mentioned in Example 4, in this program the atoms $\lnot
r\\_inf(present,0)$ and
$\lnot r\\_inf(present,1)$ were replaced by $no\\_r\\_inf(present,0)$ and
$no\\_r\\_inf(present,1)$ respectively. Usually in standard answer set
programming, the constraints

$\leftarrow no\\_r\\_inf(present,0),r\\_inf(present,0).$
$\leftarrow no\\_r\\_inf(present,1),no\\_r\\_inf(present,1)$.

must be added to the program to avoid inconsistent answer sets. In order to
illustrate the role of these kinds of constraints, let $C_{1}$ be the
following possibilistic constraints:

certain: $\;\;\leftarrow no\\_r\\_inf(present,0),r\\_inf(present,0).$
certain: $\;\;\leftarrow no\\_r\\_inf(present,1),no\\_r\\_inf(present,1)$.

Also let us consider three new possibilistic clauses (denoted by $P_{v}$):

confirmed: $v(kidney,0)\leftarrow cs(stable,1),action(transplant,0)$.
probable: $no\\_v(kidney,0)\leftarrow
r\\_inf(present,1),action(transplant,0)$.
certain: $\;\;\leftarrow\;not\;cs(stable,1)$.

The intended meaning of the predicate $v(t,T)$ is that the organ $t$ is viable
for a transplant and $T$ denotes a moment in time. Observe that we replaced
the atom $\lnot v(kidney,0)$ with $no\\_v(kidney,0)$. The reading of the first
clause is that if the clinical situation of the organ recipient is stable
after the graft, then it is _confirmed_ that the kidney is viable for
transplant. The reading of the second one is that if the organ recipient is
infected after the graft, then it is _plausible_ that the kidney is not viable
for transplant. The aim of the possibilistic constraint is to discard
scenarios in which the clinical situation of the organ recipient is not
stable. Let us consider the respective possibilistic constraint w.r.t. the
atoms $no\\_v(kidney,0)$ and $v(kidney,0)$ (denoted by $C_{2}$):

certain: $\;\;\leftarrow no\\_v(kidney,0),v(kidney,0).$

Two programs are defined:

$P:=P_{infections}\;\cup\;P_{v}\text{ and }P_{c}:=P_{infections}\;\cup
P_{v}\;\cup\;C_{1}\;\cup\;C_{2}$

Basically, the difference between $P$ and $P_{c}$ is that $P$ allows
inconsistent possibilistic models and $P_{c}$ does not allow inconsistent
possibilistic models.

Now let us consider the possibilistic answer sets of the programs $P$ and
$P_{c}$. One can see that the program $P_{c}$ has just one possibilistic
answer set:

$\\{(d\\_inf(present,0),certain),$ $(no\\_r\\_inf(present,0),certain),$
$(o(terminal\\_insufficient\\_funct,0),certain),$ $(cs(stable,0),certain),$
$(action(transplant,0),confirmed),$ $(o(good\\_graft\\_funct,1),confirmed),$
$\textbf{(cs(stable,1), plausible)},$ $\textbf{(no\\_r\\_inf(present,1),
probable)},$
$\textbf{(v(kidney,0), plausible)}\\}$

This possibilistic answer set suggests that since it is plausible that the
recipient’s clinical situation will be stable after the graft, it is plausible
that the kidney is _viable_ for transplanting. _Observe that the possibilistic
answer sets of $P$ do not show the possibility that the organ recipient could
be infected after the graft_.

Let us consider the possibilistic answer set of the program $P$:

$S_{1}:=\\{(d\\_inf(present,0),certain),$ $(no\\_r\\_inf(present,0),certain),$
$(o(terminal\\_insufficient\\_funct,0),certain),$ $(cs(stable,0),certain),$
$(action(transplant,0),confirmed),$ $(o(good\\_graft\\_funct,1),confirmed),$
$\textbf{(cs(stable,1), plausible)},$ $\textbf{(no\\_r\\_inf(present,1),
probable)},$
$\textbf{(v(kidney,0), plausible)}\\}$

$S_{2}:=\\{(d\\_inf(present,0),certain),$ $(no\\_r\\_inf(present,0),certain),$
$(o(terminal\\_insufficient\\_funct,0),certain),$ $(cs(stable,0),certain),$
$(action(transplant,0),confirmed),$ $(o(good\\_graft\\_funct,1),confirmed),$
$\textbf{(cs(stable,1), plausible)},$ $\textbf{(r\\_inf(present,1),
probable)},$
$\textbf{(v(kidney,0), plausible)},\textbf{(no\\_v(kidney,0), probable)}\\}$

$P$ has two possibilistic answer sets: $S_{1}$ and $S_{2}$. $S_{1}$
corresponds to the possibilistic answer set of the program $P_{c}$ and $S_{2}$
is an inconsistent possibilistic answer set — because the atoms (v(kidney,0),
plausible) and (no_v(kidney,0), probable) appear in $S_{2}$. Observe that
although $S_{2}$ is an inconsistent possibilistic answer set, it contains
important information w.r.t. the considerations of our scenario. $S_{2}$
suggests that even though it is plausible that the clinical situation of the
organ recipient will be stable after the graft, it is also probable that the
organ recipient will be infected by the infection of the donor’s organ.

Observe that $P_{c}$ is unable to infer the possibilistic answer set $S_{2}$;
because, it contains the following possibilistic constraint:

certain: $\;\;\leftarrow no\\_v(kidney,0),v(kidney,0).$

By defining these kinds of constraints, we can guarantee that any
possibilistic answer set inferred from $P_{c}$ will be consistent; however,
one can omit important considerations w.r.t. a decision-making problem. In
fact, we agree with Bueno [Bueno (2006)] that considering inconsistent systems
as inconsistent possibilistic answer sets is some times the only way to
explore inconsistent information without arbitrarily rejecting precious data.

###  5.2 Inconsistency degrees of possibilistic sets

To manage inconsistent possibilistic answer sets, it is necessary to define a
criterion of preference between possibilistic answer sets. In order to define
a criterion between possibilistic answer sets, the concept of _inconsistency
degree of a possibilistic set_ is defined. We say that a set of possibilistic
atoms $S$ is inconsistent (resp. consistent) if and only if $S^{*}$ is
inconsistent (resp. consistent), that is to say there is an atom $a$ such that
$a,\lnot a\in S^{*}$.

###### Definition 13

Let ${\mathcal{}A}\in{\mathcal{}SP}$. The inconsistent degree of $S$ is
defined as follows:

$InconsDegre(S):=\left\\{\begin{array}[]{lcl}\bot_{\mathcal{}Q}&&\text{ if
}S^{*}\text{ is consistent}\\\ {\mathcal{}GLB}(\\{\alpha|S_{\alpha}\text{ is
consistent}\\})&&\text{otherwise }\end{array}\right.$

in which $\bot_{\mathcal{}Q}$ is the bottom of the lattice
(${\mathcal{}Q}$,$\leq$) and $S_{\alpha}:=\\{(a,\alpha_{1})\in
S|\alpha_{1}\geq\alpha\\}$.

For instance, the possibilistic answer set $S_{2}$ of our example above has a
degree of inconsistency of _confirmed_. Based on the degree of inconsistency
of possibilistic sets, we can define a criterion of preference between
possibilistic answer sets.

###### Definition 14

Let $P=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic program and
$M_{1}$, $M_{2}$ two possibilistic answer sets of $P$. We say that $M_{1}$ is
more-consistent than $M_{2}$ if and only if
$InconsDegre(M_{1})<InconsDegre(M_{2})$.

In our example above, it is obvious that $S_{1}$ is more-consistent than
$S_{2}$. In general terms, a possibilistic answer set $M_{1}$ is preferred to
$M_{2}$ if and only if $M_{1}$ is more-consistent than $M_{2}$. This means
that any consistent possibilistic answer set will be preferred to any
inconsistent possibilistic answer set.

So far we have commented only on the case of inconsistent possibilistic answer
sets. However, there are possibilistic programs that are inconsistent because
they have no possibilistic answer sets. For instance, let us consider the
following possibilistic program $P_{inc}$ (we are assuming the lattice of
Example 7):

$0.3:$ | $a\leftarrow\;not\;b.$
---|---
$0.5:$ | $b\leftarrow\;not\;c.$
$0.6:$ | $c\leftarrow\;not\;a.$

Observe that $P_{inc}^{*}$ has no answer sets; hence, $P_{inc}$ has no
possibilistic answer sets.

###  5.3 Restoring inconsistent possibilistic knowledge bases

In order to restore consistency of an inconsistent possibilistic knowledge
base, possibilistic logic eliminates the set of possibilistic formulæ which
are lower than the inconsistent degree of the inconsistent knowledge base.
Considering this idea, the authors of [Nicolas et al. (2006)] defined the
concept of $\alpha$-cut for possibilistic logic programs. Based on Definition
14 of [Nicolas et al. (2006)], we define its respective generalization for our
approach.

###### Definition 15

Let $P$ be a possibilistic logic program

-

the strict $\alpha$-cut is the subprogram $P_{>\alpha}=\\{r\in
P|n(r)>\alpha\\}$

-

the consistency cut degree of $P$:

$ConsCutDeg(P):=\left\\{\begin{array}[]{lcl}\bot_{\mathcal{}Q}&&\text{ if
}P^{*}\text{ is consistent}\\\ {\mathcal{}GLB}(\\{\alpha|P_{\alpha}\text{ is
consistent}\\})&&\text{otherwise }\end{array}\right.$

where $\bot_{\mathcal{}Q}$ is the bottom of the lattice
(${\mathcal{}Q}$,$\leq$).

Notice that the consistency cut degree of a possibilistic logic program
identifies the minimum level of certainty for which a strict $\alpha$-cut of
$P$ is consistent. As Nicolas et al., remarked in [Nicolas et al. (2006)], by
the non-monotonicity of the framework, it is not certain that a higher cut is
necessarily consistent.

In order to illustrate these ideas, let us reconsider the program $P_{inc}$.
First, one can see that $ConsCutDeg(P_{inc})=0.3$; hence, the subprogram
$P_{ConsCutDeg(P_{inc})}$ is:

$0.5:$ | $b\leftarrow\;not\;c.$
---|---
$0.6:$ | $c\leftarrow\;not\;a.$

Observe that this program has a possibilistic answer set which is
$\\{(c,0.6)\\}$. Hence due to the strict $\alpha$-cut of $P$, one is able to
infer information from $P_{inc}$

To resume, one can identify two kinds of inconsistencies in our approach,

  * •

one which arises from the presence of complementary atoms in a possibilistic
answer set and

  * •

one which arises from the non-existence of a possibilistic answer set of a
possibilistic logic program.

To manage the inconsistency of possibilistic answer sets, a criterion of
preference between possibilistic answer sets was defined. On the other hand,
to manage the non-existence of a possibilistic answer set of a possibilistic
logic program $P$, the approach suggested by Nicolas et al. in [Nicolas et al.
(2006)], was adopted. This approach is based on $\alpha$_-cuts_ in order to
get consistent subprograms of a given program $P$.

##  6 Related Work

Research on logic programming with uncertainty has dealt with various
approaches of logic programming semantics, as well as different applications.
Most of the approaches in the literature employ one of the following
formalisms:

  * •

annotated logic programming, _e.g._ [Kifer and Subrahmanian (1992)].

  * •

probabilistic logic, _e.g._ [Ng and Subrahmanian (1992), Lukasiewicz (1998),
Kern-Isberner and Lukasiewicz (2004), Baral et al. (2009)].

  * •

fuzzy set theory, _e.g._ [van Emden (1986), Rodríguez-Artalejo and Romero-Díaz
(2008), Van-Nieuwenborgh et al. (2007)].

  * •

multi-valued logic, _e.g._ [Fitting (1991), Lakshmanan (1994)].

  * •

evidence theoretic logic programming, _e.g._ [Baldwin (1987)].

  * •

possibilistic logic, _e.g._ [Dubois et al. (1991), Alsinet and Godo (2002),
Alsinet and Godo (2000), Alsinet et al. (2008), Nicolas et al. (2006)].

Basically, these approaches differ in the underlying notion of uncertainty and
how uncertainty values, associated with clauses and facts, are managed. Among
these approaches, the formalisms based on possibilistic logic are closely
related to the approach presented in this paper. A clear distinction betweem
them and the formalism of this paper is that none of them capture disjunctive
clauses. On the other hand, excepting the work of Nicolas, et al., [Nicolas et
al. (2006)], none of these approaches describe a formalism for dealing with
uncertainty in a logic program with default negation by means of possibilistic
logic. Let us recall that the work of [Nicolas et al. (2006)] is totally
captured by the formalism presented in this paper (Proposition 5), but not
directly vice versa. For instance, let us consider the possibilistic logic
programs $P=\langle(\\{0.1,\dots,0.9\\},\leq),N\rangle$ such that $\leq$ is
the standard relation between rational number and $N$ the following set of
possibilistic clauses:

$0.5:a\vee b.$ |  | $0.5:a\leftarrow b.$
---|---|---
|  | $0.5:b\leftarrow a.$

By considering a standard transformation from disjunctive clauses to normal
clauses [Baral (2003)], this program can be transformed to the possibilistic
normal logic programs $P^{\prime}$:

$0.5:a\leftarrow\;not\;b.$ |  | $0.5:a\leftarrow b.$
---|---|---
$0.5:b\leftarrow\;not\;a.$ |  | $0.5:b\leftarrow a.$

One can see that $P$ has a possibilistic answer set: $\\{(a,0.5),(b,0.5)\\}$;
however, $P^{\prime}$ has no possibilistic answer sets.

Even though, one can find a wide range of formalisms for dealing with
uncertainty by using _normal logic programs_ , there are few proposals for
dealing with uncertainty by using _disjunctive logic programs_ [Lukasiewicz
(2001), Gergatsoulis et al. (2001), Mateis (2000), Baral et al. (2009)]:

  * •

In [Lukasiewicz (2001)], Many-Valued Disjunctive Logic Programs with
_probabilistic semantics_ are introduced. In this approach, _probabilistic
values_ are associated with each clause. Like our approach, Lukasiewicz
considers partial evaluation for characterizing different semantics by means
of probabilistic theory.

  * •

In [Gergatsoulis et al. (2001)], the logic programming language _Disjunctive
Chronolog_ is introduced. This approach combines _temporal and disjunctive
logic programming_. Disjunctive Chronolog is capable of expressing dynamic
behaviour as well as uncertainty. In this approach, like our semantics, it is
shown that logic semantics of these programs can be characterized by a fixed-
point semantics.

  * •

In [Mateis (2000)], the Quantitative Disjunctive Logic Programs (QDLP) are
introduced. These programs associate an reliability interval with each clause.
Different triangular norms (T-norms) are employed to define calculi for
propagating uncertainty information from the premises to the conclusion of a
quantitative rule; hence, the semantics of these programs is parameterized.
This means that each choice of a T-norm induces different QDLP languages.

  * •

In [Baral et al. (2009)], intensive research is done in order to achieve a
complete integration between ASP and probability theory. This approach is
similar to the approach presented in this paper; but it is in the context of
probabilistic theory.

We want to point out that the syntactic approach of this paper is motivated by
the fact that the possibilistic logic is axiomatizable; therefore, a proof
theory approach (axioms and inference rules) leads to constructions of a
possibilistic semantics such as a logic inference. This kind of possibilistic
framework allows us to explore extensions of the possibilistic answer set
semantics by considering the inference of different logics. In fact, by
considering a syntactic approach, one can explore properties such as _strong
equivalence_ and _free-syntax programs_. This means that the exploration of a
syntactic approach leads to important implications such as the implications of
an approach based on interpretations and possibilistic distributions.

The consideration of axiomatizations of given logics has shown to be a generic
approach for characterizing logic programming semantics. For instance, the
answer set semantics inference can be characterized as _a logic inference_ in
terms of the proof theory of intuitionistic logic and intermediate logics
[Pearce (1999), Osorio et al. (2004)].

##  7 Conclusions and future work

At the beginning of this research, two main goals were expected to be
achieved: 1.- a possibilistic extension of the answer set programming paradigm
for leading with uncertain, inconsistent and incomplete information; and, 2.-
exploring the axiomatization of possibilistic logic in order to define a
computable possibilistic disjunctive semantics.

In order to achieve the first goal, the work presented in [Nicolas et al.
(2006)] was taken as a reference point. Unlike the approach of [Nicolas et al.
(2006)], which is restricted to _possibilistic normal programs_ , we define a
possibilistic logic programming framework based on _possibilistic disjunctive
logic programs_. Our approach introduces the use of possibilistic disjunctive
clauses which are able to capture _incomplete information_ and _incomplete
states of a knowledge base_ at the same time.

For capturing the semantics of possibilistic disjunctive logic programs, the
axiomatization of possibilistic logic and the standard definition of the
answer set semantics are taken as a base. Given that the inference of
possibilistic logic is characterized by a possibilistic resolution rule
(Proposition 6), it is shown that:

  1. 1.

The optimal certainty value of an atom which belongs to a possibilistic answer
set corresponds to the optimal refutation by possibilistic resolution
(Proposition 7); hence,

  2. 2.

There exists an algorithm for computing the possibilistic answer sets of a
possibilistic disjunctive logic program (Proposition 8).

As an alternative approach for inferring the possibilistic answer set
semantics, it is shown that this semantics can be characterized by a
simplified version of _the principle of partial evaluation_. This means that
the possibilistic answer set semantics is characterized by a possibilistic
fixed-point operator (Proposition 10). This result gives two points of view
for constructing the possibilistic answer set semantics in terms of two
_syntactic processes_ (_i.e._ , the possibilistic proof theory and the
principle of partial evaluation).

Based on the flexibility of possibilistic logic for defining degrees of
uncertainty, it is shown that non-numerical degrees for capturing uncertain
information can be captured by the defined possibilistic answer set semantics.
This is illustrated in a medical scenario.

To manage the inconsistency of possibilistic models, we have defined a
criterion of preference between possibilistic answer sets. Also, to manage the
non-existence of possibilistic answer set of a possibilistic logic program
$P$, we have adopted the approach suggested by Nicolas et al.  in [Nicolas et
al. (2006)] of cuts for achieving consistent subprograms of $P$.

In future work, there are several topics which will be explored. One of the
main topics to explore is to show that the possibilistic answer set semantics
can be characterized as a logic inference in terms of a possibilistic version
of the intuitionistic logic. This issue is motivated by the fact that the
answer set semantic inference can be characterized as a logic inference in
terms of intuitionistic logic [Pearce (1999), Osorio et al. (2004)]. On the
other hand, we have been exploring to define a possibilistic action language.
In [Nieves et al. (2007)], we have already defined our first ideas in the
context of the action language ${\mathcal{}A}$. Finally, we have started to
explore the definition of a possibilistic framework in order to define
preference between rules and preferences between atoms. With this objective in
mind, possibilistic ordered disjunction programs have been explored
[Confalonieri et al. (2010)].

## References

  * Alsinet et al. (2008) Alsinet, T., Chesñevar, C. I., Godo, L., and Simari, G. R. 2008\.  A logic programming framework for possibilistic argumentation: Formalization and logical properties.  Fuzzy Sets and Systems 159, 10, 1208–1228.
  * Alsinet and Godo (2000) Alsinet, T. and Godo, L. 2000\.  A Complete Calculus for Possibilistic Logic Programming with Fuzzy Propositional Variables.  In Proceedings of the Sixteen Conference on Uncertainty in Artificial Intelligence. ACM Press, 1-10.
  * Alsinet and Godo (2002) Alsinet, T. and Godo, L. 2002\.  Towards an automated deduction system for first-order possibilistic logic programming with fuzzy constants.  Int. J. Intell. Syst. 17, 9, 887–924.
  * Baldwin (1987) Baldwin, J. F. 1987\.  Evidential support logic programming.  Fuzzy Sets and Systems 24, 1 (October), 1–26.
  * Baral (2003) Baral, C. 2003\.  Knowledge Representation, Reasoning and Declarative Problem Solving.  Cambridge University Press, Cambridge.
  * Baral et al. (2009) Baral, C., Gelfond, M., and Rushton, J. N. 2009\.  Probabilistic reasoning with answer sets.  TPLP 9, 1, 57–144.
  * Brass and Dix (1997) Brass, S. and Dix, J. 1997\.  Characterizations of the disjunctive stable semantics by partial evaluation.  J. Log. Program. 32, 3, 207–228.
  * Brass and Dix (1998) Brass, S. and Dix, J. 1998\.  Characterizations of the disjunctive well-founded semantics: Confluent calculi and iterated gcwa.  J. Autom. Reasoning 20, 1, 143–165.
  * Brass and Dix (1999) Brass, S. and Dix, J. 1999\.  Semantics of (Disjunctive) Logic Programs Based on Partial Evaluation.  Journal of Logic Programming 38(3), 167–213.
  * Bueno (2006) Bueno, O. 2006\.  Knowledge and Inquiry : Essays on the Pragmatism of Isaac Levi.  Cambridge Studies in Probability, Induction and Decision Theory. Cambridge University Press, Chapter Why Inconsistency Is Not Hell: Making Room for Inconsistency in Science, 70–86.
  * Confalonieri et al. (2010) Confalonieri, R., Nieves, J. C., Osorio, M., and Vázquez-Salceda, J. 2010\.  Possibilistic semantics for logic programs with ordered disjunction.  In FoIKS. Lecture Notes in Computer Science, vol. 5956. Springer, 133–152.
  * Davey and Priestly (2002) Davey, B. A. and Priestly, H. A. 2002\.  Introduction to Lattices and Order, Second ed.  Cambridge University Press.
  * Dix (1995a) Dix, J. 1995a.  A classification theory of semantics of normal logic programs: I. strong properties.  Fundam. Inform. 22, 3, 227–255.
  * Dix (1995b) Dix, J. 1995b.  A classification theory of semantics of normal logic programs: II. weak properties.  Fundam. Inform. 22, 3, 257–288.
  * Dix et al. (2001) Dix, J., Osorio, M., and Zepeda, C. 2001\.  A general theory of confluent rewriting systems for logic programming and its applications.  Ann. Pure Appl. Logic 108, 1-3, 153–188.
  * DLV (1996) DLV, S. 1996\.  Vienna University of Technology.  http://www.dbai.tuwien.ac.at/proj/dlv/.
  * Dubois et al. (1991) Dubois, D., Lang, J., and Prade, H. 1991\.  Towards possibilistic logic programming.  In ICLP, K. Furukawa, Ed. The MIT Press, 581–595.
  * Dubois et al. (1994) Dubois, D., Lang, J., and Prade, H. 1994\.  Possibilistic logic.  In Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 3: Nonmonotonic Reasoning and Uncertain Reasoning, D. Gabbay, C. J. Hogger, and J. A. Robinson, Eds. Oxford University Press, Oxford, 439–513.
  * Dubois and Prade (2004) Dubois, D. and Prade, H. 2004\.  Possibilistic logic: a retrospective and prospective view.  Fuzzy Sets and Systems 144, 1, 3–23.
  * Fitting (1991) Fitting, M. 1991\.  Bilattices and the semantics of logic programming.  Journal of Logic Programming 11, 1&2, 91–116.
  * Fox and Das (2000) Fox, J. and Das, S. 2000\.  Safe and Sound: Artificial Intelligence in Hazardous Applications.  AAAI Press/ The MIT Press.
  * Fox and Modgil (2006) Fox, J. and Modgil, S. 2006\.  From arguments to decisions: Extending the Toulmin view.  In Arguing on the Toulmin model: New essays on argument analysis and evaluation, D. Hitchcock and B. Verheij, Eds. Springer Netherlands, 273–287.
  * Gelfond (2008) Gelfond, M. 2008\.  Handbook of Knowledge Representation.  Elsevier, Chapter Answer Sets, 285–316.
  * Gelfond and Lifschitz (1988) Gelfond, M. and Lifschitz, V. 1988\.  The Stable Model Semantics for Logic Programming.  In 5th Conference on Logic Programming, R. Kowalski and K. Bowen, Eds. MIT Press, 1070–1080.
  * Gelfond and Lifschitz (1991) Gelfond, M. and Lifschitz, V. 1991\.  Classical Negation in Logic Programs and Disjunctive Databases.  New Generation Computing 9, 365–385.
  * Gergatsoulis et al. (2001) Gergatsoulis, M., Rondogiannis, P., and Panayiotopoulos, T. 2001\.  Temporal disjunctive logic programming.  New Generation Computing 19, 1, 87–100.
  * Kern-Isberner and Lukasiewicz (2004) Kern-Isberner, G. and Lukasiewicz, T. 2004\.  Combining probabilistic logic programming with the power of maximum entropy.  Artificial Intelligence 157, 1-2, 139–202.
  * Kifer and Subrahmanian (1992) Kifer, M. and Subrahmanian, V. S. 1992\.  Theory of generalized annotated logic programming and its applications.  J. Log. Program. 12, 3&4, 335–367.
  * Lakshmanan (1994) Lakshmanan, L. V. S. 1994\.  An epistemic foundation for logic programming with uncertainty.  In FSTTCS. 89–100.
  * López-Navidad and Caballero (2003) López-Navidad, A. and Caballero, F. 2003\.  Extended criteria for organ acceptance: Strategies for achieving organ safety and for increasing organ pool.  Clinical Transplantation, Blackwell Munksgaard 17, 308–324.
  * López-Navidad et al. (1997) López-Navidad, A., Domingo, P., and Viedma, M. A. 1997\.  Professional characteristics of the transplant coordinator.  In XVI International Congress of the Transplantation Society. Transplantation Proceedings, vol. 29. Elsevier Science Inc, 1607–1613.
  * Lukasiewicz (1998) Lukasiewicz, T. 1998\.  Probabilistic logic programming.  In ECAI. 388–392.
  * Lukasiewicz (2001) Lukasiewicz, T. 2001\.  Fixpoint characterizations for many-valued disjunctive logic programs with probabilistic semantics.  In LPNMR. 336–350.
  * Mateis (2000) Mateis, C. 2000\.  Quantitative disjunctive logic programming: Semantics and computation.  AI Commun. 13, 4, 225–248.
  * Ng and Subrahmanian (1992) Ng, R. T. and Subrahmanian, V. S. 1992\.  Probabilistic logic programming.  Inf. Comput. 101, 2, 150–201.
  * Nicolas et al. (2006) Nicolas, P., Garcia, L., Stéphan, I., and Lefèvre, C. 2006\.  Possibilistic Uncertainty Handling for Answer Set Programming.  Annals of Mathematics and Artificial Intelligence 47, 1-2 (June), 139–181.
  * Nieves et al. (2007a) Nieves, J. C., Osorio, M., and Cortés, U. 2007a.  Semantics for possibilistic disjunctive programs.  In Ninth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-07), C. Baral, G. Brewka, and J. Schlipf, Eds. Number 4483 in LNAI. Springer-Verlag, 315–320.
  * Nieves et al. (2007b) Nieves, J. C., Osorio, M., and Cortés, U. 2007b.  Semantics for possibilistic disjunctive programs.  In Answer Set Programming: Advances in Theory and Implementation, S. Costantini and R. Watson, Eds. 271–284.
  * Nieves et al. (2007) Nieves, J. C., Osorio, M., Cortés, U., Caballero, F., and López-Navidad, A. 2007\.  Reasoning about actions under uncertainty: A possibilistic approach.  In In proceedings of CCIA, C. Angulo and L. Godo, Eds.
  * Osorio et al. (2004) Osorio, M., Navarro, J. A., and Arrazola, J. 2004\.  Applications of Intuitionistic Logic in Answer Set Programming.  Theory and Practice of Logic Programming (TPLP) 4, 3 (May), 225–354.
  * Pearce (1999) Pearce, D. 1999\.  Stable Inference as Intuitionistic Validity.  Logic Programming 38, 79–91.
  * Rodríguez-Artalejo and Romero-Díaz (2008) Rodríguez-Artalejo, M. and Romero-Díaz, C. A. 2008\.  Quantitative Logic Programming revisited.  In 9th International Symposium, FLOPS, J. Garrigue and M. Hermenegildo, Eds. LNCS, vol. 4989. Springer-Verlag Berlin Heidelberg, 272–288.
  * Tarski (1955) Tarski, A. 1955\.  A lattice-theoretical fixpoint theorem and its applications.  Pacific Journal of Mathematics 5, 2, 285–309.
  * Tversky and Kahneman (1982) Tversky, A. and Kahneman, D. 1982\.  Judgment under uncertainty:Heuristics and biases.  Cambridge University Press, Chapter Judgment under uncertainty:Heuristics and biases, 3–20.
  * van Dalen (1994) van Dalen, D. 1994\.  Logic and structure, 3rd., aumented edition ed.  Springer-Verlag, Berlin.
  * van Emden (1986) van Emden, M. H. 1986\.  Quantitative deduction and its fixpoint theory.  Journal of Logic Programming 3, 1, 37–53.
  * Van-Nieuwenborgh et al. (2007) Van-Nieuwenborgh, D., Cock, M. D., and Vermeir, D. 2007\.  An introduction to fuzzy answer set programming.  Ann. Math. Artif. Intell. 50, 3-4, 363–388.

## Appendix: Proofs

In this appendix, we give the proofs of some results presented in this paper.

Proposition 2 Let $P=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic
disjunctive logic program and $M_{1},M_{2}\in{\mathcal{}PS}$ such that
$M_{1}^{*}=M_{2}^{*}$. If $P\Vvdash_{PL}M1$ and $P\Vvdash_{PL}M2$, then
$P\Vvdash_{PL}M_{1}\sqcup M_{2}$.

######  Proof 7.1.

The proof is straightforward.

Proposition 3 Let $P$ be a possibilistic disjunctive logic program. If $M$ is
a possibilistic answer set of P then $M^{*}$ is an answer set of $P^{*}$.

######  Proof 7.2.

The proof is straightforward by the possibilistic answer set’s definition.

Proposition 4 Let $P=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic
disjunctive logic program and $\alpha$ be a fixed element of ${\mathcal{}Q}$.
If $\forall r\in P$, $n(r)=\alpha$ and $M^{\prime}$ is an answer set of
$P^{*}$, then $M:=\\{(a,\alpha)|a\in M^{\prime}\\}$ is a possibilistic answer
set of $P$.

######  Proof 7.3.

Let us introduce two observations:

  1. 1.

We known that $\forall r\in P$, $n(r)=\alpha$; hence, if
$P\vdash_{PL}(a,\alpha^{\prime})$, then $\alpha^{\prime}=\alpha$. This
statement can be proved by contradiction.

  2. 2.

Given a set of atoms $S$, if $\forall r\in P$, $n(r)=\alpha$ then $\forall
r\in P_{S}$, $n(r)=\alpha$. This statement follows by fact that the reduction
$P_{S}$ (Definition 6) does not affect $n(r)$ of clause rule $r$ in $P$.

As premises we know that $\forall r\in P$, $n(r)=\alpha$ and $M^{\prime}$ is
an answer set of $P^{*}$; hence, let $M:=\\{(a,\alpha)|a\in M^{\prime}\\}$.
Hence, we will prove that $M$ is a possibilistic answer set of $P$.

If $M^{\prime}$ is an answer set of $P^{*}$, then $\forall a\in M^{\prime}$,
$\exists\alpha^{\prime}\in{\mathcal{}Q}$ such that
$P_{M^{\prime}}\vdash_{PL}(a,\alpha^{\prime})$. Therefore, by observations 1
and 2, $\forall a\in M^{\prime}$, $P_{M^{\prime}}\vdash_{PL}(a,\alpha)$. Then,
$P\Vvdash_{PL}M$. Observe that $M$ is a greatest set in ${\mathcal{}PS}$,
hence, since $P\Vvdash_{PL}M$ and $M$ is a greatest set, $M$ is a
possibilistic answer set of $P$.

Proposition 5 Let $P:=\langle(Q,\leq),N\rangle$ be a possibilistic normal
program such that $(Q,\leq)$ is a totally ordered set and ${\mathcal{}L}_{P}$
has no extended atoms. $M$ is a possibilistic answer set of P if and only if
$M$ is a possibilistic stable model of $P$.

######  Proof 7.4.

(Sketch) It is not difficult to see that when $P$ is a possibilistic normal
program, then the syntactic reduction of Definition 6 and the syntactic
reduction of Definition 10 from [Nicolas et al. (2006)] coincide. Then the
proof is reduced to possibilistic definite programs. But, this case is
straightforward, since essentially GMP is applied for inferring the
possibilistic models of the program in both approaches.

Proposition 6 Let ${\mathcal{}C}$ be a set of possibilistic disjunctions, and
$C=(c\;\alpha)$ be a possibilistic clause obtained by a finite number of
successive application of _(R)_ to ${\mathcal{}C}$; then
${\mathcal{}C}\vdash_{PL}C$.

######  Proof 7.5.

(The proof is similar to the proof of Proposition 3.8.2 of [Dubois et al.
(1994)]) Let us consider two possibilistic clauses:
$C_{1}=(c_{1}\;\alpha_{1})$ and $C_{2}=(c_{2}\;\alpha_{2})$, the application
of $R$ yields
$C^{\prime}=(R(c_{1},c_{2})\;{\mathcal{}GLB}(\\{\alpha_{1},\alpha_{2}\\}))$.
By classic logic, we known that $R(c_{1},c_{2})$ is sound; hence the key point
of the proof is to show that
$n(R(c_{1},c_{2}))\geq{\mathcal{}GLB}(\\{\alpha_{1},\alpha_{2}\\})$.

By definition of necessity-valued clause, $n(c_{1})\geq\alpha_{1}$ and
$n(c_{2})\geq\alpha_{2}$, then $n(c_{1}\wedge
c_{2})={\mathcal{}GLB}(\\{n(c_{1}),n(c_{2})\\})\geq{\mathcal{}GLB}(\\{\alpha_{1},\alpha_{2}\\})$.
Since $c_{1}\wedge c_{2}\vdash_{C}R(c_{1},c_{2})$, then $n(R(c_{1},c_{2}))\geq
n(c_{1}\wedge c_{2})$ (because if $\varphi\vdash_{PL}\psi$ then $N(\psi)\geq
N(\varphi)$). Thus
$n(R(c_{1},c_{2}))\geq{\mathcal{}GLB}(\\{\alpha_{1},\alpha_{2}\\})$; therefore
(R) is sound. Then by induction any possibilistic formula inferred by a finite
number of successive applications of (R) to ${\mathcal{}C}$ is a logical
consequence of ${\mathcal{}C}$.

Proposition 7 Let $P$ be a set of possibilistic clauses and ${\mathcal{}C}$ be
the set of possibilistic disjunctions obtained from $P$; then the valuation of
the optimal refutation by resolution from ${\mathcal{}C}$ is the inconsistent
degree of $P$.

######  Proof 7.6.

(The proof is similar to the proof of Proposition 3.8.3 of [Dubois et al.
(1994)]) By possibilistic logic, we know that
${\mathcal{}C}\vdash_{PL}(\bot\;\alpha)$ if and only if
$({\mathcal{}C}_{\alpha})^{*}$ is inconsistent in the sense of classic logic.
Since (R) is complete in classic logic, then there exists a refutation
$R(\square)$ from $({\mathcal{}C}_{\alpha})^{*}$. Thus considering the
valuation of the refutation $R(\square)$, we obtain a refutation from
${\mathcal{}C}_{\alpha}$ such that $n(R(\square))\geq\alpha$. Then
$n(R(\square))\geq Inc({\mathcal{}C})$. Since (R) is sound then
$n(R(\square))$ cannot be strictly greater than $Inc({\mathcal{}C})$. Thus
$n(R(\square))$ is equal to $Inc({\mathcal{}C})$. According to Proposition
3.8.1 of [Dubois et al. (1994)], $Inc({\mathcal{}C})=Inc(P)$, thus
$n(R(\square))$ is also equal to $Inc(P)$.

Proposition 8 Let $P:=\langle({\mathcal{}Q},\leq),N\rangle$ be a possibilistic
logic program. The set Poss-ASP returned by $Poss\\_Answer\\_Sets(P)$ is the
set of all the possibilistic answer sets of $P$.

######  Proof 7.7.

The result follows from the following facts:

  1. 1.

The function $ASP$ computes all the answer set of $P^{*}$.

  2. 2.

If $M$ is a possibilistic answer set of P iff $M^{*}$ is an answer set of
$P^{*}$ (Proposition 3).

  3. 3.

By Corollary 1, we know that the possibilistic resolution rule $R$ is sound
and complete for computing optimal possibilistic degrees.

Proposition 9 Let $P$ be a possibilistic disjunctive logic program. If
$\Gamma_{0}:={\mathcal{}T}(P)$ and $\Gamma_{i}:={\mathcal{}T}(\Gamma_{i-1})$
such that $i\in{\mathcal{}N}$, then $\exists\;n\in{\mathcal{}N}$ such that
$\Gamma_{n}=\Gamma_{n-1}$. We denote $\Gamma_{n}$ by $\Pi(P)$.

######  Proof 7.8.

It is not difficult to see that the operator ${\mathcal{}T}$ is monotonic,
then the proof is direct by Tarski’s Lattice-Theoretical Fixpoint Theorem
[Tarski (1955)].

Proposition 10 Let $P$ be a possibilistic disjunctive logic program and $M$ a
set of possibilistic atoms. $M$ is a possibilistic answer set of $P$ if and
only if $M$ is a possibilistic-${\mathcal{}T}$ answer set of $P$.

######  Proof 7.9.

Two observations:

  1. 1.

By definition, it is straightforward that if $M_{1}$ is a possibilistic answer
set of $P$, then there exists a possibilistic-${\mathcal{}T}$ answer set
$M_{2}$ of $P$ such that $M_{1}^{*}=M_{2}^{*}$ and viceversa.

  2. 2.

Since G-GPPE can be regarded as a macro of the possibilistic rule $(R)$, we
can conclude by Proposition 6 that G-GPPE is sound.

Let $M_{1}$ be a possibilistic answer set of $P$ and $M_{2}$ be a
possibilistic-${\mathcal{}T}$ answer set of $P$. By Observation 1, the central
point of the proof is to prove that if $(a,\alpha_{1})\in M_{1}$ and
$(a,\alpha_{2})\in M_{2}$ such that $M_{1}^{*}=M_{2}^{*}$, then
$\alpha_{1}=\alpha_{2}$.

The proof is by contradiction. Let us suppose that $(a,\alpha_{1})\in M_{1}$
and $(a,\alpha_{2})\in M_{2}$ such that $M_{1}^{*}=M_{2}^{*}$ and
$\alpha_{1}\neq\alpha_{2}$. Then there are two cases $\alpha_{1}<\alpha_{2}$
or $\alpha_{1}>\alpha_{2}$

$\alpha_{1}<\alpha_{2}$

: Since G-GPPE is sound (Observation 2), then $\alpha_{1}$ is not the optimal
necessity-value for the atom $a$, but this is false by Corollary 1.

$\alpha_{1}>\alpha_{2}$

: If $\alpha_{1}>\alpha_{2}$ then there exists a possibilistic claus
$\alpha_{1}:{\mathcal{}A}\leftarrow{\mathcal{}B}^{+}\in P^{(M_{1})^{*}}$ that
belongs to the optimal refutation of the atom $a$ and it was not reduced by
G-GPPE. But this is false because G-GPPE is a macro of the resolution rule
(R).