05.pdf

2. KLASYCZNA LOGIKA PREDYKATÓW 53

Rachunek zdań wiernie opisuje wynikanie semantyczne dla ję-

zyka, którego zdania za pomocą spójników zbudowane są ze zdań

(prostych)owewnętrznienieanalizowalnejstrukturze.Zdaniajęzyka

potocznego, języków nauk przyrodniczych, humanistycznych oraz

matematyki, budowanesązwyrażeńprostszychniżzdania,np.jest

tak w wypadku zdania 4+3=7 . Na to, aby rachunek logiczny

nadawał się do wszystkich rozumowań poprawnych przeprowadza-

nych w takich językach, konieczne jest by był rachunkiem, którego

język uwzględnia tę wewnętrzną złożoność zdań prostych. Na przy-

kładpoprawnejestwnioskowanie:

Przesłanka 1: 2jestliczbąnaturalną

Przesłanka 2: Liczbynaturalnesąwymierne

Wniosek: 2jestliczbąwymierną

Jednaknagrunciejęzykarachunkuzdańposzczególnymprzesłankom

i wnioskowi możnaprzyporządkować tylko litery zdaniowe. Będą to

różneliteryzdaniowe,alogicznyniejestschemat

Przesłanka 1: p

Przesłanka 2: q

Wniosek: r

Postulatem analizy wewnętrznej struktury zdań kierujemy się

tworzącformalnyjęzykrachunkupredykatów.

53 Wlogicezdańnajmniejsząnieanalizowalnąjednostkąjestzdanie.Teraztaką

jednostkąbędziepredykat.Przezanalogięzterminem„logikazdań”tendziałlo-

giki nazywamy „logiką predykatów”. Podobnie jak mówi się o rachunku zdań,

tak mówi się o rachunku predykatów. Nowymi, w stosunku do języka rachun-

kówzdaniowych,stałymilogicznymisąterazkwantyﬁkatory.Mówisięwięcteżo

rachunkukwantyﬁkatorów.

116

2. KLASYCZNALOGIKAPREDYKATÓW

2.1. JĘZYKRACHUNKU PREDYKATÓW

Wjęzykurachunkupredykatówelementarnymi,wewnętrznienie-

analizowalnymi wyrażeniami będą litery predykatowe, litery funk-

cyjneorazstałeizmienneindywiduowe.Słowa„litera”–podobniejak

wwypadkurachunkuzdań–używamydlazaznaczeniawewnętrznej

nieanalizowalności omawianych wyrażeń. Wśród stałych logicznych

opróczspójnikówzdaniowychbędąkwantyﬁkatory.

2.1.1. Dziedzina

Opis kategorii wyrażeń, z których zbudowane jest zdanie, po-

przedzimyopisemdziedziny,któramabyćprzedmiotemwnioskowań

przeprowadzanychwjęzykuklasycznegorachunkupredykatów.

Przedewszystkimdziedzinataskładasięzpewnegozbioru przed-

miotówindywidualnych ,czyli indywiduów .Naprzykładwarytmetyce

indywiduamisąliczbynaturalne.Jakologicyniemusimysięjednak

martwić tym, czym jest indywiduum. W poprawnie metodologicz-

nie określonej dziedzinie rozważań wyróżniona jest pewnakategoria

przedmiotów jako indywiduów. Zbiór indywiduów danej dziedziny

rozważańto przestrzeń , zbióruniwersalny ,albopoprostu uniwersum .

Ograniczenie się do tylko jednego zbioru uniwersalnego ma miejsce

wprzypadkujęzykajednosortowego.Wwypadku,gdyprzyjmujesię

więcejniżjednouniwersummasiędoczynieniazwielosortowością.

Indywidua mogą pozostawać w pewnych zależnościach, związ-

kach, czy jak będziemy ogólnie mówić – relacjach. W zbiorze liczb

możetobyćnp.relacjamniejszości( < ).

N -tkauporządkowana przedmiotów x 1 ,x 2 ,...,x n ,czyli:

( x 1 ,x 2 ,...,x n )

jestrówna n -tceuporządkowanejprzedmiotów y 1 ,y 2 ,...,y n ,czyli:

( y 1 ,y 2 ,...,y n ) ,

tj.:

( x 1 ,x 2 ,...,x n )=( y 1 ,y 2 ,...,y n )

wtedyitylkowtedy,gdydlakażdego i , 1 ≤ i ≤ n :

2.1. JĘZYK RACHUNKUPREDYKATÓW

117

x i = y i .

Ograniczamysiętutylkodookreśleniarówności n -tekuporządko-

wanych. Deﬁnicja n -tki uporządkowanej wymaga pokazania jeszcze,

żetakiprzedmiotistniejeiżedladanychprzedmiotów a 1 ,...,a n jest

dokładnie jedna n -tka ( a 1 ,...,a n ) . Jest to problem rozwiązywany w

teoriimnogości 53 .

PRZYKŁAD

Równesąpary:

(1 , 2) , (1 , 1+1) ;

różnezaśsąpary:

(1 , 2) , (2 , 1) .

Iloczynemkartezjańskimzbiorów X 1 ,X 2 ,...,X n jestzbiór:

X 1 × X 2 × ... × X n

wszystkich n -tekuporządkowanych ( x 1 ,x 2 ,...,x n ) takich,że:

( x 1 ,x 2 ,...,x n )

} .

Relacją n -członową ,którejkolejnymiczłonamisąelementyzbio-

rów,odpowiednio, X 1 ,X 2 ,...,X n jestdowolnypodzbióriloczynukar-

tezjańskiego X 1 × X 2 × ... × X n .

PRZYKŁADY

Relacjąniejest:

(I) { (1 , 2 , 3) , (1 , 2) } .

Relacjamisą:

1 , 2

}×{

1 , 3

}

{

(1 , 1) , (1 , 3) , (2 , 1) , (2 , 3)

53 Problemy te i dotyczące iloczynu kartezjańskiego oraz relacji podejmiemy

bardziej dokładnie w dziale niniejszej książki poświęconym teorii mnogości. Tu

wprowadzamy pojęcia niezbędne do wykładu logiki predykatów i w sposób dla

tychpotrzebwystarczający.

∈ X 1 × X 2 × ... × X n

wtedyitylkowtedy,gdydlakażdego i , 1 ≤ i ≤ n :

x i ∈ X i .

PRZYKŁAD

{

118

2. KLASYCZNALOGIKAPREDYKATÓW

(II) { (1 , 3 , 2) , (2 , 4 , 3) , (3 , 5 , 4) , (4 , 6 , 5) , (5 , 7 , 6) , (6 , 8 , 7) , (7 , 9 , 8) ,... } . Rela-

cja ta jest podzbiorem N×N×N ,gdzie N jest zbiorem liczb

naturalnych.

(III) Zbiór takich par ludzi, że pierwszy element pary jest krewnym

drugiegoelementupary.

(IV) { ( x,x ): x ∈ X } .

(DEF. Id )Relacja { ( x,x ): x ∈ X } to relacja identyczności wzbiorze

X .Oznaczmyją Id .

Zauważmy,żedladowolnych x,y,z ∈ X :

(I) ( x,x ) ∈ Id ,

(II) jeżeli ( x,y ) ∈ Id ,to ( y,x ) ∈ Id ,

(III) jeżeli ( x,y ) ∈ Id oraz ( y,z ) ∈ Id ,to ( x,z ) ∈ Id .

Orelacji,któraspełniawarunek(I)mówimy,żejest zwrotna .Gdy

spełniawarunek(II),mówimy,żejest symetryczna .Gdyzaśspełnia

warunek(III),tomówimy,żejest przechodnia .Relację,którajestza-

równozwrotna,symetrycznajakiprzechodniaokreślamyjakorelację

równoważności . Relacja identyczności jest więc relacją równoważno-

ści.

Niech R będzierelacją n -członową.Zbiór:

D i =

∈ R }

gdzie 1 ≤ i ≤ n,

to i -ta dziedzina relacji R .Wwypadku n =2 o pierwszej dziedzinie

mówimy,żejest dziedziną ,aodrugiejdziedzinie,żejest przeciwdzie-

dziną relacji R .

Zbiór

P = n

i =1

D i ,

czylizbiórbędącysumąteoriomnogościowąwszystkich i -dziedzin ( i =

1 , 2 ,...,n ) relacji R ,to pole relacji R .

Polemrelacjizpowyższychprzykładów(II)i(III)są,odpowied-

nio, N – zbiór liczb naturalnych i zbiór ludzi.Ale np. 2 -dziedziną z

przykładu(II)jestzbiór { 3 , 4 , 5 ,... } .

{ x i :( x 1 ,...,x i ,...,x n )

2.1. JĘZYK RACHUNKUPREDYKATÓW

119

Szczególnąklasąrelacjisąfunkcje.

Niech R będzierelacją ( n +1) -członową: R ⊆ X 1 × X 2 × ... × X n ×

X n +1 .Relacja R jest n -argumentowąfunkcją wtedyitylkowtedy,gdy

jestonajednoznacznaw ( n +1) -dziedzinie,czyli:

jeżeli

( x 1 ,...,x n ,x n +1 )

∈ R

oraz

( x 1 ,...,x n ,y n +1 )

∈ R ,

x n +1 = y n +1 .

D i , tozbiór,naktórymfunkcjajest określona ,zaśzbiór

D n +1 ,tozbiór wartości funkcji.

PRZYKŁADY

Relacja:

Zbiór n

i =1

{

(1 , 2) , (2 , 2) , (3 , 3) , (4 , 4)

}

jestfunkcją.

Relacja:

{

(1 , 2) , (1 , 3) , (2 , 3)

}

niejestfunkcją.

Zbiór takich par ludzi,że drugielement pary jest matką pierw-

szegoelementuparyjestfunkcją.

Zbiór takich par ludzi, że pierwszy element pary jest dzieckiem

drugiegoelementuparyniejestfunkcją.

} jest relacją identyczności w zbiorze { 1 , 2 } ,niejestzaś

nią w zbiorze { 1 , 2 , 3 } . W wypadku zbioru { 1 , 2 , 3 } nie jest bowiem

spełnionywarunek(I)–dladowolnych x ∈{ 1 , 2 , 3 } : ( x,x ) ∈ Id .Funk-

cja { (1 , 1) , (2 , 2 , ) } jestnazbiór { 1 , 2 } adozbioru { 1 , 2 , 3 } .

2.1.2. Stałei zmienne indywiduowe

Zauważmy,żeopisrelacji,wszczególnościfunkcjiwymagawska-

zania iloczynu kartezjańskiego, którego jest ona podzbiorem. Zbiór

{

(1 , 1) , (2 , 2)

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: