A Tutorial Z´aklady fuzzy logiky 1 George J. Klir Osiˇcka State University Petr of New York (SUNY) Binghamton, New York 13902, USA
[email protected] Palacky University, Olomouc, Czech Republic
!
prepared for International Centre for Information and Uncertainty, Palacky University, Olomouc
! !
! P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
1 / 23
C´ıl pˇredn´aˇsky
sezn´amit v´as s motivac´ı pro vznik fuzzy logiky pojmy fuzzy mnoˇzina, pravdivostn´ı stupeˇn podrobnˇeji popsat struktury pravdivostn´ıch hodnot
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
2 / 23
Neurˇcitost nˇeco nev´ıme pˇresnˇe, urˇcitˇe, u´plnˇe. s neurˇcitost´ı se setk´av´ame v bˇeˇzn´em ˇzivotˇe i ve vˇedˇe existuje nˇekolik typ˚ u neurˇcitosti Pˇr´ıklad: nejistota je d´ana mnoˇzina alternativ, nastat m˚ uˇze jenom jedna. Neurˇcitost je v tom, ˇze nev´ıme kter´a existuj´ı (hod kostkou, ruleta ...) r˚ uzn´e teorie pro zpracov´an´ı neurˇcitosti (pravdˇepodobnost, possibility theory) neurˇcitost se vyskytuje i v situac´ıch, kdy nem´ame dostatek zdroj˚ u (v´ypoˇcetn´ı s´ıla, data, apod) abychom situaci (syst´em, fenom´en) zpracovali pˇresnˇe. Pˇr´ıklad: statistick´e zpracov´an´ı dat. organized simplicity — disorganized complexity spektrum
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
3 / 23
V´agnost typ neurˇcitosti souvisej´ıc´ı s pouˇz´ıv´an´ım pˇrirozen´eho jazyka neostˇre definovan´e pojmy, kter´e pˇresnˇe nevymezuj´ı sv˚ uj v´yznam Think of arm chairs and reading chairs and dining-room chairs, and kitchen chairs, chairs that pass into benches, chairs that cross the boundary and become settees, dentist’s chairs, thrones, opera stalls, seats of all sorts, those miraculous fungoid growths that cumber the floor of arts and crafts exhibitions, and you will perceive what a lax bundle in fact is this simple straightforward term. In cooperation with an intelligent joiner I would undertake to defeat any definition of chair or chairishness that you gave me.
— H. G. Wells (First and Last Things, London, 1908) dalˇs´ı pˇr´ıklady: m´ıt vysok´y tlak, b´yt vysok´y, rychle bˇeˇzet, ˇcerven´a barva z´akon vylouˇcen´eho tˇret´ıho P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
4 / 23
Paradoxy Na paradoxech lze demonstrovat d˚ usledky pouˇzit´ı apar´atu pro pˇresn´e (ostˇre vymezen´e) v´yrazy na v´agn´ı v´yrazy. Pracujeme s v´agn´ım v´yrokem neb´ yt pleˇsat´ y (NP). M˚ uˇzeme pˇredpokl´adat, ˇze 1 Muˇz se 180 000 vlasy nen´ı pleˇsat´y (v´yrok NP(180 000) je pravdiv´y). 2 Pokud muˇzi, kter´y nen´ı pleˇsat´y, vytrhneme jeden vlas, nestane se pleˇsat´ym. (pokud je NP(x) pravdiv´y, pak je NP(x − 1) tak´e pravdiv´y). Sestroj´ıme posloupnost pravdiv´ych tvrzen´ı: NP(180000), NP(179999), NP(179998), . . . , NP(0) Doˇsli jsme k paradoxu: element´arn´ı kroky jsou logicky spr´avnˇe (pˇrepoklady 1 a 2) dojdeme k evidentnˇe nespr´avn´emu z´avˇeru (muˇz bez vlas˚ u nen´ı pleˇsat´y) P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
5 / 23
Fuzzy mnoˇzina zobecˇnuje pojem mnoˇzina = ostˇre vymezen´a kolekce objekt˚ u, crisp mnoˇ zina Pro crisp mnoˇzinu A v universu X (A ⊆ X) je charakteristick´ a funkce zobrazen´ı A : X → {0, 1} definovan´e pro x ∈ X 1 x ∈ A, tj. v´yrok x patˇr´ı do A“ je pravdiv´y A(x) = ” 0 x∈ / A, tj. v´yrok x patˇr´ı do A“ nen´ı pravdiv´y ” Neostˇre vymezenou kolekci objekt˚ u definujeme tak, ˇze umoˇzn´ıme objekt˚ um n´aleˇzet do mnoˇziny ve stupn´ıch, tj. charakteristick´a funkce m´a tvar A : X → L. Pro b ∈ L x patˇr´ı do mnoˇziny A ve stupni b A(x) = b v´yrok x patˇr´ı do A“ je pravdiv´y ve stupni b ” A naz´yv´ame fuzzy mnoˇ zina. L je mnoˇzina pravdivostn´ıch stupˇ n˚ u, ˇcasto vol´ıme [0, 1] P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
6 / 23
Myˇslenku v´ıce pravdivostn´ıch stupˇn˚ u lze snadno pouˇz´ıt i v matematick´e logice, pravdivostn´ı funkci fuzzy mnoˇziny m˚ uˇzeme interpretovat jako predik´ at. Predik´at = funkce, kter´a pˇriˇrazuje objekt˚ um (nebo n-tic´ım objekt˚ u) pravdivostn´ı stupeˇn. Pˇr´ıklady predik´at˚ u: vysok´ y-muˇ z: Muˇzi → L. Pouˇzit´ı: vysok´ y-muˇ z(prof. Bˇelohl´avek) = 1, vysok´ y-muˇ z(dr. Outrata) = 0.5 podobn´ e-barvy: Barvy × Barvy → L. Pouˇzit´ı: podobn´ e-barvy(b´ıl´a, ˇcern´a) = 0, podobn´ e-barvy(azurov´a, modr´a) = 0.8 Predik´aty lze pomoc´ı logick´ych spojek skl´adat do logick´ ych formul´ı: ϕ := Vysoky-muˇz(x) & Vysoky-tlak(x) Formule: muˇz x je vysok´y a m´a vysok´y tlak“. V z´avisloti na tom, koho dopln´ıme za ” x m´a formule nˇejakou pravdivostn´ı hodnotu. (ozn. ||ϕ||) P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
7 / 23
ˇ sen´ı paradox˚ Reˇ u NP(x) m˚ uˇzeme br´at jako charakteristickou funkci crisp mnoˇziny muˇzi, kteˇr´ı nejsou ” pleˇsat´ı“ Pokud je NP fuzzy mnoˇzina s L = [0, 1], pak m˚ uˇzeme paradox vyˇreˇsit n´asledovnˇe: 1 Muˇz se 180000 vlasy nen´ı pleˇsat´y: NP(180000)=1. 2 Pokud vytrneme muˇzi vlas, bude o malinko pleˇsatˇejˇs´ı: pokud NP(x) = a, pak 1 NP(x − 1) = a − 180000 Posloupnost NP(x) pro x = 180000, 179999, . . . , 0: NP(180000)=1, NP(179999)= 179999 , . . . , NP(0) = 0 180000
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
8 / 23
Komparativn´ı s´emantika Kde vezmu hodnoty pravdivostn´ıch stupˇ n˚ u? Z´aleˇz´ı na tom, jestli je byt-vysoky(Franta) = 0.5 nebo byt-vysoky(Franta) = 0.45 ? 1 2
Pravdivostn´ı stupnˇe maj´ı komparativn´ı v´yznam Konkr´etn´ı pravdivostn´ı stupnˇe z´ısk´ame napˇr. od odborn´ık˚ u a mohou b´yt d˚ uleˇzit´e v aplikac´ıch (napˇr. fuzzy regul´atorech)
Pˇri volbˇe pravdivostn´ıch stupˇn˚ u tedy z´aleˇz´ı hlavnˇe na tom, aby spr´avnˇe popisovaly konkr´etn´ı mnoˇzinu (Napˇr. byt-vysoky m´a vyˇsˇs´ı pravdivostn´ı stupeˇn pro nˇekoho, kdo m´a 2m, neˇz pro nˇekoho, kdo m´a 170 cm) V konkr´etn´ıch aplikac´ıch (pˇri zpracov´an´ı fuzzy mnoˇzin), lze pak stupnˇe doladit tak, jak je pro danou aplikace vhodn´e. P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
9 / 23
Mnoˇzina pravdivostn´ıch stupˇn˚ u Pro L existuj´ı rozumn´e poˇzadavky, ze kter´ych vyplyne pˇr´ısluˇsn´a formalizace: 1. Chceme porovn´avat pravdivost r˚ uzn´ych v´yrok˚ u
Definice Uspoˇr´ adan´ a mnoˇ zina je hL, ≤i, kde A je mnoˇzina a pro vˇsechny x, y, z ∈ L plat´ı x ≤ x (reflexivita) x ≤ y a y ≤ x implikuje x = y (antisymetrie) x ≤ y a y ≤ z implikuje x ≤ z (tranzitivita) a
b
c b
d
c P. Osiˇ cka (DAMOL)
a
a Z´ aklady fuzzy logiky 1
b
c
d 20. ˇr´ıjna 2011
10 / 23
Mnoˇzina pravdivostn´ıch stupˇn˚ u ´ a pravda je vˇetˇs´ı neˇz vˇsechny ostatn´ı pravdivostn´ı stupnˇe, u´pln´a nepravda je 2. Upln´ menˇs´ı neˇz vˇsechny pravdivostn´ı stupnˇe
Definice Uspoˇr´adan´a mnoˇzina hL, ≤i je ohraniˇ cen´ a pokud existuj´ı prvky 0, 1 takov´e, ˇze 0 ≤ x pro vˇsechna x ∈ L (0 je nejmenˇs´ı prvek) x ≤ 1 pro vˇsechna x ∈ L (1 je nejvˇetˇs´ı prvek) 1
b
c
0 P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
11 / 23
Mnoˇzina pravdivostn´ıch stupˇn˚ u 3. Kvantifik´atory = symboly pouˇz´ıvan´e ve formul´ıch matematick´e logiky Univers´ aln´ı kvantifik´ ator ∀ — v´yznam pro vˇsechny“: ” ϕ := (∀x) Vysoky-tlak(x) V´yznam: pro vˇsechna moˇzn´a dosazen´ı za x plat´ı, ˇze x m´a vysok´y tlak, tj. vˇsichni ” muˇzi maj´ı vysok´y tlak“ Jak dostaneme pravdivostn´ı hodnotu ϕ? vysok´y-tlak(x) ≥ ||ϕ|| pro vˇsechna dosazen´ı za x chceme, aby ||ϕ|| bylo co nejvˇetˇs´ı moˇzn´e nejvˇetˇs´ı pravdivostn´ı stupeˇn menˇs´ı neˇz vˇsechna vysok´y-tlak(x) pˇrirozenˇe vede na pojem infimum P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
12 / 23
Infimum
Definice Necht’ hL, ≤i je uspoˇr´adan´a mnoˇzina a B ⊆ L. Doln´ı kuˇ zel LL (B) mnoˇziny B vzhledem k A je LL (B) = {a ∈ L | a ≤ b pro vˇsechny b ∈ B}. Pokud m´a LL (B) nejvˇetˇs´ı prvek, naz´yv´ame jej infimem B. Operaci nalezen´ı infima ˇr´ık´ame pr˚ usek, oznaˇcujeme ∧.
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
13 / 23
Mnoˇzina pravdivostn´ıch stupˇn˚ u Existenˇ cn´ı kvantifik´ ator ∀ — v´yznam existuje alespoˇn jeden“: ” ϕ := (∀x) Vysoky-tlak(x) V´yznam: pro vˇsechna moˇzn´a dosazen´ı za x plat´ı, ˇze alespoˇn jedno x m´a vysok´y tlak, tj. existuje muˇz, kter´y m´a vysok´y tlak“ ” Jak dostaneme pravdivostn´ı hodnotu ϕ? vysok´y-tlak(x) ≤ ||ϕ|| pro vˇsechna dosazen´ı za x chceme, aby ||ϕ|| bylo co nejmenˇs´ı moˇzn´e nejmenˇs´ı pravdivostn´ı stupeˇn vˇetˇs´ı neˇz vˇsechna vysok´y-tlak(x) pˇrirozenˇe vede na pojem supremum
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
14 / 23
Supremum
Definice Necht’ hL, ≤i je uspoˇr´adan´a mnoˇzina a B ⊆ L. Horn´ı kuˇ zel UL (B) mnoˇziny B vzhledem k A je UL (B) = {a ∈ L | a ≥ b pro vˇsechny b ∈ B}. Pokud m´a UL (B) nejmenˇs´ı prvek, naz´yv´ame jej supremem B. Operaci nalezen´ı supremem ˇr´ık´ame spojen´ı, oznaˇcujeme ∨.
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
15 / 23
Konjunkce 4. Pravdivostn´ı hodnoty sloˇzen´ych formul´ı se poˇc´ıtaj´ı z pravdivostn´ıch hodnot jej´ıch podformul´ı ϕ := Vysoky-muˇz(x) & Vysoky-tlak(x) Kolik je ||ϕ||, kdyz vysoky-muˇ z(x) = b, a vysoky-tlak(x) = c? Pouˇzijeme pravdivostn´ı funkci, kter´a odpov´ıd´a spojce & — ⊗ : L × L → L. ||ϕ|| nyn´ı spoˇc´ıt´ame jako b ⊗ c.
Definice (Pravdivostn´ı funkce spojky &) Funkci ⊗ povaˇzujeme za pravdivostn´ı funkci spojky &, pokud pro vˇsechna a, b, c ∈ L a⊗b=b⊗a (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c) a⊗1=a P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
16 / 23
Implikace Pravdivostn´ı funkce implikace : → Chceme, aby dobˇre fungovalo pravidlo modus ponens z ϕ a (ϕ ⇒ ψ) odvod’ ψ Poˇzadavky ve v´ıcehodnotov´em prostˇred´ı: 1 ||ϕ|| ⊗ (||ϕ|| → ||ψ||) ≤ ||ψ|| 2 pˇritom ale chceme, aby modus ponens bylo siln´e pravidlo, tj. chceme aby pravdivostn´ı hodnota ||ϕ|| ⊗ (||ϕ|| → ||ψ||) byla maxim´aln´ı moˇzn´a Poˇzadavky vedou na podm´ınku adjunkce: Pro vˇsechna a, b, c ∈ L a ⊗ b ≤ c pr´avˇe kdyˇz a ≤ b → c P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
17 / 23
Residuovan´y svaz Definice (Svaz) ´ y svaz je spoˇr´adan´a mnoˇzina (L, ≤), ve kter´e existuj´ı infima a suprema pro Upln´ vˇsechny podmnoˇziny L.
Definice (Residuovan´y svaz) Residuovan´ y svaz je algebra L = hL, ∧, ∨, 0, 1, ⊗, →i takov´a, ˇze (L, ∧, ∨, 0, 1) je ohraniˇcen´y u´pln´y svaz ⊗ je komutitavn´ı, asociativn´ı a pro vˇsechna a ∈ L plat´ı a ⊗ 1 = 1 a ⊗ b ≤ c pr´avˇe kdyˇz a ≤ b → c
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
18 / 23
Pˇr´ıklady residuovan´ych svaz˚ u ˇ Casto pouˇz´ıvan´ymi residuovan´ymi svazy jsou svazy s nosiˇcem L = [0, 1]. hL, ∧, ∨, 0, 1i tvoˇr´ı u´pln´y svaz, kde a ∧ b = max(a, b) a a ∨ b = min(a, b). Operace multiplikace a residua jsou v nˇem definov´any: a ⊗ b = max(a + b − 1, 0), a → b = min(1 − a + b, 1) (Lukasiewitzova struktura) ( 1 a≤b a ⊗ b = min(a, b), a → b = (G¨odelova struktura) b a>b ( 1 a≤b a ⊗ b = a · b, a → b = (produktov´a struktura) b/a a > b
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
19 / 23
Pˇr´ıklady residuovan´ych svaz˚ u Definice (t-norma) Zobrazen´ı t : [0, 1] × [0, 1] → [0, 1] je t-norma, kdyˇz pro vˇsechna x, y, z ∈ [0, 1] plat´ı: T (x, y) = T (y, x) T (T (x, y), z) = T (x, T (y, z)) x ≤ y implikuje T (x, z) ≤ T (y, z) T (x, 1) = x Lze pouˇz´ı jako ⊗ v residuovan´em svazu, pokud je t-norma zleva spojit´a, tj. lim t(an , b) = t( lim an , b)
n→∞
n→∞
Pak totiˇz existuje unik´atn´ı operace → tak, ˇze (⊗ a →) tvoˇr´ı adjungovan´y p´ar. P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
20 / 23
Z´akladn´ı vlastnosti residuovan´ych svaz˚ u Vˇeta (Z´akladn´ı vlastnosti ⊗, →) V kaˇzd´em residuovan´em svazu L plat´ı pro vˇsechna x, y ∈ L: 1 y1 ≤ y2 implikuje x ⊗ y1 ≤ x ⊗ y2 , 2 x ⊗ (x → y) ≤ y, 3 x → y je nejvˇetˇs´ı prvek {z | x ⊗ z ≤ y} 4 x ≤ y p.k. x → y = 1, 5 x → x = 1, x → 1 = 1, 0 → x = 1, 6 1 → x = x, 7 x ⊗ y ≤ x, 8 x ⊗ 0 = 0,
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
21 / 23
Pr˚ unik a sjednocen´ı fuzzy mnoˇzin Pr˚ unik fuzzy mnoˇ zin A, B ∈ LX je fuzzy mnoˇzina A ∩ B, definovan´a (A ∩ B)(x) = A(x) ∧ B(x). Sjednocen´ı fuzzy mnoˇ zin A, B ∈ LX je fuzzy mnoˇzina A ∪ B (A ∪ B)(x) = A(x) ∨ B(x).
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
22 / 23
Podmnoˇziny Pro fuzzy mnoˇziny A, B ∈ LX je stupeˇ n, ve kter´ em je A podmnoˇ zinou B, definov´an ^ (A(x) → B(x)) S(A, B) = x∈X
Crisp varianta: A ⊆ B pr´avˇe kdyˇz A(x) ≤ B(x) pro vˇsechna x ∈ X Je vidˇet, ˇze A ⊆ B pr´avˇe kdyˇz S(A, B) = 1
P. Osiˇ cka (DAMOL)
Z´ aklady fuzzy logiky 1
20. ˇr´ıjna 2011
23 / 23