Captulo 1Lgica matemtica1.1. Formas proposicionalesLalgicamatemticaseocupadel anlisisdelasproposicionesydemostracionesdel razon-amiento lgico, proporciona ideas claras y precisas sobre la naturaleza de la conclusin deductiva,desarrolla el pensamiento funcional y hace una contribucin esencial al desarrollo del pensamientocientco y creador. Esto se maniesta, por ejemplo, en la correcta comprensin de las estructuraslgicas y las tareas formales, en el reconocimiento de las semejanzas de los diferentes fenmenoslgicos, enlaaplicacindelasleyesyreglaslgicasyenlapretensindeclaridad, sencillezyeconoma en la expresin lingstica.Una de las propiedades de la forma de expresin matemtica, es la de representar los objetos,las imgenes mentales, los vnculos y las relaciones mediante smbolos (signos), y combinarlos entres.Denicin 1.1 ConstanteUna constante es un signo que tiene una determinada signicacin ja.Es decir; una constante tiene, en todo el desarrollo de una investigacin o en la solucin de unatarea, siempre la misma signicacin.Denicin 1.2 VariableUnavariableesunsignoquerepresentacualquierelementodeundominiobsicopreviamenteestablecido.Estoquieredecirqueunavariablesepuedesustituirporel signodecualquierelementodeldominiobsico. Entoncessehabladelasustitucindelavariable, odelainterpretacindelavariable.Denicin 1.3 TrminoPor trmino entendemos las constantes, las variables y sus combinaciones mediante los signos deoperacin y los signos tcnicos.Lostrminosson, portanto, lasdenominacionesdelosobjetosmatemticosolascombina-ciones de signos donde se presentan variables, constantes y signos de operaciones, y que mediantela interpretacin de las variables se omiten en las designaciones de los objetos matemticos. El ob-jeto matemtico, identicado como un trmino, y en cuya denominacin se omite este calicativo9www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 10despus de la interpretacin de las variables, se conoce como valor del trmino.Las proposiciones son estructuras lingsticas cuyo valor de verdad es, o verdadero o falso. Lalgica clsica, a travs de sus axiomas y principios, ha hecho algunas consideraciones sobre el con-tenido de verdad de una proposicin. El principio de la bivalencia expresa: Toda proposicin o esfalsa o es verdadera.De este principio se pueden deducir dos teoremas.1. El teorema de la tercera posibilidad excluida, expresa:Toda proposicin es falsa o verdadera.2. El teorema de la contradiccin excluida, expresa:Ninguna proposicin es falsa y verdadera al mismo tiempo.En las observaciones posteriores veremos que los dos teoremas, considerados en conjunto, ex-presan exactamente lo mismo que el principio de la bivalencia. Por consiguiente, se puede procedera la inversa; es decir deducir el teorema de la bivalencia a partir del principio de la tercera posibil-idad excluida y del principio de la contradiccin excluida.A cada proposicin se le hace corresponder un valor de verdad, o falso F o verdadero V. Es poresta razn que tambin se habla de una lgica bivalente. La asignacin de los valores de verdad F oV de una proposicin, no es tan sencillo de determinar. Aunque en el principio de la bivalencia seexpresa claramente que una proposicin es falsa o verdadera, no se puede decir inmediatamente sicada proposicin es falsa o verdadera. En matemticas existen actualmente muchas proposicionesquehastael momentonohanpodidoserdemostradas, concebida, lademostracin, comounaaseveracin de la verdad, a continuacin se dan dos ejemplos de este tipo de proposiciones.Ejemplo 1.1 Laproposicin:Todonmeroparqueseamayorque4,sepuederepresentarcomo la suma de dos nmeros primos, excepto el 2, existe desde el ao 1742. Hasta el momentono se ha podido demostrar si es una proposicin falsa o verdadera. (Suposicin de Goldbach).Denicin 1.4 Forma proposicionalUna estructura lingstica que contiene por lo menos una variable libre, se convierte en una proposi-cin, cuando se sustituyen todas las variables por smbolos, que denotan objetos del dominio bsico,recibe el nombre de forma proposicional.Ejemplo 1.2 8+xyimplicax2>y2paratodax, y R.Surespuesta debe ser un par ordenado;b) Cmo debe restringirx ey para que sea verdadera la proposicin de la parte a)?Resp: a) ; b) .16. Exprese en forma simblica cada uno de los enunciados, suponiendo quex,y,z R y queP : x < y, Q : y< z, R : x < z:a) Six < y, entoncesy z; b) Si(x < y ey< z), entoncesx < z;c) Si(x y ey< z), entoncesx z;d) Si no es verdad que(x < z ey< z), entoncesx z;e) x < y si y slo si(y< z yx < z);f ) Si es falso que(x < y y (ya seax < y oy< z)), entonces(x y, entoncesx < z).Resp: a) ; b) ; c) ; d) ; e) ; f ) .17. Cules de las proposiciones P, Q, R deben ser verdaderas y cules falsas para que((P P) Q) Rsea verdadera?Resp: .18. Representesimblicamentecadaunadelasproposicionescondicionalesdadasacontin-uacin. Escriba su recproca, inversa y contrapositiva tanto con smbolos como con palabras.Determinetambinel valordeverdadparalaproposicincondicional, parasurecproca,inversa y para su contrapositiva:a) Si4 < 6, entonces9 > 12; b) Si4 > 6, entonces9 > 12;c) [1[ < 3 si 3 < 1 < 3; d) [4[ < 3 si 3 < 4 < 3.Resp: a) ; b) ; c) ; d) .19. Proporcione la recproca, inversa y contrapositiva de cada una de las siguientes proposi-ciones:a) Six +y= 1 entoncesx2+y2 1; b) Si 2 + 2 = 4 entonces 3 + 3 = 8.Resp: a) ; b) .20. Considere la proposicin: six > 0 entoncesx2> 0 parax N:a) Proporcione la recproca, inversa y contrapositiva de la proposicin;b) Cul de las siguientes proposiciones es verdadera: la proposicin original, la recproca,la inversa o la contrapositiva?Resp: a) ; b) .www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 2121. Determine los valores de verdad de las siguientes proposiciones compuestas:a) Si 2 + 2 = 4, entonces 2 + 4 = 8; b) Si 2 + 2 = 5, entonces 2 + 4 = 8;c) Si 2 + 2 = 4, entonces 2 + 4 = 6; d) Si 2 + 2 = 5, entonces 2 + 4 = 6;e) Si la tierra es plana, entonces Vicente Rocafuerte fue el primer presidente de Ecuador;f ) Si la tierra es plana, entonces Sixto Durn-Ballen es presidente de Ecuador en el perido92 - 96;g) Si Sixto Durn-Ballen es presidente de Ecuador en el perido 92 - 96, entonces la tierraes plana;h) Si Sixto Durn-Ballen es presidente de Ecuador en el perido 92 - 96, entonces 2 + 2 =4.Resp: a) ; b) ; c) ; d) ; e) ; f ) ; g) ; h) .22. Supngase que sabemos que P Q es falso. Proporcione los valores de verdad para:a) P Q; b) P Q; c) Q P; d) P Q; e) P Q;f ) Q P; g) Q P; h) P Q; i) P Q; j) (P Q).Resp: a) ; b) ; c) ; d) ; e) ; f ) ; g) ; h) ; i) ; j) .23. UnlgicoledijoasuhijoSi noterminastucena, teirsdirectoadormirynoverstelevisin. Termin su cena y fue enviado directamente a la cama. Disctalo.Resp: .24. Alapreguntadecul detresestudiantesestudiabalgicafueobtenidaunarespuestacorrecta: si la estudiaba el primero, tambin lo haca el tercero, pero no era cierto que si laestudiaba el segundo lo haca asmismo el tercero. Quin estudiaba lgica?Resp: .25. Luis, Carlos, Joe, Fredocuparonenlaolimpiadadematemticas los cuatroprimerospuestos. Cuandolespreguntaronacercadeladistribucindelospuestos, dieronlastressiguientes respuestas:a) Fred - primero, Carlos - segundo; b) Fred - segundo, Luis - tercero;c) Joe - segundo, Luis - cuarto.Cmo se distribuyeron los puestos si en cada una de las respuestas slo una de las arma-ciones era verdadera?Resp: a) ; b) ; c) .26. Determine cul de cuatro estudiantes dio el examen si sabemos que:a) Si lo dio el primero, el segundo tambin;b) Si lo dio el segundo, el tercero tambin o bien el primero no lo dio;c) Si no lo dio el cuarto, lo dio el primero, pero el tercero no;d) Si el cuarto lo dio, el primero tambin.Resp: a) ; b) ; c) ; d) .27. ParaunaexpedicindeochopretendientesA, B, C, D, E, F, G, Hhayqueelegirseisespecialistas: bilogo, hidrlogo, sinptico, radista, mecnicoymdico. Lasfuncionesdelbilogo pueden ser realizadas por E y G, las del hidrlogo, B y F. Las del sinptico, F y G,las del radista, C y D, las del mecnico, C y H, las del mdico, A y D. Aunque algunos de lospretendientestienendosespecialidades,enlaexpedicincadaunopuederealizarslounafuncin. Quin y en calidad de qu ha de incluirse en la expedicin si F no puede ir sin B,D sin H y sin C, C no puede ir simultneamente con G, y A no puede ir junto con B?Resp: .www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 221.2. Construccin de tablas de verdadEl enunciado G = P [(Q R) Q] incluye tres proposiciones: P, Q y R, cada una puedeser verdadera o falsa de manera independiente. Existen en total23= 8 combinaciones posibles delos valores de verdad para P, Q y R y la tabla de verdad para G deber dar el valor de verdad deG para cada uno de los casos.Denicin 1.14 CombinacionesSi unaproposicincompuestaGconstadenenunciados, habr2ncombinacionesdevaloresdeverdad, es decir, n las en la tabla de verdad de G.Unatablaquedespliegatodoslosvaloresdeverdaddeunafrmula,paratodaslasposiblesinterpretacionesquepuedatener,sedenominatabladeverdaddelafrmula.Estatablapuedeconstruirse sistemticamente de la siguiente manera:1. Las primeras n columnas se encabezan con las variables proposicionales; y se construyen mscolumnas para las combinaciones parciales de enunciados y se culmina con el enunciado dado.2. Bajo cada una de las primeras n columnas, se enlistan las2nn-adas posibles de los valores deverdad de los componentes del enunciado G. Cadan-tupla se enlista en una la separada.3. Para cada la se calculan sucesivamente los valores de verdad restantes.Ejemplo 1.21 SeaG= (P Q) (P Q), construir la correspondiente tabla de verdad:P Q P QP Q GV V V V VV F F V FF V V V VF F V V FEjemplo 1.22 SeaG= [(P Q) Q] P), construir la correspondiente tabla de verdad:P Q P Q (P Q) Q GV V V F VV F F F VF V V V VF F F F VEjemplo 1.23 SeaG= [(P Q) P] Q), construir la correspondiente tabla de verdad:P Q P Q (P Q) P GV V V F VV F V F VF V V V VF F F F VEjemplo 1.24 Sea G= (P Q) (Q P), construir la correspondiente tabla de verdad:P Q P QQ P GV V V V VV F F F VF V V V VF F V V Vwww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 23Ejemplo 1.25 SeaG= (P Q) [(P Q) (Q P)],construirlacorrespondientetablade verdad:P Q P Q P Q Q P (P Q) (Q P) GV V V V V V VV F F F V F VF V F V F F VF F V V V V V1.2.1. Operaciones con frmulas lgicas y sus propiedadesEnelestudiodelasfuncionesproposicionaleshemosutilizadolasvariablesP,Q,R,...paradesignarlasproposiciones. Estasvariablespodemosinterpretarlasconelementosdeundominiobsico, esdecir, conproposiciones. Sudominioestformadosolamentepordoselementos, losvalores de verdad V y F. Las constantes en este caso las constituyen los conectores lgicos. Medianteel enlace lineal de las variables con valores de verdad P, Q, etc., y conectores, as como mediantela aplicacin de los signos tcnicos (parntesis), podemos formar series de signos.Denicin 1.15 Frmula bien formadaUnafrmulabienformada,sedenedentrodelalgicaproposicional enlossiguientestrminosrecursivos:1) Las variables P, Q, ... son frmulas.2) a) Si P es una frmula, entonces P tambin es una frmula.b) Si P y Q son frmulas entonces P Q, P Q, P Q, P Q tambin son frmulas.3) Una serie de signos P, Q, ... es una frmula solo cuando se trata de los casos 1 y 2.Enlarepresentacinsimblicaseinterpretanlossignos , , , , ,querecibenelnom-bre de conectores, como signos de funciones proposicionales y tambin como signos de funcionesveritativas. AlosliteralestalescomoP, Q, R,... quesonusadosparadenotarproposicionessedenominan frmulas atmicas o tomos. No es difcil reconocer que expresiones como P , P noson frmulas. Cuando no exista confusin se suprimen los parntesis asignando rangos decrecientesa los conectores proposicionales de la siguiente manera; , , , ,de manera que al conectorproposicional con mas alto rango se lo evalue al nal.Ejemplo 1.26 1) P Q R = P (Q R);2) P Q R S = P Q (R S) = P [Q (R S)].Ahora vamos a establecer una relacin entre los valores de verdad y las funciones veritativaspor una parte y las expresiones, por otra. Las variables P, Q, ... las utilizamos ahora como variablesdel valor de verdad, y de igual forma los conectores proposicionales , , , , como signos delas funciones veritativas clsicas.SobrelabasedelasarmacioneshechaspodemosindicarelcorrespondientevalordeverdadparacadainterpretacindelasvariablesP, Q, ... conlosvaloresdeverdad. Enlasexpresionescomplicadas de la lgica proposicional tambin es posible calcular de esta forma, en nitos pasos,los valores de verdad, al hacer las diferentes interpretaciones de las variables.Comparando las tablas de verdad podemos decidir si dos frmulas G y H tienen la misma tablade valores de verdad. Con esto tambin podemos mostrar si una frmula formada a partir de GyH,esunaidentidaddelalgicaproposicional.Laigualdaddelastablasdevaloresdeverdady la identidad de la lgica proposicional, sin embargo, no son exactamente lo mismo. La igualdadwww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 24delatabladevaloresdeverdadesunarelacinentredosfrmulas; ylapropiedaddeserunaidentidad es una peculiaridad de una frmula. Cuando nos interesamos por la igualdad de la tabladevaloresdeverdad, entoncescomparamoslosvaloresdeverdaddedosfrmulasentodaslassustitucionesposibles.Cuandonosinteresamosporlavalidezgeneraldeunafrmula,queremosestablecer si esta determinada frmula toma, en cada interpretacin, el valor de verdad V. En estecaso, se determina el valor de verdad de una nueva frmula formada a partir de las frmulas G yH en todas las sustituciones posibles. De las frmulas con las mismas tablas de verdad, G y H, sepueden formar siempre identidades de la lgica proposicional, es decir, frmulas de validez general.Teorema 1.3 Una frmula doblemente negada tiene la misma tabla de valores de verdad que lacorrespondiente frmula dada, es decir;P = P es una identidad de la lgica proposicional.DemostracinPPPV F VF V FTeorema 1.4 Para la conjuncin, la disjuncin y la equivalencia se cumplen la ley conmutativay la ley asociativa con respecto a la igualdad de las tablas de valores de verdad. Para la implicacinno se cumple ni la ley asociativa, ni la ley conmutativa.DemostracinP Q P Q Q P P Q Q P P Q Q PV V V V V V V VV F V V F F F FF V V V F F F FF F F F F F V VDado que G1 = (P Q) R y G2 = P (Q R), entoncesP Q R (P Q) R P (Q R) (P Q) R P (Q R) G1G2V V V V V V V V VV V F V V F F F FV F V V V F F F FV F F V V F F V VF V V V V F F F FF V F V V F F V VF F V V V F F V VF F F F F F F F FEn lgica las proposiciones idnticamente verdaderas o bien idnticamente falsas desempeanimportante papel. Las proposiciones idnticamente verdaderas son siempre verdaderas independi-ente de si las proposiciones que las forman son verdaderas o falsas.Teorema 1.5 Para las proposiciones idnticamente verdaderas e idnticamente falsas, con todoP son ciertas las siguientes frmulas:P P= V; P V= V; P F= PP P= F; P V= P; P F= FDemostracinwww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 25P P Q P V P F P P P V P FV V V V F V FF V V F F F FTeorema 1.6 Las equivalencias siguientesP Q= Q P; P Q= Q PP Q= Q P; P Q= Q Pson identidades de la lgica proposicional.DemostracinP Q P QQ PP QQ PV V V V V VV F F F V VF V V V V VF F V V F FP Q Q PP Q Q PF F V VV V V VV V F FV V V VTeorema 1.7 Las equivalencias siguientes(P Q)= P Q; (P Q)= P Q(P Q) P= P; (P Q) P= P(P Q) Q= Q; (P Q) Q= QP Q= P Q; P Q= (P Q) (Q P)son identidades de la lgica proposicional.DemostracinP Q (P Q)P Q (P Q)P Q (P Q) P (P Q) PV V F F F F V VV F F F V V V VF V F F V V F FF F V V V V F F(P Q) Q (P Q) Q P QP Q P Q (P Q) (Q P)V V V V V VF F F F F FV V V V F FF F V V V VTeorema 1.8 Laconjuncines, conrespectoaladisjuncinenamboslados, distributivayviceversa, es decir, que las siguientes frmulas son identidades de la lgica proposicionalP (Q R)= (P Q) (P R); (Q R) P= (Q P) (R P)P (Q R)= (P Q) (P R); (Q R) P= (Q P) (R P)Demostracinwww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 26P Q R P (Q R) (P Q) (P R) (Q R) P (Q P) (R P)V V V V V V VV V F V V V VV F V V V V VV F F F F F FF V V F F F FF V F F F F FF F V F F F FF F F F F F FP (Q R) (P Q) (P R) (Q R) P (Q P) (R P)V V V VV V V VV V V VV V V VV V V VF F F FF F F FF F F FTeorema 1.9 Conjuntamente con la distributividad se cumple que la implicacin, con respectoa las dems funciones veritativas, es distributiva a la derecha, pero no distributiva a la izquierda,es decir, que las siguientes frmulas son de validez generalP (Q R)= (P Q) (P R); P (Q R)= (P Q) (P R)P (Q R)= (P Q) (P R); P (Q R)= (P Q) (P R)DemostracinP Q R P (Q R) (P Q) (P R) P (Q R) (P Q) (P R)V V V V V V VV V F F F V VV F V F F V VV F F F F F FF V V V V V VF V F V V V VF F V V V V VF F F V V V VP (Q R) (P Q) (P R) P (Q R) (P Q) (P R)V V V VF F F FV V F FV V V VV V V VV V V VV V V VV V V Vwww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 27Teorema 1.10 Si la conclusin, segundo miembro, de una implicacin es igualmente una impli-cacin, entonces las dos premisas (primeros miembros), se pueden unir formando una sola premisaP (Q R)= (P Q) R; (P Q) R= (P R) (Q R)DemostracinP Q R P (Q R) (P Q) R (P Q) R (P R) (Q R)V V V V V V VV V F F F F FV F V V V V VV F F V V V VF V V V V V VF V F V V V VF F V V V V VF F F V V V VEjemplo 1.27 Utilizando las leyes de la lgica proposicional, demostrar que:(P Q) (P Q)= (P Q) (P Q).Solucin(P Q) (P Q)= [(P Q) (P Q)] [(P Q) (P Q)]= [(P Q) (P Q)] [(P Q)) (P Q)]= [(P Q) (P Q)] [(P Q) (P Q)]= (P Q P Q) [(P Q) (P Q)]= [(P P) (Q Q)] [(P Q) (P Q)]= (V V) [(P Q) (P Q)]= V [(P Q) (P Q)]= (P Q) (P Q).Ejemplo 1.28 Utilizando las leyes de la lgica proposicional, demostrar que:[(P Q) P] Q= Q P.Solucin[(P Q) P] Q= [(P Q) P] Q= [(P Q) P] Q= (P) Q= P Q= Q P.Ejemplo 1.29 Utilizando las leyes de la lgica proposicional, demostrar que:[(P Q) (P R)] (Q R)= Q (P R).www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 28Solucin[(P Q) (P R)] (Q R)= [(P Q) (P R)] (Q R)= (P Q) (P R) (Q R)= (P Q) (P R) Q R= Q R (P R)= Q [(R P) (R R)]= Q [(R P) V]= Q (R P)= Q (P R).Ejemplo 1.30 Utilizando las leyes de la lgica proposicional, demostrar que:[(P Q) R] [(Q P) R]= (P Q) R.Solucin[(P Q) R] [(Q P) R]= [(P Q) R] [(Q P) R]= [(P Q) R] [(Q P) R]= [(P Q) R] [(Q P) R]= [(P Q) R] [(Q P) R]= [(P Q) (Q P) R] [R (Q P) R]= [(P Q Q) (P Q P)] R V= [(P Q) (P Q)] R= (P Q) R= (P Q) R= (P Q) R.Ejemplo 1.31 Utilizando las leyes de la lgica proposicional, demostrar que:[(P Q) P] (P Q)= P Q.Solucin[(P Q) P] (P Q)= [(P Q) P] (P Q)= [(P Q) P] (P Q)= P P Q= P Q= P Q.1.2.2. Tautologas y falaciasDenicin 1.16 TautologaSiunaproposicincompuestaessiempreverdaderabajotodassusinterpretaciones,independien-temente de los valores de vericacin de sus componentes, decimos que la proposicin compuestaes una tautologa.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 29Esdecir, aunenunciadoqueesverdaderoparatodoslosvaloresposiblesdesusvariablesproposicionalesseledenominatautologa. Cuandosecompruebaqueunaequivalenciaesunatautologa, signicaquesusdospartescomponentessonsiempreoambasverdaderasoambasfalsas,paracualesquiervaloresdelasvariablesproposicionales.Portantolosdosladossonslodiferentes maneras de proponer el mismo enunciado y se dice que son logicamente equivalentes.Denicin 1.17 FalaciaUna frmulaG es una falacia, si G es una tautologa.Ejemplo 1.32 Utilizando una tabla de verdad, determinar si la frmulaG = (P Q) (P Q)es tautologa.SolucinP Q P QP Q (P Q) ( P Q)V V V V VV F F F VF V V V VF F V V VPor lo tanto G si es tautologa.Ejemplo 1.33 Utilizando una tabla de verdad, determinar si la frmulaG = (Q P) (P Q)es tautologa.SolucinP Q Q P P Q (Q P) (P Q)V V V V VV F V F FF V F V VF F V V VPor lo tanto G no es tautologa.Ejemplo 1.34 Utilizando una tabla de verdad, determinar si la frmulaG = (P Q) (Q P)es tautologa.SolucinP Q P QQ Q (P Q) ( Q P)V V V V VV F F F VF V V V VF F V V VPor lo tanto G si es tautologa.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 30Ejemplo 1.35 Utilizando una tabla de verdad, determinar si la frmulaG = (P Q) [(P Q) (Q P)]es tautologa.SolucinP Q P Q (P Q) (Q P (P Q) [(P Q) (Q P)]V V V V VV F F F VF V F F VF F V V VPor lo tanto G si es tautologa.Ejemplo 1.36 Utilizando una tabla de verdad, determinar si la frmulaG = [(P Q) (Q R)] (P R)es tautologa.SolucinP Q R (P Q) (Q P P Q [(P Q) (Q R)] (P R)V V V V V VV V F F F VV F V F V VV F F V F VF V V V V VF V F F V VF F V V V VF F F V V VPor lo tanto G si es tautologa.Ejemplo 1.37 Utilizando una tabla de verdad, determinar si la frmulaG = [P (Q R)] [(P Q) R]es tautologa.SolucinP Q R (P (Q R) (P Q) R [P (Q R)] [(P Q) R]V V V V V VV V F F F VV F V V V VV F F V V VF V V V V VF V F V F FF F V V V VF F F V F FPor lo tanto G no es tautologa.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 311.2.3. Tarea1. Construya la tabla de verdad para cada una de las siguientes proposiciones:a) (P Q) [(P Q) (P Q)]; b) [(P Q) R] (P Q);c) [(P Q) (P R)] (Q P)]; d) P P; e) (P Q) R;f ) (P P) P; g) P Q; h) (P Q).Resp: a) ; b) ; c) ; d) ; e) ; f ) ; g) ; h) .2. Utilizando las leyes de la lgica proposicional, demostrar queP Q= (P Q) (P Q)Resp: .3. Utilizando las leyes de la lgica proposicional, demuestre o refute:a) P Q= (P Q) (P Q); b) P (Q R)= (P Q) (P R);c) (P Q) R= P (Q R).Resp: a) ; b) ; c) .4. Simplique las siguientes frmulas y diga cuales son tautologas y cuales falacias:a) P (P Q)] (P Q); b) (P Q) [(R P) Q].Resp: a) ; b) .5. Simplique las siguientes frmulas y diga cuales son tautologas y cuales falacias:a) (R Q) (P Q R) (P Q R); b) (P Q) (R Q);c) (P Q) Q [(R Q) P].Resp: a) ; b) ; c) .6. Simplique las siguientes frmulas y diga cuales son tautologas y cuales falacias:a) (P Q) (R S) (P S); b) (P Q) (P R) R;c) (P Q) (P R) (Q S).Resp: a) ; b) ; c) .7. Simplique las siguientes frmulas y diga cuales son tautologas y cuales falacias:a) (P Q) Q (P R); b) (P Q) (P R) (Q R);c) (P Q) Q (P (R S)].Resp: a) ; b) ; c) .8. Simplique las siguientes frmulas y diga cuales son tautologas y cuales falacias:a) (P S) (P Q) [(S R) T] (Q R);b) P (Q P) [(Q R) S];c) (P Q) (R Q) (R S) [(S P) T].Resp: a) ; b) ; c) .9. Simplique las siguientes frmulas y diga cuales son tautologas y cuales falacias:a) (P Q) [(P Q) (Q P)]; b) [(P Q) (Q R) P] R;c) [P (Q R)] (Q R) [(S R) P] S.Resp: a) ; b) ; c) .1.3. Transformacin de frmulasLaigualdaddelosvaloresdeverdaddedosproposicioneslahemosdemostradohastaahorautilizando las tablas completas de valores de verdad. Con su ayuda pudimos decidir si una frmulawww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 32dada es o no una identidad de la lgica proposicional.Por esta va hemos conocido mumerosas frmulas con las tablas de valores. Otras identidades,es decir; las leyes de la lgica proposicional, las obtenemos a partir de las frmulas dadas y medi-ante sustituciones o transformaciones en frmulas equivalentes.En esta seccin veremos cmo obtener equivalencias e implicaciones lgicas sin utilizar tablasde verdad. Tambin explicaremos el signicado de teorema y de demostracin. Empezaremos condos reglas tiles, que sin embargo deben manejarse con cuidado.Teorema 1.11 Si enunafrmuladevalidezgeneral, esdecir, enunaidentidaddelalgicaproposicional, se sustituye una variable proposicional por una frmula cualquiera en todos los lu-gares donde se presenta la frmula correspondiente, entonces se obtiene nuevamente una frmulade validez general.Teorema 1.12 Cuando en una frmula G se sustituye una cierta subfrmulaG1por una fr-mulaG2, que toma los mismos valores de verdad queG1, entonces la frmula obtenida F tiene losmismos valores de verdad que la frmula G. La frmula G, una vez sustituidaG1debe sustituirseporG2en todos los lugares donde esta se presenta.Ejemplo 1.38 Consideremos la proposicinG= [P (P Q)] Qque es una tautologa. Si reemplazamos, cada vez que apareceP, por la proposicinG1 = Q Robtenemos la tautologaH= [(Q R) ((Q R) Q)] Q.Si en cambio reemplazamosQ, cada vez que aparece, porG1, obtenemos la tautologaH= [P (P (Q R))] (Q R).Ejemplo 1.39 Consideremos la proposicinG= [(P Q) (P R)] [Q (P R)]que no es una tautologa. Obtenemos proposiciones lgicamente equivalentes si reemplazamos P Qporsuequivalencialgica P QosireemplazamosunaolasdosvecesqueapareceP RporP R. Podemostambinreemplazar(P Q) (P R)porP (Q R). DeestamaneraGes lgicamente equivalente a las siguientes proposiciones entre otras:[(P Q) (P R)] [Q (P R)][(P Q) (P R)] [Q (P R)][(P (Q R)] [Q (P R)].Denicin 1.18 Frmula vlidaUnafrmulaGes vlidaoconstituyeunatautologa, si yslosi es verdaderabajotodas lasinterpretaciones. En caso contrario la frmula G es invlida.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 33Denicin 1.19 Frmula inconsistenteUnafrmulaGsedenominainconsistenteoinsatisfactible, si yslosi esfalsabajotodaslasinterpretaciones. En caso contrario la frmula G es consistente o satisfactible.De las deniciones anteriores, las observaciones siguientes son obvias:1. Una frmula es vlida, si y slo si su negacin es inconsistente.2. Una frmula es inconsistente, si y slo si su negacin es vlida.3. Una frmula es invlida, si y slo si hay por lo menos una interpretacin bajo la cual lafrmula es falsa.4. Una frmula es inconsistente, si y slo si hay por lo menos una interpretacin bajo la cualla frmula es verdadera.5. Si una frmula es vlida, entonces es consistente pero no viceversa.6. Si una frmula es inconsistente, entonces es invlida pero no viceversa.Ejemplo 1.40 Vericar la validez o inconsistencia de la frmula:[(P Q) (Q R)] (P R)SolucinP Q R (P Q) (Q R) P R [(P Q) (Q R)] (P R)V V V V V VV V F F F VV F V F V VV F F V F VF V V V V VF V F F V VF F V V V VF F F V V VPor lo tanto G es una frmula vlida.Ejemplo 1.41Vericar la validez o inconsistencia de la frmula:[(P (Q R)] [(P Q) R]SolucinP Q R (P (Q R) (P Q) R [(P (Q R)] [(P Q) R]V V V V V VV V F F F VV F V V V VV F F V V VF V V V V VF V F V F FF F V V V VF F F V F FPor lo tanto G no es una frmula vlida.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 341.3.1. Formas normalesEn lgica matemtica es muy importante el poder transformar frmulas de una forma a otra,especialmente a las denominadas formas normales. Para lograr estas transformaciones de frmulas,se utiliza el concepto de equivalencias de frmulas.Denicin 1.20 Frmulas equivalentesLas frmulas G y H son equivalentes si los valores de verdad de G y H son los mismos bajo todaslas interpretaciones de estas frmulas.Por supuesto que nuestro inters no se limita a estudiar una simple clasicacin de los enun-ciados del lenguaje; pero tampoco intentamos internarnos en el fascinante mundo de la deduccinlgicasinantesestarsegurosdeconocerycomprenderalgunosconceptoselementales. Lasdosformas normales que nos interesa obtener y que son utilizadas en prueba mecnica de teoremas,son la forma normal conjuntiva y la forma normal disjuntiva.Denicin 1.21 Forma normal conjuntivaUna frmula G se dice que est en forma normal conjuntiva si y slo si G tiene la formaG= G1 G2 Gnn Ndonde cada una de las frmulasG1,G2, ...,Gn, se expresan como una conjuncin de literales.Ejemplo 1.42 Expresar la frmulaG= (Q P) (P Q)en forma normal conjuntiva.Solucin(Q P) (P Q)= (Q P) (P Q)= (Q P) (P Q)= (Q P) (P Q)= [Q (P Q)] [P (P Q)].Ejemplo 1.43 Expresar la frmulaG= (P Q) [(P Q) (Q P)]en forma normal conjuntiva.Solucin(P Q) [(P Q) (Q P)]= (P Q) (P Q)= [(P Q) (P Q)] [(P Q) (P Q)].Denicin 1.22 Forma normal disjuntivaUna frmula G se dice que est en forma normal disjuntiva si y slo G si tiene la formaG= G1 G2 Gnn Ndonde cada una de las frmulasG1,G2, ...,Gn, se expresan como una disjuncin de literales.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 35Ejemplo 1.44 Expresar la frmulaG= (Q P) (P Q)en forma normal disjuntiva.Solucin(Q P) (P Q)= (Q P) (P Q)Ejemplo 1.45 Expresar la frmulaG= (P Q) [(P Q) (Q P)]en forma normal conjuntiva.Solucin(P Q) [(P Q) (Q P)]= (P Q) (P Q)= [(P Q) (P Q)] [(P Q) (P Q)]= (P Q) (P Q)= (P Q) (P Q)Un hecho que es muyimportante anotar, es quecualquier frmula de lalgica proposicionalpuede ser transformada a una de las formas normales, utilizando las leyes de la lgica proposicional.1.3.2. Consecuencias lgicasDenicin 1.23 Consecuencia lgicaDadas las frmulasG1, G2, ..., Gny una frmula G, G se denomina consecuencia lgica deG1,G2, ..., Gnsi y slo si para cualquier interpretacin en la cual G1 G2 Gnes verdad, Gtambin lo esG1,G2, ...,Gnse denominan axiomas de G.Teorema 1.13 DadaslasfrmulasG1, G2,..., GnyunafrmulaG,Gesunaconsecuencialgica deG1,G2, ...,Gnsi y slo si la frmula(G1 G2 Gn) G es vlida.Demostracin SupongaqueGesunaconsecuencialgicadeG1, G2, ..., Gn. SeaIunainterpretacinar-bitraria. Si G1, G2, ..., GnsonverdaderosenI, entoncespordenicindeconsecuencialgicaGesverdaderoenI. Entonces (G1 G2 Gn) GesverdaderoenI. Porotraparte, siG1, G2, ..., GnsonfalsosenI, entonces (G1 G2 Gn) GesverdaderoenI. As, de-mostramos que (G1 G2 Gn) Ges verdaderobajocualquier interpretacin. Estoes,(G1 G2 Gn) G es una frmula vlida.Supongamos que (G1 G2 Gn) G es una frmula vlida. Para cualquier interpretacinI, si G1 G2 Gnes verdadero en I, G debe ser verdadero en I. Por consiguiente G es unaconsecuencia lgica deG1,G2, ...,Gn.Ejemplo 1.46 SeanG1P (Q R)G2(P S) RG QPruebe si G es consecuencia lgica deG1yG2.Solucinwww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 36Debemosprobarquelafrmula [P (Q R)] [(P S) R] Q, esverdaderaofalsa,decir:[P (Q R)] [(P S) R] Q= [P (Q R)] [P S R] Q= [(P Q R) (P S R)] Q= (P Q R) (P S R) Q= (P Q R) (P Q R) S= V.Lo cual indica que G es consecuencia lgica deG1 yG2.Ejemplo 1.47 SeanG1P Q)G2Q RG3RG RPruebe si G es consecuencia lgica deG1,G2yG3.SolucinDebemos probar que la frmula[(P Q) (Q R) R] R, es verdadera o falsa, decir:[(P Q) (Q R) R] R= [(P Q) (Q R) R] R= (P Q) (Q R) (R R)= V.Lo cual indica que G es consecuencia lgica deG1,G2 yG3.Teorema 1.14 DadaslasfrmulasG1, G2,..., GnyunafrmulaG,Gesunaconsecuencialgica deG1,G2, ...,Gnsi y slo si la frmulaG1 G2 Gn G es inconsistente.DemostracinPorelteoremaanterior,GesunaconsecuencialgicadeG1, G2,..., Gnsiyslosilafrmula(G1 G2 Gn) G es vlida. As, G es una consecuencia lgica deG1,G2, ...,Gn si y slosi la negacin de(G1 G2 Gn) G es inconsistente[(G1 G2 Gn) G]= [(G1 G2 Gn) G]= (G1 G2 Gn) G= (G1 G2 Gn) G= G1 G2 Gn GPor lo tanto, concluimos que el teorema es verdadero.Ejemplo 1.48 SeanG1P (Q R)G2(P S) RG QPruebe si G es consecuencia lgica deG1yG2.Solucinwww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 37Debemosprobarquelafrmula [P (Q R)] [(P S) R] Q,esverdaderaofalsa,decir:[P (Q R)] [(P S) R] Q= [(P Q R) (P S R)] Q= (P Q R) (P Q R) S= (P Q R) (P Q R) S= F.Lo cual indica que G es consecuencia lgica deG1 yG2.Ejemplo 1.49 SeanG1P Q)G2Q RG2RG RPruebe si G es consecuencia lgica deG1,G2yG3.SolucinDebemos probar que la frmula[P Q) (Q R) R] R, es verdadera o falsa, decir:[P Q) (Q R) R] R= (P Q) (Q R) (R R)= F.Lo cual indica que G es consecuencia lgica deG1,G2 yG3.1.3.3. Tarea1. Determine la validez o inconsistencia, luego transforme a una de sus formas normales lassiguientes frmulas::a) [P (P Q)] (P Q);b) (P Q) [(R P) Q];c) (R Q) (P Q R) (P Q R);d) (P Q) Q [(R Q) P].Resp: a) ; b) ; c) ; d) .2. Determine la validez o inconsistencia, luego transforme a una de sus formas normales lassiguientes frmulas:a) (P Q) (R S) (P S);b) (P Q) (P R) R;c) (P Q) (P R) (Q S);d) (P Q) Q (P R);e) (P Q) (P R) (Q R);f ) [(P Q) (Q R) P] R.Resp: a) ; b) ; c) ; d) ; e) ; f ) .3. Determine la validez o inconsistencia, luego transforme a una de sus formas normales lassiguientes frmulas:a) (P Q) Q [P (R S)];b) (P S) (P Q) [(S R) T] (Q R);c) P (Q P) [(Q R) S];www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 38d) (P Q) (R Q) (R S) [(S P) T];e) (P Q) [(P Q) (Q P)];f ) [P (Q R)] (Q R) [(S R) P] S.Resp: a) ; b) ; c) ; d) ; e) ; f ) .4. Decir cual de los siguientes enunciados son consecuencia lgica:a)G1(P Q) R)G2S TG3U LG4P UG5S LG Rb)G1(P Q) RG2R SG3(P Q)G4(S T) UG Uc)G1(P Q) (R S)G2(P Q)G3(R S) (T U)G T UResp: a) ; b) ; c) .5. Losalumnossonestudiososolosestudiososreprueban. Si losestudiososreprueban, en-tonces los inteligentes son felices o los alumnos no son estudiosos. Los alumnos son estudiososy los inteligentes no son felices. No es verdad que los inteligentes son felices. Los estudiantesno reprueban?Resp: .6. Juego ftbol o estudio. Si paso el examen no estudio. Sucede que no voy a jugar ftbol.En consecuencia no pas el examen.Resp: .7. La lgica es fcil. Si el lgebra es hermosa, entonces la Lgica no es fcil o la Matemticaes la reina de las ciencias. El Algebra es hermosa. En consecuencia, la Matemtica es la reinade las ciencias.Resp: .8. Ayer no fue mircoles o maana no es martes. Hoy es jueves y ayer fue mircoles. Hoy eslunes si y slo si maana es martes. En consecuencia, hoy es lunes.Resp: .www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 399. LuisharunviajeaEuropasi lograterminarsucarrera. Luisterminasucarrera, ysihace un viaje a Europa, entonces no asiste a nuestra reunin anual. En consecuencia, Luisno asistir a nuestra reunin anual.Resp: .10. Si faltan ejercicios o encuentro premisas, entonces acabo la tarea. Si el libro est claro y nome falta creatividad, entonces encuentro premisas. No acabo la tarea. En consecuencia mefalta creatividad o el libro no est claro.Resp: .11. Si ganamosel campeonato, recibimosel premio. Si jugamosyganamosel campeonato,recibiremos el premio. Jugaremos y ganaremos el campeonato. En consecuencia, recibiremosel premio.Resp: .12. Repruebo el examen o sigo mis estudios. Si repruebo el examen, perder la beca y me irde la ciudad. No perder la beca o no me ir de la ciudad. Luego, seguire estudiando.Resp: .13. Los aviones son veloces o las diligencias respetan los semforos. Si los hombres vuelan y lasbicicletas no contaminan, entonces no es verdad que las diligencias respetan los semforos.Los hombres vuelas y las bicicletas no contaminan. En conclusin, los aviones son veloces.Resp: .1.4. Expresiones de la lgica de predicadosEl clculo proposicional es una teora de la lgica, completa y autnoma, pero totalmente inade-cuada para la mayor parte de las matemticas. El problema reside en que el clculo proposicionalno permite el uso de un nmero innito de proposiciones. Adems, la notacin es difcil para mane-jar un gran nmero nito de proposiciones.Por ejemplo, con frecuencia encontramos una sucesin innita de proposiciones P(x) con ndicesen N. La armacin informal P(x) es verdadera para todax signica P(0) es verdadera,P(1)es verdadera, P(2) es verdadera, etc. El nico simbolismo que podramos utilizar, segn el clculoproposicional seraP(0) P(1) P(2) ..., pero no es aceptable en el clculo proposicional.En forma similar, la armacin informal P(x) es verdadera para algunax correspondera alinaceptado P(0) P(1) P(2) .... Para darle la vuelta a este problema, necesitamos dos smbolosnuevos: uno que signique para todo y otro que signique para algn.Entonces necesitamos saber las reglas para utilizar los nuevos smbolos y combinarlos con losviejos. Este sistema de smbolos y reglas se llama clculo de predicados. Los nuevos smbolos queintroduciremos se llaman cuanticadores.Supongamosque P(x)/x UesunafamiliaconndicesenunconjuntoUquepuedeseinnito; el conjuntoUse llama el dominio de individuos o universo de individuos.Mediante la introduccin de existe ... es conrmada la existencia de por lo menos un elementodel conjunto base que satisface la forma proposicional dada. Esta proposicin es una proposicinexistencial.Proposicionesconlaformulacinunaparte,casitodo,lamayora,algunos,etc.,sonwww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 40tambinproposicionesexistenciales.Cuandohablamosdeproposicionesexistenciales,nosreferi-mostambinaproposicionesparticulares, yaqueestasnosereerenatodosloselementosdelconjuntoquenosinteresa,sinosoloaunaparte.Enestecasodenominamosalacuanticacin,particularidad.De forma anloga, se denomina a las proposiciones en que aparece la formulacin para todos,proposiciones universales o generales, ya que estas se reeren a todos los elementos del conjunto devariables. Tal cuanticacin se denomina tambin generalizacin. La cuanticacin particularidady generalizacin son operaciones de la lgica de predicados.Partiendodelas formas proposicionales relacionadas previamenteconlos operadores, talescomoexiste..., paratodo..., noexisteningn..., hemosobtenidoproposicionesfalsasoverdaderas. Para estos operadores denominados tambin cuanticadores, se han introducido en lalgica matemtica signos especiales.El cuanticador existencial (particularizador) existe (por lo menos) un ... es simbolizado con?. Si el smbolo ? se encuentra ante una forma proposicionalP(x), esto quiere decir que existepor lo menos un elemento del conjunto fundamental que posee la propiedad reejada en la formaproposicionalP(x). Utilizamos las escrituras x P(x).La tachadura vertical o la relacin que se establece entre el smbolo y el smbolo ,, debeexpresar que no existe ningn elemento del conjunto fundamental que posea la propiedad indicadaen la forma proposicionalP(x).El cuanticador universal (operador universal, generalizador) para todo ... se representa conel smbolo. Si el smboloseencuentraanteunaformaproposicional P(x), estoquieredecirquelapropiedadreejadaenlaformaproposicional P(x)esaplicableparacadaelementodel dominio de individuos. El cuanticador universal forma pareja con una variable, x, signica,para todo x ....La tachadura vertical o la relacin que se establece entre el cuanticador universal y el smbolo, debe expresar que la propiedad reejada en P(x) no es aplicable para todos los elementos deldominio de individuos.Lalgicadepredicadosolgicadeprimergrado,nosenseaqueparalacuanticacinsloson admisibles las variables de individuos. Las variables de individuos cuanticados dejan de servariables libres para convertirse en variables ligadas. Para crear expresiones de la lgica de predi-cados utilizamos adems de los smbolos para las variables de individuos, constantes de individuos,variables predicativas, cuanticadores y los conectores de la lgica proposicional.En la lgica proposicional comprobamos el valor de verdad de una expresin mediante la susti-tucin de las variables de dicha expresin por sus valores de verdad, teniendo en cuenta las disposi-ciones correspondientes. El valor de verdad de una expresin de la lgica de predicados dependeno solo del cuanticador sino tambin de las variables de individuos y del conjunto de individuostomado como base, as como de la sustitucin o interpretacin de las variables predicativas.A la proposicin compuesta x P(x) se le asignan valores de verdad de la manera siguiente: x P(x) es verdadero siP(x) es verdadero para todax enU; en cualquier otro caso x P(x) esfalsawww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 41La proposicin compuesta x P(x) tiene los siguientes valores de verdad: x P(x) es verdadero siP(x) es verdadera para al menos unax enU; x P(x) es falso siP(x)es falsa para todax enUAnalicemoslaproposicin xP(x)demaneramsdetallada. LaexpresinP(x)sellamapredicado. Para formar una oracin hay que tener un sujeto. Por ejemplo, el predicado ... es maspoblada que Quito se transforma en la oracin Guayaquil es mas poblada que Quito al dar co-mo sujeto Guayaquil. Si llamamos Pal predicado la oracin podra escribirse como P(Guayaquil).Cada sujeto da una oracin.En nuestra lgica simblica dar un predicado es establecer una funcin que produce una proposi-cin siempre que le demos un elemento del dominio de individuos, esto es, una funcin proposicional- valuada con dominio de individuosU. Seguimos nuestra prctica usual y denotamos tal funcinporP(x). LavariablexenlaexpresinP(x)sellamavariablelibredel predicado. EntantoxvaraenUlosvaloresdeverdaddeP(x)puedenvariar. Encontraste, laproposicin xP(x)tieneunsignicadojoyunvalordeverdadquenovaraconx.Lavariablexen xP(x)sellama variable acotada; est acotada por el cuanticador . Como x P(x) tiene un signicado joy un valor de verdad sera intil y poco natural cuanticarla de nuevo. Esto es, sera vano intro-ducir x[ x P(x)] y x[ x P(x)] ya que sus valores de verdad son los mismos que los de x P(x).Podemos tambin considerar predicados que son funciones de ms de una variable, posiblementede ms de un dominio de individuos, y en tales casos el uso de varios cuanticadores resulta natural.Ejemplo 1.50 Conestosejemplosenmentevamosadarunadescripcinmsdetalladayformal. SeanU1, U2, ..., Unconjuntosnovacos. UnpredicadodenargumentossobreU1xU2x... xUnesunafuncinP(x1, x2, ..., xn)condominiodeindividuos U1xU2x... xUnylosvalores de la funcin son proposiciones. Las variables x1, x2, ..., xn para P(x1, x2, ..., xn) son todasvariables libres para el predicado y cada xj vara en su correspondiente dominio de individuos Uj. Eltrmino libre es la abreviacin de libre para sustitucin, queriendo decir que la variable xj estdisponible en caso de que queramos sustituir un valor particular deUjcada vez que aparezcaxj.Si sustituimosxjpor un valor, digamos que por ejemplo sustituimosx1 pora, enP(x1, x2, ..., xn)obtenemos el predicadoP(a, x2, ..., xn) que es libre en las restantesn 1 variablesx2, ...,xn peroya no lo es en x1. Al aplicar un cuanticador xj o xj a un predicado P(x1, x2, ..., xn) obtenemosun predicado xjP(x1, x2, ..., xn) o xjP(x1, x2, ..., xn) cuyos valores dependen nicamente de lasrestantes n1 variables. Decimos que el cuanticador liga la variable xj, haciendo que xjsea unavariable acotada para el predicado. Al aplicar n cuanticadores, uno para cada variable, obtenemosque todas las variables estn acotadas y obtenemos una proposicin cuyo valor de verdad puededeterminarse aplicando las reglas para x y x, para los dominios de individuosU1,U2 , ...,Un.Ejemplo 1.51 Anteriormente notamos que un predicado den argumentos se transforma enun predicado de(n 1) argumentos cuando se liga una de las variables con un cuanticador. Suvalordeverdaddependedelosvaloresdeverdaddelasrestantes (n 1)variableslibresyenparticular no depende de qu nombre elijamos para llamar la variable acotada. De esta manera siP(x)espredicadodeunargumentocondominiodeindividuosU,entonces xP(x), yP(y)yzP(z) tienen todas el mismo valor de verdad, es decirP(n), es verdadero para todan enUyfalso en cualquier otro caso. De manera semejante, siQ(x, y) es un predicado de dos argumentoscon dominio de individuosUyV , entonces yQ(x, y), tQ(x, t) y sQ(x, s) describen todas elmismo predicado de un argumento, a saber, el predicado que es verdadero para unax dada enUsi y slo si Q(x, V ) es verdadero para alguna Ven Vque es el dominio de la segunda variable. Porotro lado, el predicado xQ(x, x), no es el mismo que los tres ltimos. La diferencia consiste enwww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 42que el cuanticador en este caso liga las dos variables libres.Otra prctica comn es dar una descripcin del dominio de individuos justo despus de la variablecuanticada. Porejemplo, enlugardeseaRel dominiodeindividuos... xP(x)podramosescribi x R P(x). De manera similar, x R n P(xn> x) se lee como hay un nmero realx tal que para todan en P,xn> x o como hay un nmero realx tal quexn> x para todan enP.1.4.1. Leyes de la lgica de predicadosLas ideas de demostracin y de teorema que se discuti para el clculo proposicional, puedenextenderse al mbito del clculo de predicados. No es sorprendente que con ms expresiones posi-blestengamostambinmayorescomplicaciones. Unarelacinmoderadamentecompletadeestetema puede formar una parte sustancial de otro libro. En esta seccin nos limitaremos a discutiralgunasdelasms bsicas ytilesconexionesentreloscuanticadoresylosoperadores lgicos.Enel captuloanteriorutilizamoslaexpresinproposicincompuestademanerainformal paradescribir proposiciones construidas a partir de proposiciones ms simples.Las leyes de la lgica de predicados que no se pueden obtener por medio de la sustitucin delas leyes de la lgica proposicional, son por ejemplo:1. x P(x) P(a)xP(x) P(a) pruebaque, si cadaindividuodeunconjuntoposeeunadeterminadapropiedad P, entonces existe tambin un individuo determinado a que posee esta propiedad.2. P(a) x P(x)P(a) xP(x)pruebaque, si unindividuodeterminadodeunconjuntodeindividuosposee una determinada propiedadP, existe entonces, por lo menos un individuo a con estapropiedad.Toda expresin de la lgica proposicional con validez general puede convertirse en una expresinde la lgica de predicados con validez general, pero el recproco es falso.Podramos intentar obtener, por medio de la ssustitucin de una expresin de la lgica proposi-cional satisfactible sin validez general, una expresin de la lgica de predicados igualmente satis-factible, pero sin validez general. Pongamos por ejemplo en la neutralidad de la lgica proposicionalP Q para la variable proposicionalP = x[P(x) P(x)]y paraQ= x[P(x) P(x)]de esta forma obtenemos la expresinx[P(x) P(x)] Q= x[P(x) P(x)].Esta expresin es una contradiccin.Porelcontrarioresultaque:Todaexpresindelalgicaproposicional,noejecutable,satis-factible, es tambin una expresin de la lgica de predicados, no ejecutable, satisfactible.Algunas equivalencias de la lgica de predicados, que expresan la relacin que se establece entrelos cuanticadores y reciben especial atencin. Una equivalencia de la lgica de predicados tienewww.Matematica1.com CAPTULO 1. LGICA MATEMTICA 43tanta validez general como una equivalencia de la lgica proposicional, si coinciden en cada casolos valores de verdad de ambos trminos en iguales sustituciones de sus variables.Se obtiene una proposicin verdadera en cada sustitucin de las variables del dominio, a partirde un conjunto no vaco dado, y en cada sustitucin de las variables del predicado P. Esta expre-sin es una forma, en la lgica de predicados del conocido teorema del tercer excluido de la lgicaproposicional.Las identidades de la lgica de predicados (leyes) se pueden obtener de las identidades lgicasproposicionales si las variables son sustituidas por formas proposicionales de la lgica de predicadosen las expresiones de la lgica proposicional correspondiente.Enmuchoscasosnosencontramosqueestasexpresionestienenqueverconformasproposi-cionales, que se han obtenido mediante la combinacin de dos o ms proposiciones como dos formasproposicionales. La traduccin de expresiones de la lgica de predicados en el lenguaje comn esgeneralmentemsfcil quelatraduccinendireccincontraria. Sobretodoexistendicultadescuando se presentan, por ejemplo, dos o ms operadores.Teorema 1.15 Las siguientes equivalencias son vlidas:x yP(x, y)= y x P(x, y) y x yP(x, y)= y x P(x, y)DemostracinParademostrarque x yP(x, y) = y xP(x, y)esunatautologa,debemosrevisarqueestaproposicinesverdaderaparatodoslosdominiosdel discursoposibles. Porladenicinde ,necesitamos revisar solamente que y xP(x, y) es verdadera para un dominio dado si y slo six yP(x, y) es verdadera para ese dominio.Supongamosque x y P(x, y)tienevalorverdadero. Entonces y P(x0, y)esverdaderaparaalgunax0 en el universo, por lo tantoP(x0, y0) es verdadera para algunay0 en el dominio. De ahque x P(x, y0) es verdadera y por lo tanto y x P(x, y) es verdadera. La implicacin en la otradireccin es similar.Msan,lasdosproposiciones x yP(x, y)y y xP(x, y)sonlgicamenteequivalentesalaproposicin (x, y) P(x, y) donde (x, y) vara sobre D1 x D2, con D1 y D2 los dominios del discursode las variablesx ey respectivamente.Teorema 1.16 Es vlida la siguiente identidad:x yP(x, y)= y x P(x, y)DemostracinParapoderdemostraresteteorema, asumimosquesi laparteizquierdadeestaproposicinesverdaderoentoncesexistex0enel dominiodediscursotal que y P(x0, y)esverdaderoyasP(x0, y)esverdaderoparatoday.Porlotanto,paracaday, xP(x, y)esverdadero;dehechola mismax0sirve para cada y. Como xP(x, y) es verdadero para toda y, el lado derecho de laproposicin tiene valor de verdad verdadero. De esta manera la proposicin es una tautologa.Por otra parte el recproco de esta proposicin, es decir y xP(x, y) = x yP(x, y) no es engeneral verdadero. Para enfatizar la diferencia, supongamos quex ey varan sobre un dominioDde tres elementos, digamos D = a, b, c. El predicado de 2 argumentos P(x, y) tiene nueve posiblesvalores;P(a, a); P(a, b); P(a, c); P(b, a); P(b, b); P(b, c); P(c, a); P(c, b); P(c, c).www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 44Entonces x yP(x, y) es verdadero si yP(x0, y) es verdadero para algunax0. Comox0tieneque ser igual a a, b o c vemos que x yP(x, y) es verdadero si y slo si todas las proposiciones deuna de las las dadas arriba son verdaderas. En contraste, y x P(x, y) sera verdadera siempreque al menos una proposicin de cada columna sea verdadera.Por ejemplo si consideramos un predicadoP(x, y) con valores de verdadP(a, a) P(a, b) P(a, c) P(b, a) P(b, b) P(b, c) P(c, a) P(c, b) P(c, c)V F F F F V F V Ventonces y xP(x, y)serverdaderaentantoque x yP(x, y)serfalsa.ParaestaeleccindepredicadoP(x, y), xP(x, y)esverdaderaparatodayperolaxadecuadadependedelay,ningunax nica sirve para today.Teorema 1.17 Las identidades siguientes son vlidas:x P(x)= x [P(x)]; x P(x)= x [P(x)];x P(x)= x [P(x)]; x P(x)= x [P(x)].Ejemplo 1.52 Las leyes de DeMorgan pueden utilizarse repetidamente para negar cualquierproposicin cuanticadaw x y zP(w, x, y, z)es sucesivamente lgica equivalente aw[x y zP(w, x, y, z)]; w x[y zP(w, x, y, z)];w x y[zP(w, x, y, z)]; w x y z[P(w, x, y, z)];Esto ilustra la regla general: La negacin de un predicado cuanticado es lgicamente equiva-lente a la proposicin que se obtiene al sustituir cada por y cada por y reemplazando elmismo predicado por su negacin.Ejemplo 1.53 La negacin dex y z(x < z< y) es x y z[(x < z< y)].Aplicando las leyes de DeMorgan vemos que la negacin es lgicamente equivalente ax y z[(z x) (z y)]Ejemplo 1.54 La negacin dex y(x < y x2< y2) es x y[(x < z x2< y2)].Aplicando las leyes de DeMorgan vemos que la negacin es lgicamente equivalente ax y[(x < y) (x2 y2)]www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 451.4.2. Interpretacin de frmulas en la lgica de predicadosEn la lgica proposicional una interpretacin es una asignacin de valores de verdad a tomos.En la lgica de predicados, puesto que hay variables involucradas, hay que hacer ms que eso. Paradenir una interpretacin para una frmula en la lgica de predicados, tenemos que especicar doscosas, el dominio y una asignacin a constantes, smbolos de funcin y smbolos de predicado queocurren en la frmula. A continuacin se da la denicin formal de interpretacin de una frmulaen la lgica de predicados.Denicin 1.24 Interpretacin de una frmulaUnainterpretacindeunafrmulaGenlalgicadepredicados, consictedeundominioDnovaco, y una asignacin de valores a cada constante, smbolos de funcin, y smbolos de predicadoque ocurre en G de la siguiente manera:1. A cada constante asignamos un elemento en D;2. A cada smbolo de funcin asignamos una aplicacin de Dna D, Dn= x1, x2, ..., xn D3. A cada smbolo de predicado asignamos una aplicacin deDna V, F.Algunas veces para enfatizar el dominio D, hablaremos de una interpretacin de la frmula sobreD. Cuando evaluamos el valor de verdad de una frmula en una interpretacin sobre el dominioD, x ser interpretada como para todos los elementosx en D, y x como hay un elemento enD. Para cada interpretacin de una frmula sobre un dominio de individuos D, la frmula puedeser evaluada a V o F de acuerdo a las siguientes reglas:1. Si los valores de verdad de las frmulas H y G son evaluadas, entonces los valores de verdadde las frmulas H, H G, H G, H G, H G son evaluadas de la siguiente manera:H GH H G H G H G H GV V F V V V VV F F V F F FF V V V F V FF F V F F V V2. x H es evaluada a V si el valor verdadero de H es valuado a V para cadad D, de otramanera es evaluado a F.3. x H es evaluado a V si el valor de verdad de H es V para por lo menos und D, de otramanera es evaluada a F.Sepuedenotar fcilmentequecualquier frmulaconteniendovariables libres nopuedeserevaluada. En adelante asumiremos, ya sea que las frmulas no contienen variables libres o que lasvariables son tratadas como constantes.Ejemplo 1.55 Considere la frmula x yP(x, y), D = 1, 2P(1, 1)= V ; P(1, 2)= F; P(2, 1)= F; P(2, 2)= V.Si x=1, podemosverquehayunytal queP(1, y)esverdadero. Si x=2haytambinunydenominado 2 tal que P(2, y) es verdadero, por consiguiente en las interpretaciones de arriba, paracadaxenDhayunytal queP(x, y)esverdadero, estoes x yP(x, y)esverdaderoenestainterpretacin.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 46Ejemplo 1.56 Considere la frmula x [P(x) Q(f(x), k)]. Hay una constante k, un smbolode funcinfde un lugar, un smbolo de predicado P de un lugar, y un smbolo de predicado Q dedos lugares. La siguiente es una interpretacin I. Dominio D = 1, 2.Asignacin parak:a = 1.Asignacin paraf:f(1) = 2;f(2) = 1.Asignaciones para P y Q:P(1) = F; P(2) = V ; Q(1, 1) = V ; Q(1, 2) = V ; Q(2, 1) = F; Q(2, 2) = V.Six = 1, entoncesP(x) Q(f(x), k) = P(1) Q(f(1), k) = P(1) Q(2, 1) = F F= V.Six = 2, entoncesP(x) Q(f(x), k) = P(2) Q(f(2), k) = P(2) Q(1, 1) = V V= V.Puesto queP(x) Q(f(x), k) es verdadero para todos los valores dex en D, la frmulax [P(x) Q(f(x), k)]es verdadera bajo las interpretaciones I.Ejemplo 1.57 Evaluarlosvaloresdeverdaddelassiguientesfrmulasbajolasinterpreta-ciones dadas en el ejemplo anterior.1. x [P(f(x)) Q(x, f(k))];2. x [P(x) Q(x, k)];3. x y[P(x) Q(x, y)].Para 1): Six = 1, entoncesP(f(x)) Q(x, f(k)) = P(f(1)) Q(1, f(1)) = P(2) Q(1, f(1)) = P(2) Q(1, 2) = V V= V.Six = 2, entoncesP(f(x)) Q(x, f(k)) = P(f(2)) Q(2, f(1)) = P(1) Q(2, 1) = F F= F.Puesto que hay un elemento en el dominio D, esto es x = 1 tal que P(f(x))Q(x, f(k)) es verdadero,el valor de verdad de la frmula x [P(f(x)) Q(x, f(k))] es verdadera bajo la interpretacin I.Para b): Six = 1, entoncesP(x) Q(x, k) = P(1) Q(1, 1) = F V= F.Six = 2, entoncesP(x) Q(x, k) = P(2) Q(2, 1) = V F= F.Puesto que no hay elemento en el dominio D tal queP(x) Q(x, k) sea verdadero, la frmulax [P(x) Q(x, k)]es evaluada a falsa bajo la interpretacin I.Para c): Six = 1, entoncesP(x) = P(1) = F.Por consiguienteP(x) Q(x, y) = Fparay= 1 ey= 2. Puesto que existe unx, que esx = 1, lafrmula y[P(x)Q(x, y)] es falsa, la frmula x y[P(x)Q(x, y)] es falsa bajo la interpretacinI, esto es, la frmula es falsicada por I.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 47Denicin 1.25 Frmula consistenteUnafrmulaGesconsistente(satisfactible)siyslosiexisteunainterpretacinItal queGesevaluada verdadero en I. Si una frmula G es verdadera en una interpretacin I, decimos que I esun modelo de G e I satisface a G.Denicin 1.26 Frmula vlidaUna frmula G es vlida si, y slo si cada interpretacin de G satisface a G.Denicin 1.27 Frmula inconsistenteUnafrmulaGes inconsistente(insatisfactible) si yslosi, noexisteunainterpretacinquesatisface a G.Las relaciones entre validez (inconsistencia) y consecuencias lgicas, como se indica en la lgicaproposicional, son tambin verdaderas para la lgica de predicados. En efecto, la lgica de predica-dos puede ser considerada como una extensin de la lgica proposicional. Cuando una frmula enla lgica de predicados no contiene variables y cuanticadores, puede ser tratada justo como unafrmula en la lgica proposicional.Ejemplo 1.581. x P(x) y P(y) es inconsistente;2. x P(x) yP(y) es vlido;3. P(k) x P(x) es consistente;4. x P(x) y P(y) es vlido.En la lgica de predicados, puesto que hay un nmero innito de elementos en el dominio D, engeneral, hay un nmero innito de interpretaciones de una frmula. Por consiguiente al contrario dela lgica proposicional, no es posible vericar la validez e inconsistencia de una frmula, evaluandola frmula bajo todas las posibles interpretaciones.1.4.3. Forma normal prenexaEn la lgica proposicional hemos introducido dos formas normales, la forma normal conjuntivaylaformanormal disjuntiva. Enlalgicadepredicadoshayunaformanormal llamadaformanormal Prenexa. La razn para considerar una forma normal Prenexa de una frmula es simplicarprocedimientos de prueba.Denicin 1.28 Forma normal prenexaUna frmula G en la lgica de predicados se dice que es una forma normal Prenexa si y slo si, lafrmula G est en la forma(Q1x1)(Q2x2)...(Qnxn)(M)dondecada(Qixi), i =1, 2, ..., nyasea xio xi, yMesunafrmulaquenocontienecuan-ticadores, (Q1x1)(Q2x2)...(Qnxn)esllamadael prejoyMesllamadalamatrizdelafrmulaG.Dada una frmula G, consideraremos un mtodo de transformarla en una forma normal Prenexa.Esto se logra primero considerando algunos pasos bsicos de frmulas equivalentes en la lgica depredicados. Recordemos que dos frmulas G y H son equivalentes si, y slo si los valores de verdadde G y H son los mismos bajo cada interpretacin.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 48Los pares bsicos de frmulas equivalentes dadas en la lgica proposicional son todava verdadpara la lgica de predicados, adicionalmente hay otros pares de frmulas equivalentes conteniendocuanticadores, y que se estudiaron en secciones anteriores. Consideraremos estos pares adicionalesde frmulas equivalentes.Sea G una frmula que contiene una variable libre x, para enfatizar que la variable libre est enG, representamos G por G[x]. Sea H una frmula que no contiene variable x, tenemos los siguientespares de frmulas equivalentes, donde Q es ya sea o :1. (Qx)G[x] H = (Qx)(G[x] H);2. (Qx)G[x] H = (Qx)(G[x] H);3. (xG[x])= x(G[x]);4. (xG[x])= x(G[x]).Lasleyes1y2sonobviamenteverdaderaspuestoqueHnocontienex, porconsiguientepuede ser introducida enel alcance del cuanticador Q. Lasleyes 3 y 4 no son difciles deprobar. Sea I cualquier interpretacin arbitraria sobre el dominio D.Si (xG[x])esverdaderaenI,entonces xG[x]esfalsaenI.EstosignicaquehayunelementodenDtal queG[d] esfalso. Estoes G[d] esverdaderoenI. Porconsiguiente,x (G[x]) es verdadera en I. Por otra parte si (x G[x]) es falsa en I, entonces x G[x] esverdadera en I. Esto signica que G[x] es verdadera para cada elemento x en D, esto es G[x]es falso para cada elementox en D, por consiguiente, x(G[x]) es falsa en I. Puesto que(xG[x]) y x(G[x]) siempre asume el mismo valor de verdad para cada interpretacinarbitraria, pordenicin, (xG[x]) = x(G[x]). As laley3esprobadaeigualmentepodemos probar la ley 4.Supongamos queF[x] yG[x] son dos frmulas que contienenx,5. x F[x] x G[x]= x (F[x] G[x])6. x F[x] x G[x]= x (F[x] G[x])Estoes, el cuanticador universal yel existencial , puedendistribuirsesobre y ,respectivamente. Sin embargo el cuanticador universal y existencial no pueden distribuirsesobre y respectivamente. Esto esx F[x] x G[x] ,= x (F[x] G[x])x F[x] x G[x] ,= x (F[x] G[x])Para casos como estos tenemos que hacer algo especial. Puesto que cada variable ligada enunafrmulapuedeserconsideradacomounavariablerenombrable,cadavariablexpuedeser renombradaz, y la frmula x G[x] se transforma en zG[z].Supongamos que escogemos la variablez que no aparece enF[x]. Entoncesx F[x] x G[x]= x F[x] zG[z]= xz(F[x] G[z])Similarmente, renombrando todas lasx que ocurren en x G[x] comoz, podemos tenerx F[x] x G[x]= x F[x] zG[z]= xz(F[x] G[z])www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 49Por consiguiente, para estos dos casos podemos todava pasar todos los cuanticadores a laizquierda de la frmula. En general, tenemos7. (Q1x)F[x] (Q2x)G[x]= (Q1x)(Q2x)(F[x] G[z])8. (Q3x)F[x] (Q4x)G[x]= (Q3x)(Q4x)(F[x] G[z])dondeQ1,Q2,Q3 yQ4 son ya sea o , yz no aparece enF[x].Naturalmente si Q1=Q2= yQ3=Q4= , entonces no tenemos que renombrar lasx en(Q2x)G[x] o(Q4x)G[x]. Podemos usar las leyes 5 y 6 directamente. Usando las leyes de la lgicaproposicional y las leyes 1 - 8, podemos siempre transformar una frmula dada en forma normalPrenexa.La siguiente es una gua del procedimiento de transformacin:PASO 1: Use las leyes1. F G= (F G) (G F);2. F G= F G;Para eliminar las conectividades lgicas y .PASO 2: Repetidamente use las leyes3. (F)= F;4. (F G)= F G;5. (G G)= F G;6. (x F[x])= x (F[x]);7. (x F[x])= x (F[x]);para traer los signos de negacin inmediatamente antes de los tomos.PASO 3: Renombrar las variables ligadas si es necesario.PASO 4: Use las leyes8. (Qx)F[x] G= (Qx)(F[x] G);9. (Qx)F[x] G= (Qx)(F[x] G);10. x F[x] x G[x]= x (F[x] G[x]);11. x F[x] x G[x]= x (F[x] G[x]);12. (Q1x)F[x] (Q2x)G[x]= (Q1x)(Q2x)(F[x] G[z]);13. (Q3x)F[x] (Q4x)G[x]= (Q3x)(Q4x)(F[x] G[z]).paramoverloscuanticadoresalaizquierdadelafrmulayobtenerunaformanormalPrenexa.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 50Ejemplo 1.59 Transformar la frmula x P(x) x Q(x) en forma normal prenexa.Solucinx P(x) x Q(x)= x P(x) x Q(x)= xP(x) x Q(x)= x [P(x) Q(x)].Ejemplo 1.60 Transformarlafrmula x y z [P(x, z) P(y, z)] uQ(x, y, u)enforma normal Prenexa.Solucinx yz[P(x, z) P(y, z)] u Q(x, y, u)= x yz[P(x, z) P(y, z)] u Q(x, y, u)= x yz [P(x, z) P(y, z)] u Q(x, y, u)= x y z u P(x, z) P(y, z) u Q(x, y, u).1.4.4. Tarea1. Sea A = 1, 2, 3, 4 el conjunto universal. Determine el valor de verdad de cada enunciado:a) x : x + 3 < 6; b) x : x210 8; c) x : x2> 1 x + 2 = 0;d) x : 2x2+x = 15.Resp: a) Falso; b) Verdadero; c) Verdadero; d) Falso.2. Determine el valor de verdad de las siguientes proposiciones, siendo N el universo:a) x y(2y= x); b) y x (2x = y); c) x y(2x = y);d) y x (2y= x); e) x y[(2y= x)].Resp: a) ; b) ; c) ; d) ; e) .3. Determine el valor de verdad de las siguientes proposiciones, siendo R el universo:a) x y(xy= 1); b) x y[(x + y)2= x2+ y2]; c) x y(x2+ y2+ 1 = 2xy);d) x y[(x + 2y= 4) (2x y= 2)].Resp: a) ; b) ; c) ; d) .4. Determine el valor de verdad de las siguientes proposiciones, siendo R el universo:a) x R x2 x; b) x R 2x = x; c) x R2x14x2=12;d) x R x2+ 2x + 1 0.Resp: a) ; b) ; c) ; d) .5. Negar los siguientes enunciados:a) yp(y)x(q(x)); b) x(p(x)) x q(x); c) x y(p(x, y) q(x, y)).Resp: a) yp(y) x q(x); b) x p(x) x(q(x)); c) y(p(x, y) q(x, y)).6. Negar las siguientes armaciones:a) x y[(x +y es impar) (x es impar y es impar)];b) x y(x +y= 5 y= x); c) x y(x < y x2 y);d) x y z(x < y x +z= y).Resp: a) ; b) ; c) ; d) .7. Averiguar el valor de verdad siendo U= R:a) x R (x < 0 x < 3); b) x R (x2 0 x4= x3);c) x R, y R (x2+y2= 1); d) x R, y R (y< x 2y< 10).Resp: a) Verdadero; b) Verdadero; c) Falso; d) Falso.www.Matematica1.com CAPTULO 1. LGICA MATEMTICA 518. Considere el universo U de todos los profesores de ciencias bsicas. Sea P(x) el predicadoax le gusta la lgica matemtica:a) Exprese la proposicin no a todos los profesores de ciencias bsicas les gusta la lgicamatemtica, utilizando smbolos de la lgica de predicados;b) Hagalomismoparaatodoslosprofesoresdecienciasbsicasnolesgustalalgicamatemtica;c) Escriba el signcado de x P(x)= x [P(x)] para U y P(x);d) Haga lo mismo con x P(x)= x [P(x)].Resp: a) ; b) ; c) ; d) .9. Escriba la negacin de las siguientes frmulas:a) x P(x, x) [y z P(y, z) x P(x, x)];b) x y x P(f(x, y), y) [x P(f(x, y), y) z[f(z, x) = y];c) x [P(x) Q(x)] [x P(x) x Q(x)];d) x yP(x, y) yP(f(x, y), y);e) x yP(x, y) yP(y, y);f ) x [y x P(x, y) Q(x)] [y x P(x, y) Q(f(y, y))].Resp: a) ; b) ; c) ; d) ; e) ; f ) .10. Considere la siguiente interpretacin:D = 1, 2.Asignaciones a las constantesk yt:k = 1 yt = 2.Asignaciones para la funcinf:f(1) = 2 yf(2) = 1.Asignaciones para el predicadoP:P(1, 1) = V ;P(1, 2) = V ;P(2, 1) = F;P(2, 2) = F.Evale el valor de verdad de las siguientes frmulas en cada interpretacin:a) P(k, f(k)) P(t, f(t)); b) x yP(y, x); c) x y[P(x, y) P(f(x), f(y))].Resp: a) ; b) ; c) .11. Dadas las siguientes frmulas, hallar la correspondiente forma normal prenexa:a) x y[P(x, y) P(y, x)]; b) x y [P(x) P(y)] x = y;c) x y(x = y) [x P(x) x P(x)].Resp: a) ; b) ; c) .12. Escriba la negacin de las siguientes frmulas:a) x [P(x) Q(x)] [x P(x) x Q(x)];b) x yP(x, y) yP(f(x, y), y);c) x yP(x, y) yP(y, y);d) x [y x P(x, y) Q(x)] [y x P(x, y) Q(f(y, y))];e) x [P(x) Q(x)] [P(x) Q(x)];f ) x yP(f(y, x), x) yP(f(y, f(z, x)), f(z, x));g) x P(x, x) [y z P(y, z) x P(x, x)];h) x y x P(f(x, y), y) [x P(f(x, y), y) z[f(z, x) = y].Resp: a) ; b) ; c) ; d) ; e) ; f ) ; g) ; h) .www.Matematica1.com Captulo 2Teora de conjuntos2.1. ConjuntosCasi todos los objetos matemticos sonante todoconjuntos, independientemente de otrapropiedad adicional que posean. Por consiguiente, la teora de los conjuntos es, en cierto sentido,la base sobre la cual se construye toda la matemtica. A pesar de esto, la teora de los conjuntos,se aprende, y se usa fcilmente.Denicin 2.1 ConjuntoUnconjuntoescualquiercoleccinbiendenidadeobjetosllamadoselementosomiembrosdelconjunto.Se usan letras maysculas comoA,B,C, ..., para indicar conjuntos y letras minsculas comoa,b,c, ..., para indicar miembros o elementos de los conjuntos.Ejemplo 2.1 Son ejemplos de conjuntos, los siguientes:a. Las letras de alfabeto.b. Los nmeros pares.c. Los miembros de un equipo de ftbol.A continuacin se enuncian las siguientes condiciones para denir un conjunto:1. Los elementos que forman el conjunto han de ser entes bien denidos.2. Para cada uno de estos elementos no hay otra alternativa que la de pertenecer o no al conjunto.3. Para cada par de elementos a considerar no hay otra alternativa que la de estar formado o nopor elementos distintos.2.1.1. Formas de expresar un conjuntoHay dos caminos para denir o determinar un conjunto, mtodos que los lgicos designan porextensin y por comprensin.Por extensinPara expresar que el conjuntoS consta de los elementosa,b,c, escribiremosS= a, b, c, conello damos la extensin del conjunto S al enunciar cada uno de los elementos que lo componen. Esdecir, se declara individualmente todos los elementos del conjunto.52www.Matematica1.com CAPTULO 2. TEORA DE CONJUNTOS 53Por comprensinPor otra parte, los conjuntos innitos slo pueden denirse por comprensin, es decir, dandoun criterio que permita reconocer para cada ente arbitrario, si pertenece o no al conjunto. Es decir,se declara una propiedad que caracteriza a todos los elementos del conjunto.2.2. Conjuntos nitos e innitos2.2.1. Conjunto nitoDenicin 2.2 Conjunto nitoAquel conjuntoqueconstadeciertonmerodeelementosdistintoscuyoprocesodeconteotienelmite, se denomina conjunto nito.Ejemplo 2.2 SeaA = x/x = provincias de EcuadorQue se lee A es el conjunto de las x, tales que x son las provincias de Ecuador. A es un conjuntonito porque si es posible contar todas las provincias de Ecuador.2.2.2. Conjunto innitoDenicin 2.3 Conjunto innitoAquel conjunto que consta de un nmero indeterminado de elementos distintos, se denomina con-junto innito.Ejemplo 2.3 SeaA = z/z= arena en el marQueseleeAesel conjuntodelasz,talesquezsonlosgranosdearenaenel mar.Aesunconjunto innito porque no se puede contar el nmero de granos de arena, es innito.2.2.3. Nocin de pertenenciaSeindicaelhechodequexesunelementodelconjuntoAescribiendox Ayseindicaelhecho de quex no es un elemento del conjuntoA escribiendox/ A.Ejemplo 2.4 SeaA = 1, 3, 5, 7. Entonces1 A,3 A pero2/ A.Ejemplo 2.5 Si S= x/xes un nmero natural menor que4, esel conjunto 1, 2, 3de-scrito anteriormente, enlistando sus elementos.Ejemplo 2.6 SeaS = x/xes un nmero real y x2= 1, dadoqueel cuadradodeunnmero real x es siempre positivo.2.2.4. Igualdad de conjuntosDenicin 2.4 Igualdad de conjuntosLosconjuntossontotalmentedeterminadoscuandoseconocentodossusmiembros.Aspues,sedice que dos conjuntosA yBson iguales si tienen los mismos elementos y se escribeA = B.Ejemplo 2.7 SiA = 1, 2, 3 yB= x/x es un nmero natural y x2< 16, entoncesA = B.www.Matematica1.com CAPTULO 2. TEORA DE CONJUNTOS 542.2.5. Conjuntos vacoDenicin 2.5 Conjunto vacoCuando la condicin impuesta es contradictoria, no existe ningn elemento que la cumpla, se diceque dene un conjunto vaco, que suele simbolizarse por .Ejemplo 2.8 Son vacos los conjuntos siguientes: tringulos equilteros rectngulos; nmerosprimos pares mayores que 2.2.2.6. Conjunto unitarioDenicin 2.6 Conjunto unitarioUn conjunto que tiene un nico elemento, se denomina conjunto unitario.Ejemplo 2.9 SeaA = Los meses del ao, cuyo nombre empieza con F2.2.7. Conjunto universalDenicin 2.7 Conjunto universalEl conjunto que contiene a todos los elementos de otros conjuntos, se denomina conjunto universalo referencial. Se denota con la letra U.Ejemplo 2.10 SeaA = Todos los nmerosEste es un conjunto universal, porque contiene todos los nmeros de los conjuntos R, N, Z, C, ....2.2.8. SubconjuntoDenicin 2.8 SubconjuntoSi todos los elementos de A son tambin elementos de B, esto es si cuando x A, entonces x B,decimos queA es un subconjunto deBo queA est contenido enBy se escribeA B. SiA noes un subconjunto deB, se escribeAB.Los conjuntos A y B son iguales si y solamente si B est incluido en A y A est incluido en B.El conjunto vaco se considera subconjunto de todo conjunto.Si A no es subconjunto de B, entonces hay por lo menos un elemento de A que no pertenece aB.www.Matematica1.com CAPTULO 2. TEORA DE CONJUNTOS 55Subconjunto propio e impropioDenicin 2.9 Subconjunto propio e impropioSi A UyA ,= , A ,=U,el conjuntoAsedenominasubconjuntopropiodel conjuntoU.Lossubconjuntos yUdel conjuntoUreciben el nombre de impropios.Es decir, dado A B, entonces el subconjunto A es subconjunto propio del conjunto B, si porlo menos un elemento del conjunto B no es elemento del conjunto A. Pero si todos los elementosdeAsonigualesaloselementosdeB,yanoesunsubconjunto,enestecasolosconjuntossoniguales.Ejemplo 2.11 SetienequeZ+Z.Adems,si Qindicaelconjuntodetodoslosnmerosracionales, entoncesZ Q.Ejemplo 2.12 Determine si la proposicin2 A = 2, 2, 5 es verdadera o falsa.SolucinEs falsa pues2 A como elemento, pero no como subconjunto.Ejemplo 2.13 SeaA= 1, 2, 3, 4, 5, 6, B= 2, 4, 5, C= 1, 2, 3, 4, 5. EntoncesB A,B C,C A. Sin embargoAB,AB,CB.Denicin 2.10 Subconjunto de s mismoSi Aescualquierconjunto, entonces A A. Estoes, cualquierconjuntoessubconjuntodesmismo.SeaA un conjunto y seaS= A, A, por tanto, puesto queA y A son elementos deS,tenemos queA Sy A S. De esto se sigue que A Sy A S. Sin embargo, no esverdad queA S.Dado que una implicacin es verdadera si la hiptesis es falsa, se sigue que A.Ejemplo 2.14 Dados los conjuntosA,B,C, demuestre las siguientes expresiones:1. SiA B,B C, entoncesA C;2. SiA B,B C, entoncesA C;3. SiA B,B C, entoncesA C;4. SiA B,B C, entoncesA C.SolucinProcederemos a demostrar cada uno de los literales de forma minuciosa:1. Seax A. ComoA B, x B. Entonces conB C, x C. De ah quex A entoncesx CyA C.2. Seax A.A B entoncesx B.B Centoncesx C. De ah queA C. ComoA B,existey B, dondey/ A. ConB C, y C. En consecuencia, A Cey C, cony/ A, demodo queA C.3. Six A, entoncesA B entoncesx B yB C entoncesx C. De ah queA C. ComoB C, existey C cony/ B. Adems,A B ey/ B entoncesy/ A. En consecuencia,A Cey Ccony/ A entoncesA C.4. ComoA B, resulta queA B. Entonces, el resultado se obtiene de 3).Ejemplo 2.15 Para cualquier conjuntoA, A; A siA ,= .SolucinSi el primerresultadonoesverdadero, entonces A, demodoquehayunelementoxdeluniverso conx , perox/ A. Perox es imposible. Adems, si A ,= , entonces hay unelementoa A ya/ , de modo que A.www.Matematica1.com CAPTULO 2. TEORA DE CONJUNTOS 562.2.9. Conjunto de partesDenicin 2.11 Conjunto de partesTodo conjunto integrado por la totalidad de subconjuntos que se puede formar a partir de un con-junto dado, se denomina conjunto de partes y se denota P(A).Ejemplo 2.16 Indique todos los subconjuntos del conjunto de tres elementos a, b, c.SolucinEl conjuntodetreselementostienelossubconjuntosimpropios y a, b, cylossubconjuntospropios: a, b, c, a, b, a, c, b, c.2.2.10. Conjunto potenciaDenicin 2.12 Conjunto potenciaSi Aesunconjunto, entoncesal conjuntodetodoslossubconjuntosdeAselellamaconjuntopotencia deA. Tienen la misma connotacin del connunto de conjuntos.Es decir, el conjunto potencia es el nmero de subconjuntos que se puede formar con elementosdel conjunto, incluyendo el vaco. Se calcula conPA= 2n, donden es el nmero de elementos delconjunto A o cardinalidad del conjunto A.Ejemplo 2.17 Indique el nmero de subconjuntos o conjunto potencia del conjunto a, b, c, d.SolucinAqun = 4, por consiguientePA= 24= 16.2.3. Operaciones con conjuntos2.3.1. Unin de conjuntosMientrasqueenaritmticaserealizaoperacionesdesuma, restaymultiplicacin, enel ca-sodeconjuntosserealizaoperacionesdeunin, interseccinydiferenciadeconjuntos, conuncomportamiento similar al de la aritmtica.Denicin 2.13 Unin de conjuntosSi AyBsonconjuntos,sedenesuunincomoel conjuntoquetienetodosloselementosquepertenecen aA o aBy se indica comoA B= x/x A x B.Es decir, la unin de dos conjuntosA yB es el conjunto formado por todos los elementos quepertenecenal conjuntoA, al conjuntoBoaambosconjuntos. Enlaunindeconjuntosnoserepiten los elementos que pertenecen a ambos conjuntos.Obsrvese quex A B six A ox B ox pertenece a ambos conjuntos.Ejemplo 2.18 SeanA = a, b, c, e, f yB= b, d, r, s. Puesto queABconsta de todos loselementos que pertenecen tanto aA como aB, entoncesA B= a, b, c, d, e, f, r, s.Se puede ilustrar la unin de dos conjuntos con un diagrama de Venn como sigue. Si A y B sonlos conjuntos dados en la gura, entoncesA B es el conjunto de puntos en la regin sombreada.www.Matematica1.com CAPTULO 2. TEORA DE CONJUNTOS 572.3.2. Propiedades de la unin de conjuntosLasoperacionesconconjuntosqueseacabandedenirsatisfacenmuchaspropiedadesalge-braicas; algunas de stas se parecen a las propiedades algebraicas que se satisfacen en el sistemade los nmeros reales.A continuacin, damos las propiedades ms importantes sobre las operaciones de conjuntos:1. Propiedad conmutativa: Es decir, el orden de los conjuntos no altera la unin.A B= B A.2. Propiedadasociativa:Sisonmsdedosconjuntoslosqueseunen,puedenasociarsedemanera libre.A (B C) = (A B) C.3. Propiedad de idempotencia:A A = A.4. Propiedad del conjunto universal:A U= U.5. Propiedad del conjunto vaco:A = A.2.3.3. Interseccin de conjuntosDenicin 2.14 Interseccin de conjuntosSi Ay Bsonconjuntos, suinterseccinsedenecomoel conjuntoquecontieneatodos loselementos que pertenecen tanto aA como aBy se indica comoA B= x/x A x B.Es decir, la interseccin de dos conjuntosA yB es el conjunto de elementos comunes aA yB. Esposible ilustrar la interseccin de dos conjuntos por el diagrama de Venn como sigue. Si A y B sonlos conjuntos dados en la gura, entoncesA B es el conjunto de puntos en la regin sombreada.www.Matematica1.com CAPTULO 2. TEORA DE CONJUNTOS 58Ejemplo 2.19 SeanA= a, b, c, e, f, B= b, e, f, r, syC= a, t, u, v.Loselementosb,eyf, sonlosnicosquepertenecenaAyBporlocual A B= b, e, f. Deigual manera,A C= a. No existen elementos que pertenezcan tanto aA como aB, por lo cual B C= .2.3.4. Propiedades de la interseccin conjuntosA continuacin, damos las propiedades ms importantes sobre interseccin de conjuntos:1. Propiedad conmutativa: Es decir, el orden de los conjuntos no altera la interseccin.A B= B A.2. Propiedad asociativa: Es posible cambiar el orden de asociacin y no se altera el resultado.A (B C) = (A B) C.3. Propiedad distributiva:A (B C) = (A B) (A C);A (B C) = (A B) (A C).4. Propiedad de idempotencia:A A = A.5. Propiedad del conjunto universal:A U= A.6. Propiedad del conjunto vaco:A = .Ejemplo 2.20 Pruebe o refute las siguientes relaciones para los conjuntosA,B U:a) P(A B) = P(A) P(B); b) P(A B) = P(A) P(B).SolucinSeaU= 1, 2, 3,A = 1,B= 2, entonces:a) 1, 2 P(A B), pero 1, 2/ P(A) P(B).b) C P(AB) C AB C AC B C P(A)C P(B) C P(A)P(B),de modo queP(A B) = P(A) P(B).Ejemplo 2.21 Demuestre queA (B C) = (A B) (A C).SolucinDaremosunademostracindequelosconjuntossonsubconjuntosunodel otro. Consideremosprimerox A (B C). Entoncesx est enA necesariamente.Tambinx est enB C. As que, o bienx B, en cuyo casox A B, ox C, en tal casox A C. En cualquiera de los dos casos tenemos quex (A B) (A C). Esto muestra queA(B C) (AB) (AC). Consideremos ahoray (AB) (AC). Entoncesy ABoy A Cy consideramos los dos casos por separado. Si y A B, entoncesy A yy B,luegoy B Cy por lo tantoy A (B C). Anlogamente si y A Centoncesy A yy C, por lo tantoy B Cy por esoy A (B C). As, en ambos casos,y A (B C) yhemos demostrado que(A B) (A C) A (B C). Acabamos de demostrar la contencincontraria, por lo que los dos conjuntos son iguales.www.Matematica1.com CAPTULO 2. TEORA DE CONJUNTOS 59Ejemplo 2.22 Prubense o reftense las siguientes relaciones:1. Para conjuntosA,B,C U,A C= B C A = B.2. Para conjuntosA,B,C U,A C= B C A = B.3. Para conjuntosA,B,C U,A C= B C,A C= B CA = B.Solucin1. Sea U= 1, 2, 3, A = 1, B= 2, C= 3. Entonces AC= BC= , pero A ,= B.2. ParaU= 1, 2,A = 1,B= 2,C= U,A C= B C, peroA ,= B.3. x Ax A C x B C.Si x B,entoncesA B.Si x C,entoncesx AC= BC y x B. En ambos casos, A B. As mismo, y By BC= AC,de modo que y A o y C. Si y C, entonces y BC= AC. En cualquier caso, y AyB A. De ah queA = B.Denicin 2.15 Conjuntos disjuntosA dos conjuntos que no tienen elementos comunes, se les llama conjuntos disjuntos.La siguiente gura ilustra un diagrama de Venn con dos conjuntos disjuntos.Las operaciones unin e interseccin pueden generalizarse para tres o ms conjuntos. As pues,A B C= x/x A x B x CA B C= x/x A x B x CLareginsombreadaenlasegundaguraeslaunindelosconjuntosA, ByC, lareginsombreada en la tercera gura es la interseccin de los conjuntosA,B yC.En general, si A1, A2, ..., An son subconjuntos de U, entonces A1A2... An se indica como

ni=1Ai, yA1 A2 ... An se indica ni=1Ai.SeaA = 1, 2, 3, 4, 5, 7,B= 1, 3, 8, 9,C= 1, 3, 6, 8. EntoncesAB C es el conjunto deelementos que pertenecen aA,B yC. Por tantoA B C= 1, 3.2.3.5. Diferencia de conjuntosDenicin 2.16 Diferencia de conjuntosSi A yBson conjuntos, se dene la diferencia del conjuntoA menos el conjuntoB, el conjuntoformado por elementos del conjuntoA que no son elementos del conjuntoBy se indicaAB= x/x A x/ B.www.Matematica1.com CAPTULO 2. TEORA DE CONJUNTOS 60La diferencia tambin se denotaAB.Ejemplo 2.23 SeaA = a, b, c yB= b, c, d, e. EntoncesAB= a yB A = d, e.SiA yBson los conjuntos en la gura, entoncesA ByB A son los conjuntos de puntosen las regiones sombreadas.Ejemplo 2.24 Para conjuntos cualesquieraA,ByCse cumple que(A B) C= (AC) (B C).SolucinSe tiene que demostrar la igualdad de dos conjuntosA=Bsi y slo si se cumple queA ByB A.1) Veamos que(A B) C (AC) (B C) se cumple.Seax un elemento cualquiera de(A B) C, es decirx (A B) yx/ C(x A x B) yx/ C. Deben analizarse por separados dos casos segn la inferencia a partir de una alternativa.Caso1: Tenemosquex Ayx / C. Entonces x A C, deloqueresultaasuvezquex (AC) (B C).Caso2: Tenemosquex Byx / C. Entonces x B C, deloqueresultaasuvezquex (AC) (BC). De x (AB) C x (AC) (BC), resulta, segn la inferenciade para todo, la tesis 1).2) Veamos tambin que(AC) (B C) (A B) Cse cumple.Seax un elemento cualquiera de(A C) (B C), es decir, x (A C) x (B C). Aqutambin tienen que analizarse dos casos segn la inferencia a partir de una alternativa.Caso1: Tenemosquex (A C). Entoncesx Ayx/ C, delocual resultaasuvezquex (A B) yx C, es decir,x (A B) C.Caso2: Tenemosquex (B C).Entoncesx Byx/ C,delocualresulta,delamismaforma, quex (A B) yx/ C, es decir,x (A B) C.De x (AC) (BC) x (AB) C. Resulta nalmente la tesis 2). De 1) y 2) resulta,que el la identidad es verdadera.2.3.6. Complemento de un conjuntoDenicin 2.17 ComplementoSiUes un conjunto universal y contiene aA, entonces aU A se le llama complemento deA yse indicaA = x U/x/ A.Ejemplo 2.25 Sea A = x/x es un nmero entero y x 4. Entonces A = x/x es un nmero entero y x m. El nmero mencionadop se denomina suma de los nmerosm yn; se denotaconp = m+n, mientras que los nmerosm yn se llaman sumandos.Para sumar varios nmeros naturales, es necesario adicionar al principio los dos primeros, luegoaadir a la suma obtenida el siguiente nmero natural, etc.Multiplicarunnmeronatural mporotronmeronatural nsignicaencontrarunnmeronaturalq igual an, sim = 1 y; a la suma dem nmeros, cada uno de los cuales esn, siempre quem > 1. El citado nmeroq se denomina producto de los nmerosm yn; se denota comoq= mn,y los nmerosm yn se denominan factores.Paramultiplicarvariosnmerosnaturales, sedebemultiplicaral principiolosdosprimerosnmeros, luego multiplicar el nmero natural obtenido por el siguiente nmero natural, etc.A continuacin, damos a conocer las leyes principales de adicin y multiplicacin de los nmerosnaturales:1. m+n = n +m ley conmutativa de la adicin.2. (r +m) +n = r + (m+n) ley asociativa de la adicin.3. mn = nm ley conmutativa de la multiplicacin.4. (rm)n = r(mn) ley asociativa de la multiplicacin.5. (r +m)n = rn +mn ley distributiva de la adicin respecto a la multiplicacin.76www.Matematica1.com CAPTULO 3. NMEROS REALES 77Si el nmerom gura en calidad defactorkveces,dondekes nmeronaturalsuperiora launidad, entonces el productom m ...m. .kvecesse denominak-sima potencia del nmerom y se rep-resenta por mk, es decir, por denicin mk= m m ...m. .kveces. Adems, de acuerdo con la denicin,m1= m.Las propiedades de las potencias, son las siguientes:1. mkmn= mk+n.2. (mk)r= mkr.3. mknk= (mn)k.Sustraer de un nmero natural n otro nmero natural m signica encontrar un nmero naturalp tal, que seap = n m.No siempre existe tal nmero natural p que se cumpla la igualdad anterior para cualesquieranmeros naturalesn ym. Si n>m, tal nmero existe y es nico. Este se denomina diferencia oresto entre los nmerosn ym; el nmeron se llama minuendo, ym, sustraendo.Dividir un nmero naturaln por otro nmero naturalm signica hallar un nmero naturalqtal que se verique la igualdadp =nm.No siempre existe tal nmero naturalq que se verique la igualdad para cualesquiera nmerosnaturalesn ym. Si dicho nmero existe, entoncesm yq se denominan divisores del nmeron.Apoyndose en las leyes principales de adicin y multiplicacin de los nmeros naturales y enlas deniciones de las operaciones de sustraccin y divisin, se puede armar lo siguiente:1. Si el nmerom es un divisor de los nmerosp yq, entoncesm ser el divisor de la sumap +q.2. Si m es un divisor de los nmeros p y q, siendo p > q, entonces el nmero m ser el divisorde la diferenciap q.3. Sim = n, entoncesm+k = n +k para cualquier nmero naturalk.4. Sim = n, entoncesmr = n r para cualquier nmero naturalr tal, que seam > r.5. Sim = n, entoncesmp = np para cualquier nmero naturalp.6. Sim = n, entonces para cualquier nmero naturalq que es el divisor del nmerom.Veamos un nmero nuevo, a saber, el nmero cero. Para designarlo se emplea el smbolo 0. Elcero no es un nmero natural y se considera un nmero precedente a todos los nmeros naturales.La serie de nmeros naturales junto con el nmero cero lleva el nombre de serie natural ampliada.Enlaserieampliadadenmeros naturales sepuedendenir las operaciones deadicinymultiplicacin; con este objeto es suciente aadir a las deniciones de la adicin y multiplicacindelosnmerosnaturaleslasdenicionescorrespondientesdelaadicinymultiplicacin, enlascuales interviene el nmero cero:www.Matematica1.com CAPTULO 3. NMEROS REALES 781. 0 +n = n + 0 = n.2. 0 + 0 = 0.3. 0n = n0 = 0.4. 00 = 0.Por denicin, la potencia nula de todo nmero natural m es la unidad, es decir, m0=1. Ladivisin por cero y la elevacin del cero a potencia nula son operaciones no determinadas.3.2. Nmeros primos y compuestosEl conjunto de nmeros naturales se compone de la unidad y de nmeros primos y compuestos.Unnmeronatural superioralaunidadsedenominaprimo, si esdivisiblesolamenteporsmismo y por la unidad. Un nmero natural superior a la unidad se llama compuesto, si tiene porlo menos un divisor distinto de la unidad y de s mismo.Todo nmero compuestop puede ser escrito en forma de un producto de nmeros primos.Ejemplo 3.1 El nmero 713 se descompone en 2331. En este caso suele decirse que el nmerocompuesto p est descompuesto en factores primos.Cuando un nmero se descompone en factores primos, algunos de estos ltimos pueden encon-trarse en la descomposicin varias veces. Tal factor primo se escribe, elevado a una potencia quemuestra cuntas veces l interviene como factor.Ejemplo 3.2 El nmero 2701125 se descompone en32 53 74.Cualquier nmero natural puede ser escrito en la formap = pn11 pn22 ...pnkk(3.1)dondep1,p2, ...,pkson diferentes divisores primos del nmerop, yn1,n2, ...,nksealan cuntasvecesdichosdivisoresserepitenenladescomposicindel nmerop. Ladescomposicin(1)deun nmero natural p en factores primos es nica, es decir, no existen otros nmeros primos quesean divisores del nmero p, y las potencias n1, n2, ..., nk no pueden sustituirse por otras potencias.Si los nmeros naturalesp1 yp2 son divisibles por un mismo nmero naturalp, este ltimo sedenomina divisor comn de los nmerosp1 yp2. El nmero natural mximo por el que se dividenp1yp2lleva el nombre de mximo comn divisor (MCD) de dichos nmeros. Si el MCD de dosnmeros es igual a la unidad, se llaman recprocamente primos.Si los nmeros naturalesp1 yp2 son recprocamente primos y el nmero naturalp es divisibletanto porp1 como porp2, entoncesp se divide por el productop1p2.Ejemplo 3.3 Determine el mximo comn divisor de los nmeros 55125 y 16335.SolucinComo55125 = 32 53 72y16335 = 33 5112, entonces el MCD =32 5.Se llama mnimo comn mltiplo (MCM) de dos nmeros naturales p1 y p2 un nmero naturalmnimo que es divisible porp1 y porp2.www.Matematica1.com CAPTULO 3. NMEROS REALES 79Ejemplo 3.4 Determine el mnimo comn mltiplo de los nmeros 55125 y 16335.SolucinComo 55125 =32 53 72y 16335 =33 5112, entoncesMCM = 33 53 72 112.Si, como resultado de la divisin de un nmero natural p por otro nmero natural m, se obtieneel nmero naturalq tal queq=pm, se dice quep se divide porm.Dividir enteramente un nmero natural p por otro nmero natural m signica encontrar dosnmerosq yr, de la serie natural ampliada, que verique la igualdadp = mq +r, con la particu-laridad de quer satisfaga la condicin0 r < m. El nmeroq se denomina cociente y el nmeror, resto de la divisin. Sir = 0, se dice que el nmero natural p se divide por el nmero natural mexactamente.Ejemplo 3.5 Determnese el MCD(1144; 360).SolucinComo1144 = 3603 + 64, entonces MCD(1144; 360) = MCD(360; 64).Como360 = 645 + 40, entonces MCD(360; 64) = MCD(64; 40).Como64 = 401 + 24, entonces MCD(64; 40) = MCD(40; 24).Como40 = 241 + 16, entonces MCD(40; 24) = MCD(24; 16).Como24 = 161 + 8, entonces MCD(24; 16) = MCD(16; 8).Como16 = 82, entonces MCD(16; 8) = MCD(8; 0) = 8, es decir,MCD(1144; 360) = 8.Una vez determinado el MCD(p; m), resulta posible hallar tambin el mnimo comn mltiplode estos nmeros MCM(p; m), de la siguiente maneraMCM(p; m) =pmMCD(p; m).Ejemplo 3.6 Determnese el MCM(1144; 360).SolucinComo el MCD(1144; 360) = 8, entoncesMCM(p; m) =11443608= 51480.3.3. Nmeros enterosAnteriormentesealamosquelasustraccinnoessiemprerealizabledentrodel conjuntodenmeros naturales. Por esta razn tenemos la necesidad de ampliar el conjunto de nmeros natu-rales.En este anlisis, introduciremos nuevos nmeros, nmeros naturales de signo menos, es decir,nmeros del tipo m, donde m es un nmero natural, y los llamaremos nmeros enteros negativos,notados por Z.Diremos que dos nmeros enteros negativos m y n son iguales, si son iguales los nmerosm yn.www.Matematica1.com CAPTULO 3. NMEROS REALES 80Examinemos un conjunto de nmeros, que incluye todos los nmeros naturales, el cero y todoslos nmeros negativos. Convengamos en considerar que dos nmeros de dicho conjunto son iguales,si ambos son nmeros naturales iguales, si ambos son nmeros enteros negativos iguales, o si cadauno de ellos es cero.Denamos ahora las operaciones de adicin y multiplicacin para los nmeros de este conjunto.Si ambos nmeros que han de ser adicionados o multiplicados pertenecen a una serie natural ampli-ada, entonces, las operaciones de adicin y multiplicacin para dichos dos nmeros se determinande igual forma.Si uno de los nmeros o ambos nmeros, que deben sumarse o multiplicarse, son enteros nega-tivos, las operaciones de adicin y multiplicacin para estos dos nmeros se realizan de la siguientemanera:1. (m) + (n) = (m+n);2. (m) + 0 = 0 + (m) = m;3. (m) +n =___(mn), siempre que m > nn m, cuando m < n0, si m = n;4. (m)n = m(n) = (mn);5. (m)(n) = mn;6. (m)0 = 0(m) = 0.Un conjunto de nmeros que incluye todos los nmeros naturales, el cero y todos los nmerosenteros negativos con las deniciones de igualdad y de operaciones de adicin y multiplicacin, sedenomina conjunto de nmeros enteros y se representa por Z, mientras que los nmeros menciona-dos llevan el nombre de nmeros enteros.Las leyes principales de adicin y multiplicacin de los nmeros enteros son anlogas a aquellasque se usan para sumar y multiplicar los nmeros naturales.Para las operaciones de adicin y multiplicacin de los nmeros enteros se introducen opera-cionesinversas, lasdesustraccinydivisin, exceptodeladivisinporcero. Laoperacindesustraccin es en este caso siempre realizable, y la operacin de divisin, no siempre es posible. Sinembargo, al igual que para los nmeros naturales, los nmeros enteros siempre admiten la divisinentera.Dividir un nmero enteroa por un nmero natural m con resto, signica hallar dos nmerosenterosq yr tales, que sea vlida la igualdada = mq +r, con la particularidad de quer satisfacela condicin0 r < m.A continuacin damos algunas propiedades:1. Seaa un nmero entero cualquiera y seam, cualquier nmero natural. Entonces, existe elnico par de nmeros enterosq yr que satisface las condicionesa = mq +r y0 r < m.2. Todo nmero para puede escribirse en la formaa = 2q, dondeq es cierto nmero entero.www.Matematica1.com CAPTULO 3. NMEROS REALES 813. Todo nmero impara puede escribirse en la formaa=2q + 1, dondeqes cierto nmeroentero.4. Cualquier nmero entero a, que se divide exactamente por cierto nmero natural k, puedeser escrito en la formaa = kq, dondeq es un nmero entero.5. Cualquiernmeroenteroa, quenosedivideexactamenteporciertonmeronatural k,puede escribirse en la formaa = kq +r, donder es uno de los nmeros 1, 2, ...,k 1, yq esun nmero entero.3.4. Nmeros racionalesDe acuerdo con lo expuesto anteriormente, en el conjunto de nmeros naturales no son siemprerealizables las operaciones de sustraccin y divisin. Es por esta razn que surge la necesidad deintroducir nmeros nuevos.Introduzcamos en este anlisis nmeros nuevos: fracciones con signo menos, es decir, nmerosdeltipo mn ,dondemynsonnmerosnaturales.Lafraccin mnsedenominaopuestodelafraccinmn .Un conjunto de nmeros compuesto por todos los nmeros del tipopq, dondeqes un nmer