# Human Conditional Reasoning in Answer Set Programming

CHIAKI SAKAMA

###### Abstract

Given a conditional sentence $\varphi\Rightarrow\psi$ (if $\varphi$ then
$\psi$) and respective facts, four different types of inferences are observed
in human reasoning. Affirming the antecedent (AA) (or modus ponens) reasons
$\psi$ from $\varphi$; affirming the consequent (AC) reasons $\varphi$ from
$\psi$; denying the antecedent (DA) reasons $\neg\psi$ from $\neg\varphi$; and
denying the consequent (DC) (or modus tollens) reasons $\neg\varphi$ from
$\neg\psi$. Among them, AA and DC are logically valid, while AC and DA are
logically invalid and often called logical fallacies. Nevertheless, humans
often perform AC or DA as pragmatic inference in daily life. In this paper, we
realize AC, DA and DC inferences in answer set programming. Eight different
types of completion are introduced and their semantics are given by answer
sets. We investigate formal properties and characterize human reasoning tasks
in cognitive psychology. Those completions are also applied to commonsense
reasoning in AI.

Under consideration in Theory and Practice of Logic Programming (TPLP)

###### keywords:

answer set programming, completion, human conditional reasoning, pragmatic
inference

##  1 Introduction

People use conditional sentences and reason with them in everyday life. From
an early stage of artificial intelligence (AI), researchers represent
conditional sentences as if-then rules and perform deductive inference using
them. Production systems or logic programming are examples of this type of
systems. However, human conditional reasoning is not always logically valid.
In psychology and cognitive science, it is well known that humans are more
likely to perform logically invalid but pragmatic inference. For instance,
consider the following three sentences:

$S$: If the team wins the first round tournament, then it advances to the
final round.

$P$: The team wins the first round tournament.

$C$: The team advances to the final round.

Given the conditional sentence $S$ and the premise $P$, affirming the
antecedent (AA) (or modus ponens) concludes the consequence $C$. Given $S$ and
the negation of the consequence $\neg\,C$, denying the consequent (DC) (or
modus tollens) concludes the negation of the premise $\neg\,P$. AA and DC are
logically valid. On the other hand, people often infer $P$ from $S$ and $C$ or
infer $\neg\,C$ from $S$ and $\neg\,P$. The former is called affirming the
consequent (AC) and the latter is called denying the antecedent (DA). Both AC
and DA are logically invalid and often called logical fallacies.

In the pragmatics of conditional reasoning, it is assumed that a conditional
sentence is often interpreted as bi-conditional, that is, ‘if’ is interpreted
as ‘if and only if’, and such conditional perfection produces AC or DA as
invited inference (Geis and Zwicky, (1971); Horn, (2000)). Psychological
studies empirically show that a conditional sentence “$p$ if $q$” is rephrased
into the form “$p$ only if $q$” with greater frequency for
permission/obligation statements (Cheng and Holyoak, (1985); Byrne, (2005)).
For instance, the sentence “a customer can drink an alcoholic beverage if he
is over 18” is rephrased into “a customer can drink an alcoholic beverage only
if he is over 18”. It is also reported that AA is easier than DC when a
conditional is given as “if $p$ then $q$”. When a conditional is given as “$p$
only if $q$”, on the other hand, it is rephrased as “if not $q$ then not $p$”
and this paraphrase yields a directionality opposite which makes DC easier
than AA (Braine, (1978)). The fact that people do not necessarily make
inferences as in standard logic brings several proposals of new interpretation
of conditional sentences in cognitive psychology. Mental logic (Braine and
O’Brien, (1998)) interprets ‘if’ as conveying supposition and introduces a set
of pragmatic inference schemas for if-conditionals. Mental model theory
(Johnson-Laird, (1983)), on the other hand, considers that the meanings of
conditionals are not truth-functional, and represents the meaning of a
conditional sentence by models of the possibilities compatible with the
sentence. A probabilistic approach interprets a conditional sentence
$p\Rightarrow q$ in terms of conditional probability $P(q\mid p)$, then the
acceptance rates of four conditional inferences are represented by their
respective conditional probabilities (Oaksford and Chater, (2001)). Eichhorn
et al., (2018) use conditional logic and define inference patterns as
combination (AA, DC, AC, DA) of four inference rules. Given a conditional
sentence “if $p$ then $q$”, four possible worlds (combination of truth values
of $p$ and $q$) are considered. An inference in each pattern is then defined
by imposing corresponding constraints on the plausibility relation over the
worlds.

In this way, the need of considering the pragmatics of conditional reasoning
has been widely recognized in psychology and cognitive science. On the other
hand, relatively little attention has been paid for realizing such pragmatic
inferences in computational logic or logic programming (Stenning and
Lambalgen, (2008); Kowalski, (2011)). From a practical perspective, however,
people would expect AI to reason like humans, that is, one would expect AI to
conclude $P$ from $S$ and $C$, or $\neg\,C$ from $S$ and $\neg\,P$ in the
introductory example, rather than conclude $unknown$. Logic programming is a
context-independent language and has a general-purpose inference mechanism by
its nature. By contrast, pragmatic inference is governed by context-sensitive
mechanisms, rather than context-free and general-purpose mechanisms (Cheng and
Holyoak, (1985); Cosmides and Tooby, (1992)). As argued by Dietz et al.,
(2012), computational approaches to explain human reasoning should be
cognitively adequate, that is, they appropriately represent human knowledge
(conceptually adequate) and computations behave similarly to human reasoning
(inferentially adequate). Then if we use logic programming for representing
knowledge in daily life, it is useful to have a mechanism of automatic
transformation of a knowledge base to simulate human reasoning depending on
the context in which conditional sentences are used. That is, transform a
program to a conceptually adequate form in order to make computation in the
program inferentially adequate.

In this paper, we realize human conditional reasoning in answer set
programming (ASP) (Gelfond and Lifschitz, (1991)). ASP is one of the most
popular frameworks that realize declarative knowledge representation and
commonsense reasoning. ASP is a language of logic programming and conditional
sentences are represented by rules in a program. Inference in ASP is deduction
based on default logic (Reiter, (1980)), while modus tollens or DC is not
considered in ASP. AC and DA are partly realized by abductive logic
programming (Kakas et al., (1992)) and program completion (Clark, (1978)),
respectively. As will be argued in this paper, however, AC and DA produce
different results from them in general. We realize pragmatic AC and DA
inferences as well as DC inference in ASP in a uniform and modular way. We
introduce the notions of AC completion, DC completion, DA completion and their
variants. We investigate formal properties of those completions and
characterize human reasoning tasks in cognitive psychology. We also address
applications to commonsense reasoning in AI. The rest of this paper is
organized as follows. Section 2 reviews basic notions of ASP programs
considered in this paper. Section 3 introduces different types of completions
for human conditional reasoning, and Section 4 presents their variance as
default reasoning. Section 5 characterizes human reasoning tasks in the
literature, and Section 6 addresses applications to commonsense reasoning.
Section 7 discusses related works and Section 8 summarizes the paper.

##  2 Preliminaries

In this paper, we consider logic programs with disjunction, default negation,
and explicit negation. A general extended disjunctive program (GEDP)
(Lifschitz and Woo, (1992); Inoue and Sakama, (1998)) is a set of rules of the
form:

$\displaystyle
L_{1}\,;\,\cdots\,;\,L_{k}\,;\,not\,L_{k+1}\,;\cdots;\,not\,L_{l}$
$\displaystyle\quad\qquad\leftarrow\;L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}\;\;$
(1)

where $L_{i}$’s $(1\leq i\leq n)$ are (positive or negative) literals and
$0\leq k\leq l\leq m\leq n$. A program might contain two types of negation:
default negation (or negation as failure) $not$ and explicit negation $\neg$.
For any literal $L$, $not\,L$ is called an NAF-literal and define $\neg\neg
L=L$. We often use the letter $\ell$ to mean either a literal $L$ or an NAF-
literal $not\,L$. The left of $\leftarrow$ is a disjunction of literals and
NAF-literals (called head), and the right of $\leftarrow$ is a conjunction of
literals and NAF-literals (called body). Given a rule $r$ of the form (2),
define $head^{+}(r)=\\{L_{1},\ldots,L_{k}\\}$,
$head^{-}(r)=\\{L_{k+1},\ldots,L_{l}\\}$,
$body^{+}(r)=\\{L_{l+1},\ldots,L_{m}\\}$, and
$body^{-}(r)=\\{L_{m+1},\ldots,L_{n}\\}$. A rule (2) is called a fact if
$body^{+}(r)=body^{-}(r)=\varnothing$; and it is called a constraint if
$head^{+}(r)=head^{-}(r)=\varnothing$. A GEDP $\Pi$ is called $not$-free if
$head^{-}(r)=body^{-}(r)=\varnothing$ for each rule $r$ in $\Pi$.

A GEDP $\Pi$ coincides with an extended disjunctive program (EDP) of (Gelfond
and Lifschitz, (1991)) if $head^{-}(r)=\varnothing$ for any rule $r$ in $\Pi$.
An EDP $\Pi$ is called (i) an extended logic program (ELP) if
$\mid\\!head^{+}(r)\\!\mid\,\leq 1$ for any $r\in\Pi$; and (ii) a normal
disjunctive program (NDP) if $\Pi$ contains no negative literal. An NDP $\Pi$
is called (i) a positive disjunctive program (PDP) if $\Pi$ contains no NAF-
literal; and (ii) a normal logic program (NLP) if
$\mid\\!head^{+}(r)\\!\mid\,\leq 1$ for any $r\in\Pi$. In this paper, we
consider ground programs containing no variable and a program means a (ground)
GEDP unless stated otherwise.

Let $Lit$ be the set of all ground literals in the language of a program. A
set of ground literals $S\subseteq Lit$ satisfies a ground rule $r$ of the
form (2) iff $body^{+}(r)\subseteq S$ and $body^{-}(r)\cap S=\varnothing$
imply either $head^{+}(r)\cap S\neq\varnothing$ or $head^{-}(r)\not\subseteq
S$. The answer sets of a GEDP are defined by the following two steps. First,
let $\Pi$ be a $not$-free GEDP and $S\subseteq Lit$. Then, $S$ is an answer
set of $\Pi$ iff $S$ is a minimal set satisfying the conditions: (i) $S$
satisfies every rule from $\Pi$, that is, for each ground rule:

$L_{1}\,;\,\cdots\,;\,L_{k}\leftarrow L_{l+1},\,\ldots,\,L_{m}$ (2)

from $\Pi$, $\\{L_{l+1},\ldots,L_{m}\\}\subseteq S$ implies
$\\{L_{1},\ldots,L_{k}\\}\cap S\neq\varnothing$. In particular, for each
constraint

$\mbox{}\leftarrow L_{l+1},\,\ldots,\,L_{m}$

from $\Pi$, $\\{L_{l+1},\ldots,L_{m}\\}\not\subseteq S$. (ii) If $S$ contains
a pair of complementary literals $L$ and $\neg L$, then $S=Lit$.

Second, let $\Pi$ be any GEDP and $S\subseteq Lit$. The reduct $\Pi^{S}$ of
$\Pi$ by $S$ is a $not$-free EDP obtained as follows: a rule $r^{S}$ of the
form (2) is in $\Pi^{S}$ iff there is a ground rule $r$ of the form (2) from
$\Pi$ such that $head^{-}(r)\subseteq S$ and $body^{-}(r)\cap S=\varnothing$.
For programs of the form $\Pi^{S}$, their answer sets have already been
defined. Then, $S$ is an answer set of $\Pi$ iff $S$ is an answer set of
$\Pi^{S}$.

When a program $\Pi$ is an EDP, the above definition of answer sets coincides
with that given in (Gelfond and Lifschitz, (1991)). It is shown that every
answer set of a GEDP $\Pi$ satisfies every rule from $\Pi$ (Inoue and Sakama,
(1998)). An answer set is consistent if it is not $Lit$. A program $\Pi$ is
consistent if it has a consistent answer set; otherwise, $\Pi$ is
inconsistent. When a program $\Pi$ is inconsistent, there are two different
cases. If $\Pi$ has the answer set $Lit$, $\Pi$ is called contradictory; else
if $\Pi$ has no answer set, $\Pi$ is called incoherent. The difference of two
cases is illustrated by the following example.

###### Example 2.1

The program $\Pi_{1}=\\{\,p\leftarrow not\,q,\;\;\neg p\leftarrow\,\\}$ is
incoherent, while $\Pi_{2}=\\{\,p\leftarrow q,\;\;q\leftarrow,\;\;\neg
p\leftarrow\,\\}$ is contradictory. Note that $Lit$ is not the answer set of
$\Pi_{1}$ because $Lit$ is not the answer set of $\Pi_{1}^{Lit}=\\{\,\neg
p\leftarrow\,\\}$.

We write $\Pi\models_{c}L$ (resp. $\Pi\models_{s}L$ ) if a literal $L$ is
included in some (resp. every) consistent answer set of $\Pi$. Two programs
$\Pi_{1}$ and $\Pi_{2}$ are equivalent if they have the same set of answer
sets. Two programs $\Pi_{1}$ and $\Pi_{2}$ are strongly equivalent if
$\Pi_{1}\cup\Pi$ and $\Pi_{2}\cup\Pi$ are equivalent for any program $\Pi$
(Lifschitz et al., (2001)). In particular, two rules $r_{1}$ and $r_{2}$ are
strongly equivalent if $\Pi\cup\\{r_{1}\\}$ and $\Pi\cup\\{r_{2}\\}$ are
equivalent for any program $\Pi$.

An answer set of a GEDP is not always minimal, i.e., a program $\Pi$ may have
two answer sets $S$ and $T$ such that $S\subset T$ (Lifschitz and Woo, (1992);
Inoue and Sakama, (1998)). This is in contrast with the case of EDPs where
every answer set is minimal.

###### Example 2.2

Let $\Pi$ be the progam:

$\displaystyle p\,;\,not\,q\leftarrow,$ $\displaystyle
q\,;\,not\,p\leftarrow.$

Then $\Pi$ has two answer sets $\varnothing$ and $\\{p,q\\}$.

Suppose a rule $r$ such that $head^{+}(r)=\varnothing$:

$not\,L_{k+1}\,;\cdots;\,not\,L_{l}\leftarrow\;L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}.$
(3)

Define a rule $\eta(r)$ of the form:

$\leftarrow\;L_{k+1},\,\ldots,\,L_{l},L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}$
(4)

that is obtained by shifting $not\,L_{k+1}\,;\cdots;\,not\,L_{l}$ in
$head^{-}(r)$ to $L_{k+1},\,\ldots,\,L_{l}$ in $body^{+}(\eta(r))$. The two
rules (3) and (4) are strongly equivalent under the answer set semantics.

######  Proposition 2.1 (Inoue and Sakama, (1998))

Let $\Pi$ be a program and $\Phi=\\{\,r\mid
r\in\Pi\;\;\mbox{and}\;\;head^{+}(r)=\varnothing\\}$. Also let
$\Pi^{\prime}=(\Pi\setminus\Phi)\cup\\{\,\eta(r)\mid r\in\Phi\,\\}$. Then
$\Pi$ and $\Pi^{\prime}$ have the same answer sets.

###### Proposition 2.2

Let $\Pi$ be a program and $\Psi=\\{\,r\mid
r\in\Pi,\;head^{+}(r)=\varnothing\;\mbox{and}\;head^{-}(r)\cap
body^{-}(r)\neq\varnothing\\}$. Then, $\Pi$ and $\Pi\setminus\Psi$ have the
same answer sets.

######  Proof 2.1.

By Proposition 2.1, every rule (3) in $\Pi$ is transformed to a strongly
equivalent constraint (4). When $head^{-}(r)\cap body^{-}(r)\neq\varnothing$
for some $r\in\Phi$, there is a literal
$L\in\\{L_{k+1},\ldots,L_{l}\\}\cap\\{L_{m+1},\ldots,L_{n}\\}$ in $\eta(r)$.
However, no answer set satisfies both $L$ and $not\,L$ at the same time, so
the constraint $\eta(r)$ is satisfied. Hence, $\Psi$ is removed from $\Pi$ and
the result follows.

######  Example 2.2.

For any program $\Pi$,

$\Pi\cup\\{\,not\,p\,\leftarrow\,q,not\,p\,\\}$

is equivalent to the following program (Proposition 2.1):

$\Pi\cup\\{\,\leftarrow p,q,not\,p\,\\},$

which is further simplified to $\Pi$ (Proposition 2.2).

######  Proposition 2.3.

Let $\Pi$ be a not-free GEDP. If there is a constraint in $\Pi$, then $\Pi$ is
not contradictory.

######  Proof 2.4.

If there is a constraint $\leftarrow L_{1},\ldots,L_{m}$ in $\Pi$, it is also
included in $\Pi^{Lit}$. Since $Lit$ does not satisfy the constraint, it
cannot be the answer set of $\Pi^{Lit}$. Hence, $\Pi$ is not contradictory.

##  3 Human Conditional Reasoning in ASP

ASP computes answer sets by deduction that is reasoning by AA. In this
section, we present methods for reasoning by AC, DC, and DA in ASP.

###  3.1 AC Completion

We first introduce a framework for reasoning by affirming the consequent (AC)
in ASP. In GEDPs, a conditional sentence $\varphi\Rightarrow\psi$ (if
$\varphi$ then $\psi$) is represented by the rule
$\psi~{}\leftarrow~{}\varphi$ where $\psi$ is a disjunction
“$L_{1}\,;\,\cdots\,;\,L_{k}\,;\,not\,L_{k+1}\,;\cdots;\,not\,L_{l}$” and
$\varphi$ is a conjunction
“$L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}$”. To realize
reasoning backward from $\psi$ to $\varphi$, we extend a program $\Pi$ by
introducing new rules.

######  Definition 3.1 (AC completion).

Let $\Pi$ be a program and $r\in\Pi$ a rule of the form:

$\displaystyle
L_{1}\,;\,\cdots\,;\,L_{k}\,;\,not\,L_{k+1}\,;\cdots;\,not\,L_{l}$
$\displaystyle\quad\qquad\leftarrow\;L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}.\;\;$

  1. 1.

First, for each disjunct in $head^{+}(r)$ and $head^{-}(r)$, converse the
implication:

$\displaystyle
L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}\;\leftarrow\;L_{j}\;\;\;(1\leq
j\leq k),$ (5) $\displaystyle
L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}\;\leftarrow\;not\,L_{j}\;\;\;(k+1\leq
j\leq l).$ (6)

In (5) and (6), the conjunction
“$L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}$” appears on
the left of $\leftarrow$. The produced (5) (resp. (6)) is considered an
abbreviation of the collection of $(n-l)$ rules: $(L_{l+1}\leftarrow
L_{j}),\ldots,(not\,L_{n}\leftarrow L_{j})$ (resp. $(L_{l+1}\leftarrow
not\,L_{j}),\ldots,(not\,L_{n}\leftarrow not\,L_{j})$)111We often use the
parenthesis ‘()’ to improve the readability., hence we abuse the term ‘rule’
and call (5) or (6) a rule. In particular, (5) is not produced if
$head^{+}(r)=\varnothing$ or $body^{+}(r)=body^{-}(r)=\varnothing$; and (6) is
not produced if $head^{-}(r)=\varnothing$ or
$body^{+}(r)=body^{-}(r)=\varnothing$. The set of all rules (5) and (6) is
denoted as $conv(r)$.

  2. 2.

Next, define

$\displaystyle ac(\Pi)$ $\displaystyle\\!=\\!$
$\displaystyle\\{\;\Sigma_{1}\,;\,\cdots\,;\,\Sigma_{p}\;\leftarrow\;\ell_{j}\;\mid$
$\displaystyle\quad\Sigma_{i}\leftarrow\ell_{j}\;\,(1\leq i\leq p)\;\;\mbox{is
in}\;\;\bigcup_{r\in\Pi}\,conv(r)\,\\}$

where each $\Sigma_{i}$ $(1\leq i\leq p)$ is a conjunction of literals and
NAF-literals, and $\ell_{j}$ is either a literal $L_{j}$ $(1\leq j\leq k)$ or
an NAF-literal $not\,L_{j}$ $(k+1\leq j\leq l)$.

  3. 3.

The AC completion of $\Pi$ is then defined as:

$AC(\Pi)=\Pi\;\cup\;ac(\Pi).$

(5) and (6) in $conv(r)$ represent converse implications from the disjunction
in the head of $r$ to the conjunction in the body of $r$. $ac(\Pi)$ collects
rules $\Sigma_{i}\leftarrow\ell_{j}\;\,(1\leq i\leq p)$ having the same
(NAF-)literal $\ell_{j}$ on the right of $\leftarrow$, and constructs
“$\Sigma_{1}\,;\,\cdots\,;\,\Sigma_{p}\;\leftarrow\;\ell_{j}$”, which we call
an extended rule. Introducing $ac(\Pi)$ to $\Pi$ realizes reasoning by AC in
$\Pi$.

The set $ac(\Pi)$ contains an extended rule having a disjunction of
conjunctions in its head, while it is transformed to rules of a GEDP. That is,
the extended rule:

$(\ell^{1}_{1},\ldots,\ell^{1}_{m_{1}})\,;\,\cdots\,;\,(\ell^{p}_{1},\ldots,\ell^{p}_{m_{p}})\leftarrow\ell_{j}$

is identified with the set of $m_{1}\times\cdots\times m_{p}$ rules of the
form:

$\ell^{1}_{i_{1}}\,;\,\cdots\,;\,\ell^{p}_{i_{p}}\leftarrow\ell_{j}\;\;\;\;\;(1\leq
i_{k}\leq m_{k};\,1\leq k\leq p).$

By this fact, $AC(\Pi)$ is viewed as a GEDP and we do not distinguish extended
rules and rules of a GEDP hereafter. The semantics of $AC(\Pi)$ is defined by
its answer sets.

######  Example 3.2.

Let $\Pi$ be the program:

$\displaystyle p\,;\,not\,q\leftarrow r,\,not\,s,$ $\displaystyle p\leftarrow
q.$

Then $ac(\Pi)$ becomes

$\displaystyle(r,\,not\,s)\,;\,q\leftarrow p,$ $\displaystyle
r,\,not\,s\leftarrow not\,q$

where the first rule “$(r,\,not\,s)\,;\,q\leftarrow p$” is identified with

$\displaystyle r\,;\,q\leftarrow p,$ $\displaystyle not\,s\,;\,q\leftarrow p$

and the second rule “$r,\,not\,s\leftarrow not\,q$” is identified with

$\displaystyle r\leftarrow not\,q,$ $\displaystyle not\,s\leftarrow not\,q.$

Then, $AC(\Pi)\cup\\{p\leftarrow\\}$ has two answer sets $\\{p,q\\}$ and
$\\{p,r\\}$.

By definition, if there is more than one rule having the same (NAF-)literal in
the heads, they are collected to produce a single converse rule. For instance,
$\Pi=\\{\,p\leftarrow q,\;\;p\leftarrow r\,\\}$ produces
$ac(\Pi)=\\{\,q\,;\,r\leftarrow p\,\\}$ but not $\Lambda=\\{\,q\leftarrow
p,\;\;r\leftarrow p\,\\}$. Then, $AC(\Pi)\cup\\{p\leftarrow\\}$ has two answer
sets $\\{p,q\\}$ and $\\{p,r\\}$. Suppose that the new fact
$\neg\,q\leftarrow$ is added to $\Pi$. Put
$\Pi^{\prime}=\Pi\cup\\{\,\neg\,q\leftarrow\,\\}$. Then
$AC(\Pi^{\prime})\cup\\{p\leftarrow\\}$ has the answer set $\\{p,r\\}$, which
represents the result of AC reasoning in $\Pi^{\prime}$. If $\Lambda$ is used
instead of $ac(\Pi)$, however, $\Pi^{\prime}\cup\Lambda\cup\\{p\leftarrow\\}$
has the answer set $Lit$. The result is too strong because $r$ is consistently
inferred from $\Pi^{\prime}\cup\\{p\leftarrow\\}$ by AC reasoning. As a
concrete example, put $p=wet\mbox{-}grass$, $q=rain$, and
$r=sprinkler\mbox{-}on$. Then
$AC(\Pi^{\prime})\cup\\{\,wet\mbox{-}grass\leftarrow\,\\}$ has the answer set
$\\{\,wet\mbox{-}grass,\neg\,rain,sprinkler\mbox{-}on\,\\}$, while
$\Pi^{\prime}\cup\Lambda\cup\\{\,wet\mbox{-}grass\leftarrow\,\\}$ has the
answer set $Lit$. AC completion derives an antecedent from a consequent, but
it does not derive negation of antecedent by its nature. For instance, given
$\Pi=\\{\,p\,;\,q\leftarrow r,\;\;\;p\leftarrow\,\\}$, $AC(\Pi)\models_{s}r$
but $AC(\Pi)\not\models_{c}\neg\,q$.

Note that in Definition 3.1 the converse of constraints and facts are not
considered. When $head^{+}(r)=head^{-}(r)=\varnothing$, $r$ is considered a
rule with $\mathit{false}$ in the head, then $(\ref{rev-1})$ and
$(\ref{rev-2})$ become

$L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}\;\leftarrow\mathit{false}$

which has no effect as a rule. On the other hand, when
$body^{+}(r)=body^{-}(r)=\varnothing$, $r$ is considered a rule with
$\mathit{true}$ in the body, then $(\ref{rev-1})$ and $(\ref{rev-2})$
respectively become

$true\leftarrow L_{j}\;(1\leq j\leq k)\quad\mbox{and}\quad true\leftarrow
not\,L_{j}\;(k+1\leq j\leq l).$

We do not include this type of rules for constructing $ac(\Pi)$ because it
would disable AC reasoning. For instance, transforming $\Pi=\\{\,p\leftarrow
q,\;\;\;p\leftarrow\,\\}$ into $\Pi\cup\\{q\,;true\leftarrow p\\}$ produces
the answer set $\\{p\\}$, then $q$ is not obtained. With this reason,
constraints and facts are not completed at the first step of Definition 3.1.

Note also that the result of AC completion is syntax-dependent in general.
That is, two (strongly) equivalent programs may produce different AC
completions.

######  Example 3.3.

Let $\Pi_{1}=\\{\,not\,p\leftarrow q\,\\}$ and $\Pi_{2}=\\{\,\leftarrow
p,q\,\\}$. By Proposition 2.1, $\Pi_{1}$ and $\Pi_{2}$ are strongly
equivalent, but $AC(\Pi_{1})=\Pi_{1}\cup\\{\,q\leftarrow not\,p\,\\}$ and
$AC(\Pi_{2})=\Pi_{2}$. As a result, $AC(\Pi_{1})$ has the answer set $\\{q\\}$
while $AC(\Pi_{2})$ has the answer set $\varnothing$.

In the above example, “$not\,p\leftarrow q$” is a conditional sentence which
is subject to AC inference, while “$\leftarrow p,q$” is a constraint which is
not subject to AC inference by definition. For instance, given the conditional
sentence “if it is sunny, the grass is not wet” and the fact “the grass is not
wet”, people would infer “it is sunny” by AC inference. On the other hand,
given the constraint “it does not happen that wet-grass and sunny-weather at
the same time” and the fact “the grass is not wet”, the number of people who
infer “it is sunny” by AC would be smaller because the cause-effect relation
between “sunny” and “not wet” is not explicitly expressed in the constraint.

Reasoning by AC is nonmonotonic in the sense that $\Pi\models_{c}L$ (or
$\Pi\models_{s}L$) does not imply $AC(\Pi)\models_{c}L$ (or
$AC(\Pi)\models_{s}L$) in general.

######  Example 3.4.

The program $\Pi=\\{\,p\leftarrow not\,q,\;\;r\leftarrow
q,\;\;r\leftarrow\,\\}$ has the answer set $\\{p,r\\}$, while
$AC(\Pi)=\Pi\cup\\{\,not\,q\leftarrow p,\;\;q\leftarrow r\,\\}$ has the answer
set $\\{q,r\\}$.

In Example 3.4, reasoning by AC produces $q$ which blocks deriving $p$ using
the first rule in $\Pi$. As a concrete example, an online-meeting is held on
time if no network trouble arises. However, it turns that the web browser is
unconnected and one suspects that there is some trouble on the network. Put
$p$=“online-meeting is held on time”, $q$=“network trouble”, $r$=“the web
browser is unconnected”. In this case, one may withdraw the conclusion $p$
after knowing $r$. As such, additional rules $ac(\Pi)$ may change the results
of $\Pi$. One can see the effect of AC reasoning in a program $\Pi$ by
comparing answer sets of $\Pi$ and $AC(\Pi)$.

A consistent program $\Pi$ may produce an inconsistent $AC(\Pi)$. In converse,
an inconsistent $\Pi$ may produce a consistent $AC(\Pi)$.

######  Example 3.5.

$\Pi_{1}=\\{\,p\leftarrow\neg\,p,\;\;\;p\leftarrow\,\\}$ is consistent, but
$AC(\Pi_{1})=\Pi_{1}\cup\\{\,\neg\,p\leftarrow p\,\\}$ is contradictory.
$\Pi_{2}=\\{\,\leftarrow not\,p,\;\;\;q\leftarrow p,\;\;\;q\leftarrow\,\\}$ is
incoherent, but $AC(\Pi_{2})=\Pi_{2}\cup\\{\,p\leftarrow q\,\\}$ is
consistent.

A sufficient condition for the (in)consistency of $AC(\Pi)$ is given below.

######  Proposition 3.6.

If a PDP $\Pi$ contains no constraint, then $AC(\Pi)$ is consistent. Moreover,
for any answer set $S$ of $\Pi$, there is an answer set $T$ of $AC(\Pi)$ such
that $S\subseteq T$.

######  Proof 3.7.

A PDP $\Pi$ contains no NAF literal and every literal in $\Pi$ is an atom.
Then $ac(\Pi)$ is the set of rules $(\Sigma_{1};\cdots;\Sigma_{p}\leftarrow
A_{j})$ where $A_{j}$ is an atom and $\Sigma_{i}$ is a conjunction of atoms.
When $\Pi$ contains no constraint, the additional rules in $ac(\Pi)$ do not
cause inconsistency in $AC(\Pi)=\Pi\cup ac(\Pi)$.

Suppose that $S$ is an answer set (or a minimal model) of $\Pi$. Then $S$ is a
minimal set satisfying all rules in $\Pi$. Let $U=\\{\,A\,\mid\,A\in
head^{+}(r)\;\mbox{for any rule}\;r\in ac(\Pi)\;\mbox{such
that}\;body^{+}(r)\subseteq S\,\\}$. Then there is an answer set $T$ of
$AC(\Pi)$ such that $T=S\cup V$ where $V\subseteq U$. Hence the result holds.

######  Proposition 3.8.

If a program $\Pi$ is contradictory, then $AC(\Pi)$ is contradictory.

######  Proof 3.9.

If $\Pi$ is contradictory, the reduct $\Pi^{Lit}$ has the contradictory answer
set $Lit$. By definition, $AC(\Pi)^{Lit}=\Pi^{Lit}\cup ac(\Pi)^{Lit}$ where
$ac(\Pi)^{Lit}$ is the reduct of $ac(\Pi)$ by $Lit$. Introducing $not$-free
rules in $ac(\Pi)^{Lit}$ does not change the answer set $Lit$ of $\Pi^{Lit}$.
Then, $Lit$ is the answer set of $AC(\Pi)^{Lit}$ and the result follows.

###  3.2 DC Completion

We next introduce a framework for reasoning by denying the consequent (DC) in
ASP. There are two ways for negating a literal—one is using explicit negation
and the other is using default negation. Accordingly, there are two ways of
completing a program for the purpose of reasoning by DC.

######  Definition 3.10 (DC completion).

Let $\Pi$ be a program. For each rule $r\in\Pi$ of the form:

$\displaystyle
L_{1}\,;\,\cdots\,;\,L_{k}\,;\,not\,L_{k+1}\,;\cdots;\,not\,L_{l}$
$\displaystyle\qquad\leftarrow\;L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}\;\;$

define $wdc(r)$ as the rule:

$not\,L_{l+1};\cdots;not\,L_{m}\,;\,L_{m+1};\cdots;L_{n}\leftarrow
not\,L_{1},\ldots,not\,L_{k},\,L_{k+1},\ldots,L_{l}$ (7)

and define $sdc(r)$ as the rule:

$\neg\,L_{l+1};\cdots;\neg\,L_{m}\,;\,L_{m+1};\cdots;L_{n}\leftarrow\neg\,L_{1},\ldots,\neg\,L_{k},\,L_{k+1},\ldots,L_{l}.$
(8)

In particular, (7) or (8) becomes a fact if
$head^{+}(r)=head^{-}(r)=\varnothing$; and it becomes a constraint if
$body^{+}(r)=body^{-}(r)=\varnothing$. The weak DC completion and the strong
DC completion of $\Pi$ are respectively defined as:

$\displaystyle WDC(\Pi)$ $\displaystyle=$
$\displaystyle\Pi\;\cup\;\\{\,wdc(r)\,\mid\,r\in\Pi\,\\},$ $\displaystyle
SDC(\Pi)$ $\displaystyle=$
$\displaystyle\Pi\;\cup\;\\{\,sdc(r)\,\mid\,r\in\Pi\,\\}.$

By definition, $WDC(\Pi)$ and $SDC(\Pi)$ introduce contrapositive rules in two
different ways. In (7), literals $L_{i}$ $(1\leq i\leq k;\,l+1\leq i\leq m)$
are negated using default negation $not$ and NAF-literals $not\,L_{j}$
$(k+1\leq i\leq l;\,m+1\leq i\leq n)$ are converted to $L_{j}$. In (8), on the
other hand, literals $L_{i}$ $(1\leq i\leq k;\,l+1\leq i\leq m)$ are negated
using explicit negation $\neg$ and NAF-literals $not\,L_{j}$ $(k+1\leq i\leq
l;\,m+1\leq i\leq n)$ are converted to $L_{j}$.

$WDC(\Pi)$ and $SDC(\Pi)$ are GEDPs and their semantics are defined by their
answer sets. In particular, $SDC(\Pi)$ becomes an EDP if $\Pi$ is an EDP. The
WDC and SDC produce different results in general.

######  Example 3.11.

Given $\Pi=\\{\,p\leftarrow not\,q\,\\}$, it becomes

$\displaystyle WDC(\Pi)$ $\displaystyle=$ $\displaystyle\\{\,p\leftarrow
not\,q,\quad q\leftarrow not\,p\,\\},$ $\displaystyle SDC(\Pi)$
$\displaystyle=$ $\displaystyle\\{\,p\leftarrow not\,q,\quad
q\leftarrow\neg\,p\,\\}.$

Then $WDC(\Pi)$ has two answer sets $\\{p\\}$ and $\\{q\\}$, while $SDC(\Pi)$
has the single answer set $\\{p\\}$.

Example 3.11 shows that WDC is nonmonotonic as $\Pi\models_{s}p$ but
$WDC(\Pi)\not\models_{s}p$. SDC is also nonmonotonic (see Example 3.18). The
result of DC completion is syntax-dependent in general.

######  Example 3.12.

Let $\Pi_{1}=\\{\,not\,p\leftarrow q\,\\}$ and $\Pi_{2}=\\{\,\leftarrow
p,q\,\\}$. Then, $SDC(\Pi_{1})=\Pi_{1}\cup\\{\,\neg\,q\leftarrow p\,\\}$ and
$SDC(\Pi_{2})=\Pi_{2}\cup\\{\,\neg\,p\,;\neg\,q\leftarrow\,\\}$. As a result,
$SDC(\Pi_{1})$ has the answer set $\varnothing$ while $SDC(\Pi_{2})$ has two
answer sets $\\{\neg\,p\\}$ and $\\{\neg\,q\\}$.

WDC preserves the consistency of the original program.

######  Proposition 3.13.

If a program $\Pi$ has a consistent answer set $S$, then $S$ is an answer set
of $WDC(\Pi)$.

######  Proof 3.14.

Suppose a consistent answer set $S$ of $\Pi$. Then, for any rule
$L_{1}\,;\,\cdots\,;\,L_{k}\leftarrow L_{l+1},\,\ldots,\,L_{m}$ in $\Pi^{S}$,
either $\\{L_{1},\ldots,L_{k}\\}\cap S\neq\varnothing$ or
$\\{L_{l+1},\ldots,L_{m}\\}\not\subseteq S$. In each case, the rule (7) is
eliminated in $\Pi^{S}$. Then, $S$ is an answer set of $WDC(\Pi)^{S}$, hence
the result holds.

The converse of Proposition 3.13 does not hold in general.

######  Example 3.15.

The program $\Pi=\\{\,\leftarrow not\,p\,\\}$ has no answer set, while
$WDC(\Pi)=\\{\,\leftarrow~{}not\,p,\;\;p\leftarrow\,\\}$ has the answer set
$\\{p\\}$.

For $SDC(\Pi)$, the next result holds.

######  Proposition 3.16.

Let $\Pi$ be a consistent program such that every constraint in $\Pi$ is
$not$-free (i.e., $head^{+}(r)=head^{-}(r)=\varnothing$ implies
$body^{-}(r)=\varnothing$ for any $r\in\Pi$). Then $SDC(\Pi)$ is not
contradictory.

######  Proof 3.17.

Consider
$SDC(\Pi)^{Lit}=(\Pi\;\cup\;\\{\,sdc(r)\,\mid\,r\in\Pi\,\\})^{Lit}=\Pi^{Lit}\;\cup\;\\{\,sdc(r)\,\mid\,r\in\Pi\,\\}$.
(a) If there is a constraint $r\in\Pi$ such that
$head^{+}(r)=head^{-}(r)=\varnothing$, then $body^{-}(r)=\varnothing$ by the
assumption. Then $r\in\Pi^{Lit}$ and $SDC(\Pi)^{Lit}$ does not have the answer
set $Lit$ (Proposition 2.3). (b) Else if there is no constraint $\Pi$, then
$\\{\,sdc(r)\,\mid\,r\in\Pi\,\\}$ contains no fact by Def. 3.10. Consider two
cases. (i) When there is a fact $r\in\Pi$, $sdc(r)$ becomes a not-free
constraint by Def. 3.10. As $SDC(\Pi)^{Lit}$ contains this constraint, it does
not have the answer set $Lit$ (Proposition 2.3). (ii) When there is no fact in
$\Pi$, both $\Pi^{Lit}$ and $\\{\,sdc(r)\,\mid\,r\in\Pi\,\\}$ contain no fact,
so $SDC(\Pi)^{Lit}$ contains no fact. In this case, no literal is deduced in
$SDC(\Pi)^{Lit}$ and it does not have the answer set $Lit$. By (a) and (b),
$SDC(\Pi)$ is not contradictory.

A program $\Pi$ satisfying the condition of Proposition 3.16 may produce an
incoherent $SDC(\Pi)$.

######  Example 3.18.

The program $\Pi=\\{\,p\leftarrow q,\;\;\;p\leftarrow\neg
q,\;\;\;\neg\,p\leftarrow\,\\}$ has the answer set $\\{\neg\,p\\}$, but

$SDC(\Pi)=\Pi\cup\\{\,\neg\,q\leftarrow\neg\,p,\;\;\;q\leftarrow\neg\,p,\;\;\;\leftarrow
p\,\\}$

is incoherent.

######  Proposition 3.19.

If a program $\Pi$ is contradictory, then both $WDC(\Pi)$ and $SDC(\Pi)$ are
contradictory.

######  Proof 3.20.

The proof is similar to Proposition 3.8.

Note that in GEDPs contraposition of a rule does not hold in general. Thus,
the program $\Pi=\\{\,p\leftarrow q,\;\;\neg\,p\leftarrow\,\\}$ does not
deduce $\neg\,q$. $SDC$ completes the program as
$SDC(\Pi)=\Pi\cup\\{\,\neg\,q\leftarrow\neg\,p,\;\;\leftarrow p\,\\}$ and
makes $\neg\,q$ deducible. In this sense, SDC has the effect of making
explicit negation closer to classical negation in GEDP.

###  3.3 DA Completion

As a third extension, we introduce a framework for reasoning by denying the
antecedent (DA) in ASP. As in the case of DC completion, two different ways of
completion are considered depending on the choice of negation.

######  Definition 3.21 (weak DA completion).

Let $\Pi$ be a program and $r\in\Pi$ a rule of the form:

$\displaystyle
L_{1}\,;\,\cdots\,;\,L_{k}\,;\,not\,L_{k+1}\,;\cdots;\,not\,L_{l}$
$\displaystyle\quad\qquad\leftarrow\;L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}.$

  1. 1.

First, inverse the implication:

$\displaystyle not\,L_{i}$ $\displaystyle\leftarrow$ $\displaystyle
not\,L_{l+1}\,;\,\cdots\,;\,not\,L_{m}\,;\,L_{m+1}\,;\cdots\,;\,L_{n}\;\;(1\leq
i\leq k),$ (9) $\displaystyle L_{i}$ $\displaystyle\leftarrow$ $\displaystyle
not\,L_{l+1}\,;\,\cdots\,;\,not\,L_{m}\,;\,L_{m+1}\,;\,\cdots\,;\,L_{n}\;\;(k+1\leq
i\leq l).\;\;\;\;\;$ (10)

In (9) and (10), the disjunction
$not\,L_{l+1}\,;\,\cdots\,;\,not\,L_{m}\,;\,L_{m+1}\,;\,\cdots\,;\,L_{n}$
appears on the right of $\leftarrow$. The produced (9) (resp. (10)) is
considered an abbreviation of the collection of $(n-l)$ rules:
$(not\,L_{i}\leftarrow not\,L_{l+1}),\ldots,(not\,L_{i}\leftarrow L_{n})$
(resp. $(L_{i}\leftarrow not\,L_{l+1}),\ldots,(L_{i}\leftarrow L_{n})$), hence
we abuse the term ‘rule’ and call (9) or (10) a rule. In particular, (9) is
not produced if $head^{+}(r)=\varnothing$ or
$body^{+}(r)=body^{-}(r)=\varnothing$; and (10) is not produced if
$head^{-}(r)=\varnothing$ or $body^{+}(r)=body^{-}(r)=\varnothing$. The set of
rules (9)–(10) is denoted as $winv(r)$.

  2. 2.

Next, define

$\displaystyle wda(\Pi)$ $\displaystyle\\!=\\!$
$\displaystyle\\{\,\ell_{i}\leftarrow\Gamma_{1},\ldots,\Gamma_{p}\,\mid$
$\displaystyle\quad\ell_{i}\leftarrow\Gamma_{j}\;(1\leq j\leq p)\;\;\mbox{is
in}\;\;\bigcup_{r\in\Pi}\;winv(r)\,\\}$

where $\ell_{i}$ is either a literal $L_{i}$ $(k+1\leq i\leq l)$ or an NAF
literal $not\,L_{i}$ $(1\leq i\leq k)$, and each $\Gamma_{j}$ $(1\leq j\leq
p)$ is a disjunction of literals and NAF literals.

  3. 3.

The weak DA completion of $\Pi$ is defined as:

$WDA(\Pi)=\Pi\;\cup\;wda(\Pi).$

(9) and (10) in $winv(r)$ represent inverse implication from the (default)
negation of the conjunction in the body of $r$ to the (default) negation of
the disjunction in the head of $r$. $wda(\Pi)$ collects rules
$\ell_{i}\leftarrow\Gamma_{j}$ $(1\leq j\leq p)$ having the same (NAF-)literal
$\ell_{i}$ on the left of $\leftarrow$, and constructs
“$\ell_{i}\leftarrow\Gamma_{1},\ldots,\Gamma_{p}$”, which we call an extended
rule. Introducing $wda(\Pi)$ to $\Pi$ realizes reasoning by weak DA. An
extended rule has a conjunction of disjunctions in its body, while it is
transformed to rules of a GEDP as the case of AC completion. That is, the
extended rule:

$\ell_{i}\leftarrow(\ell^{1}_{1}\,;\,\cdots\,;\,\ell^{1}_{m_{1}})\,,\ldots,\,(\ell^{p}_{1}\,;\,\cdots\,;\,\ell^{p}_{m_{p}})$

is identified with the set of $m_{1}\times\cdots\times m_{p}$ rules of the
form:

$\ell_{i}\leftarrow\ell^{1}_{j_{1}},\,\ldots,\,\ell^{p}_{j_{p}}\;\;\;\;\;(1\leq
j_{k}\leq m_{k};\,1\leq k\leq p).$

By this fact, $WDA(\Pi)$ is viewed as a GEDP and we do not distinguish
extended rules and rules of a GEDP hereafter. The semantics of $WDA(\Pi)$ is
defined by its answer sets.

######  Example 3.22.

Let $\Pi$ be the program:

$\displaystyle p\,;\,q\leftarrow r,\,not\,s,$ $\displaystyle
q\,;\,not\,r\leftarrow t,$ $\displaystyle s\leftarrow.$

Then $wda(\Pi)$ becomes

$\displaystyle not\,p\leftarrow not\,r\,;\,s,$ $\displaystyle
not\,q\leftarrow(not\,r\,;\,s),\,not\,t,$ $\displaystyle r\leftarrow not\,t$

where the first rule “$not\,p\leftarrow not\,r\,;\,s$” is identified with

$\displaystyle not\,p\leftarrow not\,r,$ $\displaystyle not\,p\leftarrow s,$

and the second rule “$not\,q\leftarrow(not\,r\,;\,s),\,not\,t$” is identified
with

$\displaystyle not\,q\leftarrow not\,r,\,not\,t,$ $\displaystyle
not\,q\leftarrow s,\,not\,t.$

Then, $WDA(\Pi)$ has the answer set $\\{s,r\\}$.

As in the case of AC completion, if there is more than one rule having the
same (NAF-)literal in the heads, they are collected to produce a single
inverse rule. For instance, $\Pi=\\{\,p\leftarrow q,\;\;p\leftarrow~{}r\,\\}$
produces $wda(\Pi)=\\{\,not\,p\leftarrow not\,q,\,not\,r\,\\}$ but not
$\Lambda=\\{\,not\,p\leftarrow not\,q,\;\;not\,p\leftarrow not\,r\,\\}$.
Suppose the new fact $r\leftarrow$ is added to $\Pi$. Put
$\Pi^{\prime}=\Pi\cup\\{r\leftarrow\\}$. Then $WDA(\Pi^{\prime})$ has the
answer set $\\{p,r\\}$. If $\Lambda$ is used instead of $wda(\Pi)$, however,
$\Pi^{\prime}\cup\Lambda$ is incoherent because the first rule of $\Lambda$ is
not satisfied. The result is too strong because $p$ is deduced by $p\leftarrow
r$ and $r\leftarrow$, and it has no direct connection to DA inference in the
first rule of $\Lambda$. Hence, we conclude $not\,p$ if both $q$ and $r$ are
negated in $wda(\Pi)$.

The strong DA completion is defined in a similar manner.

######  Definition 3.23 (strong DA completion).

Let $\Pi$ be a program and $r\in\Pi$ a rule of the form:

$\displaystyle
L_{1}\,;\,\cdots\,;\,L_{k}\,;\,not\,L_{k+1}\,;\cdots;\,not\,L_{l}$
$\displaystyle\qquad\leftarrow\;L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}.$

  1. 1.

First, inverse the implication:

$\displaystyle\neg\,L_{i}$ $\displaystyle\leftarrow$
$\displaystyle\neg\,L_{l+1}\,;\,\cdots\,;\,\neg\,L_{m}\,;\,L_{m+1}\,;\cdots\,;\,L_{n}\;\;(1\leq
i\leq k),$ (11) $\displaystyle L_{i}$ $\displaystyle\leftarrow$
$\displaystyle\neg\,L_{l+1}\,;\,\cdots\,;\,\neg\,L_{m}\,;\,L_{m+1}\,;\,\cdots\,;\,L_{n}\;\;(k+1\leq
i\leq l).\;\;\;\;\;$ (12)

As in the case of WDA, the produced (11) (resp. (12)) is considered an
abbreviation of the collection of $(n-l)$ rules:
$(\neg\,L_{i}\leftarrow\neg\,L_{l+1}),\ldots,(\neg\,L_{i}\leftarrow L_{n})$
(resp. $(L_{i}\leftarrow\neg\,L_{l+1}),\ldots,(L_{i}\leftarrow L_{n})$), hence
we call (11) or (12) a rule. In particular, (11)–(12) are not produced when
their heads or bodies are empty. The set of rules (11)–(12) is denoted as
$sinv(r)$.

  2. 2.

Next, define

$\displaystyle sda(\Pi)$ $\displaystyle\\!=\\!$
$\displaystyle\\{\,\ell_{i}\leftarrow\Gamma_{1},\ldots,\Gamma_{p}\,\mid$
$\displaystyle\quad\ell_{i}\leftarrow\Gamma_{j}\;(1\leq j\leq p)\;\;\mbox{is
in}\;\;\bigcup_{r\in\Pi}\;sinv(r)\,\\}$

where $\ell_{i}$ is either a literal $L_{i}$ $(k+1\leq i\leq l)$ or
$\neg\,L_{i}$ $(1\leq i\leq k)$, and each $\Gamma_{j}$ $(1\leq j\leq p)$ is a
disjunction of positive/negative literals.

  3. 3.

The strong DA completion of $\Pi$ is defined as:

$SDA(\Pi)=\Pi\;\cup\;sda(\Pi).$

As in the case of WDA, extended rules in $sda(\Pi)$ is transformed to rules of
a GEDP. Then $SDA(\Pi)$ is viewed as a GEDP and its semantics is defined by
its answer sets. In particular, $SDA(\Pi)$ becomes an EDP if $\Pi$ is an EDP.

The result of DA completion is syntax-dependent in general.

######  Example 3.24.

Let $\Pi_{1}=\\{\,not\,p\leftarrow q\,\\}$ and $\Pi_{2}=\\{\,\leftarrow
p,q\,\\}$. Then, $WDA(\Pi_{1})=\Pi_{1}\cup\\{\,p\leftarrow not\,q\,\\}$ and
$WDA(\Pi_{2})=\Pi_{2}$. As a result, $WDA(\Pi_{1})$ has the answer set
$\\{p\\}$ while $WDA(\Pi_{2})$ has the answer set $\varnothing$.

Both WDA and SDA are nonmonotonic in general.

######  Example 3.25.

(1) $\Pi_{1}=\\{\,p\leftarrow not\,q,\;\;not\,q\leftarrow p\,\\}$ produces
$WDA(\Pi_{1})=\Pi_{1}\cup\\{\,not\,p\leftarrow q,\;\;q\leftarrow not\,p\,\\}$.
Then, $\Pi_{1}\models_{s}p$ but $WDA(\Pi_{1})\not\models_{s}p$. (2)
$\Pi_{2}=\\{\,p\leftarrow not\,\neg r,\;\;r\leftarrow
not\,q,\;\;q\leftarrow\,\\}$ produces
$SDA(\Pi_{2})=\Pi_{2}\cup\\{\,\neg\,p\leftarrow\neg\,r,\;\;\neg\,r\leftarrow
q\,\\}$. Then, $\Pi_{2}\models_{c}p$ but $SDA(\Pi_{2})\not\models_{c}p$.

When a program is a consistent EDP, the WDA does not introduce a new answer
set.

######  Proposition 3.26.

Let $\Pi$ be an EDP. If $S$ is a consistent answer set of $WDA(\Pi)$, then $S$
is an answer set of $\Pi$.

######  Proof 3.27.

When $\Pi$ is an EDP, the rules (10) are not included in $winv(r)$. By the
rules (9) in $winv(r)$, rules of the form
$not\,L_{i}\leftarrow\Gamma_{1},\ldots,\Gamma_{p}$ are produced in $wda(\Pi)$,
which are identified with the collection of rules
$not\,L_{i}\leftarrow\ell_{j_{1}}^{1},\ldots\ell_{j_{p}}^{p}$ where
$\ell_{j_{k}}^{p}$ $(1\leq k\leq p)$ is an (NAF-)literal. These rules are
converted into the strongly equivalent constraint $\leftarrow
L_{i},\ell_{j_{1}}^{1},\ldots,\ell_{j_{p}}^{p}$ (Proposition 2.1). The
additional constraints may eliminate answer sets of $\Pi$, but do not
introduce new answer sets. Thus, a consistent answer set $S$ of $WDA(\Pi)$ is
also a consistent answer set of $\Pi$.

######  Proposition 3.28.

If a program $\Pi$ is contradictory, then both $WDA(\Pi)$ and $SDA(\Pi)$ are
contradictory.

######  Proof 3.29.

The proof is similar to Proposition 3.8.

As in the case of AC, a consistent program $\Pi$ may produce an inconsistent
$WDA(\Pi)$ or $SDA(\Pi)$. In converse, an incoherent $\Pi$ may produce a
consistent $WDA(\Pi)$ or $SDA(\Pi)$.

######  Example 3.30.

(1) $\Pi_{1}=\\{\,not\,p\leftarrow p\,\\}$, which is equivalent to
$\\{\,\leftarrow p\,\\}$ (Proposition 2.1), is consistent, but
$WDA(\Pi_{1})=\Pi_{1}\cup\\{\,p\leftarrow not\,p\,\\}$ is incoherent.

(2) $\Pi_{2}=\\{\,\neg\,p\leftarrow p,\;\;\neg\,p\leftarrow\,\\}$ is
consistent, but $SDA(\Pi_{2})\\!=\Pi_{2}\cup\\{\,p\leftarrow\neg\,p\,\\}$ is
contradictory.

(3) $\Pi_{3}=\\{\,not\,p\leftarrow q,\;\;\leftarrow not\,p\,\\}$, which is
equivalent to $\\{\,\leftarrow p,q,\;\;\leftarrow not\,p\,\\}$ (Proposition
2.1), is incoherent, but $WDA(\Pi_{3})=\Pi_{3}\cup\\{\,p\leftarrow
not\,q\,\\}$ is consistent (having the answer set $\\{p\\}$).

(4) $\Pi_{4}=\\{\,\leftarrow not\,p,\;\;\neg\,p\leftarrow
not\,q,\;\;q\leftarrow\,\\}$ is incoherent, but
$SDA(\Pi_{4})=\Pi_{4}\cup\\{\,p\leftarrow q\,\\}$ is consistent (having the
answer set $\\{p,q\\}$).

##  4 AC and DA as Default Reasoning

AC and DA are logically invalid and additional rules for AC and DA often make
a program inconsistent. In this section, we relax the effects of the AC or DA
completion by introducing additional rules as default rules in the sense of
Reiter, (1980). More precisely, we capture AC and DA as the following default
inference rules:

$\displaystyle({\mathbf{d}efault\,AC})$
$\displaystyle\frac{(\varphi\Rightarrow\psi)\wedge\psi:\varphi}{\varphi}$
$\displaystyle({\mathbf{d}efault\,DA})$
$\displaystyle\frac{(\varphi\Rightarrow\psi)\wedge\neg\varphi:\neg\psi}{\neg\psi}$

The default AC rule says: given the conditional $\varphi\Rightarrow\psi$ and
the fact $\psi$, conclude $\varphi$ as a default consequence. The default DA
rule is read in a similar manner. We encode these rules in ASP.

###  4.1 Default AC completion

The AC completion is modified for default AC reasoning.

######  Definition 4.1 (default AC completion).

Let $\Pi$ be a program. For each rule $r\in\Pi$ of the form:

$\displaystyle
L_{1}\,;\,\cdots\,;\,L_{k}\,;\,not\,L_{k+1}\,;\cdots;\,not\,L_{l}$
$\displaystyle\qquad\leftarrow\;L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n},$

define $dac(r)$ as the set of rules:

$\displaystyle
L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}\leftarrow
L_{i},\,\Delta\;\;\;\;\;\quad(1\leq i\leq k),$ (13) $\displaystyle
L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}\leftarrow
not\,L_{i},\,\Delta\;\;\;\;(k+1\leq i\leq l)$ (14)

where
$\Delta=not\,\neg\,L_{l+1},\,\ldots,\,not\,\neg\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}$.
As before, (13) is not produced if $head^{+}(r)=\varnothing$ or
$body^{+}(r)=body^{-}(r)=\varnothing$; and (14) is not produced if
$head^{-}(r)=\varnothing$ or $body^{+}(r)=body^{-}(r)=\varnothing$. The
default AC completion of $\Pi$ is defined as:

$DAC(\Pi)=\Pi\;\cup\;dac(\Pi)$

in which

$\displaystyle dac(\Pi)$ $\displaystyle\\!=\\!$
$\displaystyle\\{\;\Sigma_{1}\,;\,\cdots\,;\,\Sigma_{p}\;\leftarrow\;\ell_{j},\,\Delta_{i}\;\mid$
$\displaystyle\quad\Sigma_{i}\leftarrow\ell_{j},\,\Delta_{i}\;\,(1\leq i\leq
p)\;\;\mbox{is in}\;\;\bigcup_{r\in\Pi}\,dac(r)\,\\}$

where each $\Sigma_{i}$ $(1\leq i\leq p)$ is a conjunction of literals and
NAF-literals, and $\ell_{j}$ is either a literal $L_{j}$ $(1\leq j\leq k)$ or
an NAF-literal $not\,L_{j}$ $(k+1\leq j\leq l)$.

Like $AC(\Pi)$, rules in $dac(\Pi)$ are converted into the form of a GEDP,
then $DAC(\Pi)$ is viewed as a GEDP. Compared with the AC completion, the DAC
completion introduces the conjunction $\Delta$ of NAF literals to the body of
each rule. Then the rules
($\Sigma_{1}\,;\,\cdots\,;\,\Sigma_{p}\,\leftarrow\,\ell_{j},\,\Delta_{i}$)
having the same head with different bodies are constructed for $i=1,\ldots,p$.

######  Example 4.2.

Let $\Pi=\\{\,p\leftarrow q,\;\;p\leftarrow r,\;\;p\leftarrow,\;\;\neg
r\leftarrow\,\\}$. Then $DAC(\Pi)=\Pi\cup dac(\Pi)$ where

$dac(\Pi)=\\{\,q\,;r\leftarrow p,not\,\neg q,\;\;\;q\,;r\leftarrow p,not\,\neg
r\,\\}.$

As a result, $DAC(\Pi)$ has the answer set $\\{p,q,\neg r\\}$.

######  Proposition 4.3.

Let $\Pi$ be a consistent program. If $DAC(\Pi)$ has an answer $S$, then
$S\neq Lit$.

######  Proof 4.4.

Suppose that $DAC(\Pi)$ has the answer $Lit$. Then,
$DAC(\Pi)^{Lit}=\Pi^{Lit}\cup dac(\Pi)^{Lit}$ has the answer set $Lit$. Since
$dac(\Pi)^{Lit}=\varnothing$, $\Pi^{Lit}$ has the answer set $Lit$. This
contradicts the assumption that $\Pi$ is consistent.

$DAC(\Pi)$ turns a contradictory $AC(\Pi)$ into a consistent program.

######  Example 4.5 (cont. Example 3.5).

Let $\Pi_{1}=\\{\,p\leftarrow\neg\,p,\;\;p\leftarrow\,\\}$. Then,
$DAC(\Pi_{1})=\Pi_{1}\cup\\{\,\neg\,p\leftarrow p,\,not\,p\,\\}$ has the
single answer set $\\{\,p\,\\}$. So $AC(\Pi_{1})$ is contradictory, but
$DAC(\Pi_{1})$ is consistent.

When $AC(\Pi)$ is incoherent, however, $DAC(\Pi)$ does not resolve incoherency
in general.

######  Example 4.6.

Let $\Pi=\\{\,p\leftarrow q,\;\;p\leftarrow,\;\;\leftarrow q\,\\}$. Then,
$AC(\Pi)=\Pi\cup\\{\,q\leftarrow p\,\\}$ is incoherent.
$DAC(\Pi)=\Pi\cup\\{\,q\leftarrow p,\,not\,\neg\,q\,\\}$ is still incoherent.

In what follows, we say that a set $S$ of ground literals satisfies the
conjunction $L_{1},\ldots,L_{k}$ of ground literals if
$\\{L_{1},\ldots,L_{k}\\}\subseteq S$; and $S$ satisfies the conjunction
$not\,L_{1},\ldots,not\,L_{k}$ of ground NAF-literals if
$\\{L_{1},\ldots,L_{k}\\}\cap S=\varnothing$.

When $AC(\Pi)$ has a consistent answer set, $DAC(\Pi)$ does not change it.

######  Proposition 4.7.

Let $\Pi$ be a program. If $AC(\Pi)$ has a consistent answer set $S$, then $S$
is an answer set of $DAC(\Pi)$.

######  Proof 4.8.

Suppose that $AC(\Pi)$ has a consistent answer set $S$. For each rule
$\Sigma_{1}\,;\,\cdots\,;\,\Sigma_{p}\;\leftarrow\;L_{j}$ $(1\leq j\leq k)$ in
$ac(\Pi)$, $L_{j}\in S$ implies that $S$ satisfies some conjunction
$\Sigma_{i}$ $(1\leq i\leq p)$. In this case, $S$ satisfies $\Delta_{i}$ and
$L_{j}\in S$ implies that $S$ satisfies $\Sigma_{i}$ for each rule
$\Sigma_{1}\,;\,\cdots\,;\,\Sigma_{p}\;\leftarrow\;L_{j},\Delta_{i}$ in
$dac(\Pi)$. Likewise, for each rule
$\Sigma_{1}\,;\,\cdots\,;\,\Sigma_{p}\;\leftarrow\;not\,L_{j}$ $(k+1\leq j\leq
l)$ in $ac(\Pi)$, $L_{j}\not\in S$ implies that $S$ satisfies some
$\Sigma_{i}$ $(1\leq i\leq p)$. In this case, $S$ satisfies $\Delta_{i}$ and
$L_{j}\not\in S$ implies that $S$ satisfies $\Sigma_{i}$ for each rule
$\Sigma_{1}\,;\,\cdots\,;\,\Sigma_{p}\;\leftarrow\;not\,L_{j},\Delta_{i}$ in
$dac(\Pi)$. Then $AC(\Pi)^{S}=DAC(\Pi)^{S}$ and the result follows.

###  4.2 Default DA completion

The DA completion is modified for default DA reasoning.

######  Definition 4.9 (default DA completion).

Let $\Pi$ be a program. Define

$\displaystyle wdda(\Pi)$ $\displaystyle\\!=\\!$
$\displaystyle\\{\,\ell_{i}\leftarrow\Gamma_{1},\ldots,\Gamma_{p},\,\delta^{w}_{i}\,\mid$
$\displaystyle\quad\ell_{i}\leftarrow\Gamma_{j}\;(1\leq j\leq p)\;\;\mbox{is
in}\;\;\bigcup_{r\in\Pi}\;winv(r)\,\\},$ $\displaystyle sdda(\Pi)$
$\displaystyle\\!=\\!$
$\displaystyle\\{\,\ell_{i}\leftarrow\Gamma_{1},\ldots,\Gamma_{p},\,\delta^{s}_{i}\,\mid$
$\displaystyle\quad\ell_{i}\leftarrow\Gamma_{j}\;(1\leq j\leq p)\;\;\mbox{is
in}\;\;\bigcup_{r\in\Pi}\;sinv(r)\,\\}$

where $\ell_{i}$, $\Gamma_{j}$, $winv(r)$, and $sinv(r)$ are the same as those
in Defs. 3.21 and 3.23. In addition, $\delta^{w}_{i}=not\,\neg\,L_{i}$ if
$\ell_{i}=L_{i}$, and $\delta^{w}_{i}=not\,L_{i}$ if $\ell_{i}=not\,L_{i}$;
$\delta^{s}_{i}=not\,\neg\,L_{i}$ if $\ell_{i}=L_{i}$, and
$\delta^{s}_{i}=not\,L_{i}$ if $\ell_{i}=\neg\,L_{i}$. The weak default DA
completion and the strong default DA completion of $\Pi$ are respectively
defined as:

$\displaystyle WDDA(\Pi)$ $\displaystyle=$
$\displaystyle\Pi\;\cup\;wdda(\Pi),$ $\displaystyle SDDA(\Pi)$
$\displaystyle=$ $\displaystyle\Pi\;\cup\;sdda(\Pi).$

Rules in $wdda(\Pi)$ and $sdda(\Pi)$ are converted into the form of a GEDP, so
$WDDA(\Pi)$ and $SDDA(\Pi)$ are viewed as GEDPs. Like the DAC completion, both
WDDA and SDDA introduce an additional NAF literal to each rule.

######  Proposition 4.10.

Let $\Pi$ be a consistent program. If $WDDA(\Pi)$ (or $SDDA(\Pi)$) has an
answer set $S$, then $S\neq Lit$.

######  Proof 4.11.

Suppose that $WDDA(\Pi)$ has the answer $Lit$. Then,
$WDDA(\Pi)^{Lit}=\Pi^{Lit}\cup wdda(\Pi)^{Lit}$ has the answer set $Lit$.
Since $wdda(\Pi)^{Lit}=\varnothing$, $\Pi^{Lit}$ has the answer set $Lit$.
This contradicts the assumption that $\Pi$ is consistent. The case of
$SDDA(\Pi)$ is shown in a similar manner.

The WDDA/SDDA eliminates contradiction but does not resolve incoherency.

######  Example 4.12 (cont. Example 3.30).

Let $\Pi_{1}=\\{\,not\,p\leftarrow p\,\\}$ where $WDA(\Pi_{1})$ is incoherent.
$WDDA(\Pi_{1})=\Pi_{1}\cup\\{\,p\leftarrow not\,p,\,not\,\neg\,p\,\\}$ is
still incoherent. Let $\Pi_{2}=\\{\,\neg\,p\leftarrow
p,\;\;\;\neg\,p\leftarrow\,\\}$ where $SDA(\Pi_{2})$ is contradictory.
$SDDA(\Pi_{2})=\Pi_{2}\cup\\{\,p\leftarrow\neg\,p,\,not\,\neg\,p\,\\}$ has the
answer set $\\{\neg p\\}$.

######  Proposition 4.13.

Let $\Pi$ be a program. If $WDA(\Pi)$ (resp. $SDA(\Pi)$) has a consistent
answer set $S$, then $S$ is an answer set of $WDDA(\Pi)$ (resp. $SDDA(\Pi)$).

######  Proof 4.14.

Suppose that $WDA(\Pi)$ has a consistent answer set $S$. If $L_{i}\in S$ then
$\neg\,L_{i}\not\in S$ and $\delta^{w}_{i}=not\,\neg\,L_{i}$ is eliminated in
$WDDA(\Pi)^{S}$. Else if $L_{i}\not\in S$ and $\neg\,L_{i}\in S$, there is
another rule $\ell_{i}\leftarrow\Gamma_{1},\ldots,\Gamma_{p},\,\delta^{w}_{i}$
in $wdda(\Pi)$ such that $\ell_{i}=\neg\,L_{i}$ and
$\delta^{w}_{i}=not\,L_{i}$. Then, $\delta^{w}_{i}=not\,L_{i}$ is eliminated
in $WDDA(\Pi)^{S}$. Thus, $WDA(\Pi)^{S}=WDDA(\Pi)^{S}$. Similarly,
$SDA(\Pi)^{S}=SDDA(\Pi)^{S}$. Hence, the result follows.

As such, default AC/DA completion is used for avoiding contradiction in
programs containing explicit negation.

##  5 Characterizing Human Reasoning Tasks

###  5.1 Suppression Task

Byrne, (1989) provides an emperical study which shows that human conditional
reasoning can be nonmonotonic in the so-called suppression tasks. She verifies
the effects in different types of conditional reasoning by experimental
testing on college students. Students are divided into three groups: the first
group receives simple conditional arguments; the second group receives
conditional arguments accompanied by another conditional sentence with an
alternative antecedent; and the third group receives conditional arguments
accompanied by another conditional sentence with an additional antecedent.
More precisely, suppose the following three conditional sentences:

> $S_{1}$: If she has an essay to write then she will study late in the
> library.
>
> $S_{2}$: If she has some textbooks to read then she will study late in the
> library.
>
> $S_{3}$: If the library stays open then she will study late in the library.

Given the conditional sentence $S_{1}$, $S_{2}$ represents a sentence with an
alternative antecedent, while $S_{3}$ represents a sentence with an additional
antecedent. The antecedent of $S_{2}$ is considered an alternative sufficient
condition for studying late in the library. By contrast, the antecedent of
$S_{3}$ is considered an additional sufficient condition for studying late in
the library. Table 1 presents the percentages of inferences made by subjects
from the three kinds of arguments.

Table 1: The percentages of inferences in experiments (Byrne, (1989))  Argument Type |  AA (MP) |  DC (MT) |  AC |  DA
---|---|---|---|---
simple arguments ($S_{1}$) | 96% | 92% | 71% | 46%
alternative arguments ($S_{1}$ and $S_{2}$) | 96% | 96% | 13% | 4%
additional arguments ($S_{1}$ and $S_{3}$) | 38% | 33% | 54% | 63%
|  |  |  |

By the table, given the sentence $S_{1}$ and the fact: “she will study late in
the library”, the 71% of the first group concludes: “she has an essay to
write” by AC. When $S_{1}$ is accompanied by a conditional $S_{2}$ containing
an alternative antecedent, on the other hand, the percentage of subjects who
perform AC inference reduces to 13%. The reason is that people know that the
alternative: “She has some textbooks to read”, could be the case instead.
Similar reduction is observed for DA. Byrne argues that those fallacious
inferences are suppressed when a conditional is accompanied by an alternative
antecedent. She also observe that the inference patterns change when $S_{1}$
is accompanied by a conditional $S_{3}$ containing an additional antecedent.
In Table 1 the number of subjects who conclude: “She will study late in the
library” by AA is 38%, and the number of subjects who conclude: “She does not
have an essay to write” by DC is 33%. By contrast, the suppression of AC and
DA are relaxed, 54% of subjects make AC and 63% of subjects make DA. Byrne
then argues that “valid inferences are suppressed in the same way as
fallacious inferences”.

The suppression task is characterized in our framework as follows. First, the
sentence $S_{1}$ is represented as the rule: “$library\leftarrow essay$”.
Then, four conditional inferences (AA, DC, AC, DA) in simple arguments are
respectively represented by the following programs:

(AA) $\displaystyle\Pi_{0}=\\{\,library\leftarrow
essay,\;\;\;essay\leftarrow\,\\},$ (DC)
$\displaystyle\Pi_{1}=\\{\,library\leftarrow
essay,\;\;\;\neg\,library\leftarrow\,\\},$ (AC)
$\displaystyle\Pi_{2}=\\{\,library\leftarrow
essay,\;\;\;library\leftarrow\,\\},$ (DA)
$\displaystyle\Pi_{3}=\\{\,library\leftarrow
essay,\;\;\;\neg\,essay\leftarrow\,\\}.$

Then $\Pi_{0}$ has the answer set $\\{\,library,essay\,\\}$ in which AA
inference is done. By contrast, DC, AC, and DA inferences are not performed in
$\Pi_{1}$, $\Pi_{2}$, and $\Pi_{3}$, respectively. To realize those
inferences, consider completions such that

$\displaystyle SDC(\Pi_{1})$ $\displaystyle=$
$\displaystyle\Pi_{1}\cup\\{\,\neg\,essay\leftarrow\neg\,library\,\\},$
$\displaystyle AC(\Pi_{2})$ $\displaystyle=$
$\displaystyle\Pi_{2}\cup\\{\,essay\leftarrow library\,\\},$ $\displaystyle
SDA(\Pi_{3})$ $\displaystyle=$
$\displaystyle\Pi_{3}\cup\\{\,\neg\,library\leftarrow\neg\,essay\,\\}$

where $SDC(\Pi_{1})$ has the answer set $\\{\,\neg\,library,\neg\,essay\,\\}$,
$AC(\Pi_{2})$ has the answer set $\\{\,library,essay\,\\}$, and $SDA(\Pi_{3})$
has the answer set $\\{\,\neg\,library,\neg\,essay\,\\}$. As a result, DC, AC,
and DA inferences are performed in $SDC(\Pi_{1})$, $AC(\Pi_{2})$, and
$SDA(\Pi_{3})$, respectively.

Next, consider the alternative arguments $S_{1}$ and $S_{2}$. They are
represented by the programs:

$\Pi_{k}^{\mathrm{A}LT}=\Pi_{k}\cup\\{\,library\leftarrow
text\,\\}\;\;\;(k=0,1,2,3).$

The program $\Pi_{0}^{\mathrm{A}LT}$ has the answer set
$\\{\,library,essay\,\\}$ in which the result of AA inference does not change
from $\Pi_{0}$. Programs $\Pi_{1}^{\mathrm{A}LT}$, $\Pi_{2}^{\mathrm{A}LT}$,
and $\Pi_{3}^{\mathrm{A}LT}$ are completed as follows:

$\displaystyle SDC(\Pi_{1}^{\mathrm{A}LT})$ $\displaystyle=$
$\displaystyle\Pi_{1}^{\mathrm{A}LT}\cup\\{\,\neg\,essay\leftarrow\neg\,library,\;\;\;\neg\,text\leftarrow\neg\,library\,\\},$
$\displaystyle AC(\Pi_{2}^{\mathrm{A}LT})$ $\displaystyle=$
$\displaystyle\Pi_{2}^{\mathrm{A}LT}\cup\\{\,essay\,;\,text\leftarrow
library\,\\},$ $\displaystyle SDA(\Pi_{3}^{\mathrm{A}LT})$ $\displaystyle=$
$\displaystyle\Pi_{3}^{\mathrm{A}LT}\cup\\{\,\neg\,library\leftarrow\neg\,essay,\,\neg\,text\,\\}$

where $SDC(\Pi_{1}^{\mathrm{A}LT})$ has the answer set
$\\{\,\neg\,library,\neg\,essay,\neg\,text\,\\}$, $AC(\Pi_{2}^{\mathrm{A}LT})$
has the two answer sets $\\{\,library,essay\,\\}$ and
$\\{\,library,text\,\\}$, and $SDA(\Pi_{3}^{\mathrm{A}LT})$ has the answer set
$\\{\,\neg\,essay\,\\}$. As a result,
$SDC(\Pi_{1}^{\mathrm{A}LT})\models_{s}\neg\,essay$,
$AC(\Pi_{2}^{\mathrm{A}LT})\not\models_{s}essay$, and
$SDA(\Pi_{3}^{\mathrm{A}LT})\not\models_{s}\neg\,library$, which indicate that
AC and DA inferences are suppressed while DC is not suppressed. In this way,
the completion successfully represents the effect of suppression of AC/DA
inference in alternative arguments.

In additional arguments, on the other hand, Byrne, (1989) observes that AA/DC
inference is also suppressed. Our completion method does not characterize the
suppression of AA inference because we enable fallacious inferences by AC/DA
completion while still keep the valid AA inference. Byrne, (1989) says “people
may consider that certain other conditions are necessary for this conclusion
to hold, for example, the library must remain open. Thus, conditionals are
frequently elliptical in that information that can be taken for granted is
omitted from them”. In the above example, the availability of the library is
necessary for studying in it but it is just omitted in the initial premises.
Then it is considered that the rule: “$library\leftarrow essay$” in mind is
overwritten by the rule: “$library\leftarrow essay,\,open$” when the
additional antecedent is given. Let

$\displaystyle\Pi_{0}^{\mathrm{A}DD}=\\{\,library\leftarrow
essay,\,open,\;\;\;essay\leftarrow\,\\},$
$\displaystyle\Pi_{1}^{\mathrm{A}DD}=\\{\,library\leftarrow
essay,\,open,\;\;\;\neg\,library\leftarrow\,\\},$
$\displaystyle\Pi_{2}^{\mathrm{A}DD}=\\{\,library\leftarrow
essay,\,open,\;\;\;library\leftarrow\,\\},$
$\displaystyle\Pi_{3}^{\mathrm{A}DD}=\\{\,library\leftarrow
essay,\,open,\;\;\;\neg\,essay\leftarrow\,\\}.$

The program $\Pi_{0}^{\mathrm{A}DD}$ has the answer set $\\{\,essay\,\\}$,
thereby $\Pi_{0}^{\mathrm{A}DD}\not\models_{s}library$. Then the result of AA
inference is suppressed. Programs $\Pi_{1}^{\mathrm{A}DD}$,
$\Pi_{2}^{\mathrm{A}DD}$, $\Pi_{3}^{\mathrm{A}DD}$ are completed as follows:

$\displaystyle SDC(\Pi_{1}^{\mathrm{A}DD})$ $\displaystyle=$
$\displaystyle\Pi_{1}^{\mathrm{A}DD}\cup\\{\,\neg\,essay\,;\,\neg\,open\leftarrow\neg\,library\,\\},$
$\displaystyle AC(\Pi_{2}^{\mathrm{A}DD})$ $\displaystyle=$
$\displaystyle\Pi_{2}^{\mathrm{A}DD}\cup\\{\,essay\leftarrow
library,\;\;\;open\leftarrow library\,\\},$ $\displaystyle
SDA(\Pi_{3}^{\mathrm{A}DD})$ $\displaystyle=$
$\displaystyle\Pi_{3}^{\mathrm{A}DD}\cup\;\\{\,\neg\,library\leftarrow\neg\,essay,\;\;\;\neg\,library\leftarrow\neg\,open\,\\}$

where $SDC(\Pi_{1}^{\mathrm{A}DD})$ has the two answer sets
$\\{\,\neg\,library,\neg\,essay\,\\}$ and
$\\{\,\neg\,library,\neg\,open\,\\}$, $AC(\Pi_{2}^{\mathrm{A}DD})$ has the
answer set $\\{\,library,essay,open\,\\}$, and $SDA(\Pi_{3}^{\mathrm{A}DD})$
has the the answer set $\\{\,\neg\,essay,\neg\,library\,\\}$. As a result,
$SDC(\Pi_{1}^{\mathrm{A}DD})\not\models_{s}\neg\,essay$,
$AC(\Pi_{2}^{\mathrm{A}DD})\models_{s}essay$, and
$SDA(\Pi_{3}^{\mathrm{A}DD})\models_{s}\neg\,library$. This indicates that DC
is suppressed but AC and DA are not suppressed, which explains the results of
Byrne, (1989).

The results of inferences using completion are summarized in Table 2. By the
table, the suppression of AC and DA in face of an alternative antecedent is
realized in our framework. The suppression of AA and DC in face of an
additional antecedent is also realized if the additional condition is written
in the antecedent of the original conditional sentence.

Table 2: Summary of inferences made by completion Argument Type |  AA (MP) |  DC (MT) |  AC |  DA
---|---|---|---|---
$S_{1}$ |  $\circ$ ($\Pi_{0}$) |  $\circ$ (SDC($\Pi_{1}$)) |  $\circ$ (AC($\Pi_{2}$)) |  $\circ$ (SDA($\Pi_{3}$))
$S_{1}$ and $S_{2}$ | $\circ$ |  $\circ$ (SDC($\Pi_{1}^{\mathrm{A}LT}$)) |  $\times$ (AC($\Pi_{2}^{\mathrm{A}LT}$)) |  $\times$ (SDA($\Pi_{3}^{\mathrm{A}LT}$))
$S_{1}$ and $S_{3}$ | ($\times$ ($\Pi_{0}^{\mathrm{A}DD}$)) | ($\times$ (SDC($\Pi_{1}^{\mathrm{A}DD}$))) | ($\circ$ (AC($\Pi_{2}^{\mathrm{A}DD}$))) | ($\circ$ (SDA($\Pi_{3}^{\mathrm{A}DD}$)))
$\circ$ means that inference succeeds; $\times$ means that inference is
suppressed.

###  5.2 Wason Selection Task

Wason, (1968) introduces the selection task for examining human conditional
reasoning. The task is described as follows. There are four cards on a table,
each of which has a letter on one side and a number on the other. Suppose that
those cards are showing respectively $D$, $K$, $3$, $7$. Given the sentence:
“Every card which has the letter $D$ on one side has the number $3$ on the
other side”, which cards are to be turned over in order to verify the truth of
the sentence? Testing on college students, it turns out that a relatively
small number of students select the logically correct answer ‘$D$ and $7$’
(4%), while others select ‘$D$ and $3$’ (46%) or $D$ alone (33%) (Wason and
Shapiro, (1971)). The result shows that people are likely to perform AC
inference but less likely to perform logically correct DC inference in this
task. The situation is characterized in our framework as follows.

The sentence: “Every card which has the letter $D$ on one side has the number
$3$ on the other side” is rephrased as “If a card has the letter $D$ on one
side, then it has the number $3$ on the other side”. Then it is represented by
the program:

$\Pi_{W}=\\{\,n_{3}\leftarrow\ell_{D}\\}$ (15)

where $n_{3}$ means the number 3 and $\ell_{D}$ means the letter $D$. Four
cards on the desk are represented by the facts:

$\ell_{D}\leftarrow,\quad\ell_{K}\leftarrow,\quad n_{3}\leftarrow,\quad
n_{7}\leftarrow.$ (16)

Then each card is checked one by one.

  * •

$\Pi_{W}\cup\\{\ell_{D}\leftarrow\\}$ has the answer set
$\\{\ell_{D},n_{3}\\}$. If the other side of $\ell_{D}$ is not the number 3,
however, $\\{\ell_{D},n_{3}\\}\cup\\{\neg n_{3}\\}$ is contradictory. To
verify the consistency, one has to turn over the card of $D$.

  * •

$\Pi_{W}\cup\\{\ell_{K}\leftarrow\\}$ has the answer set $\\{\ell_{K}\\}$.
Since both $\\{\ell_{K}\\}\cup\\{n_{3}\\}$ and $\\{\ell_{K}\\}\cup\\{\neg
n_{3}\\}$ are consistent, there is no need to turn over the card of $K$.

  * •

$\Pi_{W}\cup\\{n_{3}\leftarrow\\}$ has the answer set $\\{n_{3}\\}$. Since
both $\\{n_{3}\\}\cup\\{\ell_{D}\\}$ and $\\{n_{3}\\}\cup\\{\neg\ell_{D}\\}$
are consistent, there is no need to turn over the card of $3$.

  * •

$\Pi_{W}\cup\\{n_{7}\leftarrow\\}$ has the answer set $\\{n_{7}\\}$. Since
both $\\{n_{7}\\}\cup\\{\ell_{D}\\}$ and $\\{n_{7}\\}\cup\\{\neg\ell_{D}\\}$
are consistent, there is no need to turn over the card of $D$.

As the standard ASP does not realize DC inference, it characterizes reasoners
who select only $D$ as shown above.

By contrast, people who choose $D$ and $3$ are likely to perform AC inference
using the conditional sentence. In this case, the situation is represented as

$AC(\Pi_{W})=\\{\,n_{3}\leftarrow\ell_{D},\;\;\;\ell_{D}\leftarrow
n_{3}\,\\}.$

Now $AC(\Pi_{W})\cup\\{n_{3}\leftarrow\\}$ has the answer set
$\\{n_{3},\ell_{D}\\}$. If the other side of $n_{3}$ is not the letter $D$,
however, $\\{n_{3},\ell_{D}\\}\cup\\{\neg\ell_{D}\\}$ is contradictory. To
verify the consistency, they opt to turn over the card of $3$ as well as the
card of $D$.

Finally, those who choose $D$ and $7$ perform weak DC inference
as222Alternatively, the SDC $\neg\,\ell_{D}\leftarrow\neg\,n_{3}$ is used by
introducing the rule $\neg\,n_{3}\leftarrow n_{7}$ instead of the constraint
$\leftarrow n_{3},n_{7}$.

$\mathit{WDC}(\Pi_{W})=\\{\,n_{3}\leftarrow\ell_{D},\;\;\;not\,\ell_{D}\leftarrow
not\,n_{3}\,\\}.$

The program $\mathit{WDC}(\Pi_{W})\cup\\{n_{7}\leftarrow\\}$ has the answer
set $\\{n_{7}\\}$. However, if the other side of $n_{7}$ is the letter $D$,
$\mathit{WDC}(\Pi_{W})\cup\\{n_{7}\leftarrow\\}\cup\\{\ell_{D}\leftarrow\\}\cup\\{\leftarrow
n_{3},n_{7}\\}$ is incoherent, where the constraint $\leftarrow n_{3},n_{7}$
represents that one card cannot have two numbers. To verify the consistency,
they need to turn over the card 7 as well as the card of $D$.333Kowalski,
(2011) also uses an integrity constraint to explain the effect of modus
tollens in the selection task.

It is known that the Wason selection task is context dependent and the results
change when, for instance, it is presented with a deontic rule. Griggs and
Cox, (1982) use the rule: “If a person is drinking beer, then the person must
be over 19 year of age”. There are four cards on a table as before, but this
time a person’s age is on one side of a card and on the other side is what the
person is drinking. Four cards show, ‘beer’, ‘coke’, ‘16’, and ‘22’,
respectively. Then select the card(s) needed to turn over to determine whether
or not no person is violating the rule. In this drinking-age problem, almost
75% of participants select logically correct answers ‘beer’ and ‘16’. To
characterize the situation, (W)DC completion is used for representing
selection tasks in deontic contexts.

##  6 Applications to Commonsense Reasoning

The AC, DC, DA completions realize human conditional reasoning in ASP. In
addition, they are used for computing commonsense reasoning in AI.

###  6.1 Abduction and Prediction

Abduction reasons from an observation to explanations. An abductive logic
program (Kakas et al., (1992)) is defined as a pair
$\langle\,\Pi,\Gamma\,\rangle$ where $\Pi$ is a program and
$\Gamma\,(\subseteq Lit$) is a set of literals called abducibles.444Integrity
constraints are included as constraints in $\Pi$. It is assumed that
abducibles appear in the head of no rule in $\Pi$. Given an observation $O$ as
a ground literal, the abduction problem is to find an explanation
$E\,(\subseteq\Gamma)$ satisfying (i) $P\cup E\models_{x}O$ and (ii) $P\cup E$
is consistent, where $\models_{x}$ is either $\models_{c}$ or $\models_{s}$
depending on the problem. Here we consider $\models_{c}$ that realizes
credulous abduction. In GEDP, the abduction problem is characterized as
follows. Let us define

$abd(\Gamma)=\\{\,\gamma\,;\,not\,\gamma\,\leftarrow\;\mid\;\gamma\in\Gamma\,\\}.$

######  Proposition 6.1 (Inoue and Sakama, (1998)).

Let $\langle\,\Pi,\Gamma\,\rangle$ be an abductive program. Given an
observation $O$, a set $E\subseteq\Gamma$ is an explanation of $O$ iff
$\Pi\cup abd(\Gamma)\cup\\{\,\leftarrow not\,O\,\\}$ has a consistent answer
set $S$ such that $S\cap\Gamma=E$.

######  Example 6.2.

Consider $(\Pi_{1},\Gamma_{1})$ where

$\displaystyle\Pi_{1}:$ $\displaystyle arrive\\_on\\_time\leftarrow
not\;accident,$ $\displaystyle\neg\,arrive\\_on\\_time\leftarrow accident.$
$\displaystyle\Gamma_{1}:$ $\displaystyle accident.$

$\Pi_{1}$ represents that a train arrives on time unless there is an accident.
Given the observation $O=\neg\,arrive\\_on\\_time$, it has the explanation
$E=\\{accident\\}$. The problem is represented as the GEDP:

$\displaystyle arrive\\_on\\_time\leftarrow not\;accident,$
$\displaystyle\neg\,arrive\\_on\\_time\leftarrow accident,$ $\displaystyle
accident\,;\,not\,accident\leftarrow,$ $\displaystyle\leftarrow
not\,\neg\,arrive\\_on\\_time$

which has the answer set $S=\\{\neg\,arrive\\_on\\_time,\;accident\\}$ where
$S\cap\Gamma_{1}=E$.

Since abduction reasons backward from an observation, it is characterized
using AC inference as follows.

######  Proposition 6.3.

Let $\langle\,\Pi,\Gamma\,\rangle$ be an abductive program and $O$ an
observation.

(i) A set $E\subseteq\Gamma$ is an explanation of $O$ if $O\in head^{+}(r)$
for some $r\in\Pi$ and $AC(\Pi)\cup\\{O\\}$ has a consistent answer set $S$
such that $S\cap\Gamma=E$.

(ii) If a set $E\subseteq\Gamma$ is an explanation of $O$, then there is
$\Pi^{\prime}\subseteq\Pi$ such that $AC(\Pi^{\prime})\cup\\{O\\}$ has a
consistent answer set $S$ such that $S\cap\Gamma=E$.

######  Proof 6.4.

(i) Suppose that $O\in head^{+}(r)$ for some $r\in\Pi$ and
$AC(\Pi)\cup\\{O\\}$ has a consistent answer set $S$ such that
$S\cap\Gamma=E$. By the definition of $AC(\Pi)$, there is a path from $O$ to
literals in $E$ in the dependency graph555A not-free EDP $\Pi$ is associated
with a dependency graph $(V,E)$ where the nodes $V$ are literals of $\Pi$ and
there are edges in $E$ from $L\in body^{+}(r)$ to $L^{\prime}\in head^{+}(r)$
for each $r\in\Pi$.  of the program $AC(\Pi)^{S}\cup\\{O\\}$ where
$AC(\Pi)^{S}$ is the reduct of $AC(\Pi)$ by $S$. In this case, $O$ is reached
by reasoning forward from $E$ in $\Pi^{S}$, and $S$ is an answer set of
$\Pi^{S}\cup E$ such that $O\in S$. This implies that $\Pi\cup
E\cup\\{\leftarrow not\,O\\}$ has a consistent answer set $S$ such that
$abd(\Gamma)^{S}=E$, and the result holds by Proposition 6.1

(ii) If $E\subseteq\Gamma$ is an explanation of $O$, there is
$\Pi^{\prime}\subseteq\Pi$ such that $\Pi^{\prime}\cup
abd(\Gamma)\cup\\{\leftarrow not\,O\\}$ has a consistent answer set $S$
satisfying $S\cap\Gamma=E$ (Proposition 6.1). Select a minimal set
$\Pi^{\prime}$ of rules such that there is no
$\Pi^{\prime\prime}\subset\Pi^{\prime}$ satisfying the above condition. In
this case, $abd(\Gamma)^{S}=E$ is obtained by reasoning backward from $O$ in
$(\Pi^{\prime})^{S}$, and $S$ is a minimal set satisfying
$(\Pi^{\prime})^{S}\cup ac(\Pi^{\prime})^{S}\cup\\{O\\}$. Then
$AC(\Pi^{\prime})\cup\\{O\\}$ has a consistent answer set $S$ such that
$S\cap\Gamma=E$.

In Example 6.2, $AC(\Pi_{1})\cup\\{O\\}$ becomes

$\displaystyle arrive\\_on\\_time\leftarrow not\;accident,$
$\displaystyle\neg\,arrive\\_on\\_time\leftarrow accident.$ $\displaystyle
not\;accident\leftarrow arrive\\_on\\_time,$ $\displaystyle
accident\leftarrow\neg\,arrive\\_on\\_time,$
$\displaystyle\neg\,arrive\\_on\\_time\leftarrow,$

which has the answer set $S=\\{\,\neg\,arrive\\_on\\_time,\,accident\,\\}$. By
$S\cap\Gamma_{1}=\\{\,accident\,\\}$, $E=\\{\,accident\,\\}$ is the
explanation.

Note that $AC(\Pi)$ introduces converse of every rule, while explanations are
computed using the AC completion of a subset $\Pi^{\prime}\subseteq\Pi$ in
general (Proposition 6.3(ii)).

######  Example 6.5.

Let $\Pi=\\{\,p\leftarrow a,\;\;q\leftarrow\neg a,\;\;q\leftarrow\,\\}$ and
$\Gamma=\\{a,\neg a\\}$. Then $O=p$ has the explanation $E=\\{a\\}$ in
$\langle\,\Pi,\Gamma\,\rangle$, while
$AC(\Pi)\cup\\{O\\}=\Pi\cup\\{\,a\leftarrow p,\;\;\neg a\leftarrow
q,\;\;p\leftarrow\,\\}$ is contradictory. By putting
$\Pi^{\prime}=\\{\,p\leftarrow a\,\\}$, $AC(\Pi^{\prime})\cup\\{O\\}$ has the
consistent answer set $S=\\{p,a\\}$ where $S\cap\Gamma=\\{a\\}$.

As illustrated in the example, abduction and AC completion produce different
results in general. Abductive logic programs of (Kakas et al., (1992)) cannot
compute explanations when contrary to the consequent is observed. For
instance, consider $\langle\,\Pi_{2},\Gamma_{2}\,\rangle$ such that

$\displaystyle\Pi_{2}:$ $\displaystyle arrive\\_on\\_time\leftarrow
not\;accident.$ $\displaystyle\Gamma_{2}:$ $\displaystyle accident.$

Given the observation $O=\neg\,arrive\\_on\\_time$, no explanation is obtained
from $\langle\,\Pi_{2},\Gamma_{2}\,\rangle$. Generally, a program $\Pi$ does
not necessarily contain a pair of rules $r$ and $r^{\prime}$ that define $L$
and $\neg L$, respectively. When there is a rule defining $L$ but no rule
defining $\neg L$, abduction computes no explanation for the observation
$O=\neg L$. The problem is resolved by reasoning by DC. For the rule $r$ in
$\Pi_{2}$, $sdc(r)$ becomes

$accident\leftarrow\neg\,arrive\\_on\\_time.$

Then $SDC(\Pi_{2})\cup\\{O\\}$ computes the explanation $\\{\,accident\,\\}$.

In contrast to $SDC$, $WDC$ is used for abduction from negative observations.
A negative observation represents that some evidence $G$ is not observed and
it is represented as $O=not\,G$, which should be distinguished from the
(positive) observation $O=\neg\,G$ meaning that $\neg\,G$ is observed. In the
abductive program $\langle\,\Pi_{2},\Gamma_{2}\,\rangle$, the negative
observation $O=not\,arrive\\_on\\_time$ is explained using $wdc(r)$:

$accident\leftarrow not\;arrive\\_on\\_time.$

Then $WDC(\Pi_{2})\cup\\{O\\}$ has the answer set $\\{\,accident\,\\}$.

In this way, both AC and DC are used for computing explanations deductively,
and DC is used for computing explanations that are not obtained using the
framework of (Kakas et al., (1992)). Moreover, AC and DC realize prediction by
combining abduction and deduction.

######  Example 6.6.

Consider $(\Pi_{3},\Gamma_{3})$ where

$\displaystyle\Pi_{3}:$ $\displaystyle arrive\\_on\\_time\leftarrow
not\;accident,$ $\displaystyle\neg\,arrive\\_on\\_time\leftarrow accident,$
$\displaystyle newspaper\leftarrow accident.$ $\displaystyle\Gamma_{3}:$
$\displaystyle accident.$

The third rule in $\Pi_{3}$ says: if there is an accident, a newspaper will
report it. Given the observation $O=\neg\,arrive\\_on\\_time$,
$AC(\Pi_{3})\cup\\{O\\}\models_{s}newspaper$.

In this way, AC or DC combines abduction and deduction to realize prediction.

###  6.2 Counterfactual Reasoning

A counterfactual is a conditional statement representing what would be the
case if its premise were true (although it is not true in fact). Lewis, (1973)
introduces two different types of counterfactual sentences. Given two
different events $\varphi$ and $\psi$, “if it were the case that $\varphi$,
then it would be the case that $\psi$” (written
$\varphi\,\Box\\!\\!\\!\rightarrow\,\psi$) and “if it were the case that
$\varphi$, then it might be the case that $\psi$” (written
$\varphi\,\Diamond\\!\\!\\!\rightarrow\,\psi$). Here
$\varphi\,\Box\\!\\!\\!\rightarrow\,\psi$ implies
$\varphi\,\Diamond\\!\\!\\!\rightarrow\,\psi$. We characterize these types of
counterfactual reasoning using DA inference in ASP.

######  Definition 6.7 (counterfact).

Let $\varphi$ be a fact of the form:

$L_{1}\,;\,\cdots\,;\,L_{k}\,;\,not\,L_{k+1}\,;\cdots;\,not\,L_{l}\leftarrow\quad(1\leq
k\leq l).$

Then the counterfact $\overline{\varphi}$ is the set of facts such that

$\overline{\varphi}=\\{\,\neg\,L_{i}\leftarrow\,\mid\,1\leq i\leq
k\,\\}\;\cup\;\\{\,L_{j}\leftarrow\,\mid\,k+1\leq j\leq l\,\\}.$

Given a set $\Sigma$ of facts, define

$\overline{\Sigma}=\bigcup_{\varphi\in\Sigma}\overline{\varphi}.$

We say that $\overline{\Sigma}$ satisfies the conjunction
$L_{l+1},\,\ldots,\,L_{m},\,not\,L_{m+1},\,\ldots,\,not\,L_{n}$ if
$\\{\,L_{i}\leftarrow\,\mid\,l+1\leq i\leq m\\}\subseteq\overline{\Sigma}$ and
$\\{\,L_{j}\leftarrow\,\mid\,m+1\leq i\leq
n\\}\cap\overline{\Sigma}=\varnothing$.

######  Definition 6.8 (counterfactual program).

Let $\Pi$ be a program and $\Sigma$ a set of facts in $\Pi$. Then, a
counterfactual program $\Omega$ is defined as

$\Omega=(\Pi\setminus\Sigma)\;\cup\;\overline{\Sigma}\;\cup\;sda(\Pi).$

For $\lambda\in Lit$, define

$\displaystyle\overline{\Sigma}\;\Box\\!\\!\\!\rightarrow\,\lambda\;\;\mbox{if}\;\;\Omega\models_{s}\lambda,$
$\displaystyle\overline{\Sigma}\;\Diamond\\!\\!\\!\rightarrow\,\lambda\;\;\mbox{if}\;\;\Omega\models_{c}\lambda.$

By definition, $\Omega$ is obtained by first removing a set $\Sigma$ of facts
and instead introducing a set $\overline{\Sigma}$ of counterfacts. Second,
introduce strong DA rules. Then,
$\overline{\Sigma}\;\Box\\!\\!\\!\rightarrow\,\lambda$ (resp.
$\overline{\Sigma}\;\Diamond\\!\\!\\!\rightarrow\,\lambda$) means that if the
counterfacts $\overline{\Sigma}$ were the case, then $\lambda$ is included in
every (resp. some) answer set of $\Omega$.

######  Example 6.9.

Consider the program $\Pi$:

$\displaystyle London\,;\,Paris\leftarrow not\;virtual,$ $\displaystyle
virtual\leftarrow pandemic,$ $\displaystyle pandemic\leftarrow.$

An event is scheduled to take place in either London or Paris if it is not
virtual. The pandemic turns the event into virtual, however. Suppose a
counterfactual sentence: “if there were no pandemic, the event would not be
virtual”. Putting $\Sigma=\\{pandemic\\}$, $\Omega$ becomes:

$\displaystyle London\,;\,Paris\leftarrow not\;virtual,$ $\displaystyle
virtual\leftarrow pandemic,$ $\displaystyle\neg\,London\leftarrow virtual,$
$\displaystyle\neg\,Paris\leftarrow virtual,$
$\displaystyle\neg\,virtual\leftarrow\neg\,pandemic,$
$\displaystyle\neg\,pandemic\leftarrow.$

$\Omega$ has two answer sets

$\displaystyle\\{\,\neg\,pandemic,\;\neg\,virtual,\;London\,\\},$
$\displaystyle\\{\,\neg\,pandemic,\;\neg\,virtual,\;Paris\,\\}.$

As a result, it holds that

$\\{\neg\,pandemic\\}\,\Box\\!\\!\\!\rightarrow\,\neg\,virtual\quad\mbox{and}\quad\\{\neg\,pandemic\\}\,\Diamond\\!\\!\\!\rightarrow\,London.$

Given a consistent program $\Pi$, it might be the case that the program
$\Omega$ is inconsistent. To eliminate contradictory $\Omega$, default DA
completion is used instead of DA completion. Define $\Omega_{D}$ that is
obtained by replacing $sda(\Pi)$ by its default version $sdda(\Pi)$ in
Definition 6.8. The next result holds by Proposition 4.10.

######  Proposition 6.10.

Let $\Pi$ be a program and $\Sigma$ a set of facts in $\Pi$. If
$(\Pi\setminus\Sigma)\,\cup\,\overline{\Sigma}$ is consistent, then
$\Omega_{D}$ is not contradictory.

######  Proof 6.11.

Put $\Pi^{\prime}=(\Pi\setminus\Sigma)\,\cup\,\overline{\Sigma}$. Since facts
are set aside in (SD)DA completion, $SDDA(\Pi^{\prime})=SDDA(\Pi)$. Then
$\Omega_{D}=\Pi^{\prime}\cup sdda(\Pi)=\Pi^{\prime}\cup sdda(\Pi^{\prime})$,
and the result holds by Proposition 4.10.

###  6.3 Neighborhood Inference

Cooperative query answering analyzes the intent of a query and provides
associated information relevant to the query (Chu et al., (1990)).
Neighborhood inference (Gaasterland et al., (1992)) is a technique used for
such a purpose and reasons up/down in a hierarchy of atoms to reach
neighboring facts.

######  Example 6.12.

A travel agency has flight information represented by the program $\Pi$:

$\displaystyle travel(LHR,CDG)\leftarrow flight(AF1681),$ $\displaystyle
travel(LHR,CDG)\leftarrow flight(BA306),$ $\displaystyle
travel(NRT,CDG)\leftarrow flight(AF275),$ $\displaystyle
flight(BA306)\leftarrow,\;\;\;\neg\,flight(AF1681)\leftarrow,\;\;\;flight(AF275)\leftarrow.$

Suppose that a customer asks the availability of a flight AF1681 from LHR to
CDG. Unfortunately, no ticket is available on the requested time of a day. The
agent then proposes an alternative flight BA306 that is still available.

In this scenario, from the request $flight(AF1681)$ the agent understands that
the customer wants to travel from London (LHR) to Paris (CDG). The request
$flight(AF1681)$ is then relaxed to $travel(LHR,CDG)$, and reaches the fact
$flight(BA306)$.

Neighborhood inference consists of two steps: generalization from the body to
the head of one rule, and specialization from the head to the body of another
rule. The generalization is the inference of affirming the antecedent, while
the specialization is the inference of affirming the consequent. Then
neighborhood inference is realized by combining AA and AC. In what follows,
$\Pi$ is partitioned into the set of non-factual rules $\Pi_{R}$ and the set
of facts $\Pi_{F}$.

######  Definition 6.13 (neighborhood solution).

Let $\Pi$ be a program such that $\Pi=\Pi_{R}\cup\Pi_{F}$ and $G$ a literal
representing a request. Define

$\displaystyle U$ $\displaystyle=$
$\displaystyle\\{\,r\,\mid\,r\in\Pi_{R}\;\mbox{and}\;G\in body^{+}(r)\,\\},$
$\displaystyle V$ $\displaystyle=$
$\displaystyle\\{\,r^{\prime}\,\mid\,r^{\prime}\in\Pi_{R}\setminus
U\;\mbox{and}\;head^{+}(r^{\prime})\cap head^{+}(r)\neq\varnothing\;\mbox{for
some}\;r\in U\,\\}.$

If $\Pi_{R}\cup ac(V)\cup\\{G\\}$ has a consistent answer set $S$, then
$S\cap\Pi_{F}$ is called a neighborhood solution of $G$.

By definition, the AC completion is applied to a part of the program, which
realizes neighborhood inference based on a request.

######  Example 6.14 (cont. Example 6.12).

Given the request $G=flight(AF1681)$, $U=\\{\,travel(LHR,CDG)\leftarrow
flight(AF1681)\,\\}$ and $V=\\{\,travel(LHR,CDG)\leftarrow
flight(BA306)\,\\}$. Then $ac(V)=\\{\,flight(BA306)\leftarrow
travel(LHR,CDG)\,\\}$ and $\Pi_{R}\cup ac(V)$ becomes

$\displaystyle travel(LHR,CDG)\leftarrow flight(AF1681),$ $\displaystyle
travel(LHR,CDG)\leftarrow flight(BA306),$ $\displaystyle
travel(NRT,CDG)\leftarrow flight(AF275),$ $\displaystyle
flight(BA306)\leftarrow travel(LHR,CDG).$

$\Pi_{R}\cup ac(V)\cup\\{G\\}$ has the answer set

$S=\\{\,flight(AF1681),\,flight(BA306),\,travel(LHR,CDG)\,\\}.$

Hence, $S\cap\Pi_{F}=\\{flight(BA306)\\}$ is a neighborhood solution of $G$.

######  Proposition 6.15.

Let $\Pi$ be a PDP containing no constraint and $G$ an atom representing a
request. Then if $U$ and $V$ in Def. 6.13 are non-empty, $G$ has a
neighborhood solution.

######  Proof 6.16.

When $\Pi$ is a PDP containing no constraints, $AC(\Pi)$ is consistent
(Proposition 3.6). Since $\Pi_{R}\cup ac(V)\subseteq AC(\Pi)$, $\Pi_{R}\cup
ac(V)\cup\\{G\\}$ has a consistent answer set $S$. In this case, $G$ has a
neighborhood solution $S\cap\Pi_{F}$.

##  7 Related Work

There is a number of studies on human conditional reasoning in psychology and
cognitive science. In this section, we focus on related work based on logic
programming and its application to common sense reasoning.

###  7.1 Completion

The idea of interpreting if-then rules in logic programs as bi-conditional
dates back to Clark, (1978). He introduces predicate completion in normal
logic programs (NLPs), which introduces the only-if part of each rule to a
program. Given a propositional program $\Pi$, Clark completion $Comp(\Pi)$ is
obtained by two steps: (i) all rules $p\leftarrow B_{1}$,$\ldots$,
$p\leftarrow B_{k}$ in $\Pi$ having the same head $p$ are replaced by
$p\leftrightarrow B_{1}\vee\cdots\vee B_{k}$, where $B_{i}$ $(1\leq i\leq k)$
is a conjunction of literals; and (ii) for any atom $p$ appearing in the head
of no rule in $\Pi$, add $p\leftrightarrow\mathit{false}$. The AC completion
introduced in this paper extends the technique to the class of GEDP, while the
result is generally different from Clark completion in NLPs. For instance,
given the program:

$\Pi_{1}=\\{\,p\leftarrow q,\;\;\;p\leftarrow\,\\},$

Clark completion becomes

$Comp(\Pi_{1})=\\{\,p\leftrightarrow
q\vee\top,\;\;\;q\leftrightarrow\bot\,\\}$

where $\top$ and $\bot$ represent true and false, respectively.
$Comp(\Pi_{1})$ has the single completion model called a supported model (Apt
et al., (1988)) $\\{p\\}$. In contrast,

$AC(\Pi_{1})=\Pi_{1}\cup\\{\,q\leftarrow p\,\\}$

has the answer set $\\{p,q\\}$. The difference comes from the fact that in
$Comp(\Pi_{1})$, $q$ is identified with false but this is not the case in
$AC(\Pi_{1})$. In Clark completion undefined atoms (i.e., atoms appearing in
the head of no rule) are interpreted false. We do not use this type of
completion because it disturbs the basic type of AC reasoning that infers $q$
from $p$ and $p\leftarrow q$. Clark completion is extended to normal
disjunctive programs by several researchers (Lobo et al., (1988); Alviano and
Dodaro, (2016); Nieves and Osorio, (2018)). Those extensions reduce to Clark
completion in NLPs, so that they are different from the AC completion. We also
introduce the DC completion and the DA completion. When
$\Pi_{2}=\\{\,p\leftarrow not\,q\,\\}$,
$Comp(\Pi_{2})=\\{\,p\leftrightarrow\neg q,\;\;q\leftrightarrow\bot\,\\}$ has
the supported model $\\{p\\}$. On the other hand,

$WDC(\Pi_{2})=\Pi_{2}\cup\\{\,q\leftarrow not\,p\,\\}$

has two answer sets $\\{p\\}$ and $\\{q\\}$. When $\Pi_{3}=\\{\,p\leftarrow
not\,q,\;\;p\leftarrow q,\;\;q\leftarrow p\,\\}$,
$Comp(\Pi_{3})=\\{\,p\leftrightarrow q\vee\neg q,\;\;q\leftrightarrow p\,\\}$
has the supported model $\\{p,q\\}$. In contrast,

$WDA(\Pi_{3})=\Pi_{3}\cup\\{\,not\,p\leftarrow q,not\,q,\;\;not\,q\leftarrow
not\,p\,\\}$

has no answer set. As such, completion semantics introduced in this paper is
generally different from Clark completion in NLPs.

The weak completion (Hölldobler and Kencana Ramli, (2009)) leaves undefined
atoms unknown under 3-valued logic. In the program $\Pi_{1}=\\{\,p\leftarrow
q,\;\;p\leftarrow\,\\}$, the weak completion becomes

$wcomp(\Pi_{1})=\\{\,p\leftrightarrow q\vee\top\,\\}$

which is semantically equivalent to $\\{\,p\leftrightarrow\top\,\\}$. Then $p$
is true but $q$ is unknown in $wcomp(\Pi_{1})$, which is again different from
$AC(\Pi_{1})$ that has the answer set $\\{p,q\\}$. In the program
$\Pi_{2}=\\{\,p\leftarrow not\,q\,\\}$, the weak completion becomes

$wcomp(\Pi_{2})=\\{\,p\leftrightarrow\neg q\,\\}$

then both $p$ and $q$ are unknown. In contrast, $WDC(\Pi_{2})$ has two answer
sets $\\{p\\}$ and $\\{q\\}$, and $WDA(\Pi_{2})$ has the single answer set
$\\{p\\}$.

###  7.2 Human Conditional Reasoning

Stenning and Lambalgen, (2008) formulate human conditional reasoning using
Clark’s program completion under the three-valued logic of (Fitting, (1985)).
They represent a conditional sentence “if $p$ then $q$” as a logic programming
rule:666They write it “$p\wedge\neg ab\rightarrow q$” but we use the standard
writing in LP.

$q\leftarrow p\wedge\neg ab$

where $ab$ represents an abnormal atom. In this setting, DA is represented as

$\Pi_{1}=\\{\,p\leftarrow\bot,\;\;\;q\leftarrow p\wedge\neg
ab,\;\;\;ab\leftarrow\bot\,\\}$

The rule “$A\leftarrow\bot$” means that $A$ is a proposition to which the
closed world assumption (Reiter, (1978)) is applied. If a program does not
contain $A\leftarrow\bot$, nor any other rule in which $A$ occurs in its head,
then $A$ is interpreted unknown. Then its completion

$Comp(\Pi_{1})=\\{\,p\leftrightarrow\bot,\;\;\;q\leftrightarrow p\wedge\neg
ab,\;\;\;ab\leftrightarrow\bot\,\\}$

derives $q\leftrightarrow\bot$. On the other hand, completion does not realize
AC or DC inference by itself. In their framework, AC is represented as

$\Pi_{2}=\\{\,q\leftarrow\top,\;\;q\leftarrow p\wedge\neg
ab,\;\;ab\leftarrow\bot\,\\}$

while its completion

$Comp(\Pi_{2})=\\{\,q\leftrightarrow\top\vee(p\wedge\neg
ab),\;\;ab\leftrightarrow\bot\,\\}$

does not derive $p$. Likewise, DC is represented as

$\Pi_{3}=\\{\,q\leftarrow\bot,\;\;q\leftarrow p\wedge\neg
ab,\;\;ab\leftarrow\bot\,\\}$

while its completion

$Comp(\Pi_{3})=\\{\,q\leftrightarrow\bot\vee(p\wedge\neg
ab),\;\;ab\leftrightarrow\bot\,\\}$

does not derive $p\leftrightarrow\bot$. They then interpret $q\leftarrow
p\wedge\neg ab$ as an integrity constraint meaning that “if $q$ succeeds
(resp. fails) then $p\wedge\neg ab$ succeeds (resp. fails)” to get the AC
consequence $p$ (resp. DC consequence $\neg p$).

Stenning and Lambalgen, (2008) characterize the suppression task in their
formulation. The sentence “If she has an essay to write then she will study
late in the library” is represented as:

$library\;\leftarrow\;essay\wedge\neg ab_{1}.$

Given the negation of antecedent $\neg essay$ (or equivalently,
$essay\leftarrow\bot$), the completed program:

$\displaystyle library\;\leftrightarrow essay\wedge\neg ab_{1},$
$\displaystyle ab_{1}\leftrightarrow\bot,$ $\displaystyle
essay\leftrightarrow\bot$

derives $library\leftrightarrow\bot$. Next, suppose that the conditional with
an alternative antecedent: “If she has some textbooks to read then she will
study late in the library” is given. The program becomes

$\displaystyle library\;\leftarrow\;essay\wedge\neg ab_{1},$ $\displaystyle
library\;\leftarrow\;text\wedge\neg ab_{2}.$

Given the fact $\neg essay$ (or equivalently, $essay\leftarrow\bot$), the
completed program:

$\displaystyle library\;\leftrightarrow\;(essay\wedge\neg
ab_{1})\vee(text\wedge\neg ab_{2}),$ $\displaystyle
ab_{1}\leftrightarrow\bot,$ $\displaystyle ab_{2}\leftrightarrow\bot,$
$\displaystyle essay\leftrightarrow\bot$

does not derive $library\leftrightarrow\bot$. Thus, the DA inference is
suppressed. They also characterize Byrne’s suppression of valid inference.
Suppose the conditional with an additional antecedent: “If the library stays
open then she will study late in the library”. The program becomes

$\displaystyle library\;\leftarrow\;essay\wedge\neg ab_{1},$ $\displaystyle
library\;\leftarrow\;open\wedge\neg ab_{3}.$

They also introduce interaction of abnormality atoms as

$\displaystyle ab_{1}\leftarrow\neg open,$ $\displaystyle ab_{3}\leftarrow\neg
essay.$

Completing these four rules with $ab_{1}\leftarrow\bot$ and
$ab_{3}\leftarrow\bot$ produces

$\displaystyle library\leftrightarrow(essay\wedge\neg
ab_{1})\vee(open\wedge\neg ab_{3}),$ $\displaystyle ab_{1}\leftrightarrow\neg
open\vee\bot,$ $\displaystyle ab_{3}\leftrightarrow\neg essay\vee\bot,$

which reduces to

$library\leftrightarrow open\wedge essay.$

Then, $essay$ alone does not deduce $library$, so the AA inference is
suppressed. Stenning and Lambalgen, (2008) argue that most people represent
the effect of an additional premise formally as $p\leftarrow q\wedge r$ and
that of an alternative premise formally as $p\leftarrow q\vee r$. This
argument coincides with our view addressed in Section 5.1.

Dietz et al., (2012) point out a technical flaw in the formulation by
(Stenning and Lambalgen, (2008)). In the above example, open and library are
unknown (U) under the 3-valued logic, then the rule
“$library\;\leftarrow\;open\wedge\neg ab_{3}$” becomes
${\mathsf{U}}\leftarrow{\mathsf{U}}$. Under the Fitting semantics, however,
the truth value of the rule ${\mathsf{U}}\leftarrow{\mathsf{U}}$ is
${\mathsf{U}}$, then it does not represent the truth of the rule
“$library\;\leftarrow\;open\wedge\neg ab_{3}$”. To remedy the problem, they
employ Łukasiewicz’s 3-valued logic which maps
${\mathsf{U}}\leftarrow{\mathsf{U}}$ to $\top$. Dietz et al., (2012) also
characterize the suppression effects in AC or DC using an abductive logic
program $\langle\,\Pi,\Gamma\,\rangle$ with abducibles
$\Gamma=\\{\,p\leftarrow\bot,\;\;p\leftarrow\top\,\\}$. Consider
$\langle\,\Pi_{1},\Gamma_{1}\,\rangle$ where

$\displaystyle\Pi_{1}:$ $\displaystyle library\leftarrow essay\wedge\neg
ab_{1},$ $\displaystyle ab_{1}\leftarrow\bot,$ $\displaystyle\Gamma_{1}:$
$\displaystyle essay\leftarrow\bot,\;\;\;essay\leftarrow\top,$

the weakly completed program of $\Pi_{1}$ becomes

$\displaystyle library\leftrightarrow essay\wedge\neg ab_{1},$ $\displaystyle
ab_{1}\leftrightarrow\bot.$

The observation $O=(library\leftrightarrow\top)$ derives
$essay\leftrightarrow\top$, then “$essay\leftarrow\top$” is the skeptical
explanation of $O$. When the additional rules and abducibles

$\displaystyle\Pi_{2}:$ $\displaystyle library\leftarrow text\wedge\neg
ab_{2},$ $\displaystyle ab_{2}\leftarrow\bot,$ $\displaystyle\Gamma_{2}:$
$\displaystyle text\leftarrow\bot,\;\;\;text\leftarrow\top$

are given, the weakly completed program of $\Pi_{1}\cup\Pi_{2}$ becomes

$\displaystyle library\leftrightarrow(essay\wedge\neg
ab_{1})\vee(text\wedge\neg ab_{2}),$ $\displaystyle
ab_{1}\leftrightarrow\bot,$ $\displaystyle ab_{2}\leftrightarrow\bot.$

The observation $O=(library\leftrightarrow\top)$ derives $essay\vee
text\leftrightarrow\top$, and there are two credulous explanations
“$essay\leftarrow\top$” and “$text\leftarrow\top$”. In this case,
$essay\leftarrow\top$ is not concluded under skeptical reasoning, which
represents the suppression of AC.

Comparing the above mentioned two studies with our approach, there are several
differences. First, they translate a conditional sentence “if $p$ then $q$”
into the rule $q\leftarrow p\wedge\neg\,ab$. However, it is unlikely that
people who commit logical fallacies, especially younger children (Rumain et
al., (1983)), translate the conditional sentence into the rule of the above
complex form in their mind. We represent the conditional sentence directly as
$q\leftarrow p$, and assume that people would interpret it as bi-conditional
depending on the context it is used. Second, in order to characterize AC or DC
reasoning, Stenning and Lambalgen, (2008) interpret a conditional sentence as
an integrity constraint, while (Dietz et al., (2012)) uses abductive logic
programs. Our framework does not need a specific interpretation of rules (such
as integrity constraints) nor need an extra mechanism of abductive logic
programs. Third, they use a single (weak) completion for all AC/DA/DC
reasoning, while we introduce different types of completions for each
inference. By separating respective completions, individual inferences are
realized in a modular way and freely combined depending on their application
context. For instance, we use AC and (S)DA completion to characterize the
suppression task (Section 5.1), while use AC and (W)DC completion to
characterize Wason selection task (Section 5.2). Fourth, they handle normal
logic programs, while our framework can handle a more general class of logic
programs containing disjunction and two different types of negation. For
instance, consider the rule: “$buy\\_car\,;\,buy\\_house\leftarrow
win\\_lottery$” (if she wins the lottery, she buys a car or a house). When it
is known that $buy\\_car$ is true, one may infer $win\\_lottery$ by AC
inference. The AC completion realizes such an inference by introducing rules:
“$win\\_lottery\leftarrow buy\\_car$” and “$win\\_lottery\leftarrow
buy\\_house$”.

Cramer et al., (2021) represent conditionals as in (Stenning and Lambalgen,
(2008)) and use the weak completion and abductive logic programs as in (Dietz
et al., (2012)). They formulate different types of conditionals based on their
contexts and argue in which case AC or DC is more likely to happen. More
precisely, a conditional sentence whose consequent appears to be obligatory
given the antecedent is called an obligation conditional. An example of an
obligation conditional is that “if Paul rides a motorbike, then he must wear a
helmet”. If the consequence of a conditional is not obligatory, then it is
called a factual conditional. The antecedent $A$ of a conditional sentence is
said to be necessary iff its consequent $C$ cannot be true unless $A$ is true.
For example, the library being open is a necessary antecedent for studying in
the library. Cramer $et\,al.$ argue that AA and DA occur independently of the
type of a conditional. On the other hand, in AC most people will conclude $A$
from $A\Rightarrow C$ and $C$, while the number of people who conclude nothing
will increase if $A$ is a non-necessary antecedent. In DC, most people will
conclude $\neg\,A$ from $A\Rightarrow C$ and $\neg\,C$, while the number of
people who conclude nothing will increase if the conditional is factual. Those
assumptions are verified by questioning participants who do not receive any
education in logic beyond high school training. They then formulate the
situation by introducing the abducible $C\leftarrow\top$ if the antecedent is
non-necessary, and $ab\leftarrow\top$ if the conditional is factual. In the
former case, the observation $C$ does not imply $A$ because the additional
$C\leftarrow\top$ can make $C$ explainable by itself. As a result, $A$ is not
a skeptical explanation of $C$. In the latter case, the observation $\neg\,C$
does not imply $\neg\,A$ because if one employs the explanation
$ab\leftarrow\top$, $C\leftarrow A\wedge\neg ab$ does not produce
$C\leftrightarrow A$.

Dietz et al., (2022) use logic programming rules to represent different types
of conditionals. For instance,

${\mathsf{c}oncl}\leftarrow{\mathsf{p}rem(x)},\,{\mathsf{s}ufficient(x)}$

represents MP that ${\mathsf{c}oncl}$ follows if a sufficient premise is
asserted to be true. By contrast,

${\mathsf{n}ot\\_concl}\leftarrow{\mathsf{n}ot\\_prem(x)},\,{\mathsf{n}ecessary(x)}$

represents DA that ${\mathsf{c}oncl}$ does not follow if a necessary premise
is asserted to be false. With these rules, Byrne’s suppression effect is
represented as follows. First, given the fact ${\mathsf{p}rem(essay)}$ and
${\mathsf{s}ufficient(essay)}$,

${\mathsf{l}ibrary}\leftarrow{\mathsf{p}rem(essay)},\,{\mathsf{s}ufficient(essay)}$

implies ${\mathsf{l}ibrary}$. Next, given the additional fact
${\mathsf{n}ecessary(open)}$, in the absence of ${\mathsf{p}rem(open)}$

${\mathsf{n}ot\\_library}\leftarrow{\mathsf{n}ot\\_prem(open)},\,{\mathsf{n}ecessary(open)}$

has the effect of withdrawing ${\mathsf{l}ibrary}$. In the current study, we
do not distinguish different types of conditionals as in (Cramer et al.,
(2021); Dietz et al., (2022)). However, completion is done for individual
rules, so we could realize partial completion by selecting rules
$\Pi^{\prime}\subseteq\Pi$ that are subject to be completed in practice. More
precisely, if a program $\Pi$ consists of rules $R_{1}$ having necessary
antecedents and $R_{2}$ having non-necessary antecedents, apply AC completion
to $R_{1}$ while keep $R_{2}$ as they are. The resulting program then realizes
AC inference using $R_{1}$ only. Likewise, if a program $\Pi$ consists of
rules $R_{3}$ having obligatory consequents and $R_{4}$ having factual
consequents, apply DC completion to $R_{3}$ while keep $R_{4}$ as they are.
The resulting program then realizes DC inference using $R_{3}$ only. Such a
partial completion is also effectively used for commonsense reasoning in this
paper (Proposition 6.3(ii), Definition 6.13).

###  7.3 Commonsense Reasoning

Console et al., (1991) and (Fung and Kowalski, (1997)) compute abduction by
deduction using Clark completion. Abduction using AC and DC completion is
close to those approaches, while the approach based on Clark completion is
restricted to normal logic programs (NLPs). We argued that a (positive)
observation $O=\neg G$ is distinguished from a negative observation
$O=not\,G$, but such a distinction is not considered in NLPs handling only
default negation. Inoue and Sakama, (1999) introduce transaction programs to
compute extended abduction. Extended abduction computes explanations for not
only (positive) observations but also negative ones. A transaction program is
constructed based on the converse of conditionals, and its semantics is
operationally given as a fixpoint of the program. A transaction program is a
meta-level specification of the procedure and is different from the current
approach. Moreover, a transaction program is defined for NLPs only.

Pereira $et\,al.$ (1991; 2017) realize counterfactual reasoning in logic
programming. In (Pereira et al., (1991)), a counterfactual conditional
$\varphi>\psi$ (meaning $\varphi\,\Box\\!\\!\\!\rightarrow\,\psi$) is
evaluated in a program $P$ by adding $\varphi$ to $P$ and computing the
maximal non-contradictory submodels of the new program. Then the
counterfactual conditional is true iff $\psi$ holds in all such submodels.
Pereira and Saptawijaya, (2017) first use abduction to compute possible causes
of an event. Next, they assume counterfactual assumption and verify whether an
expected outcome will happen under possible causes. These studies consider
extended/normal logic programs under the well-founded semantics and realize
counterfactual reasoning via program revision or abductive reasoning. Unlike
our approach, they do not introduce new rules for DA inference in
counterfactual reasoning.

Gaasterland et al., (1992) introduce neighborhood inference for query
answering in Horn logic programs. The scope of a query is expanded by relaxing
the specification, which allows a program to return answers related to the
original query. They introduce a meta-interpreter to realize it and argue for
control strategies. We show that similar reasoning is simulated in ASP using
the AC completion.

##  8 Conclusion

This paper studies a method of realizing human conditional reasoning in ASP.
Different types of completions are introduced to realize logically invalid
inferences AC and DA as well as a logically valid inference DC. They are
applied to representing human reasoning tasks in the literature, and are also
used for computing common sense reasoning in AI. In psychology and cognitive
science, empirical studies show that people perform AC, DA or DC inference
depending on the context in which a conditional sentence is used. We could
import the results of those studies and encode knowledge in a way that people
are likely to use it. The proposed theory is used for such a purpose to
realize pragmatic inferences in ASP and produce results that are close to
human reasoning in practice.

Completions introduced in this paper are defined in a modular way, so one can
apply respective completion to specific rules of a program according to their
contexts. They are combined freely and can be mixed in the same program. Those
completions are general in the sense that they are applied to logic programs
containing disjunction, explicit and default negation. Since a completed
program is still in the class of GEDPs and a GEDP is transformed to a
semantically equivalent EDP (Inoue and Sakama, (1998)), answer sets of
completed programs are computed using existing answer set solvers.

## References

  * Alviano and Dodaro, (2016) Alviano, M. & Dodaro, C. 2016.  Completion of disjunctive logic programs.  In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, pp. 886–892.
  * Apt et al., (1988) Apt, K. R., Blair, H. A. & Walker, A. 1988.  Towards a theory of declarative knowledge.  In: J. Minker (ed.), Foundations of Deductive Databases and Logic Programming, Morgan Kaufmann, pp. 89–148.
  * Braine, (1978) Braine, M. D. S. 1978.  On the relation between the natural logic of reasoning and standard logic.  Psychological Review 85:1–21.
  * Braine and O’Brien, (1998) Braine, M. D. S. & O’Brien, D. P. (eds.) 1998.  Mental Logic. Mahwah, NJ: Erlbaum.
  * Byrne, (1989) Byrne, R. M. J. 1989.  Suppressing valid inferences with conditionals.  Cognition 31(1), pp. 61–83.
  * Byrne, (2005) Byrne, R. M. J. 2005.  The Rational Imagination: How People Create Alternatives to Reality.  Cambridge, MA: MIT Press.
  * Cheng and Holyoak, (1985) Cheng, P. W. & Holyoak, H. J. 1985.  Pragmatic reasoning schemas.  Cognitive Psychology 17:391–416.
  * Chu et al., (1990) Chu, W. W., Chen, Q. & Lee, R.-C. 1990.  Cooperative query answering via type abstraction hierarchy.  In: S. M. Deen (ed.), Cooperating Knowledge Based Systems, Springer, pp. 271–290.
  * Clark, (1978) Clark, K. L. 1978.  Negation as failure.  In: H. Gallaire and J. Minker (eds.), Logic and Data Bases, Plenum Press, pp. 293–322.
  * Console et al., (1991) Console, L., Dupré, D. T. & Torasso, P. 1991.  On the relationship between abduction and deduction.  Journal of Logic and Computation 1, pp. 661–690.
  * Cosmides and Tooby, (1992) Cosmides, L. & Tooby, J. 1992.  Cognitive adaptions for social exchange.  In Barkow, J., Cosmides, L., Tooby, J. (eds.). The adapted mind: Evolutionary psychology and the generation of culture. New York: Oxford University Press. pp. 163–228.
  * Cramer et al., (2021) Cramer, M., Hölldobler, S. & Ragnl, M. 2021.  Modeling human reasoning about conditionals.  In: Proceedings of the 19th International Workshop on Non-Monotonic Reasoning (NMR-21), pp. 223–232.
  * Dietz et al., (2012) Dietz, E., Hölldobler, S. & Ragni, M. 2012.  A computational approach to the suppression task.  In: Proceedings of the 34th Annual Conference of the Cognitive Science Society, pp. 1500–1505.
  * Dietz et al., (2022) Dietz, E., Fichte, J. K. & Hamiti, F. 2022.  A quantitative symbolic approach to individual human reasoning.  In: Proceedings of the 44th Annual Conference of the Cognitive Science Society, pp. 2838–2846.
  * Eichhorn et al., (2018) Eichhorn, C., Kern-Isberner, G. & Ragni, M. 2018.  Rational inference patterns based on conditional logic.  In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI-18), pp. 1827–1834.
  * Fitting, (1985) Fitting, M. 1985.  A Kripke-Kleene semantics for logic programs.  Journal of Logic Programming 2, pp. 295–312.
  * Fung and Kowalski, (1997) Fung, T. H. & Kowalski, R. 1997.  The iff procedure for abductive logic programming.  Journal of Logic Programming 33, pp. 151–165.
  * Gaasterland et al., (1992) Gaasterland, T., Godfrey, P. & Minker, P. 1992.  Relaxation as a platform for cooperative answering.  Journal of Intelligence Information Systems 1(3/4):293–321.
  * Geis and Zwicky, (1971) Geis, M. L. & Zwicky, A. 1971.  On invited inferences.  Linguistic Inquiry 2, pp. 561–566.
  * Gelfond and Lifschitz, (1991) Gelfond, M. & Lifschitz, V. 1991.  Classical negation in logic programs and disjunctive databases.  New Generation Computing 9 (3&4), pp. 365–385.
  * Griggs and Cox, (1982) Griggs, R. A. & Cox, J. R. 1982.  The elusive thematic‐materials effect in Wason’s selection task.  British journal of psychology 73(3), pp. 407–420.
  * Hölldobler and Kencana Ramli, (2009) Hölldobler, S. & Kencana Ramli, C. D. 2009.  Logic programs under three-valued Lukasiewicz’s semantics.  In: Proceedings of the 25th International Conference on Logic Programming, Lecture Notes in Computer Science, vol. 5649, Springer, pp. 464–478.
  * Horn, (2000) Horn, L. R. 2000.  From if to iff: conditional perfection as pragmatic strengthening.  Journal of Pragmatics 32, pp. 289–326.
  * Inoue and Sakama, (1998) Inoue, K. & Sakama, C. 1998.  Negation as failure in the head.  Journal of Logic Programming 35, pp. 39–78.
  * Inoue and Sakama, (1999) Inoue, K. & Sakama, C. 1999.  Computing extended abduction through transaction programs.  Annals of Mathematics and Artificial Intelligence 25, pp. 339–367.
  * Johnson-Laird, (1983) Johnson-Laird, P. N. 1983.  Mental models.  Cambridge, MA: Harvard University Press.
  * Kakas et al., (1992) Kakas, A. C., Kowalski, R. A. & Toni, F. 1992.  Abductive logic programming.  Journal of Logic and Computation 2(6), pp. 719–770.
  * Kowalski, (2011) Kowalski, R. A. 2011.  Computational Logic and Human Thinking: How to be Artificially Intelligent.  Cambridge University Press.
  * Lifschitz and Woo, (1992) Lifschitz, V. & Woo, T. Y. C. 1992.  Answer sets in general nonmonotonic reasoning (preliminary report).  In: B. Nebel, C. Rich, and W. Swartout (eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference, Morgan Kaufmann, pp. 603–614.
  * Lifschitz et al., (2001) Lifschitz, V., Pearce, D. & Valverde, A. 2001.  Strongly equivalent logic programs.  ACM Transactions on Computational Logic 2, pp. 526–541.
  * Lewis, (1973) Lewis, D. 1973.  Counterfactuals. Blackwell Publishing.
  * Lobo et al., (1988) Lobo, J., Minker, J. & Rajasekar, A. 1988.  Weak completion theory for non-Horn programs,  In: R. A. Kowalski and K. A. Bowen (eds.), Proceedings of the Fifth lnternational Conference and Symposium on Logic Programming, MIT Press, Cambridge, MA, pp. 828–842.
  * Nieves and Osorio, (2018) Nieves, J. C. & Osorio, M. 2018.  Extending well-founded semantics with Clark’s completion for disjunctive logic programs.  Hindawi Scientific Programming, Article ID 4157030.
  * Oaksford and Chater, (2001) Oaksford, M. & Chater, N. 2001.  The probabilistic approach to human reasoning.  Trends in Cognitive Science 5, pp. 349–357.
  * Pereira et al., (1991) Pereira, L. P., Aparício, J. N. & Alferes, J. J. 1991.  Counterfactual reasoning based on revising assumptions.  In: Logic Programming, Proceedings of the 1991 International Symposium, MIT Press, pp. 566–577.
  * Pereira and Saptawijaya, (2017) Pereira, L. P. & Saptawijaya, A. 2017.  Counterfactuals in logic programming.  In: Programming Machine Ethics, Springer, pp. 81–93.
  * Reiter, (1978) Reiter, R. 1978.  On closed world data bases.  In: H. Gallaire and J. Minker (eds.), Logic and Data Bases, Plenum Press, pp. 119–140.
  * Reiter, (1980) Reiter, R. 1980.  A logic for default reasoning,  Artificial Intelligence 13:81–132.
  * Rumain et al., (1983) Rumain, B., Connell, J., & Braine, M. D. S. 1983.  Conversational comprehension processes are responsible for reasoning fallacies in children as well as adults: IF is not the biconditional.  Developmental Psychology, 19:471–481.
  * Stenning and Lambalgen, (2008) Stenning, K. & van Lambalgen, M. 2008.  Human Reasoning and Cognitive Science, MIT Press.
  * Wason, (1968) Wason,, P. C. 1968.  Reasoning about a rule,  Quarterly Journal of Experimental Psychology 20:273–281.
  * Wason and Shapiro, (1971) Wason, P. C. & Shapiro, D. 1971.  Natural and contrived experience in a reasoning problem,  Quarterly Journal of Experimental Psychology, 23:63–71.