MATEMTICAS DISCRETASRichard JohnsonbaughJohnsonbaughMATEMTICASDISCRETASSexta edicinEste libro se dise para un curso de introduccin a las matemticas discretas. La exposicines clara y adecuada, adems de que contiene abundantes ejercicios.Esta edicin, igual que las anteriores, incluye temas como algoritmos, combinatoria, con-juntos, funciones e induccin matemtica. Tambin toma en cuenta la comprensin y con-struccin de pruebas y, en general, el reforzamiento matemtico.CAMBIOS DE LA SEXTA EDICIN El primer captulo de lgica y demostraciones se ampli en forma considerable. Seagregaron ejemplos de lgica en lenguajes de programacin. Ahora se presentan varios ejemplos de algoritmos antes de llegar a lanotacin de O mayscula. Un nuevo captulo de introduccin a la teora de nmeros. Este cap-tulo incluye resultados clsicos (como la divisibilidad, la infinitud delos primos, el teorema fundamental de la aritmtica), as como losalgoritmos de teora de nmeros. Nueva seccin de sugerencias para resolver problemas. Nuevas secciones de solucin de problemas para fun-ciones y teora de nmeros. El estilo del seudocdigo se ha actualizado deltipo Pascal al tipo Java. El nmero de ejemplos resueltos aumenta cerca de 600 y el nmero de ejerciciosaument a 4000.Vistenos en:www.pearsoneducacion.netSextaedicinLa obra tiene como apoyo el sitio Web:www.pearsoneducacion.net/johnsonbaughJohnsonbough 21x27 5/20/05 10:35 PM Page 1LGICAp q p o q; p. 2p q p y q; p. 2p no p; p. 5p q si p, entonces q; p. 8p q p si y slo si q; p. 12P Q P y Q son lgicamente equivalentes; p. 12 para todo; p. 19 existe; p. 22\ por lo tanto; p. 43NOTACIN DE CONJUNTOS{x1,, xn} conjunto que consta de los elementos x1,, xn; p. 76{x|p(x)} conjunto de los elementos x que satisfacen la propiedad p(x); p. 77x X x es un elemento de X; p. 77x X x no es un elemento de X; p. 77X = Y igualdad de conjuntos (X y Y tienen los mismos elementos); p. 77|X| nmero de elementos en X; p. 77 conjunto vaco; p. 77X Y X es un subconjunto de Y; p. 77X Y X es un subconjunto propio de Y; p. 79P(X) conjunto potencia de X (todos los subconjuntos de X); p. 79X Y X unin Y (todos los elementos en X o Y); p. 80unin de X1,, Xn(todos los elementos que pertenecen al menos a un conjunto de X1,, Xn); p. 83unin de X1, X2, (todos los elementos que pertenecen al menos a uno de X1, X2,); p. 83S unin de S (todos los elementos que pertenecen al menos a un conjunto en S); p. 83X Y X interseccin Y (todos los elementos en X y Y); p. 80interseccin de X1,, Xn(todos los elementos que pertenecen a todos los conjuntos X1, X2,, Xn); p. 83interseccin de X1, X2, (todos los elementos que pertenecen a todos los conjuntos X1, X2,); p. 83S interseccin de S (todos los elementos que pertenecen a todos los conjuntos de S); p. 83X Y diferencia de conjuntos (todos los elementos en X pero no en Y); p. 80X complemento de X (todos los elementos que no estn en X); p. 80(x, y) par ordenado; p. 83(x1,, xn) n-eada; p. 84X Y producto cartesiano de X y Y [pares (x, y) con x en X y y en Y]; p. 83LISTA DE SMBOLOSn

i =1Xi

i =1Xin

i =1Xi

i =1Xig gRELACIONESx R y (x, y) est en R (x est relacionada con y mediante la relacin R); p. 117[x] clase de equivalencia que contiene a x; p. 127R1relacin inversa [todo (x, y) que est en R]; p. 122R2 R1composicin de relaciones; p. 122x y x R y; p. 121FUNCIONESf (x) valor asignado a x; p. 88f : X Y funcin de X a Y; p. 87f g composicin de f y g; p. 97f1funcin inversa [todo (y, x) con (x, y) que est en f ]; p. 96f (n) = O(g(n)) |f (n)| C|g(n)| para n suficientemente grande; p. 158f (n) = (g(n)) c|g(n)| |f (n)| para n suficientemente grande;p. 158f (n) = (g(n)) c|g(n)| |f (n)| C|g(n)| para n suficientemente grande; p. 158CONTEOC(n, r) nmero de combinaciones r de un conjunto de n elementos (n!/[(n r)!r!]); p. 232P(n, r) nmero de permutaciones r de un conjunto de n elementos [n(n 1) (n r + 1)]; p. 231GRFICASG = (V, E) grfica G con conjunto de vrtices V y conjunto de aristas E; p. 320(v, w) arista; p. 320(v) grado del vrtice v; p. 333(v1,, vn) trayectoria de v1a vn; p. 330(v1,, vn), v1= vnciclo; p. 332Kngrfica completa en n vrtices; p. 325Km, ngrfica completa bipartita en m y n vrtices; p. 326w(i, j ) peso de la arista (i, j); p. 347Fi jflujo en la arista (i, j); p. 445Ci jcapacidad de la arista (i, j); p. 445(P, P ) cortadura en una red; p. 457PROBABILIDADP(x) probabilidad del resultado x; p. 250P(E) probabilidad del evento E; p. 251P(E|F) probabilidad condicional de E dado F [P(E F)/P(F)]; p. 255Q gQ gMATEMTICASDISCRETASQ gQ gMatemticas discretasSEXTA EDICINRichard JohnsonbaughDePaul University, ChicagoREVISIN TCNICA:ARIADNE SNCHEZ RUIZFacultad de Ingeniera, Mecnica y Elctrica Universidad Autnoma de Nuevo Len TRADUCCIN:MARCIA ADA GONZLEZ OSUNA Facultad de Ciencias Universidad Nacional Autnoma de Mxico Q gMATEMTICAS DISCRETAS. Sexta edicinJohnsonbaugh, RichardPEARSON EDUCACIN, Mxico, 2005ISBN: 970-26-0637-3rea: UniversitariosFormato: 21 27 cm Pginas 696Authorized translation from the English language edition, entitled Discrete mathematics 6thed., by Richard Johnsonbaugh published by PearsonEducation, Inc., publishing as PRENTICE HALL, INC., Copyright 2005. All rights reserved. ISBN 0-13-117686-2Traduccin autorizada de la edicin en idioma ingls, titulada Discrete mathematics 6/e de Richard Johnsonbaugh, publicada por PearsonEducation, Inc., publicada como PRENTICE HALL INC., Copyright 2005. Todos los derechos reservados. Esta edicin en espaol es la nica autorizada.Edicin en espaolEditor: Enrique Quintanar Duarte e-mail: enrique.quintanar@pearsoned.comEditor de desarrollo: Felipe Hernndez Carrasco Supervisor de produccin: Rodrigo Romero Villalobos Edicin en inglsExecutive Acquisitions Editor: George Lobell Editor-in-Chief: Sally Yagan Vice President/Director of Production and Manufacturing: David W. Riccardi Production Editor: Debbie Ryan Senior Managing Editor: Linda Mihatov Behrens Assistant Managing Editor: Bayani Mendoza de Leon Executive Managing Editor: Kathleen Schiaparelli Assistant Manufacturing Manager/Buyer: Michael Bell Manufacturing Manager: Trudy Pisciotti Marketing Manager: Halee Dinsey Marketing Assistant: Rachel Beckman Art Director: John Christiana Interior Design: Abigail Bass Cover Designer: Anthony Gemmellaro Creative Director: Carole AnsonDirector of Creative Services: Paul Belfanti Art Editor: Thomas Benfatti Editorial Assistant: Joanne Weldelken Front/Back Cover Image: Vasarely, Victor (1908-1977) ARS, NY Boo. 1978. Location: Private Collection, Monaco/Photo Credit: Erich Lessing / Art Resource, NYSEXTA EDICIN, 2005D.R. 2005 por Pearson Educacin de Mxico, S.A. de C.V. Atlacomulco No. 500, 5 piso Col. Industrial Atoto 53519, Naucalpan de Jurez, Edo. de MxicoE-mail: editorial.universidades@pearsoned.comCmara Nacional de la Industria Editorial Mexicana. Reg. Nm. 1031Prentice Hall es una marca registrada de Pearson Educacin de Mxico, S.A. de C.V. Reservados todos los derechos. Ni la totalidad ni parte de esta publicacin pueden reproducirse, registrarse o transmitirse, por un sistema de recu-peracin de informacin, en ninguna forma ni por ningn medio, sea electrnico, mecnico, fotoqumico, magntico o electroptico, por fotocopia,grabacin o cualquier otro, sin permiso previo por escrito del editor.El prstamo, alquiler o cualquier otra forma de cesin de uso de este ejemplar requerir tambin la autorizacin del editor o de sus representantes.ISBN 970-26-0637-3Impreso en Mxico. Printed in Mexico.1 2 3 4 5 6 7 8 9 0 08 07 06 05Q gPrefacio XI Lgica y demostraciones 11.1 Proposiciones 21.2 Proposiciones condicionales y equivalencia lgica 81.3 Cuantificadores 171.4 Cuantificadores anidados 291.5 Demostraciones 361.6 Pruebas por resolucin 501.7 Induccin matemtica 53Rincn de solucin de problemas: Induccin matemtica 631.8 Forma fuerte de induccin y la propiedad del buen orden 65Notas 70Repaso del captulo 71Autoevaluacin del captulo 73Ejercicios para computadora 75 El lenguaje de las matemticas 762.1 Conjuntos 762.2 Funciones 87Rincn de solucin de problemas: Funciones 1022.3 Sucesiones y cadenas 103Nota 112Repaso del captulo 112Autoevaluacin del captulo 114Ejercicios para computadora 115CONTENIDO12Q g Relaciones 1163.1 Relaciones 1163.2 Relaciones de equivalencia 125Rincn de solucin de problemas: Relaciones de equivalencia 1313.3 Matrices de relaciones 1323.4 Bases de datos relacionales 137Nota 142Repaso del captulo 142Autoevaluacin del captulo 142Ejercicios para computadora 144 Algoritmos 1454.1 Introduccin 1454.2 Ejemplos de algoritmos 1494.3 Anlisis de algoritmos 156Rincn de solucin de problemas: Diseo y anlisis de un algoritmo 1714.4 Algoritmos recursivos 173Notas 180Revisin del captulo 180Autoevaluacin del captulo 181Seccin de ejercicios de repaso 182 Introduccin a la teora de nmeros 1835.1 Divisores 1835.2 Representaciones de enteros y algoritmos enteros 1925.3 El algoritmo euclidiano 205Rincn de solucin de problemas: Composicin del importe postal 2145.4 El sistema criptogrfico de llave pblica RSA 215Notas 217Repaso del captulo 217Autoevaluacin del captulo 218Ejercicios para computadora 219 Mtodos de conteo y el principio del palomar 2206.1 Principios bsicos 220Rincn de solucin de problemas: Conteo 2286.2 Permutaciones y combinaciones 229Rincn de solucin de problemas: Combinaciones 2406.3 Algoritmos para generar permutaciones y combinaciones 2416.4 Introduccin a la probabilidad discreta 247VIII Contenido3456Q g6.5 Teora de probabilidad discreta 2506.6 Permutaciones y combinaciones generalizadas 2616.7 Coeficientes binomiales e identidades combinatorias 2666.8 El principio del palomar 271Notas 275Repaso del captulo 275Autoevaluacin del captulo 276Ejercicios para computadora 278 Relaciones de recurrencia 2797.1 Introduccin 2797.2 Solucin de relaciones de recurrencia 290Rincn de solucin de problemas: Relaciones de recurrencia 3027.3 Aplicaciones al anlisis de algoritmos 305Notas 315Repaso del captulo 315Autoevaluacin del captulo 316Ejercicios para computadora 317 Teora de grficas 3188.1 Introduccin 3188.2 Trayectorias y ciclos 329Rincn de solucin de problemas: Grficas 3398.3 Ciclos hamiltonianos y el problema del agente viajero 3408.4 Un algoritmo de la ruta ms corta 3478.5 Representaciones de grficas 3528.6 Isomorfismos de grficas 3568.7 Grficas planas 3638.8 Locura instantnea 369Notas 373Repaso del captulo 373Autoevaluacin del captulo 375Ejercicios para computadora 377 rboles 3799.1 Introduccin 3799.2 Terminologa y caracterizacin de rboles 386Rincn de solucin de problemas: rboles 3919.3 rboles de expansin 3929.4 rboles de expansin mnima 3989.5 rboles binarios 4039.6 Recorridos de rboles 4099.7 rboles de decisiones y tiempo mnimo para ordenar 414Contenido IX789Q g9.8 Isomorfismos de rboles 4209.9 rboles de juegos 429Notas 437Repaso del captulo 437Autoevaluacin del captulo 439Ejercicios para computadora 442 Modelos de redes 44410.1 Introduccin 44410.2 Algoritmo de flujo mximo 44910.3 Teorema de flujo mximo y corte mnimo 45710.4 Acoplamiento 461Rincn de solucin de problemas: Acoplamiento 466Notas 467Repaso del captulo 467Autoevaluacin del captulo 468Ejercicios para computadora 469 lgebras booleanas y circuitos combinatorios 47011.1 Circuitos combinatorios 47011.2 Propiedades de los circuitos combinatorios 47711.3 lgebras booleanas 482Rincn de solucin de problemas: lgebras booleanas 48611.4 Funciones booleanas y simplificacin de circuitos 48811.5 Aplicaciones 493Notas 501Repaso del captulo 501Autoevaluacin del captulo 502Ejercicios para computadora 504 Autmatas, gramticas y lenguajes 50612.1 Circuitos secuenciales y mquinas de estado finito 50612.2 Autmata de estado finito 51112.3 Lenguajes y gramticas 51712.4 Autmata de estado finito no determinstico 52512.5 Relaciones entre lenguajes y autmatas 531Notas 537Repaso del captulo 538Autoevaluacin del captulo 539Ejercicios para computadora 540X Contenido101112Q g Geometra para clculo 54213.1 Problema del par ms cercano 54213.2 Algoritmo para calcular el casco convexo 547Notas 554Repaso del captulo 554Autoevaluacin del captulo 554Ejercicios para computadora 555 Matrices 556 Repaso de lgebra 560 Seudocdigo 571Referencias 577Sugerencias y soluciones para ejercicios seleccionados 582ndice 662Contenido XICBA13Q gQ gEste libro fue diseado para un curso de introduccin a las matemticas discretas, basadoen mi experiencia como profesor de la asignatura durante muchos aos. Los prerrequisitosde matemticas formales son mnimos; no se requiere clculo. No hay requisitos de cien-cias de la computacin. El libro incluye ejemplos, ejercicios, figuras, tablas, secciones desolucin de problemas, secciones que contienen sugerencias para resolver problemas, sec-ciones de repaso, notas, revisin del captulo, autoevaluaciones y ejercicios para realizar encomputadora con la finalidad de ayudar al estudiante a dominar las matemticas discretas.Aprincipios de la dcada de 1980, haba pocos libros de texto adecuados para un cur-so de introduccin a las matemticas discretas. Sin embargo, era necesario un curso queconsolidara la madurez matemtica de los estudiantes y su habilidad para manejar la abs-traccin, que adems incluyera temas tiles como combinatoria, algoritmos y grficas. Laedicin original de este libro (1984) atendi esta necesidad e influy de manera significa-tiva en los cursos de matemticas discretas. Con el paso del tiempo, los cursos de matem-ticas discretas se justificaron para diferentes grupos, que incluyeron estudiantes dematemticas y ciencias de la computacin. Un panel de la Mathematical Association ofAmerica (MAA) apoy un curso de un ao de matemticas discretas. El Comit de Activi-dades Educativas del Institute of Electrical and Electronics Engineers (IEEE) recomendun curso de matemticas discretas en el primer ao. Las guas de acreditacin de la Asso-ciation for Computing Machinery (ACM) y la IEEE hacen obligatorio un curso de mate-mticas discretas. Esta edicin, al igual que las anteriores, incluye temas como algoritmos,combinatoria, conjuntos, funciones e induccin matemtica para cubrir las necesidades deestos grupos. Tambin toma en cuenta la comprensin y construccin de pruebas y, en ge-neral, el reforzamiento de la madurez matemtica.PREFACIOLos cambios en la sexta edicin de este libro surgieron a partir de comentarios y peticionesde numerosos usuarios y revisores de las ediciones anteriores. Estos cambios son los si-guientes: El primer captulo de lgica y demostraciones fue ampliado en forma considerable.La seccin de cuantificadores en la quinta edicin fue dividida en dos secciones. Laprimera seccin de cuantificadores (seccin 1.3) estudia las afirmaciones de loscuantificadores sencillos, y la siguiente (seccin 1.4) analiza los cuantificadores ani-dados. La seccin de induccin matemtica en la quinta edicin tambin fue divididaen dos secciones. La primera (seccin 1.7) introduce la induccin en la que el pasoinductivo consiste en suponer S(n) y probar S(n + 1). Se agreg a esta seccin unanlisis de las invariantes de un ciclo. La segunda seccin (1.8) contina con la in-duccin fuerte y la propiedad de buen orden. Como ejemplo del uso de la propiedaddel buen orden, se demuestra el teorema del cociente-residuo.Los materiales de exposicin, ejemplos y motivacin se ampliaron en todo el ca-ptulo. Se agregaron ejemplos de lgica en lenguajes de programacin (por ejemplo,el uso de and, or, not y las leyes de De Morgan). Con el fin de dar mayor claridad, labarra superior para denotar negacin se sustituy por . Aparece una explicacin msCambios respecto a la quinta edicinXIIIQ gdetallada de las condiciones necesaria y suficiente. Se aadieron ejemplos para mos-trar la relacin entre el lenguaje normal y la lgica simblica. En todo el captulo hayms ejemplos de demostracin de afirmaciones y de cmo construir las demostracio-nes. En este captulo se aument el nmero de ejemplos resueltos de 59 a 90, y el n-mero de ejercicios de 391 a 521. En el captulo 2, se agregaron varios ejemplos para mostrar cmo es posible usar el ma-terial del captulo 1 para probar afirmaciones referentes a conjuntos, funciones, suce-siones y cadenas (por ejemplo, cmo probar que una funcin especfica es uno a uno). Ahora se presentan varios ejemplos de algoritmos antes de llegar a la notacin de Omayscula y otras relacionadas (secciones 4.1 y 4.2), que proporcionan una introduc-cin ms suave y motivada al formalismo que le sigue. Se menciona que muchos al-goritmos modernos no tienen todas las propiedades de los algoritmos clsicos (porejemplo, muchos algoritmos modernos no son generales, determinsticos o finitos).Para ilustrar el punto, se da un ejemplo de un algoritmo aleatorizado (ejemplo 4.2.4). Un nuevo captulo (el 5) de introduccin a la teora de nmeros combina material de laquinta edicin (como la representacin de enteros, el mximo comn divisor) y amplaalgunos temas (como la teora algortmica de nmeros). Este captulo incluye resultadosclsicos (como la divisibilidad, el carcter infinito de los primos, el teorema fundamen-tal de la aritmtica), as como los algoritmos de teora de nmeros: por ejemplo, el al-goritmo euclidiano para encontrar el mximo comn divisor, cmo elevar a unexponente usando cuadrados repetidos, cmo calcular s y t tales que mcd(a, b) = sa + tb,y cmo calcular el inverso del mdulo de un entero. La aplicacin principal es el siste-ma criptogrfico de llave pblica RSA(seccin 5.4). Los clculos requeridos por el sis-tema criptogrfico se pueden realizar usando los algoritmos desarrollados en el captulo. El apartado de sugerencias para resolver problemas se agregaron al final de muchassecciones, en especial en los primeros captulos. Como el nombre lo dice, ayudan alestudiante a centrarse en las tcnicas requeridas para resolver los problemas. Las su-gerencias para resolver problemas, que aparecen al final de las secciones, enfatizany ayudan a comprender las tcnicas para resolver los problemas de la seccin. Hay nuevas secciones de solucin de problemas para funciones y teora de nmeros. El estilo del seudocdigo se ha actualizado del tipo Pascal al tipo Java (que tambinse parece a C y C++). Es ms probable que el estudiante est familiarizado con esteestilo. Adems, la descripcin del seudocdigo se ha cambiado a los apndices(apndice C), lo que hace posible dar ejemplos de seudocdigos antes (para quienesestn interesados). Se agregaron diversos libros y artculos recientes a la lista de referencias. Las refe-rencias de varios libros se actualizaron para considerar las ltimas ediciones. El nmero de ejemplos resueltos aument a cerca de 600. (Haba aproximadamente500 en la quinta edicin). El nmero de ejercicios aument a casi 4000. (Haba cerca de 3500 en la quinta edicin).XIV PrefacioEste libro incluye: Lgica (incluyendo cuantificadores), demostraciones, pruebas por resolucin e in-duccin matemtica (captulo 1). En el ejemplo 1.4.15 se presenta un juego de lgi-ca, que ofrece una manera alternativa para determinar si una funcin proposicionalcuantificada es verdadera o falsa. Conjuntos, funciones, sucesiones, notaciones de suma y producto, cadenas y relacio-nes (captulo 2 y 3), incluyendo ejemplos que despiertan la motivacin, como el dela introduccin a las funciones de dispersin (hashing) y los generadores de nmerosseudoaleatorios (seccin 2.2), una aplicacin de rdenes parciales en la programa-cin de tareas (seccin 3.1) y las bases de datos relacionales (seccin 3.4).Contenido y estructuraQ g Un anlisis exhaustivo de algoritmos, algoritmos recursivos y anlisis de algoritmos(captulo 4). Adems, se da un enfoque algortmico en todo el libro. Los algoritmos es-tn escritos en una forma flexible de seudocdigo. (El libro no supone requisitos decomputacin; la descripcin del seudocdigo que se usa se presenta en el apndice C).Entre los algoritmos presentados estn el de enlosado (seccin 4.4), el algoritmo eucli-diano para encontrar el mximo comn divisor (seccin 5.3), el algoritmo para codifi-car la llave pblica RSA (seccin 5.4), la generacin de combinaciones y permutaciones(seccin 6.3), el merge sort (seccin 7.3), el algoritmo de la ruta ms corta de Dijkstra(seccin 8.4), los algoritmos de regreso (seccin 9.3), la bsqueda a lo ancho y a pro-fundidad (seccin 9.3), el recorrido de rboles (seccin 9.6), la evaluacin de un rbolde juego (seccin 9.9), el flujo mximo en una red (seccin 10.2), el par ms cercanode puntos (seccin 13.1) y el clculo del casco convexo (seccin 13.2). Un anlisis completo de las notaciones O mayscula, omega y theta para el crecimien-to de las funciones (seccin 4.3). Disponer de todas estas notaciones hace posible ha-cer afirmaciones precisas acerca del crecimiento de funciones y el tiempo y espaciorequeridos por los algoritmos. Una introduccin a la teora de nmeros (captulo 5). Combinaciones, permutaciones, probabilidad discreta y el principio del palomar (ca-ptulo 6). Dos secciones opcionales (6.4 y 6.5) presentan la probabilidad discreta. Relaciones de recurrencia y su aplicacin al anlisis de algoritmos (captulo 7). Grficas, incluyendo modelos de cobertura de una grfica de computadoras parale-las, recorrido del caballo, ciclos de Hamilton, isomorfismos de grficas y grficasplanas (captulo 8). El teorema 8.4.3 da una demostracin elegante, breve y sencillade que el algoritmo de Dijkstra es correcto. rboles, que incluyen rboles binarios, recorridos del rbol, rbol de expansin m-nima, tiempo mnimo para ordenar e isomorfismos de rboles (captulo 9). Redes, el algoritmo del flujo mximo y acoplamiento (captulo 10). Un anlisis de lgebras booleanas que hace hincapi en la relacin de stas con loscircuitos combinatorios (captulo 11). Un enfoque de autmata que resalta el modelado y las aplicaciones (captulo 12). El cir-cuito flip-flop SR se estudia en el ejemplo 12.1.11. Los fractales, incluyendo el copo denieve de Von Koch, se describen por gramticas de tipo especial (ejemplo 12.3.19). Una introduccin a la geometra para el clculo (captulo 13). Apndices de matrices, lgebra bsica y seudocdigo. Se resalta la importancia de la interrelacin de los diferentes temas. Como ejemplos, lainduccin matemtica tiene una relacin estrecha con los algoritmos recursivos (seccin4.4); la sucesin de Fibonacci se usa en el anlisis del algoritmo euclidiano (seccin 5.3);muchos ejercicios a lo largo del libro requieren induccin matemtica; se demuestra c-mo se caracterizan las componentes de una grfica mediante la definicin de una relacinde equivalencia sobre el conjunto de vrtices (vea el anlisis que sigue al ejemplo 8.2.13);se cuentan los vrtices de rboles binarios de n vrtices (teorema 9.8.12). Se hace hincapi en la lectura y las demostraciones. Casi todas las pruebas de los teo-remas se ilustran con figuras que incluyen anotaciones. Algunas secciones separadas(los rincones de solucin de problemas) muestran al estudiante cmo abordar y re-solver problemas y cmo desarrollar demostraciones. Las secciones especiales de su-gerencias para resolver problemas resaltan las tcnicas principales de la seccin. Un gran nmero de aplicaciones, en especial de computacin. Figuras y tablas para ilustrar los conceptos, para mostrar cmo funcionan los algorit-mos, para derivar pruebas y para aclarar el material. Las figuras ilustran las pruebasde los teoremas. Las leyendas de estas figuras brindan explicaciones adicionales ymayor comprensin de la demostracin. Ejercicios de repaso de la seccin. Secciones de notas con sugerencias para otras lecturas.Prefacio XVQ g Repasos de los captulos. Autoevaluacin en cada captulo. Ejercicios para computadora. Una seccin de referencias que contiene 159 referencias. Contraportadas que resumen la notacin matemtica y de los algoritmos utilizadosen el libro.Cada captulo se organiza como sigue:Descripcin generalSeccinSeccin de ejercicios de repasoSeccin de ejerciciosSeccinSeccin de ejercicios de repasoSeccin de ejercicios...NotasRepaso del captuloAutoevaluacin del captuloEjercicios para computadoraEl apartado de ejercicios de repaso revisa los conceptos clave, definiciones, teore-mas, tcnicas, etctera, de la seccin. Todos los ejercicios de repaso tienen respuestas al fi-nal del libro. Aunque la intencin es repasar cada seccin, estos ejercicios tambin sepueden usar para la elaboracin de exmenes muestra.Las notas contienen sugerencias para otras lecturas. Las revisiones de los captulosproporcionan listas de referencia de los conceptos importantes. Las autoevaluaciones con-tienen cuatro ejercicios por seccin, con respuestas al final del libro.Los ejercicios para computadora incluyen proyectos, implementaciones de algunosalgoritmos y otras actividades relacionadas con la programacin. Aunque no hay requisitosde programacin para este libro, ni se pretende hacer una introduccin a la programacin,estos ejercicios se incluyen para quienes deseen explorar los conceptos de matemticas dis-cretas con una computadora.Por ltimo, casi todos los captulos incluyen una seccin de solucin de problemas.El libro contiene cerca de 4000 ejercicios, 147 de los cuales son para computadora. Losejercicios que parecen ms difciles que otros se indican con el smbolo . Los ejercicioscon nmeros en cursivas (cerca de un tercio de ellos) tienen una sugerencia o la solucinal final del libro. Las soluciones a los ejercicios restantes se pueden encontrar en la Guadel instructor. Es claro que un puado de ejercicios requieren del clculo. No se usan con-ceptos de clculo en el cuerpo principal del libro y, excepto por estos pocos ejercicios, nose necesita clculo para resolverlos.El libro contiene cerca de 600 ejemplos resueltos, que muestran a los estudiantes cmoabordar problemas en matemticas discretas, presentan las aplicaciones de la teora, acla-ran las demostraciones y ayudan como motivacin del material.XVI PrefacioEjerciciosEjemplosQ gLas secciones tituladas Rincn de solucin de problemas ayudan al estudiante a atacar y re-solver problemas, y le muestran cmo desarrollar demostraciones. Escritos en un estilo in-formal, cada rincn es una seccin que, por s misma, sigue el anlisis del tema delproblema. En lugar de presentar simplemente una prueba o una solucin al problema, enestas secciones se intenta mostrar los caminos alternativos para atacar el problema, se ana-liza qu buscar al tratar de resolverlo y se presentan las tcnicas para encontrar solucionesy para elaborar demostraciones.Cada seccin de solucin de problemas comienza con el enunciado de un problema.Despus de hacer el planteamiento se analizan las maneras de abordarlo. Siguen a este anli-sis las tcnicas para encontrar una solucin. Una vez que se encuentra una respuesta, se dauna solucin formal para mostrar la manera correcta de escribirla. Por ltimo, se resumen lastcnicas de solucin de problemas presentadas en la seccin, incluyendo un apartado de co-mentarios que analiza las relaciones con otros temas de matemticas y computacin, despier-ta la motivacin para resolver el problema y da una lista de referencias para otras lecturasrelacionadas. Algunos rincones de solucin de problemas concluyen con ejercicios.Gua del instructor (en ingls) sin costo para los profesores que adopten este libro. Debe so-licitarse al representante local de Pearson Educacin. La Gua del instructor contiene lassoluciones de los ejercicios no incluidas en el libro.www.pearsoneducacion.net/johnsonbaughse ha enriquecido mucho respecto a la pgina de la edicin anterior. El nuevo sitio con-tiene Mayores explicaciones del material difcil y vnculos a otros sitios para obtener in-formacin adicional de los temas de matemticas discretas. El icono www al margenseala que la pgina Web del libro contiene ms explicaciones o un vnculo. Diapositivas de PowerPoint. Material complementario Programas de computadora Una lista de erratas.Recib comentarios tiles de muchas personas, entre ellas Gary Andrus, Kendall Atkin-son, Andr Berthiaume, Gregory Brewster, Robert Busby, David G. Cantor, Tim Carroll,Joseph P. Chan, Hon-Wing Cheng, I-Ping Chu, Robert Crawford, Henry DAngelo,Jerry Delazzer, Br. Michael Driscoll, Carl E. Eckberg, Herber Enderton, Susana Epp,Gerald Gordon, Jerrold Grossman, Reino Hakala, Mark Herbster, Steve Jost, Martin Ka-lin, Nicholas Krier, Warren Krueger, Glenn Lancaster, Donald E. G. Malm, Nick Mes-hes, Kevin Phelps, Jenni Piane, Mansur Samadzadeh, Sigrid (Anne) Settle, James H.Stoddard, Chaim Goodman Strauss, Michael Sullivan, Edward J. Williams y HanyiZhang. Agradezco tambin a todos los usuarios de mi libro por sus valiosas cartas y co-rreos electrnicos.WWWPrefacio XVIIRincones de solucin de problemasComplemento para el instructorPgina de InternetAgradecimientosQ gUn agradecimiento especial por esta edicin es para George F. Bachelis, de WayneState University, por las correcciones y la retroalimentacin de su grupo de alumnos, y pa-ra Bob Fisher, mi colega en DePaul, por atraer mi atencin a algunos ejercicios agradablesde conjuntos convexos que se pueden resolver usando induccin matemtica.Por la revisin del manuscrito de esta edicin, doy gracias a:Scott Annin, California State University, FullertonBrendan Frey, University of TorontoDennis Garity, Oregon State UniversityAaron Keen, California Polytechnic State University, San Luis ObispoMiguel Lerma, Northwestern UniversityTruc Nguyen, Bowling Green State UniversityCraig Jensen, University of New OrleansRandall Pruim, Calvin CollegeDavid Stewart, University of IowaSuely Oliveira, University of IowaBogdan Suceava, California State University, FullertonAnthony S. Wojcik, Michigan State UniversityAgradezco a mi amable editora, Patricia Johnsonbaugh, por marcar cada uno de loscerca de 4000 ejercicios con codificacin mstica, por cuidar numerosos detalles, detectartexto que no pretend escribir, mejorar la exposicin y sugerir cambios que mejoraron el libro.Estoy en deuda con Helmut Epp, decano de la Escuela de ciencias de la compu-tacin, telecomunicaciones y sistemas de informacin en DePaul University, por propor-cionarme su tiempo y alentarme en el desarrollo de esta edicin y las anteriores.He recibido apoyo constante del personal de Prentice Hall. En especial, agradezco a George Lobell, editor ejecutivo, por su ayuda; a Jennifer Brady, asistente editorial, y aDebbie Ryan, supervisor de produccin.Richard JohnsonbaughXVIII PrefacioQ g1.1 Proposiciones1.2 Proposiciones condicionalesy equivalencia lgica1.3 Cuantificadores1.4 Cuantificadores anidados1.5 Demostraciones1.6 Pruebas por resolucin1.7 Induccin matemticaRincn de solucin de problemas: induccinmatemtica1.8 Forma fuerte de induccin yla propiedad del buen ordenNotasRepaso del captuloAutoevaluacin del captuloEjercicios para computadoraLgica es el estudio del razonamiento; se refiere especficamente a si el razonamiento escorrecto. La lgica se centra en la relacin entre las afirmaciones y no en el contenido deuna afirmacin en particular. Considere, por ejemplo, el siguiente argumento:Todos los matemticos usan sandaliasCualquiera que use sandalias es un algebristaPor lo tanto, todos los matemticos son algebristasEn el sentido tcnico, la lgica no ayuda a determinar si alguna de estas afirmaciones escierta; sin embargo, si las primeras dos afirmaciones son ciertas, la lgica asegura que laafirmacintodos los matemticos son algebristastambin es cierta.Los mtodos lgicos se usan en matemticas para demostrar teoremas y, en las cien-cias de la computacin, para probar que los programas hacen lo que deben hacer. Suponga,por ejemplo, que se asigna a un estudiante el desarrollo de un programa para calcular lastrayectorias ms cortas entre ciudades. Es necesario que el programa acepte como entradaun nmero arbitrario de ciudades y las distancias entre las ciudades con conexin directapor carretera, y que produzca como salida las trayectorias (rutas) ms cortas entre cada pardistinto de ciudades. Despus de escribir el programa, es fcil para el estudiante probarlocon un nmero reducido de ciudades. Con papel y lpiz, puede enumerar todas las trayec-torias posibles entre pares de ciudades y encontrar las ms cortas. Esta solucin por fuer-za bruta se compara con la salida del programa. Sin embargo, para un nmero grande deciudades, la tcnica de la fuerza bruta sera tardada. Cmo puede el estudiante estar se-guro de que el programa trabaja bien para muchos datos (casi seguro el tipo de entrada conla que el profesor probara el programa)? l tendr que usar la lgica para argumentar queel programa es correcto. El argumento puede ser informal o formal usando las tcnicas pre-sentadas en este captulo; pero se requerir un argumento lgico.Entender la lgica tambin resulta til para aclarar la escritura comn. Por ejemplo,en una ocasin, se public el siguiente decreto en Naperville, Illinois: Ser ilegal que una1LGICA YDEMOSTRACIONESCaptulo 1WWWLgica, lgica, lgica. La lgica es el principio de lasabidura, Valeria, no el fin.STAR TREK VI: EL PAS SIN DESCUBRIR Esta seccin se puede omitir sin prdida de continuidad.gpersona tenga ms de tres perros y tres gatos en su propiedad dentro de la ciudad. Un ciu-dadano que tena cinco perros y ningn gato, violaba el decreto? Piense en esta preguntaahora y analcela (vea ejercicio 54, seccin 1.1) despus de leer la seccin 1.1.Cules oraciones de la a) a la e) son verdaderas o falsas (pero no ambas)?a) Los nicos enteros positivos que dividena 7 son 1 y el mismo 7.b) Alfred Hitchcock gan un premio de la Academia en 1940 por la direccin deRebeca.c) Para todo entero positivo n, existe un nmero primomayor que n.d) La Tierra es el nico planeta en el universo que tiene vida.e) Compra dos boletos para el concierto de rock Unhinged Universe del viernes.La oracin a), que es otra manera de decir que el 7 es primo, es verdadera.La oracin b) es falsa. Aunque Rebeca gan el premio de la Academia por lamejor pelcula de 1940, John Ford gan el premio por dirigir Las vias de la ira. Es unhecho sorprendente que Alfred Hitchcock nunca haya ganado un premio de la Academiapor mejor direccin.La oracin c), que es otra forma de decir que el nmero de primos es infinito, es ver-dadera.La oracin d) puede ser verdadera o falsa (pero no ambas), sin embargo en este mo-mento se ignora.La oracin e) no es verdadera ni falsa [esta oracin es una orden].Una oracin que es verdadera o falsa, pero no ambas, se llama una proposicin. Lasoraciones a) a la d) son proposiciones, mientras que la oracin e) no es una proposicin. Escomn que una proposicin se exprese como una oracin declarativa (y no como pregun-ta, orden, exclamacin, etctera). Las proposiciones son los bloques bsicos de construc-cin de cualquier teora de lgica.Se usarn variables, como p, q y r, para representar las proposiciones, casi comose usan letras en lgebra para representar nmeros. Tambin se usar la notacinp: 1 +1 = 3para definir que p es la proposicin 1 + 1 = 3.Al hablar y escribir de forma normal, las proposiciones se combinan usando conec-tores como y y o. Por ejemplo, las proposiciones est lloviendo y hace fro se puedencombinar para formar la proposicin est lloviendo y hace fro. Acontinuacin se dan lasdefiniciones formales de y y o.Sean p y q proposiciones.La conjuncin de p y q, denotada por p q, es la proposicinp y q.La disyuncin de p y q, denotada por p q, es la proposicinp o q.Un operador binario sobre un conjunto*X, asigna a cada par de elementos en X unelemento de X (vea la definicin 2.2.44). El operador asigna a cada par de proposiciones2 Captulo 1 Lgica y demostraciones1.1 ProposicionesDefinicin 1.1.1 Divide se refiere a divisin exacta. De manera ms formal, se dice que un entero diferente de cero d divide aun entero m si existe un entero q tal que m = dq. A q se le llama el cociente. Se explorarn los enteros con detalleen el captulo 5. Un entero n > 1 es primo si los nicos enteros positivos que dividen a n son 1 y el mismo n. Por ejemplo, 2, 3 y11 son nmeros primos.*Un conjunto es una coleccin de objetos. Por ejemplo, el conjunto de enteros positivos consiste en los enteros 1,2, . . . Los conjuntos se estudian con detalle en la seccin 2.1.gEjemplo 1.1.2 p y q la proposicin p q. Entonces, es un operador binario sobre las proposiciones. Eloperador tambin es un operador binario sobre las proposiciones.Sip: Est lloviendo,q: Hace fro,entonces la conjuncin de p y q esp q: Est lloviendo y hace fro.La disyuncin de p y q esp q: Est lloviendo o hace fro.El valor de verdad de la conjuncin p q est determinado por los valores verdade-ros de p y q, y la definicin se basa en la interpretacin usual de y. Considere la propo-sicinp q: Est lloviendo y hace frodel ejemplo 1.1.2. Si est lloviendo (es decir, p es verdadera) y tambin hace fro (es decir,q tambin es verdadera), entonces la proposicinp q: Est lloviendo y hace frose considerara verdadera. Sin embargo, si no est lloviendo (esto es, p es falsa) o si no ha-ce fro (q es falsa) o ambas, entonces la proposicinp q: Est lloviendo y hace frose considerara falsa.Los valores de verdad de las proposiciones, tales como conjunciones o disyunciones,se pueden describir por las tablas de verdad. La tabla de verdad de una proposicin P, for-mada por las proposiciones individuales p1, . . . , pn, enumera todas las posibles combina-ciones de los valores de verdad para p1, . . . , pn, donde Vdenota verdadero y F denota falso,y da la lista de valores de verdad de P para cada combinacin. Se usa una tabla de verdadpara dar la definicin formal de los valores de verdad de p q.Los valores de verdad de la proposicin p q se definen por la tabla de verdadObserve que en la tabla de verdad de la definicin 1.1.3 se dan las cuatro combina-ciones posibles (cuatro alternativas posibles) de asignaciones de verdad para p y q.La definicin 1.1.3 establece que la conjuncin p q es verdadera siempre que p yq sean ambas verdaderas; de otra manera, p q es falsa.Sip: Una dcada tiene 10 aos,q: Un milenio tiene 100 aos,1.1 Proposiciones 3Definicin 1.1.3 p q p qT T TT F FF T FF F FEjemplo 1.1.4 VVVVVgentonces p es verdadera, q es falsa (un milenio tiene 1000 aos) y la conjuncinp q: Una dcada tiene 10 aos y un milenio tiene 100 aoses falsa.Casi todos los lenguajes de programacin definen y justo como la definicin 1.1.3. Por ejem-plo, en el lenguaje de programacin Java, el y (lgico) se denota por &&, y la expresines verdadera precisamente cuando el valor de la variable x es menor que 10 (esto es,x < 10 es cierta) y el valor de la variable y es mayor que 4 (es decir, y > 4 se cumple).El valor de verdad de la disyuncin p q tambin est determinado por los valoresde verdad de p y q, y la definicin se basa en la interpretacin inclusiva de o. Consi-dere la proposicinp q: Est lloviendo o hace fro,del ejemplo 1.1.2. Si est lloviendo (es decir, p es verdadera) o si hace fro (es decir, q esverdadera) o ambas, entonces se considerara que la proposicinp q: Est lloviendo o hace froes verdadera (esto es, p q es verdadera). El or-inclusivo de las proposiciones p y q esverdadero si ambas, p y q, son verdaderas. Si no est lloviendo (o sea, p es falsa) y si nohace fro (q tambin es falsa), entonces se considerara que la proposicinp q: Est lloviendo o hace fro,es falsa (esto es, p q es falsa). Tambin existe el or-exclusivo (vea el ejercicio 53) quedefine p exor q como falsa si ambas, p y q, son verdaderas.El valor de verdad de la proposicin p q se define por la tabla de verdadLa definicin 1.1.6 establece que la disyuncin p q es verdadera siempre que p oq (o ambas) sean verdaderas; de otra manera, p q ser falsa (es decir, slo si p y q sonfalsas la disyuncin ser falsa).Sip: Un milenio tiene 100 aos,q: Un milenio tiene 1000 aos,entonces p es falsa, q es verdadera y la disyuncinp q: Un milenio tiene 100 aos o un milenio tiene 1000 aoses verdadera.Casi todos los lenguajes de programacin definen un or (inclusivo) justo como en la defi-nicin 1.1.6. Por ejemplo, en Java, el or (lgico) se denota por || y la expresin4 Captulo 1 Lgica y demostracionesEjemplo 1.1.5 x < 10 && y > 4Definicin 1.1.6 p q p qT T TT F TF T TF F FVVVVVVVEjemplo 1.1.7 Ejemplo 1.1.8 gx < 10 || y > 4es verdadera precisamente cuando el valor de la variable x es menor que 10 (esto es,x < 10 es cierta) o el valor de la variable y es mayor que 4 (es decir, y > 4 se cum-ple) o ambas.En el lenguaje comn, las proposiciones que se combinan (es decir, p y q combina-das para dar la proposicin p q) suelen estar relacionadas; pero en lgica, no se requiereque estas proposiciones hagan referencia al mismo asunto. Por ejemplo, en lgica se per-miten proposiciones como3 < 5 o Pars es la capital de Inglaterra.La lgica se ocupa de la forma de las proposiciones y de la relacin de las proposicio-nes entre s, no del tema. (La proposicin anterior es verdadera porque 3 < 5 es verda-dera).El operador final en una proposicin p que analizamos en esta seccin es la nega-cin de p.La negacin de p, denotada por p, es la proposicinno p.El valor de verdad de esta proposicin p se define por la tabla de verdadAlgunas veces escribimos p para decir no ocurre que p. Por ejemplo, sip: Pars es la capital de Inglaterra,la negacin de p se escribe comop: No ocurre que Pars es la capital de Inglaterra.o ms fcil comop: Pars no es la capital de Inglaterra.Un operador unario sobre un conjunto X asigna a cada elemento de X un elementode X (vea la definicin 2.2.46). El operador asigna a cada proposicin p la proposicinp. Entonces, es un operador unario sobre las proposiciones.Sip: se calcul con 1,000,000 de dgitos decimales en 1954,la negacin de p es la proposicinp: no se calcul con 1,000,000 de dgitos decimales en 1954.No fue sino hasta 1973 que se calcul con 1,000,000 de dgitos decimales; entonces p esfalsa. (Desde entonces se han calculado ms de 200 mil millones de dgitos decimales de). Puesto que p es falsa, p es verdadera.1.1 Proposiciones 5Definicin 1.1.9 p pT FF TVVEjemplo 1.1.10 gCasi todos los lenguajes de programacin definen no justo como en la definicin 1.1.9.Por ejemplo, en Java el no se denota por !, y la expresin! (x < 10)es verdadera precisamente cuando el valor de la variable x no es menor que 10 (es decir, xes mayor que o igual a 10).En las expresiones que incluyen algunos o todos los operadores , y , en la au-sencia de parntesis, primero se evala , despus y luego . Esta convencin se cono-ce como precedencia del operador. En lgebra, la precedencia del operador indica que seevalan y / antes que + y .Puesto que la proposicin p es falsa, la proposicin q es verdadera y la proposicin r es fal-sa, determine si la proposicin p q res falsa o verdadera.Primero se evala p, que es verdadera. Despus se evala q r, que es falsa. Porltimo, se evala p q rque es verdadera.Bsqueda en InternetSe dispone de gran variedad de herramientas de bsqueda en Internet (como AltaVista,Google, Yahoo) que permiten al usuario introducir palabras clave que el portal de bsque-da intenta igualar con pginas Web. Por ejemplo, introducir matemticas produce una lista(enorme!) de pginas que contienen la palabra matemticas. Algunos sitios de bsque-da permiten al usuario incluir operadores como AND, OR y NOT (y, o y no) junto conparntesis para combinar las palabras clave (vea la figura 1.1.1), lo que admite bsquedas6 Captulo 1 Lgica y demostracionesEjemplo 1.1.11 Ejemplo 1.1.12 Ejemplo 1.1.13 Figura 1.1.1 El portal de bsqueda AltaVista permite al usuariointroducir expresiones con AND, OR y NOT junto con parntesis.(En AltaVista, NOT debe ir precedido de otro operador como AND). En la figura, el usuario busca pginas quecontengan discrete mathematics o finite mathematics(matemticas discretas o matemticas finitas) escribiendo(discrete OR finite) AND mathematics. Como se muestra,AltaVista encontr cerca de 390,000 pginas de Internet que contienen matemticas discretas o matemticas finitas.gms complejas. Por ejemplo, para buscar pginas que contengan las palabras clave discre-tas y matemticas, el usuario escribira discretas AND matemticas. Para buscar pgi-nas con las palabras clave discretas y matemticas o las palabras clave finitas ymatemticas, el usuario podra introducir (discretas OR finitas) AND matemticas.Aunque tal vez haya un camino ms corto para determinar los valores de verdad de una pro-posicin P formada al combinar las proposiciones p1, . . . , pnusando operadores como y , la tabla de verdad siempre proporcionar todos los valores de verdad posibles de Ppara diferentes valores de las proposiciones que la constituyen p1, . . . , pn.1.1 Proposiciones 7Sugerencias para resolver problemas1. Qu es una proposicin?2. Qu es una tabla de verdad?3. Qu es la conjuncin de p y q? Cmo se denota?4. Proporcione la tabla de verdad para la conjuncin de p y q.5. Qu es la disyuncin de p y q? Cmo se denota?6. Proporcione la tabla de verdad para la disyuncin de p y q.7. Qu es la negacin de p? Cmo se denota?8. Proporcione la tabla de verdad para la negacin de p.Seccin de ejercicios de repasoEjerciciosDetermine si cada oracin en los ejercicios 1 a 8 es una proposicin.Si la oracin es una proposicin, escriba su negacin. (No se piden losvalores de verdad de las oraciones que son proposiciones).1. 2 + 5 = 19.2. Mesero, servira las nueces, quiero decir, servira las nueces a losinvitados?3. Para algn entero positivo n, 19340 = n 17.4. Audrey Meadows fue la Alice original de la serie The Honey-mooners.5. Plame una uva.6. La lnea Tcala otra vez, Sam corresponde a la pelcula Casa-blanca.7. Todo entero par mayor que 4 es la suma de dos primos.8. La diferencia de dos primos.Los ejercicios 9 a 12 se refieren a una moneda que se lanza 10 veces.Escriba la negacin de la proposicin.9. Salieron 10 caras.10. Salieron algunas caras.11. Salieron algunas caras y algunas cruces.12. Sali al menos una cara.Puesto que la proposicin p es falsa, la proposicin q es verdadera y laproposicin r es falsa, determine si cada proposicin en los ejercicios13 a 18 es falsa o verdadera.13. 14.15. 16.17.18.Escriba la tabla de verdad de cada proposicin en los ejercicios 19a 26.19. 20.21. 22.23. 24.25.26.En los ejercicios 27 a 29, represente la proposicin indicada simbli-camente definiendop: 5 < 9, q: 9 < 7, r: 5 < 7.Determine si cada proposicin es verdadera o falsa.27. 5 < 9 y 9 < 7.28. No ocurre que (5 < 9 y 9 < 7).29. 5 < 9 o no ocurre que (9 < 7 y 5 < 7).En los ejercicios 30 a 35, formule la expresin simblica en palabrasusandop: Leo toma ciencias de la computacin.q: Leo toma matemticas.30. 31. 32.33. 34. 35.En los ejercicios 36 a 40, formule la expresin simblica en palabrasusandop: Hoy es lunes.q: Est lloviendo.r: Hace calor.36. 37.38. 39.p q 14. p qp q 16. p (q r)( p q) (p r)( p r) ((q r) (r p))p q 20. (p q) p( p q) p 22. ( p q) p( p q) (p q) 24. ( p q) (r p)( p q) (p q) ( p q) (p q)( p q) (q r)pp qp qp qp qp qp q( p q) rp (q r)( p q) (r p) Los nmeros de ejercicios en cursivas indican que se da una sugerencia o la solucin al final del libro, despus de la sec-cin de referenciasg40.En los ejercicios 41 a 46, represente simblicamente la proposicin de-finiendop: Hay huracn.q: Est lloviendo.41. No hay huracn.42. Hay huracn y est lloviendo.43. Hay huracn, pero no est lloviendo.44. No hay huracn y no est lloviendo.45. Hay huracn o est lloviendo (o ambas).46. Hay huracn o est lloviendo, pero no hay huracn.En los ejercicios 47 a 52, represente simblicamente la proposicin de-finiendop: Oste el concierto de rock de Flying Pigs.q: Oste el concierto de rock de Y2K.r: Tienes los tmpanos inflamados.47. Oste el concierto de rock de Flying Pigs y tienes los tmpanosinflamados.48. Oste el concierto de rock de Flying Pigs, pero no tienes los tm-panos inflamados.49. Oste el concierto de rock de Flying Pigs, oste el concierto derock de Y2K y tienes los tmpanos inflamados.50. Oste el concierto de rock de Flying Pigs o el concierto de rockde Y2K, pero no tienes los tmpanos inflamados.51. No oste el concierto de rock de Flying Pigs y no oste el con-cierto de rock de Y2K, pero tienes los tmpanos inflamados.52. No ocurre que: oste el concierto de rock de Flying Pigs o bienoste el concierto de rock de Y2K o no tienes los tmpanos in-flamados.53. Proporcione una tabla de verdad para el or-exclusivo de p y q don-de p exor q es verdadera si p o q, pero no ambas, son verdaderas.54. En una ocasin se public el siguiente decreto en Naperville, Illi-nois: Ser ilegal que una persona tenga ms de tres [3] perros ytres [3] gatos en su propiedad dentro de la ciudad. El seor Char-les Marko tena cinco perros y ningn gato, violaba el decreto?Explique.55. Escriba las instrucciones de bsqueda en Internet para encontrarparques nacionales en Dakota del Sur o del Norte.56. Escriba las instrucciones de bsqueda en Internet para obtener in-formacin de enfermedades pulmonares que no sean cncer.57. Escriba las instrucciones de bsqueda en Internet para ver equipos debisbol de las ligas menores que estn en la Liga del Medio Oeste.8 Captulo 1 Lgica y demostraciones( p (q r)) (r (q p))El decano de la escuela anunci queSi el departamento de matemticas obtiene $40,000 adicionales, entonces contratar un nuevo acadmico. (1.2.1)La afirmacin (1.2.1) establece que con la condicin de que el departamento de matemti-cas obtenga $40,000 adicionales, entonces contratar un nuevo acadmico. Este tipo deproposicin se conoce como proposicin condicional.Si p y q son proposiciones, la proposicinsi p entonces q (1.2.2)se llama proposicin condicional y se denota porp qLa proposicin p se llama hiptesis (o antecedente) y la proposicin q recibe el nombre deconclusin (o consecuente).Si se definep: El departamento de matemticas obtiene $40,000 adicionales,q: El departamento de matemticas contrata un nuevo acadmico,entonces la proposicin (1.2.1) toma la forma (1.2.2). La hiptesis es la afirmacin el de-partamento de matemticas obtiene $40,000 adicionales y la conclusin es la afirmacinel departamento de matemticas contrata un nuevo acadmico.Cul es el valor de verdad para la afirmacin del decano (1.2.1)? Primero, supongaque el departamento de matemticas obtiene $40,000 adicionales. Si de hecho contrata otroacadmico, con seguridad la afirmacin del decano es verdadera. (Usando la notacin del1.2 Proposiciones condicionales y equivalencia lgicaDefinicin 1.2.1 Ejemplo 1.2.2 gejemplo 1.2.2, si p y q son ambas verdaderas, entonces p q es verdadera). Por otra par-te, si el departamento de matemticas obtiene $40,000 adicionales y no contrata un nuevoacadmico, el decano est equivocado, es decir, la oracin (1.2.1) es falsa. (Si p es verda-dera y q es falsa, entonces p q es falsa). Ahora suponga que el departamento de mate-mticas no obtiene $40,000 adicionales. En este caso, el departamento de matemticaspuede o no contratar otro acadmico. (Quiz alguien del departamento se jubila y se con-trata a alguien ms para reemplazarlo. Por otro lado, el departamento puede no contratar aalguien). Por supuesto, no se considerara falsa la afirmacin del decano. As, si el depar-tamento de matemticas no obtiene los $40,000, la afirmacin del decano debe ser verda-dera, sin importar si el departamento contrata o no otro acadmico. (Si p es falsa, entoncesp q es verdadera sea q verdadera o falsa). Este anlisis motiva la siguiente definicin.El valor verdadero de la proposicin condicional p q est definido por la siguiente tablade verdad:De manera formal, es un operador binario sobre las proposiciones. El operadorasigna a cada par de proposiciones p y q la proposicin p q.Para quienes necesitan mayor evidencia de que p q se debe definir como verda-dera cuando p es falsa, se ofrece otra justificacin. Casi todas las personas estn de acuer-do en que la proposicinPara todos los nmeros reales x, si x > 0, entonces x2> 0, (1.2.3)es verdadera. (En la seccin 1.3 se har el anlisis formal y detallado de afirmacio-nes del tipo para todos). En la siguiente presentacin, p denotada por x > 0 y q denota-da por x2>0. El hecho de que la proposicin (1.2.3) sea verdadera significa que no importacon cul nmero real se sustituya x, la proposicinsi p entonces q (1.2.4)resultante es verdadera. Por ejemplo, si x = 3, entonces p y q son ambas ciertas (3 > 0 y32> 0 son ambas verdaderas) y, por la definicin 1.2.3, (1.2.4) es verdadera. Ahora consi-dere la situacin donde p es falsa. Si x = 2, entonces p es falsa (2 > 0 es falsa) y q esverdadera [(2)2> 0 es verdadera]. Con objeto de que la proposicin (1.2.4) sea verdade-ra en ese caso, debe definirse p q como verdadera cuando p es falsa y q es verdadera.Esto es justo lo que ocurre en el tercer rengln de la tabla de verdad para la definicin 1.2.3.Si x = 0, entonces p y q son ambas falsas (0 > 0 y 02> 0 son falsas). Para que la proposi-cin (1.2.4) sea cierta en este caso, debe definirse p q como verdadera cuando p y q sonambas falsas. Justo ocurre esto en el cuarto rengln de la tabla de verdad para la definicin1.2.3. En los ejercicios 52 y 53 se da una mayor motivacin para definir p q como ver-dadera cuando p es falsa.Seap: 1 > 2, q: 4 < 8.Entonces p es falsa y q es verdadera. Por lo tanto,p q es verdadera, q p es falsa.1.2 Proposiciones condicionales y equivalencia lgica 9Definicin 1.2.3 p q p qT T TT F FF T TF F T Ejemplo 1.2.4 VVVVV VVgEn las expresiones que incluyen a los operadores lgicos , , y , el operador condi-cional evala al final. Por ejemplo,se interpreta comoSuponiendo que p es verdadera, q es falsa y r es verdadera, encuentre el valor de verdad decada proposicin.a) b) c) d)a) Primero se evala p q porque se evala al final. Como p es cierta y q es fal-sa, p q es falsa. Por lo tanto, p q r es verdadera (sin importar si r es cier-ta o falsa).b) Primero se evala r. Como r es verdadera, r es falsa. Despus se evalap q. Como p es verdadera y q es falsa, p q es verdadera. Por lo tanto,p q r es falsa.c) Como q es falsa, q r es verdadera (sin importar si r es verdadera o falsa). Co-mo p es verdadera, p (q r) es verdadera.d) Puesto que q es falsa, q r es verdadera (sin importar si r es verdadera o falsa).Entonces, p (q r) es verdadera (sin importar si p es verdadera o falsa).Una proposicin condicional que es verdadera porque la hiptesis es falsa se dice quees verdadera por omisin o superficialmente verdadera. Por ejemplo, si la proposicin,Si el departamento de matemticas obtiene $40,000 adicionales, entonces contratarun nuevo acadmico,es verdadera porque el departamento de matemticas no obtuvo $40,000 adicionales, se di-ce que la proposicin es verdadera por omisin o que es superficialmente verdadera.Algunas afirmaciones no de la forma (1.2.2) pueden rescribirse como proposicionescondicionales, como ilustra el siguiente ejemplo.Reescriba cada proposicin en la forma (1.2.2) de una proposicin condicional.a) Mara ser una buena estudiante si estudia mucho.b) Juan toma clculo slo si est en 2, 3 o 4 grado de universidad.c) Cuando cantas, me duelen los odos.d) Una condicin necesaria para que los Cachorros ganen la Serie Mundial es quecontraten a un pitcher suplente diestro.e) Una condicin suficiente para que Mara visite Francia es ir a la Torre Eiffel.a) La hiptesis es la clusula que sigue a si; entonces una formulacin equivalente esSi Mara estudia mucho, entonces ser una buena estudiante.b) La afirmacin significa que para que Juan tome clculo debe estar en 2, 3 o 4ao de universidad. En particular, si est en 1, no puede tomar clculo. As, seconcluye que si toma clculo, entonces est en 2, 3 o 4 ao. Por lo tanto, unaformulacin equivalente seraSi Juan toma clculo, entonces est en 2, 3 o 4 ao.Observe queSi Juan est en 2, 3 o 4 ao, entonces toma clculo,no es una formulacin equivalente. Si Juan est en 2, 3 o 4 ao, puede o no to-mar clculo. (Aunque sea elegible para tomar clculo, puede decidir no tomarlo).10 Captulo 1 Lgica y demostracionesEjemplo 1.2.5 Ejemplo 1.2.6 p q r( p q) (r).p q rp q r p (q r) p (q r)gLa formulacin si p entonces q hace hincapi en la hiptesis mientras que la for-mulacin p slo si q resalta la conclusin; la diferencia es nada ms de estilo.c) Cuando significa lo mismo que si; entonces una formulacin equivalente esSi cantas, me duelen los odos.d) Una condicin necesaria es slo eso: una condicin que se necesita para lograrun resultado en particular. La condicin no garantiza el resultado; pero si no secumple, el resultado no se lograr. Aqu, la afirmacin significa que si los Cacho-rros ganan la Serie Mundial, podemos estar seguros de que contrataron un pitchersuplente diestro, ya que sin ese contrato no habran ganado. As, una formulacinequivalente de la afirmacin esSi los Cachorros ganan la Serie Mundial, entonces contrataron un pitcher su-plente diestro.La conclusin expresa una condicin necesaria.Observe queSi los Cachorros contratan un pitcher suplente diestro, entonces ellos gananla Serie Mundial,no es una formulacin equivalente. Contratar un pitcher suplente diestro no es ga-ranta de que ganarn la Serie Mundial. Sin embargo, no contratarlo garantiza queno ganarn la Serie Mundial.e) De manera similar, una condicin suficiente es una condicin que basta para ga-rantizar un resultado en particular. Si la condicin no se cumple, el resultado pue-de lograrse de otras formas o tal vez no se logre; pero si la condicin se cumple,el resultado est garantizado. Aqu, para asegurar que Mara visite Francia, bastacon que vaya a la Torre Eiffel. (Sin duda, hay otras maneras de asegurar que Ma-ra visite Francia; por ejemplo, podra ir a Lyon). As, una formulacin equivalen-te a la afirmacin en cuestin esSi Mara va a la Torre Eiffel, entonces visita Francia.La hiptesis expresa una condicin suficiente.Observe queSi Mara visita Francia, entonces va a la Torre Eiffel,no es una formulacin equivalente. Como se observ, hay otras maneras de ase-gurar que Mara visite Francia que ir a la Torre Eiffel.El ejemplo 1.2.4 muestra que la proposicin pq puede ser verdadera mientras quela proposicin q p es falsa. La proposicin q p se llama la recproca de la proposi-cin p q. As, una proposicin condicional puede ser verdadera mientras que su recpro-ca es falsa.Escriba la proposicin condicionalSi Jess recibe una beca, entonces ir a la universidad,y su recproca en smbolos y en palabras. Adems, suponga que Jess no recibe la beca, pe-ro gana la lotera y de todas formas va a la universidad, encuentre entonces el valor de ver-dad de la proposicin original y su recproca.Seap: Jess recibe una beca,q: Jess va la universidad.La proposicin se escribe en smbolos como p q. Como la hiptesis p es falsa, la pro-posicin condicional es verdadera.La recproca de la proposicin esSi Jess va a la universidad, entonces recibe una beca.1.2 Proposiciones condicionales y equivalencia lgica 11Ejemplo 1.2.7 gLa recproca se escribe en smbolos como q p. Puesto que la hiptesis q es verdadera yla conclusin p es falsa, la recproca es falsa.Otra proposicin til esp si y slo si q,que se considera verdadera precisamente cuando p y q tienen el mismo valor de verdad (esdecir, si p y q son ambas verdaderas o ambas falsas).Si p y q son proposiciones, la proposicinp si y slo si qse llama proposicin bicondicional y se denota porp q.El valor de verdad de la proposicin p q se define por la siguiente tabla de verdad:El operador tambin es un operador binario sobre las proposiciones. Asigna a ca-da par de proposiciones p y q la proposicin p q.Una manera alternativa de establecer p si y slo si q es p es una condicin necesa-ria y suficiente para q. La proposicin p si y slo si q algunas veces se escribe p ssi q.La proposicin1 < 5 si y slo si 2 < 8 (1.2.5)se escribe en smbolos comop qsi se definep: 1 < 5, q: 2 < 8Puesto que ambas, p y q, son verdaderas, la proposicin p q es verdadera.Una manera alternativa de establecer (1.2.5) es: Una condicin necesaria y suficien-te para que 1 < 5 es que 2 < 8.En algunos casos, dos proposiciones diferentes tienen los mismos valores de verdadsin importar qu valores de verdad tengan las proposiciones que las constituyen. Tales pro-posiciones se conocen como equivalentes lgicos.Suponga que las proposiciones P y Q estn formadas por las proposiciones p1, . . . , pn. Sedice que P y Q son equivalentes lgicos y se escribenP Qsiempre que, a partir de cualesquiera valores de verdad de p1, . . . , pn, o bien P y Q son am-bas verdaderas o P y Q son ambas falsas.12 Captulo 1 Lgica y demostracionesp q p qT T TT F FF T FF F TVVVVVVEjemplo 1.2.9 Definicin 1.2.10 Definicin 1.2.8 gLeyes de De Morgan para lgicaSe verificar la primera de las leyes de De Morgany se dejar la segunda como ejercicio (vea el ejercicio 54).Si se escriben las tablas de verdad para P = (p q) y Q = p q, se puede ve-rificar que, a partir de cualesquiera valores de verdad para p y q, P y Q son ambas verda-deras o P y Q son ambas falsas.Entonces, P y Q son equivalentes lgicos.Demuestre que, en Java, las expresionesx < 10 || x > 20y!(x >= 10 && x = significa y = 10 y q denota la expresin x = 10 && x 20, p q se traducen como x < 10 || x > 20. Por lo tanto, las expresio-nes x < 10 || x > 20 y !(x >= 10 && x 12. 39. Si 4 < 6, entonces 9 < 12.40. |1| < 3 si 3 < 1 < 3. 41. |4| < 3 si 3 < 4 < 3.Para cada par de proposiciones P y Q en los ejercicios 42 al 51, esta-blezca si P Q o no.42.43.44.45.46.47.48.49.50.51.Los ejercicios 52 y 53 proporcionan mayor motivacin para definirp q como verdadera cuando p es falsa. Se considera cambiar la ta-bla de verdad de p q cuando p es falsa. Para este primer cambio, eloperador resultante recibe el nombre de imp1 (ejercicio 52), y para elsegundo cambio el operador resultante es imp2 (ejercicio 53). En am-bos casos, se obtienen patologas.52. Defina la tabla de verdad para imp1 comoDemuestre que p imp1 q q imp1 p.53. Defina la tabla de verdad para imp2 comoa) Demuestre que(1.2.6)b) Demuestre que (1.2.6) permanece verdadera si se cambia eltercer rengln de la tabla de verdad de imp2 a F V F.54. Verifique la segunda ley de De Morgan, (p q) p q.55. Demuestre que (p q) (p q)1.3 Cuantificadores 17p q 33. q (r p (q r) 35. ( p q)( p (q r)) (r (q p))( p (p (q r))) ( p (r q))q (r p)( p q) rP = p, Q = p qP = p q, Q = p qP = p q, Q = p qP = p (q r), Q = p (q r)P = p (q r), Q = ( p q) ( p r)P = p q, Q = q pP = p q, Q = p qP = ( p q) (q r), Q = p rP = ( p q) r, Q = p (q r)P = (s ( p r)) (( p (r q)) s), Q = p tp q p imp1 qT T TT F FF T FF F TVVVVVVp q p imp2 qT T TT F FF T TF F FVVVV VV( p imp2 q) (q imp2 p) p q.1.3 CuantificadoresLa lgica en las secciones 1.1 y 1.2 referente a proposiciones es incapaz de describir la ma-yora de las afirmaciones en matemticas y en ciencias de la computacin. Considere, porejemplo, la afirmacinp: n es un entero imparUna proposicin es una afirmacin que es verdadera o falsa. La afirmacin p no es una pro-posicin, porque el hecho de que p sea verdadera o falsa depende del valor de n. Por ejem-plo, p es verdadera si n = 103 y falsa si n = 8. Como casi todas las afirmaciones enmatemticas y ciencias de la computacin usan variables, debe ampliarse el sistema de l-gica para incluir estas afirmaciones.Sea P(x) una oracin que incluye la variable x y sea D un conjunto. P se llama funcin pro-posicional o predicado (respecto a D) si para cada x en D, P(x) es una proposicin. D es eldominio de discurso (tambin llamado dominio de referencia) de P.Sea P(n) la afirmacinn es un entero impar,y sea D el conjunto de enteros positivos. Entonces P es una funcin proposicional con do-minio de discurso D ya que para cada n en D, P(n) es una proposicin [es decir, para cadan en D, P(n) es verdadera o falsa pero no ambas]. Por ejemplo, si n = 1, se obtiene la pro-posicinP(1): 1 es un entero imparWWWDefinicin 1.3.1 Ejemplo 1.3.2 g(que es verdadera). Si n = 2, se obtiene la proposicinP(2): 2 es un entero impar(que es falsa).Una proposicin P, por s misma, no es falsa ni verdadera. Sin embargo, para cada xen su dominio de discurso, P(x) es una proposicin y es, por lo tanto, verdadera o falsa. Sepuede pensar que una funcin proposicional define una clase de proposiciones, una para ca-da elemento de su dominio de discurso. Por ejemplo, si P es una funcin proposicional condominio de discurso igual al conjunto de enteros positivos, se obtiene una clase de propo-sicionesP(1), P(2), . . . .Cada una de las P(1), P(2), . . . es verdadera o falsa.Las siguientes son funciones proposicionales.a) n2+ 2n es un entero impar (dominio de discurso = conjunto de enteros positivos).b) x2 x 6 = 0 (dominio de discurso = conjunto de nmeros reales).c) El beisbolista bate ms de .300 en 2003 (dominio de discurso = conjunto debeisbolistas).d) El restaurante tiene ms de dos estrellas en la revista Chicago (dominio de dis-curso = restaurantes clasificados en la revista Chicago).En la afirmacin a), para cada entero positivo n, se obtiene una proposicin; por lotanto la afirmacin a) es una funcin proposicional.De manera similar, en la afirmacin b), para cada nmero real x, se obtiene una pro-posicin; por lo tanto, la afirmacin b) es una funcin proposicional.Se puede ver a la variable en la afirmacin c) como beisbolista. Siempre que sesustituya un beisbolista especfico en lugar de la variable, la afirmacin es una proposicin.Por ejemplo, si se sustituye Barry Bonds en lugar de beisbolista, la afirmacin c) esBarry Bonds bate ms de .300 en 2003,que es verdadera. Si se sustituye Alex Rodrguez en lugar de beisbolista, la afirmacinc) esAlex Rodrguez bate ms de .300 en 2003,que es falsa. As, la afirmacin c) es una funcin proposicional.La afirmacin d) es similar en la forma a c); aqu la variable es restaurante. Al sus-tituir la variable por un restaurante clasificado en la revista Chicago, la afirmacin es unaproposicin. Por ejemplo, si se sustituye Yugo Inn la afirmacin d) esYugo Inn tiene ms de dos estrellas en la revista Chicago,que es falsa. Si se sustituye Le Franais en lugar de restaurante, la afirmacin d) esLe Franais tiene ms de dos estrellas en la revista Chicago,que es verdadera. As, la afirmacin d) es una funcin proposicional.Casi todas las afirmaciones en matemticas y ciencias de la computacin usan trmi-nos como para todo y para alguno. Por ejemplo, en matemticas se tiene el siguienteteorema:Para todo tringulo T, la suma de los ngulos de T es igual a 180.En ciencias de la computacin, se tiene el siguiente teorema:Para algn programa P, la salida de P es P mismo.18 Captulo 1 Lgica y demostracionesEjemplo 1.3.3 gAhora se extender el sistema lgico de las secciones 1.1 y 1.2 de manera que las afirma-ciones que incluyen para todo y para alguno sean manejables.Sea P una funcin proposicional con dominio de discurso D. Se dice que la afirmacinpara toda x, P(x)es una afirmacin cuantificada universalmente. El smbolo significa para toda, Paracada, Para cualquier. Entonces, la afirmacinpara toda x, P(x)se escribe x P(x).El smbolo se llama cuantificador universal.La afirmacinx P(x)es verdadera si P(x) es verdadera para toda x en D. La afirmacinx P(x)es falsa si P(x) es falsa para al menos una x en D.Considere la afirmacin cuantificada universalmentex (x2 0)con el conjunto de nmeros reales como dominio de discurso. La afirmacin es verda-dera porque, para todo nmero real x, es cierto que el cuadrado de x es positivo o cero.De acuerdo con la definicin 1.3.4, la afirmacin cuantificada universalmentex P(x)es falsa si para al menos una x en el dominio de discurso, la proposicin P(x) es falsa. Unvalor x en el dominio de discurso que hace que P(x) sea falsa se llama contraejemplo dela afirmacinx P(x).Considere la afirmacin cuantificada universalmentex (x2 1 > 0)con el conjunto de los nmeros reales como dominio de discurso. La afirmacin es falsa,ya que si x = 1, la proposicin12 1 > 0es falsa. El valor 1 es un contraejemplo de la afirmacinx (x2 1 > 0).Aunque existen valores de x que hacen que la funcin proposicional sea verdadera, el con-traejemplo muestra que la afirmacin cuantificada universalmente es falsa.1.3 Cuantificadores 19Definicin 1.3.4 Ejemplo 1.3.5 Ejemplo 1.3.6 gSuponga que P es una funcin proposicional cuyo dominio de discurso consiste en los ele-mentos d1, . . . , dn. El siguiente seudocdigodetermina six P(x)es verdadera o falsa:for i = 1 to nif (P(di))return falsareturn verdaderaEl ciclo for examina los miembros didel dominio de discurso uno por uno. Si encuentraun valor dipara el que P(di) es falsa, la condicin P(di) en el estatuto if es verdadera;as, el cdigo regresa a falsa [para indicar que x P(x) es falsa] y termina. En este caso, dies un contraejemplo. Si P(di) es verdadera para toda di, la condicin P(di) en el estatutoif es siempre falsa. En este caso, el ciclo for corre hasta completarse, despus de lo cualel cdigo regresa a verdadera [para indicar que x P(x) es verdadera] y termina.Observe que si x P(x) es verdadera, el ciclo for necesariamente corre hasta el fi-nal, de manera que cada miembro del dominio se verifica para asegurar que P(x) es verda-dera para toda x. Si x P(x) es falsa, el ciclo for termina en cuanto se encuentra unelemento x del dominio de discurso para el que P(x) es falsa.La variable x en la funcin proposicional P(x) se llama variable libre. (La idea es quex es libre de recorrer el dominio de discurso). La variable x en la afirmacin cuantifica-da universalmentex P(x) (1.3.1)se llama variable acotada. (La idea es que x est acotada por el cuantificador ).Se seal ya que una funcin proposicional no tiene valor de verdad. Por otro lado,la definicin 1.3.4 asigna un valor de verdad a la afirmacin cuantificada universalmente(1.3.1). En suma, una afirmacin con variables libres (no cuantificadas) no es una proposi-cin, y una afirmacin sin variables libres (sin variables no cuantificadas) es una propo-sicin.Otras maneras de escribirx P(x)sonpara toda x, P(x)ypara cualquier x, P(x).El smbolo se lee para toda, para todos o para cualquier.Para demostrar quex P(x)es verdadera debemos, de hecho, examinar todos los valores de x en el dominio de discur-so y demostrar que para toda x, P(x) es cierta. Una tcnica para probar quex P(x)es verdadera consiste en hacer que x denote un elemento arbitrario del dominio de discur-so D. El argumento procede usando el smbolo x. Cualquier cosa que se asegure acerca de20 Captulo 1 Lgica y demostracionesEjemplo 1.3.7 El seudocdigo usado en este libro se explica en el apndice C.gx debe ser cierto sin importar qu valor pueda tener x en D. El argumento debe concluircon la prueba de que P(x) es verdadera.Algunas veces, para especificar el dominio de discurso D, se escribe la afirmacincuantificada universalmente comopara toda x en D, P(x).La afirmacin cuantificada universalmentepara todo nmero real x, si x > 1, entonces x + 1 > 1es verdadera. Esta vez se debe verificar que la afirmacinsi x > 1, entonces x + 1 > 1es verdadera para todo nmero real x.Sea x cualquier nmero real. Es cierto que para cualquier nmero real x, o bienx 1 o x > 1. Si x 1, la proposicin condicionalsi x > 1, entonces x + 1 > 1es trivialmente cierta. (La proposicin es cierta porque la hiptesis x > 1 es falsa. Recuerdeque cuando la hiptesis es falsa, la proposicin condicional es verdadera sin importar si laconclusin es falsa o verdadera). En la mayora de los argumentos, el caso trivial se omite.Ahora suponga que x > 1. Sea cual fuere el valor especfico de x, x + 1 > x. Comox + 1 > x y x > 1,se concluye que x + 1 > 1, de manera que la conclusin es verdadera. Si x > 1, la hipte-sis y la conclusin son ambas verdaderas; as, la proposicin condicionalsi x > 1, entonces x + 1 > 1es verdadera.Se ha demostrado que para todo nmero real x, la proposicinsi x > 1, entonces x + 1 > 1es verdadera. Por lo tanto, la afirmacin cuantificada universalmentepara todo nmero real x, si x > 1, entonces x + 1 > 1es verdadera.El mtodo para desaprobar la afirmacinx P(x)es bastante diferente del mtodo usado para probar que la afirmacin es verdadera. Para de-mostrar que la afirmacin cuantificada universalmentex P(x)es falsa, es suficiente encontrar un valor de x en el dominio de discurso para el que la pro-posicin P(x) sea falsa. Tal valor, como se recordar, se llama contraejemplo de la afirma-cin cuantificada universalmente.Ahora se analizarn las afirmaciones cuantificadas existencialmente.Sea P una funcin proposicional con dominio de discurso D. Se dice que la afirmacinexiste x, P(x)1.3 Cuantificadores 21Ejemplo 1.3.8 Definicin 1.3.9 ges una afirmacin cuantificada existencialmente. El smbolo significa existe. As, laafirmacinexiste x, P(x)se escribex P(x)El smbolo se llama cuantificador existencial.La afirmacinx P(x)es verdadera si P(x) es verdadera para al menos una x en D. La afirmacinx P(x)es falsa si P(x) es falsa para toda x en D.Considere la afirmacin cuantificada existencialmentecon el conjunto de nmeros reales como dominio de discurso. La afirmacin es ver-dadera porque es posible encontrar al menos un nmero real x para el que la proposi-cines verdadera. Por ejemplo, si x = 2, se obtiene la proposicin verdaderaNo ocurre que todo valor de x d una proposicin verdadera. Por ejemplo, si x = 1, la pro-posicines falsa.Segn la definicin 1.3.9, la afirmacin cuantificada existencialmentex P(x)es falsa si para toda x en el dominio de discurso, la proposicin P(x) es falsa.Para verificar que la afirmacin cuantificada existencialmentees falsa, debe demostrarse quees falsa para todo nmero real x. Ahora22 Captulo 1 Lgica y demostracionesEjemplo 1.3.10 x

xx2+1 =25

xx2+1 =25222+1 =25.112+1 =25x

1x2+1 > 1

1x2+1 > 11x2+1 > 1Ejemplo 1.3.11 ges falsa precisamente cuandoes cierta. As, debe demostrarse quees verdadera para todo nmero real x. Con este fin, sea x cualquier nmero real. Como0 x2, se puede sumar 1 en ambos lados de la desigualdad para obtener 1 x2+ 1. Si sedividen ambos lados de esta desigualdad por x2+ 1, se obtienePor lo tanto, la afirmacines verdadera para todo nmero real x. Entonces la afirmacines falsa para todo nmero real x. Se ha demostrado que la afirmacin cuantificada existen-cialmentees falsa.Suponga que P es una funcin proposicional cuyo dominio de discurso consiste en los ele-mentos d1, . . . , dn. El siguiente seudocdigo determina six P(x)es verdadera o falsa:for i = 1 to nif (P(di))return verdaderareturn falsaEl ciclo for examina los miembros didel dominio de discurso uno por uno. Si encuentraun valor dipara el que P(di) es verdadera, la condicin P(di) en el estatuto if es verdade-ra; as, el cdigo regresa a verdadera [para indicar que x P(x) es verdadera] y termina. Eneste caso, el cdigo encuentra un valor en el dominio de discurso, a saber di, para el queP(di) es verdadera. Si P(di) es falsa para toda di, la condicin P(di) en el estatuto if essiempre falsa. En este caso, el ciclo for corre hasta completarse, despus de lo cual, re-gresa a falsa [para indicar que x P(x) es verdadera] y termina.Observe que si x P(x) es verdadera, el ciclo for termina en cuanto se encuentra unelemento x del dominio de discurso para el que P(x) es verdadera. Si x P(x) es falsa, el ci-clo for corre hasta completarse, de manera que se verifique todo miembro del dominiode discurso para asegurarse de que P(x) es falsa para toda x.Otras formas de escribirx P(x)sonexiste x tal que, P(x)1.3 Cuantificadores 23Ejemplo 1.3.12 1x2+1 11x2+1 11x2+1 1.1x2+1 11x2+1 > 1x

1x2+1 > 1

gypara alguna x, P(x)ypara al menos una x, P(x).El smbolo se lee como existe, para alguna o para al menos una.Considere la afirmacin cuantificada existencialmentepara alguna n, si n es primo, entonces n + 1, n + 2, n + 3 y n + 4 no son primoscon el conjunto de enteros positivos como dominio de discurso. Esta afirmacin es verda-dera porque podemos encontrar al menos un entero positivo n para el que la proposicincondicionalsi n es primo, entonces n + 1, n + 2, n + 3 y n + 4 no son primoses verdadera. Por ejemplo, si n = 23, se obtienen las proposicionessi 23 es primo, 24, 25, 26 y 27 no son primos.(Esta proposicin condicional es verdadera porque tanto la hiptesis 23 es primo comola conclusin 24, 25, 26 y 27 no son primos son verdaderas). Algunos valores de n hacenque la proposicin condicional sea verdadera (por ejemplo, n = 23, n = 4, n = 47), mien-tras que para otros es falsa (como n = 2, n = 101). El hecho es que se encontr un valorque hace que la proposicin condicionalsi n es primo, entonces n + 1, n + 2, n + 3 y n + 4 no son primossea verdadera. Por esta razn, la afirmacin cuantificada existencialmentesi n es primo, entonces n + 1, n + 2, n + 3 y n + 4 no son primoses verdadera.En el ejemplo 1.3.11, se demostr que una afirmacin cuantificada existencialmenteera falsa probando que la afirmacin cuantificada universalmente relacionada era verdade-ra. El siguiente teorema hace precisa esa relacin. El teorema generaliza las leyes de DeMorgan de lgica (ejemplo 1.2.11).Leyes generalizadas de De Morgan para lgica Si P es una funcin proposicional, cada par de proposiciones en a) y b) tiene el mismovalor de verdad (es decir, ambas son verdaderas o ambas son falsas).a) (x P(x)); xP(x)b) (x P(x)); xP(x)Demostracin Se prueba slo el inciso a) y se deja la demostracin del inciso b) allector (ejercicio 51).Suponga que la proposicin (x P(x)) es verdadera. Entonces la proposicin xP(x) es falsa. Por la definicin 1.3.4, la proposicin x P(x) es falsa precisamente cuandoP(x) es falsa para al menos una x en el dominio de discurso. Pero si P(x) es falsa para almenos una x en el dominio de discurso, P(x) es verdadera para al menos una x en el do-minio de discurso. Por la definicin 1.3.9, cuando P(x) es verdadera para al menos una24 Captulo 1 Lgica y demostracionesEjemplo 1.3.13 Teorema 1.3.14gx en el dominio de discurso, la proposicin x P(x) es verdadera. Entonces, si la propo-sicin (x P(x)) es verdadera, la proposicin x P(x) es verdadera. De manera similar,si la proposicin (x P(x)) es falsa, la proposicin x P(x) es falsa.Por lo tanto, el par de proposiciones del inciso a) siempre tienen los mismos va-lores de verdad.Sea P(x) la afirmacinEn el ejemplo 1.3.11 se demostr quex P(x)es falsa verificando quex P(x) (1.3.2)es verdadera.La tcnica se justifica recurriendo al Teorema 1.3.14. Despus de probar que la pro-posicin (1.3.2) es verdadera, se puede negar (1.3.2) y concluir que(x P(x))es falsa. Por el Teorema 1.3.14, inciso a),x P(x)o de manera equivalente,x P(x)tambin es falsa.Escriba la afirmacinTodo amante del rock ama a U2,de manera simblica. Escriba su negacin en smbolos y en palabras.Sea P(x) la funcin proposicional x ama U2. La afirmacin se escribe simblica-mente comox P(x).El dominio de discurso es el conjunto de amantes del rock.Por el Teorema 1.3.14, inciso a), la negacin de la proposicin anterior (x P(x))es equivalente ax P(x).En palabras, esta ltima proposicin se enuncia como: Existe un amante del rock que noama a U2.Escriba la afirmacinAlgunas aves no pueden volar,simblicamente. Escriba la negacin en smbolos y en palabras.Sea P(x) la funcin proposicional x vuela. La afirmacin se escribe en smbolos comox P(x)1.3 Cuantificadores 25Ejemplo 1.3.15 Ejemplo 1.3.16 Ejemplo 1.3.17 1x2+1 > 1.g[La afirmacin tambin pudo escribirse x Q(x), donde Q(x) es la funcin proposicional xno puede volar. Al igual que en lgebra, existen muchas maneras de representar simbli-camente el texto.] El dominio de discurso es el conjunto de aves.Por el Teorema 1.3.14, inciso b), la negacin de la proposicin anterior (x P(x))es equivalente ax P(x)o lo que es lo mismo,x P(x).En palabras, esta ltima proposicin se enuncia como: Toda ave puede volar.Una proposicin cuantificada universalmente generaliza la proposicinP1 P2 . . . Pn(1.3.3)en el sentido de que las proposiciones individuales P1, P2, . . . , Pnse sustituyen por una fa-milia arbitraria P(x), donde x es un miembro del dominio de discurso, y (1.3.3) se sustitu-ye porx P(x). (1.3.4)La proposicin (1.3.3) es verdadera si y slo si Pies verdadera para toda i = 1, . . . , n. Elvalor de verdad de la proposicin (1.3.4) se define de manera similar: (1.3.4) es verdaderasi y slo si P(x) es verdadera para toda x en el dominio de discurso.De manera similar, una proposicin cuantificada existencialmente generaliza la pro-posicinP1 P2 . . . Pn(1.3.5)en el sentido de que las proposiciones individuales P1, P2, . . . , Pnse sustituyen por una fa-milia arbitraria P(x), donde x es un miembro del dominio de discurso, y (1.3.5) se sustitu-ye porx P(x).Las observaciones anteriores explican cmo el Teorema 1.3.14 generaliza las leyesde De Morgan para lgica (ejemplo 1.2.11). Recuerde que la primera ley de De Morgan pa-ra lgica establece que las proposiciones(P1 P2 . . . Pn) y P1 P2 . . . Pntienen los mismos valores de verdad. En el teorema 1.3.14, inciso b),P1 P2 . . . Pnse sustituye porx P(x)y(P1 P2 . . . Pn)se sustituye por(x P(x)).Las afirmaciones en palabras con frecuencia tienen ms de una interpretacin posible. Con-sidere la bien conocida cita de El mercader de Venecia de Shakespeare:No todo lo que brilla es oro.26 Captulo 1 Lgica y demostracionesEjemplo 1.3.18 gUna interpretacin posible de esta cita es: Todo objeto que brilla no es oro. Sin embargo,seguro que esto no es lo que Shakespeare quiso decir. La interpretacin correcta es: Algnobjeto que brilla no es oro.Si P(x) es la funcin proposicional x brilla y Q(x) es la funcin proposicional x esoro, la primera interpretacin se convierte enx(P(x) Q(x)), (1.3.6)y la segunda interpretacin se convierte enx(P(x) Q(x)). Usando el resultado del ejemplo 1.2.13, se ve que los valores de verdad dex(P(x) Q(x))yx(P(x) Q(x))son los mismos. Por el Teorema 1.3.14, los valores de verdad dex(P(x) Q(x))y(x P(x) Q(x))son los mismos. As, una manera equivalente de representar la segunda interpretacin es(x P(x) Q(x)). (1.3.7)Al comparar (1.3.6) y (1.3.7), vemos la ambigedad que resulta para establecer si la nega-cin se aplica a Q(x) (la primera interpretacin) o a toda la afirmacinx (P(x) Q(x))(la segunda interpretacin). La interpretacin correcta de la afirmacinTodo lo que brilla no es orose obtiene al negar toda la afirmacin.En afirmaciones positivas, cualquiera, cada y todo tienen el mismo significa-do. En afirmaciones negativas, la situacin cambia:No todas las x satisfacen P(x).No cada x satisface P(x).No cualquier x satisface P(x).se considera que tienen el mismo significado quePara alguna x, P(x);mientras queNi una x satisface P(x)Ninguna x satisface P(x)significanPara toda x, P(x).Vea otros ejemplos en los ejercicios 41 al 49.1.3 Cuantificadores 27gPara probar que la afirmacin cuantificada universalmentex P(x)es verdadera, demuestre que para toda x en el dominio de discurso, la proposicin P(x) esverdadera. Demostrar que P(x) es verdadera para un valor particular de x no prueba quex P(x)sea cierta.Para probar que la afirmacin cuantificada existencialmentex P(x)es verdadera, encuentre un valor de x en el dominio de discurso para el que la proposicinP(x) es verdadera. Un valor es suficiente.Para probar que la afirmacin cuantificada universalmentex P(x)es falsa, encuentre un valor de x (un contraejemplo) en el dominio de discurso para el quela proposicin P(x) es falsa.Para probar que la afirmacin cuantificada existencialmentex P(x)es falsa, demuestre que para toda x en el dominio de discurso, la proposicin P(x) es falsa.Demostrar que P(x) es falsa para un valor particular x no prueba quex P(x)sea falsa.28 Captulo 1 Lgica y demostracionesSugerencias para resolver problemas1. Qu es una funcin proposicional?2. Qu es un dominio de discurso?3. Qu es una afirmacin cuantificada universalmente?4. Qu es un contraejemplo?5. Qu es una afirmacin cuantificada existencialmente?6. Establezca las leyes generalizadas de De Morgan para lgica.7. Explique cmo probar que una afirmacin cuantificada universal-mente es verdadera.8. Explique cmo probar que una afirmacin cuantificada existen-cialmente es verdadera.9. Explique cmo probar que una afirmacin cuantificada universal-mente es falsa.10. Explique cmo probar que una afirmacin cuantificada existen-cialmente es falsa.Seccin de ejercicios de repasoEjerciciosEn los ejercicios 1 al 6, diga si la afirmacin es una funcin proposi-cional. Para cada afirmacin que sea una funcin proposicional, d undominio de discurso.1. (2n + 1)2es un entero impar.2. Seleccione un entero entre 1 y 10.3. Sea x un nmero real.4. La pelcula gan el premio de la Academia como mejor pelculaen 1955.5. 1 + 3 = 4.6. Existe x tal que x < y (x, y nmeros reales).Sea P(n) la funcin proposicional n divide a 77. Escriba cada pro-posicin en los ejercicios 7 al 11 en palabras y diga si es verdadera ofalsa. El dominio de discurso es el conjunto de enteros positivos.7. P(11) 8. P(1)9. P(3) 10. n P(n)11. n P(n)Sea P(x) la afirmacin x est en un curso de matemticas. El domi-nio de discurso es el conjunto de todos los estudiantes. Escriba cadaproposicin en los ejercicios 12 al 17 en palabras.12. 13. x P(x) x P(x)g14. 15.16. 17.18. Escriba la negacin de cada proposicin en los ejercicios 12 al 17en smbolos y en palabras.Sea P(x) la afirmacin x es un atleta profesional y sea Q(x) la afir-macin x juega ftbol. El dominio de discurso es el conjunto de to-das las personas. Escriba cada proposicin en los ejercicios 19 al 26en palabras. Determine el valor de verdad de cada afirmacin.19. 2021. 22.23. 24.25. 26.27. Escriba la negacin de cada proposicin en los ejercicios 19 al 26en smbolos y en palabras.Sea P(x)la afirmacin x es un contador y sea Q(x) la afirmacin xtiene un Porsche. Escriba en smbolos y en palabras cada afirmacinen los ejercicios 28 al 31.28. Todos los contadores tienen un Porsche.29. Algunos contadores tienen un Porsche.30. Todos los dueos de Porsches son contadores.31. Alguien que tiene un Porsche es contador.32. Escriba la negacin de cada proposicin en los ejercicios 28 al 31en smbolos y en palabras.Determine el valor de verdad de cada afirmacin en los ejercicios 33 al38. El dominio de discurso es el conjunto de nmeros reales. Justifiquesus respuestas.33.34.35.36.37.38.39. Escriba la negacin de cada proposicin en los ejercicios 33 al 38en smbolos y en palabras.40. El seudocdigo del ejemplo 1.3.7 podra escribirse como sigue?for i = 1 to nif(P(di))return falsaelsereturn verdaderaCul es el significado literal de cada afirmacin en los ejercicios 41al 49? Cul es el significado deseado? Aclare cada afirmacin expre-sndola con otras palabras y en smbolos.41. De Querida Abby: Todos los hombres no engaan a sus esposas.42. De San Antonio Express News: Todas la cosas viejas no envidiana las cosas de veinte.43. Todos los 74 hospitales no entregan su reporte cada mes.44. El economista Robert J. Samuelson: Todo problema ambiental noes una tragedia.45. Comentario del consejal de Door County: Esto todava es DoorCounty y todos nosotros no tenemos un ttulo.46. Ttulo de una columna de Martha Stewart: Todas las pantallas delas lmparas no se pueden limpiar.47. Titular en el New York Times: Un mundo donde no todo es dulzu-ra y luz.48. Encabezado de una historia de subsidio a la vivienda: Todos nopueden pagar una casa.49. De Newsweek: Las investigaciones formales son una buena prc-tica en las circunstancias correctas, pero toda circunstancia no escorrecta.50. a) Use una tabla de verdad para probar que si p y q son proposi-ciones, al menos una de p q o q p es cierta.b) Sea P(x) la funcin proposicional x es un entero y sea Q(x) lafuncin proposicional x es un nmero positivo. El dominio dediscurso es el conjunto de todos los nmeros reales. Determinesi la siguiente prueba de que todos los enteros son positivos o to-dos los nmeros reales positivos son enteros es correcta o no.Por el inciso a),x ((P(x) Q(x)) (Q(x) P(x)))es verdadera. En palabras: Para toda x, si x es un entero, enton-ces x es positivo; o si x es positivo, entonces x es un entero. Porlo tanto, todos los enteros son positivos o todos los nmerosreales positivos son enteros.51. Demuestre el Teorema 1.3.14, inciso b).1.4 Cuantificadores anidados 29x P(x)(x P(x))x P(x)(x P(x))x ( P(x) Q(x))x ( Q(x) P(x))x ( P(x) Q(x))x ( P(x) Q(x))x ( P(x) Q(x))x ( Q(x) P(x))x ( P(x) Q(x))x ( P(x) Q(x))x(x2> x)x(x2> x)x(x > 1 x2> x)x(x > 1 x2> x)x(x > 1 x/(x2+1) < 1/3)x(x > 1 x/(x2+1) < 1/3)Considere escribir la afirmacinLa suma de cualesquiera dos nmeros reales positivos es positiva,simblicamente. Primero se observa que se trata de dos nmeros, se necesitan dos varia-bles, digamos x y y. La aseveracin se puede reestablecer como: Si x > 0 y y > 0, enton-ces x +y >0. La afirmacin dice que la suma de cualesquiera dos nmeros reales positivoses positiva, de manera que se necesitan dos cuantificadores universales. As, la afirmacinse escribe simblicamente comoxy((x > 0) (y > 0) (x + y > 0)).En palabras, para cada x y para cada y, si x > 0 y y > 0, entonces x + y > 0. El dominiode discurso es el conjunto de nmeros reales. Se dice que los cuantificadores mltiples co-mo x y son cuantificadores anidados. En esta seccin se exploran con detalle los cuan-tificadores anidados.1.4 Cuantificadores anidadosgReplanteemn (m < n)en palabras. El dominio de discurso es el conjunto de enteros.Primero se replantea esta afirmacin como: Para toda m, existe n tal que m < n. Demanera menos formal, esto significa que si toma cualquier entero m, hay un entero n ma-yor que m. Dicho de otra forma: No