42 Matematica discreta y sus aplicacioncs

FOR1VfALIZACION DE SENTENCIAS EN EXPRESIONES LOGICAS

En la Seccion 1.3 vimos como se podfan utilizar los cuantificadores para formalizer frases en expresiones logicas, Sin embargo, evitamos sentencias cuya forrnalizacion requiriese el usa de cuantificadores anidados, Nos ocuparnos ahara de estas sentencias.

EJEMPLO 5 Expresa la sentencia «Si una persona es del sexo femenino y tiene un hijo, esta persona es Ia madrede alguien» COIllO una expresion 16gica que involucre predicados, cuantificadores -euyo do-

minio es eJ conjunto de todas las personas- y conectivos logicos, i

Solucion: La frase anterior se puccle expresar como «Para toda persona x, si Ia persona x es del sexo femenino y la persona .t tiene un hijo, entonces existe una persona y tal que la persona x es madre de la persona y». Introducimos los predicados F(x) para representar «x es del sexo femenino», P(x) para representar «z tiene un hijo» y M(x, y) para representar <<X es madre de y». La Erase original se puede expresar como

'ifx «F(x) 1\ P(x» -t 3y M(x, y).

Podernos desp1azar 3y hacia Ja izquierda, puesto que y no aparece en F(x) 1\ P(x), para obtener una expresion equivalcnte

'itx3y «F(x) AP(X» -t M(x, y».

EJEMPLO 6 Expresa la sentencia «Cada persona tiene exactarnente un amigo preferido» como una expresion logics que involucre predicados, cuantificadores -euyo dominio es el conjunto de todas las personas- y conectivos logicos.

Solucion: La Frase anterior se puede expresar como «Para cada persona x, la persona x tiene exactamente un amigo preferido». Introduciendo el cuantificador universal, se ve que la sentencia es la misrna que <<.'itx (la persona x tiene exactarnente ill) amigo preferido)», donde el dominio consiste en toda la gente.

Dccir que x tiene exactarnente un amigo preferido significa que hay una persona y que es eJ rnejor amigo de x, y ademas, que para toda persona z, si z no es la persona y, entonces z no es el mejor amigo de x. Cuando introducirnos eJ predicado B(x, y) COIllO «yes el mejor amigo de X», la sentencia que afirma que x tiene exactamente un amigo preferido se puede representar como

3y (B(x, y) 1\ 'itz «: :I- y) ~> -,B(x, z))).

Consecuentemente, nuestra sentencia original se puede expresar como

'ifx3y (B(x, y) 1\ 'itz «z :I- y) -t ,B(x, z))).

(Ten en cuenta que podemos escribir esta sentencia cornu 'lix3!y B(x, y), donde 3! es el «cuantiIicador de unicidad» definido en el Problema 48 de La Seccion 1.3. De cualquier forma, el «cuantificador de unicidad» no es realmente lin cuantificador; mas bien es un recurso para expresar ciertas sentencias que se pueden expresar usando los cuantificadores 'it y 3. EI. «cuantificador de unicidad. 3! se puede considerar una macro). ....

EJEMPLO 7 Emplea cuantificadores para expresar la sentencia «Hay una mujer que ha viajado en un vuelo en cada una de Las line as aereas del mundo»,

Solucion: Sea P(w,j) «w ha viajado en f» y Q(f, 0) «fes un vuelo de la linea aerea a», Podernos expresar Ia sentencia como

3w'ita3f(P(w,j) /\ Q(f, a)),

donde los dominies para w,fy a consisten en toclas las mujeres del rnundo, todos los vuelos y \0- das las lineas aereas, respectivamente.

EJEMPLO 8

.• f. -t

,.,~ 2~ "1)l:LSQ;(' . ~

I a(lte"on31R~;' ~

,'," "," .. , ':'"_ ......

EJEMPLO 9

- :~

, I).'jemplps.' J

L·_' ~didarla,~" .

. ,_

Los fundamentos: 16gica y demostraci6n, conjuntos y funciones 43

La sentencia se podria haber exprcsado tambien como 3wVa3fR(w,f, a),

donde Riw.], a) es «w ha viajado en el vuelo f de la linea aerea zr». Aunqne esta expresi6n es mas compacta, oscurece un tanto las relaciones entre las variables, Par ella, la primera solucion puede ser preferible, ....

Las sentencias matematicas expresadas en lenguaje natural se pueden formalizar en expre~ siones 16gicas, como rnuestran los Ejemplos 8~ I O.

Formaliza la afinnacion «La suma de dos enteros positives es positiva» en una expresion logica

Solucion: Para formalizar la afirmacion, primero la reescribirnos para evidential' los cuantificadores implicados: «Para cada dos enteros positives, la suma de estos enteros es positiva», Luego introducirnos las variables x e y para obtener «Para todos los enteros positivos x e y, x + y es positivo». Par consiguiente, podemos expresar esta afirmacion como

't/xVy ((:r> 0) 1\ (y > 0) --7 (x + Y > 0)),

donde el dominic para am bas variables consiste en todos los enteros.

Formaliza Ia afirmacion «Todo ruimero real, excepto el cera, tiene UD inverse para el producto».

Solucion: Primero reescribirnos la frase como «Para todo nrimero real x, excepto el cero, x tiene lin inverso para el producto», Esta sentencia se puede reescribir de nuevo como «Para todo mimero real x, si x*- 0, entonces existe lin mimero real y tal que xy =: 1». Esto se puede expresar como

Vx ((x 7:- 0) -13)' (x)' = 1»).

EJEMPLO 10 (Se requicre Calculo) Enuncia Ia definicion de limite usando cuantificadores.

Un ejemplo que te puede resultar familiar es el concepto de limite, que es importante en Calculo,

Solucion: Recordamos que la sentencia

lim/ex) =L

X-ta

significa que para todo ruirnero real £ > 0, existe un rnimero real 8> ° tal que Il(x) - L 1 < £ siernpre que 0 < 1 x - a 1 < 8. Esta definicion de limite se puede escribir en terminos de cuantificadores como

VE38Vx(0 < Ix- 01 < 8 --7ll(x) -LI < E),

donde el dominio para las variables 0 y e consiste en todos los reales positives y para x consiste en todos los reales.

Esta definicion tambien se puede expresar como

V£ > 0 38 > 0 't/x (0 < 1,,1'- al < 8 --t If(x)- LI < E),

donde el dominio para las variables e y 8 consiste en todos los numeros reales en vez de s610 los reales positives. ...

NEGACION DE CUANTIFICADORES ANIDADOS

Las sentencias con varios cuantificadores anidados se pueden negar aplicando sucesivamente las reglas de negacion de las senrencias que contienen lin unico cuantificador. Esto se ilustra en los Ejemplos 11 ~ 13.

44 Matematica discreta y sus aplicaciones

EJEMPLO 11 Expresa la negacion deja sentencia 'iix3y (xy == I) de tal forma que ninguna negacion preceda al C uanti ficador.

Ej~pJ~: ..•

, .a,Jici"on'lllcs Solucion: Aplicando sucesivarnente las reglas para negar sentencias cuantificadas dadas en la Ta-

bla 2 de la Seccion ] .3, podernos mover la negacion en -, 'iix3y Cry = 1) dentro de todos los cuantificadores. Encontramos que -'\iix3y (xy = 1) es equivalente a 3.t .. 3y (ry = I), que es equivalente a 3x'iiy -,(xy == 1). Como ..-,(,ry = 1) se puede expresar mas sirnplernente como xy * 1, concluirnos que nuestra sentencia neg ada se puede expresar como 3xVy (xy F 1). ..

EJEMPLO 12 Usa cuantificadores para expresar la sentencia «No existe ninguna mujer que haya viajado en un vuelo de cada una de las llneas aereas del rnundo»,

Solucion: La afirmacion anterior es la negaci6n de la sentencia «Hay una mujer que ha viajado en un vueio de cada linea aerea del rnundo» del Ejemplo 7, Por el Ejemplo 7, nuestra sentencia se puede expresar como --,3wVa3/(P(w,j) A (Q(j, a», donde pew,/) es «w ha viajado ess f» y Q(f, a) es <f es un vuelo de la linea aerea a», Aplicando sucesivarnente las reglas de la negacion de sentencias cuantificadas de la Tabla 2 de la Secci6n 1.3 para desplazar la negaeion dentro de cada euantificador y aplicando las leyes de De Morgan en el ultimo paso, encontramos gue nucsrra sentencia es equivalents a cada una de las de Ja siguiente secuencia:

Vv.r-,'<ia3/(P{w,J) A Q(f, a) == Vw3a-.3f(P(w,j) A Q(f, a») == 'iiw3aVf-.(P{w,j) A Q(f, a»

== Vw3aVf (,P(w,j) v --.Qif, a».

Esta ultima sentencia afirma que «Para toda rnujer hay una linea aerea tal que, para todo vuelo, esta mujer no ha viajado en ese vuelo 0 ese vuelo no es de esa linea aerea». ...

EJEMPLO 13 Utiliza cuantificadores y predicados para expresar el hecho de que ellfrn.r_><, f(x) no existe.

Solucion: Decir que el [imx a f(x) no existe significa que para todos los numeros reales L,lfm'_H

I(x) 1:- L. Usando el Ejemplo 1O.1a sentencia Jim, _, a fix) * L se puede expresar como

-Nt> 0 3D> 0 Vx (0 < Ix-al < D.....:;. U(x)-LI< E).

Aplicando sucesivamente las reglas de la negacion de expresiones cuantificadas, construirnos esta secuencia de sentencias equivalentes

-,VE> 0 3(» 0 Vx(O < Ix- al < 8 .....:;.If(x) -LI< e)

== 3E > 0.38> a 'iix(O < Ix- al < 0 .....:;.If(x)-L 1< e) :::::: 3£> 0 Vo > 0 -.Vx(O < Ix-al < 0 .....:;.If(x) -LI < E) == 3£ > 0 VO > 0 3x .(0 < Ix - al < 8 .....:;.If(x) - L 1<£) :::::: 3£> avo> 03_\:"(0 < Ix- al < 0 A IICx)-LI ~ E).

!

Usarnos la equivalencia .(p .....:;. q) == P A =q en eI ultimo paso.

Debido a que let sentencia Jim, ... a f(x) no existe, significa que.para todos los mimeros reales L, lfmr-> o f(x) i:- L, la sentencia se puede expresar como

'iiL3£> 0 'iio >O:lx (0 < Ix- 01 < 0 A I/(x)- LI;:: f).

Esta ultima sentencia afirma que para cad a niimero real L hay un rnimero real E > 0 tal que para todo numero real 0> 0 existe un mimero real x tal que 0 < I x - 0 I < 8 y I I(x) - L I ~ E. ....

EL ORDEN DE LOS CUANrrIFICADORES

" Ejcmplos a,iidiin'lf~

o

Muchas sentencias matematicas usan cuantificaciones multiples de funciones proposicionales

COD mas de una variable. Es fundamental tener en cuenta que el orden de los cuantificadores es importarue, a no ser que todos los cuantificadores sean universales 0 existenciales, Este heche se ilus-

Los fundamentos: logica y demostracion, conjuntos y funciones 45

tra en los Ejemplos 14-16. En cada uno de esros ejernplos el dorninio de las variables consiste en todos los numeros reales,

EJEMPLO 14 Sea P(x, y) Ja senlencia «r + y = y + z». l,CuaJ es el valor de verdad de In cuantificacion Vx\/y P(x, y)?

Solucion: La cuantificaci6n

Vx\/y P(x, y)

denota la proposicion

«Para todo mirnero real x y todo mimcro real y, x + y = y + x».

Como P(x, y) es verdadera para todos los rnimeros reales x e y, la proposicion \/x\/y P(x, y) es verdadera, ....

EJElVIPLO 15 Sea Q(x, y) la sentencia «x + y = 0:». (emil es cl valor de verdad de las cuantificaciones 3yVx Q(x, y) y Vx3y Q(x, y)?

Solucion: La cuantificacion

3yVx Q(x, y)

denora la proposici6n

«Hay un mimero real y tal que para todo mimero real x, Q(x,y)>>.

Para cada y elegido, hay un tinico valor de .r para el cual x + y = O. Como no hay un nrimero real y tal que x + y = 0 para todos los mimcros reales x, la sentencia 3yVx Q(x, y) cs falsa,

La cuantificacion

'v'x3y Q(x, y)

denota la proposicion

«Para todo mimcro real x hay un numero real)' tal que Q(x, y)).

Dado un nurnero real x, se puede hallar un mimero real y tal que x + )' = 0; a saber, y = - .r, Par tanto, la sentencia \/x3y Q(x, y) es verdadera. ....

El Ejemplo IS ilustra que el orden en que aparecen los cuantificadores es importantc, Las sentencias 3y\/x P(x, y) y \/x3y P(x, y) no son logicamente equivalentes. La sentencia 3yVx P(x, y) es verdadera si, y solo si, hay un y que haee P(x, y) verdadera para rodo x. Par tanto, para que csta sentencia sea verdadera, debe haber un valor particular de}' para el cual P(x, y) es verdadera, sin importar el valor que se el ija de x. Por otra parte, 'v'x3y P(x, y) es verdadera, si, y solo si, para todo valor de .r hay un valor de y para el cual P(x, y) es verdadera. Par tanto, para que esta sentencia sea verdadera, no importa la eleccion de .r, debe haber un valor de Y (posiblernente dependiente del valor que se escoja para x) para cl eual Pix, y) es verdadera. En arras palabras, en el segundo caso )' puede de pender de x, micntras que en el primer caso y es una constante independiente de x.

De estas observaciones se sigue que si 3yVx P(x, y) es verdadera, entonces Vx3y Pix; y) debe ser tambien verdadera. Sin embargo, si 'v'x3y P(x, y) es verdadera, no es necesario que 3ylix Pix, y) sea tarnbien verdadera. (Vean e los Problemas complementarios 14 y 16 al final del capitulo).

PENSANOO EN LOS CUANTlFICADORES COMO B CLES Al trabajar can cuantificadores de mas de una variable es util a veces pensar en terminos de bucles anidados, (Por supuesto, si hay un mimero infinite de elementos en el dominio de alguna variable. no podemo cerrar un bucle para todos los valorcs. A pesar de ello, esta forma de pensar sigue siendo util). Par ejemplo, para ver si \/x\/y Ptx, y) es verdadera, recorrernos en un bucle todas las variables x, y para eada x rccorrernos en un segundo bucle todos valores de y. Si encontramos que P(x, y) es verdadera para todos los valores de x e y, hemos dererrninado que Vx\/y P(x, y) es verdadera. Si, por el contrario, encontrarnos algrin valor de x para el cual hay L1n valor de y tal que P(x, y) resulta ser falsa, hemos dernostrado que Vx\/y P(x, y) es falsu.

46 M'atematica discreta y sus aplicaciones

Tabla 1. Cuantificadores de dos variables.
Seniencia i,Cudndo es verdadera? ",-Cu6ndo es fa/sa?
Vx'Vy P(x, y) PCx, y) es verdadera para todo par x, y Hay lID par X; y para el cual P(x, y)
'dy"lx P(.x, y) es falsa
'Vx3y P(-..:, y) PaJ<~ todo x hay un y para el cual P(x, y) Hay un x tal que P(x, y) es falsa para
es verdadera para todo y
3x'dy P(x, y) Hay un x para el cual Pix, y) es Para todo x hay lin y para el cual
verdadera para todo y P(x, y) es falsa
3x3y P(x, y) Hay un par .r, y para el cual P(x, y) P(x, y) es falsa para todo par x, y
3y3x P(x,y) es verdadera De forma similar, para determinar si \1x3y P(x, y) es verdadera, recorremos en un bucle todos los valores de x. Para cada x, recorremos en un bucle los valores de y hasta que encontramos un y para el cual P(x, y) es verdadera. Si para todos los x encontrarnos tal valor de y, entonces \1x3y P(x, y) es verdadera; si para algun x no encontramos un valor de y con esa propiedad, entonces 'Ii x3y P(x, y) es falsa.

Para ver si 3xi;f y P(x, y) es verdadera, recorrernos los val ores de x en un bucle hasta que encon tram os un x para el cnal P(x, y) es siernpre verdadera cuando recorremos en W1 bucle todos los valores de y. Una vez encontrado tal valor de x, sabemos que 3xi;fy Ptx, y) es verdadera. Si no encontramos nunca un x como ese, entonces sabremos que 3xVy P(x, y) es falsa,

Finalmente, para saber si 3x3y P(x, y) es verdadera, recorremos en lin bucle los valores de .r, y para cada valor de x recorremos los val ores de y hasta que encontremos un x para el cual haya un y que verifique que P(x, y) sea verdadera.

La Tabla 1 resume los significados de las diferentes cuantificaciones posibles con dos variables.

Tarnbien son comunes las cuantificaciones de mas de des variables, como ilustra el Ejernplo 16.

EJEMPLO 16 Sea Q(x, y, z) la sentencia <'<X + Y = z». l,Cuules son los valores de verdad de las sentencias i;fx'liy.3z Q(x, v. z) y 3z\tx'liy Q(x, v. z)?

Solucion: Supongamos que asignamos valores a x e y. Entonees, existe un nurnero real z tal que x + y = z. Por consiguiente, la cuanrificacion

'lixVy3z Q(x, y, z)

que es la senteneia

«Para todos los ruimeros reales .r e y hay lin ruirnero real z tal que x + y = z», es verdadera. EI orden de la cuantificacion aqui importa, ya que

3z'lixi;fy Q(x, y, z),

cs la sentencia

«Hay un ruimero real z tal que para todos los mimeros reales x e y se cumple que x + y = Z»,

1a cual es falsa, ya que ningiin valor de z satisface 1a ecuaci6n x + y = z para todos los valores de xey. ....

Los fundarneruos: 16gica y dernosrrncion, conjuntos y funciones 47

Problemas

1. Traduce estas sentencias a lenguaje natural, donde el dominie para tcdas las variables es el conjunto de los numeros reales,

a) Vody (x < y)

b) VxVy «(x 20) 1\ (y;::' 0)) -t ex)';::' 0))

c) V xVy3z (J.}1 = z)

2. Traduce estas seniencias a lenguaje natural, donde eJ dominio para Ladas las variables es el conjunto de los mirneros reales.

a) 3xVy (X)' = y)

b) 'rIxVy «ex;::' 0) 1\ (y < 0» _..." (x - y > 0)) e) VxVy3z (x = y + z)

3. Sea Q(x, y) la sentencia «z ha enviado un correo electronico a y», donde el dominic tanto para x como para y consiste en todos los estudiantes de tu clase. Expresa cada una de estas cuantificaciones en lenguaje natural.

a) 3x3y Q(x, y) b) ::3xVy Q(x, y)

c) Vx3y Q(x y) d) 3yVx Q(x, y)

e) 'rIy3x Q(x, y) n 'rIxVy Q(x, y)

4. Sea P(x, y) la sentencia «el estudiante x esta matriculado en la asignatura y», donde el dominic para x son los estudianres de tu clase y el de y consiste en todas las asignaturas de ingenieria informatica. Expresa cada una de estas cuantificaciones en lenguaje natural.

a) 3x3y P(x, y) b) ::3xVy P(x, y)

c) 'rI.dy P(x, y) d) ::lylix P(x, y)

e) 'rIy3x P(x, y) n 'rIxVy P(x, y)

S. Supongamos que mediante la sentencia !V(x, y) queremas expresar que el estudiante x ha visitado la pagina web y. don de el dominic para x eonsiste en todo: los estudiantes de tu Iacultad y para y consiste en todas las paginas web. Expresa cada una de estas cuantificaciones en lenguaje natural.

a) W(Sarah Sm i th, www.att.corn )

b) 3x W(x, www.imdb.org)

c) 3y WOose Orez, y)

d) 3y (W(Ashok Puri, y) 1\ W(Cindy Yoon, y)

e) 3yVz 6' *- (David Belcher) 1\ (W(David Belcher, z) _..." W(y, z»)

f) 3x3yVz «x", y) 1\ ell/ex, z) H W(y, 1)))

6. Supongarnos que mediante Ia sentencia C(x, y) queremos expresar que eJ cstudiante x se ha matriculado en la asignatura y, donde el dorninio para x consiste en todos los estudiantes de tu facultad y para y consiste en todas las asignaturas irnpartidas en ingenieria informatica. Expresa cada una de estas cuantificaciones en lenguaje natural.

ad C(Randy Goldberg, CC 252)

b) 3x C(x, Mate 695)

c) 3y C(Carol Sitea, y)

d) 3x (C(x, Mate 222) 1\ C(x, CC 252)

e) 3x::3y'rlz «x '* y) 1\ (e(x, z) _..." c(v, z») I) 3x3y'rlz «x '* y) 1\ (e(x, z) H C(y, z)))

7. Supongamos que mediante la sentencia T(x, y) queremos expresar que al estudiante x Ie gusta la cocina del pais y, donde el dominic para x consiste en todos los estudiantes de tu faeultad y pam y consiste en todos los paises con cultura culinaria propia, Expresa cada una de estas cuantificaciones en lenguaje natural.

a) ,T(Abdallah Hussein, japonesa)

b) 3x T(y, coreana) 1\ 'rIx Ttx, mexicana)

c) 3y (T(Monique Arsenault, y) v T(Jay Johnson, y»

d) VxVz3y (Col '* z) _..." ,(T(x, yl 1\ T(z, y))

e) 3x3z'rly (T(x, Y) H ti». y»

f) 'rIxliz3y (T(x, y) H T(z, y»

8. Sea Q(x, y) Ja sentencia «el estudiante x ha participado en el concurso y». Expresa cadu una de est as sentencias en terminos de Q(x, y), cuantificadores y conectivos l6gicos, donde el dominic para x consiste en todos los estudiantes de tu faculrad y para y consiste en todos .los concursos de television.

a) Hay un estudiante en ttl faculrad que ha participado en un concurso de television.

b) Ningun estudiante de tu facultad ha participado nunca en un concurso de television.

c) Hay un estudiante en tu Iacultad que ha participado en los concursos ,,50 x 15» y «Pasa Palabra»,

d) Cada concurso de television ha tenido un estudiante de tu facultad como participanre.

e) Al menos dos estudianres de tu facultad han participado en el concurso de television «50 x l S»,

9. Sea L(x, y) la sentencia «r quiere a y», donde el dominic tanto para x como pam y consiste en todas las personas del mundo. Usa cuantificadores para expresar cada una de las siguientes sentencias.

a) Todo eJ mundo quiere a Jaime.

b) Todo el mundo quiere a alguien,

c) Hay alguien a quien todo el rnundo quiere.

d) Nadie quiere a todo el mundo,

.e) Hay alguien a quien Lidia no quiere.

n Hay alguien a quien no le qu iere nadie,

g) Hay exactamente una persona a quien todo el mun-

do quiere,

h) Hay exactarnente dos personas a quienes Lidia quiere.

i) Todo eJ mundo se quiere a sf rnisrno.

j) Hay alguien que no quiere a los que estan a su lado.

10. Sea Ftx, y) la sentencia «r puede engaiiar a Y»), donde el dominic tanto para x como para y consiste en todas las personas del mundo. Uriliza cuanuficadores para expresar cada una de las siguientes scntencias.

a) Todo eJ mundo puede engafiar a Fred.

b) Evelyn puede engafiar a todo el mundo.

48 Matematica discrcta Y SLIS aplicaciones

c) Todo cl rnundo puede engafiar a alguien,

d) 0 hay nadie que pueda enganar a to do el rnundo.

e) Todo el rnundo puede ser engailado por alguien,

f) Nadie pucde engafiar a Fred y a Jerry (a los dos).

g) Nancy puede engafiar a exactamente dos personas.

h) Hay exactamente una persona a quien todo el nnwdo puede engariar.

i) j adie puede enganarse a sf misrno,

j) Hay alguien que puede engaiiar a exactamente una de Las personas que estan a su lado.

11. Sea Sex) el predicado «x cs un estudiante», F(x) el predicado <<.X es un profesor- y A(x, y) el predicado «r ha hecho una pregunta a)'», donde el dominio consiste en todas las personas de tu facultad, Usa cuanrificadores para expresar cada una de las siguientes sentencias.

a) Luis ha hecho una prcgunta al profesor Michaels.

b) Todos los estudiantes Ie han hecho una pregunta a1 profesor Gross.

e) Todos los profesores bien han hecho una pregurna al profcsor Miller 0 bien han sido preguntados por el profcsor Miller.

d) Algjin estudiante no ha heche una pregunta a ninguno de los profesores.

e) Hay un profesor al que ningun estudiante ha heche nuncu una pregunra.

f) Algun esrudiante ha hecho una pregunta a cada uno de los profesores,

g) Hay un profcsor que ha heche una pregunra a cada uno de los otros profesores.

h) Algtin estudiame no ha sido preguntado nunca por un profcsor.

U. Sea J(x) la scntencia «.X uene conexion a Internet» y C(x, y) la sentencia «r e y han chateado en Internet», donde el dominie de las variables x e y consisre en todos los estudianres de tu clase. Utiliza cuantificadorcs para expresar cada una de las siguientes sentencias.

a) Jaime no tiene conexion a Internet.

b) Raquel no ha chateado en Internet con Chelsea.

c) Jan y Sharon nunca han chateado en Internet.

d) adie de la clasc ha chateado con Bob.

e) Susana ha chateado can Lodos excepto con Bob. t) Aleuien de III fase no tiene conexion a Internet.

g) No todos los d 1lI clase ticnen concxion a Internet.

h) Exactaruente n estudiante de tu clase uene conexion a internet.

i) Todos excepto un estudiante de ttl clase tienen GOnexi6n a Internet.

j) Todos los cstudianre de tu clase que tienen conexion a Internet hall chateado al menos con otro estudi ante de III c lase.

k) Alguien en ru clase tiene conexion a Internet, pero no ha chateado can ningiin otro estudiante,

I) Hay dos cstudiantes en tu clase que no l~n chateaclo entre elias er] rnternel.

Ill) Hay lin estudiante en tu c1ase que ha chateado con cada uno de los esrucliantes cle lu clase.

n) Hay al menos dos estudiantes de tu clase que no han chateado con la rnisrna persona de ttl clase.

0) Hay dos estudiantes de tu clase que entre ambos han chateado con todos los estud iantes de Ia clase.

13. Sea M(x, y) «r ha enviado a y mensajes por cone a electronico. y T(x, y) «r ha telefoneado a p, donde el dominio consiste en todos los estudiantes de lu clase, Usa cuantificadores para expresar cada una de las siguientcs sentencias. (Supan que iodo: los mensajes enviados fueron rccibidos ... , que no es 10 que siempre sucede).

a) Carmen nunca ha enviado lIJ1 rncnsaje par correo electronico a Kika.

b) Arlene nunca ha enviado un rnensaje par correo electronico a telefoncado a Sara.

c) Jose nunca ha recibido un mensaje par correo electronico de Debora.

d) Todos los estudiantes de tu clase han enviado un mensaje por correo elecuonico a Ken.

e) Nadie de tu clase ha telefoneado a Nina.

f) Todo el mundo en tu clase ha telefoneado a Avi 0 Ie ha enviado un mensaje por correo electronico.

g) Hay un cstudiante en to clase que ha enviado a cada uno de los dernas un mensaje por correo electronico,

h) Hay un estudiante en tu clase que ha enviado un rnensaje por correo clectronico 0 ha telefoneado a cada uno de los demas.

i) Hay dos estudiantes en tu clase que se han cnviado rnutuamente un mensaje por correo elecrronico,

j) Hay un estudiante que se ha enviado a sf rnisrno un mensaje par correo elecironico.

k) Hay lin estudiante en tu clast que no ha recibido un mensaje por correo electronico de ningun otro estudiante de Ja clase ni tampoco ha sido telcfoneado par otro estudiante,

l) Todos los estudiantes de la clase bien han recibido un mensaje por corrco electronico de otro estudiante de la clase 0 bien han sido telefoneadus par otro estudiante de la clase.

m) Hay al menos dos estudiantes en tu c1ase tales que uno ha enviado al otro un rnensaje pm correo electronico y el segundo ha relefoneado al primero.

n) Hay dos estudiantes en tu clase que entre ambos bien han cnviado LIn rncnsaje por correo electronico o bien han telefoneado a cada uno de los demas miembros de Ia clase.

14. Utiliza cuantificadores y predicados con mas de una variable para expresar las siguientes afirrnaciones,

a) Hay un estudiante en esta clase que habla hindu t,

b) Todo estudianie de esra clase practica algun deporte.

e) Algtin estudiantc de esta clase ha visitado Alaska, pero no ha visitado Mexico.

d) Todos los esrudiantes de esta clase han aprendido al menos un lenguaje de programacion,

e) Hay llll eSUldiante de csta clase que se ha matriculudo en todas las asignaluras que afrece uno de los departamentos de I,U facll.ltad.

f) Algun estudiante de esta clase es de la misma ciudad que exactamente orro estudiante de la clase.

g) Todo estudiantc de la clase ha chateado con al menos otro estudiante en al rnenos un grupo de chat.

L5. Usa cuarui licadores y predicados con mas de una valiable para expresar las siguientes afirrnaciones -,

a) Todo cstudiante de ingeniena informatica necesita un curse de matemarica discrete.

b) Hay un esrudiante en esta clase que tiene un ordenador pcr .onal.

c) Todo estudianle de esta clase ha cursado al menos una asignatura de ciencias de la cornputacion.

d) Hay un esnrdiante en esta clase que ha cursado al menos una asignarura de ciencias de la computaci6n.

e) Todo estudiante de esia clase ha estado en todos los edificios del campus.

f) Hay un estudiante en esta clase que 1M estado en todas las habitaciones de al menus un edificio del campus.

g) Todo estudiante de esta clase ha estado al mcnos en una habitaci6n de cada edificio del campus.

16. En un aula se reunen los siguientes estudiantes: un estudianre de maternaticas de primer curso, 12 esrudiantes de rnaternaticas de segundo curso, 15 esrudianies de ingenicrfa informatica de segundo curse, 2 esiudiantes de marernaricas de tercer curso, 2 estudianies de ciencias de la computaci6n de tercer curse y un estudiante de ciencias de la cornputacion de cuarto curse, Express cada una de estas sentencias en terrninos de cuantificadores y determina su valor de verdad,

a) Hay un esrudiante en el aula que es de tercer curso,

b) Todo estudiante del aula es de ingenieria informatica,

c) Hay un estudiante en el aula que ni es de maternaticas n i es de tercer curse,

d) Todo estudiante en cl aula es bien de segundo curse o estudiante de ingenierfa in formar ica.

e) Hay una titulacion tal que en el aula se encuentra un estudiante de cada aiio de estudio de esa titulacion.

17. Express cada una de las siguientes especificaciones de sistema usando prcdicados, cuantificadores y conccti vos logicos, segiin proceda.

a) Todo usuario tiene exactamente un buzrin de correo,

b) Hay un proceso que continua su ejecucion para todos los casus de error solo si el kernel funciona correctarnente.

c) Todos los usuaries de la red del campus pueden acceder a todas las pagina web cuyas direcciones terminen en .cdu

*d) Hay exacramcnte dos sistemas que moniiorizan todos los servidores remotes.

] 8. Expresa cada una de las siguientes especificac i ones de sistema usando predicados, cuantificadores y conectivos logicos, segiin'proceda.

a) AI menos una consola debe ser accesible durante cada condicion de fallo.

Los fundarnentos: logica y demostracion, conjuntos y funciones 49

b) Se puede obtener la direccion de correo electronico de cada usuario siernpre que In carpeta contenga al rnenos un mensaje enviado por cada usuario del sistema.

c) Para cada violacion de la seguridad hay al rnenos un mecanisme que puede deicctar esta violacion si, y solo si, hay un proceso que no ha sido afectado.

d) Hay al menos des rutas que conectan cada dos terminales de la red.

e) Nadie conoce la clave de acceso de todos los usuarios del sistema, excepto el administrador.

19. Expresa cada una de las siguientes sentencias usando operadores maternaticos y logicos, predicados y cuanrificadores. EJ dominio consisie en todos los enteros,

a) La suma de dos enteros negatives es negativa.

b) La difcrencia de enteros positives no es necesariamente positiva,

c) La surna de los cuadrados de dos enteros es mayor 0 igual que el cuadrado de xu surna,

d) El valor absolute del producto de dos enteros es el producto de sus valores absolutes.

20. Expresa cada una de las siguientes sentencias usando operadores rnatcrnaticos y logicos, predicados y cuantificadores. EI dominio consiste en todos los enteros.

3) El producto de dos enteros negatives es positivo.

b) EI valor medic de dos enteros positives es positive.

c) La diferencia de dos enteros negatives no es necesariamente negativa.

d) El valor absolute de la suma de dos erueros no es mayor que la surna de los valores absolutes de estos enteros.

21. Usa predicados, cuantificadores, conectivos logicos y operadorcs matcmaticos para expresar la sentencia que dice que todo entero positive es la suma de los cuadrados de cuatro enteros:

22. Usa predicados, cuantificadores, conectivos 16gicos y operadores rnatematicos para expresar la scntencia que dice que hay un entero positive que no e la suma de Ires cuadrados.

23. Exprcsa cada una de las siguientes sentencias usando prcdicados, cuantificadorcs y operadores matenuiricos y Iogicos,

a) El producto de dos males negatives es positivo.

b) La diferencia entre un rnirncro real y el mismo es cero.

c) Todo real positive tienc exactarnente dos raices cuadradas,

d) Un real negative no tiene raices reales.

24. Traduce cada una de estas cuantificaciones anidadas a una Frase en lenguaje natural que exprese una afirmacion matematica. EJ dominic en cada caso consiste en todos los mirneros reales.

a) :txV), (x + )' == y)

b) VxVy «(x;::: 0) A (y < 0) -7 (x- Y > 0»)

SO Maternatica discreta y sus aplicaciones

c) ::Jx::Jy «(x ~ 0) 1\ (y"; 0» 1\ (x - Y > 0»

d) VxVy «x *- 0) 1\ (y *- 0» t-7 (x)':;c: 0»

25. Traduce cada una de estas cuantificaciones anidadas a una frase en lenguaje natural que exprese una afirmacion matemarica, El dominic en cada caso consiste en todos los mirueros reales.

a) ::JxVy (xy "" y)

b) VxVy «(x < 0) /\ (y < 0» ~ (X)' > 0»

c) 3x3y «x' > y) /\ (x < y»

d) lix'iy3z (x + Y = z)

26. Sea Q(x, y) la sentencia <<X + Y = x - p. Si el dorninio para ambas variables consiste en todos los enteros, ~cuales son los valores de verdad de las siguientes sentencias?

a) Q(l, 1)

d) 3_1:' Q(x, 2)

g) 3ylix Q(x, y)

h) Vy3x Q(x, y)

i) lixliy Q(.(, y)

b) Q(2,0)

e) 3x3y Q(x, y)

c) liyQ(I,y)

f) lix3y Q(t, y)

27. Determina el valor de verdad de cada una de estas sentencias si el dominic de todas las variables es el conjunto de todos los enteros,

a) 'in3m (n2 < m) b) 3n'im (n < m2)

c) Vn3m (n + m = 0) d) 3n'<fm (nm = m)

e) 3n3m (n2 + m2 = 5) I) 3n3m (/12 + m2 = 6)

g) 3n3m (n + rn = 4 /\ n - m = 1)

11) 3n3m (n +m = 4/\ n=m = 2)

i) Vnlim3p (p = (m + n)!2)

2R. Determina el valor de verdad de cada una de estas sentencias si el dominic de todas las variables es el conjunto de rodos los mimeros males.

a) Vx::Jy (.1,.1 = y) b) lix3y (x = i)

c) 3x'iy(xy=0) d) 3x3y(x+y:;l:y+x)

e) lix (x *- 0 ~ 3y (X)' = 1»

I) ::JxVy (y:;l:O ~;ty = 1)

g) lix3y (x + y =1)

h) 3x3y (x + 2y = 2/\ 21: + 4y = 5)

i) lix3y(x+y=21\2x-y=l)

j) Vxliy3z (z = (x + y)/2)

29. Sup6n que el dominic de la funcion proposicional Ptx, y) consiste en los pares x e YldODde x es 1,203 e y es 1, 2 0 3. E~en b.e estas prop sici ones usando disyunciones y conjunciones.

a) Vxliy P(x, y) b) ::Jx3y P ',Y)

c) ::JxVy P(x, y) d) liy3x P(x, y)

30. Reescribe cada una de las siguientes sentencias de tal fOOTIa que las negaciones aparezcan s610 denrro de los predicados (es decir, de tal forma que ninguna negaci6n este fuera de un cuantificador 0 de una expresion con conectivos logicos).

a) --.3y3xP(x, y) b) -Nx3y P(x, y)

c) --.3y (Qu') /\ lix --.R(x. y»

d) -.::Jy(3xR(x,y)vlixS(x,y»

e) -,3y (Vx3z T(x, y, z) v::Jx'iz U(x, y, z)

31. Expresa la negaci6n de cada una de estas sentencias de tal forma que todos los sfrnbolos de ncgaci6n precedan inrnedlatarnente a predicados.

a) lix::JyVz T(x, y, z)

b) Vx3y P(x, y) v lix3y Q(x, y)

c) Vx3y (P(x, y) /\ 3z R(x, y, z)

d) lix3y (P(x, y) ~ Q(x, y»

32. Expresa las negaciones de cada una de estas sentencias de tal forma que todos los sfmbolos de negaci6n precedan inmcdiatamente a predicados.

a) 3zliyVxT(x, y, z)

b) 3_t3y P(x, y) /\ VxVy Q(x, y)

c) 3x3y (Q(x. y) f-7 Q(Y, x)

d) 'iy3x3z (T(x, y, z) v Q(x, y)

33. Ree cribe cada una de las siguientes sentencias de tal forma que las negaciones aparezcan solo dentro de los predicados (es decir, de tal forma que ninguna negacion este fuera de LIn cuantificador 0 de una expresion con conectivos logicos).

a) -NxVy P(x, y) b) --.Vy3x P(x, y)

c -,VyVx P(x, y) v Q(x, y»

d) ,(3x3y -.P(x, y) 1\ Vxliy Q(x, y»

e) ,'dx(3yliz Pix, y, z) 1\ 3z'dy Ptx, y, Z»

34. Express cada una de estas sentencias utilizando cuantificadores, Posteriormente, forma la negacion de la sentencia de tal forma que ninguna negaci6n este a la izquierda de un cuantificador, Finalrnente, expresa la negaci6n en lenguaje natural. (No te Iimires a usar la exIJre~i611 «No se cumple que ... »),

a) Nadie ha perdido Intis de 1.000 euros jugando a la loteria.

b) Hay un estudiante en estu clase que ha chateado COn exactamente otro estudiante de la clase,

c) Ningtin estudiante de Ia clase ha enviado mensajes de correa electr6nico a exactamente dos esrudiantes de la clase,

d) Algun esrudianre ha resuelto todos los problemas de este libra.

e) Ningiin estudiante ha resuelto al menos un problema de cada seccion de este libro.

35. Express eada una de estas sentencias usando cuantificadores, Posteriormente, forma la negaei6n de la sen- • tcncia de tal forma que ninguna negacion este a Ja izquicrda de un cuantificador. Finalmente, expresa la negacion en lenguaje natural. (No te lirnites a utilizar 1<1 expresion «No se cumple que ... »),

a) Cada esrudiante de esra clasc ha cursado exactarnenre do.'; as ignaturas de marematicas en esta facultad,

b) Alguien ha visitado todos los pafses del mundo, excepto tibia.

e) Nadie ha escalade todas las montafias del Himalaya.

d) Todo actor ha participado en una pelfcula COil Kevin Bacon 0 ha parricipado en una pelfcula con algiin otro actor que ha participado en una pelicula con Kevin Bacon.

36. Expresa las negaciones de estas proposiciones utilizando cuantificadores y en lcnguaje natural.

a) A todos los estudianres de la clase les gustan las maternaticas.

b) Hay un estudiaate en esta clase que nunca 1111 visro un ordenador,

c) Hay un estudiante en esra clase que ha cursado todas las asignaturas de maternaricas de la licenciatura.

d) Hay un estudiante ell esta clase que ha estado en al menos una habitacion de cada cdificio del campus.

37. Encuentra un contraejernplo, si es posible, de estas entencias universalmente cuantificadas, donde el dominio de todas las variables consiste en todos los enteros,

a) 'ri x'd} (x2 = yl _,. x = y)

b) 'riuy (y2 = x) c) Vx'riy (xy ? x)

38. Encuentra un contraejemplo, si es posible, de estas sentencias universalmente cuanrificadas, donde el dominio de todas las variables consiste en todos los enteros.

a) 'Ij.x3y (x == I/y c) 'dx'dY(J;-2;ty3)

b) 'dx3y (y2 -x < 100)

39. Utiliza cuantificadorcs para expresar la propiedad asociativa para el producto de rnirneros reales,

40. U Ii I iza euanrificadores para exprcsar ] a ley di stri buti v a del producto con respecto a la suma de numeros rcales,

41. Deterrnina el vaJor de verdad de la sentencia V'x3y (_\y = 1) si el dominic es

a) los reales no nulos,

b) los enteros no nulos,

c) los reales positives.

42. Dererrnina el valor de verdad de la sentencia 3xliy (x ::; l) si eI dominic es

a) los reales positives,

b) los cnreros,

c) los reales no nulos.

43. Muestra que Ia dos sentencias ·3.,l:V'Y P(x, y) y ',jx3y =Pt», y) tienen el rnismo valor de verdad.

~IUeS[ra que Vx P0:) v 'rix Q(x) y Vx'dy (P(x) v Qly» son gicarnente equivalentes, (La nueva variable y se ernplea ara combiner los cuanrificadores correctamente),

*44.

*45. a) Muestra que 'dx P{x) A 3x Q(x) es equivalcnte a 'iix::ly (P(x) !\ Q(y»).

b) Muestra que 'rix P(x) v 3x Q(x) cs equivalente a 'dx3y (P(x) v Q(v).

Una sernencia csta en forma normal prenex (PNf') si, y solo si, es de la forma

Q,x,Qh··· Qlf(x"x2,L,J),

donde eada Q, i", I, 2, > •• , k, es bien el cuantificador existen-

r

V)S fundamentos: 16gica y dernostracion, conjunros y lurrciones 51

cial 0 el .cuantifieador universal, y PCx1, •••• xk) es un predicado que no involucra ningun cuantificador. Por ejernplo, 3x'dy (P(x, y) /\ Q(y) estri en forma prenex normal, rnientras que 3x P(x) v 'dx Q(x) no (ya que no rodos los cuaruificadores se present an a! principio).

Toda sentencia fonnada can variables proposicionales, predicados y los valores V y F, uti lizando conectivos l6gicos y cuantificadores, cs equivalente a una entencia en forma normal prenex. El problema 47 pide dernostrar cste heche,

*46. Pall estas sentencias en forma normal prencx. tIndicacion:

Usa las equivalencias 16gicas de las Tablas 5 y 6 de la Secci6n 1.2, la Tabla 2 de la Seccion 1.3, los Problemas 42-45 de Ia Secci6n 1.3 y los Problemas 44 y 45 de esta seccion),

a) 3x P(x) v 3x Q(x) v A, donde A es una proposicion que involucra cuanrificadores

b) -o(Vx P(x) v'dx Q(x»

c) 3x P(x) _,. :::lx Q(x)

**47. Muestra como se puede transformer una sentencia arbitraria en una sentencia en forma normal prenex que sea equivalente a la sentencia dada.

48. Un numero real xes cota superior de un conjunto S de mirncros reales si x es mayor 0 igual. que rode mimero de s. El mimero real x se dice que es el supremo de lin conjunto S de numeros reales si x es una cora superior Y x es menor 0 igual que toda cota superior de S. Si estc valor existe, es iinico.

a) Utilizando cuantificadores. expre;;a el hecho de que x es una COI.<1 superior de S.

b) Urilizando cuantificadores, expresa el hecho de que xes el supremo de S.

*49. Expresa la cuantificacion iilr P(x) usando cuantificaciones universales, existenciales y operadores logicos, La seruencia lim"_)~ a" = L significa que para todo ruimero real positive s hay un entero positive N tal que I an - L I < £ siernpre que n > N.

50. (Se requiere C:ilculo). tiliza cuantificadores para expresar la sentencia lim,,_>_ an = L.

51. (Se requierc Calculo). Utiliza cuantificadores para expresar la sentencia I fill 11_,_ an 110 existe.

52. (Se requiere Calculo), Utiliza cuantificadores para expresar la siguientc definicion: una sucesion I Q,,! es una sucesion de Cauchy si para todo rnimero real £ > 0 hay Ull entero positive N tal que I a - a. I < f. para cada par de enteros positives II y m, m ;'N, I;' > N.

53. (Se requiere Calculo), Utiliza cuantificadores y conectivoslogicos para expresar esra definicion: un rnimero L es el limite superior de una sucesion (a J si para todo mimero real E > O. a > L - £ IJant infin'itos valo-

. "

res de n y an > L + E s610 para un nurnero rillito de va-

lares de n.

52 Matcrnatica discreta Y MIS aplicaciones

lVIetodos de demostracion

Enlaces

E)eJU[?los ad ieionales

EJEMPLOI

INTRODuccn)N

Dos irnportanres cuestiones que aparecen en el estudio de las matematicas son: (1) i,cuando es correcto un argumento maternatico", y (2) "que metodos se pueden utilizar para construir argumentes matematicos? Esta secci6n ayudara a resolver estas dos preguntas describiendo varios tipos de argurnentos maternaticos, correctos e incorrectos,

Un teorema es una sentencia que se puecle verificar que es verdadera. (A veees a los teoremas se les llama proposiciones, hechos 0 resultados). Demostramos que un teorerna es verdadero mediante una secuencia de semencias que constituyen un argumento Ilamado demostraci6n. Para construir demostraciones se necesitan metodos para derivar sentencias nuevas a partir de las conocidas. Las sentencias que se utilizan en una demostraci6n pueden incluir axiomas 0 postulades, que son suposiciones que subyacen a las estructuras matematicas, hipotesis del teorerna 0 teoremas dernostrados previamente. Las reglas de inferencia, que son los rnedios usados para deducir conclusiones a partir de otras afirmaciones, enlazan los pasos de una demostracion,

En esta seccion hablarernos sobre las reglas de inferencia, 10 que ayudara a clarificar c6mo construir una dernostracion correcta, Describiremos tambien algunas formas frecuentes de razenamiento incorrecto, que Ilamarernos falacias. Presentaremos varios rnetodos que se utilizan eorminmente para demostrar teoremas,

EI rermino lema 0 corolario se ernplea para cierto tipo de teorernas. Un lema es un teorerna sencillo urilizado en la dernostracion de otros teoremas. Dernostraciones complicadas son a veces mas faciles de en tender hacienda usa de lemas, los cuales se dernuestran por separado. Un coroIario es una proposicion que se puede establecer directamente a partir de un teorema que ya ha sido demostrado, Una conjetura es una senteneia cuyo valor de verdad es desconocido, Cuando se cncuentra una demostracion para una conjetura, esta se convierte en teorema, Muchas veces las conjeturas resultan ser falsas, por 10 que no Ilegan a ser teorernas

Los metodos de demostracion que sc describen en este capitulo son importantes no solo pOTque se usan para dernostrar teoremas rnaternaticos, sino por sus muchas aplicaciones en ciencias de la cornputacion. Entre elias, podemos citar la verificacion de que un prograrna de ordenador es correcto, establecer si un sistema operative es seguro, hacer inferencias en el area dela inteligencia artificial o mostrar que las especificaciones de un sistema son consistentes, Por consiguiente, entender las tecnicas que se utili Zan en las demostraciones es esencial tanto en las matemaricas como en las ciencias de la compuracion.

REGLAS DE INFERENC:IA

Vamos a introducir en este apartado las reglas de inferencia para 16gica proposicional. Estas regJas justifican los pasos dados para dernostrar que a partir de una serie de hipotesis se llega de forma 16- gica a una conclusion. Lafautolo¥fa (P 1\ (p -7 q)) -7 q es L.fl b~se de la regia de infereneia Hamada modus ponens. Esta Ie rologfa se escribe de la forma srguiente

p p-7q

:. q

Usando esta notaci6n las hipotesis se escriben en una columna y la conclusion debajo de una barra horizontal. (El simbolo :. denota «por tanto» 0 «luego»). EI modus ponens declara que si tanto una irnplicacion como sus hipotesis son verdaderas, entonces In conclusion de esta implicacion es verdadera.

o

Supongamos que la irnplicacion «si nieva hoy, irernos a esquiar- y [a hipotesis «esta nevando hoy»

son verdaderas, Entonces, par el modus ponens, se sigue que In conclusion «irernos a esquiar» es v~~~. ~

Los fundarnenros: 16gica y demostracion, conjuntos y funciones S3

EJEMPLO 2 Supongamos que la implicaci6n «si n es mayor qlle 3, entonces n2 es mayor que 9» es verdadera.

Por tanto, si n es mayor que 3, por eJ modus ponens, se sigue que n.2 cs mayor que 9. ....

La Tabla 1 muestra un Iistado de las reglas de inferencia mas importantes. En los problemas de la Secci6n 1.2 podemos encontrar verificaciones de estas reglas. Aquf daremos algunos ejernplos de argumentos que utilizan estas reglas de inferencias,

E.JEMPLO 3 Di en que regia de inferencia se basa e1 argumento siguiente: «Ahora estamos bajo cera. Por tanto, bien estarnos bajo cera a bien llueve ahora»,

Solucion: Sea pIa proposici6n «Ahora estamos bajo cera» y q «Llueve ahora», Entonces, este argumenro es de la forma

p :.pvq

Este argumento utiliza la regia de adici6n.

EJEMPLO 4 Di en que regia de inferencia se basa el argumento siguiente: «Estamos bajo cero y llueve, Par tanto, estarnos bajo cero».

Solucion: Sea pIa proposici6n «Estarnos bajo cera» y q «Llueve». Bntonces, este argumento es de 18 forma

pAq :.p

Este argumento uriliza la reg1a de sirnplificacion.

Tabla L Reglas de inferencia,
Regia de inferencia Tautologla Nombre
F__ p ---+ (p vq) Adici6n
:. p vq
pllq (p t\ q) ---+ p SimpIi Ficaci6n
:.p
p ((p) II (q» ---+ (p t\ q) Conjunci6n 0 ley de comhinaci6n
q
--
:. p r. q
P [p II (p ---+ q)] -? q Modus ponens
p---+q
:.-q-'
I "q [-,q 1\ (p ---+ q)] -? =p Modus tollens
:. :p-? q .
p---+q l(P ---+ q) II (q -? r)] ---+ (p ---+ r) Silogismo hipotetico
q---+r
:.p---+r
pvq [(p v q) r. ..,p) ---+ q Silogismo disyuntivo
-'p
-_
:.q
pvq 0 [(P v q t\ (-,p 1\ r)] --') (q v r) Ley de resoluci6n
"'p v r
.', (jV"r 54 Maremat ica discreta y sus aplicaciones

EJEMPLO 5 Di en que regia de inferencia se basa el argumento siguiente:

«Si llueve hoy, entonces hoy no haremos una barbacoa, Si no hacemos una barbacoa hoy, haremos una barbacoa manana. Por tanto. si llueve hoy, harernos una barbacoa manana».

Soluci/m: Sean pIa proposici6n «Llueve ahara», q «Hoy no harernos una barbacoa» y r «Harem os una barbacoa manana». Entonces este argumento es de Ia forma

p~q q-;r

:.p---7r

Por tanto, este argumento es un silogisrno hipotetico,

ARhUMENTOS VALIDOS

Se dice que un argumento deductive es correcto S1 siempre que todas las hipotesis son verdaderas, la conclusion tambien 10 es. Consecuentemente, mostrar que q se deduce logicamente de Jas hi-

p6tesis PI' P2, , P; es 10 misrno que rnostrar que la implicacion

(P I /\ P2 /\ /\ p) ~ q

es verdadera, Cuando todas las proposiciones utilizadas en un argumento correeto SOn verdaderas, se Ilega a una conclusion correcta. No obstante, un argumento correcto puede conducir a una conelusion incorrecta si se utilizan una 0 mas proposiciones Ialsas en el argumento. Par ejempIo,

«Si fi> t, en tal caso ('i2) 2 > (t)2. Sabemos que --J2 > +: par consiguienre,

(-i2t ~ 2 > (tY = t»·

.Ej¢iilpt9S ~. adicionale..1ii

CS un argumento correcto basado en el modus ponens. Sin embargo, la conclusion de este argumento es falsa, porque 2 < t. Se ha usado en el argumento la proposici6n falsa «-,/2 > ~», 10 que

significa que la conclusion de este argumento puede ser falsa. ~

Cuando hay rnuchas prernisas, a rnenudo se necesitan varias reglas de inferencia para demostrar que un argumento es correct.o. Esto se ilustra en los ejemplos siguientes, donde se muestra paso a paso como se Uega de un argurnento a otro, razonando expltcitameme cada paso que se ha dado. Estos ejemplos rnuestran tambien .omo se pueden analizar argurnentos en lenguaje natural utilizando reglas de inferencia.

EJEMPL06

Muesrra que las hipotesis «Esta tarde no hace sol y hace mas fda que aye!"», «Irernos a nadar s610 si haec sol», «Si no vamos a nadar, daremos un paseo en canoa» y «Si dames un paseo en canoa, estarernos en casa para la pucsta de sol» conducen a la conclusion «Estaremos en casa para la puesta de sob>.

Solucion: Sea pIa proposition «Esta . i de haec soh>, q la proposicion «Hace mas frio que ayer», r la proposiei6n «Irernos a nadar», S l~roposici6n «darernos un pasco en canoax y t Ia proposicion «Estaremos en casa para la puesta de sol». Entonces. las hipotesis se pueden expresar como =p /\ q, r -; [1, ""r ---7 S Y S ---7 t. La conclusion es simplernente t. [En el caso de 1a segunda hip6tesis, se recuerda que una de las formas de expresar r ~ p recogida en 1a pagina 5, Secci6n 1.1, es «r s610 si p», que es la forma de la hipotesis «Iremos a nadar s610 si haee sol].

Construimos lin argumento para mostrar que nuestras hipotesis condueen a la conclusi6n deseada como sigue,

Paso

1. =p /\ q

2. 'P 3.r-;p

Razonamiento Hipotesis

Simplificaci6n usando el paso 1 Hipotesis

4. -'r

5. -'r --+ s

6. s

7. s --+ l 8.

Los fundamemos: 16gica y demostracion, conjuntos y funciones S5

Modus iotlens usando los pasos 2 y 3 Hip6tesis

Modus ponens usando los pasos 4 y 5 Hipotesis

Modus ponens usando los pasos 6 y 7

EJEM PLO 7 Muestra que las hipotesis «Si me mandas un mensaje por correo electronicc, entonces acabare de escribir e\ programa», «Si no me mandas un mensaje por correo electr6nico, me ire ala cama ternprano» y «Si me voy a la cama temprano, me levantare descansado» lie van a la conclusion «Si no acabo de escribir el programa, me levant are descansado».

Solucion: Sea p Ja proposicion «Me rnandas un rnensaje por correo elecrronico», q la proposicion «Terminare de escribir el prograrna», ria proposicion «Me ire a la cama temprano» y s la proposicion «Me levantare manana descansado». Las hipotesis se pueden reescribir como p --+ q, -'j? --+ r y r --+ s. La conclusion deseada es -,q --7 s.

Esta forma de argumento muestra que nuestras hipotesis conducen a la conclusion deseada.

Paso l.P--7q

2. -'q --+ -,p

3. ""p --7 r

4. =q --7 r

5. r --+ s

6. ""q --+ s

RESOLUCION

Razonamiento Hipotesis

Contrarreciproco del paso l Hiporesis

Silogismo hipotetico usando los pas os 2 y 3 Hiporesis

Silogisrno hipoterico usando los pasos 4 y 5.

Se han desarrollado programas de ordenador que auromatizan tareas de razonamiento y demostraciones de teoremas. Muchos de estes programas hacen uso de una regla de inferencia conocida como resolution. Esta regIa de inferencia se basa en la tautologia

«(p v q) 1\ ('P v r)) --7 (q V r),

(La comprobaci6n de que esta sentencia es una tautologfa se trat6 en el Problema 28 de la Secci6n 1.2). La disyuncion final en la regla de resolucion, q v r, se llama resolvente, Cuando se cumpie que q = r en esta tautologfa, tenemos que (p v q) 1\ (-'p v q) --+ q. Adernas, cuando r = F, obtenernos que (p v q) A ("p) --+ q (puesto que q v F == q), 10 cual es la tautologia en Ia que se basa el silogisrno disyuntivo.

Utiliza la regia de resolucion para mostrar que las hipotesis «Jaime esta esquiando 0 no nieva» y «Nieva 0 Beatriz esta jugando al hockey» impl ican que «Jaime esta esquiando 0 Beatriz esta jugando al hockey» .

S0_Iuci6n: lea p la proposicion «Nieva», q la. proposicion «Jajm~ ~sta ,esquiando» y rIa proposiCIOn «Beat~z esta jugando al hockey», Podernos representar las hipotesis como op v q y p v r, respectivamente. Utilizando la regla de resolucion, se obtiene la proposicion q v r, es decir, «Jaime esia esquiando 0 Beatriz esta jugando al hockey». ....

EJEMPL08

.t ~ ,Ei emplos

, ail ic'ionaJe.i

La regia de resolucion desempeiia un importante papel en lenguajes de programaci6n basados en las reglas de la !6gica, como el Prolog (donde se aplica la regla de resolucion sobre sentencias cuantificadas). Ademas, se puede usar para construir sistemas automaticos de demostracion de teorernas. Para construir dernostraciones en logica proposicional utilizando In rcgla de resolucion como iinica regla de inferencia, la hipotesis y la conclusion deben ser expresadas como clausulas, donde una clausula es una disyuAci6n de variables a negacion de estas variables. Podernos sustituir una sehtencia en J6gica proposicional que no sea una clausula por una 0 mas sentencias equivalentes que sean clausulas, Por ejemplo, supongamos que tenernos una sentencia de la forma

56 Malemalica discreta y sus aplicaciones

p V (q 1\ r). Como p v (q 1\ r) =- (p v q) 1\ (p v r), podemos sustituir la sentencia individual p v (q 1\ r) por la conjuncion de las dos sentencias (p v q) y (p v r), cada una de las cuales es una ·j;iusula. Podernos sustituir una sentencia de la forma -.(p v q) par la conjuncion de las dos sentencias -'p y -'q (que son clausulas), puesto que por las leyes de De Morgan -'(p v q) == -'p 1\ -'q. Podemos tam bien reemplazar una implicaci6n P ---1 q par la disyuncion equivalente 'P v q.

EJEMPLO 9 Muestra que las hipotesis (p 1\ q) v r y r ---1 s implican la conclusion p v s.

Solucion: Podernos reescribir la hipotesis (p A q) v r como dos clausulas, p v r y q v r . Podemos reemplazar tambien r ---1" S por la clausula equivaiente -,r v s. Utilizando las dos clausulas p v r y -'r v s, podemos usar la regJa de resolucion para concluir p v s. .....

FALACIAS

t Hay varias falacias muy frecuentes que surgen de razonarnientos incorrectos, Estas falacias se ase-

" I;n1~S mejan a reglas de inferencia, pero se basan en contingencias, no en tautologfas, Mostraremos en este apartado la disrincion entre razonarnientos correctos e incorrectos,

La proposici6n [(P ---1 q) A q] ---1 P no es una tantologfa, ya que es falsa cuando p es falsa y q es verdadera, No obstante, hay rnuchos argumentos incorrectos que tratan esta proposicion como si fuese una tautologfa, Esre tipo de razonamiento incorrecto se denomina falacia de afirmar la conclusion.

EJEMPLO 10 l,Es eorrecto el argumento signiente?

Si haces todos los problemas de este Iibro, aprenderas rnatematica discreta. Til has aprendido matematica discreta,

Par tanto, hiciste todos los problemas de este libro.

Solucion: Sea p la proposicion «Hiciste todos los problemas del libro», Sea q la sentencia «Til aprendiste matematica discreta». Entonces, este argumento es de la forma: s.i p -4 q Y q entonces p. Esto es un ejemplo de un argumento incorrecto que usa la falacia de afirmar la conclusion. De heche, es posible que tlJ aprendas maternatica discreta de alguna otra forma que no sea hacer todos los problemas deJ libro. (Puedes aprender maternatica discreta leyendo, asistiendo aclases y haciendo muchos, pero no todos, los problemas de este libro). ....

La proposicion [(p -) q) A -'p] ---1 =q no es una tautologfa, puesto que es falsa cuando pes falsa y q es verdadera. Muchos argumentos incorrectos utilizan erroneamente 10 anterior como regIa de inferencia, Este tipo de razonamiento incorrecto se llama falacia de negar Ia hipotesis.

EJEMPLO 11 Sean p y q las proposiciones del jemplo 10. Si la implicacion p ~ q es verdadera y -'p es verdadera, i,es correcto concluir que ""'q es verdadera? En otras palabras, Les correcto asumir que no aprendiste rnatematica discreta si no hiciste todos los problemas del libro, suponiendo que si haces todos los problemas del libro aprendes matematica discreta?

Solucion: Es posible q~e aprendas matematica discrcJ incl~O si no haces todo.s los problemas del libro. Este argumento mcorrecto es de Ia forma p ---1 ~ Y =p implica -'£1, que es un ejernplo de falacia de negacion de 13 hipotesis .....

REGLAS DE INFERENCIA PARA SENTENCIAS CUANTIFICADAS

Hemos hablado de reglas de inferencia para proposiciones. Ahara describirernos algunas reglas de inferencia importantes para sentencias que involucran cuantificadores, Estas regJ as de inferencia se usan con frecuencia en los argumentos maternaticos, a veces sin mencioaarlas explfcitamente.

Partlcular izacinn universal es Ia regIa cle inferencia que se utiliza para concluir que P(c) es verdadera, donde c es un miernbro particular del dominio, dada la premisa Vx P(x). Se utiliza la

Los fundamentos: logica y demostracion, conjuntos y funciones 57

particularizacion universal cuando se concluye de la sentencia «Todas las mujeres son sabias» que «Usa es sabia», donde Lisa es un miembro del dominic de todas las rnujeres.

Generalizaci6n universal es 121 regIa de inferencia que declara que \Ix P(x) es verdadera, dada Ia prernisa de que PCc) es verdadera para todos los elementos c del dominic. Utilizamas la generalizacion universal cuando rnostrarnos que \Ix P(x) es verdadera tomando un elemente arbitrario c del dominio y mostrando que P(c) es verdadera. El elemento c seleccionado debe ser un elemento arbitrario del dominic y no uno especffico, La generalizacion universal se usa implfcitarnente en rnuchas demostraciones rnatematicas; rara vez se menciona expllcitamente.

Particularizacion existencial es la regla que nos permite concluir que bay un elemen to c en el dorninio para el cual P(c) es verdadera si sabernos que 3x P(x) es verdadera, Aqui no pod em os seleccionar un valor arbitrario de c, sino que deber ser un c para el cual sea verdadera. Generalmente, no tenemos conocirnlento de que c es, s610 de que este existe. Como exisre, Ie podemos dar un nombre y continuar nuestro argumento,

Generalizaci6n existencial es la regIa de inferencia que se utiliza para concluir que 3x P(x) es verdadera cuando se conoee un elemento particular c con P(c) verdadera, Esto es, si conocemos un elernento c del dominio para eJ eual P(c) es verdadera, sabernos que 3x P(x) es verdadera.

Resumimos estas reglas de inferencia en la Tabla 2.11ustraremos c6mo se utiliza una de eslas reglas de inferencia para sentencias cuantificadas en el Ejemplo 12.

EJEMPLO 12

Muestra que las premisas "To do el rnundo en la clase de maremarica discreta esta rnatriculado en ingenieria informatica» y «Marfa es una estudiante cle esta clase» implican la conclusi6n «Marfa esta matriculada en ingenieria informatica».

'. EJ~mpJos ,. , a di_~ill!i'a!es __

Solucion: Sean DCy) «r esta en la clase de rnatematica discreta» y C(x) «x esta rnatriculado en ingeniena informatica». Entonces, las premisas son '\Ix (D(x) -) C(x» y D(Maria). La conclusiones C(Malia).

Se pueden usar los siguientes pasos para establecer la conclusi6n a partir de las prernisas:

Paso

1. "iIx (D(x) -7 C(x))

2. D(Maria) ~ C(Maria)

3. D(Marfa)

4. C(Maria)

Razonamiento Prernisa

Particularizacion universal de ( I ) Prernisa

Modus ponens usando (2) y (3)

EJEMPLO 13 Muestra que las premises «Un esrudiante de esta clase no ha lefdo el libro» y «Todo el mundo en esta clase aprob6 el primer examen» implican la conclusion «Alguien que aprob6 el primer examen no ha lefdo el libro».

Tabla 2, Rcglas de inf 'encia para sentencias cuantificadas,
Regia de injerencia Nomura
Vx P(x) Particularizacion universal
:.p(c)
P(c) para un c arbitrario Generalizacion universal
.. '9x nr)
:Ix P(x) Particularizacion existencial
.. P(c) para algun elernento c
P(c) para algun elernento c General izac i6n exisrcncial
:. 3x P(x) I S8 Matematica discreta y sus aplicaciones

Ele;mpliis .

. atllclun~IJcs

E,i <',IJIp] os ;ulidoi'a]es

DEFINICION 1

Solucion: Sean C(x) «x es de esta clase», R(x) «r ha leido el libro» y P(x) «r ha aprobado el primer examen». Las premisas son :Jx (C(x) 1\ ,B(x)) y 'Vx (ecx) --7 P(x», La conclusion es :::Ix (P(x) 1\ ...,B(x». Los pasos siguientes establecenla conclusion a partir de las premisas,

Paso

1. :Jx (C(x) 1\ ...,B(x»)

2. C(a) 1\ -,fl(a)

3. C(a)

4. 'V x (C(x) --7 P(x». S. C(a) --7 Pea)

6. Pea)

7. -,fl(a)

8. Pea) 1\ -'B(a)

9. 3x (P(x) A -.B(x».

Razonarniento Prernisa

Particularizacion existencial de (1) Simplificaci6n de (2)

Prernisa

Parucularizacion universal de (4) Modus ponens usando (3) y (5) Sirnplificacion de (2)

Conjunci6n de (6) y (7) Generalizacion existencial de (8)

Observacion: Los argurnentos maternaricos a menudo incluyen pasos doode se utilizan reglas de inIerencia tanto para proposiciones como para cuantificadores, Por ejemplo, la particularizacion universal y el modus ponens se nsan a menudo juntos. Cuando estas reglas de inferencia se combinan, la hipotesis 'Vx (P(x) ~ Q(x) y Pee), donde c es del dominic, rnuestra que Ia conclusion Q(c) es verdadera,

Observation: Muchos teorernas en rnatematica discreta enuncian que una propiedad se curnple para todos los elementos de un conjunto en concreto, como el conjunto de los mimeros enteros 0 los reales. Aunque el enunciado preciso de tales teorernas requiere incluir el cuantificador universa], por convencion se ornite. Por ejernplo, la sentencia «S i x > y, donde x e y son nrimeros reales positives, entonces x2 > y » significa realrnente «Para todos los reales positives x e y, si x > y, entonces x2 > y2». Adernas, cuando se dernuesrran teoremas de este tipo, se utiliza a rnenudo la ley de gencralizacion universal sin mencionarlo explfcitamente. El primer paso de la demostraei6n consiste en elegir un elemento generico del dominio. Pasos posteriores muestran que este elemento curnple la propiedad en cuestion, La generalizacion universal irnplica que el teorema se cumple para todos los miernbros del dominio.

En Jas siguientes explicaciones adoptarernos las convenciones usuales y no mencionarernos explfcitamente el uso de la cuantificacion y la generalizacion universales. No obstante, deberia entenderse siempre cuando se aplica esta regla de inferencia de modo impllcito.

METODOS PARA DEMOSTRAR TEOREMAS

Demostrar teorernas es a veces mlly dificil. por 10 que necesitamos todas las herramientas disponibles que nos puedan ayudar. Presentamos ahora Una baterfa de rnetodos diferentes de demosiracion. Estos metodos debcrian convcrtirse en parte de tu repertorio para demostrar teoremas. Dado gue muchos teorernas son implicaciones, las tecnicas para demostrar implicaciones son irnportantes. Recuerda que p --7 q es verdadera a no ser que p sea verdadera y q falsa. Ten en cucnta que cuando se demuestra la sentcncia p --7 q, s610 haee I"flta demostrar que q es verdadera s~ p 10 es; ~or 10 general, no se demue~tra que ~ es verdadera, E 10 que sigue presentaremos las tecnicas mas comunes para demostrar implicaciones.

DEMOSTRACIONES DIRECTAS La irnplicacion p -7 q se puede demosrrar viendo que si p es verdadera, entonces q debe ser verdadera tarnbien. Esto pone de rnanifiesto que Ia combinacion p verdadcra y q falsa no ocurre nunca, Una dernostracion de este tipo se llama demostraci6n directa. Para llevar a cabo este tipo de demostracion se supone que p es verdadera y se urilizan reglas de inferencia y teoremas ya dernostrados para dernosrrar que q debe ser tarn bien verdadera.

Antes de dar un ejernplo de demostracion directa, necesitarnos una definicion.

• .... .. . 1< ...

£1 enteroz es par si existe:u~ entero~ktaJque 'n ~·2Ky~s:imRiJ~ ;i:~xiste lIn entero k ialque

C', " • • ·c_ L , c. ", > :.c:

n zz: 2k+ I. (Observa 'lire un niimero entero esbienpar QQienimpar.).

Los fundarnentos: ]6gica y demostracion, conjuntos y funciones 59

EJEMPLO 14 Da una demosiracion directa del teorerna «Si n es un enrero impar, entonces n2 es un entero impar».

Solucion: Suponemos que 1a hipotesis de esta implicacion es verdadera, es decir, que n es impar. Entonces, n ::0 2k + 1, donde k es un estero. Se sigue que n2 =: (2k + 1)2::0 4k2 + 4k + 1 = 2(2k' + 2k) + 1. Por tanto, n2 es un rnirnero impar (es una unidad mayor que el doble de un enrero). ....

DElVfOSTRACIONES INOrRECTAS Como la imphcacion p --'j q es equivalente a SD con-

·:¢J~mpros.. trarrecfproca, -.q ---7 -p, la implicaci6n P --'j q se puede demostrar viendo que su contrarreciproca

'"ditl"iiafc1;, es verdadera, La contrarreciproca se suele demostrar directarnente, pew se puede utilizar cualquier orra recnica. Un argurnento de este tipo se nama dernostracien indirecta.

EJEMPLO IS Da una dernostracion directa del teorema «SI 3n + '2 es impar, entonces n es impar»,

Solucion: Supongamos que la conclusion de esta implicacion es falsa, es decir, que n es par .. Entonces, n = 2k para algun entero k. Se sigue que 3n + 2::0 3(2k) + 2::; 6k + 2 =: 2(3k + I), por 10 que 3n + 2 es par (par ser multiple de 2). Como la negacion de la conclusion implies que la hipotesis es falsa, la implicacion original es verdadera. ....

DEMOSTRACIONES VACtJAS Y TRIVJALES Supongamos C]ue la hipotesis p de una implicacion p --'j q es falsa. Entonces, la implicacion p ---7 q es verdadera, porque la sentencia tiene la forma 1<' --'j V 0 F ---7 F, Y pOI tanto es verdadera, Consecuenternente, si se puede dernostrar quep es falsa, entonces se puede dar una dernostracion, Hamada demostracion vacua, de la implicaci6n p ---7 q. Las demostraciones vacuas se utilizan para establecer cases especiales de teorernas que enuncian que una implicacion es verdadera para todos los enteros positives [esto es, un teorerna del ripo "lin P(n) donde P(n) es una funcion proposicional], Las tecnicas de dernostracion para teorernas de esta clase se discutiran en la Seccion 3.3.

EJEMPLO 16 Muestra que In proposicion P(O) es verdadera, donde P(n) es la funcion propositional «Si n > 1 es irnpar, entonces nL > n».

Solucion: Ten en enema que la proposid6n P(O) es la implicacion «Si 0 >1, entonces 02 > 0». Cornola hipotesis 0> 1 es falsa, la implicaci6n P(O) es autornaticamente verdadera. ....

Observacion: EI hecho de que la conclusion de esta implicacion, 02 > 0, sea Ialsa es irrelevante para el valor de verdad de esta implicacion, porque esta garantizado que una irnplicacion con tina h ipotesi s falsa es verdadera.

Supongamos que la conclusion q de una implicacion p --'j if es verdadera .. Entonces, p ---7 q es verdadera, puesto que la sentencia tiene la forma V ---7 V 0 F -) V, 10 cual es cierto, Por tanto, si se puede ver que q es verdadera, entonces se puede dar una demostracion, Hamada demostracion tri,vial, de.p --'j .~. Las dcmoSlraCiofes rriviales sO,n irnportanres para casos. :s.peC.iales,~e tcoremas (vease la discusion sobre la tecnicai ~ e demostracion por cases) y en induccion matemauca, que ve-

remos en let Seccion 3.3. .

EJEMPLO 17 Sea Pen) «Si a y b son enteros positivos, a 2: b, cntonces a" 2: b''», Muestra que la proposicion P(O) es verdadera.

Solucion: La proposici6n P(O) es «Si a 2: b, entonces aO 2': 17°». Como 00 = bO = 1, 1£1 conclusion de P(O) es verdadera. Po}" tanto, P(O) es verdadera. Este es un ejemplo de una dernostracion trivial, Nota que In hiporesis, que es la sentencia <(02': b», nose necesito cn Ia dcmostracion. ....

UN POCO DE ESTRATEGIA PARA HACER DEiYIOSTRACIONES Hemos descrito tanto las demostraciones directas conio indirectas y hemos proporcionado ejemplos de como se utilizan; sin embargo, cuando nos enfrentamos a un teorema que debemos demostrar, Lqm'S rnetodo

60 ]1..'1 aiemanca d iscreta y sus aplicaci ones

Ej~""pl"s ~di<'i'mal"s

DEFINICION 2

deberernos usar? Prirnero evahia si una dcmostracion directa parece eficaz. Desarrolla las definiciones dadas en las hipotesis, Luego comienza a razonar hacienda uso de cllas, junto can los axiomas y los teoremas disponibles. Sj no parece que conduzca <I ningun sitio, intenta 10 mismo con una demostracion indirecta. Recuerda que en una demostracion indirecta se asume que la conclusion de la implicacion es falsa y se utiliza una demostracion directa para demostrar que se deduce que la hiporesis debe ser Ialsa. A veccs, cuando 110 hay una forma obvia de conseguir una demostracion directa, una dernostracion indirecta puede funcionar. Ilustramos esta estrategia en los Ejernplos 18 y 19.

Antes de presentar los siguientes ejernplos.nccesitamos una definicion.

EJEMPLO 18 Dernuestra que la suma de dos numeros racionales es un mimero racional.

Solucion: Primero intentamos una dernostracion directa. Para empezar, supongamos que r y s son mimeros racionales, De la definicion de mirnero racional se sigue que hay dos enteros p y q, q :t. 0, tales que r "" plq, y orros dos enteros f y u, u:;f". 0, tales que s = / / u. l,Se puede usar esra informacion para mostrar que r + s es racional? EI paso siguiente obvio es sumar r = p/q y s = I/U para obtener

r+s:::;;E+!_= pU+ql ..

q u qu

Como q #- 0 Y II ,.: 0, se sigue que qu « O. Par cousiguierue, hemos expresado r + s como la razon de dos enleros,pu + qt y qu, donde qu"f:- O. Esto significa que r + s es racional; Nuestro intento por encontrar una dernostracion direcra ha leniclo exito, .....

EJEMPLO 19 Demuestra que si n es un entero y fl." es impar, entonces n es impar.

Solucion: Primero intentamos una dernostracion directa, Supongamosque n. es un entero y n2 es impar. Entonces, existe un entero k tal que n2 :::: 2k + 1. i,Se puede utilizar esta informacion para dernostrar que n es impar? No parece haber un camino obvio pam mostrar que n es impar porque las soluciones para n son de 13 forma n:::: ±.,}2k + I, 10 cual no es muy iitil.

Como el intenio de dar una dernostracion directa 110 parece tener exito, interuamos la dernostracion indirccta. Tomamos como hipotesis que n no es impar, Como todo entero que no es impar es par, n es par. Esto implica que existe un k tal que n :::: 2k. Para dernosrrar el teorerna, necesitamos mostrar que est a hipotesis implica la conclusion de que n2 no es impar, es decir, de que n2 es par. LPodernos usar la ecuaci6n n :::: 2k para llegar a esto? Elevando ambos miemoros al cuadrado, obtenemos nl = 4k2 = 2(2k2),lo que implica que n2 es tambien par, ya que n2= 21,. donde

1= 2k'. HemOS,leIDdO exito en el intento de enconttaT.una demoSlmci61 ... indirecta. .~.

DEMOSTRACIONES POR REDUCCION AL AHSURDO Hay otn formas de demosrracion que no son ni la directa ni la indirecta. Presentamos ahara varias tecnicas adicionales de demostraci6n.

Supongamos que se puedeencontrar una contradicci6n q tal que -OJ) -) q sea verdadera, esto e::;, =p -) Fes verdadera, Entonces la proposicion -'p tiene que ser falsa. Par tanto, p debe ser verdadera, Esta tecnica se utiliza cuando podemos encontrar una contradiccion, como por ejemplo r !\ -v, de tal forma que es posible mostrar que la irnpl icacion =p -) (r !\ -or) sea verdadera .. Un argumento de este tipo se llama demos.t.raci6n por reduccien al absurdo,

Vamos a dar ahora tres ejernplos de demostraciones pOT reducci6n al absurdo, El primero es un ejemplo de la aplicacion del principia del palomar, una tecnica de combinatoria que se veri en

profundidad en 1<1 Seccion 4 .. 2.· c

Los fundameruos: logica y dernostraeion, conjuntos y funcioncs 61

EJEMPLO 20 Muestra que al menos cuatro de cada 22 dias deben caer en el mismo dla de la semana.

,Eje[iiplo.~ " , "'ti~irrfla(,rs

Solucion. Seap la proposici6n «AI rnenos cuatro de los 22 dias elegidos caen en el mismo dia de la scrnana». Supongarnos que 0p es verdadera, Entonces, como mucho, tres de estos 22 dfas corresponden al mismo dia de la semana. Como hay siete elias de la semana, esto implies que como mucho se podrian haber clegido 21 d[~LS, puesro que Ires son los que, a 10 mas, pueden ser un dia particular de la semana. Esto es una contradiccion. ..

EJEMPLO 2J.

Muestra que fl es irracional dando una demostraci6n por reduccion al absurdo.

Solucion: Sea p la proposicion «-/2 es irracional». Supongarnos que =p es vcrdadera, Entonces, 12 es racional. Mostraremos que esto conduce a una contradiccion. Bajo la suposicion de que {2 es racional, existiran dos enreros a y b de tal forma que {2 = alb, donde a y b no tienen factores comunes (de tal forma que no hay una fraccion equivalente a alb con mimeros mas pequefios), Como {2 == alb, cuando ambos miembros de la ccuaci6n se elevan al cuadrado, se sigue que

2 == a2/b2

Por tanto,

2b2 = a2.

Esto significa que a2 es par, pOI' 10 que a es par. Adernas, como a es par, a = 2c para algun entero c. Asi,

2b2 == 4c2, par 10 que

b2 = 2c2•

Esto significa que b2 es par. Par tanto, b debe ser par tam bien.

Se ha mostrado que -'p implica que 'Y2 = alb, donde a y b no tienen Iactores comunes y 2 divide a a yah. Esto es una contradiccion, puesto que se vc que -,p irnplica tanto r como =r, donde res la sentencia «a y b son enteros sin factores cornunes». POI' tanto, -yJ es falsa, es decir, «fl es irracional» es verdadera. ..

Una c1emostraci6n indirecta de una implicaci6n se puede reescribir como una demostracion por reducci6n al absurdo. En una dernostracion indirecta mostramos que p ---!> q es verdadera utilizando una demostracion directa para ver que =q ---!> -'p es verdadera Esto es, en una prueba indirecta de p -7 q suponemos que -,q es verdadera para mostrar que 0p debe serlo. Para reescribir una demostracion indirecta de p ---!> q como una demostraci6n por reduccion al absurdo, suponemos que tanto p como ""q son verdaderas. Entonces usamos los pasos de la prueba directa -,q ---!> -'p para mostrar que ""p debe ser verdadera tarnbien . Esto conduce a la contradicci6n p A =p, completando la dernostracion por reduccion al absurdo. El Ejemplo 22 ilustra c6mo una demostracion de una implicacion se puede reescribir como una dernostracion por reduction al absurdo.

EJEMPLO 22 Da una dernostracion POf reduccioc al absurdo di teorema «Si 3. + 2 es impar, entonces n es irnpar», Solucion: Asumimos que 3n + 2 es impar y que n no es impar, es decir, n es par. Siguiendo los mismos pasos que en la solucion del Ejemplo 15 (una demosrracion indirecta de este teorerna), podemos mostrar que si n es par, entonces 311. + 2 es par. Esto contradice la suposicion de que 3n + 2 es impar, cornpletando la dernostracion. ..

DEMOSTRACI6N POR CASOS Para demostrar una implicacion de Ia forma

(PI V P2 v , .. V pJ -7 q se puede utilizar la tautologia

62 Matemauca discrete y sus aplicaciones

Ej~plos aditionales

EJEMPL023

EJ El\fPLO 24

, 'Ejemplo

, adi~iotliilcS

como regla de inferencia. Esto mucstra que la irnplicacion original con una hip6tesis construida mediante una disyunci6n de las proposiciones PI' P2' ... 'PI! se puede demostrar demostrando individualmente cada una de las n implicaciones Pi --7 q, i = 1, 2, ... , n. Tal argumento se denomina una demostracion por casos. A veces para demostrar que una irnplicacion p --7 q es verdadera, es

conveniente usar una disyunci6n de proposicionesp, v P2 v V P; en lugar de una sola proposicion

p como hipotesis de la irnplicacion, donde p y P, V P2 v V P/I SOil equivalentes, Considera el

Ejemplo 23.

Utiliza L10a dernostracion por casos para ver que Ixy I =: Ix II y I, donde x e y son rnimeros reales, (Recuerda que I x I, el valor absoluto de .r, es igual a x cuando x ~ 0 e igual a -x cuando x ~ 0).

Solucion: Sea P «z e Y son nurneros reaies» y sea q «I.xy I =0 I x II y I». Ten en cuenta que p es equivalente a Pj v Pz V PJ V P4' donde PI es «x ~ 0 1\ Y ~ 0», Pz es «r ~ 0 1\ Y < 0», P3 es ,<_X < a I\y ~ 0» y P,I es «x < 01\ Y < 0,>. Par tanto, para demostrar p --7 q, podemos ver quep, -7 q, P2 --7 q, P3 --7 q Y P¢ -'f q. (Hemos considerado estes cuatro casas porque son una eleccion apropiada para poder eliminar el signo del producto dentro de cada caso).

Vernos que PI --7 q porque xy ~ 0 cuando x ~ 0 e y ~ 0, por 10 que kyl =: xy = Ixlly I.

Para vel' que P2 -7 q, ten en cuenta que si x ~ 0 e y < 0, entonces xy :e;; 0 por 10 que 1 xy I=:-"ty = x(-y) =: Ixlly I. (Aqui, como y < 0, tenernos que Iy I=:- y),

Para ver que P3 -) q, seguimos el mismo razonamiento que en eJ caxo anterior, carnbiando x por y, y viceversa.

Para ver que P4 --7 q, ten en cuenta que cuando x < a e y < 0 se sigue que xy > O. Por tanto,

~ryl = xy '" (-x)(-y) = I xii YI. Esto completa la demostracion, ....

DEMOSTRACIONES POR EQUIVALENCIA Para demostrar un teorema que viene dado par una bicondicional, esto es, una doble implicacion de la forma pH q, donde p y q son proposiciones, se puede usar la tautologfa

(p H q) H [(p -7 q) 1\ (q ~ p)].

Esto es, la proposicion «P si, y 5610 si, q» se puede dernostrar si se demuestran las dos implicaciones «si P, entonces q» y «si q, entonces p»,

Dernuestra el teorema «El cmero n cs impar si, y s610 si, 112 es impar»,

Solucion. Este teorerna tiene la forma «p si, y s610 si, q», donde pes «rt es impar. y q es «n2 es impar». Para dernostrar este teorerna, necesitarnos mostrar que p -7 q Y q ~ P son verdaderas.

Ya hernos dernostrado quep -'f q Y que q -7 P son verdaderas (Ejemplos 14 y 19, respectiva-

mente). Como P --7 q Y q --7 P son verdaderas, hem os dernosrrado que el teorema se cumple, ....

A veces un teorema enuncia que varias proposiciones PI' Pl, ... , PI1 son equivalenres, Tales teorernas se pueden reescribir como

PI HPzH ... HPIl, !

10 cll~l declaraqu~ las II proposicione~ tiencn 10s mismos valores de verdad y, par ~ant ,q?e para todo I Y}, 1 $ l$):e;; 11, Pi Y Pj son equivalentcs, Una forma de demostrar estas equival eras mutuas es ernplear la tautologfa

E, to indica que SI las implicaciones PI --7 P2, P2 --7 PJ' ... 'Pil -7 PI se pueden mostrar que son verdaderas, entonces las proposiciones PI' Pl' ... , Pilson todas equ ivalcntes.

ESI0 es mucho mas eficiente que probar P, -'f Pj para i ;# j, 1 :e;; i ~ n y 1 :e;; j :e;; n.

Cuando dernostramos que lIll grupo de sentencias son equivalenres, podernos establecer cualquier cadena de implicaciones que elijamos, ya que a traves de la cadena es posible ir de una a otra cualesquiera. Par ejemplo, podemos ver que PI' P2 Y P3 son equivalentes mostrando que PI -'f P3' P3 -'f P1 Y P2 --7 PI'

Los fundarneruos: logicll y demosrracion, conjuntos y fnnciones 63

EJEMPLO 25 Muestra que estas sentencias son equivalentes:

PI: n es un entero par

Po: n -1 es un entero impar P;: nZ es un entero par

Solucion: Mostrarernos que estas tres sentencias son equivalenres viendo que las implicaciones que PI -7 PL' P2 -7 p] Y P, -7 Pj son verdaderas,

Hacemos una demostracion directa para PI -7 ])2' Supongamos que n es par. Entonces, 11 ~ 2k para algjin entero k. Par tanto, n - J == 2k - 1 ::-:: 2(k - 1) + 1. Esto significa que n - l es impar, pues se puede poner de la forma 2m + I, donde In es el entero k - 1.

Daremos tarnbien tina prueba directa de que P2 -7 P3. Supongamos ahara que n - 1 es irnpar. Entonces, II -1 = 2k + 1 para algiin entero k. Por tanto, n = 2k + 2, por Jo que /12 == (2k + 2)2 = 4F + 8k + 4 == 2(2k2 + 4k + 2). Esto significa que n2 es el doble del entero 2f.:} + 4k + 2, Y por tanto, par ..

Para demosrrar Po -) PI utilizamos una dernostracion indirecta. Esto es, dernostrarnos que si n no es par, entonces n2 no es par. Esto es 10 mismo que dernostrar que si n es impar, n1 es impar, 10 cual se ha hecho ya en el Ejemplo 14. Esto complete la dernostracion. .....

. 'I'EOREMAS Y CUANTIFICADORES

Machos teorernas se enuncian haciendo usa de proposiciones y cuantificadores. Se pueden utilizar varies metodos para demostrar teoremas que son cuantificaciones. Aquf describimos algunos de los mas imporrantes.

D.EMOS'fRACIONES DE EX.lSTENCIA Muchos teoremas afirman 13 existencia de un tipo particular de objetos. Un teorerna de este tipo es una proposicion de la forma Hr P(x), donde Pes un predicado. Una clemostraci6n de una proposicion de la forma ::Ix P(x) se llama demostraci6n de existeneia, Hay varias formas de demostrar Lin teorema de este tipo. A veces puede darse una dernostracion de! tipo zlx P(x) encontrando un elcmcnto a tal que P(a) sea verdadera. Tal demostracion de existencia se llama constructiva. Tambien es posible dar una dcmostracion de existencia que sea no construetiva. Esto es, no encontramos el elemento a tal qne P(a) es verdadera, sino que dernostramos que.:lx P(x) es verdadera de alguna otra forma. Un metoda cormin para dar una demostracion no constructiva de existencia es utilizar una dernostracion por redueci6n al absurdo y mostrar que la negacion de la cuantificacion existencial implica una contradiceion. El concepto de dernostracion constructive se ilustra en el Ejernplo 26.

EJEMPL026

Una demostracion eonstructiva de existencia. Demuestra que hay LUl entero positive que se puede poner de dos fOlTI1aS diferemes como surna de cubos de enteros positives.

Solucion: Tras considerables calculos (hacienda usa, pOl' ejernplo, de un programa de ordenador), encontramos que

1729 == 103 + 93 =. 123 + J3, I

Como hemos encontrado un entero positive que puedc e cribirse como la suma de cubes de dos formas diferenres, la demosuacion esta conseguida ....

EJEMPLO 27 Una demostraci6n no cunstructiva deexisteneia. Muestra que existen dos numeros irracionaJes x e y tales que Xi es racional,

'" Solution: Por el Ejemplo 21 sabemos que ..J2 es irracional, Considera el mirnero ,/2""-. Si es

racionaJ, hernos encontrado dos rnimeros x e y con x'"racional: x ~ 12 e y =;,f2. Por otra parte, si

( ~).ri

,fi ~Ii Vi . c ~.,J2

.fi es irracional, entonces podemos hacer x = .. ./2 e Y'f '12, de tal forma que xY = .,.,)2 ;0;;

fi(,fi-J2) =,f22 =2.

64 i'vlatematic3 discreta y sus aplicacioncs

EJEMPLO 28

.. Eleihphis-:· . . aJliciollal~

." "".

EJEMPL029

Esra demostraei6n es un ejernplo de dernosrracion no construciiva de existencia, porque no hemos encontrado dos mimeros x c y tales que x .... es racional, Mas bien hernos dcmostrado que

. ~..fi.- . .

bien el par .r =.fl, yo:: \(20 bien x =.,./2 ,)' == '1/2 uno de ellos nene las propiedades deseadas,

pero [no sabcmos cual de estes dos pares es el que buscamos! .....

DE 10STRACIONES DE UNJCIDAD Algunos reoremas afirman la existencia de Ull unico elemento con una propiedad particular. En arras palabras, estos teoremas afinnan que hay exactamente UIl elernento con esta propiedacl. Para demostrar una sernencia de este tipo, necesitamos mostrar que existe un elemento con esta propiedad y que ningtin otro elernento cumple esta propiedad. Las dos partes de una dernostracion unicidad son:

Existencia: Mostramos que existe un elemento x can la propiedad deseada. Unicidad: Mostramos que si y i' x, entonces y no tiene la propiedad deseada,

Observacion: Mostrar que existe un unico elerncnto x tal que P(x) es 10 rnismo que demostrar la sentencia 3x (P(x) /I Vy (y ;t; x ~ -,P(y»).

Muestra que todo entero tiene un till ico inverse respecto la suma. Esto es, rnuestra que si p es un entero, entonces existe un iinico entero q tal que p + q = O.

Solucion: Si pes un entero, encontramos que p + q;;:: 0 cuando q;;:: -p. Como q es tamoien enteTO, por consig uiente, existe un en tero q t.al que p + q = O .

Para mostrar que dado el entero p, el entero q tal que p + q;;:: 0 es iinico, supongarnos que r es lin entero tal que r :j::. q y p + r:::: O. Asi, p + q = p + r. Sustrayendo P de ambos lades de la ecuacion, se sigue que q == r, 10 que contradice la suposicion de que q i' r, Por tanto, hay LI!l unico entero q tal que p + q :::: O. ....

CONTRAEJEMPLOS En la Seeei6n 1.3 rnencionamos que se podfa ver que una sentencia de la fODl13 Vx P(x) es falsa si podemos encontrar un contraejemplo, esto es, un ejemplo x para el cual P(x) es falsa, Cuando nos encontramos una sentencia de la forma Vx P(x) y bien creemos que es falsa 0 bien se nos resisten todos los intentos para encontrar una demostracion, buscamos un contraejernplo. Ilustrarnos la caza de lin contraejernplo en el Ejernplo 29.

Muestra que la sentencia «To do entero positive es la suma de los cuadrados de tres enteros» es falsa.

Solucion: Podemos mostrar que esta sentencia es falsa si encontramos un contraejernplo, Esto es, la sentencia es falsa si podemos rnostrar que hay un entero particular que no es la suma de los cuadrados de tres enteros. Para buscar un contraejemplo, intentamos escri bir los sucesivos enreros positivos como suma de Ires cuadrados. Encontramos que 1 = ()2 + 02 + 12,2 = 02 + 12 + t2, 3 = ]2 + 12 + J2,4 = ()2 + 02 + 22,5 == 02 + 12 + 2", 6;= 12 + P + 22, pero no podernos encontrar una forma para escribrr 7 como la suma de tres cuadrados, Para demostrar que no hay Ires cuadrados que Sl1 men 7, ten en cu.elltu que po~emos utilizar s610 aqucllos cuadrados que no exceden de 7, a saber~ 0, I Y 4. Como no hay tres terrrunos escogidos entre 0, I 04 cuyos cuadrados surnen 7, se sigu· que 7 es un eontraejemplo. Concluimos que la sentencia «Todo entero positive es la surna de 10" cuadrados de tres enteros- es falsa. ....

Un error corrnin consiste en asurnir que uno 0 mas ejernplos establecen la verdad de una selltencia. No importa los ejemplos que se encuentren que hagan P(x) verdadera, la cuantificacion universal Vx P(x) puede ser Ialsa, Considera el Ejernplo 30.

NOTA HISTc)RICA Cuando el matemauco inglis G. H. Hardy visito al prodigio hindu Ramanujan en el hospital donde estaba convaleciente, Hardy seriaki que ell729, el ruimero del taxi que habla tornado, era bastante insulso, Ramanujarr le replico: «No, cs un rnimero muy interesantc: es el rnirnero mas pequefio que se puede expresar como Ia surna de cubos de dos formas diferentes». (VeaJ1se los Problemas suplemeruarios del Capitulo 3 para las biografias de Hanly y Ramanujan).

Los fundameruos: Iogica y dernostracion, conjuntos y tunciones 65

E,JEMPLO 30 ~Es verdad que todo ernero positive esla suma de 18 potencias cuartas de enteros? En otras palabras i_,es un teorerna la sentencia 'lin Pen), donde Pen) es la sentencia «n se puede escribir como la suma de J 8 potencias cuartas de enteros» y el dorninio consiste en rodos los enteros positivos?

Solucion: Para deterrninar si n se puede escribir como la suma de 18 potencias cuartas de enteros, deberfamos empezar cxarninando SI n es la surna de 18 potencias cuartas de enteros para los enteros positives mas pequefios, Como las potencias cuartas de enteros son 0, 1, 16,81, ... , si podemos seleccionar 18 terminos de estos nurncros que sumen n, entonees /1 es una suma de 18 potencias cuarras, Podemos rnostrar que todos los enteros positives hasta 78 se puede escribir como la suma de 18 potencias cuartas, (Los detalles se dejan al cuidado del lector). Sin embargo si decidieramos que esto es suficiente, habriamos lJegado a una conclusion err6nea. La sentencia inicial no es correcta parque 79 no es surna de 18 potencias cuartas (como ellector podria verificar). ....

ERRORE_.S EN DEMOSTRACIONES

Hay mucho fallos comunes en 101 construccion de dernostraciones, Describirernos brevernente algunos de eIlos aquf. Entre los fallos mas generalizados estan las equivocaciones en aritrnetica y algebra basica, Incluso matematicos profesionales corneten tales errores, especialmente cuando trabajan con formulas cornplcjas. Siempre que urilices calculos cornplejos, deberias revisarlos tan cuidadosamente como sea posible. (Serra intcresante que repasases algunos aspectos problematicos del algebra basica, especialmente antes de estudiar Ia Seccion 3.3).

Cada paso de una demostracion matematica debe ser correcto y la conclusion debe deducirse logicamenre de los pasos que la preceden. M uchas equ i vocaeiones resultan de in troducir pasos que no se han deducido logicamente de los anteriores. Esto se ilustra en Jos Ejernplos 31-33.

EJEMPLO 31 ~D6nde esta el error en Ia lamosa «dernosrracion» supuesta de que 1 == 2'1

«Demostracuin»: Considerarnos los siguientes pasos, donde a y b son dos enteros positives iguales.

Paso

Razonarniento Dado

Multiplicando ambos lados de (1) par a Restando b2 a ambos lados de (2) Factorizando ambos lados de (3) Dividiendo ambos lados de (4) por a - b

Reemplazando a por b en (5), _porque a = b, y simplificando Dividiendo ambos lades de (6) por b

1.. a = b

2. a2 = ab

3. a2_/12 =ab-b2

4. (a - b) (0 + b) = b(a - b)

5. a + b = b fl. 2b == b

7. 2 =]

SU/UCiOll: Todos los pasos son validos excepto uno, eJ paso S, donde dividimos ambos lades par a-b. El srna. esta en ql.le a - b es iguaJ a cero. La division de amb(t rniernbros de una ecuaci6n por la rnisrna cantidad es valida siempre q Lie esta cantidad no sea cer' ....

EJEMPLO 32 (_D6nde esta el error en esia «demostracion»?

«Teorerna»: Si 122 cs posirivo, eruonccs n es positivo.

«Demostracion»: Supongamos que /12 es positive. Como la implicaci6n «Si /1 es positive, entonces n2 es positive» es verdadera, concluimos que n es positive.

Solucion: Sea P(n) «n es positive» y Q(n) «n2 es positive». Entonces nuestra hipotesis es Q(n)_ La sentencia «Si n es posirivo, entonces n2 es positive» es la senrencia 'lin (P(n) __,. Q(n)). D'e la 11ip6tesis Q(n) y la sentencia 'lin (P(n) __,. Q(n» no podemos concluir pen), porque no estarnos empleando una regla de inferencia valida. De heche, cste es un ejemplo de la falacia de la aflrmacion

66 Maternatica discrera Y SIl aplicaciones

de la conclusion. Se puede poner un conrraejemplo con n "" - 1, para el cual 1'1.2 = I es cnrero positivo, rem n es negative ....

EJEMPLO 33 i,D6nde esta eJ error en esta «dernostra 'ion»'!

«Teorema»: Si n no es positive, entonces 1/2 no es positive. (Esto es contrarreciproco del «teorema» del Ejemplo 32).

«Iiemostracion»: Supongarnos que n no es positiv J. Como la implicaci6n «Si n es positivo, entonces 1'1.2 es positive» es verdadera, concluimos que n2 no es positivo.

Solucion: Sean Pen) y Q(n) del Ejemplo 32. Entonces nuestra hipotesis es -'P(n) y la sentencia «Si n es positive, entonces n2 es positive» es la sentencia Vil (P(n) -ct Q(n). De la hipotcsis ..,P(n) y la sentencia \;fn (P(n) ~ Q(n) no podernos concluir -,Q(n), porque no utilizamos una regla de inferencia correcta, De heche, esto es un ejemplo de la Ialacia de negar la hipotesis. Puede darse un contraejernplo para n = - 1, como en el Ejemplo 32. ....

Un error cormin consistcnte en hacer suposiciones no garantizadas puede darse en las demostraciones por casos, en las cuales a veces no se consideran todos los casos, Esto se ilustra en el Ejernplo 34.

EJE IPLO 34 l.D6ncle esta el error en esta «demostracion»?

«Tcorema»: Si xes un mirnero real, entonces x2 es un real positivo.

«Ilemostracion»: Sea PI «r es posirivo», p] <(X es negative» y q <<).-2 es positive». Para rnostrar que PI ~ q, ten en cuenta que cuando xes posirivo, x2 es positive, puesto que el producto de dos numeres positives (x y x) reales es un real positive. Para rnostrar que P2 ~ q, sc puede ver que CUaJldo x cs negative, x2 es positive, ya que el producto de dos mimeros negatives, x y x, es positive. Esto completa la dernostracion.

Solucion: EI problema de la solucion yue hemos dado es que hernos olvidado el caso en que x sea igual a 0. Cuando x = 0, r = O. no es positive, por 10 que el reorerna es falso. Si p es «x es un rnimero real», entonces podernos demostrar resultados donde pes la hip6tesis con tres casos P1, P2 Y p-", donde P, es «x es positive», P2 es «r es negative» y P3 es «x = 0», por la equivalencia P H PI V P2 V P3· ....

Finalmenre, discutimos brevernente un tipo cle error especial mente desafortunado, Muchos argumentos correctos se bas an en una falacia llamada peticion de principio, Esta falacia se presenta cuando uno 0 mas pasos de una demostracion se basan en la veracidad de la sentencia que se esta dernostrando. En otras palabras, esta falacia surge cuando se demuestra una sentencia usando en la demostracion la rnisrna sentencia 0 una senten cia equivalente a ella. Es por 10 que esta falacia tambien se conoce como razonamiento circular.

E.JEMPLO 35 (,Es correcto el siglliente argumento? Supuestamente, demuestra que n cs par siempre que /12 sea par.

Supongamos que n2 es par. Entonces, /12 = 2k para aigun cntero k. Sea n =: 21 para algun entero l. Esto muestra que n es par.

Sotucion: Este argumento es incorrecto. La sentencia «Sea n = 21 para algun entero l» se utiliza en la demostracion. No se ha dado ningun argumento que dernuesrre que 1'1 se puecle escribir como 21 para algtin entero I. Esto es un razonarniento circular porque Ia sentencia es equivalente a La sentencia que se quiere dernostrar. esto es, «n es par». POl' supuesto, el resultado es correcto; s610 el metoda de dernostracion es incorrecto. ....

Cometer errores ell las dernostraciones es parte del proceso de aprendizaje. Cuando cometes un fallo y otra persona 10 encuenrra, deberias analizar cuidadosarnente pOT que te equivocasre y

Los fundamentos: 16gica y dcmostracion, conjumos y funciones 67

asegurarte de que 110 cometes el mismo fallo de nuevo, Incluso los maternaticos profesionales corneten en-ores ell sus demostraciones. No pocas demostraciones incorrecras dc resultados imporiantes han confundido a la genre durante muchos alios antes de que los sutiles errores conten ides en ellas fueran encontrados.

SOLO EL COM'IENZO

Hernos presentado algunos mctodos para demostrar teorernas. Observa que no se ha dado ningun algoritrno para dernostrar teorernas; ni siquiera se ha rnencionado, Un resultado de gran calado es que no exi .te tal algoritmo.

Hay muchos teorernas cuyas dernostraciones son faciles de encontrar rrabajando dircctamente can las hipotesis y las definiciones de los terminos del teorema. No obstante, a veces es diffcil demostrar un teorema sin hacer un uso inteligente de demostraciones indirectas por reduccion al absurdo 0 por alguna om) tecnica, Construir demosrraciones es UD arte que solo se puede aprender a [raves de Ja experiencia que consiste en escribir las dernostraciones, hacerlas revisar leer y anaIizar dernostraciones hechas por otros, etc.

Presentamos mas ejemplos de dernostraciones en el resto de este capitulo y en el Capitulo 2.

En el Capitulo 3 seguiremos viendo algo del arte y 1a estrategia de dernostrar teoremas y trabajar con conjeruras, introduciendo varias lecnicas de demostracion importantes entre las que se incluye el principia de inducci6n, que se puede utilizar para dernostrar resultados que e cumplen para enteros positives. En el Capitulo 4 prescntarnos la noci6n de dernostraciones combinatorias.

Problemas

1. Que reglas de inferencia se usan en los siguiernes argumentes?

a) Alicia estudia rnatematicas. POI' tanto, Alicia estudia bien matematicas 0 bien ingenierfa informatica.

b) Jerry estudia maternaticas c ingeniena informatica.

Por tanto, kITY esrudia rnatemaricas,

c) Si Ilueve, se cierra Ia piscina, Llueve: par tanto, esta cerrada,

d) Si nieva hoy, se cerrara la universidad. La universidad no esra cerrada hoy. Par tanto, no nieva hoy.

e) Si vol' a nadar, entonccs csrare al sol dcmasiado tiempo. Si estoy al sol dernasiado tiernpo, me quemarc. Por tanto, si voy a nadar me quemare.

2. l,Quc reglas de inferencia sc usan en los siguientes argumentes?

a) Los canguros viven en Australia y son marsupiales.

Par tanto, los canguros son marsupiales

b) Estarnos a mas de 40°C hoy 0 la polucion es peligrosa, Estamos a menos de 40°C hoy. Por tanto, la poluci6n es peligrosa,

c) Linda es una excclcnre nadadora. Si Linda es una excelente nadadora, entonces puede trabajar como salvavidas. Por tanto, Linda puedc trabajar C01110 salvavidas.

d) Susana trabajara en una compafiia de informatica este verano, Por tanto, csre verano Susana trabajara en lIna cornpafiia de informatica 0 deambulara por la playa.

e) Si trabajo toda Ia noche, podre resolver todos los problemas. Si puedo resolver todos los problemas, en-

tendcre la asignatura. Par tanto, si trabajo toda la noche eruonces entendere Ia asignatura.

3. Construye un argurnento utilizanclo reglas de inferencia para rnostrar que las hiporesis «Randy [Tabaja duro», «Si Randy trabaja duro, sera lin chico soso», «Si Randy es un chico soso, no conseguira el trabajo» implican la conclusion «Randy no consegui I-a cl trabajo».

4. Construye un argumento utilizando rcglas de inferencia para mosrrar que las hiporesis «Si no llucve 0 si no hace niebla, entOI1CCS se celebrara la competicion de barcos y se hara una demostracion de los salvavidas», «Si se celebra la cornpeticion de barcos, se entregara un trofeo» y «El ITOfeo no se ha enLregado» implican la conclusion «Llovio»,

5. i,Que regla de inferencia se uriliza e~ este Iarnoso argumente? «TOGaS los h?mbr-e son mort. les. Socrates es un hombre. Par tanto, Socrates e: rnorta ».

6. i.Que regla de inferencia se usa en este argumenro? « lingun hombre es una isla. Manhattan es una isla. Par tanto. Manhattan no es un hombre».

7. Para cada uno de estes conjuntos de prernisas, l,quc conelusion 0 conclusiones se pueden deducir? Explica las reglas de inferencia urilizadas para obtener cada conclusion a partir de las prernisas.

a) «Si me tomo el dia libre, bien llueve 0 bien nieva», "Me tome el martes 0 el jucves b.ibre». «Hizo sol el maries». «No nevo el jueves».

68 'jmcll1:ltica discreta y sus aplicaciones

b) «Si eeno comidas picantcs, eruonces tengo sueiios cxuanos». «Tengo suefios extrafios si truena por la noche». «No he tenido suenos extraflos».

c) «Soy bien inteligente a bien afortunado». «No soy afonunado- «Si soy afortunado, me tocara la lOICria»,

d) «To do esrodiarue de ingenieria informatica tiene un ordenador», «Ralph no tiene ordenador», «Ana tiene un ordenador»,

e) «Lo que es bueno para las empresas, 10 es p3Hl m pais». «Lo que es bueno para tu pals es bueno para u». «Lo que cs bueno para las ernpresas es que consumas compulsivarnente».

f) «Todos los roedores men su comida», «Los rarones son roedores». «Los conejos no wen la comida». «Los rnurclelagos no son roedores».

8. Para cada una de estas premisas, <,-que conclusion 0 conclusiones relevanres se pueden dcrivar? Explica las reglas de inferencia usadas para obtener cada conclusion.

a) «Si juego al hockey, entonces estoy dolorido al dia siguiente». «U~O la banera de hidrornasaje si estoy clolorido».« 0 use la piscina de hidromasaje».

b) «Si trabajc, estn soleado 0 nublado a rachas», «Trabaje el ultimo tunes a el ultimo viernes». «El martes no esruvo soleado», «No estuvo nublado a rachas ('I viemes».

c) «Todos los insectos rienen seis patas». «Las libelulas son insectos», «Las ararias no tienen seis paras», «Las arafias se cornen a las libelulas».

d) «Todos los estudiantes tienen una cuenta de Internet», «Homer no riene una cuenta de Internet». «Maggie tiene una cuenta de Internet».

e) «Toda Ia cornida sana no sabe bien». «El tofu es sano»: «Td s610 comes 10 que sabe bien», «Tri no comes tofu». «Las hamburguesas grasientas no son sanas».

f) «Estey sofiando 0 estoy alucinado». I<No cstoy sofiando». «Si estoy alucinando, yeo elefantes corriendo par la carretera»,

9. Para cada [lila de estos argurnentos, explica que reglas de inferencia se han utilizado en cada paso

a) «Domingo, un e studiante de esta clase, sabe programar en J A V A. Todos los que sabcn prograrnar en JAVA pueden con .eguir trabajos bien remuneradcs. Por tanto, alguien en esta clase puede conseguir un trabajo bien rernunerado».

b) «A alguien de tu clase le gusta observar las ballenas. Todas las personas a las que les gusia observer las ballenas se preccupan por la contaminacion del oceano. POl' tanto, hay una persona en esta clase que se preocupa por la contarninacion del oceano»:

c) «Cada uno de los 93 cstudiantes de la cia. e tiene un ordenador. Todos los que tienen un ordenador pueden utilizar un editor de lex to. Par tanto, Zacarfas, un esrudiante de la clase, puede utilizar un editor de texto»

d) «Todo el rnundo en Santo Domingo vive a rnenos de JOO km del oceano. Alguien en Santo Domingo no

ha visto nunca el oceano. POI" tanto, alguien que vive a mcnos de 100 km del oceano no ha visto nunca el oceano».

10. Para cada uno de estos argumentos, cxplica que rcglas de inferencia sc han usado en cad a paso.

a) Linda, una estudianre de esta clase, tiene un descapotable rojo. A todos los que tiencn un descapotable rojo les han mullado alguna vez por exceso de velocidad: Por tanto, a alguien en csta clase lc han rnultaclo por cxceso de velocidad»,

b) «Cad a uno de los cinco cornpafieros de habitacion, Melisa, Aaron, Ralph, Vanesa y Kiko, han cursado la asignatura de rnatemarica discreta. Todos los estudiantes que han cursado la asignatura de matematica discreta pueden cursar 13 asignarura de algoriimos. POI tanto, los cinco companeros de habiracion pueden cursar la asignatura cle algornrnos eI afio que viene»,

c) «Todas las pclfculas producidas par John Sayles son maravillosas. John Sayles produjo LIlla pelicula sobre los mineros del carbon, Por tanto, hay una magnffica pellcula sobre los rnineros del carbon»,

d) «Hay alguien en la cia e que ha visitado Francia. Todos los que van a Francia visiian el Louvre. Por tanto, alguien en esta clase ha visitado el Louvre».

U. Para cada uno de estes argumentos determina si es correcio 0 incorrecto y explica por que.

a) Todos los estudiantes de la clase entienden J6giea.

Xavier es un estudianie de la clase, Par tanto, Xavier enticnde 16gica.

b) Todos los estudiantcs de ingenieria informatica cursan rnatematica discrora. Natacha cursa maternatica discreta, Por tanto, atacha es estudiante de ingenierfa informatica,

c) A todos los loros les gusia Ia fruta. Mi pajarc no es un lora. Por tanto, a mi pajaro no Ie gusta la fruta.

d) Los que comen vegcrales todos los ella estan sanos.

Linda no esta sana. POI" tanto, Linda no come vegetales iodos los df as.

12. Para cad a uno de estos argumentos derermina si son correctos a incorrectos y explica por que.

a) Todos los que han pasado por la universidad han vivido en una residencia, Mia no ha vivido en una residencia, Por tanto, Mia no 113 pasado por Ja universidad.

b) Los automoviles descapotables SOI1 divertidos de conducir, EI automovil de Isaac no es descapotable, Por tanto, el automovil de Isaac no es divertido de conducir,

c) A Quique le gustan las pelfculas de accion. A Quique Ie gusta In pelicula En la linea defuego. Por tanto, En fa linea de fuego es una pehcula de accion,

d) Todos los pescadores de langostas ponen al menos una docena de nasas. Hi 1 ari a cs un pescador de Iangostas, Por tanto, pone al menos una docena de nasas.

]3. Deterrnina si es correcro cada uno de los siguientes argumeruos. Si el argumento es correcto, <,-cmll es la regia

de inferencia utilizada? Si no io cs, (,que error logico ocurre?

a) Si n es un ruirnero real tal que n > 1, entonces n2 > I.

Supongarnos que n2 >1. Entonccs n > 1.

b) El mimero log23 es irraci anal si no es la razon de dos emeros. Par tanto, como log23 110 se puede escribir en la forma alb donde II y b son enteros, es irraeional.

c) Si n es un ntirnero real y n > 3, entonces /1' > 9. Supongamos que n2 ::; 9. Entonccs, II ::; 3.

d) Si n es un mirnero real y n > 2, entonces n2 > 4. Supongamos que /J .,; 2. Entonces, 112:::; 4.

14. Determina si estos argumentos son correctos.

a) «Si _A:l es irracional, enronces x es irracional, Par tanto, si xes irracional, se sigue que x' es irracional»,

b) «Si x' es irracional, entonces x es irracional. El ruimew x = ]t2 es irracional, Por tanto, el rurmero x = 1'( es irracional»,

15. l,Qlli;~ esta equivocado en este argurnento? Sea H(x) «r esta feliz". Dada la prcrnisa ::Jx H(x), concluirnos que H(Lola). Par tanto, Lola esta feliz.

16. l,Queesta equivocado en este argumcnto? Sea S(x, y) «r es mas bajo que y». Dada Ia premiss 3.5 Sts, Max), se sigue que S(Max. Max). Enrollees, par generalizacion de exisrencia, se sigue que 3x Sex. .r), por 10 que alguicn C~ mas bajo que el mismo.

17. Demuestra Ia proposicion Pro), donde P(n) es la proposicion «Si 11 es un entero positive mayor que I, cntouces n2 > n». lQue tipo de demostraci6n has ernplcado?

18. Demuestra la proposicion P( I), donde pen) es la proposicion «Si n es un cntcro positive, entonces n2 :?: I'm. "Que tipo de dernostracion has uti lizado?

19. Sea Pen) la proposicion «Si a y b son numerus reales positives, entonces (0 + b)" <:: (I" + b''», Dernuestra que P(I) es verdadera, i.Ql1C iipo de demostracion has usado?

20. Dernuestra que el cuadrarlo de un rnunero par cs uri nnrnero par uti I izando:

a) Una demostracion directa.

b) Una dernostracion indirecta.

c) Una demostracion pOT reduccion al absurdo.

21. Dernuestra que si n es UlJ entero y n3 + 5 es impar, entonces /'1 es par usando:

a) na demostracicn indirecta,

b) Una demostracion por reduccion al absurdo.

22. Dernuestra que si n es un enrero y 311 + 2 es par, entonces n es par usando:

a) Una demostracion indirccta.

h) Una dernostracion por reduccion al absurdo

23. DeT11ueslra que Ja suma de dos imp(lres es par.

Los fundarnentos: 16gica y demostracion, conjuntos Y funciones 69

24. Dernucstra que el producto de dos numeros impares es impar.

25. Dernucstra que la soma de un rnimero irracional y un mimero racional es un numero i rracional utilizando una demostracion por reduccion al absurdo.

Ui. Dcmuestra que el producto de dos numeros racionales es racional.

27. Dernuestra que se curnple, 0 que no, que el producto de dos mirneros irrac ionales es irrac ional,

28. Dernuesrra que se cumple, 0 que no, que cl producto de un rnimero racional no nulo y un irracional es irracional.

29. Demuestra que si x cs irracional, I [x lam bien 10 es.

30. Dernuestra que si x es racional y x,p 0, I/x tam bien 10 es.

31. Demuestra que 10 de cualquier grupo de 64 dias que se escojan deben corresponder al mismo dla de la sernana,

32. Demuestra que 3 de cualquier grupo de 25 dfas que se escojan deben correspondcr al mismo rnes del afio,

33. Muestra que si x e y son numeros reales, entonces max(x, y) + Illin(x, y) = x + y. tjndicacion. Usa una demostrucion par cases, siendo los des casos x?:.v y X < y).

34. Utiliza una dernostracion por casas pam rnostrar que min(a. min(b, e» = min(min(a, b), c) siernpre que a. by c sean nurneros reales.

35. Dernuestra la desigualdad triangular, que afirrna que si x e y son ruimcros reales, entonces I x I + I 'I ?: I x + y I (donde Ix I representa el valor absolute de x, que es igual ax para.r > 0 y es igual a-x para x < 0).

36. Demuestra que el cuadrado de un entero finaliza en 0,1,4, 5,609. ilndicocion: Sea /J = 10k + l, donde 1=0 1, ".,9).

37, Dern uestra que la potencia cuarta de un entero acaba en 0, 1,506.

38.

DemueSIT3 que si n es lin entero positivo, entonces n es

par si, y s610· i, 711 + 4 es par. j

Dernuestra que si n es un entero positive, entol1cei n es impar si, y solo si, 7n + 4 es impar.

39,

40. Demuestra que si m2 = n2 si, y s610 si, m = 11 0 m = -11.

41. Demuestra que se cumple, 0 que no, que si m y n SOn enreros tales que mn == l , entonces bien In = I Y 11 = I 0 bien In = - 1 Y 11 == - l .

42. Demuestra que esras tres sentencias son equivalernes, donde a y b son nurneros reales: (i) a es rnenor que b; (Ii) el valor medic de a y b es mayor qlle Q, y (iii) el'valor medio de a y b es menor que h.

70 Maternatica discreta y sus aplicaciones

43. Demuestra que esras trcs scnlencias son equivalerues: (i) 3x + 2 es un mirnero par; (it) x + 5 es un entero impar, y (iii) x· es lin entero par.

44. Dernuestra que estas rres seruencias son equivalentes: (i) x cs racional; (it) x/2 es racional, y (iii) 3x - 1 es racional.

45. Dernuesrra que estas tres sentencias son equivalenres: (i) xes irracional; (ii) 3x + 2 es irracional, y (iii) x/2 es i rraci anal.

46. i,Es correcto este razonamiento para encontrar las soluciones de la ecuacion ~ 2x2 - I =: x? (1). Se da .. J 2x2 - l == x; (2) 2t' - I = x2, elevando aJ cuadrado ambos terminos de (1); (3) x' - 1 = 0, restando Xl a ambos lados de (2); (4) (x - I )(x + I) = 0, factorizando la parte izquierda de (3); (5) x;;: lox == - 1, yaque si ab = 0 implica que bien a = 0 0 bien b = O.

47. i,Son correctos estes pa. os dados para enconrrar las soIuciones de la ecuacion ~ x + 3 = 3 - x? (1) Se parte de

_,Jx + 3 = 3 - x: (2) x + 3 '" ;1..2 - ox + 9, elevando al cuadrado am bos lados de (J); (3) ° =::"rl - 7 x + 6, restando x + 3 a ambos terminos de (2); (4) 0 = (x - l)(x - 6), actorizando la parte derecha de (3); (5) .r = lox = 6, ya que si ab = 0 implies que bien a = 0 0 bien b = O.

48. Demucsrra que hay un entero positive que es igual a la suma de los enteros positives menorcs 0 iguales que el. (,Es tu dernostracion constructiva 0 no constructiva?

49. Demuestra que hay cien erueros consecutivos que no son cuadrados perfectos. i,Es lu demosrracion constructiva 0 no constructiva?

50. Demuesrra que bien 2 . 10,00 + 15 0 bien 2· 10500 + 16 no es cuadrado perfecto. i,Es IU demostracion constructiva 0 no constructiva?

51. Dernuestra que hay un par de enteros positives consecutivos tales que uno es un cuadrado perfecto y eJ otro lin cubo perfecto.

52. Dernuestra que el producto de dos de los niimeros 6510CKJ _ R2OO1 + )117, 79l2r2 _ 9 99 + 2:'00 I Y 24449J _ 58192 + 71 m no

cs negative, i,Es ttl dernostracion constructiva 0 no constructiva? tlndicacion: .No internes evaluar estos mimcros'),

53. Dernuestra que cada una de las siguicntes seruencias se pueden utilizar para expresar el heche de que hay lIll iinico clemento x tal que PCx) cs verdadera. [Ten en cuenLa que, par el Problema 48 de la Seccion 1.3, esta es la sentencia S! P(x)].

a) 3..1.'v'y (P(y) H:r::: y)

b) ::Ix P(x) 1\ 'v'x'v'y (P(.x) 1\ P()') 4 X == y)

c) ::Ix (P(;:) 1\ 'v'}' (P(y) 4 X = )I)

54. Dernuestra que si a, bye son mimeros reales y a ;t. 0, entonces cxiste una solucion unica para la ecuacion ax + f) = c.

55. Supongamo que a y b son enteros imparcs, a ;t.. b. Muestra que existe un iinico entero c tal que I a - c I = I b - c I.

56. Muestra que si r es un mimero irracional, hay un unico entero II tal que la distancia entre r y II es menor que 1/].

57. Muestra que si 11 es un entero irnpar, entonces existe un unico entero k tal que II es la suma de k - 2 y k + 3.

58. Demuestra que dado un rnirnero real x existen dos unicos numeros nyc: tal que x = 11 + e, n eli un entcro y 0 :s: £ < 1.

59. Demucstra que dado un mimero real x existen dos unicos numeros n y E tal que x =; n - E, 11 cs un ernero yO:::; £ < .I.

60. Usa la regla de resolucion para mosrrar que las hipotesis «Allen es un mal chico 0 Hillary es una buena chica» y «Allen es un buen chico 0 David es!a contento» implican la conclusion «Hillary es una buena chica 0 David esra contcnto»,

61. Utiliza Ja regJa de resolucion para mostrar que las hipotesi «No llueve 0 Yvette riene un paraguas», «Yvette no tiene lin paraguas 0 ella no se moja» y «Llueve 0 Yvette no se rnoja» implican la conclusion "Yvette no se rnoja».

62. Muestra que las equivalencies p A op '" F e pueden derivar utilizando I:; regla de resolucion junto con el hecho de que una implicacion con hiporesis falsa es correcta. Undicacion: Sea q = r '" F CLJ311do se usc la regla de resolucion),

63. Usa la regia de resolucion para demostrar que la formula lp v q) r; ('lJ v q) A (1' v -,q) 1\ (-'P v 'q) no se cumple.

64. Dernuestra que se curnple, 0 que no, que si a y b son 116.meres racionales, entonces ab tambien 10 es,

65. Dernuestra que se cumple, 0 que no, que hay un mimero racional x y un irracional y tales que xYes irracional,

66. Muestra que puede verse que las proposiciones PI' P2' Po Y P4 son equivalenres dernostrando que PI H P4' P2 H p) Y PI H p; son verdaderas,

67. Mue 'Ira que puede verse que las proposiciones PI' P2, P" P. y Ps son equivalcntes demostrando que PI 4 P4, P;; --1 Pi' p" --1 P2' Pz --1 P5 Y P, 4 P3 son vcrdaderas.

68. Dcmuestra que un lahlero de ajedrez de 8 x 8 casillas se pucde cubrir cornpletamente ernpleando fichas de dornin6 (piezas de I x 2 casillas),

*69. Demuestra que es irnposible cubrir un tablero de ajedrez de 8 x 8 casillas con dos casillas quitadas en dos esquinas opuestas utilizando fichas de domino.

*70. EI Problema de Logica, tornado de WFF'N PROOF: The Game of Modern Logic, LIsa estas dos suposiciones:

I. «La logica es diffeil 0 11 pecos esrudiantes les gusta la logica».

2. «Si las matematicas son faciles, eruonces la logica no

es diffcil».

Formalizando estes dos enunciados a semcncias con variables proposicionales y conectivos 16gicos, determina cuales de estas conclusiones son validas para estas suposiciones,

a) Que las maternaticas no son faciles si a muchos estudiantes Ie gusta la 16gica.

b) Que a pocos estudiantes les gusta la logica si las rnaternaticas no son faciles,

c) Que las maternaticas no son faciles 0 la 16giea es diffcil,

d) Que Ia lcgica no es diffcil 0 las matematicas no son faciles,

e) Que si a pocos estudiantes les gusta la logica, entonces bien las rnaternaricas no Son faciles 0 bien la 16~ giea no es diffcil.

71. Demuestra que al menos uno de los numeros reales ai' a2, ... , ao es mayor 0 igual que el prornedio de ellos, l.Que clase de demOS1J3Ci6n has utilizado?

72. Usa el Problema 71 para mostrar que si se pan en los diez primeros mimeros enteros positives alrededor de un cfrculo, en cualquier orden, existen tres enteros en posiciones consecutivas alrededor del circulo que tienen una sum a mayor 0 igual q ue 17.

Conjuntos

Los fundarnentos: logica y dernostracion. conjuntos y Iunciones 71

73. Dernuestra que si n es UTI entero, estas cuatro serncncias son equivalentes: (i) n es par, (it) n + 1 es impar, (iii) 3n + 1 es impar, (iv) 311 es par.

74. Dernuestra que estas cuatro seruencias son equivalenics: (i) /12 es impar, (ii) 1 - n es par, (iii) /11 es impar, (iv) /72 + 1 es par.

75. i,Que reglas de inferencia se utilizan para establecerla conclusion del argumento de Lewis Carroll descriro en el Ejemplo 19 de la Secci6n J .3?

76. l.Que reglas de inferencia se utilizan para establecer la conclusion del argurnento de lewis Carroll descrito en el Ejernplo 20 de la Scccion 1.3?

*77. Deterrnina si esre argumento, tornado de Backhouse [13a86J, es correcto.

Si Superman fuese capaz y quisiese prevenir el crimen, 10 haria. Si Superman no fuese capaz de prevenir el crimen, seria debil; si no quisiese prevenir el crimen, serfs malevolente, Superman no previenc el crimen. Si SLl~ perrnan existiese, ni seria debit ni malevolente. POT tanto, Superman no existe.

INTRODUCCION

En este libra estudiarernos una gran varicdad de estrucruras discretas. Es.tas incluyen relaciones, que consisten en pares ordenados de elementos; combinaciones que son colecciones desordenadas de elementos, y grafos, que son conjuntos de vertices y aristas que conectan vertices. Adernas, ilustrarernos c6mo se utilizan estas y otras estructuras discretas en el model ado y la resolucion de problemas. En particular, se describiran machos ejemplos del uso de estructuras discretas en almacenarniento, cornunicacion y manipulacion de dales. En esta seccion estud icUT10S la esrrucrura discreta fundamental, sobre In que se construyen todas las dernas: el conjtmto.

Los conjuntos se utilizan para agrupar objetos. Generalmente, los objetos de un conjunto tienen propiedades sirnilares. Por ejemplo, todos los esrudiantes que estan rnatriculados en tu facultad forman un conjunto, De la misrna forma, todos los esrudiantes rnatriculados en la asignatura de rnarernatica discreta en cualquier facultad forman un conjunto. Ademas, aquellos alumnos de materruitica discreta rnatriculados en tu facultad forman otro conjunto que puede formarse tornando los elementos comunes de las dos primeras colecciones. El lenguaje de los conjuntos es lin medio para estudiar tales colecciones de forma organizada. continuacion proporcionamos una definicion de conjunto.

DEFINICION 1

Observa que el terrnino objeto se ha utilizado sin especificar que es. Esta definicion de conjuoto como una colecci6n de objetos, basada en la noci6n intuitiva de 10 que es un objcto, fue establecida por primera vez por el matematico aleman Georg Cantor en 1895. La teoria que resulta de esta de-