Logika prof dr hab. Bogdan WĘglorz rachunek zdań, algebry uniwersalne. Systemy relacyjne



Pobieranie 6.74 Mb.
Strona9/57
Data25.10.2017
Rozmiar6.74 Mb.
1   ...   5   6   7   8   9   10   11   12   ...   57

DEFINICJA. Dwa typy ciągów symboli nazywamy formułami atomowymi:

(i) jeśli t1 i t2 są termami to ciąg = t1 t2 jest formułą atomową;

(ii) jeśli P jest predykatem n – arnym oraz t1 , ... , tn są termami, to P t1 ... tn jest też formułą atomową.

UWAGA.(1) Podobnie jak poprzednio zaadoptujemy konwencję z §0 w sprawie używania nawiasów i przecinków i w celu poprawienia czytelności, będziemy ich swobodnie używać.

Również w celu poprawienia czytelności będziemy pisać t1 = t2 zamiast = t1 t2 .

(2) Zwróćmy uwagę, że symbol równości jest wyróżnionym predykatem. Nie jest to specjalnie konieczne a daje tylko techniczne ułatwienia w tym wykładzie.

Teraz możemy przejść do ostatniej ważnej definicji w tej części.

DEFINICJA. Pewne ciągi symboli nazywamy formułami. Formuły definiujemy indukcyjnie ze względu na ich budowę. Robimy to następująco:


  1. każda formuła atomowa jest formułą;

  2. jeśli s jest w – arnym spójnikiem, oraz 1 , ... , w są formułami, to s1 ... w jest też formułą;

  3. jeśli x jest zmienną (indywiduową),  jest formułą oraz Q jest kwantyfikatorem, to Qx też jest formułą;

  4. innych formuł nie ma.

UWAGA.(1) Zastosujemy oczywiście konwencję z §0 i konsekwentnie, będziemy używać i nawiasów i przecinków o ile to tylko polepszy czytelność. W ten sposób będziemy na przykład pisać s(1 ... w) zamiast s1 ... w oraz (Qx)  zamiast Qx .

(2) Jeśli Fm jest zbiorem wszystkich formuł, to możemy – używając spójników – utworzyć algebrę formuł Fm = < Fm , {sl}l L > , która jest typu (w , ) .

(3) Istnieją logiki, w których używa się kwantyfikatorów wielu zmiennych. Nie jest mi znane zastosowanie takich logik w zagadnieniach związanych z informatyką.

(4) Zmieniając część logiczną języka nie zmieniamy termów a jedynie możemy zmienić formuły. Również warto zauważyć, że zarówno pojęcie termu jak też formuły zależy nie od konkretnego systemu relacyjnego a od jego typu podobieństwa.

Część tę zakończymy definicją operatorów występowania, który pozwalają na wydobycie poszczególnych symboli z termu czy formuły. Zaczniemy od termów:

ZC(t) oznacza zbiór stałych występujących w termie t ;

ZV(t) oznacza zbiór zmiennych występujących w termie t ; natomiast

ZF(t) oznacza zbiór funktorów występujących w t .

Zbiory te definiujemy przez indukcję w sposób analogiczny do definicji termu.

DEFINICJA. (i) Jeśli t jest stałą c , to ZC(t) = {c} , natomiast ZV(t) = ZF(t) =  ;

(ii) jeśli t jest zmienną x , to ZV(t) = {x} , natomiast ZC(t) = ZF(t) =  ;



(iii) jeśli t = F(t1 , ... , tm) , to wówczas ZX(t) = , dla X = C i V oraz

ZF(t) =  {F} .

Dla formuł symbole ZV() i ZF() mają nieco inne znaczenie. Pierwszy oznacza mianowicie zbiór zmiennych wolnych występujących w formule  , a drugi zbiór funktorów i predykatów występujących w  . Zbiory te, podobnie jak dla termów definiujemy indukcyjnie, ze względu na budowę formuły.



DEFINICJA. (i) jeśli  jest formułą atomową typu t1 = t2 , to dla X = C , V i F mamy

ZX() = ZX(t1)  ZX(t1) ;



  1. jeśli  jest formułą atomową typu P(t1 ... tn) , to dla X = C i V mamy

ZX() = ,

natomiast ZF() =  { P } ;

  1. jeśli  jest formułą postaci s(1 ... w) , to dla X = C , V i F mamy

ZX() = ,

  1. jeśli  jest formułą postaci (Qx)  , to dla X = C i F mamy ZX() = ZX() , natomiast ZV() = ZV() \ {x} .

Tak więc kwantyfikowanie zmniejsza ilość zmiennych wolnych. Formuły bez zmiennych wolnych nazywamy zdaniami.

W dalszej części wykładu odejdziemy od takiej ogólności. Przede wszystkim zredukujemy rozmaitość logik do sytuacji, w której występują tylko niektóre z klasycznych spójników  ,  ,  ,  ,  , jak również ograniczymy kwantyfikatory do dwóch  i  . Dokładniej w zagadnieniach syntaktycznych wygodniej będzie używać spójników  ,  i kwantyfikatora  , natomiast w semantycznych (o których za chwilę) – spójników  ,  i kwantyfikatora  . Oczywiście, można to ujednolicić, ale czy trzeba?





Pobieranie 6.74 Mb.

Share with your friends:
1   ...   5   6   7   8   9   10   11   12   ...   57




©operacji.org 2020
wyślij wiadomość

    Strona główna