Formální fuzzy logikaktiml.mff.cuni.cz/fpi/data/FPI-Behounek-slides.pdf · Formální fuzzy...

Formální fuzzy logika

Libor B¥hounek

Ústav pro výzkum a aplikace fuzzy modelování Ostravské univerzity& Ústav informatiky AV�R

Filoso�cké problémy informatikyMFF UK, 5. 5. 2015

Libor B¥hounek (OU & AV�R) Formální fuzzy logika 5. 5. 2015 1 / 36

Osnova

1 Úvod do formální fuzzy logiky

2 Motivace a aplikace

3 Filoso�e vágnosti

4 Formální fuzzy matematika


Osnova






Stupn¥ pravdivosti

Klasická logika je dvojhodnotová � má 2 pravdivostní hodnoty:pravda (1) a nepravda (0)

Mnoho vlastností (mladý, vzdálený, rychlý, . . . ) v²ak není �£ernobílých� �� lze je p°ipsat ve v¥t²ím £i men²ím stupni

⇒ Základní my²lenka fuzzy logiky:Roz²í°it 2 klasické pravdivostní hodnoty na ²kálu pravdivostních stup¬·

• i nekone£n¥ mnoha• obvykle lineárn¥ uspo°ádaných• £asto (ale ne vºdy) reprezentovaných £ísly z [0, 1]


Poºadavky na sémantiku výrokových spojek

S roz²í°ením pravdivostních hodnot je t°eba ur£it chování výrokových spojek

P°íli² mnoho moºností ⇒ nutno p°ijmout vhodné omezující principy

Nej£ast¥ji p°ijímané principy:

• Extenzionalita výrokových spojek = pravdivostní stupe¬ výsledku jefunkcí pravdivostních stup¬· argument·

(�truth-functionality� � pravdivostní funkce)

• Svazové £i lineární uspo°ádání pravdivostních stup¬· (dle logické síly)

• Implikace internalizuje uspo°ádání pravdivostních stup¬·:

‖A→ B‖ = 1 i� ‖A‖ ≤ ‖B‖

• Reziduace: ‖A&B‖ ≤ ‖C‖ i� ‖A‖ ≤ ‖B → C‖• Poºadavky na vlastnosti jednotlivých spojek


Poºadavky na konjunkci

Rozumné poºadavky na pravdivostní funkci ∗ konjunkce:• Komutativita: x ∗ y = y ∗ x• Asociativita: (x ∗ y) ∗ z = x ∗ (y ∗ z)• Monotonie: pokud x ≤ x′, pak x ∗ y ≤ x′ ∗ y• Neutralita pravdy: x ∗ 1 = x (d·sledek: x ∗ 0 = 0)

• Spojitost: ∗ je spojitá funkce

Na [0, 1] = spojité t-normy

Dal²í poºadavky (nap°. idempotence: x ∗ x = x) by jiº teorii p°íli²omezovaly, proto budou jen volitelné


Spojité t-normy

Význa£né p°íklady na [0, 1]:

V²echny spojité t-normy jsou ordinální sumy t¥chto t°í základních:

x ∗G y = min(x, y) Gödelova t-norma

x ∗Π y = x · y produktová t-norma

x ∗� y = max(x+ y − 1, 0) �ukasiewiczova t-norma


Rezidua spojitých t-norem

Podmínka reziduace (x ∗ y ≤ z i� x ≤ y →∗ z) jednozna£n¥ ur£ujereziduum →∗ kaºdé spojité t-normy: x→∗ y = sup{z | z ∗ x ≤ y}

Vºdy platí: Pokud x ≤ y, pak x→∗ y = 1.

Rezidua základních t-norem

Pro y < x: x→G y = y Gödelova implikace

x→Π y = y/x Goguenova implikace

x→� y = min(1− x+ y, 1) �ukasiewiczova implikace


Výrokové spojky t-normových fuzzy logik

Spojitá t-norma ur£uje sémantiku v²ech výrokových spojek:Konjunkce . . . spojitá t-norma ∗Implikace . . . její reziduum →∗

= nejv¥t²í funkce spl¬ující fuzzy modus ponens: x ∗ (x→ y) ≤ yNegace: ¬∗ x = x→∗ 0 (reductio ad absurdum).

Disjunkce: x ∨ y = max(x, y) (de�novatelná z ∗,→)

Minimová konjunkce: x ∧ y = min(x, y) (de�novatelná z ∗,→)(tj. ve fuzzy logikách krom¥ Gödelovy máme 2 r·zné konjunkce!)

Ekvivalence = konjunkce obou implikací


Fuzzy logiky spojitých t-norem

Od sémantiky spojek k logice:Syntax = stejná jako v klasické logice

Tautologie = formule vºdy vyhodnocené na stupe¬ 1

Logické vyplývání = p°ená²ení pravdivostního stupn¥ 1A1, . . . , An |= B i� platí: kdykoli A1 = . . . = An = 1, pak B = 1

Základní logiky spojitých t-noremGödelova (G), �ukasiewiczova (�) a produktová (Π) fuzzy logika

= logiky t¥chto t-norem

Hájkova fuzzy logika BL (�basic logic�)= tautologie a vyplývání ve v²ech logikách spojitých t-norem

Tautologie t¥chto logik jsou kone£n¥ axiomatizovatelné


Axiomatizace fuzzy logik spojitých t-norem

Axiomy logiky BL

((A→ B)→ ((B → C)→ (A→ C)))

(A& (A→ B))→ (B & (B → A))

(A→ (B → C))→ ((A&B)→ C)

((A&B)→ C)→ (A→ (B → C))

((A→ B)→ C)→ (((B → A)→ C)→ C)

0→ A

a odvozovací pravidlo modus ponens: z A a A→ B odvo¤ B

Axiomy G, �, Π:

G = BL +A→ (A&A)

� = BL + ¬¬A→ A

Π = BL + ¬A ∨ ((A→ (A&B))→ B)

Bool = BL +A ∨ ¬A


Úplnost

Trojí sémantika fuzzy logik

• Standardní sémantika = spojité t-normy na [0, 1]

• Obecná sémantika = v²echny algebry spl¬ující uvedenou axiomatiku:BL-algebry, Gödelovy algebry, Π-algebry, MV-algebry

(nemusejí být lineární � nap°. direktní produkty spl¬ují tytéº formule)

• Lineární sémantika = v²echny lineární algebry pro danou fuzzy logiku

V¥ta o úplnosti BL (pro ostatní fuzzy logiky obdobn¥)

Následující podmínky jsou ekvivalentní:

• A je dokazatelná v BL• A platí ve v²ech BL-algebrách (obecná úplnost)• A platí ve v²ech lineárních BL-algebrách (lineární úplnost)• A platí ve v²ech standardních BL-algebrách (standardní úplnost)


Fuzzy logiky mezi neklasickými logikami

Gödelova logika = intuicionistická + (A→ B) ∨ (B → A)= logika lineárních Heytingových algeber

Fuzzy logiky = substrukturální logiky s axiomem prelinearity= logiky lineárních reziduovaných svaz·


�ir²í rodina výrokových fuzzy logik

Studované variace fuzzy logik:

Odebrání n¥kterých podmínek, nap°.:

psBL = bez vyºadování komutativity &

MTL = logika zleva spojitých t-norem

P°idání dodate£ných podmínek, nap°.:

IMTL = MTL + involutivnost negace (¬¬A→ A)

P°idání dodate£ných spojek, nap°.:

Logiky se spojkou ∆ (lineární sémantika: ∆x =

{1 pro x = 1,

0 jinak)

�Π = obsahuje v²echny spojky logik G, � a Π najednou


Zoo hlavních fuzzy logik studovaných od roku 1998


Prvo°ádové fuzzy logiky

Syntax: jako v klasické logice (jen více spojek)

Sémantika: ∀, ∃ = in�mum, supremum (ve svazu pravdivostních stup¬·)

Rasiowé axiomy pro kvanti�kátory (p°idat k výrokovým):

(∀x)ϕ(x)→ ϕ(t) pro t substituovatelné za x ve ϕϕ(t)→ (∃x)ϕ(x) pro t substituovatelné za x ve ϕ(∀x)(χ→ ϕ)→ (χ→ (∀x)ϕ) pokud x není volná v χ(∀x)(ϕ→ χ)→ ((∃x)ϕ→ χ) pokud x není volná v χ

a odvozovací pravidlo generalizace: z ϕ odvo¤ (∀x)ϕ

Voliteln¥ (pro zaji²t¥ní lineární úplnosti):(∀x)(ϕ ∨ χ)→ (∀x)ϕ ∨ χ pokud x není volná v χ

⇒ Prvo°ádové fuzzy logiky BL∀, G∀, �∀, Π∀, . . .


Osnova






Motivace

Fuzzy mnoºiny (Zadeh 1965): charakteristické funkce X → [0, 1](místo X → {0, 1})

Motivovány neost°e vyd¥lenými soubory objekt·(Zadeh: �soubor v²ech reálných £ísel o hodn¥ v¥t²ích neº 1,

v²ech krásných ºen £i v²ech vysokých lidí�)

Fuzzy logika (Goguen 1969): logické operátory (∧,∨,¬, . . . ) odpovídajícífuzzy-mnoºinovým operacím (∩,∪,r, . . . )

Matematická (symbolická, formální) fuzzy logika = aplikace(meta)matematických metod formální (matematické) logiky na fuzzy logiku

Témata matematické fuzzy logiky: axiomatizace, sémantika, úplnost, teoried·kaz·, výpo£tová sloºitost, . . .


Historie a sou£asnost

1920 �ukasiewiczova logika (trojhodnotová, 1930 nekone£n¥hodnotová)1932 Gödelova logika (implicitn¥, k d·kazu netabularity intuicionistické)1965 Zadeh: fuzzy mnoºiny1969 Goguen: fuzzy logika (sémanticky)1975 fuzzy °ízení (první cementová pec)1998 Hájek: Metamathematics of Fuzzy Logic (BL)2011 Handbook of Mathematical Fuzzy Logic

MFL ve sv¥t¥: �esko, Itálie, Rakousko, Japonsko, . . . (∼100 logik·)

�eská ²kola matematické fuzzy logiky:• Pultr, Pavelka (1978), Novák (1986, 1999), Hájek (1998), . . .• Ústav informatiky AV, Ostravská univerzita, UP Olomouc, �VUT,

ÚTIA AV, . . .


Osobnosti z historie fuzzy logiky

Jan �ukasiewicz, Kurt Gödel, Lot� Zadeh, Petr Hájek

(Zdroj: Wikipedia, College Publications, ÚI AV �R, MathFuzzLog)


Aplikace

• Fuzzy °ízení: spojité charakteristické funkce poskytují zp¥tnou vazbu

Fuzzy IF�THEN pravidla (reprezentovaná fuzzy relacemi):

Pokud teplota je VYSOKÁ, pak ventil má být POOTEV�ENÝ.Pokud rychlost je VELKÁ a p°ekáºka je BLÍZKO,

pak brzd¥ní má být SILNÉ.

Pouºití: automatické pece, semafory, pra£ky, fotoaparáty, stavidla, . . .

• Reprezentace znalostí: neostré a p°ibliºné atributy

Pokud barva je �ERVENÁ, pak jablko je ZRALÉ.Pokud tlak je VYSOKÝ, pak objem je MALÝ.

Extrakce fuzzy IF�THEN pravidel z popisu v p°irozeném jazycePouºití: expertní systémy (víde¬ský CADIAG)

• Dal²í aplikace: lingvistické modelování (evalua£ní výrazy, vágníkvanti�kace), rozpoznávání obraz·, data mining (fuzzy GUHA),p°edvídání £asových °ad, fuzzy logické programování, . . .


Kontroverze

Fuzzy logika má v n¥kterých kruzích kontroverzní pov¥st(zvl. mezi matematiky, pravd¥podobnostníky, �losofy a lingvisty)

Námitky se ale týkají

• bu¤ jen aplikovaných fuzzy metod(slabá matematická kvalita, míchání s pravd¥podobností),

• nebo zastaralého stavu oboru (námitky od lingvist· a �losof·),

• nebo o£ekávání nenabízeného (intenzionálních spojek apod.)

V jiných oborech má pov¥st celkem dobrou(inºený°i, informatici, logici, ekonomové)

Neformální význam stup¬· pravdivosti nicmén¥ není dosud vyjasn¥n


Osnova






Paradox hromady

Paradox hromady (�sórités�; Eubúlidés z Mílétu, 4. stol. p°. n. l.)

109 zrn písku tvo°í hromadu.

Odebráním 1 zrnka písku hromada nep°estane být hromadou.

Tedy 109 − 1 zrn písku tvo°í hromadu.

. . . [Úsudek opakujeme 109×.]Tedy 0 zrn písku tvo°í hromadu.

Analogicky pro ostatní predikáty bez ostré hranice(holohlavý, mladý, vysoký; zelená; v níºin¥; malé £íslo, . . . )


Teorie vágnosti

Vágní pojmy = pojmy, k nimº lze sestrojit posloupnost typu sórités(alespo¬ my²lenou)

Filoso�e vágnosti = snaha o uspokojivé °e²ení paradoxu hromady(trápí �losofy od starov¥ku dodnes � znejis´uje správnost usuzování)

Hlavní teorie vágnosti• Epistemická teorie vágnosti: �Je tam ostrý zlom, jen my nevíme kde�

• Supervaluacionismus: �Uvaºujeme v²echny moºné pozice zlomu; zapravdivé povaºujeme jen to, co platí pro v²echny moºné pozice zlomu�

• Stupn¥ pravdivosti = de facto °e²ení pomocí fuzzy logiky

Nevýhody epistemické teorie a supervaluacionismu:

• Validují (∃n)(Hn & ¬Hn−1) (existenci zlomu)

• Nevysv¥tlují, pro£ je induktivní premisa paradoxu p°esv¥d£ivá


Sórités ve fuzzy logice

Opakované pouºití induktivní premisy postupn¥ sniºuje garantovanoupravdivost záv¥ru:

HN & (HN → HN−1) & (HN−1 → HN−2) & . . .& (Hn+1 → Hn)→ Hn

Ve standardní �ukasiewiczov¥ logice: x ∗� y = max(x+ y − 1, 0)0,999 ∗� 0,999 = 0,998 0,999 ∗� 0,999 ∗� 0,999 = 0,997 atd.

‖Hn‖ ≥ 1 ∗� (1− 1N ) ∗� (N−n)×. . . ∗� (1− 1

N ) = 1− nN ↘ 0 pro n→ N

Induktivní premisa je p°esv¥d£ivá, nebo´ je tém¥° zcela pravdivá (1− 1N )


Um¥lá p°esnost a plurivaluace

Nejváºn¥j²í námitka = problém um¥lé p°esnosti: zatímco klasická logikamá 1 um¥lý zlom, ve fuzzy logice je N nesmysln¥ p°esných hodnot

(495 123 344 zrn tvo°í hromadu ve stupni 0,504876656)

�e²ení = fuzzy supervaluace: neuvaºujeme jeden, nýbrº v²echny p°ípustnéfuzzy modely; za pravdivé povaºujeme jen to, co platí ve v²ech z nich.

• P°esn¥ odpovídá pojmu d·sledku ve fuzzy logice• Lze zd·vodnit neur£itostí jazyka (fakt· ur£ujících význam slov)• Vztahuje se i na spojky (BL = �pro v²echny p°ípustné konjunkce�)

Ostatní námitky jsou dány neznalostí moderní fuzzy logiky:• P°ítomnosti dvou konjunkcí ve fuzzy logice

(�neplatí zákon sporu! neplatí modus ponens!� � platí s &)• Existence nelineárních algeber pravdivostních stup¬·

(�nelze porovnávat £ervenost s kulatostí!� � v nelineárních nemusíme)


Osnova






Formální fuzzy matematika

Formální fuzzy matematika = budování matematiky s fuzzy logikou cobypodkladovou logikou pouºívanou k odvozování (namísto klasické logiky)

• Automaticky p°ipou²tí fuzzy modely⇒ v²echna tvrzení a pojmy jsou defaultn¥ fuzzy

• Fuzzy obdoba ostatních odv¥tví neklasické matematiky(intuicionistické, konstruktivní atp.)

Cíle formální fuzzy matematiky• Formalizovat (a pln¥ fuzzi�kovat) inºenýrskou teorii fuzzy mnoºin

• Najít základovou teorii, v níº lze budovat ve²kerou fuzzy matematiku

• Vyuºít zvlá²tností fuzzy logiky pro alternativní budování a zkoumáníklasických pojm·


Základové teorie pro fuzzy logiku

Fuzzy logika vy²²ího °ádu (B¥hounek�Cintula 2005)

Logika: libovolná prvo°ádová t-normová fuzzy logika (s ∆ a =), jazyk:• Prom¥nné pro prvky, fuzzy mnoºiny, fuzzy mnoºiny fuzzy mnoºin atd.• Fuzzy predikáty ∈ pro náleºení mezi sousedními °ády

Axiomy (pro v²echny °ády):• Extenzionalita: (∀x)∆(x ∈ A↔ x ∈ B)→ A = B• Komprehenze: (∃A)(∀x)∆(x ∈ A↔ ϕ(x)) pro kaºdou formuli ϕ

• Formalizace Zadehova pojmu fuzzy mnoºiny = modely teorie• Základová teorie pro fuzzy matematiku

(pouºita k budování teorie fuzzy relací, fuzzy topologie, . . . )• Práce v ní je podobná klasické £i intuicionistické matematice

Podobné základové teorie:• Fuzzy teorie typ· (Novák 2004) � churchovská (formule = λ-termy)• Fuzzy teorie mnoºin ve stylu ZF (Hájek�Haniková 2003)


Cantor��ukasiewiczova teorie mnoºin

Cantorova naivní teorie mnoºinNeomezená komprehenze: (∃z)(∀x)(x ∈ z ↔ ϕ(x)), pro kaºdou formuli ϕ

Je sporná (Russell·v paradox): pro r = {x | x /∈ x} je r ∈ r ↔ r /∈ r

Existence r je v²ak splnitelná v �ukasiewiczov¥ logice!

‖r ∈ r‖ = 12 = 1− 1

2 = ¬� ‖r ∈ r‖ , tedy ‖r ∈ r ↔ r /∈ r‖ = 1

Cantor��ukasiewiczova teorie mnoºin (C�)

Neomezená komprehenze: (∃z)(∀x)(x ∈ z ↔ ϕ(x)), pro kaºdou formuli ϕ

= jediné schéma axiom· C�, v �ukasiewiczov¥ logice

Domn¥nka (Skolem 1959):• C� je bezesporná (dodnes nejasné; platí ve slab²ích logikách)• V C� lze vybudovat podstatnou £ást matematiky (nejspí² ne,

nicmén¥ jde o zajímavou teorii)


Vlastnosti Cantor��ukasiewiczovy teorie mnoºin

• C� je neextenzionální teorie mnoºin• P°idání extenzionality je sporné• Existuje nap°. nekone£n¥ mnoho prázdných mnoºin (Hájek 2013)

• {u | u ∈ x} . . . extenze x (mnoºina v²ech prvk· x){u | x ∈ u} . . . intenze x (mnoºina v²ech vlastností x � v ZF t°ída)Rovnost = (ne koextenzionalita jako v ZF, ale) kointenzionalita

(Leibniz·v princip)• Mnoºiny lze zavád¥t autoreferencí (v¥ta o pevném bod¥)

⇒ p°irozen¥j²í de�nice ω (p°ir. £íslo je 0 nebo následník p°ir. £ísla):

ω = {n | n = 0 ∨ (∃m ∈ ω)(n = m+ 1)}ω nutn¥ obsahuje (nekone£ná) nestandardní £ísla (Yatabe 2007)

• Existence zvlá²tních mnoºin:• univerzální mnoºina v = {x | x = x}• Russellova mnoºina r = {x | x /∈ x}• mnoºina svých vlastních vlastností: x = {u | x ∈ u}


Fuzzy pojem in�nitesimálu

In�nitesimální kalkul byl aº do 19. století zaloºen na pojmu in�nitesimálu(intuitivn¥j²í neº ε-δ de�nice)

Problém: pojem in�nitesimálu je logicky sporný

Lze jej v²ak aproximovat: £ím men²í £íslo, tím lep²í in�nitesimál(srv. nakládání s dx ve fyzice)

Idea:Fuzzy pojem in�nitesimálu: £ím men²í £íslo, tím v¥t²í stupe¬

in�nitesimálnosti (ale ºádné £íslo není in�nitesimál ve stupni 1)

Limitu posloupnosti lze v �ukasiewiczov¥ logice de�novat takto:

x = limn→∞

xn i� (∃n0)(∀n > n0)(|x− xn| ∈ Inf)

Pro limity funkcí nutno uvaºovat systémy fuzzy okolí 0(s tímto up°esn¥ním lze vybudovat celý in�nitesimální kalkul v �)


Bez£íselná matematika

Pozorování:Vlastnosti charakteristických funkcí odpovídají (jednodu²²ím) vlastnostemfuzzy mnoºin:

Klasické funkce Fuzzy mnoºinymonotonní funkce horní mnoºinametrika relace ekvivalencelim sup / lim inf hromadný / vnit°ní bodreálná £ísla pravdivostní hodnotyalgebraické operace výrokové spojky

Ve fuzzy logice lze £ísla �schovat� do sémantiky a nereferovat k nim v teorii= budovat matematiku (a fyziku) bez £ísel

Relativistické skládání rychlostí (s T = ict) v �Π:

¬�(v1 &Π v2)→Π (v1 ∨� v2) (disjunkce podmín¥ná neslu£itelností)


Paradox logické v²ev¥doucnosti agent·

Ve standardní epistemické logice jsou agenti logicky v²ev¥doucí= znají v²echny (výrokové) tautologie (coº je nerealistické),

díky axiomu logické racionality: Kϕ& K(ϕ→ ψ)→ Kψ

�e²ení:Fuzzy pojem proveditelné znalosti

Axiom logické racionality v �ukasiewiczov¥ logice:

Kϕ& K(ϕ→ ψ) & mp→ Kψ

P°i dlouhých odvozeních proveditelnost klesá, jako u paradoxu hromady(paradox logické v²ev¥doucnosti je vlastn¥ jeho instancí)


Reference

Kam dále pro informace:• Kapitola �Formální fuzzy logika� (30 stran) ve sborníku Umelá

inteligencia a kognitívna veda I

• Úvodní kapitola (100 stran) Introduction to mathematical fuzzy logicknihy Handbook of Mathematical Fuzzy Logic

(zdarma na webu, hledejte název)

• Kniha P. Hájka Metamathematics of fuzzy logic (v knihovnách)

• Mnoho zdroj· voln¥ na webu (nap°. MathFuzzLog.org)

• Semestrální kurz matematické fuzzy logiky na FF UK(Cintula, Noguera � anglicky, koná se na Ústavu informatiky v Ládví)

• Seminá°e pro pokro£ilé: ÚI AV (st 14:00), ÚVAFM v Ostrav¥ (£t 9:30)


Date post:	25-Jul-2020
Category:	Documents
Upload:	others
View:	2 times
Download:	0 times

Formální fuzzy logikaktiml.mff.cuni.cz/fpi/data/FPI-Behounek-slides.pdf · Formální fuzzy...

Documents