mad2008 1

mad2008 1, LOGIKA, Tautologia

[ Pobierz całość w formacie PDF ]
Metodydowodzenia
1
twierdzeń
Przezzdanierozumiemydowolnestwierdzenie,kt
ó
rejestalboprawdziwe,albofa“szywe(nie
mo»eby¢onojednocze–nieprawdziweifa“szywe).Tradycyjniebƒdziemyu»ywalima“ychliter
p, q, r, . . .jakozmiennychzdaniowych,toznaczy,zmiennychreprezentuj¡cychdowolnezdania,
oraznastƒpuj¡cychsp
ó
jnik
ó
wmiƒdzyzdaniowych:∧(koniunkcja),∨(alternatywa),⇒(implika-
cja),⇔(r
ó
wnowa»no–¢),¬(negacja).
Wpierwszymparagra
etegorozdzia“uinteresowa¢nasbƒdzieprawdziwo–¢zdaniap⇒q
(je»elip,toq).Wtymprzypadkum
ó
wimy,»epjestwarunkiemdostatecznymdlaqlub,»eqjest
warunkiemkoniecznymdlap.Stwierdzenie,»epjestwarunkiemkoniecznymidostatecznymdla
qjesttymsamym,costwierdzenieprawdziwo–cir
ó
wnowa»no–cip⇔q(pwtedyitylkowtedy,
gdyq).
1.1.Metodydowoduimplikacji
Przypomnijmy,i»implikacjap⇒q jestfa“szywawtedyitylkowtedy,gdyjejpoprzednikp
jestprawdziwy,anastƒpnikqjestfa“szywy;wpozosta“ychtrzechprzypadkachimplikacjajest
zdaniemprawdziwym.
Dow
ó
dwprost
Metodadowoduwprostpoleganaza“o»eniu,»epjestprawd¡ipokazaniu,»ew
ó
wczasqjest
prawd¡.
Przyk“ad1.1.Udowodni¢wprost,»eje»eliajesttak¡liczb¡ca“kowit¡,»ea−4jestpodzielne
przez5,toa
3
+ 1jestpodzielneprzez5.
Przyk“ad1.2.Udowodni¢wprost,»eje»elixjesttak¡liczb¡rzeczywist¡,»ex
2
−3x−10 = 0,
tox =−2lubx = 5.
Dow
ó
dniewprost
Metodadowoduniewprostopierasiƒnanastƒpuj¡cejtautologiirachunkuzda«,zwanejprawem
kontrapozycji:
(p⇒q)⇔(¬q⇒¬p).
Zatemstosuj¡ctƒmetodƒzak“adamy,»eqjestzdaniemfa“szywymipokazujemy,»epjestr
ó
wnie»
zdaniemfa“szywym.
Przyk“ad1.3.Udowodni¢niewprost,»eje»eliiloczyndw
ó
chliczbca“kowitychaibjestliczb¡
parzyst¡,toajestliczb¡parzyst¡lubbjestliczb¡parzyst¡.
4 1.Metodydowodzeniatwierdze«
Przyk“ad1.4.Udowodni¢niewprost,»eje»elinjestiloczynemdw
ó
chdodatnichliczbca“kowi-
tychaib,toa 6
nlubb 6
√
n.
Dow
ó
dprzezzaprzeczenie
Przypomnijmyinneznanepraworachunkuzda«
(p⇒q)⇔(¬p∨q).
Stosuj¡cdojegoprawejstronyprawoDeMorgana,otrzymujemyr
ó
wnowa»no–¢
(p⇒q)⇔¬(p∧¬q) ,
nakt
ó
rejopierasiƒmetodadowoduprzezzaprzeczenie(zwanegotak»edowodemprzezsprowa-
dzeniedosprzeczno–ci).Stosuj¡ctopodej–ciezak“adamy,»epjestprawd¡aqfa“szemipokazu-
jemy,»eprowadzitodosprzeczno–ci,toznaczy,pokazujemy»e(p∧¬q)jestfa“szem.
Przyk“ad1.5.Udowodni¢przezzaprzeczenie,»espo–r
ó
dtrzynastuludzidw
ó
chlubwiÆ’cejma
swojeurodzinywtymsamymmiesi¡cu.
Przyk“ad1.6.Udowodni¢przezzaprzeczenie,»eje»eliwybrano41kulzszu
adkizawieraj¡cej
kuleczerwone,bia“e,niebieskie,zielonei»
ó
“te(zak“adamy,»ewka»dymkolorzejestwiƒcejkul
ni»wybieramy),toconajmniej12kuljestczerwonychlubconajmniej15kuljestbia“ych,lub
conajmniej4kules¡niebieskie,lubconajmniej10kuljestzielonych,lubconajmniej4kules¡
»
ó
“te.Poda¢dow
ó
dtegofaktuprzezzaprzeczenie.
1.2.Zasadaindukcjimatematycznej
Niechp(n)bÆ’dziezdaniem,kt
ó
redlaka»degonaturalnegonmo»eby¢zdaniempraw-
dziwymlubfa“szywym.Abyudowodni¢,»ezdaniep(n)jestprawdziwedlawszystkich
liczbnaturalnychn,gdzien > n
0
,wystarczypokaza¢,»e
(a)zdaniep(n
0
)jestprawdziwe,
(b)dlaka»degok > n
0
,
p(k)⇒p(k + 1), (1.1)
tzn.zdaniep(k + 1)jestprawdziweje»elitylkozdaniep(k)jestprawdziwe.
Warunek(a)nazywasiƒwarunkiempocz¡tkowym.Za“o»enie,»ep(k)jestprawdziwenazywa
siƒza“o»eniemindukcyjnym,ap(k + 1)tez¡indukcyjn¡,za–samaimplikacja(1.1)krokiemin-
dukcyjnym.
Przyk“ad1.7.Znale„¢iudowodni¢wz
ó
rnasumÆ’pierwszychnliczbnaturalnych.
Przyk“ad1.8.Znale„¢iudowodni¢wz
ó
rnasumƒsze–cian
ó
wnpierwszychliczbnaturalnych,
tzn.nasumÆ’
1
3
+ 2
3
+ . . . + n
3
.
Przyk“ad1.9.Pokaza¢,»edlaka»degonaturalnegon,wyra»enie
6
n+2
+ 7
2n+1
jestpodzielneprzez43.
√
1.3.Zasadaszu
adkowa
5
Przyk“ad1.10.Pokaza¢,»edlaka»degonaturalnegon > 4,
3
n
> n
3
.
Przyk“ad1.11.Pokaza¢,»esumanpierwszychwyraz
ó
wci¡guarytmetycznegoopierwszym
wyrazieaior
ó
»nicyd,r
ó
wnajest
1
2
n (2a + (n−1)d) .
Zasadƒindukcjimatematycznejmo»nasformu“owa¢nawieler
ó
wnowa»nychsposob
ó
w.Poni»ej
podamyinn¡,czƒstowykorzystywan¡wersjƒtejzasady,kt
ó
r¡nastƒpnieu»yjemywPrzyk“a-
dzie1.12.
Niechp(n)bÆ’dziezdaniem,kt
ó
redlaka»degonaturalnegonmo»eby¢zdaniempraw-
dziwymlubfa“szywym.Abyudowodni¢,»ezdaniep(n)jestprawdziwedlawszystkich
liczbnaturalnychn,gdzien > n
0
,wystarczypokaza¢,»e
(a)zdaniep(n
0
)jestprawdziwe,
(b)dlaka»degok > n
0
,
(p(n
0
)∧p(n
0
+ 1)∧∧p(k))⇒p(k + 1)
tzn.zdaniep(k+1)jestprawdziweje»elitylkowszystkiezdaniap(i)s¡prawdziwe
dlan
0
6 i 6 k.
Przyk“ad1.12.Pokaza¢,»eje»elis¡spe“nionewarunkia
0
= 12, a
1
= 29(nazywanepocz¡tko-
wymi)orazdlan > 2zachodziwz
ó
r
a
n
= 5a
n
−
1
−6a
n
−
2
(nazywanywzoremrekurencyjnym),todlaka»degonaturalnegon
a
n
= 53
n
+ 72
n
.
1.3.Zasadaszu
adkowa
Zasadaszu
adkowa(znanate»jakozasadaszu
adkowaDirichleta)poleganaprostejobserwacji,
»eje»elirozmie–cimynprzedmiot
ó
wwmszu
adkach,gdzien > m,toistniejeszu
adka,kt
ó
ra
zawieraconajmniejdwaprzedmioty.Og
ó
lniej:
Je»elirozmie–cimynprzedmiot
ó
wwmszu
adkach,przyczymn > km(k∈
N),to
wkt
ó
rej–szu
adceznajdziesiÆ’conajmniejk + 1przedmiot
ó
w.
Przyk“ad1.13.Uzasadni¢,»ewka»dymmie–cielicz¡cymconajmniej1,7milionamieszka«c
ó
w
znajdziemyconajmniejpiĢos
ó
botejsamejliczbiew“os
ó
wnag“owie,je»eliprzyjmiemy,»e
ro–nieichnaludzkiejg“owieconajwy»ej400000.
Przyk“ad1.14.Wturniejupi“karskim,wkt
ó
rymdocelowoka»dadru»ynamazagra¢zka»d¡
inn¡bierzeudzia“nzespo“
ó
w.Uzasadni¢,»ewdowolnymmomencietrwaniaturniejuznajd¡siƒ
dwiedru»yny,kt
ó
rerozegra“ydotegomomentutƒsam¡liczbƒmecz
ó
w.
6 1.Metodydowodzeniatwierdze«
Przyk“ad1.15.Pokaza¢,»eje»eliwtr
ó
jk¡cier
ó
wnobocznymobokud“ugo–ci4umie–cimy17
punkt
ó
w,toznajdziemydwapunkty,miÆ’dzykt
ó
rymiodleg“o–¢nieprzekracza1.
Przyk“ad1.16.Pokaza¢,»ew–r
ó
dn + 1dowolnychliczbca“kowitychznajd¡siƒdwie,kt
ó
rych
r
ó
»nicadzielisiƒprzezn.
Przyk“ad1.17.Ka»dedwawierzcho“kisze–ciok¡taforemnegopo“¡czonoodcinkiemzielonym
lubczerwonym.Wykaza¢,»ezosta“narysowanyconajmniejjedentr
ó
jk¡tobokachtegosamego
koloru.
1.4.Zadania
Zadanie1.1.Udowodni¢wprost,»eje»eliaibs¡nieparzystymiliczbamica“kowitymi,toa + b
jestparzyst¡liczb¡ca“kowit¡.
Zadanie1.2.Udowodni¢niewprost,»edladowolnejliczbynaturalnejn,je»elin
2
jestliczb¡
nieparzyst¡,tonte»jestliczb¡nieparzyst¡.
Zadanie1.3.Niechnbƒdzietak¡liczb¡naturaln¡,»en > 1 i nniejestliczb¡pierwsz¡.
Udowodni¢przezsprowadzeniedosprzeczno–ci,»enposiadaconajmniejjedendzielnikpierwszy
n.
Zadanie1.4.Udowodni¢,»edlaka»degonaturalnegon
(a)1
2
+ 2
2
+ 3
2
+ . . . + n
2
=
n(n+1)(2n+1)
(c)123 + 234 + . . . + n(n + 1)(n + 2) =
n(n+1)(n+2)(n+3)
4
.
Zadanie1.5.Udowodnijprzezindukcjƒ,»edlaka»degon∈
N
11! + 22! + 33! ++ nn! = (n + 1)!−1.
Zadanie1.6.Udowodni¢,»edlaka»degoca“kowitegon > 0wyra»enie
11
n+2
+ 12
2n+1
jestpodzielneprzez133.
Zadanie1.7.Udowodni¢,»esumanpierwszychwyraz
ó
wci¡gugeometrycznegoopierwszym
wyrazieaioilorazieq(q = 1)r
ó
wnajest
a(1−q
n
)
1−q
.
Zadanie1.8.Udowodni¢,»eje»elia
0
= 6, a
1
= 11orazdlan > 2
a
n
= 3a
n
−
1
−2a
n
−
2
,
todlaka»degon > 0
a
n
= 52
n
+ 1 .
Zadanie1.9.Grupa41student
ó
wzaliczy“asesjƒsk“adaj¡c¡siƒztrzechegzamin
ó
w,wkt
ó
rych
mo»liwymiocenamiby“ybdb,dbidst.Wykaza¢,»econajmniejpiƒciorostudent
ó
wzaliczy“o
sesjÆ’zjednakowym
zbiorem
ocen.
Zadanie1.10.Wka»depoleszachownicyn×nwpisujemyjedn¡zliczb:−1, 0, 1.Nastƒpnie
dodajemydosiebieliczbystoj¡cewtymsamymwierszu,wtejsamejkolumnieinatejsamej
przek¡tnej.Pokaza¢,»ew–r
ó
dotrzymanychsumconajmniejdwies¡r
ó
wne.
ptaki,»ep≤
√
6
,
(b)1
3
+ 3
3
+ 5
3
+ . . . + (2n−1)
3
= n
2
(2n
2
−1),
1.4.Zadania
7
Zadanie1.11.Pokaza¢,»edladowolnychn + 1r
ó
»nychdodatnichliczbca“kowitychmniejszych
b¡d„r
ó
wnych2nistniej¡dwie,kt
ó
resumuj¡siƒdo2n + 1.
Zadanie1.12.Pokaza¢,»edladowolnychn + 1r
ó
»nychdodatnichliczbca“kowitychmniejszych
b¡d„r
ó
wnych2nistniej¡dwie,kt
ó
res¡wzglƒdniepierwsze.
Zadanie1.13.Pokaza¢,»edladowolnychndodatnichliczbca“kowitychistniejepodzbi
ó
r,kt
ó
-
regosumaliczbjestpodzielnaprzezn.
Zadanie1.14.NiechAbÆ’dziedwudziestoelementowympodzbioremzbioru{1, 4, 7, 10, 13, . . .,
100}.Udowodnij,»eAzawieradwier
ó
»neliczby,kt
ó
rychsumajestr
ó
wna104.
Zadanie1.15.NiechdlaustalonegonnaturalnegoAbÆ’dziepodzbioremmocyn + 1zbioru
[2n].Udowodni¢,»eAzawieradwier
ó
»neliczbyaib,takie»eajestdzielnikiemb.
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

mement.xlx.pl