APUNTES DE LOGICA, CONJUNTOS E INDUCCION PDF

Profesor: Rafael Gutiérrez Estrada APUNTES DE MATEMATICAS DISCRETAS UNIDAD I: LOGICA, CONJUNTOS E INDUCCION Definición: Una proposición lógica es un enunciado declarativo el cual se puede calificar como falso (F) o verdadero (V), pero no ambas cosas a la vez. Nota: A...

Profesor: Rafael Gutiérrez Estrada APUNTES DE MATEMATICAS DISCRETAS UNIDAD I: LOGICA, CONJUNTOS E INDUCCION Definición: Una proposición lógica es un enunciado declarativo el cual se puede calificar como falso (F) o verdadero (V), pero no ambas cosas a la vez. Nota: A las proposiciones lógicas las denotaremos con letras minúsculas. Ejemplos: 1. − a : Hoy es lunes (V ) 2. − b : 2+3=6 (F ) 3. − c : Lencha es linda (F ) 4. − d : Lencha es inteligente (V ) 5. − e : Hoy es lunes o martes (V ) 6. − f : Lencha es linda e inteligente (F ) 7. − g : Si hoy es viernes entonces mañana es sabado (V ) 8. − h : Un triángulo es rectángulo si y solo si tiene un angulo interno recto (V ) Observación: En algunas proposiciones lógicas intervienen palabras o enunciados que nos sirven para conectar o enlazar dos o más proposiciones. A estas palabras o enunciados les daremos el nombre de conectivos lógicos Conectivos lógicos más usados (i) “No es cierto que”. (ii) “o”. (iii) “y”. (iv) “Si… entonces…” (v) “Si y solo si”. Más ejemplos 1. − a : No es cierto que en esta clase vamos a utilizar ceros y unos (V ) 2. − b : Al levantarme tomo cafe o te (V ) 3. − c : Lencha es linda y fea (F ) 4. − d : Si x + 3 = 5 entonces x = 2 (V ) 5. − e : Un triángulo es equilatero si y solo si todos sus lados miden lo mismo (V ) Profesor: Rafael Gutiérrez Estrada PROPOSICIONES SIMPLES Y COMPUESTAS Definición: Una proposición lógica p se dice que es simple si en su enunciado no interviene ningún conectivo lógico. Definición: Una proposición lógica p se dice que es compuesta si en su enunciado interviene por lo menos un conectivo lógico. PROPOSICIONES COMPUESTAS MAS IMPORTANTES LA NEGACION: Sea p una proposición lógica Definición: La negación de p (Notación:  p ) es una proposición que se obtiene del enunciado de p al anteponerle el conectivo lógico “No es cierto que” Ejemplos: 1.- a : No es cierto que un rectángulo tiene 3 lados (V) 2.- b : No es cierto que 2+3=6 (V) b : 2+3  6 3.- c : No es cierto que Lencha es linda (V) c : Lencha no es linda c : Lencha es fea 4.- d : Hoy no es jueves (V) Tabla de verdad: p p V F F V LA DISYUNCION: Sean p y q dos proposiciones lógicas Definición: La disyunción de p con q (Notación: p  q ) es una proposición lógica que se obtiene al enlazar los enunciados de p y q con el conectivo lógico “o”. Ejemplos: Profesor: Rafael Gutiérrez Estrada 1.- a : Hoy es lunes o 2+3=5 (V) 2.- b : Lencha es fea o linda (V) 3.- c : Lencha es linda o fea (V) 4.- d : Lencha es linda o tonta (F) Tabla de verdad: p q pq V V V V F V F V V F F F LA CONJUNCION: Sean p y q dos proposiciones lógicas Definición: La conjunción de p con q (Notación: p  q ) es una proposición lógica que se obtiene al enlazar los enunciados de p y q con el conectivo lógico “y”. Ejemplos: 1.- a : Hoy es lunes y mañana martes (V) 2.- b : 2+2=4 y 1+3=5 (F) 3.- c : Lencha es bonita e inteligente (F) 4.- d : Lencha es bonita y tonta (F) Tabla de verdad: p q pq V V V V F F F V F F F F LA CONDICIONAL: Sean p y q dos proposiciones lógicas Profesor: Rafael Gutiérrez Estrada Definición: La condicional de p con q (Notación: p → q ) es una proposición lógica que se obtiene al enlazar los enunciados de p y q de la siguiente manera “Si p entonces q ”. Ejemplos: 1.- a : Si hoy es lunes entonces mañana es martes (V) 2.- b : Si hoy es lunes entonces mañana es domingo (F) 3.- c : Si 2+5=17 entonces 3 es un numero primo (V) 4.- d : Si hoy es viernes entonces mañana es sabado (V) Tabla de verdad: p q p→q V V V V F F F V V F F V Nota: A la proposición p se le da el nombre de antecedente o hipótesis, y a la proposición q se le da el nombre de consecuente o conclusión. LA BICONDICIONAL: Sean p y q dos proposiciones lógicas Definición: La bicondicional de p con q (Notación: p  q ) es una proposición lógica que se obtiene al enlazar los enunciados de p y q de la siguiente manera p si y solo sí q. Tabla de verdad: p q pq V V V F F V F F TAUTOLOGIAS, CONTRADICCIONES Y CONTINGENCIAS Sea p una proposición lógica compuesta. Definición: Se dice que p es una tautología si esta es siempre verdadera, no importando los valores de verdad que se le asignen a las proposiciones que la conforman. Profesor: Rafael Gutiérrez Estrada Definición: Se dice que p es una contradicción si esta es siempre falsa, no importando los valores de verdad que se le asignen a las proposiciones que la conforman. Definición: Se dice que p es una contingencia si al variar los valores de verdad de las proposiciones que la conforman, está a veces es verdadera y a veces es falsa. Ejemplos: 1.- p  q , p  q , p → q y p  q son contingencias, lo cual se puede comprobar viendo las tablas de verdad arriba trabajadas. 2.- p  p es una tautología. En efecto, esto se puede ver en la siguiente tabla. p p p  p V F V F V V  p  p es una tautología 3.- p  p es una contradicción. En efecto, esto se puede ver en la siguiente tabla. p p p  p V F F F V F  p  p es una contradicción 4.- Afirmación: ( p  q)  [p  q] es una tautología. Demostración: p q p q pq ( p  q) p  q ( p  q)  [p  q] V V F F V F F V V F F V F V V V F V V F F V V V F F V V F V V V  ( p  q)  [p  q] es una tautología 5.- Afirmación: ( p → q)  [p  q] es una contradicción. Demostración: p q p p→q ( p → q) p  q ( p → q)  [p  q] V V F V F V F V F F F V F F F V V V F V F F F V V F V F  ( p → q)  [p  q] es una contradicción Profesor: Rafael Gutiérrez Estrada PROPOSICIONES EQUIVALENTES Sean p y q dos proposiciones lógicas compuestas. Definición: Se dice que p y q son dos proposiciones lógicamente equivalentes (Notación: p  q ) si ambas toman los mismos valores de verdad, esto es, si una es verdadera (o falsa), la otra también lo es. Ejemplos: 1.- Afirmación: Las proposiciones lógicas ( p  q) y p  q son lógicamente equivalentes Demostración: p q p q pq ( p  q) p  q V V F F V F F V F F V F V V F V V F F V V F F V V F V V  ( p  q)  p  q 2.- Afirmación: Las proposiciones lógicas ( p → q) y p  q son lógicamente equivalentes Demostración: p q q p  q p→q ( p → q) V V F F V F V F V V F V F V F F V F F F V F V F  ( p → q)  p  q Leyes de D Morgan: (i) ( p  q)  p  q (ii) ( p  q)  p  q 3.- Demostrar que [( p → q)  ( p → r )]  [( p → (q  r )] p q r p→q p→r ( p → q)  ( p → r ) qr p → (q  r ) V V V V V V V V V V F V F F F F V F V F V F F F V F F F F F F F F V V V V V V V F V F V V V F V F F V V V V F V F F F V V V F V  [( p → q)  ( p → r )]  [( p → (q  r )] Profesor: Rafael Gutiérrez Estrada PROPOSICIONES ABIERTAS Definición: Una proposición abierta es un enunciado en donde el sujeto x no está definido, pero que al definirlo adecuadamente hace que el enunciado se convierta en una proposición lógica. A una proposición abierta con sujeto x se le suele denotar por px Nota: Siempre que se trabaje con una proposición abierta, al sujeto x se le deben asignar valores adecuados, los cuales viven o son parte de un gran conjunto llamado el universo ( U ). Definición: Dada una proposición abierta px. Al conjunto formado por los objetos del universo que hacen que la proposición sea verdadera se le da el nombre de conjunto de verdad asociado a la proposición. Ejemplos: 1.- px : x es un digito mayor que 6 Universo: U = {0,1, 2,3, 4,5, 6, 7,8,9} Conjunto de verdad: P = {7,8,9} 2.- qx : x es un digito tal que x2 − 9 = 0 Universo: U = {0,1, 2,3, 4,5, 6, 7,8,9} Conjunto de verdad: P = {3} INDUCCION MATEMATICA Introducción. En esta actividad se revisará uno de los principios más usados en toda la matemática y en las ciencias computacionales considerando que su uso es de vital importancia para su preparación, puesto que es una herramienta para la resolución de problemas relacionados con la programación ya que permite definir un mecanismo para encontrar todos los posibles elementos de interés a partir de algunos elementos conocidos y probar con ello su validez. Inducción matemática. En muchos cursos de matemáticas, uno suele hacer conjeturas (afirmaciones que uno cree que son verdaderas, pero que no están demostradas) que giran en torno al conjunto de los números naturales. Por ejemplo dada la formula n 2 + n + 41 , al asignarle a n los valores 0,1,2, 3 y 4 los resultados que arroja son 41,43,47,53 y 61 los cuales son números primos, de donde uno se puede atrever a conjeturar que la anterior formula da siempre números primos, no importando las valores Profesor: Rafael Gutiérrez Estrada que se le asignen a n ( n número natural). Por supuesto que nadie nos garantiza que los resultados que nos arroje tal formula al asignarle a n valores naturales, sean siempre números primos, de hecho, si n = 40 al evaluar en la formula nos da 402 + 40 + 41 = 412 el cual obviamente no es un numero primo. Ejemplos como el anterior existen muchos, en donde a veces ir de lo particular a lo general, esto es, usar el método inductivo, no siempre arroja resultados correctos. ¿Cuándo una proposición que gira en torno al conjunto de los números naturales es verdadera para todo número natural? La respuesta a la anterior pregunta la da el Principio de Inducción Matemática el cual nos dice que una proposición es verdadera para todo número natural n si y solo si se cumplen las siguientes 2 condiciones: (i) La proposición es verdadera para n = 1 y (ii) La proposición es verdadera para n = k + 1 , siempre que sea verdadera para n = k Observemos que en (ii) está implícita una proposición condicional del tipo “Si p entonces q” en donde el enunciado para p es, “la proposición es verdadera para n = k ”, y el enunciado para q es, “la proposición es verdadera para n = k + 1 ”. Por tal razón (ii) se puede descomponer a su vez en 2 pasos, la hipótesis y la conclusión. Por lo tanto, para demostrar que una proposición es verdadera para todo número natural se procede de la siguiente manera: (i) Se verifica que la proposición sea verdadera para n = 1. (Base de la inducción) (ii) Se supone que la proposición es verdadera para el número natural n = k. (Hipótesis de inducción). (iii) Se demuestra que la proposición es verdadera para el número natural n = k + 1. (Paso inductivo) Ejemplo1: Demuéstrese que para todo número natural n n(n + 1) pn : 1 + 2 + 3 + +n= Es verdadera 2 Demostración: Observa que el lado izquierdo de la fórmula es una suma con n sumandos, que inicia en 1, va aumentando de 1 en 1 y termina en n. (i) (Base de la inducción). Claramente la proposición es verdadera para n = 1 , ya que: Profesor: Rafael Gutiérrez Estrada 1(1 + 1) p1 : 1= es verdadera 2 Nota: Debes sustituir en la fórmula el valor de n=1, considerando que para el ejemplo el lado izquierdo de la igualdad es una suma que inicia en 1 y termina en 1 (ii) (Hipótesis de inducción). Supongamos que la proposición es verdadera para n = k , esto es, k (k + 1) pk : 1 + 2 + 3 + +k = es verdadera 2 (iii) (Paso inductivo). Por demostrar que la proposición es verdadera para n = k + 1 , esto es, por demostrar que: (k + 1)[(k + 1) + 1] (k + 1)(k + 2) 1+ 2 + 3 + + k + (k + 1) = = 2 2 Para demostrar esto último obsérvese que por hipótesis de inducción: k (k + 1) 1+ 2 + 3 + +k = 2 De donde sumando k+1 a ambos miembros de la igualdad se obtiene: k (k + 1) 1+ 2 + 3 + + k + (k + 1) = + (k + 1) "sumando" 2 k (k + 1) + 2(k + 1) = "factorizando" 2 (k + 1)(k + 2) = 2 Con lo cual queda demostrado que la proposición es verdadera para n = k + 1 , y así la proposición es verdadera para todo número natural. Ejemplo2: Demuéstrese que para todo número natural n Profesor: Rafael Gutiérrez Estrada 1 + 1 + + 1 = 3− 1 − 1 2 −1 3 −1 (n + 1) − 1 4 2(n + 1) 2(n + 2) 2 2 2 Demostración: Por inducción matemática (i) (Base de la inducción). Claramente la proposición es verdadera para n = 1 , ya que 1 3 1 1 = − − (1 + 1) − 1 4 2(1 + 1) 2(1 + 2) 2 (ii) (Hipótesis de inducción). Supongamos que la proposición es verdadera para n = k , esto es, 1 + 1 + + 1 = 3− 1 − 1 2 −1 3 −1 (k + 1) − 1 4 2(k + 1) 2(k + 2) 22 2 (iii) (Paso inductivo). Por demostrar que la proposición es verdadera para n = k + 1 , esto es, por demostrar que: 1 + 1 + + 1 + 1 = 3− 1 − 1 2 −1 3 −1 (k + 1) − 1 [( k + 1) + 1] − 1 4 2[(k + 1) + 1] 2[( k + 1) + 2] 2 2 2 2 ó 1 + 1 + + 1 + 1 = 3− 1 − 1 2 −1 3 −1 ( k + 1) − 1 ( k + 2) − 1 4 2(k + 2) 2(k + 3) 2 2 2 2 Para demostrar esto último obsérvese que por hipótesis de inducción: 1 + 1 + + 1 = 3− 1 − 1 2 −1 3 −1 (k + 1) − 1 4 2(k + 1) 2(k + 2) 22 2 1 De donde sumando a ambos miembros de la igualdad se tiene: (k + 2) − 1 2 Profesor: Rafael Gutiérrez Estrada 1 1 1 1 3 1 1 1 + 2 + + + = − − + 2 −1 3 −1 (k + 1) − 1 (k + 2) − 1 4 2(k + 1) 2(k + 2) (k + 2) − 1 2 2 2 2 3 1 1 1 = − − + 4 2(k + 2) 2(k + 1) (k + 2) 2 − 1 3 1 1 1 = − − + 2 4 2(k + 2) 2(k + 1) k + 4k + 3 3 1 1 1 = − − + 4 2(k + 2) 2(k + 1) (k + 3)(k + 1) 3 1 (k + 3) − 2 = − − 4 2(k + 2) 2(k + 1)(k + 3) 3 1 (k + 1) = − − 4 2(k + 2) 2(k + 1)(k + 3) 3 1 1 = − − † 4 2(k + 2) 2(k + 3) Con lo cual queda demostrado que la proposición es verdadera para n = k + 1 , y así la proposición es verdadera para todo número natural. Algo importante con relación al principio de inducción matemática es que el inciso (i) (Base de la inducción) es de vital importancia, ya que si este se supone que se cumple como mucha gente lo hace, entonces podría llegarse a concluir que una cierta proposición que gira en torno a los números naturales es verdadera para todo número natural, cuando en realidad quizás no lo sea para ningún número. Un ejemplo típico para ilustrar la anterior situación es el dado por la proposición “Todo número natural es igual a su sucesor”, es fácil comprobar que si se supone valido el paso (i) del principio de inducción matemática, entonces el paso (ii) implica el paso (iii), de donde se concluiría que todos los números naturales son iguales, lo cual obviamente es falso. También es importante mencionar que en el principio de inducción matemática se pueden hacer algunas variantes de tal manera que la base de la inducción no necesariamente empiece en n = 1 , si no que empiece en un número mayor o incluso en números menores (Ver ejercicio 3 de la tarea, en donde la base de inducción empieza en n = 14 ). MAS EJEMPLOS DE INDUCCION MATEMATICA 1.- Demuestre que la siguiente proposición es verdadera para todo número natural n. pn : 1 + 3 + 5 + 7 + + (2n − 1) = n2 Demostración: Por inducción matemática (i) (Base de la inducción). Claramente la proposición es verdadera para n = 1 , ya que: Profesor: Rafael Gutiérrez Estrada 2(1) − 1 = 12 (ii) (Hipótesis de inducción). Supongamos que la proposición es verdadera para n = k , esto es, 1+ 3 + 5 + 7 + + (2k − 1) = k 2 (iii) (Paso inductivo). Por demostrar que la proposición es verdadera para n = k + 1 , esto es, por demostrar que: 1+ 3 + 5 + 7 + + (2k − 1) +  2( k + 1) − 1 = ( k + 1) 2 Observación: Por (ii) 1+ 3 + 5 + 7 + + (2k − 1) + (2k + 1) = k 2 + (2k + 1) = k 2 + 2k + 1 = (k + 1)2 † 2.- Demuestre que la siguiente proposición es verdadera para todo número natural n. n(n + 1)(2n + 1) pn : 12 + 22 + 32 + + n2 = 6 Demostración: Por inducción matemática (i) (Base de la inducción). Claramente la proposición es verdadera para n = 1 , ya que: 1(1 + 1) ( 2(1) + 1) 12 = 6 (ii) (Hipótesis de inducción). Supongamos que la proposición es verdadera para n = k , esto es, k (k + 1)(2k + 1) 12 + 22 + 32 + + k2 = 6 (iii) (Paso inductivo). Por demostrar que la proposición es verdadera para n = k + 1 , esto es, por demostrar que: (k + 1)[(k + 1) + 1][2(k + 1) + 1] (k + 1)(k + 2)(2k + 3) 12 + 22 + 32 + + k 2 + (k + 1) 2 = = 6 6 Observación: Profesor: Rafael Gutiérrez Estrada k (k + 1)(2k + 1) Por (ii) 1 +2 +3 + 2 2 2 + k + (k + 1) 2 2 = + (k + 1) 2 6 k (k + 1)(2k + 1) + 6(k + 1) 2 = 6 (k + 1)[k (2k + 1) + 6(k + 1)] = 6 (k + 1)[2k 2 + 7k + 6] = 6 (k + 1)(k + 2)(2k + 3) = † 6 3.- Demuestre que la siguiente proposición es verdadera para todo número natural n. pn : 7n − 1 es divisible entre 6 Demostración: Por inducción matemática (i) (Base de la inducción). Claramente la proposición es verdadera para n = 1 , ya que: 71 − 1 = 6 es divisible entre 6 (ii) (Hipótesis de inducción). Supongamos que la proposición es verdadera para n = k , esto es, 7 k − 1 es divisible entre 6 Equivalentemente 7k − 1 = 6c para algún c  (iii) (Paso inductivo). Por demostrar que la proposición es verdadera para n = k + 1 , esto es, por demostrar que: 7 k +1 − 1 es divisible entre 6 Observación: Por (ii) 7k +1 − 1 = 7(7 k ) − 1 = 7(7 k − 1) + 7 − 1 = 7(7 k − 1) + 6 = 7(6c) + 6 = 6(7c + 1)  7k +1 − 1 es divisible entre 6 † Profesor: Rafael Gutiérrez Estrada 31/2.- Demuestre que la siguiente proposición es verdadera para todo número natural n. pn : 11n − 6 es divisible entre 5 Demostración: Por inducción matemática (i) (Base de la inducción). Claramente la proposición es verdadera para n = 1 , ya que: 111 − 6 = 5 es divisible entre 5 (ii) (Hipótesis de inducción). Supongamos que la proposición es verdadera para n = k , esto es, 11k − 6 es divisible entre 5 Equivalentemente 11k − 6 = 5c para algún c  (iii) (Paso inductivo). Por demostrar que la proposición es verdadera para n = k + 1 , esto es, por demostrar que: 11k +1 − 6 es divisible entre 5 Observación: Por (ii) k +1 11 − 6 = 11(11 ) − 6 = 11(11 − 6) + 66 − 6 = 11(11 − 6) + 60 = 11(5c) + 5(12) = 5(11c + 12) k k k  11k +1 − 6 es divisible entre 5 † 4.- Demuestre que la siguiente proposición es verdadera para todo número natural n. pn : 6(7n ) − 2(3n ) es divisible entre 4 Demostración: Por inducción matemática (i) (Base de la inducción). Claramente la proposición es verdadera para n = 1 , ya que: 6(71 ) − 2(31 ) =36 es divisible entre 4 (ii) (Hipótesis de inducción). Supongamos que la proposición es verdadera para n = k , esto es, 6(7k ) − 2(3k ) es divisible entre 4 Equivalentemente Profesor: Rafael Gutiérrez Estrada 6(7k ) − 2(3k )=4c para alguna c  (iii) (Paso inductivo). Por demostrar que la proposición es verdadera para n = k + 1 , esto es, por demostrar que: 6(7k +1 ) − 2(3k +1 ) es divisible entre 4 Observación: 6(7 k +1 ) − 2(3k +1 ) = 6(7)(7 k ) − 2(3k +1 ) = 7 6(7 k )  − 2(3k +1 ) = 7 6(7 k ) − 2(3k )  + 14(3k ) − 2(3k +1 ) = 7 6(7 k ) − 2(3k )  + 14(3k ) − 2(3)(3k ) = 7 6(7 k ) − 2(3k )  + 8(3k ) Por (ii) = 7  4c  + 8(3k ) = 4 7c + 2(3k )   6(7 k +1 ) − 2(3k +1 ) es divisible entre 4 †