Semantyka logiczna 05. 10. 2010r

1. Własności teorii 1. rzędu
   niesprzeczność

2. Semantyka:

prawdziwość

Podręcznik: Batóg „Podstawy logiki” [niektórych rzeczy nie ma w podręczniku!]

1. Rachunek predykatów pierwszego rzędu

1. Język KRP

Język J jest j. 1. rzędu wtw spełnia warunki:

• nieskończenie zmiennych indywiduowych/nazwowych

• przynajmniej jeden symbol relacyjny [predykat, obojętnie ilu argumentowy]

• skończoną l. Spójników zdaniowych [klasyczne - ~, ^, v, → , <=> ]

• w słowniku występują kwantyfikatory - wiążą wył. Zmienne indywiduowe

• znaki techniczne ), (

• stałe indywiduowe - nazwy jednostkowe, konkretnych obiektów

• symbole funkcyjne - tworzy się nazwy złożone

wyrażenia sensowne = schematy poprawnie zbudowanych nazw/zdań jakiegoś języka.

Przykładem j. 1. rzędu jest język KRP.

Słownik:

zmienne indywiduowe: x1, x2, … [nieskończenie, przeliczalnie wiele]

stałe indywiduowe: a1, a2, … [nieskończenie, przeliczalnie wiele]

symbole funkcyjne: f₁², f₂¹, …

symbole relacyjne: P¹₁, …, P_kⁿ [górny indeks - liczba argumentów, dolny do odróżnienia symboli funkcyjnych]

spójniki: ~, ^, v, →, <=>

kwantyfikatory: \-/, 3

znaki techniczne: ), (

Terminologia: spójniki i kwantyfikatory tworzą zbiór stalych logicznych; stałe indywiduowe, symbole funkcyjne i symbole relacyjne tworzą zbiór stalych pozalogicznych.

Def 2. Wyrażenie - każdy skończony ciąg symboli ze słownika KRP nazywamy wyrażeniem tego języka.

Mamy dwie kategorie wyrażeń sensownych:

• formuły nazwowe - termy

• formuły zdaniowe

Pojęcia te definiujemy indukcyjnie:

Def 3: term

1. wszystkie zmienne i stałe indywiduowe są termami KRP. Są to termy proste.

2. Jeżeli f_kⁿ(t1, …, tn) jest również termem (tzw. term złożony)

3. nie ma innych termów poza wymienionymi w punkcie (1) i takimi, które powstają dzięki zastosowaniu reguły (2).

Termy bez zmiennych to termy domknięte, czyli nazwy.

np. +(x₁,2) → x₁ + 2 [wyrażenie nie jest nazwą]

0 + 2 [wyrażenie jest nazwą]

Def 4: formuła zdaniowa atomowa. Formułą atomową języka KRP nazywamy dowolne wyrażenie postaci P_kⁿ(t1, …, tn), gdzie P_kⁿ jest n-argumentowym predykatem, zaś t1, …, tn są dowolnymi termami.

np. x₁ + 2 = x₃

Formuły atomowe reprezentują wyrażenia najprostsze.

Def 5: Formuła zdaniowa:

1. Wszystkie formuły atomowe są formułami KRP

2. Jeżeli A, B są dowolnymi formułami KRP, to wyrażenia:

~(A), (A) ^ (B), (A) v (B), (A) → (B), (A) ↔ (B), \-/ (A), 3 (A)

3. Nie ma innych formuł j. KRP poza formułami atomowymi i takimi, które powstają po zastosowaniu reguły (2).

Jeżeli kwantyfikator znajduje się w jakiejś formule, to zawsze bezpośrednio za nim występuje zmienna indywiduowa. Mówimy wówczas, że kwantyfikator wiążę tę zmienną.

Def. 6: Jeżeli formuła ma postać \-/x_i(A) lub 3x_i(A), to mówimy, że odpowiedni kwantyfikator wiąże zmienną x_i.

Umowy notacyjne:

• Dużych liter z początku alfabetu A, B, C, D... (ew. z indeksami) używamy jako zmienne metajęzykowe oznaczające dowolne formuły języka KRP.

• Dużych liter z końca alfabetu X, Y, Z (ew. z indeksami) używamy jako zmiennych metajęzykowych oznaczających dowolne zbiory formuł języka KRP.

• Liter t, s (ew. z indeksami) używamy jako zmiennych metajęzykowych oznaczających dowolne termy KRP.

Dla uproszczenia notacji pisać będziemy:

• zamiast x₁, … będziemy pisać x. Pomijać będziemy górny i dolny indeks określający liczbę argumentów danego symbolu funkcyjnego bądź relacyjnego jeżeli występuje on ze swoimi argumentami.

• Dla większej przejrzystości będziemy używać nawiasów okrągłych, kwadratowych i klamrowe.

• Podobnie jak w przypadku KRZ, przyjmujemy że:

~ wiąże najsilniej

^ i v wiążą silniej niż → i ↔

Formułami nie są: P³₁ (x, y) ← wyrażenie, ale nie formuła zdaniowa (sensowna);

Def. 7: (Zasięg kwantyfikatora) Formułę A w formule \-/x_i(A) lub 3x_i(A) nazywamy zasięgiem kwantyfikatora. (formuła zdaniowa w nawiasie za kwantyfikatorem).

Jeśli wiadomo jaki zasięg ma kwantyfikator nie używamy nawiasów - zamiast: \-/x(3y(P₁(x,y))) piszemy: \-/x3yP₁(x,y)

Def. 8: Zmienna związana:

Zmienna x₁ występująca na danym miejscu w formule A jest w tym miejscu związana wtw występuję bezpośrednio po kwantyfikatorze lub znajduje się w zasięgu kwantyfikatora wiążącego tę zmienną.

Zmienna x₁ występująca w formule A jest w niej związana wtw x₁ jest związana na każdym miejscu w formule A.

Def. 9: Zmienna wolna:

Jeżeli zmienna xi występująca na danym miejscu w formule A, nie jest na tym miejscu związana, to mówimy, że jest ona na tym miejscu wolna w A. Mówimy, że zmienna xi jest wolna w formule A wtw jest ona wolna na przynajmniej jednym miejscu w formule A.

np. P₁(x) → \-/x P₂(x) - zmienna x jest wolna.

Def 10: (Zdanie, funkcja zdaniowa):

Formuły bez zmiennych wolnych nazywamy zdaniami. Pozostałe formuły nazywamy funkcjami zdaniowymi.

Wyr. j. KRP

• wyr. sensowne

- formuły nazwowe [termy] → termy proste i złożone
- nazyw - termy otwarte
- formuły zdaniowe [formuły] → atomowe i złożone
- funkcje zdaniowe - zdania

• bezsensowne

Pojęcie domknięcia (uniwersalnego) formuły, jest to operacja pozwalająca z dowolnej formuły otrzymać zdanie.

Def 11: Domknięcie formuły:

Domknięciem formuły A nazywamy formułę powstałą z A przez poprowadzenie jej dużymi kwantyfikatorami, które wiążą wszystkie występujące w niej zmienne wolne. Domknięcie formuły A oznaczać będziemy symbolem kreską nad symbolem formuły

__

[np. A ]

np.

_____

P₁(x,y) = \-/x\-/y P₁(x,y)

Umowy notacyjne: Predykaty:

używa się P, Q, R, S, … . Liczbę argumentów wyznacza kontekst.

Jako symboli funkcyjnych będziemy używać też malych liter f...

Przypomnienie: W ujęciu syntaktycznym rachunek logiczny ma postać systemu aksjomatycznego. Wymaga to:

• wyodrębnienie pewnego początkowego zbioru formuł, tzw. aksjomatów;

• podania pierwotnych reguł dowodzenia, czyli „instrukcji” wyprowadzania jeednych formuł z innych.

Wszystkie aksjomaty i formuły, które można z nich wyprowadzić za pomocą przyjętych reguł dowodzenia określa się mianem tez rachunku logicznego.

KRP - w przeciwieństwie do KRZ - nie jest skończenie aksjomatyzowalny, tzn. jego zbiór aksjomatów - w każdym ujęciu - jest zbiorem nieskończonym...

Wariant 2: Przyjmujemy, że zbiór aksjomatów KRP tworzą wszystkie i tylko te formuły, które powstają z poniższych schematów przez podstawienie dowolnych formuł w miejsce metazmiennych. Schematy A1 - A8.

Dwie reguły inferencyjne:

RO - A → B, A / B;

RG - A / \-/x_i(A)

Zbiór aksjomatów KRP = Arp.

Dowodzenie:

Każdy schemat tezy KRZ jest zarazem schematem tezy KRP.

np. (A → ~B) → (B → ~A) jest schematem tez KRZ i zarazem tez KRP.

Aby rozwijać pewne teorie, np. matematyczne, wprowadza się symbol relacji identyczności [zazwyczaj uważa się go za stałą logiczną]. Syntaktycznie rzecz biorąc, znak identyczności jest predykatem 2 - argumentowym.

Wymaga zmodyfikowanie def. Formuły atomowej - dodanie t₁ = t₂.

I1. x = x [zwrotnośc]

I2. x = y → y = x [symetrycznośc]

I3. x = y ^ y = z → x = z [przechodniość]

I4.

I5.

Kwantyfikator o ograniczonym zakresie:

Za kwantyfikatorem występuje formuła zdaniowa - funkcja zdaniowa z jedną zmienną - warunek kwantyfikatora, np.

\-/x>0(|x| = x) wyrażenie „\-/x>0” czytamy dla kazdego x większego od 0.

Niech A(x) będzie formułą KRP w której x jest zmienną wolną. Pisz się:

\-/(A(x)) (B(x)) zamiast: \-/x(A(x) → B(x))

oraz

3(A(x)) (B(x)) zamiast: 3x(A(x) → B(x))

ELEMENTY METALOGIKI:

Derywacja - dowód formuły A w oparciu o zbiór X. Wyprowadzenie formuły ze zbioru formuł z uwagi na zadany zbiór reguł inferencyjnych. Pojęcie derywacji jest uogólnieniem wprowadzonego pojęcia dowodu w oparciu o zbiór Arp. Różnica polega na tym, że nie żądamy aby przesłanki były aksjomatami KRP. Dowód jakieś formuły w oparciu o Arp jest jej derywacją w oparciu o ten zbiór ale nie na odwrót.

Def. 1: Derywacją formuły A w oparciu o zbiór X nazywamy każdy skończony ciąg formuł:

500. D₁, D₂, ... D_n

taki, że:

1. formuła ostatnia D_n jest identyczna z formułą A,

2. formuła pierwsza D1 jest elementem zbioru X

3. każda formuła w ciągu (D) nie będąca elementem zbioru X powstaje z poprzedzających ją formuł w tym ciągu przez zastosowanie do nich jednej z przyjętych reguł inferencyjnych.

Cn(X) = zbiór wszystkich konsekwencji zbioru X.

A e Cn(X) = A jest el.

Def 2. A e Cn(X) wtw istnieje co najmniej jeden dowód formuły A w oparciu o zbiór X.

Podstawowe własności operacji Cn są taie same jak w KRZ.

Def. 3: Konsekwencja logiczna: A e CnL(X) wtw A e Cn(X u Arp)

A jest konsekwencją logiczną zbioru X wtw A jest konsekwencją zbioru X rozszerzonego o Arp.

Twierdzenie 2. L = CnL( (/) )

[ (/) - zbiór pusty ]

Twierdzenie to można zapisać również jako: A e L wtw A e CnL( (/) ).

Tezy KRP są to wszystkie formuły, które można wyprowadzić wyłącznie z aksjomatów KRP.

Twierdzenie 3: Dla dowolnego zbioru formuł X, L _c CnL(X).

Każdą tezę możemy poprzedzić kwantyfikatorem generalnym, korzystając z reguły generalizacji.

Twierdzenie 7: _

A e CnL(X) wtw A e CnL(X)

_

znaczy to, ze CnL(X) = CnL(X)

twierdzenie o dedukcji wprost:

Jeżeli A jest zdaniem oraz formuła B e CnL(X u {A}), to (A → B) e CnL(X).

Jeżeli A jest zdaniem, to B e CnL(X u {A}) wtw (A → B) e CnL(X).

Wniosek: jeżeli A1, …, An są zdaniami oraz B e CnL({A1, …, An}), to

1. (A1 ^ … An → B) e L

2. 
   

---