Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
FormatakajestklasyP,gdyprzyjmiemyX1Y1NlubX1NjY1[0j1];jestklasyF,gdy
X1{
1
2}jY1(0j
1
2);jestklasyT,gdyprzyjmiemyX1Y1(0j1).
Przykład1.3Podobnie,jakwprzypadkurachunkuzdań,możemymówićtakżeorachunku
kwantyfikatorów.Dlaprzykładuuzasadnimy,żeschemat
∀x∈X(0(x)1⇒w(x))1⇒(∀x∈X0(x)1⇒∀x∈Xw(x))
jestprawemrachunkukwantyfikatorów.
(1.6)
Rozwiązanie
Dowódprzeprowadzimymetodąniewprost,tzn.przypuszczamy,żeistniejetakiewartościowanie,
przyktórymschemat(1.6)niejestzdaniemprawdziwym,coimplikuje:
w(∀x∈X(0(x)1⇒w(x)))11
oraz
w(∀x∈X0(x)1⇒∀x∈Xw(x))10.
Napodstawie(1.8)stwierdzamy,że
w(∀x∈X0(x))11j
w(∀x∈Xw(x))10
(1.7)
(1.8)
zczegownioskujemy,że0(x)jestklasyP,aw(x)klasyFlubT.Ztegowynika,żeformazdaniowa
0(x)1⇒w(x)jestklasyFlubTidalej
w(∀x∈X(0(x)1⇒w(x)))10j
coprowadzidosprzecznościz(1.7).Tokończydowód.
Przykład1.4Uzasadnimy,żewyrażenie
(∀x∈X0(x)1⇒∀x∈Xw(x))1⇒∀x∈X(0(x)1⇒w(x))
niejestprawemrachunkukwantyfikatorów.
Rozwiązanie
WtymcelurozważmyX1Rorazformyzdaniowe0(x):x<0j
zdaniowesąklasyT,skąd0(x)1⇒w(x)jestklasyT,azatem
(1.9)
w(x):x>0.Obieformy
w(∀x∈X(0(x)1⇒w(x)))10
oraz
w(∀x∈X0(x)1⇒∀x∈Xw(x))11
gdyż
w(∀x∈X0(x))10j
w(∀x∈Xw(x))10.
Zależności(1.10)i(1.11)dająnam
w[(∀x∈X0(x)1⇒∀x∈Xw(x))1⇒∀x∈X(0(x)1⇒w(x))]10.
Tooznacza,żepodanyschematniejestprawemrachunkukwantyfikatorów.
13
(1.10)
(1.11)