Leila Amgoud

Victor David

Measuring Similarity between Logical Arguments

Argumentation is a prominent approach for reasoning with (inconsistent) propositional information. It is based on the justification of formulas by arguments, which are minimal and consistent logical proofs of the formulas.

The aim of this paper is to evaluate to what extent two such arguments are similar. For that purpose, we introduce a notion of similarity measure and a set of principles that such a measure should satisfy. We propose some intuitive extensions of measures from the literature, and show that they fail to satisfy some of the principles. Then, we come up with a more discriminating measure which satisfies them all.

Introduction

Argumentation is a reasoning process based on the justification of claims by arguments, i.e., reasons for accepting claims. It has been extensively developed in Artificial Intelligence. Indeed, it was used for different purposes including decision making (eg. [Amgoud andPrade2009, Bonet andGeffner1996]), defeasible reasoning (eg. [Governatori et al.2004, García andSimari2004]), and negotiation [Sycara1990, Hadidi et al.2010].

Argumentation is also used as an alternative approach for handling inconsistency in knowledge bases [Besnard andHunter2001, Amgoud andBesnard2013]. Starting from a knowledge base encoded in propositional logic, arguments are built using the consequence operator of the logic. An argument is a pair made of a set of formulas (called support) and a single formula (called conclusion). The conclusion follows logically from the support. An example of argument is {p, q}, p ∧ q . Its support and conclusion are respectively {p, q} and p ∧ q. Once arguments are defined, attacks between them are identified and a semantics is used for evaluating the arguments, finally formulas supported by strong arguments are inferred from the base.

The number of arguments built from a (finite) knowledge base may be infinite, which impedes the relevance of the argumentation approach. It was shown in [Amgoud et al.2014] that infiniteness is partly due to the existence of equivalent or fully similar arguments like:

{p}, p {p}, p ∧ p {p}, p ∧ p ∧ p . . .

In the same paper, the authors studied when two arguments are equivalent. Then, they proposed to keep only one argument per equivalent class in an argumentation graph.

For instance, the argument e below is attacked by four arguments a, b, c, and d. According to [Amgoud et al.2014], b and c are equivalent while a and b (resp. a and c) are not. Thus, the argumentation graph will contain a, d, and either b or c (but not both).

a : {p ∧ r}, p b : {p}, p c : {p}, p ∧ p d : {q}, q e: {¬p, ¬q}, ¬p ∧ ¬q

This approach reduces drastically the number of arguments. Furthermore, it avoids considering equivalent attackers in the evaluation of arguments by a semantics. This is particularly important for semantics, like h-Categorizer [Besnard and Hunter2001], where each attacker of an argument contributes to the decrease of the argument's strength. Thus, if an argumentation graph contains the four attackers of e, both b and c will have negative impact on e. This would lead to an inaccurate acceptability status of e. The previous approach solves this problem since it removes either b or c (but not both) from the graph.

While the previous proposal solves the problem of fully similar attackers, it leaves the issue with partially similar ones open. Indeed, pairs of arguments may share parts of their supports, parts of their conclusions, or even both. Consider again the attackers of e, namely a, b and d. According to [Amgoud et al.2014], these arguments are pairwise non-equivalent. However, while d is completely different from the two others, a and b are quite similar since their supports share p and their conclusions are the same. Thus, for an accurate evaluation of e, one would expect to consider the full strengths of a and d but only a slight impact of b (since it is quite redundant with a). This means that for an accurate evaluation of arguments, it is important to assess the degree of similarity between pairs of attackers. In the example, the degree of similarity between a and b is greater than the one between a and d.

This paper investigates similarity between pairs of logical arguments. It defines the notion of similarity measure as well as a set of principles that a measure should satisfy. Some principles describe rational behavior of a measure while others are about the origin of similarity between arguments. As a second contribution, it extends existing measures from the literature, namely the well-known Jaccard measure [Jaccard1901], Dice measure [Dice1945], Sorensen one [Sørensen1948], and their other refinements proposed in [Anderberg1973, Sneath et al.1973, Ochiai1957, Kulczynski1927]. It shows that the extended measures satisfy all the principles, except one of them which deals with conclusions of arguments. Then, it comes up with another measure which satisfies all of them.

The paper is organized as follows: It starts by presenting some background on propositional logic and arguments. Then, it introduces the notion of similarity measure and principles. In a next section, it discusses properties of measures satisfying some principles. Then, it presents extended versions of some existing measures and a novel one.

Background

Throughout the paper, we consider classical propositional logic (L, ), where L is a propositional language built up from a finite set P of variables, the two Boolean constants (true) and ⊥ (false), and the usual connectives (¬, ∨, ∧, →, ↔), and is the consequence relation of the logic.

The function Var(φ) returns all the variables occurring in the formula φ (e.g., Var(p ∧ ¬q) = {p, q}) and the function CN(φ) is the set of all logical consequences of φ, i.e. CN(φ) = {ψ ∈ L | φ ψ}. Two formulas φ, ψ ∈ L are logically equivalent, denoted by φ ≡ ψ, iff φ ψ and ψ φ; they are isomorphic if and only if there exists a permutation -a bijective renaming functionπ : P → P \ Var(φ) of the variables of φ such that ψ and π(φ)1 become logically equivalent. We say that φ and ψ are isomorphic wrt π. For instance, the formulas p ∧ ¬q and t ∧ ¬v are isomorphic wrt the renaming function π, where π

(t) = p, π(v) = q, hence π(t ∧ ¬v) = p ∧ ¬q. A finite subset Φ of L, denoted by Φ ⊆ f L, is consistent iff Φ ⊥, it is inconsistent otherwise.
Let us now define when two finite sets Φ and Ψ of formulas are equivalent. A natural definition is when the two sets have the same logical consequences, i.e., {φ ∈ L |Φ φ} = {ψ ∈ L |Ψ ψ}. Thus, the three sets {p, q}, {p ∧ p, ¬¬q}, and {p ∧ q} are pairwise equivalent. This definition is strong since it considers any inconsistent sets as equivalent. For instance, {p, ¬p} and {q, ¬q} are equivalent even if the contents (i.e. meaning of variables and formulas) of the two sets are unrelated (assume that p and q stand respectively for "the weather is nice" and "the laptop is heavy"). Furthermore, it considers the two sets {p, p → q} and {q, q → p} as equivalent while their contents are different as well. Indeed, "birds generally fly" is different from "Everything which flies is generally a bird". Moreover, the two arguments {p, p → q}, q and {q, q → p}, p may have different attackers, especially using the assumption-attack relation [Elvang-Gøransson et al.1993]. Hence, for identifying similarities between arguments, the content is crucial. The idea is to spot commonalities between supports (respectively conclusions) of arguments. This is not much related to the semantics of propositional logic. Thus, in what follows we consider the following definition borrowed from [Amgoud et al.2014]. It compares formulas contained in sets instead of logical consequences of the sets.

Definition 1 (Equivalent Sets of Formulas) Two sets of formulas Φ, Ψ ⊆ f L 2 are equivalent, denoted by Φ ∼ = Ψ, iff ∀φ ∈ Φ, ∃ψ ∈ Ψ such that φ ≡ ψ and ∀ψ ∈ Ψ, ∃φ ∈ Φ such that φ ≡ ψ . We write Φ ∼ = Ψ otherwise.
Note that {p, p → q} ∼ = {q, q → p}, {p, ¬p} ∼ = {q, ¬q}, and {p, q} ∼ = {p ∧ q} while {p, q} ∼ = {p ∧ p, ¬¬q}.

Notation: For Φ, Ψ ⊆ f L, Co(Φ, Ψ) = {φ ∈ Φ | ∃ψ ∈ Ψ such that φ ≡ ψ}. Property 1 For all Φ, Ψ ⊆ f L, Φ ∼ = Ψ iff Co(Φ, Ψ) = Φ and Co(Ψ, Φ) = Ψ.
Proof Assume that Co(Φ, Ψ) = Φ and Co(Ψ, Φ) = Ψ. We can deduce that:

• Co(Φ, Ψ) = Φ implies ∀φ ∈ Φ, ∃ψ ∈ Ψ such that φ ≡ ψ, • Co(Ψ, Φ) = Ψ implies ∀ψ ∈ Ψ, ∃φ ∈ Φ such that ψ ≡ φ.
Therefore, Φ ∼ = Ψ according to the definition 1. The other way follows also trivially from Definition 1.

Logical Arguments

Let us define the main concept of the paper, that of argument. We follow the classical definition from the literature, namely [Besnard and Hunter2001].

Definition 2 (Argument) An argument built in logic (L, ) is a pair a = Φ, φ such that:

• Φ ⊆ f L, φ ∈ L, • Φ is consistent, • Φ φ, • Φ ⊂ Φ such that Φ φ.
An argument a = Φ, φ is trivial iff Φ = ∅ and φ ≡ .

Example 1 The following are examples of arguments: {p ∧ q}, p , {p, q}, p ∧ q , {p}, p , {p}, p ∨ q , ∅, p ∨ ¬p .

Notations: We denote by Arg(L) the set of all arguments that can be built in (L, ) in the sense of Definition 2. For any a = Φ, φ ∈ Arg(L), the functions Supp and Conc return respectively the support (Supp(a) = Φ) and the conclusion (Conc(a) = φ) of a.

Let us now introduce the useful notion of sub-argument.

Definition 3 (Sub-argument) Let a = Φ, φ , b = Ψ, ψ ∈ Arg(L). a is a sub- argument of b, denoted by a b, iff Supp(a) ⊂ Supp(b).
Note that an argument is not a sub-argument of itself according to Definition 3.

Example 1 (Cont) The two arguments {p}, p and {p}, p ∨ q are sub-arguments of {p, q}, p ∧ q .

We now define the notion of isomorphic arguments.

Definition 4 (Isomorphic Arguments) Two arguments a, b ∈ Arg(L) are isomorphic with respect to a renaming function π iff the two following conditions hold:

• there exists a bijective function f : Supp(a) → Supp(b) such that for any φ ∈ Supp(a), φ and f (φ) are isomorphic wrt π,

• Conc(a) and Conc(b) are isomorphic wrt π.

Example 2 Let π be a renaming function such that π(r) = p, π(v) = q. The arguments {p ∧ q}, p ∧ q and {r ∧ v}, r ∧ v are isomorphic wrt π while {p ∧ q}, p ∧ q and {p → q}, p → q are not.

In [Amgoud et al.2014], the authors studied when two arguments are equivalent. We recall below their most general definition according to which two arguments are equivalent if their supports (respectively their conclusions) are equivalent. Isomorphic arguments are not necessarily equivalent. For instance, {p ∧ q}, p ∧ q and {r ∧ v}, r ∧ v are isomorphic but not equivalent. All trivial arguments are equivalent.

Property 2 All trivial arguments are pairwise equivalent.

We next present a useful property of the function Co. It holds in case of arguments but not in general.

Similarity Measures

Our aim is to evaluate at what extent pairs of logical arguments are similar. For that purpose, we define similarity measure, that is a function that assigns a value from the unit interval [0, 1] to every pair of arguments. The greater the value, the more similar the arguments.

Definition 6 (Similarity Measure) A similarity measure is a function S :

Arg(L) × Arg(L) → [0, 1].
This definition is very general in that it accepts any function. In what follows, we restrict the possible candidate functions by proposing a set of principles that any reasonable similarity measure should satisfy. Principles are basic and desirable properties of a measure S. The first property states that similarity between arguments should be independent from the syntax (i.e., names of variables).

Principle 1 (Syntax Independence) A similarity measure S satisfies Syntax Independence iff for any renaming function π, for all a, b, a , b ∈ Arg(L) such that:

• a and a are isomorphic wrt π,

• b and b are isomorphic wrt π,

it holds that S(a, b) = S(a , b ).
The second principle, called Maximality, is about the case of full similarity. It states that each argument is fully similar to itself. It is worth mentioning that despite the wide range of similarity measures in the literature (see [Lesot et al.2009, Choi et al.2010] for surveys of existing measures), there are only two formal properties that have been identified in the literature: maximality and symmetry which is presented next.

Principle 2 (Maximality) A similarity measure S satisfies Maximality iff for any a ∈ Arg(L), S(a, a) = 1.

Symmetry states that similarity is a symmetric notion.

Principle 3 (Symmetry

) A similarity measure S satisfies Symmetry iff for all a, b ∈ Arg(L), S(a, b) = S(b, a).
The next principle states that two fully similar arguments are equally similar to any third argument.

Principle 4 (Substitution) A similarity measure S satisfies Substitution iff for all a, b, c ∈

Arg(L), if S(a, b) = 1 then S(a, c) = S(b, c).
The next principle states that similarity between two arguments is all the greater when the supports of the arguments share more formulas. That is, similarity increases with addition of common logically equivalent formulas in supports or deletion of distinctive formulas.

Principle 5 (Monotony -Strict Monotony) A similarity measure S satisfies Monotony iff for all a, b, c ∈ Arg(L), if

1. Conc(a) ≡ Conc(b) or Var(Conc(a)) ∩ Var(Conc(c)) = ∅, 2. Co(Supp(a), Supp(c)) ⊆ Co(Supp(a), Supp(b)), 3. Supp(b) \ Co(Supp(b), Supp(a)) ⊆ Supp(c) \ Co(Supp(c), Supp(a)),
then the following hold:

• S(a, b) ≥ S(a, c) (Monotony) • If the inclusion in condition 2 is strict, then S(a, b) > S(a, c). (Strict Monotony)
The first condition ensures that the conclusions of a and b are not different and those of a and c are not similar. Strict Monotony compares the common elements in the supports of arguments. It cannot be defined with distinct formulas (strict version of condition 3) since that would allow undesirable cases as shown in the example below.

Example 3 Consider the arguments below. Note that the definition of Monotony uses Co for supports while Dominance uses CN for conclusions. We have seen in the background section that CN is not suitable for comparing sets of formulas, thus supports, especially for the purpose of assessing similarity between arguments. However, the conclusion of an argument is a single formula, and Co would only check whether the conclusions of two arguments are equivalent or not. This is not sufficient for capturing the fact that some conclusions are logical consequences of others.

• a = {p, p → q}, q , • b = {p}, p , • c = {t}, t , • d = ∅, t ∨ ¬t .
Example 4 Consider the three arguments below. The principles are independent, i.e., none of them follows from the others. A notable exception is Substitution, which follows from a subset of principles. The principles are compatible, in that they can be satisfied all together by a similarity measure.

• a = {p ∧ q ∧ t}, p , • b = {p ∧ q ∧ t}, p ∧ q , • c = {p ∧ q ∧ t}, p ∧ q ∧ t ,
Proposition 2 All the principles are compatible.

Proof The measures S σ m satisfy all the principles.

Properties

Let us investigate some consequences of satisfying the proposed principles. We provide a characterization of all cases where similarity between two arguments is maximal (equal to 1). Let us present the result progressively. We first show that any measure satisfying Maximality and Monotony declares equivalent arguments as fully similar. Note that the case where b is non-trivial is similar to the previous case.

From the two previous results, it follows that any similarity measure that satisfies Maximality, Monotony, Strict Monotony, Strict Dominance assigns the maximal value 1 to equivalent pairs of arguments and only to equivalent ones.

Corollary 1 Let S be a similarity measure that satisfies Maximality, Monotony, Strict Monotony, and Strict Dominance. For all a, b ∈ Arg(L) the following holds:

S(a, b) = 1 iff a ≈ b.
The next result shows that an argument is neither fully similar nor completely different from its sub-arguments. This is the case when the similarity measure satisfies Maximality, Strict Monotony, and Strict Dominance. Recall that an argument is not a sub-argument of itself. The last result states that the union of supports of two fully similar arguments is consistent. This is particularly the case for similarity measures that satisfy Maximality, Strict Monotony, and Strict Dominance. Jaccard [Jaccard1901]

s jac (X, Y ) = a a+b+c Dice [Dice1945] s dic (X, Y ) = 2a 2a+b+c Sorensen [Sørensen1948] s sor (X, Y ) = 4a 4a+b+c Symmetric Anderberg [Anderberg1973] s and (X, Y ) = 8a 8a+b+c
Sokal and Sneath 2 [Sneath et al.1973] Extended Jaccard

s ss (X, Y ) = a a+2(b+c) Ochiai [Ochiai1957] s och (X, Y ) = a √ a+b √ a+c Kulczynski 2 [Kulczynski1927] s ku2 (X, Y ) = 1 2 a a+b + a a+c
s j (Φ, Ψ) = |Co(Φ,Ψ)| |Φ|+|Ψ|-|Co(Φ,Ψ)| Extended Dice s d (Φ, Ψ) = 2|Co(Φ,Ψ)| |Φ|+|Ψ| Extended Sorensen s s (Φ, Ψ) = 4|Co(Φ,Ψ)| |Φ|+|Ψ|+2|Co(Φ,Ψ)| Extended Symmetric Anderberg s a (Φ, Ψ) = 8|Co(Φ,Ψ)| |Φ|+|Ψ|+6|Co(Φ,Ψ)| Extended Sokal and Sneath 2 s ss (Φ, Ψ) = |Co(Φ,Ψ)| 2(|Φ|+|Ψ|)-3|Co(Φ,Ψ)| Extended Ochiai s o (Φ, Ψ) = |Co(Φ,Ψ)| √ |Φ| √ |Ψ| Extended Kulczynski 2 s ku (Φ, Ψ) = 1 2 |Co(Φ,Ψ)| |Φ| + |Co(Φ,Ψ)| |Ψ|

Syntactic Similarity Measures

There are several similarity measures in the literature (see [Lesot et al.2009, Choi et al.2010] for some surveys). They were mainly defined for classification, clustering, or recognition problems. Most of them compare pairs of objects, which have the same size. Others, like the well-known Jaccard measure [Jaccard1901], Dice measure [Dice1945],

Sorensen one [Sørensen1948], and those proposed in [Anderberg1973, Sneath et al.1973, Ochiai1957, Kulczynski1927] 1 recalls the formal definition of each of the seven measures. These measures are suitable in the argumentation context since an argument may be seen as a pair of two sets: one set containing the formulas of the support and another one containing the conclusion. In what follows, we use these measures for assessing similarity between supports (respectively conclusions) of pairs of arguments. However, those measures cannot be applied directly to supports of arguments since supports may have different but still equivalent formulas. For instance, the two sets {p} and {p ∧ p} are equivalent while their intersection is empty. Thus, we extend each measure of Table 1 using the function Co as shown in Table 2 in case of non-empty sets. Note that the original definitions compare non-empty sets. In the argumentation context, trivial arguments have an empty support. Thus, the definition of each measure follows the following schema that we illustrate with the Jaccard-based measure. For all Φ, Ψ ⊆ L,

s j (Φ, Ψ) =    |Co(Φ,Ψ)| |Φ|+|Ψ|-|Co(Φ,Ψ)| if Φ = ∅, Ψ = ∅ 1 if Φ = Ψ = ∅ 0 otherwise.
Let us illustrate the definition of extended Jaccard measure by the following example.

Example 5 Consider the following sets of formulas:

• Φ 0 = {p, q}, • Φ 1 = {r, s, r ∧ s → t}, • Φ 2 = {r, s, z, r ∧ s ∧ z → u},
• Φ 3 = {¬¬r, s}, and

• Φ 4 = {r, ¬¬s}.
It can be checked that s j (Φ 0 , Φ 1 ) = 0, s j (Φ 1 , Φ 2 ) = 0.4, s j (Φ 1 , Φ 3 ) = 0.66, s j (Φ 2 , Φ 3 ) = 0.5, and s j (Φ 3 , Φ 4 ) = 1. 2 evaluate in the same way pairs of sets containing each one formula. They assign value 1 if the two formulas of the sets are equivalent and 0 otherwise.

The measures of Table

Proposition 7 For any x ∈ {j, d, s, a, ss, o, ku}, for all φ, ψ ∈ L, the following holds:

s x ({φ}, {ψ}) = 1 if φ ≡ ψ 0 otherwise.
Proof Follows from the definition of the measures. The size of each of the compared sets is 1.

We are now ready to introduce our similarity measures between pairs of logical arguments. They are syntactic in nature, and are based on a parameter σ ∈ ]0, 1[ which allows a user to give different importance degrees to supports and conclusions. Indeed, one may declare two arguments as similar as soon as they have quite equivalent supports, or my be more requiring by ensuring that the conclusions also are equivalent. Due to the previous result, the same measure is used for assessing similarity between supports an similarity between conclusions of pairs of logical arguments. Note that σ cannot take the value 0 since the corresponding similarity measure would ignore the supports of arguments, and cannot get value 1 since the measure would ignore the conclusions. Both cases are undesirable since an argument is a pair (support, conclusion).

Example 3 (Cont) It can be checked that for σ = 0.5, S σ j (a, b) = 0.25, S σ j (a, c) = 0, S σ j (a, d) = 0.

Example 4 (Cont) It can be checked that for σ = 0.5, S σ j (a, b) = S σ j (a, c) = 0.5.

Example 5 (Cont) Let σ = 0.5 and x = s j . Consider the following arguments:

• a 0 = Φ 0 , p ∧ q , • a 1 = Φ 1 , t ,
• a 2 = Φ 2 , u ,

• a 3 = Φ 3 , r ∧ s , and

• a 4 = Φ 4 , r ∧ ¬¬s .
It can be checked that we get the following values: S 0.5 j (a 0 , a 1 ) = 0, S 0.5 j (a 1 , a 2 ) = 0.5 × 0.4 + 0.5 × 0 = 0.2, S 0.5 j (a 1 , a 3 ) = 0.5 × 0.66 + 0.5 × 0 = 0.33, S 0.5 j (a 2 , a 3 ) = 0.5 × 0.5 + 0.5 × 0 = 0.25, and S 0.5 j (a 3 , a 4 ) = 1.

Due to Proposition 7, the definition of the extended measures can be simplified as follows:

Proposition 8 For any 0 < σ < 1, for any x ∈ {j, d, s, a, ss, o, ku}, for all (a, b) ∈ Arg(L) × Arg(L), the following property holds:

S σ x (a, b) =    σ.s x (Supp(a), Supp(b)) + (1 -σ) if Conc(a) ≡ Conc(b) σ.s x (Supp(a), Supp(b)) otherwise.
Proof Follows from Proposition 7.

We show that any measure S σ

x assigns values from the unit interval [0, 1] to any pair of arguments. Thus, any S σ

x is a similarity measure in the sense of Definition 6.

Proposition 9 For any 0 < σ < 1, for any x ∈ {j, d, s, a, ss, o, ku}, for all a, b ∈

Arg(L), S σ x (a, b) ∈ [0, 1]. Hence, S σ
x is a similarity measure.

Proof Let a, b ∈ Arg(L), x ∈ {j, d, s, a, ss, o, ku}, and

0 < σ < 1. s x (Supp(a), Supp(b)) ∈ [0, 1] and s x (Conc(a), Conc(b)) ∈ [0, 1]. Hence, S σ x (a, b) ∈ [0, 1]. Similarity measures S σ
x satisfy all the principles except Strict Dominance. Theorem 3 For any 0 < σ < 1, for any x ∈ {j, d, s, a, ss, o, ku}, S σ

x violates Strict Dominance and satisfies all the remaining principles.

Proof We prove the result for extended Jaccard measures. The same reasoning holds for the others. Let σ ∈]0, 1[. Maximality: Let a ∈ Arg(L). There are two cases: i) a is trivial, hence Supp(a) = ∅. By definition of extended Jaccard measure, s j (Supp(a), Supp(a)) = 1. ii) a is nontrivial. Hence, Co(Supp(a), Supp(a)) = Supp(a). Thus, s j (Supp(a), Supp(a)) = 1. Furthermore, from Proposition 7, s j (Conc(a), Conc(a)) = 1. Hence, S σ j (a, a) = 1. There are two cases: -Assume that a is trivial. Since Supp(b) ∼ = Supp(a), then b is also trivial. From Theorem 4, S σ j (a, b) = S σ j (a, c) = 1. -Assume that a is not trivial. Then, Conc(a) ≡ Conc(c) and s j ({Conc(a)}, {Conc(c)}) = 0. Furthermore, s j (Supp(a), Supp(c)) = 0. Hence, S σ j (a, c) = 0. So, S σ j (a, b) > S σ j (a, c).

Symmetry: Let a, b ∈ Arg(L). We show that s σ j (a, b) = s σ j (b,
• c is trivial, i.
• c is not trivial, i.e., Supp(c) = ∅ and Conc(c) ≡ .

-Assume that a is trivial. So, Example 4 shows that S σ j violate Strict Dominance. Despite the fact of violating Strict Dominance, any measure S σ

x assigns the maximal value 1 only to equivalent arguments, i.e. the result of Corollary 1 still holds. This result generalizes the binary similarity measure defined in [Amgoud et al.2014], where arguments are either equivalent (value 1) or completely different (value 0).

Measures S σ

x assign the minimal value 0 to pairs of arguments whose conclusions are not equivalent and their supports do not share any equivalent formula.

Theorem 5 For any σ ∈ (0, 1), for all x ∈ {j, d, s, a, ss, o, ku}, for all a, b ∈ Arg(L), Theorem 3 shows that all the measures S σ x , with x ∈ {j, d, s, a, ss, o, ku}, satisfy the same set of principles and violate Strict Dominance. An interesting question is thus: are there links between these measures? do they return the same values? For answering these questions, we introduce the notion of equivalent measures. We show that the measures S σ j , S σ d , S σ s , S σ a , and S σ ss are pairwise equivalent for some arbitrary but fixed σ.

Theorem 6 Let σ ∈ (0, 1). The measures S σ j , S σ d , S σ s , S σ a , and S σ ss are pairwise equivalent.

The following result compares the values assigned by each measure for a given pair of arguments. It shows that for a fixed σ, S σ a provides the greatest degree of similarity while S σ ss provides the lowest one. Similarly, the values assigned by the measure S σ o are lower than those of S σ ku .

Theorem 7 Let σ ∈ (0, 1). For any a, b ∈ Arg(L),

• S σ ss (a, b) ≤ S σ j (a, b) ≤ S σ d (a, b) ≤ S σ a (a, b) ≤ S σ a (a, b). • S σ o (a, b) ≤ S σ ku (a, b).

Model-based Similarity Measure

We have seen in the previous section, that the syntactic measures S σ x violate Strict Dominance. Thus, they do not distinguish between arguments like: a = {p∧q∧t}, p , b = {p ∧ q ∧ t}, p ∧ q , and c = {p ∧ q ∧ t}, p ∧ q ∧ t . They all return S σ x (a, b) = S σ

x (a, c). They are thus not able to capture the fact that the conclusion of a is closer to the conclusion of b than that of c.

In what follows, we propose to use a semantic approach for comparing conclusions. The idea is to compare their models. Recall that a model of a formula φ is an interpretation (a total function from P to {0, 1}) that makes φ true in the usual truth-functional way. Mod(φ) denotes the set of all models of the formula φ, i.e. Mod(φ) = {ω ∈ W | ω |= φ}, where W is the set of all interpretations.

Similarity between conclusions of two arguments will be assessed by the measure s mj below. It applies Jaccard formula on their models as follows:

Definition 9 (Model-based Jaccard Measure) The model-based Jaccard measure is a function s mj assigning for all φ, ψ ∈ L, the value:

s mj (φ, ψ) = |Mod(φ) ∩ Mod(ψ)| |Mod(φ) ∪ Mod(ψ)|
We are now ready to introduce the novel similarity measure for logical arguments. It combines a syntactic measure for comparing the supports and s mj for conclusions. The former can be any measure of Table 2 since they satisfy all Monotony and Strict Monotony which deal with supports. However, for the sake of simplicity and clarity, we only focus on Jaccard-based one, s j . It is worth mentioning that the measure s mj is not suitable for supports since it would assign value 1 to supports that do not express the same information like {p, p → q} and {q, q → p}.

Example 4 (Cont) Recall again the arguments below.

• a = {p ∧ q ∧ t}, p ,

• b = {p ∧ q ∧ t}, p ∧ q ,

• c = {p ∧ q ∧ t}, p ∧ q ∧ t .

It can be checked that S 0.5 m (a, b) = 0.75, S 0.5 m (a, c) = 0.625.

Theorem 8 For any σ ∈ (0, 1), the similarity measure S σ m satisfies all the principles.

Related Work

Similarity is studied in different domains (information retrieval, classification, image processing, etc). There are thus several measures in the literature. Some of them compare numerical objects while others compare arbitrary sets [Lesot et al.2009, Choi et al.2010]. The numerical ones are not appropriate in the context of arguments while the others are shown to be efficient, especially in the comparison of supports of arguments.

In the argumentation literature, similarity has also been investigated either within an argument [Walton et al.2008, Walton2010, Walton2013] or between pairs of arguments [Misra et al.2016, Stein2016, Konat et al.2016]. Indeed, Walton discussed different argument schemes like analogical arguments or similarity arguments. The supports of such arguments contain premises with compare objects.

Similarity between pairs of arguments was investigated in the context of argument mining [Misra et al.2016, Stein2016, Konat et al.2016]. The goal is to detect redundant textual arguments. Budan et al. [Budan et al.2015] defined another measure assessing similarity between pairs of analogical arguments. It is based on the number of common features between compared objects. The type of arguments considered is thus different from the deductive arguments investigated in our paper.

Finally, [Wooldridge et al.2006, Amgoud et al.2014] investigated equivalence, full similarity, between logical arguments. We have seen that our approach generalizes those proposals. Indeed, it assigns the maximal value to each pair of equivalent arguments.

Conclusion

The paper investigated the question: to what extent two logical arguments are similar? It defined thus the notion of similarity measure, and proposed some intuitive principles that might be satisfied by a measure. Then, it proposed several syntactic measures that extend very old ones from the literature, and investigated their properties.

This work can be extended in several ways. The first one consists of characterizing the whole family of measures that satisfy the principles. The second one consists of using the proposed measures for refining argumentation systems that deal with inconsistent information.

Definition 5 (

 5 Equivalent Arguments) Two arguments a, b ∈ Arg(L) are equivalent, denoted by a ≈ b, iff (Supp(a) ∼ = Supp(b)) and (Conc(a) ≡ Conc(b)).

Property 3

 3 For all a, b ∈ Arg(L), |Co(Supp(a), Supp(b))| = |Co(Supp(b), Supp(a))|. Proof Let a, b ∈ Arg(L). We distinguish two cases: i) Supp(a) = ∅ or Supp(b) = ∅. By definition, Co(Supp(a), Supp(b)) = Co(Supp(b), Supp(a)) = ∅. Hence, |Co(Supp(a), Supp(b))| = |Co(Supp(b), Supp(a))| = 0. ii) Supp(a) = ∅ and Supp(b) = ∅. If Co(Supp(a), Supp(b)) = ∅, then Co(Supp(b), Supp(a)) = ∅. Assume now that Co(Supp(a), Supp(b)) = ∅. Assume that |Co(Supp(a), Supp(b))| < |Co(Supp(b), Supp(a))|. Thus, there exists at least two formulas φ, ψ ∈ Co(Supp(b), Supp(a)) such that φ ≡ λ and ψ ≡ λ, with λ ∈ Supp(a). This means that φ ≡ ψ. This contradicts the fact that Supp(b) is minimal for set inclusion. Property 4 For all a, b ∈ Arg(L), Supp(a) ∼ = Supp(b) ⇒ |Supp(a)| = |Supp(b)|. Proof Let a, b ∈ Arg(L) be such that Supp(a) ∼ = Supp(b). Property 1 implies Co(Supp(a), Supp(b)) = Supp(a) and Co(Supp(b), Supp(a)) = Supp(b). Property 3 implies that |Co(Supp(a), Supp(b))| = |Co(Supp(b), Supp(a))|. Hence, |Supp(a)| = |Supp(b)|.

  Monotony ensures that S(a, b) ≥ S(a, c) and S(d, b) ≥ S(d, a) while Strict Monotony states that S(a, b) > S(a, c). Note that if we extend the definition of Strict Monotony by allowing strict inclusion in condition 3, then we get S(d, b) > S(d, a) ≥ 0. Hence, S(d, b) > 0 which is counter-intuitive. The last principle, called Dominance, ensures that similarity between two logical arguments depends also on the conclusions of the arguments. The more consequences the conclusions have in common, the greater the similarity. Principle 6 (Dominance -Strict Dominance) A similarity measure S satisfies Dominance iff for all a, b, c ∈ Arg(L), if 1. Supp(b) ∼ = Supp(c), 2. CN({Conc(a)}) ∩ CN({Conc(c)}) ⊆ CN({Conc(a)}) ∩ CN({Conc(b)}), 3. CN({Conc(b)}) \ CN({Conc(a)}) ⊆ CN({Conc(c)}) \ CN({Conc(a)}) then the following hold: • S(a, b) ≥ S(a, c). (Dominance) • If the inclusion in condition 2 is strict and Co(Supp(a), Supp(b)) = ∅, then S(a, b) > S(a, c). (Strict Dominance)

  Dominance ensures that S(a, b) ≥ S(a, c) and S(c, b) ≥ S(c, a). Strict Dominance ensures S(c, b) > S(c, a).

Proposition 1

 1 If a similarity measure S satisfies Symmetry, Maximality, Strict Monotony, Dominance, and Strict Dominance, then S satisfies Substitution. Proof Let S be a similarity measure which satisfies Maximality, Symmetry, Strict Monotony, Dominance, and Strict Dominance. Let a, b, c ∈ Arg(L) such that S(a, b) = 1. From Theorem 2, it holds that Supp(a) ∼ = Supp(b) and Conc(a) ≡ Conc(b). By applying Dominance twice, we get S(c, a) ≥ S(c, b) and S(c, b) ≥ S(c, a). Hence, S(c, a) = S(c, b). Symmetry implies S(c, a) = S(a, c) = S(c, b) = S(b, c).

Theorem 1

 1 Let S be a similarity measure that satisfies Maximality and Monotony. For all a, b ∈ Arg(L), if a ≈ b, then S(a, b) = 1. Proof Let S be a similarity measure which satisfies Maximality and Monotony. Let a, b ∈ Arg(L) be such that a ≈ b. Let us show that S(a, b) = 1. From Definition 5, Supp(a) ∼ = Supp(b) and Conc(a) ≡ Conc(b). From Monotony, it follows that S(a, a) ≥ S(a, b) and S(a, b) ≥ S(a, a). Therefore, S(a, a) = S(a, b). From Maximality, S(a, a) = 1, so S(a, b) = 1. We show next that if, in addition to Maximality, a similarity measure satisfies Strict Monotony and Strict Dominance, then two fully similar arguments are necessarily equivalent. Theorem 2 Let S be a similarity measure that satisfies Maximality, Strict Monotony, and Strict Dominance. For all a, b ∈ Arg(L) the following holds: if S(a, b) = 1 then a ≈ b. Proof Let S be a similarity measure which satisfies Maximality, Strict Monotony and Strict Dominance. Let a, b ∈ Arg(L) be such that S(a, b) = 1. Let us show that a ≈ b. There are two cases: i) a and b are trivial: From Property 2, it holds that a ≈ b. ii) a is non-trivial: Assume that a ≈ b. By definition, Supp(a) ∼ = Supp(b) or Conc(a) ≡ Conc(b). Consider the case where Supp(a) ∼ = Supp(b). Clearly, i) Conc(a) ≡ Conc(a), ii) Co(Supp(a), Supp(b)) ⊂ Co(Supp(a), Supp(a)) = Supp(a) (this inclusion is strict since Supp(a) = ∅ and Supp(a) ∼ = Supp(b)), iii) Supp(a)\Co(Supp(a), Supp(a)) ⊂ Supp(b)\Co(Supp(a), Supp(b)). By applying Strict Monotony, we get S(a, a) > S(a, b). From Maximality S(a, a) = 1, so S(a, b) < 1. This shows that Supp(a) ∼ = Supp(b). Consider now the case where Supp(a) ∼ = Supp(b) and Conc(a) ≡ Conc(b). The conditions of Strict Dominance are verified, indeed: • Supp(a) ∼ = Supp(b), • CN(Conc(a))∩CN(Conc(b)) ⊂ CN(Conc(a))∩CN(Conc(a)) = CN(Conc(a)). The implication is strict since Conc(a) ≡ Conc(b). • CN(Conc(a)) \ CN(Conc(a)) ⊂ CN(Conc(b)) \ CN(Conc(a)). • Co(Supp(a), Supp(a)) = Supp(a). Since a is non trivial, then Supp(a) = ∅. Strict Dominance ensures S(a, a) > S(a, b) while Maximality ensures S(a, a) = 1, so S(a, b) < 1.

Proposition 3

 3 Let S be a similarity measure which satisfies Maximality, Strict Monotony, and Strict Dominance. For all a, b ∈ Arg(L), if b a, then 0 < S(a, b) < 1. Proof Let S be a similarity measure which satisfies Maximality, Strict Monotony, and Strict Dominance. Let a, b ∈ Arg(L) be such that b a. From the definitions of argument and sub-argument, Supp(b) ⊂ Supp(a) and Conc(b) ≡ Conc(a). Thus, a ≈ b. From Theorem 2, it holds that S(a, b) < 1. Let us now show that S(a, b) > 0. Consider an arbitrary non-trivial argument c ∈ Arg(L) such that Vars(a) ∩ Vars(c) = ∅. The conditions of Strict Monotony are satisfied, and thus the principle leads to S(a, b) > S(a, c). Furthermore, by definition of a similarity measure S(a, c) ≥ 0. Hence, S(a, b) > 0. Similarity measures satisfying Strict Monotony satisfy some monotony property regarding the sub-argument relationship between arguments. Proposition 4 Let S be a similarity measure that satisfies Strict Monotony. For all a, b, c ∈ Arg(L), if • Var(Conc(a)) ∩ Var(Conc(c)) = ∅, and • c b a, then S(a, b) > S(a, c). Proof Let S be a similarity measure which satisfies Strict Monotony. Let a, b, c ∈ Arg(L) be such that: • Var(Conc(a)) ∩ Var(Conc(c)) = ∅, and • c b a. It can be checked below that the conditions of Strict Monotony are guaranteed. Indeed, • Var(Conc(a)) ∩ Var(Conc(c)) = ∅, • Co(Supp(a), Supp(c)) = Supp(c) ⊂ Co(Supp(a), Supp(b)) = Supp(b), (note that inclusion is strict since c b and thus by definition Supp(c) ⊂ Supp(b)), • Supp(b) \ Co(Supp(a), Supp(b)) = Supp(c) \ Co(Supp(a), Supp(c)) = ∅. Strict Monotony ensures S(a, b) > S(a, c). Strict Dominance ensures that the more consequences are shared by the conclusions of two arguments, the more similar the arguments. Proposition 5 Let S be a similarity measure which satisfies Strict Dominance. For all a, b, c ∈ Arg(L), if • a, b, c are non trivial, • Supp(a) ∼ = Supp(b) ∼ = Supp(c), • Conc(a) Conc(b) Conc(c), • Conc(c) Conc(b), Conc(b) Conc(a), then S(a, b) > S(a, c). Proof Let S be a similarity measure which satisfies Strict Dominance. Let a, b, c ∈ Arg(L) be such that: 1. a, b, c are non trivial, 2. Supp(a) ∼ = Supp(b) ∼ = Supp(c), 3. Conc(a) Conc(b) Conc(c), 4. Conc(c) Conc(b), Conc(b) Conc(a), The conditions of Strict Dominance are guaranteed, indeed: • Co(Supp(a), Supp(b)) = ∅ (from condition 1), • Supp(b) ∼ = Supp(c) (from condition 2), • CN(Conc(a)) ∩ CN(Conc(c)) ⊂ CN(Conc(a)) ∩ CN(Conc(b)) (from conditions 3, 4), • CN(Conc(b)) \ CN(Conc(a)) = CN(Conc(c)) \ CN(Conc(a)) = ∅ (from condition 3). Hence, Strict Dominance leads to S(a, b) > S(a, c).

Proposition 6

 6 Let S be a similarity measure which satisfies Maximality, Strict Monotony, and Strict Dominance. For all a, b ∈ Arg(L), if S(a, b) = 1, then Supp(a) ∪ Supp(b) is consistent. Proof Let S be a similarity measure which satisfies Maximality, Strict Monotony, and Strict Dominance. From Theorem 2, it follows that Supp(a) ∼ = Supp(b). Hence, Supp(a) ∪ Supp(b) ∼ = Supp(a). Furthermore, by definition of an argument, Supp(a) is consistent. So is for Supp(a) ∪ Supp(b).

  compare arbitrary pairs of non-empty sets (X and Y ) of objects. Let a = |X ∩ Y |, b = |X -Y |, c = |Y -X|, where |.| denotes the cardinality of a set. Table

Definition 7 (

 7 Extended Measures) Let 0 < σ < 1. We define S σ x , with x ∈ {j, d, s, a, ss, o, ku}, as a function assigning to any pair (a, b) ∈ Arg(L) × Arg(L) a value S σ x (a, b) = σ.s x (Supp(a), Supp(b)) + (1 -σ)s x ({Conc(a)}, {Conc(b)}).

  a). There are three cases: i) a and b are both trivial. Then, Supp(a) = Supp(b) = ∅ and Conc(a) ≡ Conc(b). Hence, by definition of extended measure, s j (Supp(a), Supp(b)) = 1 and from Proposition 7, s j (Conc(a), Conc(b)) = 1. Hence, S σ j (a, b) = S σ j (b, a) = 1. ii) a is trivial and b is non-trivial. Then, Supp(a) = ∅ and Conc(a) ≡ Conc(b). By definition, s j (Supp(a), Supp(b)) = s j (Supp(b), Supp(a)) = 0 and from Proposition 7, s j ({Conc(a)}, {Conc(b)}) = 0. So, S σ j (a, b) = S σ j (b, a) = 0. iii) both a and b are not trivial, i.e., Supp(a) = ∅ and Supp(b) = ∅. From Property 3, |Co(Supp(a), Supp(b))| = |Co(Supp(b), Supp(a))|. So, s j (Supp(a), Supp(b)) = s j (Supp(b), Supp(a)). From Proposition 7, s j ({Conc(a)}, {Conc(b)}) = s j ({Conc(b)}, {Conc(a)}). Thus, S σ j (a, b) = S σ j (b, a). Substitution: Let a, b, c ∈ Arg(L) such that S σ j (a, b) = 1. From Theorem 4, it holds that a ≈ b. Hence, Supp(a) ∼ = Supp(b) and Conc(a) ≡ Conc(b). If Conc(a) ≡ Conc(c), then Conc(b) ≡ Conc(c). So, s j ({Conc(a)}, {Conc(c)}) = s j ({Conc(b)}, {Conc(c)}). It is thus sufficient to check the equality s j (Supp(a), Supp(c)) = s j (Supp(b), Supp(c)). From Property 1, Co(Supp(a), Supp(b)) = Supp(a) and Co(Supp(b), Supp(a)) = Supp(b). From Property 3, |Supp(a)| = |Supp(b)|. Furthermore, Co(Supp(a), Supp(c)) = Co(Supp(b), Supp(c)). Hence, s j (Supp(a), Supp(c)) = s j (Supp(b), Supp(c)). Consequently, S σ j (a, c) = S σ j (b, c). Monotony -Strict Monotony: Let σ ∈]0, 1[ and a, b, c ∈ Arg(L) be such that: 1. Conc(a) ≡ Conc(b) or Var(Conc(a)) ∩ Var(Conc(c)) = ∅, 2. Co(Supp(a), Supp(c)) ⊆ Co(Supp(a), Supp(b)), 3. Supp(b) \ Co(Supp(a), Supp(b)) ⊆ Supp(c) \ Co(Supp(a), Supp(c)).

  e., Supp(c) = ∅. Condition 3) implies Supp(b)\Co(Supp(a), Supp(b)) = ∅, hence Supp(b) = Co(Supp(a), Supp(b)) and Supp(a) ∼ = Supp(b). Consequently, s j (Supp(a), Supp(b)) = 1. Since σ > 0, then S σ j (a, b) > 0.

  s j (Supp(a), Supp(c)) = 0 and s j ({Conc(a)}, {Conc(c)}) = 0 leading to S σ j (a, c) = 0. If b is trivial, then S σ j (a, b) = 1 (from Theorem 4). If b is not trivial, then s j (Supp(a), Supp(b)) = 0 and s j ({Conc(a)}, {Conc(b)}) = 0 leading to S σ j (a, b) = 0. -Assume that a is not trivial. Assume that b is trivial, then s j (Supp(a), Supp(b)) = 0 and s j ({Conc(a)}, {Conc(b)}) = 0 leading to S σ j (a, b) = 0. Condition 2) implies that Co(Supp(a), Supp(c) = ∅. So, s j (Supp(a), Supp(c)) = 0. Note that Conc(a) ≡ Conc(b) (since a is not trivial), then Var(Conc(a)) ∩ Var(Conc(c)) = ∅. Thus, Conc(a) ≡ Conc(c) and so s j ({Conc(a)}, {Conc(c)}) = 0 leading to S σ j (a, c) = 0. Thus, S σ j (a, b) = S σ j (a, c). Assume now that b is not trivial (i.e., the 3 arguments are not trivial). From condition 2) it holds that |Co(Supp(a), Supp(c))| ≤ |Co(Supp(a), Supp(b))| and from condition 3) |Supp(b) \ Co(Supp(b), Supp(a))| ≤ |Supp(c) \ Co(Supp(c), Supp(a))|. Since s j (Supp(a), Supp(b)) = |Co(Supp(a), Supp(b))| |Supp(a)| + |Supp(b) \ Co(Supp(a), Supp(b)))| , we get s j (Supp(a), Supp(b)) ≥ s j (Supp(a), Supp(c)). Since s j ({Conc(a)}, {Conc(b)}) = 1 or s j ({Conc(a)}, {Conc(c)}) = 0, then s σ j (a, b) ≥ s σ j (a, c). If the condition 2 is strict then |Co(Supp(a), Supp(b))| > |Co(Supp(a), Supp(c))| and thus S σ j (a, b) > S σ j (a, c). Dominance: Let a, b, c ∈ Arg(L) such that: 1. Supp(b) ∼ = Supp(c), 2. CN({Conc(a)}) ∩ CN({Conc(c)}) ⊆ CN({Conc(a)}) ∩ CN({Conc(b)}), 3. CN({Conc(b)}) \ CN({Conc(a)}) ⊆ CN({Conc(c)}) \ CN({Conc(a)}). Condition 1 implies that Co(Supp(a), Supp(b)) = Co(Supp(a), Supp(c)). From Property 4, |Supp(b)| = |Supp(c)|. Hence, s j (Supp(a), Supp(b)) = s j (Supp(a), Supp(c)). Assume now that Conc(a) ≡ Conc(b). Thus, s j (Conc(a), Conc(b)) = 1. Furthermore, from condition 2), we get CN({Conc(a)}) ∩ CN({Conc(c)}) = CN({Conc(a)}). Thus, CN({Conc(a)}) = CN({Conc(c)}), and Conc(a) ≡ Conc(c). So, s j (Conc(a), Conc(c)) = 1 and finally, S σ j (a, b) = S σ j (a, c). The same holds for the case Conc(a) ≡ Conc(c). Assume now that Conc(a) ≡ Conc(b) and Conc(a) ≡ Conc(c). From Proposition 7, s j (Conc(a), Conc(b)) = s j (Conc(a), Conc(c)) = 0. Thus, S σ j (a, b) = S σ j (a, c).

Theorem 4

 4 For any σ ∈ (0, 1), for any x ∈ {j, d, s, a, ss, o, ku}, for all a, b ∈ Arg(L), S σ x (a, b) = 1 iff a ≈ b. Proof We show the result for extended Jaccard-based measures. The same reasoning holds for the other measures. Let a, b ∈ Arg(L) and σ ∈ ]0, 1[. Assume that a ≈ b, then i) Supp(a) ∼ = Supp(b) and ii) Conc(a) ≡ Conc(b). From i) and Property 1, Co(Supp(a), Supp(b)) = Supp(a). From Property 4, |Supp(a)| = |Supp(b)|. Thus, s j (Supp(a), Supp(b)) = 1. From ii) and Proposition 7, s j (Conc(a), Conc(b)) = 1. So, S σ j (a, b) = 1. Assume that S σ j (a, b) = 1. Since σ ∈ ]0, 1[, then s j (Supp(a), Supp(b)) = 1 and s j (Conc(a), Conc(b)) = 1. From Proposition 7, it holds that Conc(a) ≡ Conc(b). Recall that s j (Supp(a), Supp(b)) = |Co(Supp(a),Supp(b))| |Supp(a)|+|Supp(b)|-|Co(Supp(a),Supp(b))| = 1. Furthermore, |Supp(a)| + |Supp(b)| -|Co(Supp(a), Supp(b))| = |Supp(a) \ Co(Supp(a), Supp(b))|+|Supp(b)\Co(Supp(b), Supp(a))|+|Co(Supp(a), Supp(b))|. Thus, |Supp(a) \ Co(Supp(a), Supp(b))| + |Supp(b) \ Co(Supp(b), Supp(a))| = 0. So, |Supp(a) \ Co(Supp(a), Supp(b))| = 0 and |Supp(b) \ Co(Supp(b), Supp(a))| = 0. Then Supp(a) = Co(Supp(a), Supp(b)) and Supp(b) = Co(Supp(b), Supp(a)). Thus, Supp(a) ∼ = Supp(b), and so a ≈ b.

  S σ x (a, b) = 0 iff Co(Supp(a), Supp(b)) = ∅ and Conc(a) ≡ Conc(b). Proof Let x ∈ {j, d, s, a, ss, o, ku}, σ ∈ (0, 1), and a, b ∈ Arg(L). Assume that S σ x (a, b) = 0. Since σ > 0, then i) s x (Supp(a), Supp(b)) = 0 and ii) s x ({Conc(a)}, {Conc(b)}) = 0. From Proposition 7, Conc(a) ≡ Conc(b). This means also that either a or b is not trivial. There are thus two cases regarding ii): Case 1. Supp(a) = ∅ or Supp(b) = ∅. Hence, Co(Supp(a), Supp(b)) = ∅. Case 2. Supp(a) = ∅ and Supp(b) = ∅. Thus, Co(Supp(a), Supp(b)) = ∅. Assume now that i) Co(Supp(a), Supp(b)) = ∅ and ii) Conc(a) ≡ Conc(b). From Proposition 7, s x ({Conc(a)}, {Conc(b)}) = 0. Regarding i) there are two cases: Case 1. Supp(a) = ∅ and Supp(b) = ∅; and Case 2. Supp(a) = ∅ or Supp(b) = ∅ (but not both since Conc(a) ≡ Conc(b)). In both cases, s x (Supp(a), Supp(b)) = 0. Hence, S σ x (a, b) = 0.

Definition 8 (

 8 Equivalent Measures) Two similarity measures S and S are equivalent iff for all a, b, c, d ∈ Arg(L), S(a, b) < S(c, d) ⇐⇒ S (a, b) < S (c, d).

  Definition 10 (Model-based Measure) Let 0 < σ < 1. We define S σ m as a function assigning to any pair (a, b) ∈ Arg(L) × Arg(L) a value S σ m (a, b) = σ.s j (Supp(a), Supp(b)) + (1 -σ)s mj (Conc(a), Conc(b)).

Table 1 :

 1 Similarity Measures for Sets of Objects

Table 2 :

 2 Similarity Measures for Sets Φ, Ψ ⊆ f L.

π(φ) denotes the formula obtained by replacing in φ each variable v ∈ Var(φ) by π(v).

The notation Ψ ⊆ f L means Ψ is a finite subset of L.