wykład_semestr1.pdf

1.WIADOMO ´ SCIWSTE , PNE.

1.1.Rachunekzda´n.

WmowiepotocznejformuÃlujemytakiezdania,okt´orychmo˙zemypowiedzie´c,˙ze

sa , prawdziweba , d´zfaÃlszywebezwzgle , dunato,jakajestaktualnasytuacjaw

otaczaja , cymnas´swiecie.NaprzykÃladzdanie:”Je´slidzi´sjest´sroda,tojutro

be , dzieczwartek”jestprawdziwe,azdanie:”3jestliczba , parzysta , ”jestfaÃlszywe.

Natomiastocenaprawdziwo´scizdania:”MatematykajestÃlatwa”zale˙zyju˙zod

subiektywnegoodczuciaosobyjewypowiadaja , cej.Wdalszymcia , gube , da , nas

interesowaÃlyzdaniapierwszegorodzaju.Przyjmiemynaste , puja , ceoznaczeniai

deﬁnicje.

Deﬁnicja1.1.1. Zdaniem nazywamywlogicewypowied´zorzekaja , ca , ,kt´orej

mo˙znaprzypisa´cjedna , zdw´ochocen:prawde , lubfaÃlsz.

Prawdziwo´s´cifaÃlszywo´s´cnazywamy warto´sciamilogicznymizdania.

Prawde , oznaczamycyfra , 1,afaÃlszcyfra , 0.

Zdaniabe , dziemyoznacza´csymbolami p;q;r;s ,awarto´s´clogiczna , zdania w ( p ).

W´owczas w ( p )=0oznacza,˙zezdanie p jestfaÃlszywe,a w ( q )=1oznacza,˙ze

zdanie q jestprawdziwe.

Zdanychzda´nmo˙zemyprzypomocysp´ojnik´ow”i”,”lub”,”je´sli...,to...”,

”wtedyitylkowtedy,gdy...”,”nie”tworzy´cnowezdania.Sp´ojnikitenazywamy

funktoramizdaniotw´orczymi .

Funktoryzdaniotw´orczeoznaczamynaste , puja , cymisymbolamiinadajemyim

odpowiednionazwy

”nie” » negacja

”lub” _ alternatywa

”i” ^ koniunkcja

”je´sli...,to...” ) implikacja

”wtedyitylkowtedy,gdy...” , r´ownowa˙zno´s´c

Zesp´ojnik´owizda´nprostychmo˙zemytworzy´czdaniazÃlo˙zone.Namocy

przyje , tychpoprzedniooznacze´ndeﬁnicje , sp´ojnik´owmo˙zemyzapisa´cprzyu˙zyciu

naste , puja , cejtabelki

p q»pp^qp_qp)qp,q

11 0 1 1 1 1

01 1 0 1 1 0

10 0 0 1 0 0

00 1 0 0 1 1

Zbudowaneprzyu˙zyciuzmiennychzdaniowych,funktor´owzdaniotw´orczych

oraznawias´owwyra˙zeniarachunkuzda´nnazywamytak˙zeformuÃlamirachunku

zda´nalboschematamirachunkuzda´n.Ka˙zdaformuÃlastajesie , zdaniem,gdyw

miejscewyste , puja , cychwniejliterpodstawiamyzdania.W´sr´odwszystkichformuÃl

rachunkuzda´nszczeg´olniewa˙zna , role , peÃlnia , tautologie.

Deﬁnicja1.1.2.ZdanieprawdziwebezwzgÃledunawarto´scilogicznezda´nskÃla-

dowychnazywamy tautologia , .

Wa˙znymzagadnieniemrachunkuzda´njestsprawdzenie,czydanaformuÃlajest

tautologia , .Najcze , ´sciejstosowana , metoda , badaniawarto´scilogicznejwyra˙ze´n

rachunkuzda´njest metodazero-jedynkowa .Polegaonanarozpatrzeniuwszyst-

kichukÃlad´owwarto´scilogicznychzmiennychzdaniowychwyste , puja , cychwdanym

wyra˙zeniu.Metode , ta , zilustrujemynaste , puja , cymprzykÃladem.

PrzykÃlad1.1.1.Sprawdzi´cczywyra˙zenie

¡ p)q ¢ )

h ¡ q)r ¢ ) ¡ p)r ¢ i

jesttautologia , .

pqrp)qq)rp)r ( q)r ) ) ( p)r )( p)q ) ) [( q)r ) ) ( p)r )]

111 1 1 1 1 1

110 1 0 0 1 1

101 0 1 1 1 1

011 1 1 1 1 1

100 0 1 0 0 1

010 1 0 1 1 1

001 1 1 1 1 1

000 1 1 1 1 1

Zadanie1.1.1.Sprawdzi´cczypodanezdaniasa , tautologiami

p) ¡ q)r ¢ i

h ¡ p)q ¢ ) ¡ p)r ¢ i

)

c) p) ¡ »p)q ¢ ,

d) ¡ »p)q ¢ )p ,

e) ¡ p_q ¢ , ¡ »p)q ¢ ,

f) ¡ p^q ¢ , ¡ p)»q ¢ ,

g) » ¡ p^q ¢ , ¡ »p_»q ¢ -prawodeMorgana,

a) p) ¡ q)p ¢ ,

h) » ¡ p_q ¢ , ¡ »p^»q ¢ -prawodeMorgana,

p^ ¡ q_r ¢ i

h ¡ p^q ¢ _ ¡ p^r ¢ i

-praworozdzielno´scikoniunkcjiwzgle , dem

alternatywy,

p_ ¡ q^r ¢ i

h ¡ p_q ¢ ^ ¡ p_r ¢ i

-praworozdzielno´scialternatywywzgle , dem

koniunkcji.

Interptretacjaﬁzycznakoniunkcjiialternatywy.

Niech p , q oznaczja , wyÃla , czniki,zkt´orychka˙zdymo˙zeby´cwÃla , czony(stan1)albo

wyÃla , czony(stan0).Wstanie”1”wyÃla , cznikprzewodzipra , d,natomiastwstanie

”0”wyÃla , czniknieprzewodzipra , du.StanukÃladuutworzonegoprzezpoÃla , czenie

szeregowewyÃla , cznik´ow p i q zale˙zyodstanuwyÃla , cznika p iodstanuwyÃla , cznika

q tak,jakwarto´s´clogicznakoniunkcji p^q zale˙zyodwarto´scilogicznychzda´n p i

q .Wzwia , zkuztymmo˙znapowiedzie´c,˙ze

koniunkcje , realizujepoÃla , czenieszeregowe.

PodobniestanukÃladuutworzonegoprzezpoÃla , czenier´ownolegÃlewyÃla , cznik´ow p i q

zale˙zyodstanuwyÃla , cznika p lubodstanuwyÃla , cznika q tak,jakwarto´s´clogiczna

alternatywy p_q zale˙zyodwarto´scilogicznychzda´n p i q .Wzwia , zkuztym

mo˙znapowiedzie´c,˙ze

alternatywe , realizujepoÃla , czenier´ownolegÃle.

Warunekkoniecznyidostateczny.

Je˙zelizezdania p wynikazdanie q ( p)q ),tom´owimy,˙ze

p jest warunkiemdostatecznym (wystarczaja , cym) dlaq,

natomiast q jest warunkiemkoniecznymdlap.

4 ± n) 2 ± n

Podzielno´s´cliczby n przez4niejestwarunkiemkoniecznympodzielno´sci

liczby n przez2,oczym´swiadczyprzykÃladliczby6,kt´orajestpodzielnaprzez2,

aleniejestpodzielnaprzez4.

Mo˙zesie , zda˙zy´c,˙zewarunekkoniecznyjestjednocze´sniewarunkiemdostatecznym.

M´owimyw´owczas,˙zejesttowarunekkoniecznyidostateczny.

PrzykÃlad1.1.3.Podzielno´s´cliczby n przez2iprzez5jestwarunkiemkoniecznym

idostatecznympodzielno´sciliczby n przez10.

¡ 2 ± n^ 5 ± n ¢ ) 10 ± n

i) » ¡ p)q ¢ , ¡ p^»q ¢ ,

PrzykÃlad1.1.2.Podzielno´s´cliczby n przez4jestwarunkiemdostatecznym

podzielno´sciliczby n przez2.

1.2.Rachunekzbior´ow.

Poje , ciezbioruinale˙zeniadozbioruprzyjmujemyjakopierwotneiniewyma-

gaja , cedeﬁniowania.

Je˙zelielement a nale˙zydozbioru A ,topiszemy a2A ,wprzeciwnymprzy-

padku,gdyelement a nienale˙zydozbioru A piszemy a62A .

Deﬁnicja1.2.1.Zbi´or,kt´oregowszystkimielementamisa , a 1 ;a 2 ;:::;a n nazy-

wamy zbioremsko´nczonym.

Zbi´or,kt´oryposiadatylkojedenelementnazywamy zbioremjednoelemen-

towym.

Zbi´or,dokt´orego˙zadenelementnienale˙zynazywamy zbiorempustym.

Zbi´or,kt´oryniejestanisko´nczony,anipustynazywamy zbioremniesko´nczo-

nym.

Niech A i B be , da , dowolnymizbiorami.

Deﬁnicja1.2.2.M´owimy,˙zezbi´or A jest r´owny zbiorowi B ,gdyka˙zdyelement

zbioru A jestelementemzbioru B ika˙zdyelementzbioru B jestelementemzbioru

A .Piszemywtedy A = B .

Okre´slimyterazdziaÃlanianazbiorach.

Deﬁnicja1.2.3. Suma , zbior´ow A i B nazywamyzbi´orzÃlo˙zonyzewszystkich

element´ow,kt´orenale˙za , dozbioru A lubdozbioru B .

a2 ¡ A[B ¢ ,

h ¡ a2A ¢ _ ¡ a2B ¢ i

Deﬁnicja1.2.4. Iloczynem zbior´ow A i B nazywamyzbi´orzÃlo˙zonyzelement´ow,

kt´orejednocze´snienale˙za , dozbioru A idozbioru B .

a2 ¡ A\B ¢ ,

h ¡ a2A ¢ ^ ¡ a2B ¢ i

Deﬁnicja1.2.5. R´o˙znica , zbior´ow A i B nazywamyzbi´orzÃlo˙zonyztychele-

ment´ow,kt´orenale˙za , dozbioru A inienale˙za , dozbioru B .

a2 ¡ AnB ¢ ,

h ¡ a2A ¢ ^» ¡ a2B ¢ i

Deﬁnicja1.2.6.Je˙zelika˙zdyelementzbioru A nale˙zydozbioru B ,tom´owimy,

˙ze zbi´orAzawierasie , wzbiorzeB.

a2 ¡ A½B ¢ ,

h ¡ a2A ¢ ) ¡ a2B ¢ i

Deﬁnicja1.2.7.Zbiory A i B nazywamy rozÃla , cznymi, je˙zeliniemaja , wsp´olnego

elementu,tzn. A\B = ; .

Przypu´s´cmyteraz,˙zewszystkierozpatrywaneprzeznaszbiory,wustalonym

zagadnieniusa , podzbioramijednegozbioru,kt´oryoznaczymyprzez X .Wtedy

dlaka˙zdegorozpatrywanegozbioru A mamy: A½X .Zbi´or X nazywa´cbe , dziemy

przestrzenia , .

Deﬁnicja1.2.8. DopeÃlnieniemzbioruA (doprzestrzeni X )nazywamyzbi´or

A 0 = XnA .

h ¡ x2X ¢ ^» ¡ x2A ¢ i

x2A 0 ,

PrzykÃlad1.2.1.DopeÃlnieniemzbioruliczbujemnych(dozbioruliczbrzeczy-

wistych)jestzbi´orliczbnieujemnych.

Ka˙zdedziaÃlaniewrachunkuzbior´owmasw´ojodpowiednikwrachunkuzda´n

inaodwr´ot.Mo˙zemytoustali´cpor´ownuja , cokre´sleniaodpowiednichdziaÃla´n.Na

przykÃladiloczynowizbior´owodpowiadakoniunkcja,gdy˙z a2A\B wtedyitylko

wtedy,gdy a jestelementemzbioru A i(koniunkcja)jestelementemzbioru B .

Fakttenprowadziwkonsekwencjidowykorzystaniaprawrachunkuzda´nprzy

dowodzeniuprawrachunkuzbior´ow.

Niechdanebe , da , dwadowolneiniepustezbiory A i B orazniech a2A i b2B .

Uporza , dkowana , pare , element´ow a i b be , dziemyoznaczali( a;b ).

Deﬁnicja1.2.8. Iloczynemkartezja´nskimzbior´owAiB nazywamyzbi´orupo-

rza , dkowanychpar( a;b )takich,˙ze a2A i b2B .

A£B = f ( a;b ): a2A\b2Bg:

Zadanie1.2.1.Udowodni´cpodaner´owno´sci

a)( A[B ) \C =( A\C ) [ ( B\C ),

b)( A\B ) [C =( A[C ) \ ( B[C ),

c)( A[B ) 0 = A 0 \B 0 ,

d)( A\B ) 0 = A 0 [B 0 ,

e)( AnB ) \B = ; ,

f) AnB = A\B 0 ,

g) AnB = An ( A\B ),

h)( AnB ) \C =( A\C ) nB ,

i)( A\B ) [ ( A 0 \B )= B .

Zadanie1.2.2.Podajinterpretacje , geometryczna , napÃlaszczy´znie OXY naste , -

puja , cychzbior´ow

a) < 2 ; 3 >£< 1 ; 5 > , b)N £f 2 g ,

c)R £< 1 ;1> , d)R £f¼g .

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: