Teoria mnogosci - zadania ...

[ Pobierz całość w formacie PDF ]
//-->Podstawy matematyki dla informatykówJanusz J. SzusterZadaniaz logiki i teorii mnogościLublin 20061. WSTĘP21.WstępW literaturze przedmiotu „Logika i teoria mnogości” istnieje kilka zbiorów zadań wyda-nych w języku polskim, które są powszechnie znane i cytowane w proponowanej czytelnikowiliteraturze. Jedne z nich zostały wydane już dość dawno, inne w ostatnich latach, ale jak tozwykle bywa każdy z nich adresowany był do nieco innego odbiorcy. Wraz z upływem latzmieniły się programy nauczania, ale zmieniła się także pewnego rodzaju maniera w jakiejredagowane były zadania. Sformułowanie nazwy przedmiotu jako „Logika i teoria mnogości”jest dość ogólne i nie uwzględnia specyfiki uczelni jak też poziomu wykształcenia. Ponieważw zasadzie każdy wykład jest inny, to jest koniecznością dobranie do tego konkretnego wy-kładu zadań ilustrujących teorię i rozwijających jej rozumienie. W proponowanym zestawiezadań zawarte zostały zadania, które w mojej intencji mają największy związek z zakresemi poziomem wykładanego przedmiotu. W kolekcji znalazły się zadania, które wielokrotniezostały wykorzystane na ćwiczeniach audytoryjnych, ale także zadania zawarte w zestawachkolokwialnych czy egzaminacyjnych. Każde z nich ma więc własną historię, swoje „ofiary” izwycięzców. Ideą przewodnią tworzenia takiej kolekcji zadań, żeby nie powiedzeć zbyt mocnozbioru zadań, była chęć ułatwienia studentom wyboru egzamplarzy treningowych, dostoso-wanych do tematyki wykładu i poziomu odbiorców. Kolekcja ta jest ciągle otwarta i każdanowa edycja wykładu, a wraz z nią nowa seria sprawdzianów, kolokwiów i egzaminów do-starczać będzie kolejnych zadań. Pragnę podkreślić, że część z proponowanych zadań zostałazaczerpnięta z cytowanych przez mnie zbiorów, częśc jest modyfikacją oryginałów, a pokaź-na część, to zadania mojego autorstwa. Jest dla mnie honorem móc podziękować Autoromcytowanych zbiorów, z których czerpałem i których zadania stanowiły dla mnie standardtak poziomu redakcyjnego jak i merytorycznego. Pozostaje mi mieć jedynie nadzieję, żezestawienie ich z zadaniami mojego autorstwa nie będzie dla Nich powodem zakłopotania.Na zakończenie chcę życzyć tym, którzy będą korzystać zaprezentowanych tu zadań, byrozwiązując je przybliżyli się do wiedzy jaką zaplanowano na kursowy wykład. Będę takżezobowiązany za wskazanie usterek wszelkiej natury, co do istnienia których chwilowo nic niewiem, ale nie wierzę również w to, by nie istniały.Janusz J. Szuster2. WPROWADZENIE DO TEORII MNOGOŚCI32.2.1.Wprowadzenie do teorii mnogościNarzędzia zapisuZadanie 1.Korzystając z metodytablic Schr¨deralub metodynie wprostsprawdzić czyonastępujące formuły zdaniowe są twierdzeniami rachunku zdań:(a) [p⇒(q⇒r)]⇔[q⇒(p⇒r)](b){(α ⇒β)∧[(∼α)⇒(∼β)]}⇐⇒(α⇔β)(c) [(p⇒q)∨(p⇒r)∨(p⇒s)]⇒[p⇒(q∨r∨s)] .(d) (p∧q⇒r)⇒[p⇒(q⇒r)].(e) [(p⇒q)∨(r⇒q)]⇒[(p∧r)⇒q].(f){[(p ∧q)⇒r]∧[p∨(q⇒∼r)]}Zadanie 2.Którego spośród znaków⇔, ⇒, ⇐należy użyć w miejscu kropek, aby nastę-pujący napis stał się tautologią rachunku zdań. Udowodnić słuszność wyboru.(a) (p∨q)⇒r . . .(p⇒r)∧(q⇒r)(b)p⇒(q∧r) . . .(p⇒q)∧(p⇒r)(c) (p∧q)⇒r . . .(p⇒r)∧(q⇒r)(d) (p⇒q)∧(q⇒r) . . .(p⇒r)Zadanie 3.Posługując się symboliką logiczną zapisać następujące zdanie w postaci formułyrachunku zdań, a następnie sprawdzić czy jest ono twierdzeniem tego rachunku:(a)„Jeśli Chuck Norris nie jest szaleńcem to, jeśli Chuck Norris jest szaleńcem, to Chuckurodził się w Ostrowie Lubelskim”(b)„Hans Kloss jest patriotą wtedy i tylko wtedy, gdy nie jest prawdą, że nie jest prawdą,że Hans Kloss nie jest patriotą.”(c)„Jeśli James Bond nie jest agentem Jej Królewskiej Mości, to gdy James Bond jestagentem Jej Królewskiej Mości, to jest studentem Informatyki.”Zadanie 4.Sprawdzić, czy następujące zdania są prawdziwe:(a) (A∪C)\B= (A\B)∪(C\B),(b) (A\C)∪B= (A∩C)\(B∪C),(c)A\(B∪C)= (A\B)∩(A\C),(d)A\(B∪C)= (A\B)\C,2. WPROWADZENIE DO TEORII MNOGOŚCI(e)“JeśliA⊂CiB⊂C,toA∪B⊂C.”(f)“JeśliC⊂AiC⊂B,toC⊂A∩B.”(g)“JeśliA⊂CiB⊂D,toA∪B⊂C∪D”,(h)“JeśliA⊂CiB⊂D,toA∩B⊂C∩D”,(i) (A⊂B)∧(C⊂D)=⇒ (A∩C⊂B∩D),(j) (j) (A⊂B)∧(C⊂D)=⇒ [(A\D)⊂(B\C)],(k) (k)A\(B∩C)= (A∪C)∩(A\B).4Zadanie 5.Wiedząc, że przezróżnicę symetryczną zbiorówAiBrozumiemy zbiórA Bokreślony równością:A B= (A\B)∪(B\A)udowodnić, że dla dowolnych zbiorówAiBzachodzi równość:(i) (A∪B)\(A∩B)=A B,(ii)A∪(BC)= (A∪B)(A∪C),(iii) (A∪B)(A∩B)=A B.(iv) (A∪B)\(A∩B)=A BZadanie 6.Wyznaczyć zbiory:A∪B, A\BorazA∩B,gdy:(i)A=x∈Ê: log5(x2−2)<log5(ii)A={x ∈Ê:|x −1|3|x|2−1,B=x∈Ê:5log52√5x−1log√5x >1.33∨x <1},B={x ∈Ê:x2−7x + 6<0}.Zadanie 7.Dla rodziny zbiorówX={{α,β},{x,y, z}}zbudować zbiory:P(X) orazX × P(X).Zadanie 8.Dla zbiorówS={a,b}orazT={ϕ,ψ}utworzyć zbiór:T ×(P(S∪ T)\ {S, T,∅}.Zadanie 9.Pamiętając, że istnieje możliwość zastąpienia implikacji alternatywą, podaćzwiązek między zbioramiAiB(a tam gdzie to konieczne równieżC)odpowiadający nastę-pującej formule:(a) (p∨q)∧∼p⇒q,(b) [(p⇒q)∧p]⇒q,(c) (p⇒q)⇒[(r∧∼q)⇒(r∧∼p)],(d){(p ⇒q)∧[(∼p)⇒(∼q)]}⇔(p⇔q).2. WPROWADZENIE DO TEORII MNOGOŚCI5Zadanie 10.Podać przykład zbioruAgdy wiadomo, żeB={x ∈Ê:x∈(−2, 3)} orazA∩B={x ∈Ê:x∈(−∞,−4) ∩(−4,−2>∪(4,∞)}.Zadanie 11.Podać przykład zbioruBgdy wiadomo, żeA={x ∈Ê:x∈(−4,−1) ∪0, 2)} orazA∩B={x ∈Ê:x∈(−∞,−3) ∩(−3,−2 ∪(−1, 0)∪(1,∞)}.Zadanie 12.Dla danego zbioruAzdefiniować pojęcie zbioru potęgowegoP(A)(lub przyinnym oznaczeniu) 2A. Wyznaczyć zbiórP({a,b, c, d}).Zadanie 13.Ile elementów ma zbiórP(n),gdzienjest liczbą naturalną?Zadanie 14.Wykazać, że jeśli dla dowolnych zbiorówA⊆B,toP(A) ⊆ P(B).Zadanie 15.Czy dla dowolnych zbiorówAiBzachodzi równość:P(A∩B)=P(A)∩P(B)?Zadanie 16.Wykazać, że dla dowolnej rodziny zbiorówAzachodzi warunek:A ⊆ P(A) ⇐⇒A ⊆ A.Zadanie 17.Dana jest rodzina zbiorówA.Która z implikacji wchodząca w skład następu-jącej równoważności jest prawdziwa:P(A) ⊆ A ⇐⇒ A ⊆ A?Zadanie 18.Wykazać, że dla każdego zbioruAprawdziwa jest równośćP(A)=A.2.2.Indukcja matematycznaZadanie 1.Wykazać, że jeśliM ⊆Æjest zbiorem tych liczb naturalnych, że spełniają onenastępujące zależności, toMjest zbiorem induktywnym.(a) 0 + 1 + 2 + 3 +. . .+n=n(n+ 1);2n(n+ 1)(2n + 1);6n(n+ 1)(n + 2);3(b) 02+ 12+ 22+ 32+. . . n2=(c) 0·1 + 1·2 + 2·3 +. . .+n·(n−1) =22(n + 1)2(n + 1)(n + 2)12++...+=;(d)1·3 3·5(2n + 1)(2n + 3)2(2n + 3)(e)n1=;(2i + 1)(2i + 3)2n + 1i=0n1=;(a +i)(a+i+ 1)a(a+n)i=0nnn(f)11 sin (n +2)α(g)cosiα= +;22 sin1αi=02 [ Pobierz całość w formacie PDF ]