A three-valued logic approach to partially known formal concepts 1

2.1 Formal context and concept

Let K = (OB, AT, I) be a complete formal context ([6]), for a set of objects O ⊆ OB and a set of attributes A ⊆ AT, by considering the maximal set of attributes shared by all objects in O and the maximal set of objects sharing all attributes in A, we arrive at a pair of derivation operators and their properties, as listed below.

Definition 2.1. [6] In a complete formal context K = (OB, AT, I), a pair of derivation operators, σ : 2 ^OB  → 2 ^AT and τ : 2 ^AT  → 2 ^OB , is defined by: for a set of objects O ⊆ OB and a set of attributes A ⊆ AT, σ ( O ) = { a ∈ AT ∣ ∀ o ∈ O , oIa } , τ ( A ) = { o ∈ OB ∣ ∀ a ∈ A , oIa } .

Definition 2.2. [6] A pair (O, A) of a set of objects and a set of attributes is called a formal concept if σ (O) = A and τ (A) = O. The set of objects O and the set of attributes A are, respectively, called the extent and the intent of the formal concept (O, A).

As stated in the introduction part, in real situations, we may only have incomplete information. That is, for an object, we know a set of attributes that the object has, we also know another set of attributes that the object does not have, however, for the rest of attributes, we do not know their states. Such a formal context is called an incomplete formal context in the literature ([1, 18]). In what follows, we use K = (OB, AT, {+ , ? , -} , J) to denote an incomplete context, where the symbol ? means an unknown state.

In an incomplete context K = (OB, AT, {+, ?, -}, J), for a set of objects we can no longer derive a set of attributes shared by these objects by using the derivation operator σ, and for a set of attributes nor can we derive a set of objects that share all these attributes by using the derivation operator τ. Burmeister and Hozer and Obiedkow generalized derivation operators σ and τ into modal-style derivation operators as given in the next definition.

Definition 2.3. [1, 14] In an incomplete formal context K = (OB, AT, {+ , ? , -} , J), a pair of derivation operators, σ _ , σ ¯ : 2 OB → 2 AT that maps a set of objects O ⊆ OB to a pair of sets of attributes is defined as follows: σ _ ( O ) = { a ∈ AT ∣ ∀ o ∈ O ( ( o , a , + ) ∈ J ) } , σ ¯ ( O ) = { a ∈ AT ∣ ∀ o ∈ O ( ( o , a , + ) ∈ J ∨ ( o , a , ? ) ∈ J ) } .

Similarly, corresponding to the derivation operator τ, a pair of lower and upper derivation operators that maps a set of attributes A ⊆ AT to a pair of the sets of objects as follows: τ _ ( A ) = { o ∈ OB ∣ ∀ a ∈ A ( ( o , a , + ) ∈ J ) } , τ ¯ ( A ) = { o ∈ OB ∣ ∀ a ∈ A ( ( o , a , + ) ∈ J ∨ ( o , a , ? ) ∈ J ) } .

2.2 Three-valued logic

Three-valued logics are straightforward generalizations of Boolean logic based on the most simple bipolar scale 3 = { 0 , 1 2 , 1 } , where 1 has a positive flavor, 0 has a negative flavor and 1 2 is neutral. To date, three-valued logics have been widely used in several applied contexts such as logic programming, electronic circuits, databases and so on.

In [4], the authors defined a maximal family of sensible conjunctions, in addition to the existing ones.

Definition 2.4. [4] A conjunction on 3 is a binary mapping ∗ : 3 × 3 ⟶ 3, that is monotonically increasing in the wide sense, and extends the connective AND in Boolean logic:

If x ≤ y then x∗ z ≤ y ∗ z ;

In the case of implication, the authors give a general definition, which extend Boolean logic and supposes monotonicity.

Definition 2.5. [4] An implication on 3 is a binary mapping ∗ : 3 × 3 ⟶ 3 such that

If x ≤ y then y→ z ≤ x ∗ z ;

We can easily derive from Definition 2.5 that 0 → 1 = 1 2 → 1 = 1 , 1 2 → 1 2 ≥ { 1 → 1 2 , 1 2 → 0 } . There are 14 implications satisfying this definition, as listed in Table 1. Nine of them are known and have been studied.

3.1 Three-valued logics and SE-ISI concepts and ISE-SI concepts

For an incomplete formal context, the collection of objects has altogether three different states with respect to the set of attributes, the truth values are {0, ? , 1}, or equivalently, { 0 , 1 2 , 1 } . Usually, two natural orderings on { 0 , 1 2 , 1 } are considered, one is the truth ordering that characterizes the nature of objects and the other is a knowledge ordering that reflects our knowledge about objects. For the truth ordering ⪯ _t , we have 0 ⪯ t 1 2 ⪯ t 1 , and for the knowledge ordering ⪯ _k , we have 1 2 ⪯ k 0 , 1 2 ⪯ t 1 .

In what follows, we mainly consider the truth ordering, then { 0 , 1 2 , 1 } forms a simple lattice ([7]). By treating an incomplete context K = (OB, AT, {+ , ? , -} , J) as a lattice-valued context. We can thus use the proposed fuzzy concept lattices to analyse SER-ISI concepts.

Definition 3.1. A tuple (L, ∧ , ∨ , ⊗ , → , 0, 1) is called a complete residuated lattice, if

(L, ∧ , ∨ , 0, 1) is a complete lattice with the least element 0 and the greatest element 1;

Definition 3.2. [2, 3] Let L = (L, ∧ , ∨ , ⊗ , → , 0, 1) be a complete residuated lattice, for an L-fuzzy formal context (U, A, I), for all X ∈ L ^OB , Y ∈ L ^AT , define the operators as follows: X * ( a ) = ⋀ o ∈ OB ( X ( o ) → I ( o , a ) ) ,(1) Y * ( o ) = ⋀ a ∈ AT ( Y ( a ) → I ( o , a ) ) .(2) The pair (X, Y) is called a formal concept if and only if X^* = Y and Y^* = X .

In a residuate lattice L = (L, ∧ , ∨ , ⊗ , → , 0, 1), → is called a residual implication. It is a known fact that there exists altogether 2 residual implications on { 0 , 1 2 , 1 } , that is, the Łukasiewicz implication and G o ̈ del implication, as shown in Table 1, respectively. The corresponding conjunction operators on { 0 , 1 2 , 1 } are listed in Table 2 and Table 3.

Definition 3.3. [18] In an incomplete formal context, a pair of a set of objects and an interval set of attributes ( O , [ A _ , A ¯ ] ) , is called a partially-known formal concept with a set extent and an interval-set intent, or simply a partially-known SE-ISI formal concept, if the following conditions hold: [ σ _ , σ ¯ ] ( O ) = [ A _ , A ¯ ] , < τ _ , τ ¯ > ( [ A _ , A ¯ ] ) = O , where [ σ _ , σ ¯ ] ( O ) = [ σ _ ( O ) , σ ¯ ( O ) ] , < τ _ , τ ¯ > ( [ A _ , A ¯ ] ) = τ _ ( A _ ) ∩ τ ¯ ( A ¯ ) .

In what follows, we will focus on the following question: if we adopt the residual implication on { 0 , 1 2 , 1 } , what types of interval sets can we obtain? The obtained results are summarized in the following propositions. It is important to note that we don’t distinguish interval set and three-valued mappings in the following discussion, because they are in an one-to-one correspondence. Precisely, given an interval set [ O _ , O ¯ ] , we can define a three-valued mapping f as follows: f (o) =1 for o ∈ O _ , f (o) =0 for o ∈ ( O ¯ ) c and 1 2 else. Conversely, given a three-valued mapping f, an interval set [ O _ , O ¯ ] can be constructed as follows: O _ = f - 1 ( 1 ) , O ¯ = f - 1 ( 1 ) ∪ f - 1 ( 1 2 ) . Such a correspondence is surjective and injective.

Proposition 3.1. Let L = ( { 0 , 1 2 , 1 } , ∧ , ∨ , ⊗ L , → L , 0 , 1 ) be a residuated lattice, (OB, AT, {0, ? , 1} , J) be an L-fuzzy context, then for O ⊆ OB, A ⊆ AT, O * = [ σ _ ( O ) , σ ¯ ( O ) ] , A * = [ τ _ ( A ) , τ ¯ ( A ) ] .

Example 3.1. Table 1 is an example of an incomplete formal context. It can be naturally treated as an L-fuzzy formal context, where L = { 0 , 1 2 , 1 } . Let O = {1, 2, 3} , then according to Definition 2.3, we have σ _ ( O ) = { a } , σ ¯ ( O ) = { a , c } , and thus, [ σ _ , σ ¯ ] ( O ) = [ A _ , A ¯ ] = [ { a } , { a , c } ] . This result can be reinterpreted from the viewpoint of three-valued logics. Indeed, the three-valued mapping corresponding to O is as follows: f : AT → { 0 , 1 2 , 1 } , f ( 1 ) = f ( 2 ) = f ( 3 ) = 1 , f ( 4 ) = f ( 5 ) = f ( 6 ) = 0 .

According to Definition 3.2, if we employ Łukasiewicz implication operator →, we have

f^∗ (a) = ⋀_o∈OB (f (o) → I (o, a)) = (f (1) → I (1, a)) ∧ (f (2) → I (2, a)) ∧ (f (3) → I (3, a)) ∧ (f (4) → I (4, a)) ∧ (f (5) → I (5, a)) ∧ (f (6) → I (6, a)) = (1 → 1) ∧ (1 → 1) ∧ (1 → 1) ∧ (0 → 1 2 ) ∧ (0 → 1) ∧ (0 → 1) = 1,

f^∗ (b) = ⋀_o∈OB (f (o) → I (o, b)) = (f (1) → I (1, b)) ∧ (f (2) → I (2, b)) ∧ (f (3) → I (3, b)) ∧ (f (4) → I (4, b)) ∧ (f (5) → I (5, b)) ∧ (f (6) → I (6, b)) = (1 → 1) ∧ (1 → 0) ∧ (1 → 1) ∧ (0 → 1) ∧ (0 → 1) ∧ (0 → 1) = 0,

f^∗ (c) = ⋀_o∈OB (f (o) → I (o, c)) = (f (1) → I (1, c)) ∧ (f (2) → I (2, c)) ∧ (f (3) → I (3, c)) ∧ (f (4) → I (4, c)) ∧ (f (5) → I (5, c)) ∧ (f (6) → I (6, c)) = (1 → 1 2 ) ∧ (1 → 1 2 ) ∧ (1 → 1) ∧ (0 → 1) ∧ (0 → 0) ∧ (0 → 1) = 1 2 ,

similarly, f^∗ (d) = f^∗ (e) =0 . That is, f^∗ is defined as follows:

f ∗ : AT → { 0 , 1 2 , 1 } , f ( a ) = 1 , f ( c ) = 1 2 , f ( b ) = f ( d ) = f ( e ) = 0 .

It can be checked easily that the corresponding interval set is [{a} , {a, c}], as desired.

Proposition 3.2. Let L = (L, ∧ , ∨ , ⊗  _G , →  _G , 0, 1) be a residual lattice, (OB, AT, {0, ? , 1} , J) be an L-fuzzy context, then for O ⊆ OB, A ⊆ AT, O * = [ σ _ ( O ) , σ ¯ ( O ) ] , A * = [ τ _ ( A ) , τ ¯ ( A ) ] .

Proof. Note that the fundamental properties that are used in the proof of Proposition 3.1 are still valid for G o ̈ del implication, and hence, the desired result also holds.

Since Łukasiewicz implication and G o ̈ del implication are all residual implications on { 0 , 1 2 , 1 } , we can conclude that the proposed SE-ISI concepts can be equivalently described by using residual implications on { 0 , 1 2 , 1 } . A natural question then arises: if we employ other types of implications on { 0 , 1 2 , 1 } (not restricted to residual implication), what types of interval sets can we obtain? Before doing this, we should bear in mind that if we employ a non-residual implication on { 0 , 1 2 , 1 } , ( { 0 , 1 2 , 1 } , ∧ , ∨ , → , 0 , 1 ) does not form a residual lattice. The following discussion is conducted without such a premise.

Proposition 3.3. In (1)-(2), if we employ Ja s ´ kowski implication, Kleene implication, Nelson implication, then for O ⊆ OB, A ⊆ AT, we have O * = [ σ _ ( O ) , σ ¯ ( O ) ] , A * = [ τ _ ( A ) , τ ¯ ( A ) ] .

Proof. The fundamental properties that used in the proof of Proposition 3.2 are 0 → a = 1, 1 → b = 1 ⇔ b = 1 and 1 → 1 2 = 1 2 , which are valid for Ja s ´ kowski implication, Kleene implication, Nelson implication, and hence, the desired result holds.

The following proposition shows that if we use Gaines-Rescher implication, then < τ _ , τ ¯ > in Definition 3.3 coincides with the mapping ∗ in Definition 3.2.

Proposition 3.4. If we use the Gaines-Rescher implication on { 0 , 1 2 , 1 } , then for [ A _ , A ¯ ] ∈ 2 AT , < τ _ , τ ¯ > ( [ A _ , A ¯ ] ) = τ _ ( A _ ) ∩ τ ¯ ( A ¯ ) = g * , where g denotes the three-valued mapping on AT corresponding to [ A _ , A ¯ ] .

Proof. According to Definition 3.3, < τ _ , τ ¯ > ( [ A _ , A ¯ ] ) = τ _ ( A _ ) ∩ τ ¯ ( A ¯ ) , and therefore, it is equivalent to show that for any o ∈ OB, o ∈ τ _ ( A _ ) ∩ τ ¯ ( A ¯ ) if and only if g^∗ (o) =1 . Taking into Definition 3.2 into account, g^∗ (o) =1 if and only if for any a ∈ AT, g (a) =1 implies I (o, a) =1 and g ( a ) = 1 2 implies I (o, a) =1 or I ( o , a ) = 1 2 , or equivalently, for any a ∈ A _ , I (o, a) =1 and for any a ∈ A ¯ , I (o, a) =1 or I ( o , a ) = 1 2 , that is, o ∈ τ _ ( A _ ) ∩ τ ¯ ( A ¯ ) .

We thus conclude from Proposition 3.1-Proposition 3.4 that the collection SE-ISI and ISE-SI concepts can be obtained by employing Łukasiewicz implication (or equivalently, G o ̈ del implication, Ja s ´ kowski implication, Kleene implication, Nelson implication) in E-I direction (i.e., from extension to intension) and Gaines-Rescher implication in I-E direction (i.e., from intension to extension).

However, if we employ Sette and Gaines-Rescher implication in E-I direction, we may obtain a different result.

Proposition 3.5. If we employ Soboci n ´ ski implication, Bochvar external implication and Gaines-Rescher implication in (1), then for O ⊆ OB, A ⊆ AT, we have O * = [ σ _ ( O ) , σ _ ( O ) ] , A * = [ τ _ ( A ) , τ _ ( A ) ] .

Proof. According to the definition of Soboci n ´ ski implication (see Table 1), a → b ∈ {0, 1} for a , b ∈ { 0 , 1 2 , 1 } , and thus, O^* reduces to a ordinary set. Moreover, since O^* (a) =1 if and only if for any o ∈ OB, O (o) =1 implies I (o, a) =1, if and only if for any o ∈ O, I (o, a) =1, we conclude that O * = [ σ _ ( O ) , σ _ ( O ) ] . A * = [ τ _ ( A ) , τ _ ( A ) ] can be shown in a similar manner.

The above proposition shows that if we employ Soboci n ´ ski implication, Bochvar external implication and Gaines-Rescher implication, then O^* is equal to the derivation operator in the least completion of an incomplete formal context.

Example 3.2. (Continued from Example 3.1) Let O = {3, 4} , then according to Definition 2.3, we have σ _ ( O ) = { b , c } , σ ¯ ( O ) = { a , b , c , d } , and thus, [ σ _ , σ ¯ ] ( O ) = [ O _ , O ¯ ] = [ { b , c } , { a , b , c , d } ] . This result can be reinterpreted from the viewpoint of three-valued logics. Indeed, the three-valued mapping corresponding to O is as follows: f : AT → { 0 , 1 2 , 1 } , f ( 3 ) = f ( 4 ) = 1 , f ( 1 ) = f ( 2 ) = f ( 5 ) = f ( 6 ) = 0 .

According to Definition 3.2, if we employ G O ̈ del implication operator →, we have

f^∗ (a) = ⋀_o∈OB (f (o) → I (o, a)) = (f (1) → I (1, a)) ∧ (f (2) → I (2, a)) ∧ (f (3) → I (3, a)) ∧ (f (4) → I (4, a)) ∧ (f (5) → I (5, a)) ∧ (f (6) → I (6, a)) = (0 → 1) ∧ (0 → 1) ∧ (1 → 1) ∧ (1 → 1 2 ) ∧ (0 → 1) ∧ (0 → 1) = 1 2 ,

f^∗ (b) = ⋀_o∈OB (f (o) → I (o, b)) = (f (1) → I (1, b)) ∧ (f (2) → I (2, b)) ∧ (f (3) → I (3, b)) ∧ (f (4) → I (4, b)) ∧ (f (5) → I (5, b)) ∧ (f (6) → I (6, b)) = (0 → 1) ∧ (0 → 0) ∧ (1 → 1) ∧ (1 → 1) ∧ (0 → 1) ∧ (0 → 1) = 1,

f^∗ (c) = ⋀_o∈OB (f (o) → I (o, c)) = (f (1) → I (1, c)) ∧ (f (2) → I (2, c)) ∧ (f (3) → I (3, c)) ∧ (f (4) → I (4, c)) ∧ (f (5) → I (5, c)) ∧ (f (6) → I (6, c)) = (0 → 1 2 ) ∧ (0 → 1 2 ) ∧ (1 → 1) ∧ (0 → 1) ∧ (0 → 0) ∧ (0 → 1) = 1,

similarly, f^∗ (d) =1, f^∗ (e) =0 . That is, f^∗ is defined as follows: f ∗ : AT → { 0 , 1 2 , 1 } , f ( b ) = f ( c ) = 1 , f ( a ) = f ( d ) = 1 2 , f ( e ) = 0 .

It can be checked easily that the corresponding interval set is [{b, c} , {a, b, c, d}], as desired.

Proposition 3.6. If we employ Sette implication in (1), then for O ⊆ OB, A ⊆ AT, we have O * = [ σ ¯ ( O ) , σ ¯ ( O ) ] , A * = [ τ ¯ ( A ) , τ ¯ ( A ) ] .

Proof. According to the definition of Sette implication (see Table 1), a → b ∈ {0, 1} for a , b ∈ { 0 , 1 2 , 1 } , and thus, O^* reduces to a ordinary set, moreover, since O^* (a) =1 if and only if for any o ∈ OB, O (o) =1 implies I ( o , a ) ∈ { 1 2 , 1 } , if and only if a ∈ σ ¯ ( O ) . We can thus conclude that O * = [ σ ¯ ( O ) , σ ¯ ( O ) ] .

A * = [ τ ¯ ( A ) , τ ¯ ( A ) ] can be shown in a similar manner.

The above proposition shows that if we employ Sette implication, then O^* is equal to the derivation operator in the greatest completion of an incomplete formal context.

We summarize the obtained results in Table 4.

Definition 3.4. [17] A pair of interval-set based operators [ σ _ , σ ¯ ] : I ( 2 OB ) → I ( 2 AT ) ∪ ∅ and [ τ _ , τ ¯ ] : I ( 2 AT ) → I ( 2 OB ) ∪ ∅ is defined by: for an interval set of objects [ O _ , O ¯ ] and an interval set of attributes [ A _ , A ¯ ] , [ σ _ , σ ¯ ] ( [ O _ , O ¯ ] ) = [ σ _ ( O _ ) , σ ¯ ( O ¯ ) ] , [ τ _ , τ ¯ ] ( [ A _ , A ¯ ] ) = [ τ _ ( A _ ) , τ ¯ ( A ¯ ) ] , where [ σ _ ( O _ ) , σ ¯ ( O ¯ ) ] = ∅ when σ ¯ ( O ¯ ) ⊂ σ _ ( O _ ) and [ τ _ ( A _ ) , τ ¯ ( A ¯ ) ] = ∅ when τ ¯ ( A ¯ ) ⊂ τ _ ( A _ ) .

For ISE-ISI concepts, both extents and intents are interval sets, they can be equivalently represented by three-valued mappings. In what follows, we will examine the following issue: Whether ISE-ISI concepts can be generated by using the existing implications on { 0 , 1 2 , 1 } ?

The following proposition provides different ISE-ISI concepts by using all possible implications on { 0 , 1 2 , 1 } .

Proposition 3.7. (i) If we use Łukasiewicz implication, then for [ O _ , O ¯ ] ∈ 2 OB , we have [ O _ , O ¯ ] * = [ σ ¯ ( O ¯ \ O _ ) ∩ σ _ ( O _ ) , σ ¯ ( O _ ) ] ,

(ii) If we use G o ̈ del implication, then for [ O _ , O ¯ ] ∈ 2 OB , we have [ O _ , O ¯ ] * = [ σ ¯ ( O ¯ \ O _ ) ∩ σ _ ( O _ ) , σ ¯ ( O ¯ ) ] ,

(iii) If we use Sette implication, then for [ O _ , O ¯ ] ∈ 2 OB , we have [ O _ , O ¯ ] * = [ σ ¯ ( O ¯ ) , σ ¯ ( O ¯ ) ] ,

(iv) If we use Nelson implication, then for [ O _ , O ¯ ] ∈ 2 OB , we have [ O _ , O ¯ ] * = [ σ _ ( O _ ) , σ ¯ ( O _ ) ] ,

(v) If we use Kleene implication, then for [ O _ , O ¯ ] ∈ 2 OB , we have [ O _ , O ¯ ] * = [ σ _ ( O ¯ ) , σ ¯ ( O _ ) ] ,

(vi) If we use Ja s ´ kowski implication, then for [ O _ , O ¯ ] ∈ 2 OB , we have [ O _ , O ¯ ] * = [ σ _ ( O ¯ ) , σ ¯ ( O ¯ ) ] ,

(vii) If we use Soboci n ´ ski implication, then for [ O _ , O ¯ ] ∈ 2 OB , we have [ O _ , O ¯ ] * = [ σ _ ( O ¯ ) , σ ¯ ( O ¯ \ O _ ) ∩ σ _ ( O _ ) ] ,

(viii) If we use Gaines-Rescher implication, then for [ O _ , O ¯ ] ∈ 2 OB , we have [ O _ , O ¯ ] * = [ σ ¯ ( O ¯ \ O _ ) ∩ σ _ ( O _ ) , σ ¯ ( O ¯ \ O _ ) ∩ σ _ ( O _ ) ] ,

(ix) If we use Bochvar external implication, then for [ O _ , O ¯ ] ∈ 2 OB , we have [ O _ , O ¯ ] * = [ σ _ ( O _ ) , σ _ ( O _ ) ] .

Proposition 3.7 tells that if we use different types if implications on { 0 , 1 2 , 1 } , we can get different interval sets. In particularly, if we use Sette, Bochvar external or Gaines-Rescher implication, then the obtained interval set reduces to an ordinary set.

According to Definition 3.4, if σ _ ( O _ ) ⊆ σ ¯ ( O ¯ ) , then the interval-set based operator [ σ _ , σ ¯ ] satisfies [ σ _ , σ ¯ ] ( [ O _ , O ¯ ] ) = [ σ _ ( O _ ) , σ ¯ ( O ¯ ) ] . The following proposition states that there doesn’t exist an implication → on { 0 , 1 2 , 1 } such that [ σ _ , σ ¯ ] can be realized by using →.

Proposition 3.8. Let → be one of implication operators on { 0 , 1 2 , 1 } in Table 1 and [ O _ , O ¯ ] ⊆ 2 OB , then [ σ _ , σ ¯ ] cannot be obtained by using →, under the premise of σ _ ( O _ ) ⊆ σ ¯ ( O ¯ ) .

4.1 Attribute implications

Attribute implications are important tools of conceptual data analysis. Let K = (OB, AT, I) be a complete context. For sets A, B ⊆ AT of attributes, we designate by A → B an attribute implication, where A is called the premise, B is called the conclusion of the implication. We say that this implication holds (is valid) in K, if and only if, for every object o ∈ OB to which all attributes from A apply, all attributes from B apply, too, or equivalently, A ⊆ σ ({o}) implies B ⊆ σ ({o}) .

By treating attributes in M as propositional variables, we can also interpret A → B as a propositional formula ∧_a∈A → ∧ _b∈B. Such attribute implications contain a lot of information about the data, and the concept lattice of a given complete context K is determined up to isomorphism by the knowledge of a set of attribute implications valid in K and generating the set of all attribute implications valid in K with respect to the ARMSTRONG rules ^[1].

For incomplete contexts, attribute implications can be generated as follows. Let K = (OB, AT, {+, ?, -}, J) be an incomplete formal context. An attribute implication A → B is certainly valid in K if it holds in any completion of K; an attribute implication A → B is possibly valid in K, if it holds in some completion of K; otherwise, the attribute implication is invalid in K. Usually, we assign the value 1 to those certainly valid attribute implications, the value 1 2 to those possibly but not certainly valid attribute implications and 0 to those invalid attribute implications.

4.2 Evaluating attribute implications with Kleene logic

In [1], the three-valued Kleene logic is used to evaluate attribute implications. Every pair (o, a) (o ∈ OB, a ∈ AT) can be associated with a propositional variable, whose value is given by J (o, a), that is, J ( o , a ) ∈ { 0 , 1 2 , 1 } . The value of an attribute implication A → B in the context K is actually the conjunction of the values of corresponding implications on single objects & o ∈ OB ( & a ∈ A J ( o , a ) → & a ∈ B J ( o , a ) ) .(3) (3) is also called a Kripke semantics. However, as stated in [1], the Kleene logic is not guaranteed to compute the truth-value of an implication, as well as of any other propositional formula, which can be seen from the fact that the implication {a} → {a} is valid in every completion of any incomplete context, yet one also easily realizes that it will get the truth value 1 2 whenever a gets the value. However, one has the following result, which is helpful to check the validity and possibility of attribute implications with disjoints sets for premise and conclusion.

Proposition 4.1. Let K = (OB, AT, {+ , - , ?} , J) be an incomplete context, and let Φ be a propositional formula with propositional variables in AT. Then the three-valued Kleene-logic computes the truth value of Φ with respect to K correctly in the sense of our Kriple-semantics, whenever every propositional variable occurs within Φ at most once.

Proposition 4.2. [1] Let A → B be an attribute implication with respect to some incomplete context K, then the three-valued Kleene logic computes its truth value correctly when it is applied to A → (B \ A) instead of A → B.

Proposition 4.2 shows a way to evaluate an attribute implication syntactically with respect to any incomplete context, because the implications A → B and A → (B \ A) always contain the same information.

Note that Proposition 4.1 and 4.2 hold for attribute implications with disjoint sets for premise and conclusion. By considering a more general case, we can present the following sufficient and necessary condition for computing the true value of an attribute implication correctly by means of three-valued Kleene logic.

Let A → B be an attribute implication and C = A ∩ B. For o ∈ OB, c ∈ C, a ∈ A \ C, b ∈ B \ C, we call (J (o, a), J (o, b), J (o, c)) a truth vector of o with respect to A → B if J (o, c) & J (o, a) → J (o, c) & J (o, b) = &_o ∈OB (& _a∈A J (o, a) → &_a∈B J (o, a)). Denote

H 0 = { ( J ( o , c ) , J ( o , a ) , J ( o , b ) ) ∣ J ( o , c ) & J ( o , a ) → J ( o , c ) & J ( o , b ) = 0 } , H 1 2 = { ( J ( o , a ) , J ( o , b ) , J ( o , c ) ) ∣ J ( o , c ) & J ( o , a ) → J ( o , c ) & J ( o , b ) = 1 2 } , H 1 = { ( J ( o , a ) , J ( o , b ) , J ( o , c ) ) ∣ J ( o , c ) & J ( o , a ) → J ( o , c ) & J ( o , b ) = 1 } .

Owing to Proposition 4.1, we will consider the case C≠ ∅ in the following discussion.

Proposition 4.3. Let K = (OB, AT, {+ , - , ?} , J) be an incomplete context, and let A → B be an attribute implication with A\ C ≠ ∅ and B\ C ≠ ∅. Then the three-valued Kleene-logic computes the truth value of A → B with respect to K correctly in the sense of our Kriple-semantics if and only if & o ∈ OB ( & a ∈ A J ( o , a ) → & b ∈ B J ( o , b ) ) = 1 2 implies H 1 2 \ { ( + , + , ? ) , ( ? , + , ? ) } ≠ ∅ .

Proposition 4.3 holds under the preliminary condition A\ C ≠ ∅ and B\ C ≠ ∅. For the left cases, we have the following results.

Proposition 4.4. Let K = (OB, AT, {+ , - , ?} , J) be an incomplete context, and let A → B be an attribute implication with A\ C = ∅ and B\ C ≠ ∅. Then the three-valued Kleene-logic computes the truth value of A → B with respect to K correctly in the sense of our Kriple-semantics.

Proof. The preliminary condition A\ C = ∅ and B\ C ≠ ∅ means A ⊂ B, which leads immediately to &_a∈AJ (o, a) ≥ & _b∈BJ (o, b) for any o ∈ OB. Then the desired result follows from the following table (i.e., Table 6).

Proposition 4.5. Let K = (OB, AT, {+ , - , ?} , J) be an incomplete context, and let A → B be an attribute implication with A\ C ≠ ∅ and B\ C = ∅. Then the three-valued Kleene-logic computes the truth value of A → B with respect to K correctly in the sense of our Kriple-semantics.

Proof. The preliminary condition A\ C ≠ ∅ and B\ C = ∅ means A ⊃ B, which leads immediately to &_a∈AJ (o, a) ≤ & _b∈BJ (o, b) for any o ∈ OB. Then the desired result follows from the following table (i.e., Table 7).

Proposition 4.6. Let K = (OB, AT, {+ , - , ?} , J) be an incomplete context, and let A → B be an attribute implication with A\ C = ∅ and B\ C = ∅. Then the three-valued Kleene-logic computes the truth value of A → B with respect to K correctly in the sense of our Kriple-semantics if and only if ∀o ∈ OB, & _a∈AJ (o, a) = & _b∈BJ (o, b) ∈ {0, 1}.

Proof. The preliminary condition A\ C = ∅ and B\ C = ∅ means A = B, which is a certainly valid attribute implication. Then the desired result follows immediately from the fact that ? → ? = ? holds in three-valued Kleene logic (see Table 8).