T-norm
2099179
179800657
2007-12-23T16:44:06Z
83.237.202.235
/* References */
In [[mathematics]], a '''t-norm''' (also '''T-norm''' or, unabbreviated, '''triangular norm''') is a kind of [[binary operation]] used in the framework of [[probabilistic metric space|probabilistic metric spaces]] and in [[multi-valued logic]], specifically in [[fuzzy logic]]. A t-norm generalizes [[intersection (set theory)|intersection]] in a [[lattice (order)|lattice]] and [[logical conjunction|conjunction]] in [[logic]]. The name ''triangular norm'' refers to the fact that in the framework of probabilistic metric spaces t-norms are used to generalize [[triangle inequality]] of ordinary [[metric space|metric spaces]].
== Definition ==
A t-norm is a [[function (mathematics)|function]] T: [0, 1] × [0, 1] → [0, 1] which satisfies the following properties:
* [[Commutativity]]: T(''a'', ''b'') = T(''b'', ''a'')
* [[Monotonicity]]: T(''a'', ''b'') ≤ T(''c'', ''d'') if ''a'' ≤ ''c'' and ''b'' ≤ ''d''
* [[Associativity]]: T(''a'', T(''b'', ''c'')) = T(T(''a'', ''b''), ''c'')
* The number 1 acts as [[identity element]]: T(''a'', 1) = ''a''
Since a t-norm is a [[binary operation|binary algebraic operation]] on the interval [0, 1], infix algebraic notation is also common, with the t-norm usually denoted by <math>*</math>.
The defining conditions of the t-norm are exactly those of the partially ordered Abelian monoid on the real unit interval [0, 1]. '' (Cf. [[ordered group]].)'' The monoidal operation of any partially ordered Abelian monoid ''L'' is therefore by some authors called a ''triangular norm on L''.
=== Motivations and applications ===
T-norms are a generalization of the usual two-valued [[logical conjunction]], studied by classical logic, for [[fuzzy logic]]s. Indeed, the classical Boolean conjunction is both commutative and associative. The monotonicity property ensures that the [[degree of truth|truth value]] of conjunction does not decrease if the truth values of conjuncts increase. The requirement that 1 be an identity element corresponds to the interpretation of 1 as ''true'' (and consequently 0 as ''false''). Continuity, which is often required from fuzzy conjunction as well, expresses the idea that, roughly speaking, very small changes in truth values of conjuncts should not macroscopically affect the truth value of their conjunction.
T-norms are also used to construct the [[intersection (set theory)|intersection]] of [[fuzzy set]]s or as a basis for aggregation operators (see [[fuzzy set operations]]). In [[probabilistic metric space]]s, t-norms are used to generalize [[triangle inequality]] of ordinary metric spaces. Individual t-norms may of course frequently occur in further disciplines of mathematics, since the class contains many familiar functions.
=== Classification of t-norms ===
A t-norm is called ''continuous'' if it is [[continuous function|continuous]] as a function, in the usual interval topology on [0, 1]<sup>2</sup> (similarly for ''left-'' and ''right-continuity'').
A t-norm <math>*</math> is called ''Archimedean'' if it has the [[Archimedean property]], i.e., if for each ''x'', ''y'' in the open interval (0, 1) there is a natural number ''n'' such that ''x'' <math>*</math> ... <math>*</math> ''x'' (''n'' times) is less than or equal to ''y''. A continuous Archimedean t-norm is called ''strict'' if 0 is its only [[nilpotent]] element; otherwise it is called ''nilpotent''.
The usual partial ordering of t-norms is pointwise, i.e.,
: T<sub>1</sub> ≤ T<sub>2</sub> if T<sub>1</sub>(''a'', ''b'') ≤ T<sub>2</sub>(''a'', ''b'') for all ''a'', ''b'' in [0, 1].
As functions, pointwise larger t-norms are sometimes called ''stronger'' than those pointwise smaller. In the semantics of fuzzy logic, however, the larger a t-norm, the ''weaker'' the conjunction it represents.
==Prominent examples==
[[Image:MinimumTnorm-graph-contour.png|thumb|270px|Graph of the minimum t-norm (3D and contours)]]
*'''Minimum t-norm''' <math>\top_{\mathrm{min}}(a, b) = \min \{a, b\},</math> also called the '''Gōdel t-norm''', as it is the standard semantics for conjunction in [[Gōdel fuzzy logic]]. Besides that, it occurs in most t-norm based fuzzy logics as the standard semantics for weak conjunction. It is the pointwise largest t-norm (see the [[#Properties of t-norms|properties of t-norms]] below).
[[Image:ProductTnorm-graph-contour.png|thumb|270px|Graph of the product t-norm]]
*'''Product t-norm''' <math>\top_{\mathrm{prod}}(a, b) = a \cdot b</math> (the ordinary product of real numbers). Besides other uses, the product t-norm is the standard semantics for strong conjunction in [[product fuzzy logic]]. It is a strict Archimedean t-norm.
[[Image:LukasiewiczTnorm-graph-contour.png|thumb|270px|Graph of the Łukasiewicz t-norm]]
*'''Łukasiewicz t-norm''' <math>\top_{\mathrm{Luk}}(a, b) = \max \{0, a+b-1\}.</math> The name comes from the fact that the t-norm is the standard semantics for strong conjunction in [[Łukasiewicz fuzzy logic]]. It is a nilpotent Archimedean t-norm, pointwise smaller than the product t-norm.
[[Image:DrasticTnorm-graph-contour.png|thumb|270px|Graph of the drastic t-norm. The function is discontinuous at the lines 0 < ''x'' = 1 and 0 < ''y'' = 1.]]
*'''Drastic t-norm'''
::<math>\top_{\mathrm{D}}(a, b) = \begin{cases}
b & \mbox{if }a=1 \\
a & \mbox{if }b=1 \\
0 & \mbox{otherwise.}
\end{cases}</math>
:The name reflects the fact that the drastic t-norm is the pointwise smallest t-norm (see the [[#Properties of t-norms|properties of t-norms]] below). It is a right-continuous Archimedean t-norm.
[[Image:NilpotentMinimum-graph-contour.png|thumb|270px|Graph of the nilpotent minimum. The function is discontinuous at the line 0 < ''x'' = 1 − ''y'' < 1.]]
*'''Nilpotent minimum'''
::<math>\top_{\mathrm{nM}}(a, b) = \begin{cases}
\min(a,b) & \mbox{if }a+b > 1 \\
0 & \mbox{otherwise}
\end{cases}</math>
:is a standard example of a t-norm which is left-continuous, but not continuous. Despite its name, the nilpotent minimum is not a nilpotent t-norm.
[[Image:HamacherProduct-graph-contour.png|thumb|270px|Graph of the Hamacher product]]
*'''Hamacher product'''
::<math>\top_{\mathrm{H}_0}(a, b) = \begin{cases}
0 & \mbox{if } a=b=0 \\
\frac{ab}{a+b-ab} & \mbox{otherwise}
\end{cases}</math>
:is a strict Archimedean t-norm, and an important representative of the parametric classes of [[Construction of t-norms#Hamacher t-norms|Hamacher t-norms]] and [[Construction of t-norms#Schweizer–Sklar t-norms|Schweizer–Sklar t-norms]].
==Properties of t-norms==
The drastic t-norm is the pointwise smallest t-norm and the minimum is the pointwise largest t-norm:
:<math>\top_{\mathrm{D}}(a, b) \le \top(a, b) \le \mathrm{\top_{min}}(a, b),</math> for any t-norm <math>\top</math> and all ''a'', ''b'' in [0, 1].
For every t-norm T, the number 0 acts as null element: T(''a'', 0) = 0 for all ''a'' in [0, 1].
A t-norm T has [[zero divisor]]s if and only if it has [[nilpotent element|nilpotent]] elements; each nilpotent element of T is also a zero divisor of T. The set of all nilpotent elements is an interval [0, ''a''] or [0, ''a''), for some ''a'' in [0, 1].
=== Properties of continuous t-norms ===
Although real functions of two variables can be continuous in each variable without being continuous on [0, 1]<sup>2</sup>, this is not the case with t-norms: a t-norm T is continuous if and only if it is continuous in one variable, i.e., if and only if the functions ''f<sub>y</sub>''(''x'') = T(''x'', ''y'') are continuous for each ''y'' in [0, 1]. Analogous theorems hold for left- and right-continuity of a t-norm.
A continuous t-norm is Archimedean if and only if 0 and 1 are its only [[idempotent|idempotents]].
A continuous Archimedean t-norm T is nilpotent if and only if each ''x'' < 1 is a nilpotent element of T. Thus with a continuous Archimedean t-norm T, either all or none of the elements of (0, 1) are nilpotent. If it is the case that all elements in (0, 1) are nilpotent, then the t-norm is isomorphic to the Łukasiewicz t-norm; i.e., there is a strictly increasing function ''f'' such that
:<math>\top(x,y) = f^{-1}(\top_{\mathrm{Luk}}(f(x), f(y))).</math>
If on the other hand it is the case that there are no nilpotent elements of T, the t-norm is isomorphic to the product t-norm. In other words, all nilpotent t-norms are isomorphic, the Łukasiewicz t-norm being their prototypical representative; and all strict t-norms are isomorphic, with the product t-norm as their prototypical example. The Łukasiewicz t-norm is itself isomorphic to the product t-norm undercut at 0.25, i.e., to the function ''p''(''x'', ''y'') = max(0.25, ''x'' · ''y'') on [0.25, 1]<sup>2</sup>.
For each continuous t-norm, the set of its idempotents is a closed subset of [0, 1]. Its complement — the set of all elements which are not idempotent — is therefore a union of countably many non-overlapping open intervals. The restriction of the t-norm to any of these intervals (including its endpoints) is Archimedean, and thus isomorphic either to the Łukasiewicz t-norm or the product t-norm. For such ''x'', ''y'' that do not fall into the same open interval of non-idempotents, the t-norm evaluates to the minimum of ''x'' and ''y''. These conditions actually give a characterization of continuous t-norms, called the '''Mostert–Shields theorem''', since every continuous t-norm can in this way be decomposed, and the described construction always yields a continuous t-norm. The theorem can also be formulated as follows:
:A t-norm is continuous if and only if it is isomorphic to an [[Construction of t-norms#Ordinal sums|ordinal sum]] of the minimum, Łukasiewicz, and product t-norm.
A similar characterization theorem for non-continuous t-norms is not known (not even for left-continuous ones), only some non-exhaustive methods for the [[construction of t-norms]] have been found.
== Residuum ==
For any left-continuous t-norm <math>\top</math>, there is a unique binary operation <math>\Rightarrow</math> on [0, 1] such that
:<math>\top(z, x) \le y</math> if and only if <math>z \le (x \Rightarrow y)</math>
for all ''x'', ''y'', ''z'' in [0, 1]. This operation is called the ''residuum'' of the t-norm. In prefix notation, the residuum to a t-norm <math>\top</math> is often denoted by <math>\vec{\top}</math> or by the letter R.
The interval [0, 1] equipped with a t-norm and its residuum forms a [[residuated lattice]]. The relation between a t-norm T and its residuum R is an instance of [[adjunction]]: the residuum forms a right adjoint R(''x'', –) to the functor T(–, ''x'') for each ''x'' in the lattice [0, 1] taken as a [[poset]] category.
In the standard semantics of t-norm based fuzzy logics, where conjunction is interpreted by a t-norm, the residuum plays the role of implication (often called ''R-implication'').
=== Basic properties of residua ===
If <math>\Rightarrow</math> is the residuum of a left-continuous t-norm <math>\top</math>, then
:<math>(x \Rightarrow y) = \sup\{z\mid\top(z,x) \le y\}.</math>
Consequently, for all ''x'', ''y'' in the unit interval,
:<math>(x \Rightarrow y) = 1</math> if and only if <math>x \le y</math>
and
:<math>(1 \Rightarrow y) = y.</math>
If <math>*</math> is a left-continuous t-norm and <math>\Rightarrow</math> its residuum, then
:<math>\begin{array}{rcl}
\min(x,y) & \ge & x * (x \Rightarrow y) \\
\max(x, y) & = & \min((x \Rightarrow y)\Rightarrow y, (y \Rightarrow x)\Rightarrow x).
\end{array}</math>
If <math>*</math> is continuous, then equality holds in the former.
=== Residua of prominent left-continuous t-norms ===
If ''x'' ≤ ''y'', then R(''x'', ''y'') = 1 for any residuum R. The following table therefore gives the values of prominent residua only for ''x'' > ''y''.
{| class="wikitable"
! Residuum of the !! Name !! Value for ''x'' > ''y'' !! Graph
|-
| Minimum t-norm
| Standard Gōdel implication
| align="center" | ''y''
| [[Image:ResiduumMinimumTnorm-graph-contour.png|thumb|270px|left|Standard Gödel implication. The function is discontinuous at the line ''y'' = ''x'' < 1.]]
|-
| Product t-norm
| [[Joseph Goguen|Goguen]] implication
| align="center" | ''y'' / ''x''
| [[Image:ResiduumProductTnorm-graph-contour.png|thumb|270px|left|Goguen implication. The function is discontinuous at the point ''x'' = ''y'' = 0.]]
|-
| Łukasiewicz t-norm
| Standard Łukasiewicz implication
| align="center" | 1 – ''x'' + ''y''
| [[Image:ResiduumLukasiewiczTnorm-graph-contour.png|thumb|270px|left|Standard Łukasiewicz implication.]]
|-
| Nilpotent minimum
|
| align="center" | max(1 – ''x'', ''y'')
| [[Image:ResiduumNilpotentMinimum-graph-contour.png|thumb|270px|left|Residuum of the nilpotent minimum. The function is discontinuous at the line 0 < ''y'' = ''x'' < 1.]]
|}
== T-conorms ==
'''T-conorms''' (also called '''S-norms''') are dual to t-norms under the order-reversing operation which assigns 1 – ''x'' to ''x'' on [0, 1]. Given a t-norm, the complementary conorm is defined by
: <math>\bot(a,b) = 1-\top(1-a, 1-b).</math>
This generalizes [[De Morgan's laws]].
It follows that a t-conorm satisfies the following conditions, which can be used for an equivalent axiomatic definition of t-conorms independently of t-norms:
* Commutativity: ⊥(''a'', ''b'') = ⊥(''b'', ''a'')
* Monotonicity: ⊥(''a'', ''b'') ≤ ⊥(''c'', ''d'') if ''a'' ≤ ''c'' and ''b'' ≤ ''d''
* Associativity: ⊥(''a'', ⊥(''b'', ''c'')) = ⊥(⊥(''a'', ''b''), ''c'')
* Identity element: ⊥(''a'', 0) = ''a''
T-conorms are used to represent [[logical disjunction]] in [[fuzzy logic]] and [[union (set theory)|union]] in [[fuzzy set theory]].
===Examples of t-conorms===
Important t-conorms are those dual to prominent t-norms:
[[Image:MaximumTconorm-graph-contour.png|thumb|270px|Graph of the maximum t-conorm (3D and contours)]]
*'''Maximum t-conorm''' <math>\bot_{\mathrm{max}}(a, b) = \max \{a, b\}</math>, dual to the minimum t-norm, is the smallest t-conorm (see the [[#Properties of t-conorms|properties of t-conorms]] below). It is the standard semantics for disjunction in [[Gödel fuzzy logic]] and for weak disjunction in all t-norm based fuzzy logics.
[[Image:ProbabilisticSum-graph-contour.png|thumb|270px|Graph of the probabilistic sum]]
*'''Probabilistic sum''' <math>\bot_{\mathrm{sum}}(a, b) = a + b - a \cdot b</math> is dual to the product t-norm. In [[probability theory]] it expresses the probability of the union of independent [[event (probability theory)|event]]s. It is also the standard semantics for strong disjunction in such extensions of [[product fuzzy logic]] in which it is definable (e.g., those containing involutive negation).
[[Image:BoundedSum-graph-contour.png|thumb|270px|Graph of the bounded sum t-conorm]]
*'''Bounded sum''' <math>\bot_{\mathrm{Luk}}(a, b) = \min \{a+b, 1\}</math> is dual to the Łukasiewicz t-norm. It is the standard semantics for strong disjunction in [[Łukasiewicz fuzzy logic]].
[[Image:DrasticTconorm-graph-contour.png|thumb|270px|Graph of the drastic t-conorm. The function is discontinuous at the lines 1 > ''x'' = 0 and 1 > ''y'' = 0.]]
*'''Drastic t-conorm'''
::<math>\bot_{\mathrm{D}}(a, b) = \begin{cases}
b & \mbox{if }a=0 \\
a & \mbox{if }b=0 \\
1 & \mbox{otherwise,}
\end{cases}</math>
:dual to the drastic t-norm, is the largest t-conorm (see the [[#Properties of t-conorms|properties of t-conorms]] below).
[[Image:NilpotentMaximum-graph-contour.png|thumb|270px|Graph of the nilpotent maximum. The function is discontinuous at the line 0 < ''x'' = 1 – ''y'' < 1.]]
*'''Nilpotent maximum''', dual to the nilpotent minimum:
::<math>\bot_{\mathrm{nM}}(a, b) = \begin{cases}
\max(a,b) & \mbox{if }a+b < 1 \\
1 & \mbox{otherwise.}
\end{cases}</math>
[[Image:EinsteinSum-graph-contour.png|thumb|270px|Graph of the Einstein sum]]
*'''Einstein sum''' (compare the [[velocity-addition formula]] under special relativity)
::<math>\bot_{\mathrm{H}_2}(a, b) = \frac{a+b}{1+ab}</math>
:is a dual to one of the [[Construction of t-norms#Hamacher t-norms|Hamacher t-norms]].
===Properties of t-conorms===
Many properties of t-conorms can be obtained by dualizing the properties of t-norms, for example:
* For any t-conorm ⊥, the number 1 is an annihilating element: ⊥(''a'', 1) = 1, for any ''a'' in [0, 1].
* Dually to t-norms, all t-conorms are bounded by the maximum and the drastic t-conorm:
::<math>\mathrm{\bot_{max}}(a, b) \le \bot(a, b) \le \bot_{\mathrm{D}}(a, b)</math>, for any t-conorm <math>\bot</math> and all ''a'', ''b'' in [0, 1].
Further properties result from the relationships between t-norms and t-conorms or their interplay with other operators, e.g.:
* A t-norm T [[distributivity|distributes]] over a t-conorm S, i.e.,
::T(''x'', S(''y'', ''z'')) = S(T(''x'', ''y''), T(''x'', ''z'')) for all ''x'', ''y'', ''z'' in [0, 1],
:if and only if S is the maximum t-conorm. Dually, any t-conorm distributes over the minimum, but not over any other t-norm.
== See also ==
* [[Construction of t-norms]]
== References ==
* Klement, Erich Peter; Mesiar, Radko; and Pap, Endre (2000), ''Triangular Norms''. Dordrecht: Kluwer. ISBN 0-7923-6416-3.
* Hájek, Petr (1998), ''Metamathematics of Fuzzy Logic''. Dordrecht: Kluwer. ISBN 0792352389
* Cignoli, Roberto L.O.; D'Ottaviano, Itala M.L.; and Mundici, Daniele (2000), ''Algebraic Foundations of Many-valued Reasoning''. Dordrecht: Kluwer. ISBN 0792360095
* Fodor, János (2004), [http://www.bmf.hu/journal/Fodor_2.pdf "Left-continuous t-norms in fuzzy logic: An overview".] ''Acta Polytechnica Hungarica'' '''1'''(2), ISSN 1785-8860 [http://www.bmf.hu/journal/]
[[Category:Fuzzy logic]]
[[de:T-Norm]]
[[ru:T-норма]]