06.pdf

(302 KB) Pobierz
c:\3\6.dvi
2.2. KLASYCZNYRACHUNEKPREDYKATÓW
Podamydefinicjędowoduwrachunkupredykatów.Dowódwra-
chunkupredykatówróżnisięoddowoduwrachunkuzdańtylkodo-
datkowymi możliwościami. Ujmująonewiększe bogactwo językara-
chunkupredykatówwstosunkudojęzykarachunkuzdań.
2.2.1. Dowód w rachunku predykatów
(DEF.tautologiijęzykarachunkupredykatów) Tautologią językara-
chunku predykatów jest każda formułatego języka otrzymana z ja-
kiejśtautologii α językarachunkuzdańprzezpodstawieniezakażdą
literęzdaniowąwystępującąw α ,jakiejśformułyjęzykarachunkupre-
dykatów (jednocześnie w każdym miejscu dla wszystkich wystąpień
danejliteryzdaniowej).
Oprócztautologiibędziemymieliaksjomaty(teorii)identyczno-
ści( ≡ )
Id1. v ≡ v
Id2. v i ≡ v ⇒ Fv 1 ...v i − 1 v i v i +1 ...v n ≡ Fv 1 ...v i − 1 vv i +1 ...v n ,
gdzie F jest n -argumentowąliterąfunkcyjną,a n> 0
Id3. ( v i ≡ v ∧ Pv 1 ...v i − 1 v i v i +1 ...v n ) ⇒ Pv 1 ...v i − 1 vv i +1 ...v n
gdzie P jest n -argumentowąliterąpredykatową,a n> 0 .
Zauważmy,żeaksjomatówId1jesttyle,ilejestzmiennychindy-
widuowych,–Id2jesttyle,ilejestwszystkichkombinacjiliterfunk-
cyjnychizmiennychindywiduowych,aaksjomatów Id3tyle, ilejest
kombinacjiliterpredykatowychizmiennychindywiduowych.
Rachunek predykatów można budować dla języka nie zawiera-
jącego predykatu identyczności 56 . Predykat identyczności jest pre-
dykatem używanym w zasadzie we wszystkich językach (teoriach)
56 Predykatidentycznościmożebyćzdefiniowany.Możliwetojestnp.wjęzyku,
wktórymwystępujązmiennepredykatowe(
n
-argumentowazmiennapredykatowa
przebiegaklasęwszystkich itylkorelacji
n
-członowych,dającychsięutworzyćw
1716889.002.png
132
2. KLASYCZNALOGIKAPREDYKATÓW
mających praktyczne znaczenie. Dlatego też jest celowe budowanie
rachunkulogicznegodlajęzykazawierającegotenpredykat.
Zależy nam na syntaktycznym scharakteryzowaniu pojęcia wy-
nikania rzeczywistego (definicja wynikaniarzeczywistego jako wyni-
kania semantycznego podana zostanie później). Musimy więc spre-
cyzowaćpojęciedowodu.Zbiórregułdowodowychwrachunkuzdań
wzbogacamyonoweregułydowodzenia.Opróczregułyodrywania
REGUŁAODRYWANIA
MP. z ϕ i ϕ ⇒ φ wynika φ ,
mamyjeszcze
REGUŁAPODSTAWIANIA
zbiorzeuniwersalnym)orazmożliwajestkwantyfikacjapotychzmiennych(język
drugiegorzędu).JużuArystotelesaspotykamysięzmyślą,żeprzedmiotomiden-
tycznymprzysługujątesamewłasności.Wedługokreśleniaśw.TomaszazAkwinu
identyczne są takie przedmioty, że cokolwiek przysługuje jedenemu z nich przy-
sługuje też drugiemu. Autorem pewnej definicji identyczności jest Leibniz. Jest
ona znana jakozasada identyczności przedmiotów nieodróżnialnych ( principium
identitatisindiscernibilium ).Zasadętęmożnabysformułowaćnastępująco
x ≡ y
wtedyitylkowtedy,gdy
dlakażdego
P.Px ⇔ Py ,
jest zmienną predykatową,której zakresem jest zbiór wszystkich relacji
jednoczłonowych.
Gdyby uznać, że sprawa odróżnialności bądź nieodróżnialności jest sprawą
języka, z którego korzystamy przy opisie, to identyczność można by zdefiniować
następująco
P
x ≡ y
.
Tymrazemma miejsce kwantyfikacja,którejzakresem jestzbiórjednoargumen-
towychliterpredykatowych,aniejakpowyżejzbiórrelacjijednoczłonowych.Tę
definicjęmożnazapisaćjakoschematformuł.Takiesformułowaniejakopierwszy
podałPeirce w1885r.Pozamieszczeniu jejw Principia Mathematica Whitehe-
adaiRussellazostałaspopularyzowanainiekiedynazywasięjąrussellowskąlub
leibnizowsko-russellowskądefinicjąidentyczności.Definicjatadajepodstawyzna-
czącej dla matematyki regule zastępowania równych (regułytej nienależy mylić
zregułąpodstawiania).Więcej natentematzob.Tarski[1994],s.56–65.
P.Px ⇔ Py
gdzie
wtedyitylkowtedy,gdy
dladowolnejjednoargumentowejliterypredykatowej
1716889.003.png
2.2. KLASYCZNYRACHUNEK PREDYKATÓW
133
Sb. z ϕ wynika ϕ ( v/t ) , o ile term t jest podstawialny w miejsce
zmiennej v
REGUŁAOPUSZCZANIADUŻEGOKWANTYFIKATORA
O ∀ .z ϕ ⇒∀ v.φ wynika ϕ ⇒ φ
REGUŁADOŁĄCZANIADUŻEGOKWANTYFIKATORA
D ∀ .z ϕ ⇒ φ wynika ϕ ⇒∀ v.φ ,jeżeli v niejestzmiennąwolnąw ϕ
REGUŁAOPUSZCZANIAMAŁEGOKWANTYFIKATORA
O ∃ .z ∃ v.ϕ ⇒ φ wynika ϕ ⇒ φ
REGUŁADOŁĄCZANIAMAŁEGOKWANTYFIKATORA
D ∃ .z ϕ ⇒ φ wynika ∃ v.ϕ ⇒ φ ,jeżeli v niejestzmiennąwolnąw φ .
Oczywiścieregułysątakdobrane,żebyzachowywałyrzeczywisty
stosunek wynikania. Stosujemy je do formuł, które nie muszą być
zdaniami.Mówieniewięcoprawdziwościwyrażeń,doktórychreguły
sąstosowaneniejestzasadne.Zamiastterminu„prawda”możemytu
użyćogólniejszegoterminu„spełnianie”.Będzietotermintechniczny
logiki, jegościsłeznaczenie określimy wdalszej części rozważań. Na
tymetapiewystarczykierowaćsięjegointuicyjnymznaczeniem.
Reguła podstawiania odpowiada sposobowi takiego rozumowa-
nia,gdynp.mającformułę 57
x 2 ≥
0
przyjmujemy
(
y
+1) 2 ≥
0
0 .
Obieotrzymaneformułysąspełnionewzbiorzeliczbrzeczywistych.
Pierwszadlawszystkichmożliwychznaczeń,jakiemożeprzyjmować
zmienna y w zbiorze liczb rzeczywistych, zaś druga nie zawierając
zmiennychjestpoprostuprawdziwa.
2 2 ≥
57 Wyrażającą prawdziwą zależność w zbiorze liczb rzeczywistych, tj. praw-
dziwąpozwiązaniuprzezdużykwantyfikatorwszystkichzmiennychwolnych,czyli
spełnioną dla dowolnego znaczenia, jakie możemy przyporządkować zmiennej
x
wzbiorzeliczb rzeczywistych.
1716889.004.png
134
2. KLASYCZNALOGIKAPREDYKATÓW
Sposób rozumowania odpowiadający regule opuszczania dużego
kwantyfikatorastosujemywówczas,gdynapodstawie
a>
0
⇒∀ x.
x>
0
⇒ x
+
a>
0)
uznajemy
a>
0
⇒
(
x>
0
⇒ x
+
a>
0) .
Regułę dołączania dużego kwantyfikatora stosujemy wówczas,
gdynapodstawie
y>
0
⇒
(
x>
0
⇒ x
+
y>
0)
uznajemy
0) .
Warunek nałożony na poprzednik ( ϕ ) implikacji, do której na-
stępnika( φ ) dołączamy duży kwantyfikator jest istotny. Na podsta-
wie
y>
0
⇒∀ x.
(
x>
0
⇒ x
+
y>
y>
0
⇒
(
x>
0
⇒ x
+
y>
0)
niemożemyuznać
y>
0
⇒∀ y.
(
x>
0
⇒ x
+
y>
0) 58 .
Regule opuszczania małego kwantyfikatora odpowiada rozumo-
wanie,gdynapodstawie
∃ x.
(0
<x ∧ x ≤ y
)
⇒
0
<y
uznajemy
<y .
Sposób rozumowania odpowiadający regule dołączania małego
kwantyfikatoramożemyzastosowaćdo
0
0
<x ∧ x ≤ y ⇒
0
<x ∧ x ≤ y ⇒
0
<y .
58 Wtymwypadkukolidowałobytozregułąpodstawiania.Mianowiciezgodnie
z tąregułą za zmienną wolną
y
∀ y.
(
x>
0
⇒ x
+
y>
0) .Podsta-
, lub po prostu wiążąc ją dużym kwan-
tyfikatoremotrzymujemy zdanie fałszywe. Tymczasem formuła:
x
y>
0
⇒
x>
0
⇒ x
+
y>
0) jestspełniona.
(
moglibyśmy podstawić dowolnąliczbę dodatnią
istosującregułę odrywaniaotrzymalibyśmy:
wiając zaś dowolną liczbę za zmienną
(
1716889.005.png
2.2. KLASYCZNYRACHUNEK PREDYKATÓW
135
Warunek nałożony na następnik ( φ ) implikacji, do której po-
przednika ( ϕ ) dołączamy mały kwantyfikator jest istotny. Na pod-
stawie
x ≥
0
⇒
(
y>x ⇒ y>
0)
niemożemyuznać
∃ x.
(
x ≥
0)
⇒
(
y>x ⇒ y>
0) .
DEFINICJADOWODUWRACHUNKUPREDYKATÓW
Formuła ϕ ma dowód zezbioru Σ formułjęzykarachunkukwan-
tyfikatorów–cozapisujemy: Σ ϕ –wtedyitylkowtedy,gdyistnieje
skończonyciągformuł ϕ 0 ,ϕ 1 ,...,ϕ n taki,że
ϕ n =
orazdlakażdego i (0 ≤ i ≤ n ) spełnionyjestjedenzwarunków
(I) ϕ i jestelementem Σ ,
(II) ϕ i jesttautologią(językarachunkupredykatów),
(III) ϕ i jestaksjomatem(teorii)identyczności,
(IV) istnieją ϕ j , ϕ k takie,że ϕ k = ϕ j ⇒ ϕ i ; j,k<i ,
(V) istnieją ϕ k ,k<i ,orazterm t izmienna v takie, że t jestpod-
stawialneza v wformule ϕ k i ϕ k ( v/t )= ϕ i ,
(VI) istnieje ϕ k ,k<i ,takie,że ϕ k = φ ⇒∀ v.ψ oraz ϕ i = φ ⇒ ψ ,
(VII) istnieje ϕ k ,k<i ,takie,że ϕ k = φ ⇒ ψ izmienna v niewystępuje
jakozmiennawolnaw φ oraz ϕ i = φ ⇒∀ v.ψ ,
(VIII) istnieje ϕ k ,k<i ,takie,że ϕ k = ∃ v.φ ⇒ ψ oraz ϕ i = φ ⇒ ψ ,
(IX) istnieje ϕ k ,k<i ,takie,że ϕ k = φ ⇒ ψ izmienna v niewystępuje
jakozmiennawolnaw ψ oraz ϕ i = ∃ v.φ ⇒ ψ .
Podanadefinicjadowodujestjednązmożliwychdefinicji.Istnieją
innejejrównoważnewtymsensie,żeniezależniektórąztychdefinicji
ϕ ,
gdzie„=”jestskrótemdla„jestrównokształtnez”
1716889.001.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin