Klasyczny rachunek predykatów:
Język KRP: na slajdach w zeszłym semestrze [KRP].
Słownik:
Zmienne indywiduowe (nazwowe): x1, x2 – jest zbiorem przeliczalnym.
Stałe indywiduowe (nazwowe): a1, a2 – nieskończenie, przeliczalnie wiele.
Symbole funkcyjne: f11, f11, f11,
Symbole predykatów P11, P11, P11,
górny indeks – liczba argumentów predykaty
dolny – odróżnianie
spójniki takie jak w KRZ.
Kwantyfikatory: \-/ (generalny); 3 (egzystencjalny)
nawiasy: ),(
Terminologia: spójniki i kwantyfikatory tworzą zbiór tzw. Stałych logicznych.
Stałe indywiduowe, symbole funkcyjne i symbole relacyjne tworzą zbiór tzw. Stałych pzalogicznych.
Def2. (Wyrażenie) każdy skończony ciąg symboli ze słownika KRP nazywamy wyrażeniem tego języka.
Mamy tu dwie kategorie wyrażeń sensownych:
· formuły nazwowe, zwane termami;
· formuły zdaniowe -> formuły;
pojęcia te definiujemy indukcyjnie w nast. Sposób.
Def 3) Term:
(1) Wszystkie zmienne i stałe indywiduowe są termami języka KRP ; nazywamy je termami prostymi
(2) Jeżeli fnk jest n-argumentowym symboleme funkcyjnym zaś t1, ..., tn są dowolnymi termami, to wyrażenie postaci fnk( t1, ..., tn) jest również termem (tzw. Termem złożonym)
(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.
Def 4. (Formuła zdaniowa atomowa) Formułą atomową języka KRP nazywamy dowolne wyrażenie o postaci Pkn( t1, ..., tn) gdzie Pkn jest n-argumentowym predykatem, zaś t1, ..., tn są dowolnymi termami.
Formuły atomowe są cegiełkami z których z pomocą stałych logicznych, tj. Spójników oraz kwantyfiaktorów, możemy budować bardziej złożone formuły. Pojęcie formuły zdaniowej definiujemy indukcyjnie:
Def 5.
(1) Wszystkie formuły atomowe są formułami j. KRP
(2) Jeżeli A, B są dowolnymi formułami języka KRP to wyrażenia postaci:
~(A), (A) /\ (B), (A) v (B), (A) -> (B), (A) <-> (B), \-/x(A), 3x(A) są również formułami j. KRP.
(3) Nie ma innych formuł j. KRP poza formułami atomowymi i takimi, które powstają na mocy reguły (2).
Jeżeli kwantyfikator znajduje się w jakiejś formule, to zwsze bezpośrednio za nim występuje zmienna indywiduowa, mówimy o niej jako o związanej przez kwantyfikator (kwantyfikator wiąże zmienną).
Def 6. jeżeli formuła ma postać \-/x(A) lub 3x(A) to mówimy, że kwantyfikator wiąże zmienną x.
W j. 1. rzędu kwantyfikatory wiążę tylko zmienne indywiduowe.
Umowy notacyjne:
Dużych liter z początku alfabetu A, B, C, D (ew. Z indeksami) używamy jako zmiennych metajęzykowych oznaczających dowolne formuły j. 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. KRP.
Liter t, s (ew. Z indeksami) używamy jako zmiennych metajęzykowych oznaczających dowolne termy języka KRP. Podobnie xi oraz ai są zmiennymi metajęzykowymi, których wartościami są odpowiednio zmienne indywiduowe i stałe indywiduowe.
Dla uproszczenia notacji pisać będziemy:
x zamiast x1 y zamiast y2 etc a zamiast a1 etc. Pomijać będziemy też górny indeks określający liczbę argumentów danego symbolu funkcyjnego lub relacyjnego jeżeli występuje on wraz ze swymi argumentami.
Dla większej przejrzystości używać będziemy różnych nawiasów ([{}])
Podobnie jak w przypadku KRZ przyjmujemy, że:
spójnik ~ wiąże najsilniej
spójniki /\ i v wiążą silniej niż -> i <->
reszta na slajdach z zeszłego semestru, nie chce mi się przepisywać;
· zasięg kwantyfikatora.
· zmienne związane i zmienne wolne.
nawiasy pełnią rolę znaków interpunkcyjnych oraz wskazują na zasięg kwantyfikatora.
Def 10 zdanie, funkcja zdaniowa, formuły bez zmiennych wolnych nazywamy zdaniami. Pozostałe formuły nazywamy funkcjami zdaniowymi.
Wprowadźmy jeszcze pojęcie domknięcia (uniwersalnego) formuły. Jest to operacja pozwalająca z dowolnej formuły otrzymać zdanie.
Def. 11 domknięcie formuły A nazywamy formułe powstałą z formuły A przez poprzedzenie jej dużymi kwantyfikatorami, które wiązą wszystkie występujące w niej zmienne wolne. Domknięcie formuły A oznaczać będziemy symbolem:
_
A
_____P1(x,y) = \-/x\-/yP1(x,y)______________
P1(x) /\ 3x P2(x,y) = \-/x\-/y[P1(x) /\ 3xP2(x,y)]
___________________
3x\-/y[P1(x) -> P2 (x,y)] = 3x\-/y[P1(x) -> P2 (x,y)]
Umowy notacyjne: aby jeszcze bardziej uprosić symbolikę predykatów na ogół nie przedstawiaj się w wersji oryginalnej, lezc zastęuje symbolami P, Q, R, S,.... Liczbę argumentów wyznacza kontekst. Jako symboli funkcyjnych będziemy używać też małych liter f, g, h, itd.
W ujęciu syntaktycznym rachunek logiczny ma postać systemu aksjomatycznego. Wymaga to:
· wyodrębnienia pewnego początkowego zbioru formuł, tzw. Aksjomatów.
· Podania pierwotnych reguł dowodzenia, czyli instrukcji wyprowadzania jednych 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, chociaż daje się on uzyskać z pewnego skończonego zbioru schematów metajęzykowych (aksjomatów?).
Zostaną tu przedstawione dwa warianty aksjomatycznego ujęcia KRP.
Pierwszy pochodzi z podręcznika Batóga, drugi z dupy ale używany przez dr.
Wariant 1. Aksjomatami KRP są wszystkie te i tylko te formuły, które powstają z tautologii KRZ przez konsekwentne zastąpienie zmiennych zdaniowych dowolnymi formułami języka KRP.
np. prawo transpozycji:
(p -> q) -> (~q -> ~p)
Powstają:
· [\-/x1P1(x1) - > 3x1P1(x1)] -> [~3x1P1(x1) -> ~\-/x1P1(x1)],
Generalnie w ogóle wszystkie formuły o postaci (A -> B) -> (~A -> ~B), gdzie A B są jakimikolwiek formułami j. KRP...
Def1. Podstawialność: mówimy, że term t jest podstawialny za zmienną x do formuły A wtw zmienna x nie leży w A jako wolna w zasięgu żadnego kwantyfikatora wiążącego którąś ze zmiennych występujących w termie t.
Przykłady: weźmy formułę jęzka artymetyki: 3x(x =< y) zarówno term x+z2 jak i 0 są podstawialne za zmienną x w owej formule, gdyż w wyniku ew. Podstawień otrzymamy nast. Formuły: 3y(x + z2 =< y) i 3y(0 =< y) takie, że żadna ze zmiennych występujących w tych termach nie stała się zmienna związaną („0” jest nazwą, czyli nie ma zmiennych). Natomiast y+z2 nie jest podstawialny za zmienną x do owej formuły, gdyż po podstawieniu występująca w nim zmienna y stałaby się związana.
Notacja: wynik podstawiania termu t za zmienną x do formuły A będziemy oznaczać sybolem A[xi/t] (podobnie jak w KRZ).
Precyzyjna definicja operacji podstawiania jest indukcyjna:
(1)
jelonka72