Implication (information science)

Definition

A pair of sets ( U , V ) is an implication. U ⊆ A and V ⊆ A . U is the premise and V is the conclusion. A stands for attributes.

A set W respects U → V , if U ⊈ W  or  V ⊆ W .

Implications in a Concept Lattice

U → V holds in a concept lattice, if every intent respects it. This is true if

1. iff U ′ ⊆ V ′ .

1. iff V ⊆ U ″ .

An implication U → V follows semantically from a set L of implications, if each subset of A respecting L also respects U → V . L is closed, if it contains all implications that follow from L.

A set L of implications that hold in a context is called sound. It is called complete if every implications that holds in the context follows from L. L is non-redundant if implications that follow from L are not in L.

If L is a set of implications, then { X ⊆ A | X respects L } is a closure system.

Implication Basis

Let X ↦ X ″ be a closure operator then P is pseudo-closed if

1. P ≠ P ″
2. Q ⊂ P ⟹ Q ″ ⊆ P

The set { P ↦ P ″ | P pseudo-closed } is sound, complete and non-redundant. It is called Duquenne-Guiges-Basis (D-G-basis) or Stem basis.

There cannot be a implication basis with less implications than the Duquenne-Guiges-Basis, but one can choose implications that are simpler regarding ∑ | U | | V | . Such implications are U → V with V ≠ ∅ and U ∩ V = ∅ .