Semantyka logiczna 30. 11. 2010r

Def. 1) Interpretacją semantyczną danego języka pierwszego rzędu nazywamy dowolną parę uporządkowaną M = <U, /_\> taką, że U jest dowolnym zbiorem niepustym (zwanym uniwersum interpretacji) zaś /_\ jest funkcją przyporządkowującą stałym pozalogicznym rozważanego języka elementy zbioru U lub konstrukcje z tych elementów w sposób spełniający zasadę kategorialnej zgodności (zwaną funkcją denotowania):

1. Dla każdego n-argumentowego predykatu Pⁿ_i , /_\(Pⁿ_i) jest n-członową relację zachodzącą między elementami zbioru U (symbolicznie: /_\(Pⁿ_i) _c Uⁿ);

2. Dla każdego n-argumentowego symbolu funkcyjnego f_iⁿ , /_\(fⁿ_i) jest n-argumentową funkcją o argumentach i wartościach w zbiorze U;

3. Dla każdej stałej indywiduowej a_i , /_\(a_I) jest elementem wyróżnionym ze zbioru U
   (symbolicznie: /_\(a_i) e U)
   

Cała strona formalna konstrukcji Tarskiego dotyczy podana definicja spełniania takiej, że:

• będzie dotyczyła ona zarówno funkcji zdaniowych jak i zdań;

• będzie miała postać definicji rekurencyjnej względem budowy formuł, tj. spełnianie formuł złożonych będzie w sposób jednoznaczny określone przez spełnianie prostszych formuł składowych;

• pozwoli zdefiniować prawdziwość zgodnie z Konwencją (T):

Formalnie poprawną definicję pewnego wyrażenia oznaczającego pewien zbiór zdań języka przedmiotowego J, sformułowaną w jego metajęzyku MJ można uważać za merytorycznie trafną definicję pojęcia prawdy, jeśli pozwala ona udowodnić w MJ wszystkie równoważności powstające ze schematu (T):

(T) Prawdziwe(a) ↔ a^MJ

gdzie a reprezentuje nazwę jednostkową zdania a, a a^MJ jego przekład na metajęzyk MJ.

Funkcja wartościowania. Rozważmy formułę: x+1=y.

Ze zmiennymi w tej formule można skorelować różne ciągi liczb, np.

c = <7,8,9,...>,

s = <6,4,2,...>.

Ciąg c koreluje ze zmienną x (pierwszą zmienną) pierwszy swój wyraz, czyli liczbę 7 a ze zmienną y (druga zmienna) drugi swój wyraz, czyli liczbę 8. Natomiast ciąg s koreluje ze zmienną x liczbę 6 a ze zmienną y liczbę 4. Obiekty skorelowane w ten sposób ze zmiennymi nazywa się ich wartościami, a ciąg który poszczególnym zmiennym przyporządkowuje wartości nazywa się wartościowaniem.

Wniosek: Wartość zmiennej nie jest stała lecz zmienia się od jednego wartościowania do drugiego. Natomiast, wartość nazwy jest stała (niezależna od wartościowania), tj. przy każdym wartościowaniu wartością danej nazwy jest przedmiot przyporządkowany jej przez funkcję denotowania.

Def. 2) Wartościowanie. Nieskończone ciągi elementów uniwersum danej intepretacji M nazywamy M-wartościowaniami lub - po prostu - wartościowaniami (gdy interpretacja M jest ustalona).

Oznaczenie: W_M(t, <w_n>) = wartość termu t przy interpretacji M i wartościowaniu <wn>.

Def. 3) Funkcja wartościowania:

1. Wm(xi, <wn>) = wi (czyli i-ty wyraz ciągu <wn>)

2. Wm(ai, <wn>) = /_\(ai)

3. Wm(|fi(t1, …, tn)|, <wn>) = /_\(fi)(Wm(t1, <wn>), …, Wm(tn, <wn>)).

Czyli wartością termu złożonego fi(t1,..., tn) jest wartość funkcji /_\(fi) dla argumentów Wm(t1, <wn>), …, Wm(tn, <wn>) (tj. wartości termów t1, … tn).

Przykład; Niech U = {0,1,2,...} Niech Ponadto:
/_\(0) = 0
/_\(+) = sum, gdzie „sum” jest dodawaniem liczb naturalnych.
Wtedy:
Wm(|x+0|, <2,...>) = /_\(+)(Wm(x, <2,...>), Wm(0, <2,...>)) = sum(2,0) = 2

Twierdzenie 1. Jeżeli <wn> i <vn> są M-wartościowaniami nie różniącymi się na miejscach o indeksach pokrywających się z indeksami zmiennych wolnych występujących w termie t, to

/Wm = W_M /

Wm(t, <wn>) = Wm(t, <vn>).

Idea: Na wartość termu mają wpływ jedynie te wyrazy wartościowania, które odpowiadają indeksom zmiennych występujących w danym termie.

Przykład: Niech U={0,1,2,...} Niech ponadto:

/_\(0)=0

/_\(+)=sum

Niech dalej c i s będą wartościowaniami nie różniącymi się na pierwszych miejscach (pierwszymi wyrazami), np.

c=<2,3,...>,

s<2,4,...>.

Wtedy

Wm(|x+0|,c) = sum(2,0) = Wm(|x + 0|,s).

/dowód u Batoga/

Spełnianie: Rozważmy formułę x<s(0). Jest ona spełniona przez ciąg c=<0,2,..> bo liczba 0 (=Wm(x,c)) jest mniejsza od liczby 1 (=Wm(|s(0)|,c)).

Natomiast nie jest ona spełniona przez ciąg s=(2,3,...), bo liczba 2 (=Wm(x,s)) nie jest mniejsza od liczby 1 (=Wm(|s(0)|,s)).

Oznaczenia:

<wn> Spł_M|A| czytamy ciąg <wn> spełnia formułę A przy interpretacji M.

<wn>(w_i/u) oznacza: ciąg różniący się od ciągu <wn> co najwyżej na i tym miejscu, tj.

<wn>(wi/u) = <w1, …, wi-1, u, wi+1,...>

Znak stałej logicznej bez kropki = np. ^ - należy do języka przedmiotowego, natomiast ten sam znak ale z kropką u góry - np. ^ należy do metajęzyka. /nad ^ jest kropka, której nie ma bo nie ma jak zrobić/.

Dygresja. Stosuje się też inną notację dla spełnienia formuł:

M |= A[s] gdzie s jest dowolną ale ustoalonym M-wartościowaniem.

Def 4. (Spełnianie):

.

1. <wn> SpłM|Pi(t1, …, tn)| ↔ /_\ (Pi)(Wm(t1, <wn>), .., Wm (tn, <wn>)).

Słownie: ciąg <wn> spełnia formułę atomową Pi(t1, …, tn) przy interpretacji M wtw pomiędzy wartościami termów t1, …, tn - tj. przedmiotami Wm(t1, <wn>), …, Wm(tn, <wn>) zachodzi relacja którą funkcja denotowania /_\ przyporządkowuje predykatowi Pi.

. .

2. <wn>SpłM |~A| ↔ ~ (<wn>SpłM|A|).

/reszta u mary się zeskanuje/

5. 
   

Dygresja: (1) Aby zapis uczynić prostszym w dalszym ciągu wykładu nie będzie kropek nad symbolami logicznymi metajęzyka. Kontekst będzie rozstrzygał czy dany symbol należy do języka przedmiotowego czy do metajęzyka.

2. będziemy pisać <wn>SpłMA zamiast <wn>SpłM|A|

Przykłady: Rozawżmy powtórnie język L. Niech s = <MARS, SŁOŃCE, ...>.

s SpłM|Planeta(x)| ↔ Wm(x,s) e /_\(Planeta) ↔ MARS e PLANETA.

S SpłM|Planeta(Phobos)| ↔ Wm(Phobos, s) e /_\(Planeta) ↔ /_\(Phobos) e /_\(Planeta) ↔ PHOBOS e PLANETA.

Ponieważ skądinąd wiadomo że PHOBOS /e PLANETA więc ciąg s nie spełnia zdania Planeta(Phobos).

S SpłM |Okrąża(x,y)| ↔ <Wm(x,s), Wm(y,s)> e /_\(Okrąża) ↔ <MARS, SŁOŃCE> e OKRĄŻA.

S SpłM|3x ~Okrąża(x, Phobos)|

↔ 3u e U (<u, SŁOŃCE,...> SpłM|~Okrąża(x, Phobos)|)

↔ 3u e U ~(<Wm(x, <u, SŁOŃCE,...>), Wm(Phobos, <u, SŁOŃCE,...>)) e /_\(okrąża))

↔ 3u e U ~(<u, /_\(Phobos)> e /_\(okrąża))

↔ 3u e U ~(<u, PHOBOS> e OKRĄŻA)

↔ 3u e U (<u, PHOBOS> /e OKRĄŻA)

(czyli istnieje element U, który nie okrąża Phobosa).

Tw 2. Jeżeli <wn> i <vn> są M-wartościowaniami nie różniącymi się na miejsca o indeksach pokrywających się z indeksami zmiennych wolnych występujących w formule A, to <wn> SpłM A ↔ <vn>SpłM A.

Idea: Istotne w ciągu spełniającym są tylko te wyrazy, które przez funkcję wartościowania zostały skorelowane ze zmiennymi wolnymi występującymi w danej formule.

Wnioskiem z tego tw. Jest twierdzenie:

Tw. 3) Jeżeli A jesrt zdanie, zaś <wn> i <vn> są dowolnymi M-wartościowaniami, to <wn> SpłMA ↔ <vn>SpłMA.

Idea: W przypadku zdań postać ciągu spełniającego jest obojętna.

Konsekwencją twierdzenia 3 i faktu, że uniwersum interpretacji jest zbiorem niepustym jest twierdzenie:

Tw. 4. Jeżeli A jest zdaniem to równoważne są następujące warunki:

1. Dla każdego wartościowania <wn>, <wn>SpłMA;

2. istnieje wartościowanie <wn> takie, że <wn>SpłMA

Dygresja. W szczególnym przypadku wartościowaniem o którym mowa punkcie 2 jest ciąg pusty, tj. ciąg o 0 liczbie wyrazów. Spełnianie zdań zależy bowiem tylko od denotacji stałych pozalogicznych.

Mamy już wszystkie „narzędzia” niezbędne do zdefiniowania pojęcia prawdy.

/Pojęcie prawdy jako szczególny przypadek pojęcia spełniania/

Def. 3) Prawdziwość/Fałszywość. Formuła A jest prawdziwa przy interpretacji M=<U, /_\> wtw każdy nieskończony przeliczalny ciąg elementów zbioru U spełnia formułę A przy interpretacji M. W przeciwnym przypadku jest ona fałszywa.

Oznaczenie:
Vr(M) = zbiór formuł prawdziwych przy interpretacji M

Fa(M) = zbiór formuł fałszywych przy interpretacji M

Symbolicznie: Niech <wn> będzie dowolnym M-wartościowaniem. Wtedy:

A e Vr(M) ↔ \-/<wn>(<wn> SpłMA).

A e Fa(M) ↔ 3<wn> ~(<wn> SpłMA).

Dygresja. Cała definicja prawdy sformułowana jest metajęzyku (!).

/definicja jest formalnie poprawna, pytanie czy merytorycznie poprawna? Dam dam dam dam!/.

Przykład. Niech A = ~\-/x Planeta(x) /nie wszystko jest planetą).

|~\-/xPlaneta(x)| e Vr(M) ↔ \-/<wn>(<wn> SpłM |~\-/x Planeta(x)|)

↔ 3<wn>(<wn>SpłM |~\-/x Planeta(x)|) [twierdzenie 4]

Rozważmy M-wartościowanie <MARS,...>.

|~\-/x Planeta(x)| e Vr(M) ↔ <MARS, ...> SpłM |\-/x Planeta(x)|)

Dalej korzystamy z definicji spełniania:

↔ ~(<MARS,...> SpłM |\-/x Planeta(x)|)

↔ ~\-/u e U (<u, ...> SpłM |Planeta(x)|)

↔ ~\-/u e U (Wm(x<u,...>) e /_\Planeta))

↔ ~\-/u e U (u e PLANETA).

Dygresja. Po lewej stronie powyższej równoważności występuje nazwa analizowanego zdania, a po prawej - jego przekład na metajęzyk. Równoważność ta jest cząstkową definicją prawdy, odpowiadającą na pytanie: Kiedy analizowane zdanie jest prawdziwe?

Nie odpowiada na pytanie: Czy analizowane zdanie jest prawdziwe? Prawa strona równoważności musi być tezą metajęzyka - definicja prawdy mówi nam głównie kiedy zdanie jest prawdziwe.

Na pytanie „czy” logika nie odpowiada - zajmują się tym nauki szczegółowe.

Eksplikacja klasycznego pojęcia prawdy; stwierdziliśmy, że definicja jest formalnie poprawna i merytorycznie trafna. Czy dobrze formalizuje klasyczne pojęcie prawdy?

---