Rachunek predykatów pierwszego rzędu

Nasza ocena:

5
Pobrań: 21
Wyświetleń: 868
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Rachunek predykatów pierwszego rzędu - strona 1 Rachunek predykatów pierwszego rzędu - strona 2 Rachunek predykatów pierwszego rzędu - strona 3

Fragment notatki:

Rachunek predykatów pierwszego rzędu 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 1 2 , f 2 1 , …
symbole relacyjne: P 1 1 , …, P k n [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
wszystkie zmienne i stałe indywiduowe są termami KRP. Są to termy proste.
Jeżeli f k n (t1, …, tn) jest również termem (tzw. term złożony)
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 1 ,2) → x 1 + 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 n (t1, …, tn), gdzie P k n jest n-argumentowym predykatem, zaś t1, …, tn są dowolnymi termami.
np. x 1 + 2 = x 3 Formuły atomowe reprezentują wyrażenia najprostsze.
Def 5: Formuła zdaniowa:
Wszystkie formuły atomowe są formułami KRP
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)
Nie ma innych formuł j. KRP poza formułami atomowymi i takimi, które powstają po zastosowaniu reguły (2).


(…)

…:
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. P1(x) → \-/x P2(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łą…
… 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 / \-/xi(A)
Zbiór aksjomatów…
…. 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…
... zobacz całą notatkę

Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz