Fm Examens Juliol 2015

exmens resolts defonaments matemtics

edici a crrec de Jos Luis Ruizjuliol de 2015

Departament de Matemtica Aplicada IIFacultat dInformtica de BarcelonaUniversitat Politcnica de Catalunya

c 20102015

Col.lecci de problemes apareguts en diferents actes davaluaci de lassignatura Fona-ments Matemtics del Grau en Enginyeria Informtica de la Facultat dInformtica deBarcelona, U.P.C., des del setembre de 2010. Problemes proposats i recopilats per:

Josep ElguetaRafel FarrMerc MoraFrancesc PratsJos Luis RuizPilar SobrevillaFrancesc TienaJoan Trias

Les solucions han estat redactades per Jos Luis Ruiz amb contribucions de FernandoMartnez, Joan Trias i Francesc Tiena. c 20102015.

ndex

1 Enunciats E11.1 Exmens de taller 20102011 Q1 . . . . . . . . . . . . . . . . . . . . . . . . E11.2 Examen parcial 22/11/2010 . . . . . . . . . . . . . . . . . . . . . . . . . . E101.3 Examen final 17/01/2011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . E121.4 Exmens de taller 20102011 Q2 . . . . . . . . . . . . . . . . . . . . . . . . E121.5 Examen parcial 28/04/2011 . . . . . . . . . . . . . . . . . . . . . . . . . . E161.6 Examen final 06/06/2011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . E171.7 Exmens de taller 20112012 Q1 . . . . . . . . . . . . . . . . . . . . . . . . E181.8 Examen parcial 17/11/2011 . . . . . . . . . . . . . . . . . . . . . . . . . . E231.9 Examen final 20/01/2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . E241.10 Exmens de taller 20112012 Q2 . . . . . . . . . . . . . . . . . . . . . . . . E251.11 Examen parcial 26/04/2012 . . . . . . . . . . . . . . . . . . . . . . . . . . E291.12 Examen final 07/06/2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . E301.13 Exmens de taller 20122013 Q1 . . . . . . . . . . . . . . . . . . . . . . . . E311.14 Examen parcial 15/11/2012 . . . . . . . . . . . . . . . . . . . . . . . . . . E351.15 Examen final 14/01/2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . E361.16 Examen final de reavaluaci 04/02/2013 . . . . . . . . . . . . . . . . . . . E361.17 Exmens de taller 20122013 Q2 . . . . . . . . . . . . . . . . . . . . . . . . E371.18 Examen parcial 2/5/2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . E391.19 Examen final 6/6/2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E401.20 Examen final de reavaluaci 10/07/2013 . . . . . . . . . . . . . . . . . . . E411.21 Examen parcial 17/10/2013 . . . . . . . . . . . . . . . . . . . . . . . . . . E411.22 Examen parcial 14/11/2013 . . . . . . . . . . . . . . . . . . . . . . . . . . E421.23 Examen final 09/01/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . . . E421.24 Examen de recuperaci del primer parcial 09/01/2014 . . . . . . . . . . . . E431.25 Examen de recuperaci del segon parcial 09/01/2014 . . . . . . . . . . . . E431.26 Examen final de reavaluaci 07/02/2014 . . . . . . . . . . . . . . . . . . . E431.27 Examen parcial 20/03/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . E441.28 Examen parcial 30/04/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . E441.29 Examen final 12/06/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . . . E451.30 Examen de recuperaci del primer parcial 12/06/2014 . . . . . . . . . . . . E46

iii

1.31 Examen de recuperaci del segon parcial 12/06/2014 . . . . . . . . . . . . E461.32 Examen final de reavaluaci 11/07/2014 . . . . . . . . . . . . . . . . . . . E471.33 Examen parcial 16/10/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . E481.34 Examen parcial 17/11/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . E481.35 Examen final 14/01/2015 . . . . . . . . . . . . . . . . . . . . . . . . . . . . E491.36 Examen de recuperaci del primer parcial 14/01/2015 . . . . . . . . . . . . E491.37 Examen de recuperaci del segon parcial 14/01/2015 . . . . . . . . . . . . E501.38 Examen final de reavaluaci 6/02/2015 . . . . . . . . . . . . . . . . . . . . E501.39 Examen parcial 23/03/2015 . . . . . . . . . . . . . . . . . . . . . . . . . . E511.40 Examen parcial 11/05/2015 . . . . . . . . . . . . . . . . . . . . . . . . . . E511.41 Examen final 09/06/2015 . . . . . . . . . . . . . . . . . . . . . . . . . . . . E521.42 Examen de recuperaci del primer parcial 09/06/2015 . . . . . . . . . . . . E531.43 Examen de recuperaci del segon parcial 09/06/2015 . . . . . . . . . . . . E531.44 Examen final de reavaluaci 13/07/2015 . . . . . . . . . . . . . . . . . . . E54

2 Solucions S12.1 Exmens de taller 20102011 Q1 . . . . . . . . . . . . . . . . . . . . . . . . S12.2 Examen parcial 22/11/2010 . . . . . . . . . . . . . . . . . . . . . . . . . . S162.3 Examen final 17/01/2011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . S192.4 Exmens de taller 20102011 Q2 . . . . . . . . . . . . . . . . . . . . . . . . S212.5 Examen parcial 28/04/2011 . . . . . . . . . . . . . . . . . . . . . . . . . . S272.6 Examen final 06/06/2011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . S292.7 Exmens de taller 20112012 Q1 . . . . . . . . . . . . . . . . . . . . . . . . S312.8 Examen parcial 17/11/2011 . . . . . . . . . . . . . . . . . . . . . . . . . . S422.9 Examen final 20/01/2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . S442.10 Exmens de taller 20112012 Q2 . . . . . . . . . . . . . . . . . . . . . . . . S462.11 Examen parcial 26/04/2012 . . . . . . . . . . . . . . . . . . . . . . . . . . S542.12 Examen final 07/06/2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . S552.13 Exmens de taller 20122013 Q1 . . . . . . . . . . . . . . . . . . . . . . . . S572.14 Examen parcial 15/11/2012 . . . . . . . . . . . . . . . . . . . . . . . . . . S572.15 Examen final 14/01/2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . S602.16 Examen final de reavaluaci 04/02/2013 . . . . . . . . . . . . . . . . . . . S622.17 Exmens de taller 20122013 Q2 . . . . . . . . . . . . . . . . . . . . . . . . S622.18 Examen parcial 2/5/2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . S622.19 Examen final 6/6/2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . S632.20 Examen final de reavaluaci 10/07/2013 . . . . . . . . . . . . . . . . . . . S652.21 Examen parcial 17/10/2013 . . . . . . . . . . . . . . . . . . . . . . . . . . S682.22 Examen parcial 14/11/2013 . . . . . . . . . . . . . . . . . . . . . . . . . . S692.23 Examen final 09/01/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . . . S702.24 Examen de recuperaci del primer parcial 09/01/2014 . . . . . . . . . . . . S732.25 Examen de recuperaci del segon parcial 09/01/2014 . . . . . . . . . . . . S732.26 Examen final de reavaluaci 07/02/2014 . . . . . . . . . . . . . . . . . . . S752.27 Examen parcial 20/03/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . S782.28 Examen parcial 30/04/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . S792.29 Examen final 12/06/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . . . S802.30 Examen de recuperaci del primer parcial 12/06/2014 . . . . . . . . . . . . S822.31 Examen de recuperaci del segon parcial 12/06/2014 . . . . . . . . . . . . S83

iv

2.32 Examen final de reavaluaci 11/07/2014 . . . . . . . . . . . . . . . . . . . S852.33 Examen parcial 16/10/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . S862.34 Examen parcial 17/11/2014 . . . . . . . . . . . . . . . . . . . . . . . . . . S872.35 Examen final 14/01/2015 . . . . . . . . . . . . . . . . . . . . . . . . . . . . S892.36 Examen de recuperaci del primer parcial 14/01/2015 . . . . . . . . . . . . S902.37 Examen de recuperaci del segon parcial 14/01/2015 . . . . . . . . . . . . S912.38 Examen parcial 23/03/2015 . . . . . . . . . . . . . . . . . . . . . . . . . . S922.39 Examen parcial 11/05/2015 . . . . . . . . . . . . . . . . . . . . . . . . . . S942.40 Examen final 09/06/2015 . . . . . . . . . . . . . . . . . . . . . . . . . . . . S952.41 Examen de recuperaci del primer parcial 09/06/2015 . . . . . . . . . . . . S972.42 Examen de recuperaci del segon parcial 09/06/2015 . . . . . . . . . . . . S98

v

1Enunciats

1.1 Exmens de taller 20102011 Q1

Raonament

1 Considereu el connectiu definit de la manera segent:

p q := (p q) (q p)

1) Feu la taula de veritat de la proposici (p (p p)) q.2) Doneu una proposici equivalent a (p (p p)) q que no contingui el connectiu

i que contingui el mnim nombre possible de connectius.

2 Considereu el connectiu definit de la manera segent:

p q := p q

1) Feu la taula de veritat de la proposici ((p p) q) ((p p) q).2) Doneu una proposici equivalent a ((p p) q) ((p p) q) que no contingui el

connectiu i que contingui el mnim nombre possible de connectius.

3 Considereu el connectiu | definit de la manera segent:

p|q := p q

1) Feu les taules de veritat de les proposicions (p|p)|(q|q) i (p|q)|(p|q).2) Doneu una proposici equivalent a (p|p)|(q|q) que no contingui el connectiu | i que

contingui el mnim nombre possible de connectius.

3) Doneu una proposici equivalent a (p|q)|(p|q) que no contingui el connectiu | i quecontingui el mnim nombre possible de connectius.

E1

Exmens resolts de Fonaments Matemtics E2

4 Considereu els connectius i | definits de la manera segent:

p q := p q, p|q := p q

1) Feu la taula de veritat de les proposicions p|q i (p p) (q q) i doneu una proposiciequivalent a p|q que noms contingui els connectius i .

2) Feu la taula de veritat de les proposicions p q i (p|p)|(q|q) i doneu una proposiciequivalent a p q que noms contingui els connectius i |.

3) Doneu una proposici equivalent a p p on noms intervinguin connectius clssics(negaci, conjunci, disjunci, condicional, bicondicional) i doneu una proposici equi-valent a p|q que noms contingui el connectiu .

4) Doneu una proposici equivalent a p|p on noms intervinguin connectius clssics (nega-ci, conjunci, disjunci, condicional, bicondicional) i doneu una proposici equivalenta p q que noms contingui el connectiu |.

5 Trobeu una proposici equivalent a p q on hi apareguin exclusivament:1) Els connectius i .2) Els connectius i .3) Els connectius i .

6 Simbolitzeu en el llenguatge del clcul de predicats els enunciats que segueixen. Ho heude fer de dues maneres:

a) sense utilitzar quantificadors universals () ni condicionals () i amb el mnim nombrepossible de negacions ();

b) sense utilitzar quantificadors existencials () i utilitzant condicionals ().Els enunciats sn:

1) No tota funci t derivada.

2) Hi ha funcions contnues no derivables.

3) Cap nombre enter s parell i senar alhora.

4) Tot nombre enter s parell o senar.

Useu els predicats: F : ser funci; C: ser contnua; D: ser derivable; N : ser nombreenter; P : ser parell; S: ser senar.

7 Simbolitzeu:

J.L. Ruiz (ed.) c 20102015 CAPTOL 1. ENUNCIATS


1) Hi ha un nic objecte que t la propietat P .

2) Hi ha exactament dos objectes que tenen la propietat P .

3) Hi ha com a mxim un objecte que t la propietat P .

4) Hi ha com a mnim dos objectes que tenen la propietat P .

Conjunts

8 Siguin A, B i C conjunts arbitraris. Demostreu que A (B C) AB si, i noms si,A B A C.

9 Siguin A i B conjunts arbitraris. Demostreu que (A B) (B A) = A si, i noms si,B = .

10 Siguin A i B conjunts arbitraris. Demostreu que (AB) (B A) = A B si, i nomssi, A B = .

11 Siguin un conjunt i A,B,C subconjunts tals que A Bc C i Cc B = .Demostreu que A C.

12 Siguin un conjunt i A,B,C subconjunts tals que B Cc = . Demostreu queA (A B) A C.

13 Siguin un conjunt i A,B,C subconjunts no buits tals que A B C = . Proveuque si D s un subconjunt tal que D A D B, aleshores D C Ac.

14 Siguin A, B i C conjunts tals que A B A C i A B A C. Demostreu queB C.

15 Siguin un conjunt i A,B,C subconjunts tals que A B 6= i B Cc = .Demostreu que A C 6= .

16 Siguin un conjunt i A,B,C subconjunts. Demostreu que C A B si, i nomssi, C Ac = i C Bc = .



Aplicacions

17 Considerem laplicaci f : N N definida per:

f(n) =

{n, si n s parelln + 1, si n s senar

1) Proveu que f f = f .2) Calculeu f [{1, 2, 3, 4}]. Deduu que f no s injectiva.3) Calculeu f1[{0, 1, 2}]. Deduu que f no s exhaustiva.


f(n) =

{n, si n s mltiple de 33n, en cas contrari

1) Proveu que f f = f .2) Calculeu f [{1, 2, 3, 4}]. Deduu que f no s injectiva.3) Calculeu f1[{0, 1, 2}]. Deduu que f no s exhaustiva.

19 Considerem laplicaci f : Z Z definida per:

f(n) =

{n2, si n < 0n2, si n 0

1) Calculeu f [{2,1, 0, 1, 2}].2) Proveu que f s injectiva.

3) Calculeu f1[{0, 1, 2}]. Deduu que f no s exhaustiva.

20 Considerem laplicaci f : Z N definida per:

f(n) =

{2n 1, si n > 02n, si n 0

1) Calculeu f [{2,1, 0, 1, 2}] i f [{5,3, 0, 3, 5}].2) Calculeu f1[{0, 1, 2}] i f1[{0, 3, 6}]3) Proveu que f s injectiva.



4) Proveu que f s exhaustiva.

21 Considerem laplicaci f : N Z definida per:

f(n) =

{n

2, si n s parell

n+12

, si n s senar

1) Calculeu f [{0, 1, 2, 3, 4, 5}] i f [{0, 3, 5, 6, 7, 10}].2) Calculeu f1[{1, 0, 1, 2}] i f1[{3,1, 0, 1}].3) Proveu que f s exhaustiva.

4) Proveu que f s injectiva.


f(n) =

{n + 1, si n no s mltiple de 5n5, si n s mltiple de 5

1) Calculeu f1[{0, 1, 2, 3, 4, 5}].2) Proveu que f s exhaustiva.

3) Calculeu f [{0, 1, 2, 5, 10, 15}]. Deduu que f no s injectiva.

23 Considerem laplicaci f : Z N definida per:

f(n) = n2 + 1.

Siguin: S = {n N : n s senar}, P = {m Z : m s parell}.1) Proveu que f1[S] = P .

2) Proveu que f no s exhaustiva.

3) Proveu que f no s injectiva.

4) s f bijectiva?


f(n) =

{7n, si n s parelln + 2, si n s senar



1) Calculeu f1[{1, 0, 1, 2}]. Deduu que f no s exhaustiva.2) Proveu que f s injectiva.

3) s f bijectiva?


f(n) = n2 + n + 1

1) Calculeu f [{2,1, 0, 1, 2}]. Deduu que f no s injectiva.2) Calculeu f1[{0, 1}]. Deduu que f no s exhaustiva.3) s f bijectiva?

26 Considerem els conjunts:

A = {n N : n 2}, P = {p N : p s un nombre primer}

i laplicaci f : A P definida per:

f(n) = nombre primer ms petit que divideix n

1) Proveu que f|P = IP . (f|P s la restricci de f a P A i IP s laplicaci identitat deP .)

2) Calculeu f [{2, 6, 9, 11, 35}]. Deduu que f no s injectiva.3) Proveu que f s exhaustiva.

4) s f bijectiva?


f(n) =

{n, si n s mltiple de 55n, en cas contrari

1) Proveu que f f = f .2) Calculeu f [{0, 1, 2, 3, 4, 5}]. Deduu que f no s injectiva.3) Calculeu f1[{0, 1, 5}]. Deduu que f no s exhaustiva.4) s f bijectiva?




f(n) =

n, si n s mltiple de 3n + 1, si el residu de dividir n per 3 s 1n 1, si el residu de dividir n per 3 s 2

1) Calculeu f [A], si A = {1, 2, 3, 4, 5, 6}.2) Deduu que laplicaci g : A A definida per g(a) = f(a), si a A, s bijectiva.3) Proveu que f s injectiva.

4) Calculeu f [B], si B = {0, 1, 2, 4, 5, 9}.5) Deduu que laplicaci h : B B definida per h(b) = f(b), si b B, s bijectiva.6) Proveu que f s exhaustiva.

29 Considerem els conjunts:

A = {n N : n 2}, P = {p N : p s un nombre primer}i les aplicacions f : A P , g : P A definides per:

f(n) = nombre primer ms petit que divideix ng(p) = p2

1) Calculeu g[{2, 3, 5, 7, 11}] i f1[{2}].2) Proveu que f g = IP . (IP s laplicaci identitat de P .)3) Proveu que f s exhaustiva.

4) Per a quins valors de n A se satisf (g f)(n) = n?5) Proveu que g s injectiva.


f(n) =

{n/2, si n s parell2n, si n s senar

1) Calculeu f [{0, 1, 2, 4, 8}]. Deduu que f no s injectiva.2) Proveu que f s exhaustiva.

3) s f bijectiva?



Principi dinducci

31 Demostreu per inducci que per a tot n 1:n

i=1

i i! = (n + 1)! 1


k=1

(1)k1k2 = (1)n1 n(n + 1)2


j=1

j(j + 1) =n(n + 1)(n + 2)

3


`=1

1

`(` + 1)=

n

n + 1


r=1

(3r 2) = 3n2 n2


s=1

(4s + 1) = n(2n + 3)


v=1

(v2 + v) =n(n + 1)(n + 2)

3




m=1

(5m 3) = 5n2 n2


u=1

(u2 u) = n(n2 1)3


t=1

t3 =n2(n + 1)2

4


p=1

1

(p + 1)(p + 2)=

n

2(n + 2)

Enters: divisibilitat

42 Siguin a, b Z i d = mcd(a, b). Proveu que mcd(2a, d) = d.

43 Siguin a, b Z primers entre ells. Proveu que si b s senar, llavors mcd(2a, b) = 1.

44 Siguin a, b Z primers entre ells i p, q nombres primers diferents. Proveu que mcd(pa, qb)s igual a 1, p, q o pq.

45 Sigui p un nombre primer senar i a un enter parell. Proveu que mcd(a, 2p) s igual a 2 oigual a 2p.

46 Siguin p, q i ` tres nombres primers diferents i a un enter. Sabem que `|a i que a = p N =q M , on N i M sn enters. Proveu que mcd(N,M) 6= 1.

47 Siguin a, b, c, d enters. Proveu que si a | b i c | d, llavors ac | bd.



48 Siguin a, b, c, d enters. Proveu que si ac + bd = 1, llavors mcd(a, b) = 1.

49 Siguin a, b Z. Proveu que si mcd(a, a + b) = 1, llavors mcd(a, a b) = 1.

50 Siguin a, b Z. Proveu que mcd(a, b) s un divisor de mcm(a, a + b).

51 Siguin a, b, c enters i p un nombre primer. Proveu que si p | ab, p | ac i mcd(b, c) = 1,llavors p | a.

52 Siguin a, b, c, d enters i r = mcd(a, b), s = mcd(c, d). Proveu que si a | c i b | d, llavorsr | s.

53 Calculeu el mxim com divisor dels nombres que sindiquen i els coeficients x i y de laidentitat de Bzout corresponent.

a b mcd(a, b) x y603 651 3 95 88484 460 4 19 20792 599 1 90 119317 482 1 111 73643 524 1 251 308430 721 1 166 99372 348 12 14 15696 467 1 104 155431 636 1 121 82680 593 1 259 297545 433 1 58 73384 748 4 37 19794 591 1 230 309560 502 2 26 29391 505 1 31 24686 651 7 37 39722 667 1 97 105310 685 5 42 19558 314 2 9 16388 657 1 127 75

1.2 Examen parcial 22/11/2010

54



1) Considerem la proposici p segent:

a, b, c Z ( c parell c = a b a parell b parell )Digueu si p s certa o falsa i justifiqueu la resposta.

2) Siguin A,B conjunts no buits. Proveu que laplicaci g : A B A definida perg((x, y)

)= x s exhaustiva.

55 Considerem el conjunt A = (Z {0}) (Z {0}) i la relaci R sobre A definida per:(a, b) R (c, d) a d = b c,

on (a, b), (c, d) A.1) Demostreu que R s una relaci dequivalncia sobre A.

2) Trobeu la classe dequivalncia de lelement (a, b) A.3) Doneu una descripci del conjunt quocient A/R.

56 Demostreu per inducci que lenter n3 +3n2 +2n s divisible per 6, per a tot enter n 0.

57

1) Considerem la proposici p segent:

a, b, c Z ( a parell a = b + c b senar c senar )Digueu si p s certa o falsa i justifiqueu la resposta.

2) Siguin A,B conjunts no buits i b0 B un element fix. Proveu que laplicaci h : A A B definida per h(x) = (x, b0) s injectiva.

58 Considerem el conjunt A = Z Z i la relaci R sobre A definida per:(a, b) R (c, d) a + d = b + c,

on (a, b), (c, d) A.1) Demostreu que R s una relaci dequivalncia sobre A.

2) Trobeu la classe dequivalncia de lelement (0, b) A.3) Doneu una descripci del conjunt quocient A/R.

59 Demostreu per inducci que lenter (n+1)3n1 s mltiple de 6, per a tot enter n 0.



1.3 Examen final 17/01/2011

60 Digueu si les afirmacions segents sn certes o falses i justifiqueu la resposta.

1) (n Z)(a, b Z n = 5a + 7b)2) Les proposicions [((p) q) r] i (p) q (r) sn lgicament equivalents.3) Si f : X Y s una funci, llavors f(f1(Y )) = Y .

61 Proveu que si a, b, c Z, llavors mcd(a, b) = mcd(bc a, b).

62 Considerem laplicaci f : Z29 Z29 definida per f(x) = 22 x + 71) Proveu que f s bijectiva i trobeu la seva inversa.

2) Considerem lalfabet de 29 smbols indicat a continuaci i assignem a cada smbol elnombre que t a la dreta:

A 0 F 5 K 10 P 15 U 20 Z 25B 1 G 6 L 11 Q 16 V 21 26 (espai)C 2 H 7 M 12 R 17 W 22 . 27D 3 I 8 N 13 S 18 X 23 , 28E 4 J 9 O 14 T 19 Y 24

Codifiquem cada frase escrita en lalfabet anterior aplicant la regla de codificaci x 722x+7 (mod 29) al valor numric corresponent a cadascun dels smbols. Per exempleAVUI s 0 21 20 8 i es codificaria en 7 5 12 9, o sigui HFMJ, ja que 0 7 7,21 7 5, 20 7 12, 8 7 9.Si el resultat duna codificaci ha estat el missatge KZRT,AI (el que hi ha entre lescometes), quin era el missatge original?

63 Proveu que per a tot n 0 es compleix que 2n+2 + 32n+1 0 (mod 7). (Indicaci: potfer-se per inducci, per tamb daltres maneres.)


Lgica i raonament

64 Considerem els dos connectius lgics X i O definits per les taules de veritat que segueixen:

p q pXq pOq0 0 1 10 1 1 01 0 1 01 1 0 0



a) Expresseu el connectiu en funci nicament del connectiu X.b) Expresseu el connectiu en funci nicament del connectiu X.c) Expresseu el connectiu en funci nicament del connectiu X.d) Expresseu el connectiu en funci nicament del connectiu O.e) Expresseu el connectiu en funci nicament del connectiu O.f) Expresseu el connectiu en funci nicament del connectiu O.g) Expresseu el connectiu X en funci nicament del connectiu O.

h) Expresseu el connectiu O en funci nicament del connectiu X.

65 Doneu una condici necessria per no suficient perqu el nombre natural n sigui parell.Doneu una condici suficient per no necessria perqu el nombre natural n sigui parell.Justifiqueu les respostes.

66 s necessari que la suma de dos enters sigui parell perqu els dos nombres siguin parells?I suficient? Justifiqueu les respostes.

67 Doneu una condici necessria i suficient, diferent della mateixa, perqu el nombre naturaln sigui mltiple de 6. Doneu-ne tamb una de necessria per no suficient i una de suficientper no necessria. Justifiqueu les respostes.

68 Formalitzeu lenunciat segent: no hi ha ms de dos enters diferents que compleixin lapropietat P . Doneu una propietat P per a la qual lenunciat sigui vertader i una altrapropietat P per a la qual lenunciat sigui fals. Justifiqueu les respostes.

69 Formalitzeu lenunciat segent: hi ha al menys tres enters diferents que compleixen lapropietat P . Doneu una propietat P per a la qual lenunciat sigui vertader i una altrapropietat P per a la qual lenunciat sigui fals. Justifiqueu les respostes.

70 Siguin A i B dos enunciats. De A i de si B, llavors A, s correcte deduir B? Justifiqueula resposta.

71 En una demostraci trobem un primer apartat on a partir de p i de q sarriba a r i unsegon apartat on a partir de p i r sarriba a q. s una demostraci de q r? s unademostraci de q r? Justifiqueu les respostes.



Conjunts i aplicacions

72

1) Siguin A, B i C conjunts arbitraris.

a) Proveu que si B C = , llavors (A B) C (A B C) (A B).b) s certa la igualtat (AB)C = (AB C) (AB)? Justifiqueu la resposta.

2) Doneu un exemple de funci f : Z Z que sigui injectiva per no exhaustiva. Justifi-queu la injectivitat i la no exhaustivitat.

73


a) Proveu que A (B C) (A B) C.b) s certa la igualtat A (B C) = (A B) C? Justifiqueu la resposta.

2) Doneu un exemple de funci f : Z Z que sigui exhaustiva per no injectiva. Justifi-queu la exhaustivitat i la no injectivitat.

74


a) Proveu que (A B) (A C) A (B C).b) s certa la igualtat (A B) (A C) = A (B C)? Justifiqueu la resposta.

2) Doneu un exemple de funci f : Z Z que sigui bijectiva i que no sigui laplicaciidentitat. Calculeu f1.

75


a) Proveu que A (B C) (A B) (A C).b) s certa la igualtat A (B C) = (A B) (A C)? Justifiqueu la resposta.

2) Doneu un exemple de funci f : N N que sigui bijectiva i que no sigui laplicaciidentitat. Calculeu f1.

76



1) Siguin f : A B una aplicaci i P,Q A.a) s certa la implicaci: f [P ] = f [Q] P = Q? Justifiqueu la resposta.b) Proveu que si f s injectiva, llavors la implicaci anterior s certa.

2) Siguin A, B, C conjunts tals que A 6= B i C 6= . Es pot donar el cas que A C =B C? Justifiqueu la resposta.

77

1) Siguin g : A B una aplicaci i S, T B.a) s certa la implicaci: f1[S] = f1[T ] S = T? Justifiqueu la resposta.b) Proveu que si f s exhaustiva, llavors la implicaci anterior s certa.

2) Siguin A, B, C, D conjunts. Podem assegurar que

(A B) (C D) = (A C) (B D)?Justifiqueu la resposta.

78

1) Siguin f : A B una aplicaci i C A.a) s certa la igualtat: f [A C] = f [A] f [C]? Justifica la resposta.b) Proveu que si f s injectiva, llavors la igualtat anterior s certa.

2) Sigui X un conjunt no buit. Definiu a X una relaci dequivalncia R tal que X/Rtingui un element. Comproveu que es tracta duna relaci dequivalncia.

Principi dinducci i divisibilitat

79 Proveu per inducci que si n 1, llavors lenter 6 7n 2 3n s un mltiple de 4.

80 Proveu per inducci que si n 0, llavors n55

+ n3

3+ 7n

15s un nombre enter.

81 Proveu per inducci que si n 0, llavors 9 | [n3 + (n + 1)3 + (n + 2)3].

82 Proveu per inducci que si n 0, llavors 73 | (8n+2 + 92n+1).

83 Proveu per inducci que si n 1, llavors (2n)!2n

Z.



84 Proveu per inducci que si n 1, llavors (2n)!n!2n

Z.

85 Calculeu el mxim com divisor dels nombres que sindiquen i els coeficients x i y de laidentitat de Bzout corresponent.

a b mcd(a, b) x y7658 3853 1 883 17559191 6987 1 1975 25985548 1727 1 80 2573614 7752 2 1435 6691084 4904 4 95 217084 3563 7 85 1699176 7084 4 640 8293419 9168 1 4403 16427119 6966 9 91 933643 8590 1 3353 14226312 2659 1 1276 32091628 9613 1 124 218304 1274 2 83 541


86 Considerem en R R la relaci segent:(x, y)R(z, t) si, i noms si, |x|+ |y| = |z|+ |t|.

1) Proveu que R s una relaci dequivalncia.

2) Assenyaleu, en el pla, quins sn els elements de la classe de (1, 0). Raoneu la resposta.

87 Siguin X, Y conjunts.

1) Proveu que P(X) P(Y ) P(X Y ).2) s certa linclusi contrria? Justifiqueu la resposta.

88 Sigui A un conjunt i f, g : A A dues aplicacions tals que f g = IA.1) Proveu que g s injectiva.

2) Proveu que f s exhaustiva.

3) Podem afirmar que g f = IA? Justifiqueu la resposta.




89

1) Comproveu que mcd(1876, 365) = 1 i calculeu enters r i s tals que:

1876 r + 365 s = 1

Expliciteu els clculs que feu per a arribar a la soluci.

2) Trobeu el mnim enter positiu x tal que 365x + 902 508 (mod 1876). Expliciteu ijustifiqueu els clculs que feu per a arribar a la soluci.

90 Proveu que si n 0, llavors:n

k=0

k2nk = 2n+1 n 2

91 Siguin m, n enters positius.

1) Proveu que, en general, mcd(m,n) 6= mcd(m n,m + n).2) Proveu que una condici suficient perqu mcd(m,n) = mcd(m n,m + n) s que m i

n tinguin paritat diferent.

3) Proveu que la condici esmentada a lapartat anterior no s necessria.

92 Trieu dues preguntes de les segents.

1) Enuncieu les lleis de De Morgan per a proposicions i demostreu-les.

2) Definiu el concepte de diferncia de dos conjunts. Demostreu que si A i B sn conjunts,llavors:

A B A B =

3) Siguin a, a, b, b Z i n > 1 tals que a a (mod n) i b b (mod n). Demostreu quea + b a + b (mod n) i ab ab (mod n).




Raonament

93

1) Siguin m i n nombres enters. s suficient que m i n siguin mltiples de 3 per a poderafirmar que m + n s mltiple de 3? I necessari? Justifiqueu les respostes.

2) Formalitzeu la proposici segent i negueu-la: hi ha enters que sn quadrats, senarsi mltiples de 5.

94

1) Sigui n un nombre enter. s necessari que n sigui mltiple de 4 perqu n2 siguimltiple de 8? I suficient? Justifiqueu les respostes.

2) Formalitzeu la proposici segent i negueu-la: hi ha nombres naturals que no snparells, ni mltiples de 3, per s mltiples de 5.

95

1) Proveu que una condici necessria i suficient perqu un enter sigui parell s que elseu quadrat sigui parell.

2) Formalitzeu la proposici segent i negueu-la: per a tot nombre natural n ms petitque 100, n2 + n + 41 s un nombre primer.

96

1) Acabar en 55, s una condici necessria per ser senar mltiple de 5? I suficient?Justifiqueu les respostes.

2) Formalitzeu la proposici segent i negueu-la: tot nombre natural s suma de dosquadrats.

97

1) Siguin m i n nombres enters. s suficient que m i n siguin consecutius per a poderafirmar que (m + n)2 s senar? I necessari? Justifiqueu les respostes.

2) Formalitzeu la proposici segent i negueu-la: per a tot nombre naturals n, o b n2

s parell o b no acaba en 7.



98

1) Demostreu, per reducci a labsurd, que tot nombre que acaba en 4 i no s mltiplede 4 t la xifra de les desenes senar.

2) Formalitzeu la proposici segent i negueu-la: per a tot enter n, n s parell o n3 noacaba en 9.

99

1) Demostreu que el cub de qualsevol enter s o b multiple de 8 o b s senar.

2) Formalitzeu la proposici segent i negueu-la: hi ha enters n que sn cubs, parells imltiples 8.

100

1) Demostreu, per reducci a labsurd, que si x s un nombre racional tal que x2 s unnombre enter, aleshores x s un nombre enter.

2) Formalitzeu la proposici segent i negueu-la: el producte de dos nombres primers sun nombre primer.

101

1) Proveu si m s un enter qualsevol i n s un enter senar mltiple de 3, aleshores elproducte mn s senar o s mltiple de 6.

2) Formalitzeu la proposici segent i negueu-la: la suma de dos nombres primers s unnombre parell.

102

1) Proveu que si n s un nombre natural, aleshores n2 dividit per 3 dna com a residu 0o 1, per mai no dna 2. Pista: feu una demostraci per casos: considereu el residude n entre 3.

2) Formalitzeu la proposici segent i negueu-la: hi ha enters n que sn quadrats, parellsper no mltiples de 8.




103

1) Siguin f : N N una aplicaci injectiva. Proveu que laplicaci g : N N definidaper g(n) = 2f(n) tamb s injectiva.

2) Descriu per extensi el conjunt P(P()); s a dir, digueu quins sn els seus elements.

104

1) Sigui f : N N una aplicaci injectiva. Proveu que laplicaci g : N N definida perg(n) = 2f(n) + 1 tamb s injectiva.

2) Siguin A i B conjunts tals que A B = B i A B = B. Qu podem dir de A i de B?Justifica la resposta.

105

1) Sigui f : Z Z una aplicaci injectiva. Proveu que laplicaci g : Z Z definida perg(n) = f(n 1) tamb s injectiva.

2) Siguin A i B conjunts no buits. s vertader o fals que P(A B) = P(A) P(B)?Justifica la resposta.

106

1) Sigui f : Z Z una aplicaci exhaustiva. Proveu que laplicaci g : Z Z definidaper g(n) = f(n + 1) tamb s exhaustiva.

2) Siguin A i B conjunts no buits. s vertader o fals que P(A B) = P(A) P(B)?Justifica la resposta.

107

1) Sigui f : R R una aplicaci injectiva. Proveu que laplicaci g : R R definidaper g(x) = 1/f(x) tamb s injectiva. (R = R {0}.)

2) Siguin un conjunt no buit i A . s vertader o fals que P(Ac) = P(A)c? Justificala resposta. (P(A)c es calcula a P().)

108



1) Sigui f : R R una aplicaci exhaustiva. Proveu que laplicaci g : R Rdefinida per g(x) = 1/f(x) tamb s exhaustiva. (R = R {0}.)

2) Siguin un conjunt no buit i A i B tals que A B = i A B = . Qupodem dir de A i B? Justifica la resposta.

109

1) Sigui f : N N una aplicaci bijectiva i sigui a N. Proveu que laplicaci g : N Ndefinida per g(n) = f(n) + a s injectiva, per no exhaustiva.

2) s possible que en un conjunt no buit A hi ha hagi definida una relaci R que siguisimtrica i antisimtrica? Justifica la resposta.

110

1) Sigui f : Z Z una aplicaci injectiva. Proveu que laplicaci g : Z Z definida perg(n) = f(n 1) + 1 s injectiva.

2) s possible que en un conjunt no buit A hi ha hagi definida una relaci R que no siguireflexiva ni antireflexiva? Justifica la resposta

111

1) Sigui f : Z Z una aplicaci exhaustiva. Proveu que laplicaci g : Z Z definidaper g(n) = f(n + 1) 1 s exhaustiva.

2) Siguin A, B i C conjunts no buits tals que AB = AC. Podem afirmar que B = C?Justifica la resposta.

112

1) Sigui f : Z Z una aplicaci injectiva. Proveu que laplicaci g : Z Z definida perg(n) = 2f(n 1) s injectiva.

2) Siguin A i B conjunts no buits. s vertader o fals que si Z (A B), llavors hi haX A i Y B tals que Z = X Y ? Justifica la resposta.



Principi diInducci

113 Proveu per inducci que si n 2, llavors:

1 3 + 2 4 + 3 5 + + (n 1)(n + 1) = n(n 1)(2n + 5)6


12 + 32 + 52 + + (2n 1)2 = n(2n 1)(2n + 1)3


22 + 42 + 62 + + (2n)2 = 2n(n + 1)(2n + 1)3


1 4 + 9 16 + + (1)n+1n2 = (1)n+1 n(n + 1)2

117 Proveu per inducci que si n 1, llavors:1

1 3 +1

3 5 +1

5 7 + +1

(2n 1)(2n + 1) =n

2n + 1


1 5 +1

5 9 +1

9 13 + +1

(4n 3)(4n + 1) =n

4n + 1


1 4 +1

4 7 +1

7 10 + +1

(3n 2)(3n + 1) =n

3n + 1

120 Proveu per inducci que si n 2, llavors:(1 1

2

)(1 1

3

)(1 1

4

) (

1 1n

)=

1

n



121 Proveu per inducci que si n 2, llavors:(1 1

4

)(1 1

9

)(1 1

16

) (

1 1n2

)=

n + 1

2n


1 3 +1

2 4 +1

3 5 + +1

n(n + 2)=

n(3n + 5)

4(n + 1)(n + 2)


123

1) Definiu el concepte de diferncia de dos conjunts. Proveu lequivalncia segent:

(C A B) (C A C B = )on A, B i C sn conjunts. Justifiqueu tots els passos.

2) Definiu el concepte dantiimage dun subconjunt per una aplicaci. Siguin A, B con-junts i f : A B una aplicaci. Proveu, justificant tots els passos, que si B1 B,B2 B, llavors f1[B1 B2] = f1[B1] f1[B2].

124 Considerem en el conjunt A = Z {0} la relaci R segent:m R n (signe(n) = signe(m) paritat(n) = paritat(m))

(signe(n) 6= signe(m) paritat(n) 6= paritat(m))1) Proveu que R s una relaci dequivalncia.

2) Trobeu les classes dequivalncia de lelement 1 i de lelement 2. Raoneu la resposta.

3) Expliciteu el conjunt quocient A/R. Raoneu la resposta.

125 Considerem el conjunt X = {n N : 1 n 100} i laplicaci f : X X definida per:

f(n) =

{2n, si 1 n 502(n 51) + 1, si 51 n 100

1) Proveu que f s una aplicaci bijectiva.

2) Calculeu f1[S], si S = {n X : n senar}. Justifiqueu la resposta.




126

1) Expliqueu en qu consisteix la tcnica de demostraci per reducci a labsurd? Proveuque

2 no s un nombre racional.

2) Sigui m 1 un enter. Definiu el concepte de relaci de congruncia mdul m idemostreu que s una relaci dequivalncia.

127

1) Proveu que la classe 2957 s invertible a Z4096 i trobeu la seva classe inversa. Justifiqueui expliciteu tots els clculs que feu per a arribar al resultat.

2) Comproveu que les aplicacions:

f : Z4096 Z4096, f(x) = 2957 xg : Z4096 Z4096, g(x) = 3909 x

sn inverses una de laltra.

128

1) Justifiqueu que per a ser mltiple de 30 s suficient ser mltiple de 6 i acabar en 0.s aquesta una condici necessria? Justifiqueu la resposta.

2) Siguin a,m enters tals que mcd(a,m) = 2. Proveu que existeix un enter x tal queax 2 (mod m).

129

1) Sigui A un conjunt no buit i R una relaci reflexiva i transitiva en A. Demostreu quela relaci S definida per:

x S y (x R y y R x)s dequivalncia.

2) Sigui P el conjunt de punts del pla i considerem un punt O P . Definim a P larelaci R segent:

X R Y d(X,O) d(Y,O)a) Proveu que R s una relaci reflexiva i transitiva.

b) Trobeu les classes dequivalncia per la relaci S associada a R segons lapartat 1).




Raonament

130

1) Troba una proposici equivalent a p q on no hi aparegui cap connectiu diferent de i . Justifica lequivalncia (aplicant equivalncies conegudes o mitjanant taules deveritat).

2) s suficient ser mltiple de 24 per ser mltiple de 6? I necessari? Explica claramentqu has de demostrar/refutar per veure la suficincia i la necessitat de les condicions(que quedi clar qu vol dir, en aquest context, necessari i qu vol dir suficient) i justificales respostes.

131

1) Troba una proposici equivalent a p q on no hi aparegui cap connectiu diferent de i . Justifica lequivalncia (aplicant equivalncies conegudes o mitjanant taulesde veritat).

2) s necessari ser parell per ser mltiple de 3? I suficient? Explica clarament quhas de demostrar/refutar per veure la suficincia i la necessitat de les condicions (quequedi clar qu vol dir, en aquest context, necessari i qu vol dir suficient) i justifica lesrespostes.

132

1) Troba una proposici equivalent a p (qr) on no hi aparegui cap connectiu diferentde i. Justifica lequivalncia (aplicant equivalncies conegudes o mitjanant taulesde veritat).

2) s necessari ser parell per ser mltiple de 6? I suficient? Explica clarament quhas de demostrar/refutar per veure la suficincia i la necessitat de les condicions (quequedi clar qu vol dir, en aquest context, necessari i qu vol dir suficient) i justifica lesrespostes.

133

1) Troba una proposici equivalent a (pq) r on no hi aparegui cap connectiu diferentde i. Justifica lequivalncia (aplicant equivalncies conegudes o mitjanant taulesde veritat).

2) s necessari acabar en 00 per ser mltiple de 50? I suficient? Explica clarament quhas de demostrar/refutar per veure la suficincia i la necessitat de les condicions (quequedi clar qu vol dir, en aquest context, necessari i qu vol dir suficient) i justifica lesrespostes.



134

1) Usant els predicats N per ser nombre enter i P per ser enter parell, simbolitza enel llenguatge del clcul de predicats els enunciats segents:

a) No tots els nombres enters sn parells

b) Tot nombre enter t dues arrels quadrades diferents

2) Perqu el producte de dos nombres sigui parell, s necessari que algun dels dos nom-bres sigui parell? I suficient? Explica clarament qu has de demostrar/refutar perveure la suficincia i la necessitat de les condicions (que quedi clar qu vol dir, enaquest context, necessari i qu vol dir suficient) i justifica les respostes.

135

1) Usant els predicats P per ser enter parell i S per ser enter senar, simbolitza en elllenguatge del clcul de predicats els enunciats segents:

a) Cap nombre enter s parell i senar alhora

b) Hi ha dos nombres enters que sn parells (s a dir, al menys dos nombres)

2) Perqu el producte de dos nombres sigui senar, s necessari que tots dos nombressiguin senars? I suficient? Explica clarament qu has de demostrar/refutar per veurela suficincia i la necessitat de les condicions (que quedi clar qu vol dir, en aquestcontext, necessari i qu vol dir suficient) i justifica les respostes.

136

1) Usant els predicats P per ser enter parell i S per ser enter senar, simbolitza en elllenguatge del clcul de predicats els enunciats segents:

a) No hi ha nombres enters parells amb quadrat senar

b) Hi ha ms dun nombre enter senar

2) s necessari que dos nombres siguin iguals perqu lun ms el quadrat de laltrecoincideixi amb laltre ms el quadrat de lun? I suficient? Explica clarament quhas de demostrar/refutar per veure la suficincia i la necessitat de les condicions (quequedi clar qu vol dir, en aquest context, necessari i qu vol dir suficient) i justifica lesrespostes.




137

1) Si A, B i C sn conjunts tals que AB AC, es compleix que C B? Justificala resposta (la resposta no pot ser un diagrama de Venn).

2) Siguin A i B subconjunts dun conjunt no buit ? Si AcB = ABc, es pot afirmarque A = ? Justifica la resposta (la resposta no pot ser un diagrama de Venn). Xc sel complementari de X en .

138

1) Si A, B i C sn conjunts, es compleix que A (B C) (A B) C? Justifica laresposta (la resposta no pot ser un diagrama de Venn).

2) Siguin A, B i C conjunts, A no buit. Si C A (AB), es pot afirmar que C = ?Justifica la resposta.

139

1) Siguin A i B subconjunts dun conjunt no buit . Si A Bc i A B = , es potafirmar que A = Bc? Justifica la resposta (la resposta no pot ser un diagrama deVenn). Xc s el complementari de X en .

2) Siguin A i B conjunts. Es pot afirmar que P(A B) = P(A) P(B)? Justifica laresposta. P(X) representa el conjunt de les parts de X.

140

1) Siguin A, B i C subconjunts dun conjunt no buit . Si A (BC)c, es pot afirmarque A B = ? Justifica la resposta (la resposta no pot ser un diagrama de Venn).Xc s el complementari de X en .

2) s transitiva la relaci 6? Justifica la resposta.

141

1) Siguin A, B i C subconjunts dun conjunt no buit . Es pot afirmar que (AB)cC =Bc (C A)? Justifica la resposta (la resposta no pot ser un diagrama de Venn). Xcs el complementari de X en .

2) En el conjunt N dels nombres naturals definim la relaci R de la manera segent:mR n si, i noms si, |m n| 4. s R transitiva? Justifica la resposta.



142

1) Si A, B i C sn conjunts, s veritat que A (B C) = (A B) C? Justifica laresposta (la resposta no pot ser un diagrama de Venn).

2) Si A i B sn conjunts, es pot afirmar que P(P(A)B) = P(AP(B))? Justifica laresposta. P(X) representa el conjunt de les parts de X.

143 Siguin A i B subconjunts dun conjunt no buit . Si (A Bc) (Ac B) = A B, espot afirmar que A B = ? Justifica la resposta (la resposta no pot ser un diagrama deVenn). Xc s el complementari de X en .

Inducci

144 Sigui f : N N laplicaci f(x) = 2x + 1. Demostreu que per a tot n 1 es compleixf (n)(x) = 2nx+2n 1, on f (n) = f f (composici de f amb ella mateixa n vegades;f (1) = f).

145 Proveu que per a tot n 3 es compleix:1

n + 1+

1

n + 2+

1

n + 3+ + 1

2n>

3

5

146 Sigui f : Q Q laplicaci f(x) = x2

+ 1. Demostreu que per a tot n 1 es compleixf (n)(x) = x

2n 1

2n1 +2, on f(n) = f f (composici de f amb ella mateixa n vegades;

f (1) = f).

147 Proveu que per a tot n 2 es compleix:n

k=1

1k

>

n

148 Proveu que per a tot n 2 es compleix:4n

n + 1 0.

2) Proveu que si n 1, llavors 6n 1 s mltiple de 5.

199

1) Trobeu una soluci entera (x0, y0) de lequaci 61x + 78y = 1 tal que x0 > 0.




200

1) Trobeu una soluci entera (x0, y0) de lequaci 77x + 67y = 1 tal que x0 > 0.


201

1) Trobeu una soluci entera (x0, y0) de lequaci 63x + 59y = 1 tal que y0 > 0.


202

1) Trobeu una soluci entera (x0, y0) de lequaci 81x + 77y = 1 tal que y0 < 0.

2) Proveu que si n 1, llavors (5)n 1 s mltiple de 6.

203

1) Trobeu una soluci entera (x0, y0) de lequaci 70x + 83y = 1 tal que y0 < 0.

2) Proveu que si n 1, llavors (10)n 1 s mltiple de 11.


204

1) Definiu el concepte duni de conjunts. Siguin A, B i C conjunts. Demostreu:

A B C (A C B C)

2) Definiu el concepte de composici daplicacions. Siguin A, B i C conjunts i f : A Bi g : B C aplicacions. Demostreu que si f i g sn injectives, aleshores g f sinjectiva.

205

1) Sigui f : R {7} R {5} laplicaci definida per:

f(x) =5x

x 7Proveu que s bijectiva i trobeu la seva inversa.



2) Definim a N N la relaci R:(x, y)R(x, y) x + y = x + y

Proveu que R s transitiva.

206 Sigui R una relaci dequivalncia en un conjunt A. Donats a i b elements de A, demostrarlequivalncia de les afirmacions segents:

1) [a] [b] 6= 2) a [b]3) [a] [b]


207

a) Proveu que hi ha infinits nombres primers (teorema dEuclides).

b) Sigui m 2 un enter. Demostreu que si a b (mod m) i a b (mod m), llavorsa + a b + b (mod m).

208

a) Calculeu els inversos de totes les classes no nul.les de Z7. Justifiqueu tots els passos.

b) Resoleu el sistema dequacions segent a Z7:

5 x 5 y = 43 x + 2 y = 5

Justifiqueu tots els passos.

209 Si n Z, definim el conjunt Mn = {x Z : n | x}.1) Siguin p i q nombres primers diferents. Proveu que Mp Mq = Mpq.2) Sigui p un nombre primer. Proveu que Mp2 Mp.

210 Proveu per inducci que si n 1, aleshores:

2 6 10 (4n 2) = (2n)!n!



1.20 Examen final de reavaluaci 10/07/2013

211 Definim f : Z7 Z7, f(x) = 4 x + 2. Considereu els conjunts A = {1, 2, 3, 5} iB = {1, 5, 6}.1) Obteniu f [S], on S = A B.2) Estudieu si f s bijectiva, si t inversa i, en cas afirmatiu, obteniu f1.

3) Obteniu f1[A B].

212 Demostreu que 6|(7n + 5), per a tot n natural:1) Per inducci.

2) Per congruncies.

3) Per classes de residus.

213

1) Sigui n N. Calculeu mcd(3n + 10, 2n + 7).2) Sigui n Z. Proveu que n2 + 3n + 6 s parell.

3) Sigui n N. Calculeun

k=0

(n

k

)7k.


214 Sigui n un nombre enter. Demostreu que les proposicions segents sn equivalents:

a) n s senar;

b) n2 s de la forma 4k + 1, per a algun k Z;c) n2 + 1 s parell.

Justifiqueu tots els passos.

215 Demostreu, per inducci sobre n, que si n 1, aleshores:1 + 3 5 + + (1)n(2n 1) = (1)n n

Expliciteu, al pas inductiu, la hiptesi dinducci i el qu voleu demostrar. Justifiqueutots els passos.




216 Siguin A, B i C conjunts. Proveu que si AB = A, llavors ABC = BC. Justifiqueutots els passos.

217 Sigui n 2 i considerem el conjunt X = {0, 1}n de les paraules binries de longitud n.Considerem la relaci R definida en X de la manera segent:

x1x2 xn R y1y2 yn x1 = y1 x2 = y2a) Comproveu que R s una relaci dequivalncia.

b) Trobeu les classes dequivalncia, dient quin sn els elements de cada classe.

c) Doneu per extensi el conjunt quocient i digueu quants elements t.

Observaci: {0, 1}n = {0, 1} n {0, 1}. Un element (x1, x2, . . . , xn) {0, 1}n tamblescrivim com a x1x2 . . . xn.

1.23 Examen final 09/01/2014

218 Considerem lequaci a x + (3 + 2a) y = 10, on a Z.1) Determineu tots els enters a tals que lequaci anterior t almenys una soluci entera.

2) Trobeu totes les solucions enteres de lequaci anterior quan a = 31.

219 Sigui n N. Proveu que si n 4 (mod 6), aleshores 10n + 3 0 (mod 7).

220 Considerem laplicaci f : Z400 Z400 definida de la manera segent:

f(x) =

{7 x + 1, si x {0, 2, , 398}4 x + 3, si x {1, 3, , 399}

a) s f injectiva?

b) s f exhaustiva?

c) Calculeu f1[{201}].



1.24 Examen de recuperaci del primer parcial 09/01/2014

221 Proveu per inducci que si n 1, llavors 3 52n+1 +23n+1 s un mltiple de 17. Expliciteuclarament, en el pas inductiu, quina s la hiptesi dinducci i el que sha de demostrar.

222 Considerem les proposicions segents referides a nombres naturals:

P1) x y (x + y = 0)P2) x y (x + y = y)a) Negueu-les i expresseu el resultat final sense utilitzar el smbol . Justifiqueu tots els

passos.

b) Digueu si sn certes o falses i justifiqueu la resposta en cada cas.

1.25 Examen de recuperaci del segon parcial 09/01/2014

223 Siguin A i B conjunts. Demostreu que si A B, llavors P(A) P(B). s cert elrecproc? Justifiqueu la resposta.

224 Definim a R2 la relacin R segent:

(x1, y1)R(x2, y2) y1x21 + 1

=y2

x22 + 1

a) Proveu que R s una relaci dequivalncia.

b) Trobeu la classe dequivalncia dels elements (0, 0), (0, 1) i (0,2).c) Trobeu la classe dequivalncia de (a, b) R2. Descriviu-la geomtricament.


225 Siguin A,B,C conjunts tals que B Cc = .a) Demostreu que A \ (A \B) Cb) Demostreu que, en general, C 6 A \ (A \B).

226 Considerem laplicaci f : Z Z Z definida per:f(x, y) = 333x + 120y



a) s injectiva? Justifiqueu la resposta.

b) s exhaustiva? Justifiqueu la resposta.

c) Calculeu f1[{3}].

227 Demostreu que, per a qualsevol enter n 2, els dos ltims dgits del nombre 11n 10nsn 01.

228 Considerem, al conjunt Z, la relaci:

xRy mcd(x, 4) = mcd(y, 4)

a) Demostreu que R s dequivalncia.

b) Doneu una descripci de cada una de les classes dequivalncia. En la descripci no espot usar mcd(, 4) ni cap relaci de congruncia. Doneu el conjunt quocient Z/R.


229 Proveu per inducci que si n 1, llavors:n

k=1

k(k + 2) =n(n + 1)(2n + 7)

6

Al pas inductiu, indiqueu clarament quina s la hiptesi dinducci i el que heu de de-mostrar. Justifiqueu tots els passos.

230 Siguin x, y Z. Proveu que les proposicions segents sn equivalents:a) x y s senar;b) x + y s senar;

c) 3x + y s senar.


231 Definim a R la relaci S per:

xSy x y Q



a) Proveu que S s una relaci dequivalncia a R.

b) Calculeu la classe dequivalncia de 0.

Justifiqueu les respostes.

232 Definim les aplicacions f, g : Z Z de la manera segent:

f(n) =

{n2, si n s parell(n 1)2, si n s senar g(n) =

{3n, si n s parell3n + 1, si n s senar

a) Proveu que per a tot n Z es compleix (g f)(n) = 3f(n).b) s f una aplicaci injectiva? Justifiqueu la resposta.

c) s g una aplicaci exhaustiva? Justifiqueu la resposta.

d) Sigui T = {3k : k Z}. Calculeu el conjunt f [g1[T ]].

1.29 Examen final 12/06/2014

233 Volem demostrar que si n Z, llavors 5n2 + 10 no s el quadrat dun nombre enter. Hofarem per reducci a labsurd. Suposem que existeixen n,m Z tals que 5n2 + 10 = m2.1) Proveu que 5 | m.2) Proveu que 5 | (n2 + 2).3) Proveu que n2 = 3, a Z5.

Deduu que si n Z, llavors 5n2 + 10 no pot ser el quadrat dun nombre enter.

234 Una banda de 13 pirates sapodera duna caixa de monedes dor. Desprs de repartir-lesequitativament queda un residu de 8 monedes. Moren 2 pirates, es torna a repartir i es tun residu de 3 monedes. Desapareixen 3 pirates ms, es torna a repartir i es t un residude 5 monedes. Quin s, com a mnim, el bot dels pirates?

235

a) Calculeu totes les solucions enteres de lequaci 13x 47y = 10.b) Trobeu la soluci (x, y) de lequaci anterior tal que y t el valor negatiu ms gran

possible.





k=0

2k (2k + 1) k! = (n + 1)! 2n+1 1

Indiqueu clarament, al pas inductiu, quina s la hiptesi dinducci i el que volem demos-trar.

237

a) Siguin p, q, r lletres proposicionals. Quina de les frmules proposicionals segents suna tautologia?

1) ((p q) r) ((p r) (q r))2) ((p r) (q r)) ((p q) r)

b) Siguin a, b, c Z. Proveu que si a + b = c, llavors almenys un dels enters a, b o c sparell.


238 Definim a R2 la relaci S de la manera segent:

(a, b)S(c, d) a + b = c + da) Proveu que S s una relaci dequivalncia.

b) Calculeu la classe dequivalncia de lelement (3, 1) i descriviu-la geomtricament.

c) Sigui D = {(x, y) R2 : y = x}. Proveu que per a cada classe dequivalncia [(a, b)],la intersecci D [(a, b)] t noms un element i trobeu-lo.

239 Definim laplicaci f : R2 R2 per la frmula segent:f(x, y) = (x + y, x y)

a) Proveu que f s una aplicaci injectiva.

b) Proveu que f s una aplicaci exhaustiva.

c) Justifiqueu que f t inversa i trobeu-la.

d) Calculeu f1(6, 2).




240

1) Se sap que la proposici x X (A(x) B(x)) s certa. Considerem els conjunts:

U = {x X |A(x)}, V = {x X |B(x)}.

Raona quina de les inclusions segents s certa: U V o V U .2) Sigui f : R R, f(x) = x3 + x. Demostreu:

a R (a 6= 0 f(a) 6= 0)

3) Demostreu que 15 2n 1 (mod 7), per a tot n natural i mltiple de 3.

241 Una relaci binria R en un conjunt A s circular quan es compleix:

a, b, c A (aRb bRc cRa)

Proveu:

1) Si R s dequivalncia, llavors s circular.

2) Si R s reflexiva i circular, llavors s simtrica.

3) Si R s reflexiva i circular, llavors s dequivalncia.

242 Es dna el sistema de congruncies segent:{x a (mod m)x b (mod n)

1) Demostreu que el sistema t soluci si, i noms si, es compleix d | a b, ssentd = mcd(m,n).

2) Deduu que el sistema:{x 1 (mod 12)x b (mod 14)

t soluci si, i noms si, b s senar.

3) Resoleu el sistema anterior quan b = 17.




243 Considerem la proposici P segent:

Per a tots els enters m i n, si m n s mltiple de 4, aleshores m2 n2 smltiple de 4.

a) Formalitzeu la proposici P . (Totes les variables prenen valors enters.)

b) Negueu lexpressi que heu obtingut a lapartat anterior. (No poden quedar quantifi-cadors negats directament.)

c) Proveu que la proposici P s certa. Indiqueu quin mtode de demostraci utilitzeu.

d) Considereu la proposici R segent:

Per a tots els enters m i n, si m2 n2 s mltiple de 4, aleshores m n smltiple de 4.

Qu hem de fer si volem provar que R s falsa? Proveu que R s una proposici falsa.

244 Calculeu el valor de lenter positiu n sabent que:n

k=n(3k + 5) = 1005.


245 Siguin X = {1, 2, 3, 4} i Y = {4}. Considerem al conjunt P(X) de las parts de X larelaci R definida per:

A R B A Y = B Ya) Proveu que R s una relaci dequivalncia.

b) Trobeu totes les classes dequivalncia.

c) Trobeu el conjunt quocient P(X)/R.

246 Proveu per inducci que si n 2, aleshores:n

k=2

(1 1

k2

)=

1 + n

2n

Indiqueu clarament, en el pas inductiu, quina s la hiptesi dinducci i qu hem dedemostrar.



1.35 Examen final 14/01/2015

247 Considerem laplicaci f : Z80 Z80 definida per f(x) = 2x+1. Siguin A = {1, 3, 22, 43}i B = {3, 50}.a) Calculeu els conjunts f [A] i f1[B].

b) s f injectiva? s f exhaustiva?

c) Comproveu que f [A f1[B]] = f [A] B.

248 Calculeu 2145616140 (mod 101).

249

a) Siguin a, b Z i p, q nombres primers diferents. Demostreu que a b (mod pq) si, inoms si, a b (mod p) i a b (mod q).

b) Calculeu les solucions de x2 4 (mod p), on p s un nombre primer senar.c) Proveu que la congruncia x2 4 (mod 35) t 4 solucions mdul 35. Trobeu les

solucions de la congruncia que siguin diferents de x 2 (mod 35) i de x 2(mod 35).


250

1) Sigui n N. Proveu lequivalncia segent: n s parell n3 s parell.2) Proveu que 3

2 s irracional. (Podeu usar lapartat anterior, si s necessari.)

251 Considerem la proposici segent: Hi ha un nombre natural que s ms petit o igual quetots els nombres naturals.

a) Formalitzeu la proposici anterior, tenint en compte que: lunivers de discurs s elconjunt dels nombres naturals; podeu usar els quantificadors i connectives lgiques, elsmbol i les variables que siguin necessries.

b) Negueu la formalitzaci que heu obtingut a lapartat anterior (a lexpressi final no hipot aparixer el smbol de negaci).




252 Sigui n 1 un nombre enter. Considerem el conjunt X = {1, 2, . . . , n}. Considerem aP(X) la relaci R definida per: A R B si, i noms si, |A| = |B|. (|A| denota el cardinaldel conjunt A.)


b) Trobeu la classe dequivalncia de {1, 3, 4, 5} quan n = 5.c) Trobeu el conjunt quocient P(X)/R i digueu quants elements t.

253 Proveu que si n 1, llavors nk=1 k5k = (5 + (4n 1)5n+1)/16.1.38 Examen final de reavaluaci 6/02/2015

254 Considerem laplicaci f : Z15 Z15 definida per f(x) = 5x.1) Calculeu els conjunts f [Z15] i f1[{0}].2) Estudieu si f s injectiva o exhaustiva.

3) Demostreu que f f f = f .4) Considerem la relaci R en Z15 definida per xRy si, i noms si, f(x) = f(y).



255 Siguin A, B i C conjunts.

1) Demostreu que si AB = , AC = i B C = , llavors AB C = . Indiqueuquin mtode de demostraci utilitzeu i justifiqueu els passos.

2) Escriviu el recproc de la implicaci anterior. s certa aquesta implicaci? Per qu?Justifiqueu la resposta.

3) Considerem la propietat: si A 6= i A B C, aleshores B C 6= . s certa ofalsa? Justifiqueu la resposta.


2 3 + 22 32 + + 2n 3n = 2n+2 3n+1 1

2



257 Trobeu lenter positiu x ms petit tal que:

x 425 (mod 23), x 145 (mod 51), x 293 (mod 91)

258 Considerem el polinomi p(x) = x1024 + x512 + x256 + 1. Calculeu p(23) mdul 251.


259 Considerem la proposici P segent:

Tot enter s tal que la seva meitat s entera o la sevameitat sumada amb 0, 5 s entera.

a) Formalitzeu la proposici P . (Totes les variables prenen valors enters.)

b) Negueu lexpressi que heu obtingut a lapartat anterior. (No poden quedar quantifi-cadors negats directament.)

c) Indiqueu quina seria la hiptesi si volem demostrar la proposici P utilitzant el mtodede reducci a labsurd.

d) Proveu que la proposici P s certa. Indiqueu quin mtode de demostraci utilitzeu.

260 Proveu per inducci que si n 2, llavors:n

i=2

1

i2 1 =(n 1)(3n + 2)

4n(n + 1).


261

1) Construu dos conjunts A i B que compleixin totes les condicions segents: A B;A B; A B = {1}.

2) Siguin A, B i C conjunts tals que A B C. Demostreu que:

C \ A = (C \B) (B \ A).

3) Siguin X = {1, 2, 3, 4} i M = {1, 2}.a) Escriviu per extensi el conjunt P(X).



b) Definim laplicaci:

f : P(X) P(X), f(A) = A M.Estudieu si f s injectiva i si f s exhaustiva.

262 Definim a R {0} la relaci:

a R b a 1a

= b 1b

1) Demostreu que R s una relaci dequivalncia.

2) Proveu que si a R b, llavors (a b)(ab + 1) = 0.3) Calculeu la classe dequivalncia dun nombre real no nul a.

4) Escriviu el conjunt quocient.

1.41 Examen final 09/06/2015

263 Trobeu lenter positiu x ms petit tal que:

x 5 (mod 7), x 12 (mod 8), x 13 (mod 9), x 16 (mod 11)

264 Sigui p i q nombres primers diferents.

a) Demostreu que pq1 + qp1 1 (mod p) i que pq1 + qp1 1 (mod q). (Pista: podeuusar el teorema petit de Fermat.)

b) Deduu de lapartat a) que pq1 + qp1 1 (mod pq).c) Calculeu 2328 + 2922 a Z667.

265

a) Trobeu totes les solucions de lequaci 2m + 3d = 78 amb d,m Z i d 1 i m 1.b) Demostreu que si d,m Z sn enters positius tals que 2m + 3d = 78 i d | m, llavors

d = 2 i m = 36 o d = 6 i m = 30.

c) Trobeu tots els enters positius a, b tals que a < b, mcd(a, b) = d, mcm(a, b) = m,2m + 3d = 78.




266 Proveu que si n 1, llavors:n

k=1

1

(4k 3)(4k + 1) =n

4n + 1.

267 Considerem la proposici segent: Per a tot nombre racional x existeix un nombre entern tal que nx s enter.

a) Formalitzeu la proposici anterior.

b) Negueu la formalitzaci que heu obtingut a lapartat anterior (a lexpressi final no hipot aparixer el smbol de negaci).

c) Digueu si la proposici donada s certa o falsa i justifiqueu la vostra afirmaci.


268 Sigui F el conjunt dalumnes de lassignatura de FM de la FIB i sigui X = F F .Suposem que hi ha 8 grups, de l1 al 8. Si a F , denotem per g(a) el seu grup. Definimuna relaci a X:

(a, b)R(c, d) g(a) + g(b) = g(c) + g(d).



c) Trobeu el conjunt quocient X/R i digueu quants elements t.

269 Definim laplicaci f : N N per:

f(n) =

{2n + 1, si n parelln + 2, si n senar

a) s f injectiva? s f exhaustiva?

b) Trobeu subconjunts A,B N tals que: f [A B] = f [A] f [B].c) Trobeu subconjunts A,B N tals que: f [A B] f [A] f [B] (inclusi estricta).




270

1) Sigui n enter. Proveu per classes de residus que 6|n3 n.2) Sigui n enter. Proveu per congruncies que 2|n2 + n 2.3) Sigui n nombre natural. Proveu que 2|n3 + n + 6 per inducci i utilitzant classes de

residus.

271 Considereu la propietat 22|23n 1, per a n nombre natural.1) Demostreu-la per inducci.

2) Demostreu-la aplicant la frmula del binomi de Newton.

3) Estudieu si es pot demostrar aplicant la frmulaxn yn = (x y)(xn1 + xn2y + + xyn2 + yn1).

272

1) Demostreu que laplicaci f : Z13 Z13, f(x) = 5 x + 7 s bijectiva i obteniu f1.2) Calculeu mcd(3n + 4, 4n + 5), per a n nombre natural.


2Solucions


5 Tenim en compte les equivalncies: (p q) (p q) (q p), (p q) ((p) q),(p q) (p ((q))) (p (q)) i les lleis de de Morgan.1)

p q (p q) (q p) ((p) q) ((q) p) ((((p) q)) (((q) p)))

2)

p q (p q) (q p) ((p) q) ((q) p) ((p (q))) ((q (p)))

3) p q (p q) (q p) ((p q) ((q p)))

7

1) x (P (x) y(P (y) y = x))2) x, y ((P (x) P (y) x 6= y) z(P (z) z = x z = x))

8

) En primer lloc, observem que: A (B C) = (A B) (A C).Si x A B, llavors x A i x B. Volem provar que x A i x C.Que x A ja ho sabem, per hiptesi.Suposem que x / C. Llavors tenim duna banda que x A i daltra x / C. Pertant, x A C (A B) (A C). Ara, per hiptesi, podem afirmar quex A B. s a dir, x A i x / B.

S1

Exmens resolts de Fonaments Matemtics S2

Per ara tenim que x B i x / B: contradicci.Per tant, x C.

) Tenim:

x A (B C) x A x / B C x A (x B x C) x A (x / B x / C) (1) (x A x / B) (x A x / C) (2) x A B x A C

(1): llei de de Morgan; (2): distributiva.

Ara si x A C llavors x A i x / C. Per tant, per hiptesi tenim que x A ix / B. Aix doncs, en qualsevol cas obtenim que x AB, com volem demostrar.

9 Es tracta duna equivalncia. Per tant, haurem de demostrar dues implicacions.

) Suposem que B = . Llavors:

(A B) (B A) = (A ) ( A) = A = A

Efectivament: els elements de A sn els elements de A que no pertanyen a ; sa dir, tots els elements de A. A ms, A est format pels elements de que nopertanyen a A; s a dir, s .

) Suposem ara que (AB) (BA) = A. Volem demostrar que B = . Ho fem perreducci al absurd. Suposem que B 6= . Llavors existeix un element x B. Aradistingim dos casos: x A i x / A.Cas 1: x A. Llavors x A, per x / BA i x / AB; s a dir, x / (AB)

(B A). Contradicci, perqu aquest conjunt s igual a A per hiptesi.Cas 2: x / A. Llavors x B A i, per tant, x (A B) (B A) = A.

Contradicci perqu estem suposant que x / A.Per tant, en qualsevol cas arribem a una contradicci. Conseqentment, B = .

10 Es tracta duna equivalncia. Per tant, haurem de demostrar dues implicacions.

) Suposem que A B = . Llavors:

A B = {x A : x / B} = AB A = {x B : x / A} = B

Per tant, (A B) (B A) = A B.

J.L. Ruiz (ed.) c 20102015 CAPTOL 2. SOLUCIONS


) Suposem ara que (AB) (BA) = AB. Volem demostrar que AB = . Hofem per reducci al absurd. Suposem que A B 6= . Llavors existeix un elementx AB, s a dir x A i x B. Per aquest element x satisf: x / AB, perqux B, i x / B A, perqu x A. Per tant, x / (A B) (B A) i x A B.Contradicci, perqu estem suposant que aquests dos conjunts sn iguals.

11 En primer lloc observem que la condici Cc B = s equivalent a dir que B C.Efectivament: si Cc B = i x B, llavors x / Cc i per tant x C. Recprocament, siB C i x Cc B, llavors x B i x / C; s a dir, x C i x / C. Absurd. Per tant,Cc B = .

Sigui x A. Distingim dos casos:Cas 1: x B. Llavors x C, per lanterior observaci.Cas 2: x / B. Llavors x A Bc i, per hiptesi, aquest conjunt s un subconjunt de

C. Per tant, x C.

12 En primer lloc observem que la condici Cc B = s equivalent a dir que B C.Efectivament: si Cc B = i x B, llavors x / Cc i per tant x C. Recprocament, siB C i x Cc B, llavors x B i x / C; s a dir, x C i x / C. Absurd. Per tant,Cc B = .

En segon lloc, qu s A (A B)?

x A (A B) x A x / (A B) x A (x / A x B) (x A x / A) (x A x B) x A B

s a dir: A (A B) = A B.Per tant, hem de demostrar que A B A C. Sigui x A B. Llavors x A i

x B. Per hiptesi, si x B, llavors x C. Per tant, x A i x C. s adir, x AC.

13 Sigui x D C. Llavors x D i x C. Volem demostrar que x Ac. Ho fem perreducci a labsurd. Suposem doncs que x / Ac. Llavors x A. s a dir: x D i x A.Per hiptesi, x D B. Per ara tenim que x A B C, que s el conjunt buit, perhiptesi. Contradicci.

Per tant, x Ac.

14 Donem dues demostracions.Soluci 1: Sigui x B qualsevol. Llavors x A B, i, per la primera hiptesi,

x A C. Ara tenim dos casos.Cas 1) x A. Llavors x A B i per la segona hiptesi x A C i per tant x C.Cas 2) x / A. Com tenem x A C, necessriament llavors x C.



En ambds casos resulta x C, i per tant queda provat que B C.

Soluci 2: Sigui x B un element qualsevol. Per la definici duni tindrem x A B. Per la primera part de la hiptesi resulta llavors que x A C i a ms recordemque x B.

Per tant x (AC)B, que per la propietat distributiva assegura que x (AB)(C B). Emprant la segona part de la hiptesi resulta ara que x (A C) (B C).Tornant a aplicar la propietat distributiva resulta x (AB)C. I per tant, en particularresulta que x C. Per tant queda provat que B C.

15 Ho fem per reducci a labsurd. Suposem que A C = . Per hiptesi, A B 6= ; pertant, existeix un element x AB. Aquest element x no pot ser un element de C, perquestem suposant que A C = . Per tant, x Cc. Per ara tenim que x B i x Cc, i,per hiptesi, sabem que B Cc = . Contradicci. Per tant, A C 6= .

16 Es tracta de demostrar una equivalncia. Per tant, hem de provar dues implicacions.

) La hiptesis ens diu que tot element de C ho s de A i de B. Si C Ac 6= ,aleshores existeix x C Ac, i llavors x C i x / A. Per si x C, llavors, perhiptesi, x A. Ara tenim que x A i x / A: Contradicci. Per tant, C Ac = .Anlogament es demostra que C Bc = .

) Hem de provar una inclusi: C AB. Sigui x C. Volem veure que x A i quex B. Suposem que x / A. Llavors tenim que x C Ac, que per hiptesi s elconjunt buit. Contradicci. Per tant, x A. Anlogament demostrem que x B.

17

1) a) Si n s parell, llavors f(n) = n i f(f(n)) = f(n) = n,

b) Si n s senar, llavors f(n) = n + 1 i f(f(n)) = f(n + 1); com ara n + 1 s parell,f(f(n)) = f(n + 1) = n + 1.

En tots els casos f f = f .2) f [{1, 2, 3, 4}] = {2, 4}. f no s injectiva ja que f(2k) = f(2k 1).3) f1[{0, 1, 2}] = {0, 1, 2}. f no s exhaustiva ja que el nombres senars no tenen antii-

matge.

18

1) a) Si n s mltiple de 3, llavors f(n) = n i f(f(n)) = f(n) = n,

b) Si n no s mltiple de 3, llavors f(n) = 3n i f(f(n)) = f(3n); com ara 3n smltiple de 3, f(f(n)) = f(3n) = 3n.

En tots els casos f f = f .



2) f [{1, 2, 3, 4}] = {3, 6, 12}. f no s injectiva ja que si n no s mltiple de f(3n) = f(n).3) f1[{0, 1, 2}] = {0}. f no s exhaustiva ja que el nombres que no sn mltiple de 3 no

tenen antiimatge.

19

1) f [{2,1, 0, 1, 2}] = {4,1, 0, 1, 4}.2) Hem de veure que si f(n1) = f(n2), llavors n1 = n2.

f(n1) = f(n2) n21 = n22 n21 = n22 n21 n22 = 0 n21 + n22 = 0a) si n21 + n

22 = 0, llavors n1 = n2 = 0,

b) si n21 n22 = 0, llavors (n1 n2)(n1 + n2) = 0 i n1 n2 = 0, ja que o n1, n2 < 0 on1, n2 0.

En tots els casos n1 = n2.

3) f1[{0, 1, 2}] = {0, 1}. f no s exhaustiva ja que el nombres que no sn quadratsperfectes no tenen antiimatge.

20

1) f [{2,1, 0, 1, 2}] = {4, 2, 0, 1, 3}. f [{5,3, 0, 3, 5}] = {10, 6, 0, 5, 9}.2) f1[{0, 1, 2}] = {1, 0, 1}. f1[{0, 3, 6}] = {3, 0, 2}.3) Hem de veure que si f(n1) = f(n2), llavors n1 = n2. Notem que si f(n1) = f(n2),

llavors n1, n2 > 0 o n1, n2 0, ja que si n1 > 0 i n2 0, llavors tindrem que unnombre s parell i senar a la vegada.

a) si n1, n2 > 0, llavors 2n1 1 = 2n2 1, i n1 = n2,b) si n1, n2 0, llavors 2n1 = 2n2, i n1 = n2.En tots els casos n1 = n2.

4) Hem de veure que per a tot m N existeix n Z tal que f(n) = m :a) si m s parell, m = 2k amb k 0, llavors f(k) = m,b) si m s senar, m = 2k 1 amb k 1, llavors f(k) = m.

21

1) f [{0, 1, 2, 3, 4, 5}] = {0, 1,1, 2,2, 3}.f [{0, 3, 5, 6, 7, 10}] = {0, 2, 3,3, 4,5}.

2) f1[{1, 0, 1, 2}] = {2, 0, 1, 3}. f1[{3,1, 0, 1}] = {0, 1, 2, 6}.



3) Hem de veure que per a tot m Z existeix n N tal que f(n) = m :a) si m 0, llavors f(2m 1) = m,b) si m < 0, llavors f(2m) = m.

4) Hem de veure que si f(n1) = f(n2), llavors n1 = n2. Notem que si f(n1) = f(n2),llavors n1 i n2 sn tots parells o tots dos sn senars, ja que si un fos parell i laltre fossenar llavors tindrem un nombre que s a la vegada ms gran o igual que 0 i ms petitque 0.

a) Si n1 i n2 sn parells, llavors n12 = n22 , i n1 = n2,b) si n1 i n2 sn senars, llavors n1+12 =

n2+12

, i n1 = n2.

En tots els casos n1 = n2.

22

1) f1[{0, 1, 2, 3, 4, 5}] = {1, 0, 1, 2, 3, 4, 5, 10, 15, 20, 25}.2) Hem de veure que per a tot m N existeix n N tal que f(n) = m : si m N, llavors

f(5m) = m.

3) f [{0, 1, 2, 5, 10, 15}] = {0, 1, 2, 3}. No s injectiva ja que si n no s mltiple de 5 llavorsf(5(n + 1)) = f(n).

23

1) Hem de veure que f1[S] P i P f1[S] :a) f1[S] P : si k f1[S], llavors existeix l S tal que l = k2 + 1. Donat que l s

senar, k2 s parell i, per tant, k s parell; s a dir, k P .b) P f1[S]: si k P , llavors f(k) = k2 + 1 s senar, ja que k s parell. En

conseqncia, f(k) S i k f1[S].2) Per exemple, 3 no t antiimatge perqu no hi ha cap natural amb quadrat igual a 2.

3) No s injectiva perqu f(n) = f(n)4) No, perqu no s exhaustiva ni injectiva.

24

1) f1[{1, 0, 1, 2}] = {3,1, 0, 2}. No es exhaustiva perqu 2 no t antiimatge.2) Hem de veure que si f(n1) = f(n2), llavors n1 = n2. Notem que si f(n1) = f(n2),

llavors n1 i n2 sn tots parells o tots dos sn senars, ja que si un fos parell i laltre fossenar llavors tindrem un nombre que s a la vegada parell i senar.



a) Si n1 i n2 sn parells, llavors 7n1 = 7n2, i n1 = n2,

b) si n1 i n2 sn senars, llavors n1 + 2 = n2 + 2, i n1 = n2.

3) No, perqu no s exhaustiva.

25

1) f [{2,1, 0, 1, 2}] = {1, 3, 7}. No s injectiva ja que f(2) = f(1).2) f1[{0, 1}] = {1, 0}. No es exhaustiva perqu 1 no t antiimatge.3) No, perqu no s ni exhaustiva ni injectiva.

26

1) Noms cal notar que f(p) = p per tot p P .2) f [{2, 6, 9, 11, 35}] = {2, 3, 5, 11}. No s injectiva ja que f(2) = f(6).3) Hem de veure que per a tot m P existeix n A tal que f(n) = m : Noms cal notar

que f(p) = p per tot p P ; una antiimatge de p P s el mateix p.4) No, perqu no s injectiva.

27

1) a) Si n s mltiple de 5, llavors f(n) = n i f(f(n)) = f(n) = n,

b) si n no s mltiple de 5, llavors f(n) = 5n i f(f(n)) = f(5n); com ara 5n s mltiplede 5, f(f(n)) = f(5n) = 5n.

En tots els casos f f = f .2) f [{0, 1, 2, 3, 4, 5}] = {0, 5, 10, 15, 20}. No s injectiva ja que si n no s mltiple de 5,

f(n) = f(5n).

3) f1[{0}] = {0}, f1[{1}] = , f1[{5}] = {1, 5}, f1[{0, 1, 5}] = {0, 1, 5}. No sexhaustiva ja que el enters que no sn mltiple de 5 no tenen antiimatge.

4) No, perqu no s injectiva ni exhaustiva.

28

1) f [{1, 2, 3, 4, 5, 6}] = {2, 1, 3, 5, 4, 6} = A.2) Per inspecci, tenim que:

a) si a1 6= a2, llavors g(a1) 6= g(a2); s a dir, g s injectiva;



b) g[A] = A; s a dir, g s exhaustiva.

Conseqentment g es bijectiva.

3) Hem de veure que si f(n1) = f(n2), llavors n1 = n2. Notem que:

a) si n s mltiple de 3, f(n) s mltiple de 3,

b) si el residu de dividir n per 3 s 1, el de f(n) s 2,

c) si el residu de dividir n per 3 s 2, el de f(n) s 1.

Si f(n1) = f(n2), llavors:

a) o n1 i n2 sn tots dos mltiple de 3,

b) o n1 i n2 sn tots dos mltiple de 3 ms 1,

c) o n1 i n2 sn tots dos mltiple de 3 ms 2.

En qualsevol cas, la condici f(n1) = f(n2) s pot escriure:

n1 + = n2 + , {1, 0, 1},

i, per tant, n1 = n2.

4)

f [{0, 1, 2, 4, 5, 9}] = {f(0), f(1), f(2), f(4), f(5), f(9)}= {0, 2, 1, 5, 4, 9} = B

5) Per inspecci, tenim que:

a) si b1 6= b2, llavors h(b1) 6= h(b2); s a dir, h s injectiva,b) h[B] = B; s a dir, h s exhaustiva.

Conseqentment h es bijectiva.

6) Hem de veure que per a tot m N existeix n N tal que f(n) = m : notem quequalsevol m N s pot escriure com m = 3k o m = 3k + 1 o m = 3k + 2, per a certk N; llavors:a) si m = 3k, f(m) = m,

b) si m = 3k + 1, f(m + 1) = m,

c) si m = 3k + 2, f(m 1) = m.En tots el casos hem trobat una antiimatge de m.

29

1) g[{2, 3, 5, 7, 11}] = {4, 9, 25, 49, 121}; f1[{2}] = {2k : k N}.



2) Si p P , f(g(p)) = f(p2). El primer ms petit que divideix p2 s p; llavors f(g(p)) =f(p2) = p.

3) Hem de veure que per a tot m P existeix n A tal que f(n) = m : noms cal notarque f(p) = p, per tot p P ; una antiimatge de p P s el mateix p.

30

1) f [{0, 1, 2, 4, 8}] = {0, 1, 2, 4}. No es injectiva ja que f(2k + 1) = f(4(2k + 1)), k Z.2) Hem de veure que per a to m Z existeix n Z tal que f(n) = m : una antiimatge

de m Z s n = 2m ja que f(2m) = m.3) No, perqu no s injectiva.

31

Cas inicial: n = 1.

1i=1

i i! = 1 1! = 1 = (1 + 1)! 1 = 2 1

Pas dinducci: Fixem un enter n 1 i suposem que ni=1 i i! = (n + 1)! 1 (hiptesidinducci). Volem demostrar:

n+1i=1

i i! = (n + 2)! 1

Ara tenim:

n+1i=1

i i! =n

i=1

i i! + (n + 1)(n + 1)!

= (n + 1)! 1 + (n + 1)(n + 1)! per H.I.= (n + 1)!(1 + n + 1) 1= (n + 1)!(n + 2) 1 = (n + 2)! 1

Per tant, pel principi dinducci, la propietat s certa per a tot n 1.

32

Cas inicial: n = 1.

1k=1

(1)k1k2 = 1 = (1)0 1(1 + 1)2



Pas dinducci: Fixem un enter n 1 i suposem quenk=1(1)k1 k2 = (1)n1 n(n+1)2(hiptesi dinducci). Volem demostrar:

n+1k=1

(1)k1k2 = (1)n (n + 1)(n + 2)2

Ara tenim:

n+1k=1

(1)k1k2 =n

k=1

(1)k1k2 + (1)n(n + 1)2

= (1)n1 n(n + 1)2

+ (1)n(n + 1)2 per H.I.

= (1)n1(n + 1)(n

2 (n + 1)

)= (1)n (n + 1)(n + 2)

2


33

Cas inicial: n = 1.

1j=1

j(j + 1) = 1 (1 + 1) = 2 = 1 (1 + 1) (1 + 2)3

Pas dinducci: Fixem un enter n 1 i suposem que nj=1 j(j + 1) = n(n+1)(n+2)3(hiptesi dinducci). Volem demostrar:

n+1j=1

j(j + 1) =(n + 1)(n + 2)(n + 3)

3

Ara tenim:

n+1j=1

j(j + 1) =n

j=1

j(j + 1) + (n + 1)(n + 2)

=n(n + 1)(n + 2)

3+ (n + 1)(n + 2) per H.I.

= (n + 1)(n + 2)(n

3+ 1)

=(n + 1)(n + 2)(n + 3)

3


34



Cas inicial: n = 1.1

`=1

1

`(` + 1)=

1

1 + 1=

1

2

Pas dinducci: Fixem un enter n 1 i suposem que n`=1 1`(`+1) = nn+1 (hiptesi din-ducci). Volem demostrar:

n+1`=1

1

`(` + 1)=

n + 1

n + 2

Ara tenim:n+1`=1

1

`(` + 1)=

n`=1

1

`(` + 1)+

1

(n + 1)(n + 2)

=n

(n + 1)+

1

(n + 1)(n + 2)per H.I.

=n2 + 2n + 1

(n + 1)(n + 2)

=(n + 1)2

(n + 1)(n + 2)

=n + 1

n + 2


35


r=1

(3r 2) = 3 2 = 1 = 3 12

Pas dinducci: Fixem un enter n 1 i suposem que nr=1(3r 2) = 3n2n2 (hiptesidinducci). Volem demostrar:

n+1r=1

(3r 2) = 3(n + 1)2 (n + 1)2

Ara tenim:n+1r=1

(3r 2) =n

r=1

(3r 2) + (3(n + 1) 2)

=3n2 n

2+ 3n + 1 per H.I.

=3n2 + 5n + 1

2)

=3(n + 1)2 (n + 1)

2




36


s=1

(4s + 1) = 4 + 1 = 5 = 1 (2 + 3)

Pas dinducci: Fixem un enter n 1 i suposem quens=1(4s+1) = n(2n+3) (hiptesidinducci). Volem demostrar:

n+1s=1

(4s + 1) = (n + 1)(2(n + 1) + 3)

Ara tenim:n+1s=1

(4s + 1) =n

s=1

(4s + 1) + 4(n + 1) + 1

= n(2n + 3) + 4n + 5 per H.I.= 2n2 + 7n + 5

Daltra banda: (n + 1)(2(n + 1) + 3) = (n + 1)(2n + 5) = 2n2 + 7n + 5.


37


v=1

(v2 + v) = 12 + 1 = 2 =1 (1 + 1)(1 + 2)

3

Pas dinducci: Fixem un enter n 1 i suposem quenv=1(v2 + v) = n(n+1)(n+2)3 (hip-tesi dinducci). Volem demostrar:

n+1v=1

(v2 + v) =(n + 1)(n + 2)(n + 3)

3

Ara tenim:n+1v=1

(v2 + v) =n

v=1

(v2 + v) + (n + 1)2 + (n + 1)

=n(n + 1)(n + 2)

3+ (n + 1)2 + (n + 1) per H.I.

=n(n + 1)(n + 2)

3+

3(n + 1)2 + 3(n + 1)

3

=(n + 1)[n(n + 2) + 3(n + 1) + 3]

3

=(n + 1)(n2 + 5n + 6)

3=

(n + 1)(n + 2)(n + 3)

3




38

Cas inicial: n = 1.

1m=1

(5m 3) = 5 3 = 2 = 5 12

Pas dinducci: Fixem un enter n 1 i suposem que nm=1(5m 3) = 5n2n2 (hiptesidinducci). Volem demostrar:

n+1m=1

(5m 3) = 5(n + 1)2 (n + 1)2

Ara tenim:

n+1m=1

(5m 3) =n

m=1

(5m 3) + 5(n + 1) 3

=5n2 n

2+ 5n + 2 per H.I.

=5n2 n + 2(5n + 2)

2

=5n2 + 9n + 4

2

Daltra banda: 5(n+1)2(n+1)2

= 5n2+10n+5n1

2= 5n

2+9n+42

.


39

Cas inicial: n = 1.

1u=1

(u2 u) = 12 1 = 0 = 1 (1 1)3

Pas dinducci: Fixem un enter n 1 i suposem que nu=1(u2 u) = n(n21)3 (hiptesidinducci). Volem demostrar:

n+1u=1

(u2 u) = (n + 1)((n + 1)2 1)

3



Ara tenim:

n+1u=1

(u2 u) =n

u=1

(u2 u) + (n + 1)2 (n + 1)

=n(n2 1)

3+ (n + 1)2 (n + 1) per H.I.

=n(n2 1)

3+

3(n + 1)2 3(n + 1)3

(*)

=(n + 1)[n(n 1) + 3(n + 1) 3]

3

=(n + 1)(n2 + 2n)

3

=(n + 1)((n + 1)2 1)

3

(*) Hem utilitzat que: n2 1 = (n + 1)(n 1).Per tant, pel principi dinducci, la propietat s certa per a tot n 1.

40

Cas inicial: n = 1.

1t=1

t3 = 1 =1(1 + 1)2

4

Pas dinducci: Fixem un enter n 1 i suposem que nt=1 t3 = n2(n+1)24 (hiptesidinducci). Volem demostrar:

n+1t=1

t3 =(n + 1)2(n + 2)2

4

Ara tenim:

n+1t=1

t3 =n

t=1

t3 + (n + 1)3

=n2(n + 1)2

4+

4(n + 1)3

4per H.I.

=(n + 1)2(n2 + 4n + 4)

4

=(n + 1)2(n + 2)2

4


41



Cas inicial: n = 1.

1p=1

1

(p + 1)(p + 2)=

1

(1 + 1)(1 + 2)=

1

6=

1

2(1 + 2)

Pas dinducci: Fixem un enter n 1 i suposem que np=1 1(p+1)(p+2) = n2(n+2) (hiptesidinducci). Volem demostrar:

n+1p=1

1

(p + 1)(p + 2)=

n + 1

2(n + 3)

Ara tenim:

n+1p=1

1

(p + 1)(p + 2)=

np=1

1

(p + 1)(p + 2)+

1

(n + 2)(n + 3)

=n

2(n + 2)+

1

(n + 2)(n + 3)per H.I.

=n(n + 3) + 2

2(n + 2)(n + 3)

=n2 + 3n + 2

2(n + 2)(n + 3)

=(n + 2)(n + 3)

2(n + 2)(n + 3)=

n + 1

2(n + 3)


42 Si d = mcd(a, b), llavors d | a i, per tant, d | 2a. Conseqentment, mcd(2a, d) = d.

43 Si d s un divisor positiu com de 2a i b, llavors d ha de ser un divisor com de 2 i b,perque a i b sn primers entre si. Per b s senar, per tant d = 1. s a dir, mcd(2a, b) = 1.

44 Si p 6 | b i q 6 | a, llavors mcd(pa, qb) = 1, ja que a i b sn primers entre si. Suposem doncsque aquest mcd no s 1 i sigui ` un primer tal que ` | pa i ` | qb. Llavors tenim els casos:

` = p i ` | b: llavors p | mcd(pa, qb); ` = q i ` | a: llavors q | mcd(pa, qb).

s a dir, els nics primers que poden dividir a mcd(pa, qb) sn p o q. Per tant: el mcd sp, q o pq.

45 Si a s parell, llavors existeix un enter a tal que a = 2a. s a dir 2 s un divisor comde a i 2p. Llavors: si p | a, el mcd s 2p; si p 6 | a, el mcd s 2.


Fm Examens Juliol 2015

Documents

Transcript of Fm Examens Juliol 2015