~'('~rn,l(\ !. NOCIONES DE LOG!CA 1. 2. Proposiciones l. 3. Notaciones y conectivos 1 4. Operaciones proposicionales l. 5. Condiciones necesarias y suficientes 1. 6. Leyes lgicas l. 7. Implicaciones asociadas 1. 8. Negacin de una implicacin l. 9. Razonamiento deductivo vlido 1.10. Funciones proposicionales 1.11. Circuitos lgicos Trabajo Prctico 1

(Captulo 2. CONJUNTOS 2. 2. Detenninacin de conjuntos 2. 3. Inclusin 2. 4. Conjunto de partes 2. 5. Complementacin 2. 6. Interseccin 2. 7. Unin 2. 8. Le~es distributivas 2. 9. Leyes de De Morgan 2.10. Diferencia 2.1 1. Diferencia simtrica 2.12. Producto cartesiano 2.13. Operaciones generalizadas 2.14. Uniones di~untas Trabajo Prctico II

{Captulo 3. RELACIONES 3. 2. Relaciones binarias 3. 3. Representacin de relaciones

CONTENIDO

2 1 7 8

11 12 13 14 l8

.22

25 25 30 34 36 38 42 45 46 48 50 53 S6 58 60

64 64 65

www.

Matem

atica

1.com

CONTENIDO

3. 4. Dominio, imagen, relacin inversa 3. 5. Composicin de relaciones 3. 6. Relaciones en un conjunto 3. 7. Propiedades de las relaciones 3. 8. Relaciones de equivalencia 3. 9. Relaciones de orden Trabajo Prctico III

~ Capitulo 4, Ff.'NCIONES 4. ~ .. Rdaciones funcionales 4. 3. Representacin de fodones 4. 4. Clasificacin de tl.meiones 4. S. Funciones especiales 4. 6. Composicin de funciones 4. 7. Funciones inversas 4. 8. Imgenes de subconjuntos del dominio 4. 9. Preimgenes de partes del codo minio 4.10. Restriccin y extensin de una funcin Trabajo Prctico IV

Captulo 5. LEYES DE COMPOSICION 5. 2. Leyes de composicin interna 5. 3. Propiedades y elementos distinguidos 5. 4. HomomorfIsmos 5. S. Compatibilidad de una relacin de equivalencia con una

interna 5. 6. ley de composicin externa Trabajo Prctico V

Capftulo 6. COORDli'lABIUDAD. INDUCCION COMPLETA. COMEINATORIA 6. ::. Conjuntos coordinables o equipotentes 6. 3. Conjuntos finitos y numerables 6. 4. Induccin completa 6. 5. El smbolo de sumatoria 6. 6. La funcin factora!

",6. 7. Nmeros combinatorios ~6. 8. Potencia de un binomio

'\ 6. 9. Funciones entra intervalos naturales ~6.10. Combinatoria simple y con repeticii1

Trabajo Prctico VI

66. 68 69 71 77 90 98

102 lO::; 105 110 114 ll? 121 128 131 137 138

142

142 144 151

154 158 ]60

l6:: i)::

164 167 170 176 f77 179 186

.... 197 204

CO~;JENlDO

. Captulo 7. SISTEMAS AXIOMA TIeos 7. 2. Sistemas axiomticos

. -- 7. 3. AIgebra de Boole 7. 4. Sistema axiomtico de Peano 7. 5. Estructura de monoide 7. 6. Estructura de semigrupo Trabajo Prctico VII

Captulo 8. ~STRU~RA DE GRUPO 8. 2. El concepto de grupo 8. 3. Propiedades de los grupos 8. 4. Subgrupos 8. 5. Operaciones con subgrupos 8. 6. Homomorfismos de grupos 8. 7. Ncleo e imagen de un lllorfIsmo de grupos 8. 8. Relacin de equivalencia compatible 8. 9. Subgrupos distinguidos 8.1 O. Subgrupos normales o invariantes 8.1 L Grupo cociente asociado a un subgrupo 8.12. Grupos cclicos 8.13. Traslaciones de un grupo 8.14. Grupos ftnitos Trabajo Prctico VIII

Captulo 9. ESTRUCTURAS DE ANILLO Y DE CUERPO. ENTEROS Y RAOONALES 9. 2. Estructura de anillo 9. 3. Propiedades de los anillos 9. 4. Anillo sin divisores de cero 9. S.-Dominio de integridad 9. 6. Subanillos e ideales '.Jl. "7 Factoril:lcln en un anillo 9. 8. ,~nillo ordenado 9. 9. Estructura de cuerpo 9 .. 10. Dominio de integridad de los enteros 9.1 L Isomorfismo de los enteros positivos con N 9.12. Propiedades del valor absoluto

)9.13. Algoritmo de la divisin entera 9.14. Algoritmo de Euclides 9.15. Nmeros primos ~.16. El cuerpo de los racionales

208 20g 210 212 219 220 223

:!~5 :.:5 218 231 235 ;~.., _;:n

240 247 248 15:; 254 257 258 259 261

264 264 266 267 272 272 174 :76 278 280 284 285 287 288 290 293

www.

Matem

atica

1.com

CONTENIDO

~ 9.17. Isomorfismo de una parte de Q en Z 9.18. Relacin de orden eri Q 9.19. Numerabilidad de Q

'Trabajo Prctico IX ~

Captulo 10. NUMEROS REALES )110. 2. El nmero real

10. 3. Operaciones en R 10. 4. Isomo~o de una parte de R en Q 10. 5. Cuerpo ordenado y completo de los reales 10. 6. Cortaduras en Q 10. 7. Completitud de R 10. 8. Potenciacin en R 10. 9. Logaritmacin en R + 10.10. Potencia del c0rUunto R Trabajo Prctico X

Captulo 11. EL CUERPO DE LOS ,f NUMEROS COMPLEJOS

1 l. 2. El nmero complejo 11.3. Isomorfismo de los complejos reales en los reales 11. 4. Forma bnmica de un complejo 11. 5. la conjugacin en C 11. 6. Mdulo de un complejo 11. 7. Raz cuadrada en e 11. 8. Forma polar o trigonomtrica 1 L 9. Operaciones en forma polar 11.l0. Radicacin en e 11.11. Forma exponencial en e 11.12. Logaritmacin en e IU3. Exponencial compleja general 11.14. Races primitivas de la unidad Trabajo Prctico XI

Captulo 12 . POLINOMIOS 12. 2. Anillo de polinomios formales de un anillo

12. 3. Anillo de polinomios de un cuerpo 12. 4. Divisibilidad en el dominio K [Xl 12. 5. Ideales de K [X] 11. 6. Factoruacin en K [X} t 2. 7. Especializacin de X y races de polinomios

298 301 301 303

308 308 315 321 321 321 326 329 333 335 338

341 341 347 347 349 351 354 356 358 362 366 367 369 370 373

378 378 383 384 388 389 396

CONTENIDO

12. 8. Races mltiples 12. 9. Polinomio derivado y races mltiples 12.10. Nmero de races de polinomios 12.11. Races de polinomios reales 12.12. Relaciones entre races y cOeficientes 12.13. Fnnula de Taylor y Mtodo de Horner Trabajo Prctico XII

BmLIOGRAFIA

RESPUESTAS A LOS TRABAJOS PRACTlCOS

INDICE

3~ 400 401 403 407 400 414

417

419

473

www.

Matem

atica

1.com

Captulo 1

NOCIONES DE LOG/CA

1.1. INTRODUCCION

Todo desarrollo matemtico exige razonar en forma vlida acerca de cosas trascendentes y particularmente abstracta~. Hay que comenzar por eliminar las ambigedades del lenguaje ordi!1ario, introduciendo smbolos y conectivos cuyo uso adecuado descarte las contingencias. aporte claridad y economa de pensamiento. En este captulo introducimos el concepto de proposicin, las operaciones proposiciona-les y sus leyes, reglas de inferencia, y la cuantif"lCacin de funciones proposicionales, cuyo uso estar presente en todo el texto.

J .2. PROPOSICIONES

Consideramos las siguientes oraciones:

l. Quin viene? 2. Detngase 3. El calor dilata los cuerpos 4. 4 es un nfunero impar S. Juan ama la msica 6. La msica es amada por Juan

Se aU de seis ordcine> diferenh::~, tina interrc~tiva,> ~~~1 orden V ~uatro_ declarativas. De las dos primeras no podemo$ decir que sean verdaderas ni falsa,,; una pregunta puede formularse o no, y una orden puede ser cumplida o no. En cambio, de las cuatro ltimas, que S

2 NOCIONES DE LOGlCA

Es decir, proposicin es toda oracin declarativa. Toda proposicin est asociada a un valor de verdad, el cual puede ser verdadero (V) o bien falso (F). Las oraciones (5) y (6) son diferentes desde el punto de vista gramatical; el objeto directo de la (5) es el sujeto de la (6), pero ambas tienen el mismo significado, y las consideramos como la misma proposicin. Podernos decir entonces proposicin es el significado de roda oracin declarativa.

1.3. NOTACIONES Y CONECTIVOS

las proposiciones genricas son denotadas con las letras p. q. r, etc. A partir de rrr;r .. ~if'ont's ,imp!e~ e$ posible generar otra~: SimpJp 5 (l rnmp'l!"5tllS. Es decir. se pude operar con proposiciones, y segn sean tales operaciones se utilizan ciertos slrJ1olos, llamados conectivos lgicos.

Conectivo

t,

V =>

>

J!

Operacin asociada

Negacin Conjuncin o producto lgico Disyuncin o suma lgica Implicacin Doble implicacin Diferencia. simtrica

Signif'lCadO

no P o no es cierto que p p y g po q (en sentido incluyente) p implica q o si P. entonces q p si y slo si q p o q (en sentido excluyente)

lA. OPERACIONES PROPOSICIONALES

Definiremos las operaciones entre proposiciones en el sentido siguiente: dadas una o dos proposiciones, cuyos valores de verdad se conocelJ, se trata de caracterizar ia proposicin resultante a travs de su valor de verdad: Se supone que en la eleccin de estos valores se tiene en cuenta el buen sentido.

1.4.1. Negacin '<

Definicin Negacin de la propoSlclon p es la proposicin -p (n9 p), cuya tabla de valores de verdad es

tTITI-P V F F V Se trata de una operacin unitaria, pues .3 partir de una proposicin se obtiene

. (ra. que es su negacin.

Ejemplo J.J. La negacin de

es

o bien:

OPERACIONES PROPOSICIONALES

p: todo hombre es honesto -p: no todo hombre es honesto -p: no es cierto que todo hombre es honesto ..... p: hay hombres que no son honestos ..... p: existen hombres deshonestos

la cual es V, ya que la primera es F.

1.4.2. Conjuncin Definicin

Conjuncin de las proposiciones p y q es la proposicin p " q lp Y q). cuya tabla de valores de verdad es

p q P ,\ q , V V V V F F F V F F F F

La tabla que define la operacin establece que la conjuncin slo es verdadera si lo son las dos proposiciones componentes. En todo otro caso es falsa.

Ejemplo J1. Si declaramos

i ) 3 es un nmero impar y 2 es un nmero primo se trata de la conjuncin de las proposiciones

p : 3 es un nmero impar " : 2 es un nmero primo

y por ser ambas verdaderas, ,la proposicin compuesta es V. ii) hoyes lunes y maana es jueves

esta conjuncin e~ F, ya que llo coexisten las verdades de p y q.

1.4.3. Disyuncin

Definicin Disyuncin de las proposiciones p y q es la proposicin p v q (p o q) cuya tabla de valores de verdad es

www.

Matem

atica

1.com

NOCIONES DI: LOGICA

p q p V q V V V V F V

J

F V V F F F

La conjunclon o es utilizada en sentido incluyente, ya que la verdad de la disyuncin se da en el caso de que al menos una de las proposiciones sea V. En el lenguaje ordinario l:l pal~bra es utiiilada en sentido excIuyent ... o induyente.

La ambigedad ~e eilmina t;cm la ele.:.:in del slrnholo adecudd\J. En matem.tica se utliza la disyuncin definida por la tabia precedente la clI:Jl

agota toda posibilidad.

La disyuncin slo es F en el .. "aso en que las dos proposiciones componentes sean falsas.

Ejemplo 1.3. i ) hoyes lunes o martes

represema la disyuncin de las proposiciones p: hoyes lunes y q: hoyes martes. El sentido de la '~onjuncir' o es exIcuyente, ya que p y q no pueden ser sim ultnea-mente verdaderas. No obstante, la proposicin compuesta puede analizarse a la luz de la tabla propuesta, a travs de los tres ltimos renglones, y ser falsa slo si las dos lo son.

i ) regalo los libros viejos o que no me sirven es la disyuncin de las proposiciones

p : regalo los libros viejos q : regalo los libros que no me sirven

El sentido del (} es incluyente, pues si en efecto regalo un iibro que ~s viejo v .'~ Jd,;m3~ no :n,;> sine. enton,"es P 'el Q es V

i 3 es ,m nmero 1) 4 es un nmero prirno

;:\ una pcopoposi(.'in \i, pues la primera es V.

1.4A. Implicacin o Condicional Definicin

Implicacin de las pr~posicions p y q es la proposicin p ==> q (p implica q, si p entonces q) cuya tabla de valores de verdad es

OP1: RAClONI.S FROPOSICIONALES

p q p ==> q V V V V F F F V V

1 F F V

Las proposiciones p y q se llaman antecedente>, consecuente de la imp!ica..:n:> i:cmJki'maL Ll impli..::.iI.:in usual en matemtica es forma! en e! sentido de 4U~ no es necesario que el consecuente se derive lgicamente de! antecedente: cuando esto ocurre. la impiicacin se llama material y queda incluida en la primera,

Las tablas de valores de verdad se definen arbitrariamente, pero respetando el sentido comn. Enunciamos la siguiente proposicin:

"SI apruebo el examen, ENTONCES te presto el apunte" (1) Se trat:r de la implicacin de las proposiciones

p : apruebo el examen q : te presto el apunte

Interesa inducir la verdad o falsedad de la implicacin (1), en tnninos de la Yo F de las proposiciones p y q. El enunciado (1) puede pensarse- como un compromiso, condicionado por p. y podemos asociar ~u verdad al cumplimiento del compromis/), Es obvio que si p eS F, es decir, si no apruebo el examen, quedo liberado del compromiso, y preste o no preste el, apunte la proposicin (1) es V. Es decir, si el antecedente es F. la implicacin es V.

Si p es V, en cuyo caso apruebo el examen, y no presto el apunte, el compromiso no se cumple, y la proposicin (1) es entonces F. Si p Y q son V, entonces la implicacin es V porque el compromiso se cumple.

De este modo, la implicacin slo es falsa cuando el antecedente' es V y el consecuente es F

Eemplo ....J. 1) SI hoyes lunes" entonces maana e:>. marte~

es la implicacin de las proposiciones

p : hoyes lunes q : maana es martes

Como no puede darse antecedente V y consecuente F, la implicacin es V. m 1 = -1 ==> 12 = ~lf

es V por ser el antecedente F,

www.

Matem

atica

1.com

6 NOCIONES DE LOGICA

1.4.5. Doble implicacin o bicondicional

Definicin Doble implicacin de las proposiciones p y q es la proposicin p ~ q (p si y slo si q), cuya tabla de valores de verdad es

p q p ~ q V V V V F f F V F F F V

La doble implicacin o bicondicionai slo es verdadera si ambas proposiciones tlenen el mismo valor de verdad.

La doble implicacin puede definIse como la conjuncin de una implicacin y su ~e,~prllca. De este modo, la tabla de valores de verdad de p - q ,puede obtenerse

"diante la tabla de (p =:. q) " tq = p), como sigue

p q p => q q =;> p (p =:. q) V V V Y V F F V F V V F F F V .y

.ejemplo 1-5. j) T es equiltero si y slo si Tes equingJlo

IJS :a dob:e jmplil.:acin de las proposicIones p: T es equiltero q : T es equingulo

" (q =1> p)

V F F V

Toda vez que p sea V, tambin lo es q. y anlogamente, si p es F, q es F. De mudo que la doble implicacin es V.

ji) a = b si Y slo si a2 = b 2 las rroposiciones son

p: a = b q : a2 = b2

la 1. q es V, si q es V, entonces p puede ser V o f; mas para que p sea V se necesita que q lo sea. Se dice entonces que q es condicin ~eJ;l..dlL.. para p.

---Res-umiendo, si p => q es V. entonces p es condicin suficiente para q Y q es condicin necesaria para p.

Estas condiciones suelen expresarse' as:

q si p (condicin suficiente) p slo si q (condicin ne.cesaria)

www.

Matem

atica

1.com

NOClm;S DE LOGleA

Ejemplo 1-6. La siguiente implicacin es Y:

"SI T es equiltero, ENTONCES T es issceles"

En este caso p : T es equiltero q : 1 es issceles

y p es cmdicin suficiente para q, es decir, que un tringulo sea equiltero es suficiente para asegurar que sea issceles. Por otra parte. T es equiltero slo si es issceles: es decIL que un tringulo sea issceles es necesario para que sea equiltero.

Sea ahora la doble implicacin p ~> q, es decir (p ;;. q) , (q -;:;;. p) Si p ~ q es V. entonces p ~ q es V y q => p es V. Se tiene. atendiendo a la primera, que p es condicin suficiente para q; y, teniendo en cuenta la segunda implicacin. ocurre que p es condicin necesaria para q.

Es decir, si p ~ q es V, entonces el antecedente p es condicin necesaria y suficiente para el consecuente q.

Anlogamente. en el caso de doble implicacin verdadera, el consecuente q es tambin condicin necesaria y suficiente para el ante..:edente p.

Ejemplo J.i. La proposicin

"1 es equiltero SI Y SOLO SI 1 es equingulo"

es la doble implicacin de las proposiciones p : T es equiltero q . T es equinguio

Aqulla es Y, y cualquiera de las dos proposiciones es condicin necesaria y suficiente para la otra.

1.6. LEYES LOGICAS

Consideremos la proposicin

Hp "'l> q) cuy tabla de valores de verdad es:

p q p~q (p -=> q) A P V V V V

V F I F E F V V F F F V F

-

--

~ ,~ , "1 " { , }

[(p "'" q) ,\ pI"'" q V V V V

LEYES LOGICAS 9

La proposicin compuesta (1) es V, independientemente de los valores de verdad de las proposiciones componentes. Se dice entonces que tal proposicin es una

tautologa o ley lgica. La proposicin p => P es V cualquiera que sea el valor de verdad de p. Es otro

ejemplo de una ley lgica. En cambio P A ""'p es F, cualquiera que sea p. Se dice que es una contra-

diccin. En el ciculo proposicional se utilizan las siguientes leyes o tautologas cuya demostracin se reduce a \a confeccin de la correspondiente tabla de valores de

vcrdad:

l.6.L Involucin - ( -p)

IMI'L1C'ACIONl:S ASOCIADAS

10 NOCIONES DE LOGIeA

1.6.6. Leyes de De Morgan Ejemplo J-10. La proposicin

aj La negacin de una disyuncn es equivalente a la conjuncin de las negaciones -- (p v q) o$? -p /1. -q

b) La negacin de una conjuncin es equivalente a la disyuncin de las negaciones

- (p A q) o$? -p V -q Ejemplo 1-8.

Tabla de valores de verdad de la distributividad de la coniuncin respertn d!.' ~ J' o _ "

U;) ...... q, que llamamos directo: en conexlon con l, se presentan otros tres. obtenidos por pennutacones o negaciones del antecedente Y consecuente:

q => p -p => -q -q => -p

recproco contrario contrarrecproco

Las cuatro illlplicacones propuestas se llaman conjugadas, y cualquiera de ellas puede tomarse como directa. El siguiente esquema nos proporciona la relacin que las vincul:l:

p => q recprocos 4 =p

Ca!}! .0"0

r.; .~ ... .;jo- r.; e J'j ... ec"\ e :::. =

~ 5" \."(~ I'ec; ...,

~. 'J:;,., c' co~ oCos '" -p =>-q recprocos -t{ => -p

Es fcil verificar que las implicaciones contrarrecpro(.'Js son equivalentes, es decir. los siguientes b condicionales son tautologas:

(p => q) ~ (-q => -p) (q => p) ~ (-p => -q)

Si la implicacin directa es V, tambin 19 es la contrarrecproca, Y no podemos afirmar la verdad de la recproca de la contraria. Pero si son verdaderos un

www.

Matem

atica

1.com

12 NOCIONES DE LOGICA

condicional y su recproco o contrario, entonces son verdaderos los cuatro, y las proposiciones antecedente Y consecuente son equivalentes.

Se presenta continuamente la necesidad de demostrar la verdad de p =? q, y de acuerdo con lo expuesto se presentan dos mtodos:

i) directo. Si p es F, nada hay que probar, pues en este caso p => q es V. Si p es V Jay que establecer que el valor de verdad de q es V.

ii) indirecto. Si q es V queda establecida la verdad de p =? q. Pero si q es F hay que examinar p y llegar a establecer que su valor de verdad es F.

t .8. NEGACION DE UNA lMPLICACION

Las proposlcones P """ q y .~( P ,\-~q) son equivalentes. cumo lo muesua la siguiente tabla

(p => q) ~ (p \ --q) V V V V V V F F V F F V F V V V F V V V V F F F F V F V V F F V

En consecuencia, la negacin de la primera equivale a la negacin de la segunda. es decir

-(p => q) - -(p f\ -q)J

y por 1.6.1, se tiene

-(p => q) (p" -q) Es decir. la negacin de una implicacin no es una implicacin. sino la

conjundn del antecedente con la negacin del consecu?nte.

EJemplo ! 11,

Sean las implkaeiones i ) Si hoyes 'lunes. entonces maana es mircoles. ii) 1 = -1 = 12 = (- 1)2

Sus negaciones son, respectivamente,

"Hoyes lunes y maana no es mircoles"

1 = - 1 !I 12 * (- 1)2 "

RAZONAMIENTO DEDUCIIVO 13

1.9; RAZONAMIENTO DEDUCTIVO VALIDO

En matemtica interesa el tipo de razonamiento llamado deductivo. Llamamos razonamiento a un par ordenado ({ Pi} ; q), siendo { Pi ) un conjunto finito de proposiciones, llamadas premisas, y q una proposicin, llamada conclusin, respecto de la cual se I?firma que deriva de las premisas.

Un razonamiento es deductivo si y slo si las premisas son evidencias de la verdad de la conclusin. es decir, si PI, pz.. . Pn son verdaderas, entonces q verdadera. Un razonamiento deductivo es vlido si no es posible que las premisas sean verdadera!> y la conclusin falsa. De un f;.tlOnamiento no se dice qUe es V o r. smu qii es vlido ~j no.

Llamamos regla de inferencia. a todo esquema vlido de razonamiento. indepen-dientemente de la V o F de las proposiciunes componentes. De este modo. toda regla de inferencia es tautolgica.

Un razonamiento deductivo es vlido cuando el condicional cuyo antecedente es la conjuncin ue las premisas. y el consecuente' es la conclusin, es tautolgico.

Son ejemplos de reglas de inferen..:ia: a) Ley del modus pVlIens:

SI P y P => q, ENTONCES q La notacin clsica es

b) Ley del modus tolrms:

p p =q q

p =q -q

-P

Este esquema es la !iotacin clsica del condicional

[1 (J ~ 'n "1 Ley del silogIsmo fllPQtrico:

-q! =>-D

P ;;;;;.q q =?f

P =r

Es decir, la proposicin [ r)] = (p => r) es una' tautologa. En cambio, el condicional. [ ( P => q ) A q ] => p no es una forma vlida de

www.

Matem

atica

1.com

14 NOClONES DE l.OGIeA

razonamiento, ya que la correspondiente tabla de valores de verdad nos muestra que no es tautolgico.

EJemplo 112. a) Justificar la validez del razonamiento

p =*q -r ~-q

-( -p ,\ -t) t ~s -r

s

En lugar de confeccionar la tabla del condicional entre la conjuncin de las premisas y la conclusin. haremos uso de las leyes dei clculo proposicional, a fm de simplificar la situacin. La segunda premisa es equivalente a la contrarrecproca q => r; por la ley del silogismo hipottico. de la primera y de sta, resulta p => r. La ltima premisa es V, Y en consecuencia r es F, Y COmo p =l> r es V resulta necesara:.-nente que p es F. La tercera premisa equvale a p v t. de acuerdo con una ley de De Morgan, y por ser p falsa resulta la verdad de t. Ahora bien. siendo t y t =l> S verdaderos. resulta la verdad de s. por 1.9 a).

bj Justificar la validez del razonamiento cuyas premisas son:

y la conclusin: Hoy Hueve.

Hoy llueve o hace frio. Hoy llueve o no hace fro,

En lenguaje simblico se tiene p v q P v ..... q p

q, o bien -q es F; cualquiera que sea el caso, por ser las disyunciones verdaderas. resulta que p es V. De otro modo, la conjuncin de ambas disyunciones, por la .iiStrbutividad, es equivalente a p v (q 1, "-q). La verdad de aqullas asegura la -.rerdad de sta, y como q " -q es F, resulta la verdad de p.

1.10. FUNCIONES PROPOSIOONALES. SU CUANTIFICAOON

El smbolo P (x) es la ~epresentacin de un predicado o propedad relativos al ,)bjeto indeterminado x, perteneciente a cierto uriiverso o conjunto. Si nos referimos a

FUNCIONES PROPOSICIONALES 15

los nmeros enteros y estamos interesados en la propiedad de ser impar, entonces la traduccin de P. (x) consiste en: x es impar, y se escnbe

P (x) : x es impar

Es claro que el enunciado: "x es impar" no es una proposicin, ya que a menos que se especifique a x no podemos decir nada acerca de sU verdad o falsedad. curre, sin embargo, que para cada asignacin dada al sujeto x dicho enunciado es una proposicin. A expresiones de este tipo se las llama funciones esquemas proposicionales.

Definicin Funcin proposicional en una variable o indeterminada x es toda oracin en la que figura x como sujeto u objeto directo, la cual se convierte en proposicin para cada especificacin de x.

En nuestro ejemplo resultan proposicioneS como

P (- 4) . - 4 es impar P( 5): 5 es impar

(F) (V), etc.

Se presentan tambin funciones propOSicionales con dos variables o indeterminada . Sea, por ejemplo .

P(X ,y) :x es divisor dey Lo mismo que en el caso anterior, si x e y son enteros, P (x .}') no es proposicin,

ya que no podemos afirmar la verdad o falsedad de] enunciado. Mas para cada particularizacin de valores se tiene una proposicin

P (- 2,6) : - 2 es divisor de 6 (V) P( 12.6): 12 es divisor de 6 (F)

A partir de funciones proposicionales es posible obtener proposiciones generales mediante un proces~ narn~o de cuantificacin. Asociados a la indeterminada x, introducimos los smbolos 'r;f x y 3 x. llamados cuantificadores universal y existencial en x. respectivamente. Las expresiones

Par; todo x, se verifica P (x) Existe x, tal que se verifica P (x)

se denotan mediante 'r;f x; P (x) (1) 3xj P(x) (2)

y corresponden a una funcin proposicional P (x) cuantificada llniversalmente en el primer caso, y existencialmente en el segundo. lID:! fundn proposicional cuantificada

www.

Matem

atica

1.com

16 : NOCIONES DE tOCleA

adquiere el carcter de proposicin, En efecto, retomando el primer ejemplo, si decimos

"Todos los nmeros enteros son impares", (1') es claro que hemos enunciado una proposicin general y relativa a todos los nmeros enteros, cuyo valor de verdad es F. Una trad uccin ms detallada de esta proposicin consiste en

Es decir

"Cualquiera que sea x, x es impar",

'1 x : x es impar

Si .:cuamificamos e:xisiencalmente la misma fundn proposicional. se tene

o sea

O bien

O ms brevemente

3 x x es impar "Existe x, tal que x es impar",

"Existen enteros que son impares",

"Hay enteros impares",

(2')

El valor de verdad es V, y en consecuencia se trata de una proposicin. El cuantificador existencial se refiere a, por lo menos, un x,

Es obvio que una funcin proposicional cuantificada universalmente es V si y slo si son V todas las proposiciones particulares asociadas a aqulla, P~ra asegurar la verdad de una funcin proposicional, cuantificada existencialmente, es suficiente que sea verdadera alguna de las proposiciones asociadas a la funcin proposicional.

Un problema de inters es la negacin de funciones proposicionales cuantificadas, La negacin (1') es

es decir

y en smbolos

"No todos los enteros son impares"

"Existen enteros que no son impares"

3 x / -p (x) Entonces, para negar una funcin proposicional cuantit1cada universalmente se

,;a,nbu el cuantifi..:ador en existencial. y ;re niega la fund~ proposicionat La !1~~a~nde i:;", .. ~~

"No t!xis~en enteros impares", Es decir "Cualquiera que sea el entero, no es impar"

o lo que es lo mismo

"Todo entero es par".

En smbolos "J' X : -p (x)

I f r t ,

l :1 t ;

':1 H~

1I ! .

"

'

L ..

CUANTIl'lCACION 17

Vale entonces la siguiente regla: para negar una funcin proposicional cuantificadc-existencialmente se cambia el cuantificar en universal, Y se niega la fllncion

proposicional. Se tienen las siguientes equivalencias

-[Vx:p(x)19 3xi~P(x) -[3x I p(x}l 9 Vx: -P(x)

Ejemplo 1-13. Sea la proposkillfl .

Todo el que la conoel'!. la admu:::t.

NOS interesa escribirla en lenguaje smblico, negar!J., y retraducir ia uegadn al lenguaje ordinario,

La proposicin dada puede enunciarse: Cualquiera que sea la persona. si la conoce. entonces la ldmira.

Aparece clara la cuantificacin de una implicacin de las funciones proposicionales

1> (x), x la conoce Q (x): x la admira

Se tiene 'v'x:P(x) :;>Q(x)

Teniendo en cuenta la forma de negar una funcin proposicional cuantificada universalmente Y una implicacin resulta

3x / P (x) ,\ -Q l.\:}

y pasando allenguaje ordinario: Hay personas que la conocen Y no la admiran.

Ejemplo H.J Consideretnos ia nH~i1'ia ~ue~Iin;!n ~l si}!~.tientc ,:a50:

. Todo entero admite un inverso aditivo.

Es decir "Cualquiera que sea el entero, existe otro que sumado a l da cero"

Intervienen dos variables Y la ri.tncin proposicional P(x,y):x+y=O

--

www.

Matem

atica

1.com

18 NOCIONES DE LOGICA

La expresin simblica es entonces

'l:/x3y/x+y=O

Su negacin es

3 x / -[3y / x + y = O] Es decir

3xl'l:/y:x+y:~O

La traduccin al lenguaje comn es i Ul~Lilla C I,.ciu ,.

Ejemplo 1-15. Sea la proposicin

Hay alumnos que estudian y trabajan. Su enunciado sugiere un cuantificador existencial y dos funciones proposicionales

p (x): x estudia Q (xi: x trabaja

En forma simblica se tiene

3 x I P (x) A Q (x) Su negacin es

'1:/ x: -[P(x) " Q (x)] y por ley de De Morgan

'l:/x: -P{x) v -Q(x) Traduciendo al leng:mje ordinario

"Cualquiera que sea el alumno, no estudia o no trabaja".

1.11 CIRCUITOS LOGICOS

La verdad de una proposicin puede asociarse al pasaje de corriente en un circuito electrico con un interruptor.

Para representar a p, si es V, se tiene

O r-- O

{ .. ir-

'.\.>.1.

1

? ~~

~ ~

CIRCUITOS LOGICaS 19

y para p, si es F

O / --Q

Es decir, el interruptor se cierra si p es V y se abre si pes F. Las operaciones proposicionales pueden representarse mediante circuitos con tantos

interruptores como proposiciones componentes, combinados en serie o paralelamente. i ) Conjuncin

o / / O p q

Este circuito admite el pasaje de comente, es decir. la verdad de p' q, slo si las dos son V.

ii ) Disyuncin, Est representada por un tircuito en paralelo

o I . ~ ~~ q

La falsedad de p v q. es decir, el hecho de que no pase corriente, slo se verifica en el caso de la falsedad simultnea de p y q.

i) ~mplicacin. Como (p => q) ~ -(p 1\ -q)

de acuerdo ~on 1.8, aplicando una ley de De Morgan y la doble negacin, se tiene

(p => q) ~ (-p v q) En consecuencia. el ~ircuito asociado es

-p

I I O ___ 1

q

iv) Diferencia simtrica. Utilizando sucesivament~ 1.4.6., 1.4.5 .. una ley de De Morgan, la negacin de

www.

Matem

atica

1.com

(Ii--:';;:.t!

~

TRABAJO PRACTICO I

117. En el libro Hijos en libertad. de A. S. Nell, estn escritas las siguientes proposiciones

p : Mis maestros hacen que todas las lecciones sean aburridas. q : No aceptan las respuestas que no figuran en los libros. r: Imponen un cmulo de normas estpidas

Construir las pro~:lOsiciones

P .' q """q v r (p ., q) => r

J18. Escribir en forma simblica la siguiente proposicin compuesta que figura en el mismo texto:

"La chatura y el tedio de ciertas disciplinas escolares se trasmiten a los maestros, y las escuelas se llenan de hombres y mujeres de mentalidad estrecha, vanidosos. cuyo horizonte est limitado por el pizarrn y el libro de texto".

J -} 9. Confeccionar las tablas de valores de verdad de las proposiciones i ) (p t', q) => r i) -(p v q) -p ,\ -q

1 -10. Negar las proposiciones construidas en el ejercicio 1-17. }11. Proponer las siguientes proposiciones en forma simblica, negarlas, y retraducir

las al lenguaje comn: i ) No es justa, pero mantiene el orden. ii ) Los alumnos conocen a los simuladores y los desprecian. iii) Si los 'lumnos conocen a los simuladores, entonces los desprecian.

/12. Detenninar si l~s siguientes proposiciones son leyes lgicas: i)pllq*q ii) [(p => q) /\ (q => r)J => (p => r) ili) p => P A q

. iv) P => P v q

!

,

iJ1

TRABAJO PRACTICO 1

123. Simplificar las siguientes proposiciones:

i ) -(~p v -q) ) -(p v q) v (-p 1\ q)

1-24. Sabiendo que p V q es V y que .~q es V, determinar el valorde verdad de [(p v q) A -q)*q

23

]25. Determinar, en cada caso, si la informacin que se da es suficiente para conocer el valor de verdad de las siguientes proposiciones compuestas. En caso afirmativo. justificarlo.

(p => q\ => r rl'~ V ii)(p q) .... (-p -q) q es V Ui} (p ,\ q) => (p v r) ; p es V y res F iv) p \ (q => r) ; p => r es V

/-26. Los valores de verdad de las proposiciones p, q, r y s son, respectivamente, V, F, F, V. Obtener los valores de verdad de

il [( P \f q) \f r] ~. s ii, r => s " p mI p v r r ,\ -s

}27. Negar las proposiciones i ) 3 x! p (x) v -O Ix) ii) V x : P (x) => Q (x) iii) V x 3 y / x . y = O

1-28. Verificar que para probar la equivalencia de las proposiciones p. q. r y s es suficiente demostrar las siguientes implicaciones:

P =!- q q=>r r=>s y s=>p 1 -19. Dadas las proposiciones

i ) El cuadrado de todo nmero real es mayor que 2. ii) Existen enteros cuyo cubo aumentado en 1 es igual al cubo del siguiente, iii) Todo el que estudia triunfa,

expresarlas simblicamente, negar las expresiones obtenidas y retraducirlas al lenguaje ordinario.

130. Construir un circuito correspondiente a la proposicin

(p 11 -q) V (-p /1 q) V (-P /1 -q)

www.

Matem

atica

1.com

L

24 NOCIONES DE LOGleA

]-31. Se tiel1e el siguien te circuito:

~ / I I I r

--l -P '-q I ./_-I "'-~./ 11 !: J !! ! L~ __ d_.-J L--- q , / I

~ __ / I

i ) determinar la proposicin correspondiente ', ) simplificar sta, y construir el circuito asociado.

1-32. Exp:esar simblicamente el siguiente teorema: "si un nmero es unpar, entonces su cJadrado es impar". Enunciar el contrarrecproco, el contrario y el recproco, Demostrar el primero.

J-33. Siendo

Demostrar p = q

.J4. Justificar el !'n2onamiento

p : a. b es impar q : a y b son impares

p v -q -q > T

p V -r p

1.35. Lo TMno ~n ej sigUIente caso:

{P ro ".

q qi "'"

r => s

s

1-36. Investigar la validez del razonamiento siguiente: Si el inters no es egosta, entonces es, la fuerza vital de las personas y es espontneo. El inters no es la fuerza vital de las personas y es espontneo

El inters es egosta

1" i

f

" E- ..o.

Captulo 2

CONJUNTOS

2.1. INTRODUCCION

El propsito de esta seccin es el estudio de'la teora intuitiva ue conjuntos. En este sentido. los trmmos "conjunto", "pertenencia" y "elemento" son considerados como primitivo$, Sobre esta base se definen la inclusin y la igualdad, y se estudian sus propiedades. El mismo tratamiento se hace corresponder a las operaciones entre conjuntos. El captulo se completa con el desarrol1o de ejemplos en lo. que se pretende mostrar un mtodo adecuado de trabajo.

1.2. DETERMINAOON DE CONJtJNTOS

2.2.1. Notaciones

Para denotar conjuntos utilizaremos generalmente letras maysculas, y para especificar elementos se usarn letras minsculas, a menos que dichos elementos sean, a su vez, conjuntos. Para indicar la pertenencia de un elemento a un conjunto ser utilizado el smbolo .

la proposicin "a e 1\" se lee: "o pertenece a A", o bien "el elemento a pertenece al conjunto A",

Su negaci.l e,," f A'", que se iee: C'a no pertenece a A" Si el ~lliunlu ~ ;J~d furrIado por los ~lementos a~ b ~,,' f ~ cscJibms

A -fa be' - \ .. J

en este caso se nombran todos los elementos' del conjunto, y se dice que est determinado por extensin.

Las notaciones usuales para caracterizar conjuntos numricos son las siguientes: N conjunto de los nmeros naturales Z conjunto de los nmeros enteros

www.

Matem

atica

1.com

26 CONJUNTOS

Q conjunto de los nmeros racionales R cortiunto de los nmeros reales C conjunto de los nmeros complejos

La representacin por extensin del conjunto cuyos elementos son - 1, y 1, es

A={-I,O,I} Es fcil ver que se trata del conjunto de los nmeros enteros cuyo valor absoluto es

menor que 2; en este enunciado hacemos referencia a elementos del conjunto Z. de los nmLa notacin cOI:.respondiente es

A = x e Z i Ixl < 2 j Y se dice que el conjunto ha sido determinado por comprensin,

El conjunto universal depende de la disciplina en estudio, se fija de antemano, y est formado por todos los elementos que intervienen en el tema de inters. En general se denotar con U. Definicin l

Un conjunto se determina por extensin si y slo si se enumeran todos los elementos que lo constituyen. Un conjunto se define por comprensin si y slo si se da la propiedad que caracteriza a sus elementos.

El conjunto cuyos elementos verifican la propiedad P se indica

A = ( x II P (x) ~ " ;

u ms brevemente. si U est sobrentendido

A = { xl P(x)} y se lee: "A es el conjunto formado por los elementos x. tales que P (x)". P (x) es una funcin proposicional, y un objeto del universal pertenece al conjunto si y slo si verifica la propiedad. es decir

aA ~P~a) es V

En consecuencia

a tl A 4l' P la) es F

2.2.2. Conjuntos especiales Extendemos la nocin intuitiva de conjunto :J Il's cas~ dt: -:art:nca de elementos y

de unicidad de elementos. mediante la intwducci!l n" los conjuntos vaco y unitario.

;'1'1'' .

1 :;

!

I

1

,1 I

1 I

i ii :1

~ ~

DETERMINACION DE CONJUNTOS 27

"Un conjunto vaco es liquel que carece de elementos. Un conjunto unitario est f~rmado por un nico elemento.

Una propiedad o funcin proposicional, que se convierte en proposicin falsa para todos los elementos del universal. caracteriza por comprensin un conjunto vaco. Designaremos con ti> al\:onjunto vaco, y puede definirse simblicamente as

tI>=[x!x*x~ " )

En este caso la propiedad relativa a x es P (x) : x =1= x. la cual resulta falsa cualquiera que sea x.

Si A es el conjunto cuyo nico elemento esa. escribiremos

A=i~a ,.x:x=a

Ejemplo 21. Determinar simblicamente y por extensin ls siguientes conjuntos definidos por

comprensin: i ) A .es el conjunto de los nmeros enteros cuyo cuadrado es igual a t.

En este caso la propiedad que caracteriza a los elementos de A es la conjuncin de p (~) : x Z y Q (x) : X2 = 1

Entonces ~ 1 1

A = t x i x Z A. x = 1 J y como universal puede sobrentenderse el conjunto de Jos nmeros reales o racionales. Si proponemos a Z como universal, puede escribirse

A = { x Z I X2 = 1 } Obviamente, la determinacin por extensin es

'A={-l,l} ji) B es el conjunto de los nmeros naturales mayores que 2, y que no superan a

6. Considerando a N como universal. la propiedad caracterstica de los elementos de B

es la conjuncin de

que podemos expresar

y se tiene

P (x) : x> 2 y Q (x) : x..;; 6 R(x): 2

...........

28 CONJUNTOS

Por extensin nos qucda

B={3,4,5,6} iii) e es el conjunto de los nmeros reales cuyo cuadrado es igual a - l.

Se tiene:

e :::: ( X R I X2 := - 1 ~ '- "

('JITIO el (uaJradd de nmero real es negativo P (x) : X2 es F para lodo real. y Tcst:!ta e = 3keZ/a='2k Entonces p={xeZ/x=2k 11 kEZ) Es claro que P consiste en el conjunto de los mltiplos de 2. A ve~es, acudiendo a un abuso de notacin, suele proponerse una aparente

determimcin por extensin de un conjunto infinito, con la adjuncin de puntos suspensivos. As

P - r -4 _'i O 'i 4 6 ~ -~~.~ ... , ,-, ,-, , , ...... J ii ):\ es el conjunto de los mimeros naturales que son mltiplos de 3.

,\ yeN k , . .:"1 f\, ,-. "

En N n w.:!uim;)$ al ceft), 'f se nene _ r 4> .. q A-,j,tl",

~ ." ~ )

Si O se considera natural, escribiremos No Y en este caso

A = { x No Ix = 3 k " k No ~ , . )

Es decir A={O,3,6,9, ...... }

r

j' I

~

f : l' A,

IlFTER1>lNAC'lON D! COtUl.lNTOS 29

i) B es el conjunto de los nmeros naturales cuyo cuadrado es par. B = { X Ni X2 es par}

o bien

B= {X,N/x 2 =2k A k~N} Cmo se determina la pertenencia de un elemento a B? De acuerdo con la

definicin de B, dado un nmero natural. se analiza su cuadrado; si dicho cuadrado es par, el nmero pertenece a B; si su cuadrado es impar. no pertenece a B. Es decir

il i5 "";1- e~ ir

iV) e es el conjunto de los puntos del plano cuyas distancias a un punto O son iguales a l.

Entendemos que el conjunto universal es el d~ los puntos del plano a. Si bien O es un elemento, como es usual en geometra, lo denotamos con mayscula. Indic"mos la distancia emre \ y O mediante d (A . O). Entonces

e = { X e a j d (X , O ) =- 1 }

es la definicin simblica de la circunferencia de centro O y radio 1. v) D es el conjunto de los puntos del plano que equidistan de dos puntos fijos A

yB.

D = ( X a f d (X , A) = d (X , B) } ;"" )

D consiste en la mediatriz del segmento AB.

Ejemplo 2-3. El conjunto S est fQrmado por los posibles resultados que se obtienen al lanzar dos

monedas, Los resultados para la primera moneda son e (cara) y s (sello) y por cad:! uno ;le ellos. "e tienen las mismas posibilidades para la segunda" es decir

,_c

c~s "...~ e

~$~..,X'

30 CONJUNTOS

2.3. INCLUSION

2.3.1. Concepto

Sean A Y B dos conjuntos, Si ocurre que todo elemento de A pertenece a B, diremos que A est incluido en B, o que A es parte de B, o que A es un subconjunto de B, y eScribimos A C B.

Definicin ;< ACB ~'I1x:xA "">xB

Esta definicin tiene el siguiente significado: si sabemos que A e B. entonces la proposicin V x : X A ""> x B es V; recprocamente. si esta !Jro!Josicin es V. entonces se verifica que A e R

En repetidas ocasiones se necesitar demostrar que un conjunto es parte de otro; ~ntonces. de acuerdo con la definicin, ser suficiente demostrar que cualquier elemento del primero pertenece al segundo.

Teniendo en cuenta la equivalencia entre una implicacin y la contrarrecproca,la efinicin anterior puede expresarse as

ACB ~'I1x:xtB =xtlA Adems. considerando la equivalencia entre p => q y - (p ,\ -q), podemos

traducir la misma definicin de la siguiente manera

A C B ~ 3 x / x A " x f B es F Es decir, en la inclusin no puede darse que haya un elemento de A que no

i'ertenezca a B. Sobrentendiendo el cuantificador universal. para descargar la notacin, escribi-

remos

ACB ~xA =xEB

2.3.2. Diagramas de Venn

Ex!ste una representacin visual de los conjuntos dada por diagramas llamados de Venn.' En este sentido, el conjur.to universal s,uele representarse por un rectngulo, y los conJuntos por recintos cerrados. Es claro que todo elemento de A pertenece a U, es decir, A C U. Sean A, By C subconjuntos de U, como indica el diagrama .~

U

C

~:1 , ... .. 1 t

;.

~:. j ~ '>"

i

I

, .

l,i

INCLUSION DE CONJUf\TOS

En este caso se verifica A C B.

Ejemplo 2-4. Sean U = N y los conjuntos

A ={ x/xI6} B ={ xx!S} C ={X/X~2}

31

~c pide !a :-eprese!1tacin de t3!e~ conjuntes mediant~ d.iagr:L"!1!l~ de "en%":. Definimos la relacin de divisor en N mediante

a I b si Y slo si 3 n N b = a, n Teniendo en cuenta esta defInicin, y la relacin de menor o igual, la representacin

por extensin de tales conjuntos es r ~ r ~

A=t l ,2,3,6) B=~1,2,4.8) ( ' C=1. 1,2J

y en trminos de diagramas de Venn

N

Ejemplo 2-5. Consideremos el conjunto U de todos los tringulos; si 1 denota el conjunto de los

tringulos issceles, E de los equilteros y R de los tringulos rectngulos, se tiene

u

R

www.

Matem

atica

1.com

32 CONJUNTOS

Ya que todo tringulo equiltero tiene los tres lados igua1cg, en consecuencia tiene dos iguales, es decir, es issceles. Adems existen tringulos issceles que son rectngulos, p~ro ningn tringulo 'equiltero es rectngulo. ".

2.3.3. Igualdad de conjuntos Es claro que dos conjuntos son iguales si son idnticos, es decir. si tienen los mismos

elementos. Entonces, todo elemento del primero pertenece al segundo, y todo elemento de ste pertenece al primero.

Definicill A~13=A,-B B ': A.

Ejemplo 2-6. Los conjuntos de nmeros reales

son iguales ya que

A = ( x / X2 = x} B

( , , X i (x - 1 ) . x := O (

x e A ~ X2 = X X2 - X = O ~ x . tx - 1) = O ~ X e B El bicondicional se desdobla en las dos implicaciones que prueban la doble

inclusin, y en consecuencia la igualdad.

Ejemplo ]7 Sean los conjumos de nmeros enteros

( ~ A = t xi X2 = 1 f B = { x I Ixl = 1 }

Teniendo en cuenta que el cuadrado de un nmero entero es igual al cuadrado de su val,u absolu~(\, resulta

X A ~ :;:: => "'" Ix i xe3

En consecuencia, A "" B.

Ejemplo 28. Demostrar que el conjunto de los nmeros naturales impares es igual al conjunto de ,

los nmerol naturales cuyo cuadrado es impar. Hiptesis) A = { X e N I x es impar} Tesis) A = B

B = { X e N I x 2 es impar } Demostracin)

}}

t

IGUALDAD DE CONJUNTOS 33

Nota preria: Por definicin, un nmero natural x es impar si y slo si existe k N tal que

x=2k-1. Por otra parte, es fcil ver que el producto de dos naturales consecutivos es impar, y

que la diferencia entre un nmero par y uno impar es impar. Vamos ahora a nuestra demostracin, la cual consiste en probar las dos inclusiones que definen la igualdad 10) A e B. En efecto: sea x A.

Se tiene x A "'" x es = x = 2 k - 1 con k E N =:> "'" X2 -:::,.. k'- 4 k 't- 1 con k N ""'" X2 =:" C~ k - 2 k\ + .2 - 1 """ :=> x~ e,>; 4,2 ft" ~- ~ k .-

- 1 'el1l1n k :'i =o-=7 x: es l'llpar = x ti B

Hemos utilizado sucesivamente, la definicin de A. la det!nil:in de nmero impar. cuadrado de un binomio. la distributividad de la multiplicacin, la susttucin de I pr (.:! ~ n. nuevamente la disuibutividad. la definicin de nmero unpar. y finalmente la def'mcin de B.

2) B e A, Es claro que x = x (x + 1) - x " Ahora bien

x e B =? X2 es impar =} x. (X + 1) - X2 e, impar => => x es impar =} x A

En consecuencia A = B.

1.3 A. Propiedades de la inclusin "

i ) REFLEXIVIDAD. Todo conjunto es parte de s mismo. En efecto. si A es un conjunto, la implicacin

Vx :xeA =>xeA es V

En ,:oH,ecacnci!L por det1nidefl, se tien.:- \ C \, i TRANSITlVIDAD SI un .:onjuntu "s pan;.' ,'Tr",

ter(ero" ~niuJl..:;;S ~i prlm~ro csti ~.n~lud en 2'1 HlpoteslS) A e B

BC e Demostradn)

Sea .'( E A. Por hiptesis se tene X A ,= x B

Y xeB =>xeC

Tesis) A

es J~ un

www.

Matem

atica

1.com

:H CONJUNTOS

bronces, por ley del silogismo hipottico "

xEA =>XC

Y, en consewencia, por definicin de inclusin AC C. ji) ANT!SIMETRIA. Si un conjunto es parte de otro y ste es parte del primero,

entcnces son iguales.

ACB 1\ BCA =A=B

s una consecuencia de la definicin de igualdad.

~.3 5. Caracterizacin del conjunto vaco ! ) Propiedad. El conjunto vaCo est incluido en cualquier otro.

(..:ssl A .;:~ un ..:onjunw. i-::ilS) rp CA. Demostracin) Consideramos la siguiente proposicin:

' =xeA 'a ':'.1;:11 es V por ser el antecedente F. En consecuencia. de acuerdo con la definicin ..le md..:sin. se tiene C A. y"u,'

E teorema es vlido cualquiera que sea A; en particular, A puede ser vacio. ji ) Propiedad. El conjunto vaco es nico.

En efe..:to. suponemos que. adems de 1>, existe 1>' tambin vado. Entonces. de l;U"a!o con i ). es verdadera la proposicin

I/J' e I/J ,~ c liJ' y por Jefinicin de igualdad. resulta 1>' = 1>

Ejemplo 2-9. Demostrar A e fb = A = p. Como se trata de una igualdad se requieren dos inclusiones.

1") f;CA por2.3.5.i). 2) A e 1>. Se verifica por11iptesis.

luego A = .

@2.4. CONJUNTO DE PARTES

[1-Jo un L e A, y por la misma definicin 1> e P \ Al. Es

decir. cualquiera que sea A.. el mismo A y el vaco son elementos de P lA). Ejemplo 2] O.

Detenninar el conjunto de partes de A;;;: ( :2 , 3 ,4} Los elementos de P lA) son todos los subconjuntos de A, es decir

rp ,') (" r l ~2),pj.\4j l.... l (... '" r 1, ,_,3;. _,4(,,3,4, 1" ,,) l..., ..1

A

y la notacin por extensin es

((' {''l {' {'l '} {) l P (A) = \1>, \2 j, 3), 4), 2,3 j , F' 4 , 3 ,4 ,A f Ejemplo 211.

) El conjunto de partes del vaco es el conjunto cuyo nico elemento es el vaco.

P(4J)={CA cf;eA

cf; EP(A)

V

F V

www.

Matem

atica

1.com

36 CONJUNTOS

1/> CP(A) V {' 2,3) eP(A) V

2 P (A) F

{ 2) P(A) V AP(A) V AA F AC A V

!:lemplo JI:J. Si A time .'1 elementos, enhm.;e" P A) tiene 1" elementos, Se trata de computar ei

nmero de sub.;onjuntos de A,. Uno de ellos es el vado. Conjuntos unitarios hay flI'J' d' b' , d I d d exactameme 11 = I 1 . es eClr. tantos como com maClOnes e fl e ementos, e or en \ '

1, El nmero de suhwnjuntos de dos elementos es el de combmaciones de

-ti elementos de orden 2, es decir 1" I

il". Subconjuntos ternarios hay (3 ! :

\ /

Y as sucesivamente, hasta obtener el nico subconjunto de II elementos. El nmero total est dado por la suma

II!' 'n' .' n . .',,' 'u 'n' +i.,l+t~l+ +1 1+1=11+1 I+j.,!+ _J .1, JI - 1'.0... L ,_,

n

L i=O

.n) n {f/I , ( i. = 1: , i) 1'. 1 n - i = (1 + 1)" :;;;; ~n ;=0

, : I! + 1=

.. nI

En este desarrollo hemos aplicado la frmula del binomio de Newton. que se justificar en el Captulu .

1.5 C(j\WlDIE:-" r ~,C10N DE CONJUNTOS

Sean A Y B subconjuntos de L, 2.5 .1. Definicin

Complemento de A es el conjunto formado por los elementos de U (1ue no pertenecen a A.

El complemento de A se denotar por A C ; suelen usarse tambin A' y A.

ir.t:--~- .... -.. ~._ ...

COMPLEiIILNTAClON DE CONJUNTOS 37

En smbolos N= {xU/X~

obien

AC = { x I x t

Se tiene xc:AC ""*xiA

El dl:.I':;'' ,la ,j" YcHl (;,j.

La complementacin es una operacin unitaria. en el sentido de que a partir de un conjunto se obtiene otro.

Es usual tambin obtener el complemento de un conjunto A. respecto de otro S, en cuyo caso la definicin es

C' A = [ x e B i x f A> "-'B, '

En particular se tiene ) El complementario del vaco es el universal.

:; x U => x f rf> => X 6' (J ~1f'J le:: tjl.'

\~I,}IWJ I;'{ resulla \ ) El ,'lmpl.:m,;n;rlO del un;ers;i es el

llC -::= (.~ x E U x f L

2.5.2. Propiedades de la complementacin

, I) INVOLUCION. (Ae )'" = A Demostracin)

=1/>

x(A{ ~xttAe ~-(xA(") ~-(xttA) c>xA

www.

Matem

atica

1.com

38 CONJUNTOS

En esta demostracin hemos utilizado la definicin de complemento y la ley involutiva del clculo proposicional.

II) A e B =-? Be e Ae

Demostracin) Utilizando sucesivamente las defi~iciones de complemento, de inclusin y de complemento, se tiene

Luego

Ejemplo 2-J3.

x E Be "'" X f B =O> X f. A => X e AC Be e A C

Demostrar A = B => A e :::: Be

x A (' ~ x ti. A ~ x fi B ~ x Be tn virtud de las definicions de complemento, igualdad y complemento.

Ejemplo 2-14. i ) Si , es una recta incluida en el plano 0:, entonces su complemento es el par de

semiplanos opuestos abiertos, de borde r. ji ) El complementario del conjunto de los nmeros naturales pares es el

conjunto de los naturales impares. iii) El complementario de Q en R es el conjunto de los nmeros irracionales.

..-2.6. INTERSECCION DE CONJUNTOS

Sean A Y B subconjuntos de U.

2.6.1. Definicin

Interseccin de dos conjuntos A y B es el conjunto formado por los elementos que pertenecen a A y a B.

El diagrama de Venn correspondiente es

u

A B

~t

I ~

<

J t

t I <

I ~

.,

I

INTERSFCCION DE CONJUNTOS

En smbolos se tiene

ArlB={xeU!XEA 1\ XEB} O bien, sobrentendido U

ArlB::;{x/XA 1\ XEB}

39

La interseccin entre conjuntos es una operacin binaria, porque a partir de dos conjuntos se obtiene un tercero.

La propiedad que caracteriza a los elementos de la interseccin es la de pertenecer s!mnlt~nl"llml"nre In~ rlo~ conjlJntm y o;e e~t:lhlece en trminm de una conjuncin

La defnicin de interseccin establece

xeAnB xeA /\ xEB

Si la interseccin de dos conjuntos es vaca ,dichos conjuntos re llaman disjuntos. A y B son disjuntos ~ A n B = iJ>

Ejemplo 1-J 5. ) Si r y r' son- dos rectas distintas incluidas en un plano, entonces su

interseccin puede ser vaca, o bien reducirse a un punto. En el primer caso son paralelas. y en el segundo caso se llaman incidentes.

ii ) Sean dos rectas AC y AB, donde A. B Y C son tres puntos no alineados pertenecientes al plano a. Quedan definidos los conjuntos

S (AS, C) : semlplano de borde AB que pasa por C S (AC , B) : semiplano de borde AC que pasa por B

Entonces el conjunto S (AB C) rI S (AC , B) es el ngulo convexo BAC

a

i) Consideremos tres pumos distintos A, B Y e pertenecientes a la recta r:

A B C r

www.

Matem

atica

1.com

40 CONJUNTOS

la, semirrectas S (A , B) (de origen A que pasa por B), S (A , C) y S (e , B) son subconjuntos de r, taies que

S (A, C) n S (e, B) = AC S (A, C) n S (A ,B) == S (A. C) = S (A , B)

iv) La interseccin entre el conjunto de los nmeros enteros pares y el conjunto de los nmeros impares es vaca, ya que no existe ningn entero que sea simultneamente par e impar.

v) En Z.la interse X A 1\ X B n e .... x A n (B n C)

llI)eONMUTATIVIDAD: A n B = B n A. La demostracin es obvia aplicando la definicin de interseccin y la

conmutatividad de la conjuncin.

1\ 1 ELEMENTO NEUTRO PARA LA INTERSECCION ES EL lNIVERSAL La !nterse2cion opera sobre eiementos d.~ P (t;j~ ~~ Jc~~if ~ lbre :;ut~nnjn;G:; :1Z'

J:. Interesa determir.ar s existe un subconjunto de l: cuya interseccin ":"1": cuaiquier otro no lo altere. Tal elemento de P () se llama neutro para la interseccin, y en nuestro caso es el mismo U. En efecto

cualquiera que sea A e U, se verifica A n e =' U n A = A

Ejemplo 2-16. La propiedad IV es un corolario del siguiente teorema

AC B ~ AnB=A

I 1

INTERSECClON DL CONJUNTOS 41

Por tratarse de una condicin necesaria y suficiente realizamos las demostraciones de las dos implicaciones:

)ACB =*AnB=A Con la informacin proporcionada por la hipte5is A C B, tenemos que demostrar la igualdad A n B = A. Por defJi1icin de igualdad hemos de probar dos inclusiones: a) Sea x tI tal que x A n B. Ahora bien

x A n B = x fA:. x e B =:> X A

por defmicin de intersecd!!. y ley loglca p q ""'" p. En consecuencia ,~ n B e \ i l i La relacin (1) nos dice que la interseccin entre dos conjuntos est incluida en cualquiera de ellos.

b) Sea ahora xeA=>xeA ,,'xeB =:.xeAnB

por la hiptesis y por definicin de interseccin. Entonces se verifica A e A;, S (2),

De (1) y (2) resulta A n B = A. ii)AnB=A ~ACB

Para demostrar que A C S, consideramos

xeA =>xAnB ~xeA " xeB =>xeB pues por hiptesis A = A n B; hemos utilizado adems la definicin de interseccin y ia iey lgica p ,. q => q. Queca probado as que A e B.

Ntese que en i ) a) no hemos hecho uso de la hiptesis, pero s en b). Esto nos dice que la proposicin A n B e A es independiente de toda condicin, es decir. es una propiedad intrnseca de la interseccin.

Ejemplo 2-}7. Demostraremos que " dos conjuntos estn incluidos en un tercero, entonces in

interseccin de los do; primero!;.:s parte del tercero. Esto se '.v A () B e X

www.

Matem

atica

1.com

CO;-WNTO:-.

Lo demostramos as

xEA(iB "*xEA A xeB "*xeX 1\ xeX "*xeX Hemos aplicado sucesi\amente la definicin de interseccin, la hiptesis y la ley

" gca p " p ~ p. .r qemplo 2-18.

Demostrar que el conjunto de partes de la interseccin es igual a la interseccin de 1\ 's conjuntos de partes.

. P(A n B) = P(A) (iP(B) En efecto: teniendo f'n ("lienTa 0111" 1(1~ f'lt'mi'ntn~ ilp h~ n'lrtp< ,;p lln ,.."n;"",,, .,,,,

.b'::03Jlntos, consdemmo; -. - --- - L' - - -- - -. ---"J~'''- ----

XPA0B) doXCAnB ~X'':A XCB ~XEP(A) ~ Xe P(A) np{s)

XeP(B)

'f Jefnicin ue conjunto de partes; teniendo en cuenta i ) a) del ejemplo 2-16, la :ms,vidad de la relacin de inclusin, la definicin de conjunto de partes y la

:, -mdn de interseccin,

2.7. UNION DE CONJUNTOS

: i.1. Definicin

l nin de dos conjuntos A y B es el conjunto formado por los elementos que pertenecen a A o a B.

Simblicamente se indica (' ~

AUB=tXUxA v xEBJ

Pre5cindiendo del universal

Aus={x1xeA v XES}

La unin de conjuntos, lo mismo que la interseccin, es una operacin binaria definida en el conjunto de partes de U,

De acuerdo con la definicin, podemos escribir

aAUB~aEA v aeB

El "o" utilizado es incluyente. y pertenecen a la unin aquellos elementos de U ~a los .:uales es verdadera la disyuncin; entonces un elemento pertenece; la unin " 3d.) si pertenece :l alguno de los dos conjuntos.

I ,

I 1 r ,

I t

j '1 1 t 1 j

~

l

UNIN 1)1. CONJUNTOS 43

El diagrama correspondiente es

A la unin pertenecen todos los elementos de los conjuntos dados. En e I caso disjunto se liene

donde la pan.: ~umbreada es A U B . Es claro (1',,' todo conjunto est contenido en su unin con cualquier OtiO, En

efecto

X E.~ => X A v X S => X A U B

en virtud de la ley lgica p => p v q, y de la definicin de unin. Entonces

A e A U B como queramos.

Ejemplo 2-/9. i ) La unin de un par de rectas r y r' contenidas en un plano es el par de rectas. ii ) La unin de dos semiplanos opuestos y cerrados es el plano. i) Sean los p,;ntos A. B Y (', como en el ejemplo 215. iii). Se tiene

S (B , A) U S (B ,C) = r StA, B) U S (B. C) = S (A. B)

2.7.2. Propiedades de la unin

I) IDEMPOTHiCJA. ualquiera que sea A. se verifica AUA=A

Pues xeAU;\ *'>xeA v xA~xeA

por definicin de unin, y la ley lgica p v p

~

44 CONJUNTOS

m ASCIATIVIDAD. Cualesquiera que sean A, B Y e (A u B) U C = A u (B u C)

La demoslwCn es anloga a la propuesta en el caso de la asociatividad de la interseccin, utilizando ahora la definicin de unin y propiedades de la disyuncin.

lH) CONMU'T A TIVIDAD. Para todo par de subconjuntos de U, se verifica AUB=BUA

fue", x f A B """ x e.\ v x e B > X B X A ~ X B ',.' A

IV, ELEMEl"TO :-ECTRO PAR>\. LA tJNION ES El CONJUNTO VACIO. Es decir, cualquiera que sea A e U, se tiene

AUP=tjlVA=A Tratamm slo el caso A V (J == A, ya que la conmutatividad nos exime de la otra

situacin. Sabemospor '::.7.1. que A C A u ~ x e A v x e if ~ x e A

por definici~n de unin, y por ser falso x e ifJ . Luego AU P CA (2) Por ( 1) Y (2) resulta la igualdad propuesta.

Ejemplo 2-20. Demustrar A .: B "'> A U B = B. Seguimol el mismo esquema empleado en el ejemplo 2-16.

) Hiplesis} A C B Tesis! A U B = B Dem()stracin) Como cada conjunto est contenido en su unin con cualquier Otro. segn 2.7.1 se tiene

B -\ B (nsid~renlOS Jb~)r3

teA\,.,S =>xA v xB ='xi:S v xB =>xEB

por definicin de unin. por hiptesis y por la ley p v p ==1> p. Entonces: De (1) y (2) resulta A U B:= B

ii) Hiptesis) A U B = B Tesis) A C B

AUBCB

Demostracin) x A ~ X e A V B => x B

!1}

(21

"

i r l,

! 1 f'

'-

1 i'

t

i i

1'1WPIEDADES DE L:\ UNION 45

porque si un elemento. pertenece a un conjunto, entoncs pertenece a su unin con cualquiera y adems por hiptesis, ya que A V B = B.

Es decir: A C B.

Ejemplo 2-21.

) Demostrar X e A 1\ X e B =:> X e A U B. En efecto. sea

XEX =xeA \1 xEB =:>:\'eAUB

le' ~U(; e~ d'::ft por y ddinlcion ,le .min i 1 L:l imp!k.;in anterior no admite rCI:I'proC;; verdader:.!. ~ J que puca", darse

que X:::: A 'J B. Y sm emb;rgo X: .0\ } X''::' B. corno puede ';crse en el diagrama sigUIente

A~B e

iii)Demostrar P(A)UP(B)C P(AUB).

r'JDsidaemos

XeP(A)UP(B) =* XeP(A) v XeP(B) => =XCA v XCB =XCAUB =XP(AUB)

por definicin de. unin. de conjunto de panes. propiedad ). y definiCin de .:onlmWJ de pane,

~.'1. LEYES DlSTRIBt:TIVAS

La umn e interseccin de cOl)junto:. pueden conectarse a travs de dos propiedades fundamentales. llamadas leyes distributivas, que se expresan mediante las frmulas

(A U B) n C = (A n

16 CONJUNTOS

B B

(AUB)r.C (A n C) U (B n C)

Las demostraciones fonnales s:m las siguientes:

:.~.i. Distributividad de la interseccin respecto de la unin x (A U B) n e ~ x A U B ,\ X e ~ (x A v x B) " x C >

~ (x A ,\ X e) v (x B 1\ X e C) ~ x E A n e v x e B n e > ~ X e / A l C) U (B l el

?cr definiciones de interseccin y de unin. y distrbutividad de la conjuncin respecto de la disyuncin.

1.'L!. Distributividad de la unin respecto de la interseccin

xe(AnB)ue >xeA:lB v :cee *> ~ (x A " x B) v X e >

~ (x A v x C) \ (x B v x C) ~ ~ x E A U e A x lE BU e ~ -xe(AUC) n (BUC)

Se han utilizado las defilliciones de unin, de ~nterseccn. y la ley distributiva de la lis: uncin respecto de la conjuncin.

2.9. LEYES DE DE MORGAN

Estas leyes, de gran aplicacin. penniten relacionar la complememacin con la unin e interseccin.

:.9.1. Teorema. El complemento de la unin de dos conjuntos es igual a la intersec. .:in de sus complementos.

,

l r t"

I

LEYES DE DE MORGAN 47

Tesis) (A U BY = AC n Be Demostracin) x e (A U By ~ x 1/ A U B ~

*> ~(x A U B) *> -- (x E A v x E B) *> ~ x r A A X ti. B ~ x e AC /\ X e BC *>

~xAc n BC

Por definicin de complemento, de unin, negacin de una disyuncin, y defmicin de interseccin.

2.9.2. Teorema. El complemento de la interseccin de dos conjuntos es igual a la u;-Jn de sus cuiliplcil1CitOSa

Tesis) (A n Bt ::;:: AC U Be Demostracin) x (A n B)C > x tAn B *>

*> ~ (x A n B) *> -- (.v e A\ x B) ? *> x ti A v x f B *> x A e V X Be .... X e AC U Be

De acuerdo con las definiciones de complemento. de interseccin, negacin de . una conjuncin y definicin de unin.

Ejemplo ].]2. Demostrar la equivalencia de las siguientes proposiciones:

ACB Be CAe AUB=B AnB = A De acuerdo con lo establecdo en el Captulo 1, para demostrar la equivalencia de

una cadena de n proposiciones, es suficiente probar n implicaciones. En nuestro caso

p~q~r~s~p

1) ACB~BcCAc En efecto x SC ~ x t B ~ x f. A ~ x A C

por defmicin de complemento, por hiptesis y defmicin de complemento. 2) Be e A e ~ A U B = B

Sea x e A U B ~ x A v :x e B ~ ~ x ; A e V x e B ~ x tt Be V X e B ~ ~xB v xeB ~xeB

. por definiciones de unin y de complemento, por hiptesis, definicin de complemento y ley lgica p v p ~ p. .

As AVBCB (1)

www.

Matem

atica

1.com

.........

43 CONJUNTOS

Por Jtra parte B e A u B (1)

ya que todo conjunto es parte de su unin con cualquier otro. De el) Y (2) resulta A U B == S

3) A U I:l = B ~ A n B = A a) COITO la intersel:cin est incluida en cualquiera de los dos conjuntos. se tiene

AnBe A biSca xEA "",,'xeAUB =*"xGB

puc, \ = A >_' B y por hinM",i, Entonc~s

(1)

xeA =xeA A xeS =xeAns

Es ,lecir ACAns ( 2) Por ( 1) Y (2) resulta

AflB=:\.

4) A n B = A =:> A C B ESl demostrado en el ejemplo 2-16 ii )

2.10. DIFERENCIA DE CONJUNTOS

2.10.1. Dtfinicin

Diferencia entre dos conjuntos A y B es el conjunto formado por los elementos de A que no pertenecen a B.

A-B::: fx xcA t. xtB) , "'

El diagmm: wrrcspondiente e!'

B

Es dan que A - B *' S - A; es decir. la diferencia de conJuntosno es conmutativa.

.. ~ '" 1 {i '( I

'$e ~ .~ !; 1

1 f I ,

.JI'

DIFERENCIA DE CONJUNTOS 49

Ejemplo 2-23. i ) Considerando como universal al conjunto de los puntos del plano, la

diferencia entre la recta /' y el segmento AS es la unin de las semirrectas abiertas AM Y BN

A 13 r 1-

.----~------~~>- -- --r- ----o

~t N

) La diferencia entre el .:onjunto de los nmeros pares y el conjunto de los nmeros primo5 es el conjunto di' j')5 nmeros enteros del tipo :, .~ 2 . k siendo k *:t 1 .

2.10.2. Propiedad. La diferenda entre dos conjuntos es igual a la interseccin del primero con el complemento del segundo. I

Se trata de probar que A - B:: A n Be. En efecto. aplicando sucesivamente las definiciones de diferencia. complementacin

e interseccin, se tiene

A-S={xIXA!I X~B} I x e A !I X Be } = A n BC

Ejemplo 2-24. Demostrar seA

)

IfL~"" , " r

'1.'

50 CONJUNTOS

aplicando 2. JO. 2, ley de Dc Morga n, distributividad de la interseccin respecto de la unin

(A n B) -' (A n ej = (A n B) n (A n e)c = = (A n B) n (A e U Ce) = = (A n B n A e) U (A () B n Ce) = = q, U (A n B n Ce) = A n B n Ce

De (1) y (2) resulta

A n (B - C) = (A (lB)-(A ne)

2.11. D1FERENOA SIMETRICA

Sean A Y B dos subconjuntos de U.

2.11.1. Defmicin

(2)

Diferencia simtrica de los conjuntos A } B es la unin de los conjuntos A - B Y B-A.

ta notacin es A b. B = (A - B) U (B - A)

Y el diagrama coITespondiente

Otra identificacin de la diferencia simtrica es

A b. B = (A n BC ) U (B n AC ) (2)

(1)

que se deduce como consecuencia inmediata de la definicin, teniendo en cuenta que la diferencia entre dos conjuntos es igual a la interseccin del prim~ro con el complemento del segundo, segn 2.to.2.

Resulta tambin

A b. B = (A U B) - (A n B) , (3)

,

.Y{. i: :'

I i I

DIFFRENCIA SlMFTRICA

En efecto A b. B = (A -- B) U (B - A) = (A n Be) U (B n A C) =..'"

= [(A n BC ) U Bl n [(A n BC ) U AC ] = = (A U B)n(BC U B) n (A U AC)n (BC U AC ) = = .(A U B) n U n U n (AC U BC) = =: (A U B) l (A C U BC) = (A U B) n (A n B)C = (A U B) - (A n B)

~l ,

De acuerdo con (2), por ley distributiva de la unin respecto de la interseccin, por ser Be U B = A U AC = U, por ser U neutro para la interseccin, por conmutatividad de la unin, por ley de De Morgan y por 2.10.2.

Las expresiones alternativas para a diferencia suntrica son

A 6. B=(A-S)U(B-A)=(AnBC)U(BnAC)= = (A U S) - (A n B) = (A U B) n (A n B)C

,

2.11.2. Propiedades de la diferencia simtrica '

I) CONMUTA TIVIDAD A A B = (A - B) U (B - A) = (B - A) U (A - B) = B b. A

Il) EXISTENCIA DE NEUTRO. En P (U), el vaco es neutro para la diferencia simtrica. En efecto

At:.cjJ=(A -cjJ)U(cjJ- A)= A utJ>= A = cjJ~A 1II) EXISTENCIA DE INVERSOS. En una operacin entre elementos de un

conjunto (en este caso el conjunto es P (U). los elementos son los subconjuntos de U y la operacin es la diferencia simtrica), interesa determinar si, dado un conjunto, existe otro cuya diferencia simtrica con l es el neutro. Afirmamos que todo. conjunto A e U admite I mismo A como inverso respecto de la diferencia simtrica. En efecto

A t:. A = (A - A) U (A ....: A) = cjJ U cjJ =

52 CONJUNTOS

= (A n Be n Ce) U (A e n S n CC) U (A e n BC n' C) U (A n B n C') = = (A n B n C) U (A () SC n CC) U (A e () B n CC) U (A C n Se () C) (l)

En este desarrollo se han utilizado las consecuencias de la definicin de diferencia simtrica, leyes de De Morgan, distributividad de la interseccin respecto de la unin y la conmutatividad.

Desarrollamos ahora el segundo miembro aplicando la conmutatividad de la diferencia simtrica y utilizando el resultado anterior

A6.(S 6C) == (B 6C)6.A == =(8 n e n'A) U(BncC nA') V(Be n C n AC} U(BC n Ce n Al.;; =(A n B nqU(Ac n Bn CC)U(AC n Sen C) U(An BC n C') De (1) Y (2) resulta (A 6. B) 6. C = A 6. (B . C)

Ejemplo 226. i) La diferencia simtrica entre los intervalos reales

(I ,-)6.(-00,3J=(3 ."")U(- ..... l) ji) En cambio

(1 , CCI) . (- 00 3) = [3 ,(0) U (- 00 1]

Ejemplo 2-27. Demostrar la ley cancelativa de la diferencia simtrica, es decir

En efecto

Ejemplo 2-28.

A.B=A6.C ~B=C

A 6. B = A 6. C ~ A 6. (A Ll B) = A Ll (A Ll C) .... .... (A Ll A) Ll B := (A Ll A) Ll e .... =>9l::.B=i;'>[,C =:> B=C

(':)

Demostrar la distributividad de la interseccin respecto de la diferencia simtrica. Tesis) (A D. B) n C = (A n C) tJ. (8 ri e) . Demostracin) Desarrollamos los dos miembros por separado

(A Ll B) n C = [(A n BC ) U (A C n B)] n C = = (A n BC n C) U (A C n B n C) (1)

.~

, ~;

i ~ .. i:

I "" ;;

.~ t I1

PRODUCTO CARTESI/\NO DE CONJUNTOS

(A n C) b. (B n C) = [(A n e) n (B n C)e] U [(A n Cl' n (B n C)] =. = [(A (i C) n (BC U Ce)] U [(Ae U Ce) n (B n C)] = ::;;; (A n C n BC ) U (A n C n Ce) U (A C n B n C) U (Ce n B n C) = =(A n BC n C)U

L"

54 COl\JUNTOS

En particular

A X A = A 2 = { (a , b) I a E A /\ b E A } Ejemplo 1-19.

) Producto cartesiano de A = { 1 , 2 , 3} Y B = {1 , 2 }

A X B = { (I , 1), (1 , 2), (2 , 1) , (2 2), (3 , 1) , (3 2) }

ii ) Por ser pares ordenados, los elementos del producto cartesiano de dos conjuntos pueden representarse mediante puntos del pIano cuya abscisa y ordc&ada SC~f respecli\'aientc~ !a prh-ncra ,. Li ~gundd ;.;OIHpuncIllc.

Q} " 2 I /" m en AX B B

2 3 A

Los vrtices de la cuadrcula obtenida son los elementos del producto cartesiano. ii) El producto cartesiano no es conmutativo, pues

Ejemplo 2-30_

(3 , 1) A X B Y (3, 1) f B X A => =>AXB#:BXA

Sean los intervalos cerrados de nmeros reales

Entonces

[a,b]= {xeRla

56 CONJUNTOS

Ejemplo 2-32. El producto cartes'jano es distributivO respecto de la unin

En efecto

(A U B) X C = (A X C) U (B X C)

(x ,y) ( A U B) X C

Iiiroo.-

SR CONJUNTOS

Ejemplo 233. Operaciones con intervalos reales

i) U [i-I.i)=[Q,I)U[I.2)U[2.3)U .... = i = 1

= R' U {O ) = [0,(0) donde R ~ denota el conjunto d~ los nmeros reales positivos.

ii) r- ~, ~) =(-I,l)n L ~ . ~, n .... = {o} i'" 1" ,,7 \ _ _J '"

iii) "" ~ r\\o, n .... "'" q, =(0.1)" (O, ;) Il (o,J..) ,_, \ 3.1 2.14. UNIONES DISJUNTAS

En Probabilidades se utilizan uniones de conjuntos disjuntos y en lugar de utilizar las notaciones

A U B para el caso A 0 B = rt>

es usual escribir

A+B

smbolo que indica una unin disjunta. Si se tiene una unin arbitraria de conjuntos. sta puede expresarse como unin

disjunta de la siguiente manera AUB =A+Ac nB

EiI:t Consideremos ahora la unin de tres conjuntos Al, A2 Y A3 ; la podemos expresar

como unin disjunta mediante 3

U A = Al + Ai n A2 + Ai n A~ n A3 j= 1

OPE.RACIONES GENIRALlZADAS 59

lnd'icando con el smbolo ; la unin en el caso disjunto, la expresin anterior en el caso de una sucesin de conjuntos puede escribirse as

U A == Al + i: A~ n A~ n .. > n A~ 1 n Aj i e N j = 2 J.

Se trata de probar esta igualdad. a) El segundo miembro es una unin disjunta.

Sean dos trminos de la sumatoria con i i= j. por ejemplo: i < j. Se tiene (Afn ... nAi.lnAi)n(A~n .. > nAi n ... lAf. nAj )= = JI pues A n Af = rJ>

b) Todo elemento del primer miembro pertenece al segundo.

Sea x U A '* 3 i N x A ie N

Si k es el menor entero positivo para el cual x Ak. se tiene x t Al U Az U ... U A

Ir.\ ya que x no pertenece a ningn A con i

TRABAJO PRACTICO 1I

2']4. Se consIdera un experimento aleatorio consistente en lanzar tres monedas. Si una moneda cae cara. se anota 1, Y si cae sello se anota O. Formar el conjunto cuyos eleme~tos son los posibles resultados del experimento.

2-35. Con nlacin al ejercicio anterior, detenninar por extensin los siguientes sub-ConjuIltoS:

SI : se dan ms caras que sellos. $2 : s~ obtienen al menos dos caras. S3 : se obtiene el mismo resultado en las tres monedas.

2-36. Con los conjuntos defmidos en 2-30, obtener: S~ ;S2 -S3 ;SI nS3 ;(S2 US3 )ns

2-37. Sean los conjuntos A = { x e Z ! Ix .;;; 3 } B ( ::Z' 2

!J2

2-54. Demostrar

2-55. Demostrar

2-56. Demostrar

2-57. Demostrar

}-58. Demostrar

2-59. Demostrar

]-60. Demostrar

]-61. Demostrar

2-62. Demostrar

2-63. Demostrar

]-64. Demostru

]-(j5. Demostrar

2-66. Demostrar

i ) Ue = p ii) U = pe

J67. Demostrar

CONJUNTOS

A = (A n B) U (A n Be)

B C A ~ (A - B) U B = A

(A - B) U B = A U B

AL1B=if>~A=B

AXB=t,b ~A=P V B=t,b

ACB 1\ CCD~AXCCBXD

(A t"'I B) X C = (A X e)!\ (B X C)

(A - B) X e ::::; (A X C) - (B X C)

i) A C B =!> (A U C) C (B U C) ) A C B =!> (A n C) C (B n C)

ACB 1\ Ace ~ AC(BnC)

A C e 1\ B C e - (A U B) C C

AnB=p 1\ AUB=C =!>A=e-B

ili) AnAc=p iv) AUAc=U

AUB=U 1\ AnB=cp~B=Ac

H

~

2-68. Demostrar

TRAUAJO PRACTICO I!

i) A-(A- B)= A n B ii) A U (B - A) = A U B

].69. Demostrar la equivalencia de

AUB=U y ACCB 2-70, Demostrar la equivalencia de

A e Be y A l B =

iIl.....-

Captulo 3

RELACIONES

3.1. INlRODUCCION

Se des:molla aqu un tema de fundamental importancia en el esquema de la mato!mtlca actual: las relaciones binarias. Mediante ellas es posible vincular elementos de dos conjuntos, no necesariamente diferentes, y segn sea el tipo de conexin se tienen las distintas ciases de relaciones. En este captulo se estudiarn con adecuado detalle las relaciones de equivalencia y de orden.

3.2. RELACIONES BINARIAS

Sean ;\ y B dos conjuntos y P (x y) una propiedad relativa a los elementos x A e y B, en ese orden. Esto sugiere naturalmente la consideracin del producto cartesiano AX B, Y la determinacin de los pares ordenados (a , b) para los cuales P (o b) es una prOposc1n verdadera. De este modo queda definido un subconjunto R e AXB. llamado relacin.

Para fijar ideas consideremos el conjunto A formado por las personas a. b. e y d. Y el conjunto B cuyos elementos son las posibles notas semanales obtenidas en una asignatura, L 2, J, 4 Y 5, correspondientes a insuficiente. aprobado, bueno. distinguid0 ~f sobresaliente E decir

A={ a.b.c.J) y B-J i "" 4';1, -l. ,-.", ,- )

Los elementos de A quedan vinculados con los del conjunto B mediante la propiedad

p (x, y) : x obtuvo la notay SupGngamos que la situacin al cabo de una semana queda especificada mediante el

siguiente diagrama

I

t

r

RELACIONES IllNARIAS 65

Esta relacin entre A y B est caracterizada por el conjunto de pares ordenados

R = { (a ,2) ,(a, 4), (P ,4) . (d , 5) ) como e no tiene ningn correspondiente en B. consideramos que no ha sido clasificado en la semana. Se tiene

(x ,y)R ~ P(x ,y) es V

Definicin Relacin entre A y B es todo subconjunto del producto cartesiano AXB.

Ensmbclos

R es una relacin entre A y B

RELACIONES

Considerando el ejemplo propuesto en 3.2, se tiene:

5'" l I I ;/ t' '\ AXB 4 J I (+ ;p.e I \: \

3 I I I~ /1 I ' R

2 + I ,. / I

iii) Mediante un matriz. Sobre una corumna se anotan los elementos de A, y sobre una fila los de B. En el ngulo superior izquierdo, el significado de la relacin. Se asigna a cada elemento del producto cartesiano AXB un 1 o bien un O, segn que el par ordenado correspondiente pertenezca o no a la relacin. Con el mismo ejemplo, resulta

R

a

lJ. e

d

O O O O

:2

O O O

3

o O O O

4

O O

5

o O O

3.4. DOMINIO. IMAG~N, RELACION INVERSA

Consideremos una relacinR entre los conjuntos A y B. Si (x . y) R diremos que y es una imagen de x a travs de R. y que x es un

::mtecedente o preimagen dey por R.

Definicin :~ Dominio de R es la totalidad de los elementos de A, que admiten imagen en B

D R = {x A I (x ,y) R }

:it "*

".1

t' * .. ~

~':.

" ~,i. "", i "':,

i

RELACIONES lNVc.RSAS 67

Definicin / Imagen de R es el conjunto de los elementos de B, que admiten un antecedente enA

iR = {y B I (x ,y) fE R }

Definicin '-Relacin inversa de R es el subconjunto de BXA definido por

R- 1 ={ (Y,x)!(x,y)R}

Ejemplo J-J. Con relacin al caso estudiado en 3.2, se tiene

DR = (a.b.d} , -' IR = {2,4, S}

La relacin inversa es R- 1 = (2 ,a).(4 ,a).(4.b).(5 ,d)}

\ -

y corresponde a la propiedad P (y . x) y es la nota obtenida por x

El grfico cartesiano de esta relacin inversa es

di 1I I 1+) \

c\ I IUI ~R-I

b+ ' I I ,t" I a ~ \ I r, /F\: + J I I

2 3 4 5

www.

Matem

atica

1.com

68 RELACIONES

3.5. COMPOSICION J.?E RELACIONES

A partir de las relaciones Re AXB y S e BXC, es posible definir una relacin entre A y e, llamada composicin entre R y S, mediante

S_oR = {(X,Z)/3YfB A (x~Y)fR /1 (y,Z)fS} La composicin de relaciones admite las siguientes propiedades:

i ) Asociatividad. (T" S) R = 1" (S o R )

i ) La relacin inversa de la composicin es igual a la composicin de las relaciones inversas, en orden permutado.

(SoR)-1 =R- oS-1 Las demostraciones quedan como ejercicios.

Ejemplo ]-2. Consideremos los siguientes conjuntos y relaciones:

A= {-I,O,I} B={1,3} C = { 3/2, 5/2 , O } Re AXB est defmida por: la imagen de x es su cuadrado. S e BX e caracterizada por: el correspondiente de y es su mitad aumentada en 1.

>~ j .~ B

----.~~

--~ /=:c;i . \

A

Se tiene:

R= {(-1,1),(1, 1)) S = { (1. ;) , (3, ;)}

So R = { (-1, ;) ,0, ;)}

.;,

.,

COMPOSIClON DE RELACIONES

La relacin compuesta S o R e AXC est determinada as: X2

(x, z) S o R#-z =-- + 1 2 .

3.6. RELACIONES DEFINIDAS EN UN CONJNTO

69

Sea R una relacin entre A y B, donde B "'" A. En este caso la relacin est defnid~ en A. y se identifica con un su bco~iunto de A 2 = AX A. Definicin

R es una relacin definida en A, si y slo si R e Al . Como todo subconjunto de A"2 es un elemento de las partes de A'}., podemos decir:

R es una relacin defmida en A si y slo si R P (A'}.) ,

Es claro que el conjunto vaco y el mismo A 2 son relaciones definidas en todo conjunto A, ya que son subconjuntos de A Z

Si A tiene n elementos, entonces Al tiene n l elementos, y el conjunto de partes de A 7 tiene 2( n') elementos, es decir, existen 2(n 2) subconjuntos de A:1. o lo que es lo mismo, relaciones en A.

Ejemplo J3. Se trata de formar todas las relaciones que es posible defmir en el conjunto

A = (al ,a2} , "

a2 -J--.:.. /. "\-

~ '\ + J al "

al a2

"~":~..,.

www.

Matem

atica

1.com

~'{5 RELACIONES

Detemlinamos primero el producto cartesiano ,r- ,---.... ("--. . ..,-----....

A2={ (~l ,a),(al ,02),(a2 ,a),(a2 ,a2)}

('omo A2

tiene cuatro elementos, existen 24 relaciones en A, y son las siguientes:

Ejemplo 3-1.

Rl = } Ru ={ (412 ,a),(a2 ,a2)} RlZ ={ (al ,o),(al ,02). {al ,ad} RI3 ={ (al ,ad,(ol ,02),(a1 ,a::)} R14 ={ (al ,a),(a:z 'OI),(aZ ,a2)} Rs ={ (al ,a2),(a2 ,al), (02 ,a::) } Ri = A2

Grfico cartesiano de la relacin definida en R. mediante (x,y)ek

72 RI.LACIONES

3.7.2. No reflexividad

Consiste en la negacin de 3.7.1.

R es no reflexiva (x . xl f} R Es decir, ningn elemento de A est relacionado consigo mismo. o lo que es igual,

ningn elenento de la diagonal de A 2 pertenece a la relacin o equivalentemente

R es arreflexiva ~ R n D 'C"' I/J Es claro que toda relacin arreflexiva es no reflexiva.

Ejemplo' 35. En A = { 1 , 2 , 3} consideramos las siguientes relaciones:

i ) JI. = { (1 , 1), (2 , 2) , (3 ,3), (2 , 3) } De acuerdo con la definicin dada en 3.7.1., resulta Runa re ladn retlexiva

R 31! / 1 \

211 V r i Ir ~r i J ~nr7 -I ; 3

ii) E~ cambio S = { (1., 1) , (2 , 3) ,(3 2)} es no reflexiva, pues 2 A A (2, 2) ti R

i "

. ..

l I

PROPIEDADES DE LAS RELACIONES 73

31 ,tI (,', \

21' 1//1 \:~l: s

! 3

iii) T:::; { (l , 2), (2 , 1) , (3 , 1) \ . .)

Es arreflexiva. ya que ningn elemento de A foOlla parela consigo m ismo en la rdadn.

3.1. ,, ",

2'' {. '...: T

2 3

3. -; A. Simetra

R :;s snnetnCJ ~ v X re R= r?

Es decir. si un par pertenece a la relacin, el par que resulta de pennutar sus componentes tambin pertenece. Y en consecuencia el diagrama cartesiano es simtrico respecto de la diagonal de A 2

3.7.5. No simetra

Es la negacin de la simetra. R es no simtrica ~ 3 x 3 y I (x y) e R I (y, x H R

www.

Matem

atica

1.com

74 RELACIONES

La no ametra no impide que dos pares de componentes permutadas pertenezcan a la relacin, pero exige que haya al menos un par en la relacin, y que el quc resulta de permutar sus componentes no pertenezca a ella.

3.7.6. Asimetra

R es asimtrica *> V x V y: (x ,y) e R :;. (y ,x) t R En este caso debe ocurrir que si un par pertenece a la relacin, entonces el que se

deduce por pennutactn no pertenece.

Ejemplo 36. En A = { 1 . ~ , 3) clasificamos desde este punto de vista las relaciones:

i) 5= {n,l).q,3),(3,2)) es simtrica.

) T={O,2},(2,I),(3,O} es no simtrica. ya que

(3,I)eT A (l,3);T

un (J = { (l , 2) . (l ,3), (2 ,3)} es una relacin asimtrica en A.

3.7.7. Transitividad

R es transitiva" V x V y V z: (x e R 1\ (y, z) e R =;> (x , z) R Es decir, si un elemento est relacionado con otro (no necesariamente distinto), y

Sfe est relacionado con un tercero, entonces el primero est relacionado con el tercero.

3.7.8. No transitividad

Por ser la negacin de la transitividad. decimos

Resnotransitiva *3x3Y3z/(x.y)eR 1\ (y,z)eR 1\ (x,z)I/R 3.7.9. Atransitividad --

Resatransitiva" VxVyVz:(x.y)eR /1. (y,z}eR =;>(x,z)iR Ejemplo 3-7.

Considerando el mismo conjunto A de los ejemplos 35 y 3-6 se tiene: i ) R Y U son transitivas.

1 ,

'1

I ~ ~ i

PROPIl IJADES DE LAS RELAClONFS

ii) V=., { (1 ,2) , (2 ,3) ,(1 ,3) ,(3, 1) } 'es no transitiva, ya que (1 ,3) e V 1\ (3, 1) V (1, 1 H V

ti) JI! = { (1 ,2) , (2,3)} es atransitiva, ya que (1,2)eW 1\ (2,3)eW:;.(1,3),e'W,

3.7.10. Antisimetra Resantisimtrica *>VxVy:(x.y),R A (v.x)R =;>x=y

75

Eu c~itZ "'d:)O, s~ d0S pares de ~o&1pcnc~tes pe~u.tad:!~ perten~r.e~ 3 h~ re1a(in entonces dichas componentes se identifican.

De este modo, ia relacin R del ejemplo 3-5 es antisimtrica, pero no lo es S puesto que es f la proposicin

a - b e Z /'. b - e e Z =;> ,,*(a':-b)+(b-c)EZ :!JoQ-ceZ ,,*(a.c)eR

iv) R no es antisimtrica. pues (3.2)eR l\ (2:3)eR=>2=3esF

v ) Grfico de R. A R pertenecen los pares de reales (x. y) tales que x - y Z

Ahora bien

x - y e Z =;> x - y = klk e Z "* j' = x - k con kel

www.

Matem

atica

1.com

~"

,6 RELACIONES

rara cad, entero k se tiene una recta paralela a la primera bisectriz.

/

1/ ) .. A /'""'v y" 'l- ?' 'l- ?'\:) //~?, .... -. - / / //'l- ~I/" ///,,/

// /

x

La relacln consiste en todos los pares (x , y) R2 pertenecientes a la familia de rectas, es decir:

R = U {(x, y) R2 I y = x - k } keZ' _ Ejemplo J.1.

Sea A Uf conjunto. Como el vacio es parte de cualquier otro, la proposicin p e A2 es verdaderl y, en consecuencia, 1/1 es una relacin en A. Tal relacin verifica las propiedades:

i ) Arreflexividad. La proposicin V t' _ x t f\ ""'" C~ _ .tI ,!J

es verdadera, ya que el consecuente de la implicacin es V_ ii ) SI1etra. Se verifica por ser V la proposicin

v x V y : (x y) 1/1 =- (y ,x) e p iii) Tlansitividad

(x,y)efJ A (y,z)el/1 =(x,z)el/1 es V porque el antecedente es F.

t 1

RELACIONES DE EQUIV ALFNCIA n

.iv) Como la implicadn (x,y)eq, A (y,z)eq, =>x==y

es verdadera por tener el antecedente falso, la relacin es antisimtrica. Es decir, la relacin vaca definida en un conjunto, es arreflexiva, simtrica,

transitiva, y antisirntrca. Si A ==

7f; RELACIONES

e$ de equivalencia. Clasificamos las siguientes proposiciones:

1 -1 V 1 ""2 V 2 -2 V 2 -1 V 3 -3 V 1 -3 F

3 -1 F 2 -3 F 3 -2 F

En virtud de las tres primeras queda asegurada la reflexividad. En cuanto a la simetra es suficiente ver que

1 -2 => 2 -1 es V

Ms aun. si el antecedente es falso la implicacin es verdadera

1-3 => 3-1

Para la transitividad, descartando los casos de a.'1.tecedente falso, es suficiente verificar:

1 -1 1\ 1 -2 => 1 -2 V 1 -2 1\ 2 -1 => 1-1 V 2-1 11 1-2 => 2-2 V 1 --1 1\ i -1 => 1 -1 V

El diagrama de Venn es

~Q, 03

donde cada arco orientado est asociado a un par perteneciente a la relacin. En farola ... anesiana:

;;;:::::----~--_.~

I

"'

CLASES 1>1" J (.)UIVALENCIA 7'J

3 J r 1.1 \-.

211 re '1

2 3

3.8.2. Oases de equivalencia y conjunto cociente Sea - una relacin de equivalencia en A * rp. Un problema de inters es la

detenninacin de todos los elementos de A qde son equivalentes a uno dado, es decir. que forman pareja con l. La respuesta conduce en cada caso a un subconjunto de A. llamado clase de equivalencia de! elemento"

Definicin Clase de equivalencia del elemento a e A es el conjunto de todos los elemerltos de A equivalentes a a.

Ka={ xeA/x-a} ('on relacin al ejemplo 3-10:

K = { 1 . 2 } = K: K3 = { 3 }

Es decir, hay dos clases de equivalencia, que son subconjuntos de A.

KI

www.

Matem

atica

1.com

f:O RELACIONES

Podemos avanzar un poco ms y preguntamos por el conjunto cuyos elementos' son las clases de :quivalenca: K 1 y K s,

Para demtarlo, podemos elegir un nico elemento en cada clase de equivalencia, digamos 1 y 3, con lo que queda caracterizado un conjunto de ndices 1 = { 1 3) , de modo tal que a cada elemento de ste le est asociada una clase de equivalencia. El conjunto fornado por las clases de equivalencia se llama conjunto cociente de A por la relacin de e~uivalencia, y la notacin es

~ = {K ,K3 } o bien, media1te el conjllnto de ndices

A, '1 -=) K Uf!'

...... t, lA ~ . f Las clases de equivalencia constituyen una particin de A, en el sentido siguiente:

son no vacas, disjuntas de a pares, y su unin es A. Este concepto ser precisado en los prrafos siguEntes, y es un hecho comn a toda relacin de equivalencia definida en un conjunto ro vacio.

Ejemplo ]li En el conJmto Z de los enteros introducmos la relacn de congruencia mdulo n.

mediante la s~uiente

Definicin Dos enros son congruentes mdulo n, si y slo si n es divisor de su diferencia.

En smboIcs a y b son congruentes mdulo n ~ nI 0- b

Adelantnd.mos al hecho de que la congruencia es una relacin de equivalencia podemos escritir

a -b n I a - b (1)

Por defmicin, el nmero natural n es diVisor del entero x si y slo si ste e s igual :.11 primero por unentero, es decir

nlx -3 keZ/x=n.k Especificami)s las siguientes propiedades de a relacin de diVisor" que utilizaremos:

) SI un nmero divide a un entero, divide al producto de ste por cualquier enterco

nlx =:>nlx.y

En efecto, por definicin de divisor

n,x =:>x= n.k =:>x.y=(n.k).y =:>x,y=n.(k.y) =:> =:>n x,y

I I 1

CONJUNTO COCIENTE

i