Formální fuzzy logika

(1)

Formální fuzzy logika

Libor B¥hounek

Ústav pro výzkum a aplikace fuzzy modelování Ostravské univerzity

& Ústav informatiky AV R

Filosocké problémy informatiky MFF UK, 5. 5. 2015

(2)

Osnova

1 Úvod do formální fuzzy logiky

2 Motivace a aplikace

3 Filosoe vágnosti

4 Formální fuzzy matematika

(3)

Osnova

3 Filosoe vágnosti

(4)

Stupn¥ pravdivosti

Klasická logika je dvojhodnotová má 2 pravdivostní hodnoty:

pravda(1)anepravda (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]

(5)

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 je funkcí 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¬·:

kA→Bk= 1 i kAk ≤ kBk

• Reziduace: kA&Bk ≤ kCk ikAk ≤ kB →Ck

• Poºadavky na vlastnosti jednotlivých spojek

(6)

Poºadavky na konjunkci

Rozumné poºadavky na pravdivostní funkci ∗ konjunkce:

• Komutativita: x∗y=y∗x

• Asociativita: (x∗y)∗z=x∗(y∗z)

• Monotonie: pokudx≤x⁰, pakx∗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é

(7)

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∗_Gy= min(x, y) Gödelova t-norma

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

x∗y= max(x+y−1,0) ukasiewiczovat-norma

(8)

Rezidua spojitých t-norem

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

Vºdy platí: Pokudx≤y, pakx→∗ y= 1.

Rezidua základních t-norem

Pro y < x: x→_Gy =y Gödelova implikace x→_Πy =y/x Goguenova implikace x→y = min(1−x+y,1) ukasiewiczova implikace

(9)

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)≤y Negace: ¬_∗x=x→_∗ 0 (reductio ad absurdum).

Disjunkce: x∨y= max(x, y) (denovatelná z∗,→)

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

(10)

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¥ 1

A₁, . . . , A_n|=B i platí: kdykoliA₁=. . .=A_n= 1, pak B= 1

Základní logiky spojitých t-norem

Gödelova (G),ukasiewiczova() aproduktová(Π) 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é

(11)

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í pravidlomodus ponens: zAaA→B odvo¤B

Axiomy G, , Π:

G=BL+A→(A&A)

=BL+¬¬A→A

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

(12)

Ú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í vev²ech BL-algebrách(obecná úplnost)

• A platí ve v²echlineárníchBL-algebrách(lineární úplnost)

• A platí ve v²echstandardníchBL-algebrách(standardní úplnost)

(13)

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·

(14)

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 = logikazleva 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 prox= 1, 0 jinak)

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

(15)

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

(16)

Prvo°ádové fuzzy logiky

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

Sémantika: ∀,∃ = inmum, supremum (ve svazu pravdivostních stup¬·) Rasiowé axiomy pro kvantikátory (p°idat k výrokovým):

(∀x)ϕ(x)→ϕ(t) prot substituovatelné zax veϕ ϕ(t)→(∃x)ϕ(x) prot substituovatelné zax veϕ (∀x)(χ→ϕ)→(χ→(∀x)ϕ) pokudx není volná vχ

(∀x)(ϕ→χ)→((∃x)ϕ→χ) pokudx není volná vχ a odvozovací pravidlogeneralizace: z ϕodvo¤(∀x)ϕ Voliteln¥(pro zaji²t¥ní lineární úplnosti):

(∀x)(ϕ∨χ)→(∀x)ϕ∨χ pokudx není volná vχ

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

(17)

Osnova

3 Filosoe vágnosti

(18)

Motivace

Fuzzy mnoºiny (Zadeh 1965): charakteristické funkceX →[0,1]

(místoX → {0,1}) Motivovány neost°e vyd¥lenými soubory objekt·

(Zadeh: soubor v²ech reálných £íselo 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, teorie d·kaz·, výpo£tová sloºitost, . . .

(19)

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ºiny

1969 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, . . .

(20)

Osobnosti z historie fuzzy logiky

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

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

(21)

Aplikace

• Fuzzy °ízení: spojité charakteristické funkce poskytují zp¥tnou vazbu Fuzzy IFTHEN pravidla(reprezentovaná fuzzy relacemi):

Pokud teplota je VYSOKÁ, pak ventil má být POOTEVENÝ.

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 IFTHEN pravidel z popisu v p°irozeném jazyce Pouºití: expertní systémy (víde¬ský CADIAG)

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

(22)

Kontroverze

Fuzzy logika má v n¥kterých kruzíchkontroverzní 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

(23)

Osnova

3 Filosoe vágnosti

(24)

Paradox hromady

Paradox hromady (sórités; Eubúlidés z Mílétu, 4. stol. p°. n. l.) 10⁹ zrn písku tvo°í hromadu.

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

Tedy10⁹−1zrn písku tvo°í hromadu.

. . . [Úsudek opakujeme 10⁹×.]

Tedy0 zrn písku tvo°í hromadu.

Analogicky pro ostatní predikáty bez ostré hranice

(holohlavý, mladý, vysoký; zelená; v níºin¥; malé £íslo, . . . )

(25)

Teorie vágnosti

Vágní pojmy = pojmy, k nimº lze sestrojit posloupnost typu sórités

(alespo¬ my²lenou) Filosoe 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; za pravdivé 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)(H_n&¬Hn−1) (existenci zlomu)

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

(26)

Sórités ve fuzzy logice

Opakované pouºití induktivní premisy postupn¥ sniºuje garantovanou pravdivost 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.

kH_nk ≥1∗(1−_N¹)∗^(N. . .^−n)×∗(1− _N¹) = 1−_Nⁿ &0pron→N Induktivní premisa je p°esv¥d£ivá, nebo´ je tém¥° zcela pravdivá (1−_N¹)

(27)

Um¥lá p°esnost a plurivaluace

Nejváºn¥j²í námitka=problém um¥lé p°esnosti: zatímco klasická logika má 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)

(28)

Osnova

3 Filosoe vágnosti

(29)

Formální fuzzy matematika

Formální fuzzy matematika = budování matematiky s fuzzy logikou coby podkladovou 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¥ fuzzikovat)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·

(30)

Základové teorie pro fuzzy logiku

Fuzzy logika vy²²ího °ádu (B¥hounekCintula 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ájekHaniková 2003)

(31)

Cantorukasiewiczova teorie mnoºin

Cantorova naivní teorie mnoºin

Neomezená komprehenze: (∃z)(∀x)(x∈z↔ϕ(x)), pro kaºdou formuliϕ Je sporná(Russell·v paradox): pror={x|x /∈x} jer∈r↔r /∈r Existence r je v²ak splnitelná v ukasiewiczov¥ logice!

kr∈rk= ¹₂ = 1−¹₂ =¬kr∈rk, tedy kr ∈r ↔r /∈rk= 1 Cantorukasiewiczova teorie mnoºin (C)

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

= jediné schéma axiom· C, vukasiewiczov¥ 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)

(32)

Vlastnosti Cantorukasiewiczovy 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} . . . intenzex (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¥tautoreferencí (v¥ta o pevném bod¥)

⇒ p°irozen¥j²í deniceω (p°ir. £íslo je 0nebo 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}

(33)

Fuzzy pojem innitesimálu

Innitesimální kalkul byl aº do 19. století zaloºen na pojmu innitesimálu (intuitivn¥j²í neºε-δ denice) Problém: pojem innitesimálu je logicky sporný

Lze jej v²ak aproximovat: £ím men²í £íslo, tím lep²í innitesimál

(srv. nakládání sdx ve fyzice) Idea:

Fuzzy pojem innitesimálu: £ím men²í £íslo, tím v¥t²í stupe¬

innitesimálnosti (ale ºádné £íslo není innitesimál ve stupni1) Limitu posloupnosti lze v ukasiewiczov¥ logice denovat takto:

x= lim

n→∞xn i (∃n₀)(∀n > n₀)(|x−xn| ∈Inf) Pro limity funkcínutno uvaºovat systémy fuzzy okolí 0

(s tímto up°esn¥ním lze vybudovat celý innitesimální kalkul v )

(34)

Bez£íselná matematika

Pozorování:

Vlastnosti charakteristických funkcíodpovídají (jednodu²²ím) vlastnostem fuzzy mnoºin:

Klasické funkce Fuzzy mnoºiny monotonní funkce horní mnoºina metrika relace ekvivalence lim sup / lim inf hromadný / vnit°ní bod reálná £ísla pravdivostní hodnoty algebraické 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 Π:

¬(v₁&_Πv₂)→_Π(v₁∨v₂) (disjunkce podmín¥ná neslu£itelností)

(35)

Paradox logické v²ev¥doucnosti agent·

Ve standardní epistemické logice jsou agentilogicky v²ev¥doucí

= znají v²echny (výrokové) tautologie(coº je nerealistické), díky axiomulogické 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í)

(36)

Reference

Kam dále pro informace:

• KapitolaFormální fuzzy logika (30 stran) ve sborníku Umelá inteligencia a kognitívna veda I

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

(zdarma na webu, hledejte název)

• KnihaP. HájkaMetamathematics 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)

Formální fuzzy logika