Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
84
2.Elementylogiki
Dlan∈Nniechq(n)będziezdaniem„(n+1)2=n2+2n+1”.
Możemyużywaćp(n),q(n)ispójnikówlogicznychzrachunku
zdań,abyotrzymaćinnezdaniazkwantyfikatorami.Naprzy-
kład∃n(¬q(n))jestzdaniemfałszywym;każdezdanieq(n)jest
prawdziwe,awięckażdezdanie¬q(n)jestfałszywe.Zdanie
∀n(p(n)∨q(n))jestprawdziwe,ponieważkażdezdaniep(n)∨q(n)
jestprawdziwe.(Pamiętajmy,żeznak∨oznacza„lub”).Oczywi-
ściezdaniesłabsze∃n(p(n)∨q(n))teżjestprawdziwe.
(b)Niechp(x)oznacza„x≤2x”,aq(x)oznacza„x2≥0”dla
x∈R.PonieważelementówzbioruRniemożnawypisaćwpo-
staciciągu,byłobyzupełnieniemożliwezapisaniesymbolicznie
zdań∃xp(x)czy∀xq(x)wrachunkuzdań.Jasnejest,żezdanie
∃xp(x)jestprawdziwe;zdanie∀xp(x)jestfałszywe,ponieważ
zdaniep(x)jestfałszywedlaxujemnych.Obazdania∀xq(x)
i∃xq(x)sąprawdziwe,azdanie∃x(¬q(x))jestfałszywe.
(c)Kwantyfikatorysąrównieżprzydatnewtedy,gdymamydo
czynieniazeskończonymi,aledużymizbioramizdań.Przypuśćmy
np.,żemamyzdaniap(n)dlanzezbioru{n∈N:0≤n≤65535}.
Wolimyoczywiściezapis∀np(n)zamiast
p(0)∧p(1)∧p(2)∧p(3)∧...∧p(65535),
chociażmoglibyśmywprowadzićteoretyczniedopuszczalnyzapis
65535
n=o
p(n).
(d)HipotezaGoldbachamożebyćterazzapisanajako∀np(n),
gdziep(n)=„jeśliliczbanzezbioruNjestparzystaiwiększa
od4,tonjestsumądwóchliczbpierwszych”.
PRZYKŁAD11
(a)Kwantyfikatory∀i∃sąużywaneczęstonieformalniejako
skróty.Pierwszedwazdaniazprzykładu2mogłybybyćzapisane
wpostaci„x+y=y+x∀x,y∈R”oraz„∃n∈Ntakie,że
2n=n2”.
(b)Wpraktyceczęstoopuszczamyoczywistekwantyfikatory.
PrawałącznościiskracaniadladziałańwzbiorzeRczęstozapi-
sujemywpostaci
(Ł)
(S)
(x+y)+z=x+(y+z),
xz=yz
oraz
z/=0implikujex=y.
Mamynamyślioczywiście
(Ł)
(S)
∀x∀y∀z[(x+y)+z=x+(y+z)],
∀x∀y∀z[(xz=yz∧z/=0)→x=y],
