MOŻLIWE ŚWIATY; WPROWADZENIE DO LOGIK MODALNYCH Wykład w semestrze zimowym 2004/2005 dla studentów filozofii (wykłady 3-11) Andrzej Indrzejczak Spis treści 1. Różne pojęcia modalności 2. Historia rozważań nad modalnościami w fi- lozofii i logice 3. S5 - semantyka i aksjomatyzacja 4. Klasyfikacja logik modalnych; ogólne poję- cie semantyki relacyjnej 5. Ważniejsze logiki normalne 6. Logiki multimodalne 7. Dowód pełności 8. Dedukcja naturalna i etykietowane systemy tableaux 9. Logiki okresów warunkowych 10. Logiki hybrydowe 11. Semantyka topologiczna dla słabych logik modalnych 12. Problemy logik modalnych 1-go rzędu sztywna denotacja, aktualizm a possybi- lizm 13. Logiki wolne i ich zastosowanie w logice modalnej 14. Identyczność i deskrypcje określone Logika S5: Semantyka Definicja 1 (Modele S5) Modelem S5 jest dowolna para M = W, V , gdzie: " dziedzina modelu to W = ", który jest zbio-
rem punktów (światów możliwych); " V jest funkcją ewaluacji (wartościowania) dla zmiennych w punktach dziedziny, tj. V : ZZ - P(W) (ZZ to zbiór zmiennych zdaniowych a P(W) to zbiór potęgowy na W) Zbiór wszystkich modeli S5 oznaczać będzie- my symbolem MOD(S5). Dziedzinę danego modelu M będziemy ozna- czać przez WM. Definicję spełniania formuły w punkcie w mo- delu M ( M, w ) wyrażają poniższe warunki: M, w wtw w " V () dla dowolnej " ZZ M, w Ź wtw M, w M, w '" wtw M, w i M, w M, w (" wtw M, w lub M, w M, w wtw M, w lub M, w M, w wtw M, w dla dowolnego w " WM M, w f& wtw M, w dla pewnego w " WM Dla zbiorów formuł zapis M, w oznacza, że M, w dla "". M, w oznacza fałszywość formuły w w; M, w oznacza fałszywość co najmniej jed- nego elementu w w. W przypadku gdy model jest ustalony, bądz do- myślny będziemy po prostu pisać w (względ- nie w ) lub w (względnie w ) dla zbioru. Zbiór wszystkich punktów spełniających daną formułę (zbiór) oznaczamy: M = {w " WM : w };
M = M dla "" Zazwyczaj używać będziemy notacji skróconej ( ) przy M domyślnym lub ustalonym. będziemy czytać dla wygody zwyczajowo jako "sąd " (intensja ) w danym M. Przykład 1: Niech M = {w1, w2, w3}, V (p) = {w1, w3}, V (q) = {w2, w3} . . . , to: " w1 p (" q " w2 p (" f&q " w2 p (" q " w1 (p (" q) " w1 (p '" q) " w1 f&(p '" q) " w1 (q (f&p (" f&q)) c.d. przykładu 1: (ten sam model M = {w1, w2, w3}, V (p) = {w1, w3}, V (q) = {w2, w3} . . . ) " f&p = W " p = " " p (" q = {w1, w3} " p q = {w2} " {p (" q, p '" q} = p (" q )" p '" q = {w3} " {p (" q, p q} = " Definicja 2 (Spełnialność, falsyfikowalność) () jest spełnialna w modelu M wtw, =
" ( = ").
() jest spełnialna wtw, istnieje model, w którym jest spełnialna. () jest sfalsyfikowana w modelu M wtw, =
WM ( = WM) (inaczej: M falsyfikuje ()).
() jest sfalsyfikowana wtw, istnieje model, w którym jest sfalsyfikowana. Przykład 2: f&p '" (p f&Źp) jest spełnialne. Definicja spełniania formuły (czy zbioru for- muł) w modelu daje nam lokalną charaktery- stykę prawdziwości. Dalszym krokiem jest wpro- wadzenie pojęcia globalnej prawdziwości: Definicja 3 (Prawdziwość w modelu) M wtw, "w"WM, M, w (lub M = WM); analogicznie dla , M wtw, M = WM. Zawartością modelu M nazywamy zbiór E(M) = { : M }. Zbiór wszystkich modeli, w których () jest globalnie prawdziwa, to Mod() = {M : M } (Mod() = {M : M }) Trzeci poziom prawdziwości to tautologiczność, czyli prawdziwość w każdym modelu. Definicja 4 (Prawdziwość w każdym modelu) |= wtw, "M"MOD(S5), M (inaczej: |= wtw, MOD(S5) ą" Mod()). |= oznacza formułę nietautologiczną, czyli falsyfikowalną. Przykład 3: |= |= f& "! Ź Ź f& f& f& f&
f& f& f& f& ( ) ( ) ! ( ) (f& f&) ! (f& ) ( ) ! (" ( (" ) ! f&( '" ) f& '" f& ! ( '" ) "! '" f&( (" ) "! f& (" f& "! f& "! f&f& "! f& f& "! f& Definicja 5 (Wynikanie lokalne i globalne) 1. wynika lokalnie z : |= wtw, "M"MOD(S5)( M ą" M) (inaczej: "M"MOD(S5), "w"WM(jeżeli M, w , to M, w )) 2. wynika globalnie z : ||= wtw, Mod() ą" Mod() (inaczej: "M"MOD(S5)(jeżeli M , to M )) Twierdzenie 1 Jeżeli |= , to ||= , ale nie odwrotnie. Przykład 4: ||= , ale |= . Logika S5: Ujęcie aksjomatyczne A. Schematy aksjomatów: " Dowolne , które jest schematem tezy KRZ " (Dual) f& "! Ź Ź " (K) ( ) ( ) " (T) " (4) " (B) f& f& B. Reguły pierwotne: " (MP) jeżeli " S5 i " S5, to " S5 " (RG) jeżeli " S5, to " S5 Definicja 6 (dowód, teza) Dowodem formu- ły jest skończony ciąg, którego dowolny ele- ment, to aksjomat lub formuła wydedukowana z wcześniejszych elementów za pomocą reguł pierwotnych, a ostatni element ciągu to . jest tezą S5 ( ) wtw, ma dowód. Twierdzenie 2 (Przystosowanie, pełność, adekwatność (słaba)) (a) Jeżeli , to |= . (b) Jeżeli |= , to . (c) |= wtw, . Definicja 7 (Dowiedlność lokalna i globalna) 1. wtw '" , dla pewnego skończonego ą" 2. wtw istnieje dowód z na gruncie S5 jest relacją mocniejszą od , gdyż dla nie zachodzi twierdzenie o dedukcji, które w przy- padku jest spełnione z definicji. Dla przykła- du, mamy p p (z racji domknięcia na (RG)), ale p p (bo p p). Natomiast zachodzi zależność jednostronna: Jeżeli , to Twierdzenie 3 (Adekwatność mocna) 1. wtw, |= 2. wtw, ||= Podział logik modalnych Uwaga: Logiki są tu rozumiane jako zbiory for- muł domknięte na pewne operacje (reguły). Definicja 8 (Logika modalna) Przez logikę modalną L rozumiemy dowolny zbiór formuł w pewnym języku modalnym J, który spełnia następujące warunki: " TAUT ą" L, gdzie TAUT to zbiór tautologii KRZ " jeżeli " L, to e() " L, gdzie e to dowolny endomorfizm z ZZ w F OR(J) " jeżeli " L i " L, to " L Uwaga: Dla uproszczenia rozważań, ograniczy- my się do języka monomodalnego z jednym funktorem konieczności (J ) (zakładamy, że f& jest wprowadzana przez definicję). Rozważmy następujące reguły: (RE) jeżeli "! " L, to "! " L (RM) jeżeli " L , to " L (RR) jeżeli '" " L , to '" " L, gdzie = "
(RG) jeżeli " L , to " L Definicja 9 (Klasy logik modalnych) Dowolna logika modalna L domknięta na (RE) to logika kongruencyjna (klasyczna modalna), domknię- ta na (RM) to logika monotoniczna, domknię- ta na (RR), to logika regularna, wreszcie do- mknięta na (RR) i (RG) to logika normalna. Lemat 1 (Relacje między logikami) (a) Każda logika normalna jest zarazem regu- larna; (b) Każda logika regularna jest zarazem monotoniczna ((RM) jest szczególnym przypadkiem (RR)); (c) Każda logika monotoniczna jest logiką kongruencyjną. Definicja 10 (Bazowe logiki modalne) Niech E oznacza najsłabszą logikę kongruencyjną, M monotoniczną, R regularną, a K normal- ną. Definicja dowodu, tezy i dedukowalności bez zmian; L ( L ) oznacza, że jest tezą L (jest dedukowalne z w L). Monomodalne logiki normalne: semantyka relacyjna Definicja 11 (Struktura relacyjna) Strukturą relacyjną, albo ramą (frame) jest do- wolna para F = W, R gdzie: " dziedzina to W = ", który jest zbiorem
punktów (światów możliwych); " R to binarna relacja na W, zwana relacją osiągalności. W logikach modalnych aletycznych Rww ozna- cza, że w jest osiągalne z w (możliwe ze wzglę- du na w). R(w) = {w : Rww } to zbiór dostępnych dla w możliwości. Definicja 12 (Model na strukturze) Modelem na danej strukturze F jest dowolny układ M = F, V , gdzie V jest funkcją ewaluacji dla zmiennych, tj. V : ZZ - P(W). Zbiór wszystkich modeli na danej strukturze oznaczać będziemy symbolem MOD(F). Zbiór wszystkich modeli relacyjnych (na dowolnej strukturze) oznaczać będziemy symbolem MOD. Definicję spełniania formuły w punkcie w mo- delu M ( M, w ) wyrażają poniższe warunki: M, w wtw w " V () dla dowolnej " ZZ M, w Ź wtw M, w M, w '" wtw M, w i M, w M, w (" wtw M, w lub M, w M, w wtw M, w lub M, w M, w wtw M, w dla dowolnego w " R(w) M, w f& wtw M, w dla pewnego w " R(w) Uwaga: definicje spełniania, falsyfikowania, prawdziwości w modelu (we wszystkich mode- lach) i wynikania pozostają bez zmian. Przykład 1: Rozważmy strukturę F = W, R gdzie: W = {w1, w2, w3, w4}, a R = { w1, w2 , w1, w3 , w2, w2 , w3, w4 , w4, w3 }. Niech M1 = F, V1 , gdzie V1(p) = {w2, w3}, V1(q) = {w1, w4}, a M2 = F, V2 , gdzie V2(p) = ", V2(q) = {w1, w3, w4}. " M1, w1 p M2, w1 p " M2, w1 f&q M1, w1 f& q " M1, w3 p M1, w1 p p " M1, w2 p p M1, w2 f&p p " M2, w1 f& nq, dla dowolnego n > 0 Zachodzi następujące: Twierdzenie 1 (Adekwatność K) K wtw, |= Lemat 2 (K-tautologie) Następujące schematy generują formuły prawdziwe we wszystkich modelach: f& "! Ź Ź ( ) ( ) ( ) (f& f&) (" ( (" ) f&( '" ) f& '" f& ( '" ) "! '" f&( (" ) "! f& (" f& Lemat 3 (formuły falsyfikowalne) Następujące schematy nie są schematami K- tautologii: (D) f& (T) (T ) f& (4) (5) f& f& (B) f& Aby scharakteryzować semantycznie inne logiki normalne musimy wprowadzić dodatkową terminologię: Definicja 13 (Prawdziwość w strukturach) 1. F wtw, "M"MOD(F), M (inaczej: MOD(F) ą" Mod()). 2. Niech F oznacza dowolną klasę struktur, wtedy: F wtw, "F"F, F . 3. Zawartością struktury F nazywamy zbiór E(F) = { : F }. 4. Zawartością klasy struktur F nazywamy zbiór E(F) = { : F }. Twierdzenie 4 Zawartość dowolnej F (F) jest logiką normalną. Ponieważ nośnik danej struktury (charakter je- go elementów i liczność) nie ma wpływu na określenie danej logiki, natomiast strukturalne własności relacji osiągalności mają wpływ za- sadniczy, więc będziemy mówić o klasach struk- tur jednolitych pod względem własności relacji osiągalności. Oto najważniejsze z nich: nazwa warunek serialność "x"yRxy zwrotność "xRxx przechodniość "xyz(Rxy '" Ryz Rxz) symetria "xy(Rxy Ryx) euklidesowość "xyz(Rxy '" Rxz Ryz) Struktury i klasy struktur (a także modele na nich ufundowane) będziemy określać według własności, które posiadają ich relacje osiągal- ności. Np. powiemy, że F (F, M) jest klasą (strukturą, modelem) zwrotną, gdy każda struk- tura F " F jest strukturą zwrotną. Twierdzenie 5 Zachodzą następujące równoważności dla for- muł (D), (T), (4), (5) i (B): F f& wtw, F jest serialna F wtw, F jest zwrotna F wtw, F jest przechodnia F f& f& wtw, F jest euklidesowa F f& wtw, F jest symetryczna. Monomodalne logiki normalne: ujęcie aksjomatyczne K standardowo jest charakteryzowane nastę- pująco: Schematy aksjomatów i reguł pierwotnych: " Dowolne , które jest schematem tezy KRZ " (Dual) f& "! Ź Ź " (K) ( ) ( ) " (MP) jeżeli " K i " K, to " K " (RG) jeżeli " K, to " K nazwa aksjomat (D) f& (D ) ( f&) (DC) f& (T) (T ) ( ) (TC) (4) (4 ) ( ) (4C) (B) f& (B ) ( f&) (5) f& f& (2) f& f& (M) f& f& (3) ( ) (" ( ) (L) ( '" ) (" ( '" ) (F) ( ) (" (f& ) (R) f& ( ) (G) ( ) ) (Grz) ( ( ) ) (Go) ( ( ) ) Zasadniczo będziemy stosować konwencję Lemmona w nazywaniu logik: jeżeli dana lo- gika jest zbudowana przez dodanie do K ak- sjomatów (X), (Y), (Z), to jej nazwę zapisu- jemy KXYZ, z ewentualnym użyciem kropek jako znaków przestankowych (zwłaszcza, gdy nazwa aksjomatu to liczba naturalna). W od- niesieniu do kilku logik zrobimy jednak wyjątek od tej konwencji, ze względu na rozpowszech- nione użycie innych nazw; w szczególności: D=KD T=KT B=KTB S4=KT4 S5=KT5 Szczególnie znaną grupę logik normalnych sta- nowi zbiór logik aksjomatyzowalnych za pomo- cą pięciu formuł z listy: (D), (T), (B), (4) i (5). Chociaż możliwych kombinacji w połączeniu z K jest tu 32 (=25), to różnych logik jest tyl- ko 15, gdyż część kombinacji daje tylko różne aksjomatyzacje tej samej logiki, ze względu na wzajemną dedukowalność niektórych formuł. Podstawę redukcji podaje poniższy Lemat 1 W klasie logik normalnych zachodzą następujące zależności: (D) jest tezą T (5) jest tezą KB4 (4) jest tezą KB5 (4) jest tezą S5 (T) jest tezą KDB4 (B) jest tezą S5 Przykładowo S5=KT45=KTB4=KT5 Adekwatność względem klas struktur Ogólna postać twierdzenia o przystosowaniu logiki L względem klasy struktur F mówi, że: Twierdzenie 1 (Przystosowanie) Jeżeli L , to |=F . Twierdzenie o pełności logiki L względem klasy struktur F mówi, że: Twierdzenie 2 (Pełność) Jeżeli |=F , to L . Oba twierdzenia dają nam twierdzenie o słabej adekwatności L względem klasy F: L=E(F). Mówimy wtedy, że F determinuje, albo charakteryzuje L. F jest wtedy określane ja- ko klasa L-struktur, a każdy model należący do MOD(F), to L-model. Powiemy też, że () jest L-spełnialny (lub L-falsyfikowalny) wtw, jest spełnialny (falsyfikowalny) w jakimś L-modelu. Definicja 14 (Tautologiczność i wynikanie w klasach struktur) Niech F determinuje L, wtedy: 1. |=L wtw, |=F . 2. |=L wtw, "M"MOD(F), "w"WM (jeżeli M, w , to M, w ) 3. ||=L wtw, "M"MOD(F) (jeżeli M , to M ) Wynikanie lokalne odpowiada dowiedlności ty- pu L, a globalne dowiedlności typu L, w tym sensie, że twierdzenie 1. i 2. można wzmocnić otrzymując mocne twierdzenia o adekwatno- ści: Twierdzenie 3 (Mocna adekwatność) 1. L wtw, |=L 2. L wtw, ||=L Tabela zestawia wyniki dotyczące determinacji 15 ważnych logik. L L-struktury K dowolne D serialne T zwrotne K4 przechodnie KB symetryczne K5 euklidesowe KD5 serialne i euklidesowe KDB serialne i symetryczne B zwrotne i symetryczne K4B przechodnie i symetryczne K4D przechodnie i serialne K45 przechodnie i euklidesowe KD45 serialne, przechodnie i euklidesowe S4 zwrotne i przechodnie S5 równoważnościowe Teoria korespondencji A. Ważne własności relacji osiągalności nazwa warunek funkcyjność "xyz(Rxy '" Rxz y = z) prawie-zwrotność "xy(Rxy Ryy) przeciwzwrotność "xŹRxx prawie- "xyzv(Rxy przechodniość (Ryz '" Rzv Ryv)) gęstość "xy(Rxy "z(Rxz '" Rzy)) antyprzechodniość "xyz(Rxy '" Ryz ŹRxz) prawie-symetria "xyz(Rxy '" Ryz Rzy) asymetria mocna "xy(Rxy ŹRyx) asymetria słaba "xy(Rxy '" x = y ŹRyx)
zbieżność "xyz(Rxy '" Rxz "v(Ryv '" Rzv)) liniowość mocna "xy(Rxy (" Ryx) liniowość słaba "xy(Rxy (" Ryx (" x = y) spójność mocna "xyz(Rxy '" Rxz Ryz (" Rzy) spójność słaba "xyz(Rxy '" Rxz Ryz (" Rzy (" y = z) Twierdzenie 1 Zachodzą następujące równoważności dla (DC), (T ), (4 ), (4C), (B ), (2), (3) i (L): F f& wtw, F jest funkcyjna F ( ) wtw, F jest prawie-zwrotna F ( ) wtw, F jest prawie-przechodnia F wtw, F jest gęsta F ( f&) wtw, F jest prawie-symetryczna. F f& f& wtw, F jest zbieżna F ( ) (" ( ) wtw, F jest mocno spójna F ( '" ) (" ( '" ) wtw, F jest słabo spójna Twierdzenie 2 (Sahlqvist) F f&i j kf&l wtw, R w F spełnia wa- runek "xyz(Rixy '" Rjxz "v(Rkyv '" Rlzv)) B. Warunki niewyrażalne w standardowych ję- zykach modalnych. Twierdzenie 3 Przeciwzwrotność, antyprzechodniość, asyme- tria (mocna i słaba) i liniowość (mocna i słaba) nie mają formuł-odpowiedników. C. Formuły niewyrażalne w języku pierwszego rzędu. Twierdzenie 4 Formuły: (M) f& f& i (G) ( ) definiują klasy struktur, w których relacja osiągalności ma własności wyrażalne w języku drugiego rzędu. Logiki multimodalne (normalne) Logiki multimodalne (polimodalne) budujemy w językach typu Jn, gdzie mamy do dyspozycji n (par) funktorów modalnych. Zapis i ozna- cza, że mamy do czynienia z i-tym funktorem konieczności (1 d" i d" n). Semantyka ulega sto- sownemu uogólnieniu: Definicja (Struktura relacyjna multimodal- na) Strukturą relacyjną, albo ramą (frame) jest dowolny układ F = W, {Ri} gdzie W = " jest
zbiorem punktów (światów możliwych, punk- tów czasowych), a {Ri} jest zbiorem binarnych relacji na W, zwanych relacjami osiągalności. Definicja modelu na strukturze multimodalnej jest bez zmian. Podobnie definicja spełniania formuł za wyjątkiem warunków dla konieczno- ści i możliwości, które przybierają postać: M, w i wtw M, w dla dowolnego w " Ri(w) M, w f&i wtw M, w dla pewnego w " Ri(w) Logiki multimodalne, w których każda modal- ność spełnia te same warunki to homogeniczne logiki, natomiast takie, w których różne mo- dalności mają różne własności, to logiki hete- rogeniczne. W obu wypadkach możemy mieć do czynienia ze zwykłym złożeniem kilku logik monomodalnych, w której brak jest interakcji pomiędzy różnymi modalnościami lub z logika- mi interaktywnymi, w których zachodzą relacje między różnymi modalnościami. Przykład 2 (Logiki temporalne) Są to logiki bimodalne interaktywne z czterema funktora- mi: G dla "odtąd zawsze" (zamiast F ) F dla "nastąpi" (zamiast f&F ) H dla "dotąd zawsze" (zamiast P ) P dla "nastąpiło" (zamiast f&P ) Język ten oznaczać będziemy jako JT. Każda z (par) modalności jest modalnością normalną tzn., że zachodzi aksjomat (K) za- równo dla G jak i dla H, oraz dla obu funkto- rów mamy domknięcie na regułę (RG). Logi- ki te muszą też wyrażać symetrię przyszłości i przeszłości a zatem potrzebujemy też aksjo- matów interakcji obu modalności. Uzyskujemy to z pomocą następującej pary formuł: (B-Te) if&j, gdzie i = j " {F, P }.
Najsłabsza logika temporalna, która spełnia po- dane warunki to Kt. Struktury dla bimodalnych logik temporalnych są postaci W, RF , RP , gdzie W jest zbiorem punktów czasowych, RF jest relacją następ- stwa w czasie, a RP jest relacją poprzedzania w czasie. Dodatkowo zakładamy, że RP jest konwersem RF . Definicja modelu, spełniania itd. bez zmian. Nadlogiki Kt mogą być zarówno homogenicz- ne, jak i heterogeniczne np. możemy przyjąć, że przeszłość jest linearna, ale przyszłość do- puszcza rozgałęzienia. Systemy dedukcyjne A. Konwencje zapisu ą ą1 ą2 1 2 '" Ź( '" ) Ź Ź Ź( (" ) Ź Ź (" Ź( ) Ź Ź Ąi i Ą = f&i i Ź i Źf&i Ź Definicja 15 (Dopełnienia, podformuły) - oznacza dopełnienie lub inaczej: jest formułą komplementarną do ; jest to , jeżeli = Ź, lub Ź w przeciwnym wypadku. B. Dedukcja Naturalna: reguły inferencji (Ą") , - / Ą" (ŹŹ) ŹŹ / (ąE) ą / ąi, gdzie i " {1,2} (ąD) ą1 , ą2 / ą (E) , -i / j , gdzie i = j " {1,2}
(D) i / , gdzie i " {1,2} (D) i / Ąi , gdzie = Ą (T) i / oraz Ą / Ąi Reguły konstrukcji dowodu: D D i DW: i DW: i + 1 -i i + 1 -
k j k Ą" i *" {Ą1} i i DW: i i DW: Ą2 i + 1 Ą1
k k Ą2 Definicja nazwa K, D, T { : i " } K4, D4 {i : i " } *" { : i " } S4 {i : i " } KB, DB, B { : i " } *" {Ąi : Ą " } KB4, KBD4 { : i " } *" {i : i " }*" {Ąi : Ą " } K5, KD5 { : i " } *" {Ąi : Ąi " } K45, KD45 { : i " } *" {i : i " }*" {Ąi : Ąi " } S5 {i : i " } *" {Ąi : Ąi " } C. Etykietowane diagramy Betha Definicja 16 (Etykiety) 1. 1 "ET 2. Jeżeli "ET, to .k "ET .k denotuje etykietę, której ostatni element to k; : oznacza etykietę, która jest konkatena- cją dwóch ciągów; Będziemy nazywali etykietę rodzicem a .i dzieckiem; oprócz 1. każda inna etykieta jest dzieckiem. | | oznacza długość etykiety, czyli ilość wy- stąpień liczb całkowitych w etykiecie. Przykład i interpretacja 1, 1.2.1.1.5, 1.1.1.1.3, są etykietami, a 4.1.3.7., czy 1.3.0.5. etykietami nie są. Nieformalnie, etykieta jest nazwą określonego świata w kon- struowanym modelu, a jej struktura pokazu- je, jakie punkty w tym modelu ją poprzedzają przez R, np. drugi przykład etykiety można od- czytać jako (częściowy) opis modelu, w którym 1, 1.2, 1.2.1, 1.2.1.1, i 1.2.1.1.5, należą do W a pary 1, 1.2 , 1.2, 1.2.1 , ...., 1.2.1.1, 1.2.1.1.5 należą do R. Ogólnie, dla dowolnych dwóch etykiet, z których jedna jest dzieckiem drugiej, oznacza to, że .i jest osiągalne przez R z . Definicja 17 (Formuły etykietowane) Jeżeli " F OR(MOD) a "ET, to : jest formułą etykietowaną. Intuicyjnie : oznacza, że jest spełnione w modelu w punkcie . Reguły 1. Bazowa formalizacja (K-EDB) (Ą") : , : - / Ą" (ŹŹ) : ŹŹ / : (ą) : ą / : ąi, gdzie i " {1, 2} () : , / : 1 | : 2 , (Ą) : Ąi / .k : Ą , gdzie .k jest nową i-etykietą () : i / .k : , gdzie .k jest dowolną i-etykietą Reguły specjalne: (D) : i / : f&i oraz : Źf&i / : Ź i (T) : i / : (4) : i / .k : i , gdzie .k jest dowolną i-etykietą (B) .k : i / : , gdzie .k jest dowolną i-etykietą (B4) .k : i / : i , gdzie .k jest dowolną i-etykietą (5 ) 1.k : i / 1 : ii , gdzie 1.k jest dowolną i-etykietą (5.4) : i / .k : i , gdzie | | >1 i .k jest dowolną i-etykietą Formalizacje znanych logik normalnych można uzyskać przez następujące kombinacje poda- nych reguł. D-EDB K-EDB*"{(D)} T-EDB K-EDB*"{(T )} K4-EDB K-EDB*"{(4)} KB-EDB K-EDB*"{(B)} K5-EDB K-EDB*"{(B4), (5 ), (5.4.)} KD4-EDB D-EDB*"{(4)} KDB-EDB D-EDB*"{(B)} KD5-EDB K5-EDB*"{(D)} S4-EDB T-EDB*"{(4)} B-EDB T-EDB*"{(B)} KB4-EDB KB-EDB*"{(4), (B4)} K4.5-EDB K-EDB*"{(4), (5 ), (5.4.)} KD4.5-EDB K4.5-EDB*"{(D)} S5-EDB S4-EDB*"{(B4)} The Master Argument 1. Wszystko co jest przeszłe i prawdziwe jest konieczne. 2. Niemożliwe nie wynika z możliwego. 3. Co ani nie jest, ani nie będzie, jest możliwe. ZP: Każda możliwość kiedyś się zaktualizuje. 1. P P 2. / f& f& 3. Ź '" ŹF '" f& (Ź3 "! Ź '" ŹF Źf&) DC: '" G P G Standardowy dowód pełności dla L Jest to dowód niekonstruktywny, oparty o konstrukcję modelu kanonicznego metodą Hen- kina (a właściwie Lindenbauma). Pokazuje, że istnieje jeden model nieskończony (model ka- noniczny), należący do MOD(L), który falsyfi- kuje każdą formułę niedowiedlną w L. Definicja (Zbiór niesprzeczny i maksymal- nie niesprzeczny): 1. jest niesprzeczny (Nsp()) wtw, Ą" 2. jest maksymalnie niesprzeczny (MNsp()) wtw,: i) Nsp() ii) dla dowolnego ", jeżeli ą" ", to " Ą" Przypomnijmy, że zachodzi: (TDN): , Ź Ą" wtw, Lemat 1 Dla dowolnego MNsp() zachodzi: 1.1. " wtw, Ź " / 1.2. jeżeli , to " 1.3. jeżeli " i " , to " Lemat 2 (Lindenbaum) Jeżeli Nsp(), to ist- nieje MNsp("), taki, że ą" " Lemat 3 Niech Nsp(), to jeżeli f& " , to Nsp( *" {}) Definicja: Model kanoniczny dla L, to Mc = Wc, Rc, Vc gdzie: Wc = { : MNsp()} Rc" wtw, ą" " Vc(p) = { : p " } Lemat 4 Dla dowolnego MNsp(), jeżeli " , to " ", dla dowolnego ", takiego, że Rc" Lemat 5 Dla dowolnego MNsp(), " wtw, Mc, |= Jako wniosek otrzymujemy: Twiedzenie o pełności: Jeżeli |= , to Logiki okresów warunkowych Kłopotliwe schematy rozumowania: (SH) , / (TR) / Ź Ź (OP) / '" Gdyby Kowalski nie wygrał w audiotele, toby nie miał samochodu. Gdyby nie miał samocho- du, toby nie przejechał swojego sąsiada. Za- tem, gdyby przejechał swojego sąsiada, toby wygrał w audiotele. Jeżeli nasypię do filiżanki kawy 3 łyżki cukru, to będzie słodka. Zatem, jeżeli nasypię tam 3 łyżki cukru i naleję oleju silnikowego, to będzie słodka. Reguły, tezy, logiki: (RCEA) "! / > "! > (RCEC) "! / > "! > (CM) > '" ( > ) '" ( > ) (CC) ( > ) '" ( > ) > '" (RCK) 1 '" ..... '" n / ( > 1) '" ..... '" ( > n) > , ne"0 Logika domknięta na (RCEA) i (RCEC) jest logiką klasyczną, jeżeli dodatkowo zawiera (CM) to jest monotoniczna, a jeżeli zawiera też (CR), to jest regularna. Logika klasyczna domknięta na (RCK) to logika normalna. Najsłabsza lo- gika klasyczna to CE, monotoniczna to CM, regularna to CR a normalna to CK. Semantyka dla logik normalnych Przez standardowy model warunkowy rozumie- my strukturę M = W, f, V gdzie W to zbiór światów, V to waluacja zmiennych, a f to funk- cja selekcji klasy światów (sądu), która dowol- nemu światu i sądowi przyporządkowuje jakiś sąd. Formalnie f : W P(W) - P(W). Wa- runki spełniania dla dowolnego zdania są takie same jak w dowolnych rozważanych poprzed- nio modelach, dla okresów warunkowych sto- sowna klauzula wygląda tak: M, w |= > wtw, f(w, ) ą" Tautologiczność i wynikanie w takich mode- lach definiujemy tak jak poprzednio. CK można teraz scharakteryzować semantycz- nie jako logikę zdeterminowaną przez klasę wszyst- kich standardowych modeli warunkowych. Naj- bardziej znane logiki OW są nadlogikami CK. Ważniejsze logiki normalne 1.CKD (dependable) to najmniejsza logika zawierająca CK +(ID) > (id) f(w, X) ą" X 2.CKWM (weakly material) to najmniejsza lo- gika zawierająca CK + (MP) > ( ) (mp) jeżeli w " X, to w " f(w, X) 3. CKDO (ordered) to najmniejsza logika zawierająca CKD + (CO.1) Ź > > + (CO.2) ( > )'"( > ) ( > "! > ) (co1) jeżeli f(w, X) = ", to f(w, Y ) )" X = " (co2) jeżeli f(w, X) ą" Y i f(w, Y ) ą" X, to f(w, X) = f(w, Y ) 4. CO = CKDO+(MP) 5. CA (additive) = CO+ (CA) ( > ) '" ( > ) (" > (ca) f(w, (" ) ą" f(w, ) *" f(w, ) 6. V = CKDOV (variably strict) to najmniej- sza logika zawierająca CKDO + (CV) ( > ) '" Ź( > Ź) '" > (cv) jeżeli f(w, ) ą" X, to f(w, ) ą" Ź lub f(w, '" ) ą" X 7. VW = CKDOV+(MP) 8. CKM (material) = CKD+(MP)+ (CS) '" > (cs) jeżeli w " X, to f(w, X) = {w} 9. SS = CA+(CS) 10. VC = VW+(CS) 11. C2 (singular) = VC+ (CEM) ( > ) (" ( > Ź) (cem) f(w, X) ma co najwyżej jeden element LOGIKI HYBRYDOWE: Język Bazowy hybrydowy (zdaniowy) j ezyk modalny JH uzyskujemy poprzez dodanie do JM: a) Drugiego sortu zmiennych zdaniowych, zwa- nych nominałami; jest to przeliczalny zbiór NOM = {i, j, k, ...}. Ich zadaniem jest nazywanie punk- tów w modelu. Atomy j ezyka to teraz zbiór ZZ*"NOM (ZZ)"NOM = "). W metaj ezyku b edziemy używać symboli , , dla reprezen- tacji nominałów. b) Dwuargumentowego funktora spełniania, który ł a aczy dowolny nominał z dowoln for- muł Formuły tego typu (sat-formuły) zazna- a. czamy nast aco: : i odczytujemy: "for- epuj muła jest spełniona w punkcie . Przykłady sat-formuł: i : (p f&q), i : j, i : f&j. Formuły, w których jedyne zmienne to nomi- nały, to czyste (pure) formuły JH. 2. Semantyka Poj ecie struktury modelowej dla logiki hybry- dowej nie ulega zmianie, natomiast definicja waluacji musi ulec pewnej zmianie, aby zga- dzać si z intuicyjn interpretacj nominałów. e a a Definicja 18 Waluacj jest dowolna funkcja a V:ZZ*"NOM- P(W), taka, że V() dla do- wolnego nominału jest singletonem. Warunki spełniania formuł pozostaj bez zmian a natomiast dodatkowy warunek dla sat-formuł wygl nast aco: ada epuj M, w : wtw M, w , gdzie {w }=V() Pozostałe definicje semantyczne nie wymagaj a zmian. 3. Logiki Najmniejsza (monomodalna) hybrydowa logika normalna KH wymaga dodania do K nast acych epuj schematów aksjomatów: (K:) : ( ) ( : : ) (S-D:) : "! Ź : Ź (D:) '" : (ZWR-N) : (SYM-N) : "! : (NOM) : '" : : (AGREE) : : "! : (BACK) f& : : Oprócz domkni ecia na (MP) i (RG) KH jest domkni na reguł Gdla dla funktora speł- eta e niania tzn. (RG:) jeżeli " KH, to : " KH dla dowolnego nominału . Natomiast reguła podstawiania zachodzi w nast acej postaci: epuj jeżeli " KH, to e() " KH, gdzie e:ZZ-FOR, ale e:NOM-NOM. 4. Teoria korespondencji nazwa aksjomat warunek (D ) f& serialność (DC ) f& funkcyjność (T ) zwrotność (T ) ( ) prawie-zwrotność (TC ) (IRR) Ź przeciwzwrotność (4 ) przechodniość (4C ) g estość (INT) Ź antyprzechodniość (B ) f& symetria (ASM) Ź asymetria mocna (ASS) (f& ) asymetria słaba (5 ) f& f& euklidesowość (2 ) f& f& zbieżność (3 ) ( )(" spójność mocna ( ) (L ) ( '" ) spójność słaba (" ( '" ) (DI) : f& (" : f& liniowość mocna (TRI) : f& (" : f& (" : liniowość słaba SEMANTYKA TOPOLOGICZNA Definicja 19 (Struktura otoczeniowa) Strukturą otoczeniową jest dowolna para F = W, N gdzie: " dziedzina to W = ", który jest zbiorem
punktów (światów możliwych); " N to funkcja z W w PP(W) (N : W - PP(W)), zwana funkcją sąsiedztwa (inaczej: N (w) ą" P(W), dla każdego w" W). N (od neighbourhood lub od necessary) jest to funkcja, która każdemu punktowi przypo- rządkowuje zbiór tych sądów, które są w nim konieczne. Modelem na danej strukturze F jest dowolny układ M = F, V , gdzie V jest funkcją waluacji zmiennych. Zarówno definicja wartościowania zmiennych, jak i warunki spełniania w modelu dla wszystkich formuł za wyjątkiem modalnych są takie same jak w semantyce relacyjnej. Róż- nica dotyczy waluacji formuł modalnych; w |= wtw " N (w) w |= f& wtw - " N (w) / Definicje prawdziwości w modelu, tautologicz- ności i wynikania bez zmian. Intuicyjnie jest prawdziwe w punkcie w wte- dy gdy sąd wyrażany przez jest w tym punk- cie konieczny. Analogicznie, formuła jest w w możliwa wtedy gdy N (w) nie zawiera dopeł- nienia sądu wyrażanego przez tę formułę. Jak widać funkcja N w istocie interpretuje koniecz- ność jako operator wnętrza a możliwość jako operator domknięcia, stąd często semantyka otoczeniowa określana jest jako semantyka to- pologiczna. Charakteryzacja E jest adekwatne względem klasy wszystkich modeli otoczeniowych. M jest adekwatne względem klasy tych modeli otoczeniowych, które spełniają warunek: (m) jeżeli X )" Y " N (w), to X " N (w) i Y " N (w) lub równoważnie (m ) jeżeli X ą" Y i X " N (w), to Y " N (w) (c) jeżeli X " N (w) i Y " N (w), to X )" Y " N (w) (n) W " N (w) (d) jeżeli X " N (w), to -X " N (w) / (t) jeżeli X " N (w), to w " X (4) jeżeli X " N (w), to {w : X " N (w )} " N (w) Klasa modeli otoczeniowych spełniających wa- runki (m) i (c) daje nam najsłabszą logikę re- gularną R, a po zawężeniu do modeli spełnia- jących dodatkowo warunek (n) otrzymujemy otoczeniową charakteryzację K. (d), (t) i (4) charakteryzują modele otoczeniowe spełniają- ce aksjomaty: (D), (T) i (4).