Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
1 Fundamentos de la Matemática Prof. Adrián Milano Tema 1: CONCEPTOS BÁSICOS DE LÓGICA “Es por lógica que demostramos, pero es por intuición que descubrimos” Henri Poincaré. (Matemático francés 1854 – 1912) INTRODUCCIÓN Es objetivo primordial de este material acercar al lector al lenguaje y simbología matemática así también como las reglas lógicas que permiten comprender y resolver problemas matemáticos. Intentar definir en pocas palabras que es la lógica es tan difícil como intentar definir que es la matemática, por lo tanto, no lo haremos. Como aproximación, partiremos de que la lógica es la disciplina que se ocupa del estudio de los razonamientos, deducciones e inferencias. Por “razonamiento” entendemos un proceso por el cual se concluye una afirmación, llamada conclusión, a partir de un conjunto de afirmaciones llamadas premisas o hipótesis. Podríamos decir que uno de los objetivos de la lógica es la formalización del lenguaje y el estudio de los razonamientos, estableciendo reglas y técnicas para decidir si un determinado razonamiento es o no válido. Por ejemplo, un razonamiento válido, desde el punto de vista lógico es el siguiente: Todos los uruguayos tienen cuatro ojos. Luis es uruguayo. Por lo tanto, Luis tiene cuatro ojos. Un ejemplo de razonamiento no válido es: Todos los gatos tienen cuatro patas. Una paloma no es un gato. Entonces, una paloma no tiene cuatro patas. Observar que, si bien es cierto que las palomas no tienen cuatro patas, esto no puede deducirse de la verdad de las premisas “Todos los gatos tienen cuatro patas” y “Una paloma no es un gato”. La validez de un razonamiento no depende de si las premisas o la conclusión son verdaderas. Un razonamiento es válido si la conclusión es verdadera bajo el supuesto de que las premisas lo son. Si bien el filósofo griego Aristóteles (384 AC – 322 AC) fue el primero en hacer un estudio sistemático del razonamiento lógico, se debe al matemático y filósofo alemán Gottfried Leibniz (1646 – 1716) el desarrollo de la lógica simbólica como un lenguaje científico universal y al matemático y lógico británico George Boole (1815 – 1864) los comienzos de la lógica matemática. Dado que la lógica aporta las bases para construir una teoría matemática sin contradicciones, es que presentamos, de manera intuitiva, algunos conceptos básicos de dos ramas de la lógica que utiliza la matemática que son: la lógica proposicional y la lógica de predicados. PROPOSICIONES En el lenguaje coloquial muchas veces, con el fin de simplificar los discursos, establecemos enunciados que dan lugar a distintas interpretaciones. Por ejemplo: “En un hospital se atendieron los amigos de Luis y María”. Este enunciado tiene diferentes interpretaciones. Podemos pensar que en el hospital se atendieron los amigos de Luis y los amigos de María o que se atendieron los amigos comunes a Luis y María o inclusive que se atendieron los amigos de Luis y además María. Enunciados como estos no son en general utilizados en matemática. Los enunciados o problemas matemáticos no pueden dar lugar a distintas interpretaciones. Para que esto ocurra, el lenguaje utilizado, tanto en la forma de escribir el problema (sintaxis) como el significado que tiene lo que se está escribiendo (semántica) deben estar claramente especificados, de esta manera, el que escribe y el que lee deben entender lo mismo. Por ejemplo, para investigar si 42 es múltiplo de 3 , debemos conocer, aparte de los números, el significado de la palabra “múltiplo”. Si no conocemos o tenemos dudas del significado de “múltiplo”, difícilmente podamos decidir si 42 es múltiplo de 3 . Como mencionamos anteriormente, los objetos de estudio de la lógica son los razonamientos. En estos razonamientos se utilizan determinadas oraciones, llamadas proposiciones. Una proposición o enunciado es una oración de la cual podemos decir, sin ambigüedad, si es verdadera o falsa. Es por tal motivo que decimos que las proposiciones son bivalentes, ya que pueden tomar solo dos valores de verdad, que son: 1) V o 2) F . V si la proposición es verdadera y F si es falsa. Algunos textos, asignan el 1 a las proposiciones verdaderas y el 0 a las proposiciones falsas. 2 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA En un determinado universo, cada proposición tiene un valor de verdad bien definido, es verdadera o es falsa, pero no ambas o ninguna de ellas. Ejemplos de oraciones que son proposiciones son las siguientes: 1) Los triángulos equiláteros tienen sus tres lados iguales. 2) 3 5 11 3) El 15 de enero de 1934 llovió en algún barrio de Montevideo. Ejemplos de oraciones que no son proposiciones son: 4) Debes estudiar asiduamente. 5) ¿Qué hora es? 6) ¡Qué bien! 7) Hoy es viernes. 8) Hoy es un hermoso día. 9) Ella vivió en Uruguay. 10) El número x es un número par. 11) Los números ba y ba 2 son números pares. La oración 7) no es una proposición debido que cambia su valor de verdad con el tiempo, es verdadera los viernes y falsa los demás días. Por otra parte, la oración 8) tampoco es una proposición, pues depende de la apreciación personal. Algunas personas pueden considerar hermosos los días de lluvia, mientras que otros considerar hermosos los días soleados. Si bien, las oraciones 9), 10) y 11) no son proposiciones, pueden transformarse en ellas si se les asigna un valor a las variables que contienen. Es decir, la oración 9) se transforma en una proposición si especificamos quien es “Ella”. Lo mismo ocurre con las oraciones 10) y 11). Por ejemplo, si en la oración 10) remplazamos x por 3 obtenemos una proposición falsa, pero si lo remplazamos por 4 obtenemos una proposición verdadera. Expresiones como la oración 9), 10) y 11) reciben el nombre de predicados, proposiciones abiertas o funciones proposicionales. En el caso de la oración 9) decimos que la variable es “Ella” , en la 10) la variable es x y en el caso de la proposición 11) las variables son a y b . En general, una proposición abierta o predicado, contiene una o más variables y no es una proposición, salvo que se sustituya cada una de las variables por ciertas opciones o valores permitidos. El conjunto al cual pertenecen los valores que pueden tomar las variables de una cierta función proposicional se le llama universo o dominio de la proposición. Este conjunto no puede ser vacío. Muchas veces, haciendo abuso del lenguaje, a los predicados se les llama simplemente proposiciones. Ejercicio 1 Indicar cuáles de las siguientes oraciones son proposiciones. En caso de ser proposiciones establecer su valor de verdad. 1) En el año 2007, el Dr. Tabaré Vázquez era el presidente de Uruguay. 2) 23 es un número par. 3) Feliz cumpleaños. 4) Es más fácil estudiar matemática que física. 5) La temperatura es agradable. 6) En el conjunto de los números naturales, existen tres números impares. 7) 2 3 5x SINTAXIS DE LA LÓGICA PROPOSICIONAL El área de la lógica que trata de proposiciones se llama lógica proposicional y fue desarrollada inicialmente por el filósofo griego Aristóteles hace más de dos mil trescientos años. La lógica proposicional distingue dos tipos de proposiciones, las simples y las compuestas. Una proposición simple, primitiva o atómica consta solamente de un sujeto y un predicado.Ejemplos de proposiciones simples son las siguientes: 1) Eduardo Galeano fue periodista. 2) Los triángulos isósceles tienen dos ángulos iguales. 3 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Las proposiciones compuestas, son proposiciones simples unidas mediante conectivos lógicos. Los conectivos lógicos son cinco: 1) No 2) o 3) y 4) si … entonces 5) si, y solo sí. Ejemplos de proposiciones compuestas son: 1) Eduardo Galeano fue periodista y su familia vive en Perú. 2) Si sale el sol entonces, lloverá o habrá viento. Solemos representar las proposiciones simples mediante letras como p , ,q r , etc. Por ejemplo, la notación p “Los perros vuelan” indica que p es el nombre de la proposición “Los perros vuelan”. Definidos los conectivos lógicos, podemos decir que una proposición simple es la que carece de conectivos lógicos. Los métodos para producir nuevas proposiciones a partir de las proposiciones simples fueron estudiados por el matemático inglés George Boole en 1854 en su libro “Las leyes del pensamiento” y son de utilidad para la matemática, ya que muchos de los enunciados matemáticos se construyen combinando una o más proposiciones simples. El conjunto formado por las infinitas proposiciones simples, los conectivos lógicos y algunos símbolos auxiliares, como, por ejemplo, los paréntesis, forman parte de lo que llamamos el alfabeto de la lógica proposicional. Conociendo el alfabeto de la lógica proposicional, podemos construir un lenguaje a partir de determinadas reglas. Si p y q son dos proposiciones simples cualesquiera, las proposiciones compuestas: p , ,p q p q p q y p q que se leen respectivamente como: “no p ” , “ p y q ”, “ p o q ” , “si p entonces q ” y “ p si, y solo si, q ” y que estudiaremos a continuación formarán parte de dicho lenguaje. SEMÁNTICA DE LA LÓGICA PROPOSICIONAL El primer paso para el estudio de la lógica proposicional es conocer su sintaxis, el segundo, es el estudio de las reglas que rigen la semántica del lenguaje. Ya mencionamos que una proposición puede ser verdadera o es falsa, pero ¿cómo saber si es verdadera o falsa? Comenzaremos asumiendo que las proposiciones simples tienen, en un determinado universo, un valor de verdad conocido. A partir de estos valores de verdad, construiremos el valor de verdad de las proposiciones compuestas dependiendo de los conectivos lógicos que la definan. Para poder asignar el valor de verdad de una proposición compuesta necesitamos conocer el valor de verdad de las proposiciones simples que la definen y el significado que se le da a cada conectivo lógico. Comencemos entonces por dar un significado a cada conectivo lógico. NEGACIÓN Si p es una proposición, entonces “no p ” es una proposición llamada negación de p que se simboliza: p o ( )p Por ejemplo, si consideramos la proposición “Uruguay es un país de América Latina” entonces su negación es “No es cierto que Uruguay es un país de América Latina” o lo que es lo mismo “Uruguay no es un país de América Latina”. Se debe tener cuidado al negar una proposición. La negación de la proposición “Todos los alumnos estudian física” no es “Ningún alumno estudia física” sino que es “Existe por lo menos un alumno que no estudia física”. Daremos el siguiente significado al conectivo lógico : Si la proposición p es verdadera, entonces p es falsa y si p es falsa, entonces p es verdadera. Por tal motivo p y p se suelen llamar proposiciones contradictorias. CONECTIVO SIGNIFICADO SÍMBOLO Negación no Conjunción y Disyunción o Condicional si … entonces Bicondicional si, y solo si, p p V F F V Esta información se puede resumir en la siguiente tabla, llamada tabla de verdad para la negación: Los llamados conectivos lógicos u operadores lógicos son: la negación, la conjunción, la disyunción, el condicional y el bicondicional. Su significado y los símbolos utilizados para cada uno de estos conectivos se indican en la tabla adjunta: 4 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA CONJUNCIÓN Si p y q son dos proposiciones, entonces “ p y q ” es una nueva proposición, llamada conjunción o producto lógico de p y q y se simboliza como: p q o ( )p q Por ejemplo, si p es la proposición “Cauchy fue un matemático francés” y q es la proposición “Cauchy nació en 1789” entonces p q es la proposición “Cauchy fue un matemático francés y Cauchy nació en 1789” o lo que es lo mismo “Cauchy fue un matemático francés y nació en 1789”. La proposición p q será verdadera cuando lo sean p y q a la vez. En general, una tabla de verdad para una proposición compuesta es una tabla donde en sus columnas se listan las posibles combinaciones de los valores de verdad de las proposiciones simples que integran la proposición compuesta y los correspondientes valores de verdad que esta última toma. DISYUNCIÓN Si p y q son dos proposiciones entonces “ p o q ” es una nueva proposición, llamada disyunción o suma lógica de p y q y se simboliza como: p q o ( )p q Por ejemplo, si p es la proposición “Cauchy fue un matemático francés” y q es la proposición “Cauchy nació en 1789” entonces p q es la proposición “Cauchy fue un matemático francés o Cauchy nació en 1789” que también puede traducirse en “Cauchy fue un matemático francés o nació en 1789”. En matemática, por definición, siempre consideraremos que el “o” es inclusivo. Esto quiere decir que una proposición de la forma p q es verdadera cuando p es verdadera o cuando q es verdadera o cuando ambas proposiciones lo son. Es decir, la disyunción p q es verdadera cuando al menos una de las proposiciones p o q es verdadera. Por ejemplo, la proposición “Cauchy fue matemático o filósofo” es verdadera si es verdad que Cauchy fue matemático o filósofo o ambas cosas a la vez. La proposición solo es falsa si Cauchy no fue matemático ni filósofo. El uso del “o” inclusivo es típico de la matemática ya que en el lenguaje ordinario el “o” tiene un uso exclusivo. Por ejemplo, cuando en el menú de un restaurante dice “Sin cargo adicional, se sirve sopa o postre” nos informan que, sin cargo adicional, podemos elegir sopa o postre pero no ambas cosas a la vez. Teniendo en cuenta las consideraciones anteriores es que tenemos lo siguiente: Considerando lo anterior, concluimos que la tabla de verdad para la disyunción es la siguiente: p q p q V V V V F F F V F F F F p q p q V V V V F V F V V F F F La conjunción p q es una proposición verdadera solo cuando p y q son ambas verdaderas, por tal motivo, la tabla de verdad para la conjunción es la siguiente: La disyunción p q es una proposición falsa solo cuando p y q son ambas falsas, por tal motivo, la tabla de verdad para la disyunción es la siguiente: 5 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA CONDICIONAL O IMPLICACIÓN Si p y q son dos proposiciones, entonces la proposición: “ si p entonces q ” se llama condicional o implicaciónde q por p y se simboliza por: p q o ( )p q En este caso p se llama antecedente o hipótesis y q consecuente o tesis. Por ejemplo, si p es la proposición “ 2 es mayor que 4 ” y q la proposición “ 3 2 7 ”, entonces p q es la proposición “Si 2 es mayor que 4 , entonces 3 2 7 ”. Es inadmisible que una proposición verdadera nos conduzca a una proposición falsa, por tal motivo, diremos que la implicación p q es verdadera en todos los casos, salvo cuando p es verdadera y q es falsa. Por ejemplo, si p “Apruebo el examen” y q “Presto el libro”, entonces la implicación p q puede considerarse como una “promesa” condicionada por p . Si p es falsa, es decir, si no apruebo el examen, queda liberada la promesa y por tanto si q es verdadera o falsa, la implicación p q es verdadera. Por el contrario, si p es verdadera, es decir, si apruebo el examen y es falso que preste el libro, la promesa no se cumple y la implicación p q es falsa. Aunque pueda resultar extraño, la proposición “Si 2 2 5 , entonces 7 14 3 ” es verdadera, debido a que las proposiciones 2 2 5 y 7 14 3 son ambas falsas (en la aritmética usual). Lo mencionado anteriormente, conduce a que la tabla de verdad para el condicional sea la siguiente: Observar que el hecho que p q sea verdadera no nos brinda información sobre los valores de verdad de p y q . Solo en el caso que p q sea falsa, podemos concluir que p es verdadera y q es falsa. El símbolo p q desempeña un papel fundamental en la matemática y puede leerse de las siguientes formas: “ Si p entonces q ” , “ p implica q ” , “ p es condición suficiente para q ” o “ q es condición necesaria para p ”. Hay que tener en cuenta que en una implicación no necesariamente se da una relación de “causa – efecto” entre el antecedente y el consecuente. Por ejemplo, en la implicación: “Si corro mucho, entonces me canso” efectivamente hay una relación de causa (corro mucho) y efecto (me canso), pero en la implicación “Si 4 no es un número par, entonces el cuadrado es un triángulo” no lo hay, sin embargo ambas implicaciones son verdaderas. BICONDICIONAL O DOBLE IMPLICACIÓN Si p y q son dos proposiciones, entonces “ p si, y solo si, q ” es una proposición llamada doble implicación o bicondicional de p y q y se simboliza: p q o ( )p q Las distintas formas de leer el símbolo p q son: “ p si, y solo si, q ” , “ p es condición necesaria y suficiente para q ” o “ p y q son proposiciones equivalentes”. La proposición p q es verdadera, únicamente cuando p y q son ambas verdaderas o ambas falsas. Por ejemplo, la proposición “La Tierra es cuadrada si, y solo si, la Luna es de queso” es verdadera, ya que las proposiciones “La Tierra es cuadrada” y “La Luna es de queso” son ambas falsas. p q p q V V V V F F F V V F F V p q qp V V V V F F F V F F F V La implicación p q es una proposición falsa solo cuando p es verdadera y q es falsa, por tal motivo, la tabla de verdad para el condicional es la siguiente: El bicondicional p q es una proposición verdadera solo cuando p y q son ambas verdaderas o ambas falsas. La tabla de verdad para el bicondicional es la siguiente: 6 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Rara vez en el lenguaje cotidiano se utiliza el bicondicional. En general, se suele usar el condicional como si fuera un bicondicional. Por ejemplo, cuando en el lenguaje cotidiano se dice: “Si culminas los deberes, entonces podrás salir a jugar” se está queriendo decir, “Sales a jugar si, y solo si culminas los deberes” Es decir, se utiliza “entonces” como un “si, y solo si”. Si culminó los deberes, saldrá a jugar y si salió a jugar es porque culminó los deberes. En general, en matemática evitaremos este tipo de ambigüedades, y no interpretaremos un condicional por un bicondicional o viceversa. EJEMPLO 1 Consideremos el siguiente enunciado: “ 3 5 9 y, si 2 11 13 entonces 2 3 5 ” Si llamamos respectivamente p , q y r a las proposiciones “ 3 5 9 ” , “ 2 11 13 ” y “ 2 3 5 ” , tenemos que el enunciado original se simboliza mediante la fórmula lógica: ( )p q r La tabla de verdad correspondiente a la proposición ( )p q r es la siguiente: p q r q q r ( )p q r V V V F V V V V F F V V V F V V V V V F F V F F F V V F V F F V F F V F F F V V V F F F F V F F CONVENCIONES SINTÁCTICAS Normalmente se adoptan algunas convecciones para evitar poner paréntesis en algunas proposiciones compuestas en las que intervienen más de un conectivo lógico. Estas convenciones se resumen en el siguiente recuadro. El orden de precedencia de los conectivos lógicos es el siguiente: 1) tiene prioridad frente a y 2) y tienen la misma prioridad. 3) y tienen la misma prioridad. 4) y tienen mayor prioridad que y . 5) Conectivos de igual prioridad se agrupan comenzando por la izquierda. En resumen, el orden de los conectivos lógicos de mayor a menor prioridad es: 1) 2) y 3) y Además, en fórmulas lógicas donde intervienen muchos conectivos, luego de tener en cuenta las prioridades de los conectivos y los paréntesis, se agrupa comenzando por la izquierda y se leerá de izquierda a derecha. Para poder entender mejor las convenciones sintácticas, proponemos los siguientes ejemplos: 1) La proposición p q es la misma que ( )p q dado que tiene prioridad frente a . 2) La proposición p q r es la misma que ( )p q r ya que al tener y la misma prioridad, se agrupa comenzando por la izquierda. 3) La proposición p q r s t es la misma que ( )p q r ( )s t . Ejercicio 2 Sean las proposiciones: s “15 es divisible entre 3 ” , t “ 3 es un número primo” y u “ 15 es par” a) Traducir al lenguaje usual y analizar el valor de verdad de cada una de las siguientes proposiciones: 1) u s 2) ut 3) ( )t u s 4) t u s 5) ( )t s u 6) ( )t s u b) Simbolizar en el lenguaje de la lógica proposicional las siguientes proposiciones usando los conectivos lógicos. 1) Si 3 es un número primo y 15 no es un número par, entonces 15 es divisible entre 3 . 2) Si 3 es un número primo, entonces si 15 no es un número par, 15 es divisible entre 3 . 3) Que 3 sea un número primo y 15 no sea un número par es necesario para que 15 sea divisible entre 3 . 7 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Ejercicio 3 Si p y q son dos proposiciones simples, verificar que la proposición p p q es verdadera y que la proposición ( ) ( )p q p q es falsa, cualesquiera sean los valores de verdad de p y q . TAUTOLOGÍAS, CONTRADICCIONES Y CONTINGENCIAS Decimos que una proposición compuesta es una tautología si es verdadera cualesquiera sean los valores de verdad de las proposiciones que la componen. En el casoque una proposición compuesta sea falsa, cualesquiera sean los valores de verdad de las proposiciones que la componen, diremos que es una contradicción. Las proposiciones compuestas que no son tautología ni contradicción se llaman contingencias. Las tautologías y las contradicciones son claves en los razonamientos matemáticos. Si p y q son proposiciones simples, sabemos por el ejercicio 3, que p p q es una tautología, ya que es verdadera independientemente de los valores de verdad de p y q y que la proposición ( ) ( )p q p q es una contradicción. Una forma que se puede utilizar para decidir si una proposición compuesta es una tautología, contradicción o contingencia es construyendo la tabla de verdad correspondiente. Obviamente, que esto es sencillo en el caso que la proposición esté compuesta por pocas proposiciones simples. Por ejemplo, si p , q y r son proposiciones simples, verifiquemos que qrprqp )()( es una tautología realizando la tabla de verdad correspondiente. Una manera de construir la tabla de verdad de proposiciones que contienen varios conectivos y proposiciones simples, es la siguiente: p q r p r q V V V V V V V F F V F V V V F F V V V V F F V F F V V V V F F V V V F F V F V V V V V V F F V V V V F F F V F F F V V F V F F V V F F F F V V V F F F V V F F F V F V F F V V V 1) Comenzamos completando las columnas l, 3 y 5 con los distintos valores de verdad que pueden tomar las proposiciones p , q y r . (El patrón utilizado para construir estas columnas nos asegura que se contemplaron todas las formas de combinar V y F y que cada combinación aparece una sola vez). 2) Bajo cada conectivo lógico se coloca el valor de verdad correspondiente, hasta obtener la columna de la proposición que debemos verificar que es una tautología. El orden en que se colocaron los valores de verdad debajo de cada conectivo fue el siguiente: columna 2, columna 4, columna 8, columna 10 y por último columna 6. Ejercicio 4 Siendo p y q dos proposiciones simples, construir la tabla de verdad para cada una de las siguientes proposiciones compuestas. Indicar cuáles son tautologías, contradicciones o contingencias. 1) p p (Ley del tercer excluido) 2) p p 3) ( ) ( )p q q p 4) qqpp )( (Modus Ponens) 5) ( ) ( )p q q p 8 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA IMPLICACIÓN REÇÍPROCA, CONTRARIA Y CONTRARRECÍPROCA A cada implicación p q podemos asociarle otras tres implicaciones: 1) q p llamada implicación recíproca de p q . 2) p q llamada implicación contraria de p q . 3) q p llamada implicación contrarrecíproca de p q . (Lleva este nombre por ser la proposición contraria a la implicación recíproca). Por ejemplo, para la implicación “Si ABC es un triángulo equilátero, entonces ABC es un triángulo isósceles” la implicación recíproca es: “Si ABC es un triángulo isósceles, entonces ABC es un triángulo equilátero”, la contraria es “Si ABC es un triángulo no equilátero, entonces ABC es un triángulo no isósceles” y la contrarrecíproca: “Si ABC es un triángulo no isósceles, entonces ABC es un triángulo no equilátero”. Nos interesa investigar si existe una relación entre los valores de verdad de una implicación, su recíproca, su contraria y su contrarrecíporca. El hecho que una proposición sea verdadera no implica que lo sea su recíproca. De hecho, el enunciado “Si ABC es un triángulo equilátero, entonces ABC es un triángulo isósceles” es verdadero y no lo es el enunciado “Si ABC es un triángulo isósceles, entonces ABC es un triángulo equilátero”. Ahora, ¿sucede lo mismo con una implicación y su contrarrecíproca? o con una implicación y su contraria? Para poder contestar a estas preguntas, realizaremos las tablas de verdad para las implicaciones recíprocas, contraria y contrarrecíproca de una proposición cualquiera p q . p q qp pq p q pq qp V V V V F F V V V F F V F V F V F V V F V F V F F F V V V V V V Como puede observarse, la columna correspondiente a la implicación p q coincide con la columna de la implicación q p . Sin embargo, las columnas correspondientes a las implicaciones p q , q p y p q no coinciden. Esto permite asegurar lo siguiente: La verdad o falsedad de una implicación, no asegura la verdad o falsedad de su recíproca ni la de su contraria, pero si la de su contrarrecíproca. Informalmente, podemos decir que la implicación contrarrecíproca de una implicación dada es la misma implicación, pero dicha con otras palabras. IMPLICACIÓN LÓGICA En la parte 4) del ejercicio 4 se verificó que la proposición qqpp )( , llamada Modus Ponens, es una tautología. En este caso, dado que la verdad de la conclusión q se deduce o infiere de la verdad de las premisas p y p q diremos que q es una consecuencia lógica de ( )p p q . Diremos que una proposición p implica lógicamente la proposición q o que q es una consecuencia lógica de p si, y solo si, q es verdadera cuando p es verdadera. En el caso que una proposición p implica lógicamente otra proposición q escribiremos: p q . Por ejemplo: si Ana puede votar en las elecciones nacionales de Uruguay, entonces Ana tiene 18 años o más. Es decir, la proposición “Ana puede votar en las elecciones nacionales de Uruguay” implica lógicamente la proposición “Ana tiene 18 años o más” 9 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA La implicación lógica p q indica que nunca tendremos que p es verdadera y q es falsa. Si p q , entonces q es verdadera cuando p es verdadera y si q es falsa entonces p es falsa. La noción de implicación lógica la podemos asociar con la noción de teorema. Un teorema es una proposición condicional que se puede demostrar que es tautológica. Los símbolos p q y p q no representan lo mismo. Hay una cierta relación entre ellos y es la siguiente: PROPIEDAD La proposición p implica lógicamente la proposición q si, y solo si, el condicional p q es una tautología. Por ejemplo, ya que en el ejercicio 4 se demostró que ( )p p q q es una tautología, podemos decir que ( )p p q implica lógicamente q y por lo tanto podemos escribir: ( )p p q q . Como resumen podemos decir lo siguiente: La diferencia entre los símbolos p q y p q es que mientras p q es una proposición que puede ser verdadera o falsa, p q significa que p q es una tautología. El símbolo es un conectivo lógico, sin embargo no lo es. Aclaremos que en matemática, en general y haciendo abuso del lenguaje, el símbolo p q se lee “si p entonces q ” cuando en realidad hemos visto que significa que p implica lógicamente q . En el siguiente ejercicio se enuncian las principales implicaciones lógicas o reglas de inferencia con sus nombres. Ejercicio 5 (PRINCIPALES IMPLICACIONES LÓGICAS O REGLAS DE INFERENCIA) Si p , q y r son tres proposiciones cualesquiera, demostrar cada una de las siguientesimplicaciones lógicas. Encontrar un ejemplo de un enunciado que corresponda a dicha implicación. 1) Simplificación: ,p q p p q q 2) Ampliación o adición: p p q 3) Modus Ponens: qqpp )(( El Modus Ponens se suele escribir de la forma: q qp p donde el símbolo se lee “por lo tanto”. Modus Ponens proviene del latín y significa “Modo o procedimiento de afirmación” y afirma que, si una implicación y su hipótesis son verdaderas, entonces la conclusión de la implicación también lo será. Por ejemplo, si consideramos que es verdadero que “Si n es un número natural mayor que 3 , entonces 2n es mayor que 9 ” y asumimos que la hipótesis “ n es un número natural mayor que 3 ” también es verdadera, entonces también lo será la conclusión “ 2n es mayor que 9 ”. 4) Modus Tollens: pqqp )( Al igual que en el caso anterior, esta implicación lógica puede escribirse de la forma: p q q p Modus Tollens proviene del latín y significa “Modo o procedimiento de negación” y es el procedimiento que niega el antecedente de un condicional negando el consecuente. Por ejemplo, consideremos p “El triángulo ABC tiene dos lados iguales” y q “El triángulo ABC tiene dos ángulos iguales”. Dado que la implicación p q es verdadera, si q es falsa, entonces p también lo será. 10 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA 5) Silogismo hipotético: )()()( rprqqp Esta regla puede escribirse de la forma: rp rq qp 6) Silogismo disyuntivo: pqqp )( 7) Prueba por casos: rqprqrp )()()( 8) Regla de contradicción: ( )p C p donde C es una contradicción. Observar que si p C es verdadera, como C es falsa, debe ser p falsa y por lo tanto p debe ser verdadera. La regla de contradicción es la base del método de demostración por contradicción o por reducción al absurdo, que es utilizado en muchas demostraciones de teoremas matemáticos. La idea detrás de este método es demostrar la conclusión p de un argumento, mostrando que, si p fuera falsa, entonces llegaríamos a deducir una consecuencia C que es imposible. Es decir, suponemos que la conclusión p que queremos demostrar es falsa y usando las restantes premisas (hipótesis) buscamos obtener una contradicción C . Una vez obtenida la contradicción C , podemos decir que la conclusión es verdadera. Ejemplos de demostraciones por reducción al absurdo podrán encontrarse más adelante. EQUIVALENCIA LÓGICA En todas las áreas de la matemática, necesitamos decidir cuándo dos objetos son iguales. En lógica, definiremos el concepto de igualdad entre proposiciones. Como vimos anteriormente, las tablas de verdad correspondientes a las proposiciones p q y q p son la misma, es decir, independientemente de los valores de verdad que tomen las proposiciones p y q las proposiciones p q y q p toman el mismo valor de verdad. Esto nos lleva a definir cuando dos proposiciones son iguales desde el punto de vista de la lógica, es decir, cuando son lógicamente equivalentes. Diremos que dos proposiciones p y q son lógicamente equivalentes o equivalentes , y escribimos: p q , cuando p y q tienen respectivamente los mismos valores de verdad. Según esta definición, para demostrar que dos proposiciones p y q son lógicamente equivalentes, hay que verificar que si p es verdadera entonces q es verdadera y que si p es falsa, entonces q también lo es. Algunos textos utilizan la notación p q para indicar que p y q son lógicamente equivalentes. Informalmente, podemos decir que dos proposiciones lógicamente equivalentes, son dos maneras distintas de decir lo mismo. EJEMPLO 2 Si p y q son dos proposiciones, entonces se cumplen las siguientes equivalencias lógicas llamadas Leyes de De Morgan, en honor al matemático británico Augustus De Morgan (1806 -1871): 1) qpqp )( 2) qpqp )( Demostraremos la propiedad 1) y dejamos al lector la demostración de la 2). Si ( )p q es verdadera, entonces p q es falsa y por lo tanto una de las proposiciones p o q es falsa y sus negaciones verdaderas y consecuentemente p q es verdadera. Si ( )p q es falsa, entonces p q es verdadera y por lo tanto las proposiciones p y q son ambas verdaderas y su negaciones falsas y consecuentemente p q es falsa. Concluimos así que: qpqp )( 11 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Otro ejemplo de equivalencia lógica importante es la siguiente: ( ) ( ) ( )p q p q q p Al igual que p q y p q no tienen el mismo significado, tampoco lo tienen p q y p q . Mientras p q significa que p q es una tautología, p q es una proposición que puede ser verdadera o falsa. PROPIEDAD Las proposiciones p y q son lógicamente equivalentes si, y solo si, p q es una tautología. Dejamos a cargo del lector la demostración de esta propiedad que muchos textos toman como definición de proposiciones lógicamente equivalentes. Aclaremos que al igual que con la implicación lógica, en matemática, haciendo abuso del lenguaje el símbolo p q lo leemos “ p si, y solo si, q ” cuando en realidad sabemos que significa que p y q son lógicamente equivalentes. De la misma manera que existe el álgebra de números, existe el álgebra de proposiciones. Enunciaremos en el siguiente ejercicio sus propiedades, llamadas leyes de la lógica, usando el concepto de equivalencia lógica. Estas leyes permiten transformar una determinada proposición en otra más sencilla. LEYES DE LA LÓGICA Si p , q , r y s son cuatro proposiciones cualesquiera, T es una tautología y C una contradicción, entonces se cumplen las siguientes leyes, llamadas leyes de la lógica: 1) Ley de la doble negación: ( )p p 2) Leyes idempotentes: ( )p p p y ( )p p p 3) Leyes conmutativas: ( ) ( )p q q p y ( ) ( )p q q p 4) Leyes asociativas: rqprqp )()( y rqprqp )()( 5) Leyes distributivas: ( ) ( ) ( )p q r p q p r y ( ) ( ) ( )p q r p q p r 6) Leyes de neutro: pCp y pTp 7) Leyes inversas: Cpp y Tpp 8) Leyes de dominación: TTp y CCp 9) Leyes de absorción: pqpp )( y pqpp )( 10) Leyes de De Morgan: qpqp )( y qpqp )( Las leyes de De Morgan permiten negar proposiciones en las intervienen la conjunción y la disyunción. 11) Ley contrarrecíproca: )()( pqqp 12) Ley de la implicación: )()( qpqp 13) Ley de reducción al absurdo: ( ) ( )p q p q C 14) Leydel bicondicional ( ) ( ) ( )p q p q q p Queda a cargo del lector demostrar las leyes de la lógica que considere conveniente. 12 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Las leyes de la lógica se pueden utilizar para transformar proposiciones complejas en otras más sencillas. Esto se debe a que una proposición en una fórmula lógica se puede sustituir por otra que sea lógicamente equivalente sin alterar el valor de verdad de la fórmula. Esta técnica se ilustra en el siguiente ejemplo, junto con el hecho de que si se cumple p q y q r entonces p r . EJEMPLO 3 Si p y q son dos proposiciones, hallar una proposición lo más sencilla posible que sea lógicamente equivalente a la proposición )()( qpqp . )()()()()()( qpqpqpqpqpqp negacióndobleladeLeyMorganDedeLeyes pCpqqp neutrodeLeyinversaladeLeyvasdistributiLeyes )(( Hemos llegado a que las proposiciones )()( qpqp y p son lógicamente equivalentes. Ejercicio 6 Escribir las proposiciones p q , p q y sus negaciones utilizando solamente la conjunción, disyunción o negación. Ejercicio 7 Si p , q y r son tres proposiciones, demostrar, sin usar tablas de verdad, las siguientes equivalencias lógicas usando las leyes de la lógica. 1) ( ) ( )p q p q p 2) ( ) ( )p q r q q r RAZONAMIENTOS Nos proponemos a continuación definir lo que llamaremos razonamiento y razonamiento válido. Un argumento o razonamiento tiene asociado una implicación de la forma 1 2( ... )np p p q donde 1 2, ,..., np p p son n proposiciones que llamamos premisas o hipótesis del argumento y q es una proposición que llamamos conclusión o tesis. La implicación 1 2( ... )np p p q se llama condicional asociado al razonamiento. Diremos que qppp n ).......( 21 es un razonamiento válido si, y solo si, cada vez que las premisas 1 2, ,..., np p p son verdaderas, la conclusión q también lo es. Si alguna de las premisas 1 2, ,..., np p p es falsa, entonces qppp n ).......( 21 es verdadera sin importar el valor de verdad de la proposición q y por lo tanto, el razonamiento es válido. Si alguna de las premisas es falsa, no podemos asegurar que la conclusión sea verdadera. Por ejemplo, Supongamos que es verdad que 2 1,5 y que a su vez, si 2 1,5 entonces 2 22 (1,5) . Usando la regla de inferencia Modus Ponens, podemos concluir que 2 22 2 (1,5) 2,25 , lo cual es falso. Se ha usado en el argumento la proposición falsa 2 1,5 . 13 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Para demostrar que un razonamiento cuyo condicional asociado es qppp n ).......( 21 es válido, es demostrar que la implicación qppp n ).......( 21 es una tautología. EJEMPLO 4 Verificar la validez del siguiente razonamiento dado por su condicional asociado cualesquiera sean las proposiciones simples , , ,p r s t y u . ( ) ( ) ( ) ( )p r r s t s t u u p Justificación: TollensModus Premisa renglónoctavoysextoelusandoSilogismo lógicaiaEquivalenc Premisa renglónquintoysegundoelusandohipóteticoSilogismo lógicaiaEquivalenc deaConmutativ Premisa hipóteticoSilogismo Premisas )()( )()( )()( p u up ututut ut tp tststs ts st sp srrp Ejercicio 8 a) Simbolizar los siguientes razonamientos y decidir si son razonamientos válidos. 1) Si Ana es la asesina, mentirá cuando la interroguen. Ana mintió cuando la interrogaron, por lo tanto, Ana es la asesina. 2) Si un número natural x es divisible entre 10 , entonces termina en 0 . Si el número x no termina en 0 , entonces x no es divisible entre 10 . 3) Si Luis se compró su casa, ha ganado la lotería o ha pedido un préstamo en el banco. Luis no ha pedido un préstamo en el banco. Por lo tanto, si Luis no ha ganado la lotería, entonces no se ha comprado su casa. b) Sean p , q y r tres proposiciones simples cualesquiera. 1) Investigar si es válido el siguiente razonamiento cuyo condicional asociado es ( ) ( )p q q r r p Observación: Para decidir si este razonamiento es válido, es necesario observar solo las filas cruciales de la tabla de verdad donde las tres premisas p q , q r y r son verdaderas a la vez, ya que si la proposición rrqqp )()( es falsa, la implicación ( ) ( )p q q r r p es verdadera sin importar el valor de verdad de p . 2) Verificar la validez del siguiente razonamiento dado por su condicional asociado estudiando solo la o las filas de la tabla de verdad que son cruciales para establecer dicha validez. rqprqpp )()( Si bien es cierto que podemos utilizar las tablas de verdad para decidir si un determinado razonamiento es o no válido, el trabajo resulta tedioso cuando el número de premisas es alto. (Piense el número de filas que tiene la tabla de verdad de un razonamiento que tiene cuatro, cinco o seis proposiciones simples). En estos casos, resulta conveniente estudiar la validez del razonamiento usando reglas de inferencia o leyes de la lógica. En el siguiente ejemplo, utilizaremos las reglas de inferencia y las leyes de la lógica para justificar la validez del siguiente razonamiento: 14 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Para mostrar que un razonamiento cuyo condicional asociado es qppp n ).......( 21 no es válido, debemos verificar que la implicación qppp n ).......( 21 no es una tautología y para ello basta con encontrar un caso (y con uno solo basta) para el cual dicha implicación es falsa, es decir, debemos encontrar un caso en el cual las premisas nppp ,.......,, 21 son verdaderas y la conclusión q es falsa. Este caso encontrado, es lo que llamamos un contraejemplo para el razonamiento. EJEMPLO 5 Se consideran las proposiciones simples , , ,p q r s y t . Demostraremos que no es válido el razonamiento cuyo condicional asociado está dado por: ( ) ( ( )) ( ) ( )p p q q r s t r s t . Para ello necesitamos asignar un valor de verdad a cada una de las proposiciones , , ,p q r s y t de modo que la conclusión s t sea falsa mientras que las cuatro premisas , , ( )p p q q r s y t r son verdaderas. El único caso en que s t es falsa es cuando s es verdadera y t es falsa, es decir, cuando s es falsa y t es verdadera. Como p es una de las premisas, entonces p debe ser verdadera. Luego, para que p q sea verdadera q puede ser verdadera o falsa. Como t r y t son verdaderas, entonces r es verdadera. Si r es verdadera y s es falsa, entonces r s es falsa y la única forma que ( )q r s sea verdadera es cuando q es falsa. Concluimos así que, si p es verdadera, q es falsa, r es verdadera, s es falsa y t es verdadera, entonces las premisas , , ( )p p q q r s y t r son verdaderas y la conclusión s t es falsa y por lo tanto no es válido el razonamiento cuyo condicional asociado es ( ) ( ( )) ( ) ( )p p q q r s t r s t . Ejercicio 9 Sean ,p q y r tres proposiciones simples. Sin usar tablas de verdad estudiar la validez de los siguientes razonamientos dados por su condicional asociado. En caso de no ser un razonamiento válido, atribuir valores de verdad a ,p q y r de modo que todas las premisas sean verdaderas y la conclusión sea falsa. a) ( ) ( )p p q q r T siendo T una tautología. b) ( ) ( ( )p q p q r r c) (( ) ) ( )p q r q r p NOCIONES BÁSICAS DE LÓGICA DE PREDICADOS La lógica proposicional no es suficiente para expresar adecuadamente el significado de muchos de los razonamientos que habitualmente hacemos en matemática. Por ejemplo, consideremos el siguiente enunciado: Todo número natural es un número entero. Si 3 es un número natural, entonces 3 es un número entero. Si llamamos p “Todo número natural es un número entero”, q “ 3 es un número natural” y r “3 es un número entero”, debería ocurrir que q r sea una consecuencia lógica de p , es decir: ( )p q r . Sin embargo, esto no se da debido a que no hay independencia entre las proposiciones que intervienen. Las proposiciones q y r , que en nuestro enunciado quedan como independientes, en realidad no lo son, ya que hablan de un mismo elemento que es el número 3 . En este ejemplo, y muchos casos, la validez de un razonamiento depende de la relación existente entre las proposiciones que forman parte de él. En estos casos, la lógica proposicional no es suficiente para establecer la validez o no del razonamiento, si lo será la lógica de predicados, que es una extensión de la lógica proposicional. Para construir un lenguaje en la lógica de predicados debemos tener símbolos para denotar: 1) los objetos del universo, 2) las propiedades que cumplen dichos objetos, 3) los conectivos y 4) los cuantificadores. Ejemplos de símbolos para las propiedades que tienen los objetos del universo pueden ser, el símbolo de mayor, el de menor, etc. Los símbolos para los conectivos son los mismos que los utilizados para la lógica proposicional y los símbolos para los cuantificadores son los que pasaremos a explicar a continuación. 15 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA CUANTIFICADORES En el lenguaje matemático, los cuantificadores permiten usar y simbolizar la noción de cantidad, que en el lenguaje coloquial expresamos utilizando términos como: “todos” , “existe algún” , “alguno” , “ninguno” , etc. En matemática es bastante común la utilización de funciones proposicionales o predicados. Como ya hemos mencionado, una función proposicional o predicado, contiene una o más variables y no es una proposición, salvo que se sustituya cada una de las variables por ciertas opciones o valores permitidos en el universo de la proposición. En el predicado “ 2 3x es un número impar” con una sola variable x , la cual toma valores en el universo de los números naturales, 2 3x es el sujeto y “es un número impar” es la propiedad que tiene el sujeto de dicho predicado. Otro ejemplo de predicado es: 2 2 0x y , donde las variables x e y varían en el universo de los números reales. Más ejemplos de predicados, donde las variables son números reales son: 1) ( )p x “ 5x ” 2) ( , )p x y “ 5 3x y ” 3) ( , , )p x y z “ 2 2x z y x y ” Los predicados no son ni verdaderos ni falsos por si solos, su valor de verdad depende de los valores que toman las variables en el universo de estudio. Por ejemplo, si llamamos ( )p x al predicado “ El número 3x es impar si x es un número natural”, podemos observar que cuando sustituimos x por números pares, ( )p x es verdadero y cuando sustituimos x por números impares, ( )p x es falso. Es decir, si tomamos como universo el conjunto de los números pares, ( )p x es verdadero, mientras que si el universo es el conjunto de los números impares ( )p x es falso. Como casos particulares, (0)p ; (2)p y (8)p son proposiciones verdaderas mientras que (1)p ; (3)p y (1001)p son proposiciones falsas. La expresión ( )p x “ x es un número impar” no es una proposición a menos que se le asigne un valor específico a la variable x . Ahora, si decimos: “Para todo número natural x , se cumple ( )p x ” o “Existe un número natural x para el cual se cumple ( )p x ” estas expresiones pasan a ser proposiciones ya que podemos afirmar que la primera es falsa y la segunda es verdadera. Lo que hemos hecho es cuantificar la expresión ( )p x mediante las expresiones “Para todo” y “Existe”. Cuantificamos al utilizar expresiones como “todos” , “siempre” , “nunca” , “existe algún” , “no existe” , “ninguno”, etc. Por ejemplo, “Siempre un triángulo tiene dos lados” o “Nunca un triángulo tiene dos lados” El área de la lógica que trabaja con predicados y cuantificadores es llamada lógica de predicados o lógica de primer orden. Sus fórmulas, que se forman a partir de los predicados, los conectivos lógicos de la lógica proposicional y los cuantificadores son las utilizadas en matemática. Explicaremos a continuación el significado de los dos cuantificadores utilizados en matemática, el cuantificador universal y el cuantificador existencial. CUANTIFICADOR UNIVERSAL Muchos de los enunciados en matemática establecen que una cierta propiedad es verdadera para todos los valores de una o varias variables pertenecientes a un determinado universo o dominio. Por ejemplo, Para todo número real x se cumple que 2 0x . Enunciados como este se expresan utilizando el cuantificador universal que se simboliza con: El símbolo , significa “Para todo” y se llama cuantificador universal. Si ( )p x es un predicado que depende de una variable x , entonces los símbolos: ( )( ( ))x p x o , ( )x p x pueden leerse como: “Para todo x , ( )p x ” , “Para cualquier x , ( )p x ” o “Para cada x , ( )p x ” . Decimos que la cuantificación universal del predicado ( )p x es “ ( )p x es verdadera para todos los x del dominio”. Es decir, , ( )x p x es la cuantificación universal del predicado ( )p x . 16 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA EJEMPLO 6 El enunciado “ Para todo x se cumple que 2 0x ” se puede simbolizar como: 2, 0x x Si estamos interesados en especificar que x pertenece al universo o dominio de los números reales, debemos escribir: 2,( 0)x x x o simplemente, haciendo abuso del lenguaje, 2, 0x x (donde simboliza al conjunto de los números reales y el símbolo se lee “pertenece” o “perteneciente”) Otro ejemplo es el siguiente: El enunciado “Para todo x , si x es múltiplo de 2 y menor que 1 , entonces 0x ” se puede simbolizar de la siguiente manera: , (2 1) 0x x x x donde el símbolo 2 x significa que x es múltiplo de 2 . Observar que este enunciado es verdadero para cada número natural x , pero no lo es para cada número entero x , es decir, el enunciado es verdadero en el universo de los números naturales, pero no en el universo de los números enteros. Si estamos interesados en especificar que x pertenece al universo de los números naturales, deberíamos escribir: , (2 1) 0x x x x (donde simboliza al conjunto de los números naturales). OBSERVACIÓN En matemática es bastante común omitir el cuantificador universal en enunciados que lo requieren. Por ejemplo,el enunciado “ Si x es un número natural, entonces 0x ” en realidad quiere decir que “ Para todo número natural x se cumple que 0x ” CUANTIFICADOR EXISTENCIAL Así como muchos de los enunciados en matemática establecen que una cierta propiedad es verdadera para todos los valores de una o varias variables, otros tantos confirman la existencia de por lo menos un elemento que cumple con una cierta propiedad. Por ejemplo, Existe un número real x tal que 2 4x . Enunciados como este se expresan utilizando el cuantificador existencial que se simboliza con: El símbolo significa “Existe (por lo menos)” y se llama cuantificador existencial. Si ( )p x es un predicado que depende de una variable x , entonces los símbolos: ( )( ( ))x p x o , ( )x p x o / ( )x p x pueden leerse de la siguiente forma: “Existe x tal que ( )p x ” , “Para algún x se cumple ( )p x ” o “Existe algún x que cumple ( )p x ” . Decimos que la cuantificación existencial del predicado ( )p x es “ Existe por lo menos un elemento x del dominio tal que ( )p x es verdadera”. Es decir, / ( )x p x es la cuantificación existencial del predicado ( )p x . EJEMPLO 7 El enunciado “ Existe un número real x que cumple 2 10x ” se puede simbolizar como: 2/ 10x x Es común encontrar enunciados donde intervengan los dos cuantificadores, por ejemplo, el enunciado ( )( )( )x y x y que por abuso de lenguaje se escribe , /x y x y se lee: “ Para todo x , existe y tal que x es mayor o igual a y ” Este tipo de predicados tiene dos variables x e y y es verdadero en el universo de todas las parejas de números naturales, de números enteros, de números racionales y de números reales. Inclusive es verdadero en el universo formado por todas las parejas de personas del mundo, si consideramos que en este contexto el símbolo x y significa que la persona x mide más o igual que la persona y . En realidad, el enunciado , /x y x y es verdadero en cualquier universo no vacío, pues dado cualquier x del universo, existe un y del mismo universo que cumple x y , por ejemplo, el propio x . 17 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Ejercicio 10 Se consideran en el universo de los números enteros los siguientes predicados: ( )p x “ 0x ” , ( )q x “ x es par” y ( )r x “ x es un cuadrado perfecto” Escribir los siguientes enunciados en forma simbólica utilizando los cuantificadores universal o existencial. 1) Al menos un número entero es par. 2) Cada número entero es estrictamente menor que el siguiente. 3) Existe por lo menos un entero positivo que es par. 4) Si x es un cuadrado perfecto, entonces x es par. 5) Cualquier número real x mayor que cero y cuadrado perfecto es par. VALORES DE VERDAD DE LAS CUANTIFICACIONES Investiguemos en cada uno de los siguientes casos cual es el valor de verdad de las siguientes cuantificaciones, considerando que x pertenece al dominio de los números reales. 1) , 3x x x 2) 2, 12x x 3) , 3x x x 4) 2, 12x x Es claro que la cuantificación 1) es verdadera, pues la desigualdad 3x x es verdadera para cada número real x , sin embargo, la cuantificación 2) es falsa dado que existen números reales que no cumple la desigualdad 2 12x , por ejemplo, el 3 verifica 23 12 . Respecto a las cuantificaciones 3) y 4), como no existe número real que verifique la igualdad 3x x , podemos decir que la cuantificación 3) es falsa y que la 4) es verdadera porque lo es, por ejemplo, para 5x . Como generalización de estos ejemplos, tenemos lo siguiente: Si ( )p x es un predicado cuya variable x pertenece a un universo U , entonces: 1) la cuantificación universal , ( )x p x es verdadera si el predicado ( )p x es verdadero para cada x perteneciente a U y es falsa, si existe al menos un x perteneciente a U para el cual ( )p x es falso. 2) la cuantificación existencial , ( )x p x es verdadera si ( )p x es verdadero para al menos un x perteneciente a U y es falsa, si ( )p x es falso para todos los x pertenecientes a U . Observar además que cualquiera sea el predicado ( )p x , si la cuantificación universal , ( )x p x es verdadera, entonces también lo es la cuantificación existencial , ( )x p x , es decir, “ ( )( ( )) ( )( ( ))x p x x p x ”. Sin embargo, si la cuantificación , ( )x p x es verdadera, no necesariamente lo es la cuantificación , ( )x p x . Por ejemplo, si consideramos los predicados ( )p x “ x es múltiplo de 4 ” y ( )q x “ x es múltiplo de 2 ” donde x es un número natural cualquiera, entonces: son verdaderas las cuantificaciones: ,( ( ) ( ))x p x q x , ,( ( ) ( ))x p x q x y ,( ( ) ( ))x p x q x y son falsas: ,( ( ) ( ))x p x q x y ,( ( ) ( ))x q x p x . NEGACIÓN DE CUANTIFICADORES La negación de “Todos los hombres tienen pelo corto” es “Existe algún hombre que no tiene pelo corto” y recíprocamente la negación de “Existe algún hombre que no tiene pelo corto” es “Todos los hombres tienen pelo corto”. La negación de , ( )x p x es ( )( ( ))x p x y la negación de ( )( ( ))x p x es ( )( ( ))x p x . 18 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA IMPLICACIÓN LÓGICA Y EQUIVALENCIA LÓGICA Los conceptos de implicación lógica y equivalencia lógica para la lógica de predicados se definen de forma análoga a como se definen en la lógica proposicional. Sean ( )p x y ( )q x dos predicados que dependen de una misma variable x que pertenece a un universo U (no vacío) Decimos que ( )p x implica lógicamente ( )q x , y escribimos: ,( ( ) ( ))x U p x q x , si, y solo si, el condicional ( ) ( )p x q x es verdadero para cada x perteneciente a U . Decimos que ( )p x y ( )q x son lógicamente equivalentes, y escribimos: ,( ( ) ( ))x U p x q x , si, y solo si el bicondicional ( ) ( )p x q x es verdadero para cada x perteneciente a U . Aclaramos que tanto las reglas de inferencia como las leyes de la lógica proposicional mencionadas anteriormente también son válidas para la lógica de predicados. Usando el concepto de equivalencia lógica entre predicados, establecemos las siguientes equivalencias lógicas: Leyes de De Morgan generalizadas: 1) ( , ( )) , ( )x p x x p x 2) ( , ( )) , ( )x p x x p x 3) , ( ) , ( )x p x x p x 4) , ( ) , ( )x p x x p x Las leyes de De Morgan confirman que la negación de un predicado cuantificado es lógicamente equivalente al predicado que se obtiene de sustituir el símbolo por , el de por y el predicado por su negación. La negación de un cuantificador universal es un cuantificador existencial y, viceversa, la negación de un cuantificador existencial es un cuantificador universal. También son válidas las siguientes equivalencias lógicas: 1) , , ( , ) , , ( , )x y p x y y x p x y 2) , , ( , ) , , ( , )x y p x y y x p x y EJEMPLO 8 Consideremos los predicados ( )p x “ x es múltiplo de 4 ” y ( )q x “ x es múltiplo de 2 ” donde x es un número natural cualquiera. El enunciado “ Si x es múltiplo de 4 , entonces x es múltiplo de 2 ” se simboliza: ))()((, xqxpx . El proceso que permite simbolizar su negación es el siguiente: ,( ( ) ( )) , ( ( ) ( )) , ( ( ) ( )) ,( ( ) ( ))x p x q x x p x q x x p x q x x p x q x Por lo tanto, la negación de “ Si x es múltiplo de 4 , entonces x es múltiplo de 2 ” es “ Existe un número x tal que x es múltiplo de 4 y x no es múltiplo de 2 ” Ejercicio 11 a) Simbolizar los siguientes enunciados y establecer su valor de verdad. 1) Todos los números naturales son mayores o iguales a cero. 2) Existe un número natural x tal que 012 x 3) El cuadrado de todo número natural es un número natural. 4) Todo número natural x es mayor o es menor que 1 . 5) Los números naturales son positivos e impares. 6) Existe un número natural n tal que, para todo número natural x , se cumple xn . 7) La suma de dos números naturales es un número natural. b) Negar los enunciados anteriores y simbolizarlos. c) Traducir el siguiente enunciado a lenguaje simbólico y luego negarlo. Si el producto de dos números naturales es mayor a veinticinco, entonces uno de ellos es mayor a cinco. 19 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Ejercicio 12 a) Consideremos los siguientes enunciados donde x , y , z son números naturales. 1) , , /x y z x y z y 2) / , ,z x y x y z Traducir las cuantificaciones al lenguaje usual y establecer su valor de verdad. b) Consideremos los predicados ( )p x “ 2 1 5x ” y ( )q x “ 2 9x ” donde x es un número entero. Investigar si alguna de las siguientes proposiciones implica la otra: 1) / ( ( ) ( ))x p x q x 2) ( / ( )) ( / ( ))x p x x q x ¿Son equivalentes las proposiciones / ( ( ) ( ))x p x q x y ( / ( )) ( / ( ))x p x x q x ? c) Encontrar un ejemplo para el cual , / ( , )x y p x y sea verdadera y / , ( , )x y p x y sea falsa. Como consecuencia de lo obtenido en el ejercicio 12 tenemos que: Las proposiciones / ( ( ) ( ))x p x q x y ( / ( )) ( / ( ))x p x x q x no son lógicamente equivalentes al igual que , / ( , )x y p x y y / , ( , )x y p x y . Son lógicamente equivalentes las proposiciones / ( ( ) ( ))x p x q x y ( / ( )) ( / ( ))x p x x q x al igual que las proposiciones ,( ( ) ( ))x p x q x y ( , ( )) ( / ( ))x p x x q x CONCEPTOS PRIMITIVOS, DEFINICIONES, AXIOMAS Y TEOREMAS. En toda teoría matemática se pueden distinguir cuatro elementos: 1) Conceptos primitivos 2) Axiomas o postulados 3) Definiciones y 4) Teoremas Los conceptos o elementos primitivos son los que no se definen por no poderlos reducirlos a otros más sencillos. Por ejemplo, en la geometría clásica son conceptos primitivos, punto, recta y plano. Los axiomas o postulados son supuestos iniciales que entrelazan los conceptos primitivos. Son enunciados acerca de algún concepto de alguna rama de la matemática que en general ya conocemos, como, por ejemplo, la aritmética o la geometría. Los axiomas se aceptan sin demostración y son el punto de partida del desarrollo de la teoría. Según Aristóteles (384 – 321 AC), toda ciencia demostrativa necesita partir de ciertos principios indemostrables, ya que, de lo contrario, los pasos que permiten demostrar algunas de sus propiedades pueden ser infinitos. Los axiomas de la geometría clásica (o euclidiana) vinculan los conceptos de punto, recta y plano sin que previamente se hayan definido. En este caso, se apela a la intuición para dar una interpretación natural a estos conceptos. No conocemos cual es la naturaleza de los objetos con los cuales trabajamos, solo conocemos, gracias a los axiomas, las relaciones entre ellos. Por ejemplo, en la geometría clásica, el axioma de determinación de una recta, que afirma que “Dos puntos distintos determinan una única recta a la que pertenecen” , se vinculan los términos punto y recta, sin que ellos estén definidos dentro de la teoría. Aunque los matemáticos actuales le dan el mismo significado a la palabra axioma y postulado, en la antigüedad, los griegos establecían una diferencia. Llamaban axiomas, a los principios indemostrables comunes a todas las ciencias y postulados, a los principios particulares de una determinada ciencia. Por ejemplo, “Todo elemento es igual a sí mismo” sería un axioma y “Dos puntos distintos determinan una única recta a la que pertenecen” sería un postulado. En cuanto a las definiciones dadas en matemática, aclaremos que estas no son axiomas, introducen nuevos términos que se expresan a partir de los axiomas o de otros ya conocidos. Por ejemplo, en la geometría clásica, la definición de puntos alineados, como tres puntos que pertenecen a una misma recta, se expresa haciendo referencia al axioma de determinación de una recta. Definir es dar un nombre a un objeto que verifica ciertas propiedades interesantes, es poderlo identificar de manera única. Las definiciones, además de contribuir a la economía del discurso, son convenciones. Por ejemplo, se puede definir triángulo equilátero, como aquel con sus tres lados iguales, o como uno que tiene sus tres ángulos iguales. Una definición debe ser lo suficientemente clara, de modo que, dado un concepto u objeto, debemos poder decidir si cumple o no con tal definición. 20 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Es bastante común, al definir un concepto matemático, utilizar “si” o “cuando” en vez de utilizar “si, y solo si,”. Es decir, se utiliza el condicional cuando en realidad lo más adecuado es utilizar el bicondicional. Por ejemplo, en varios textos se definen cuando tres puntos están alineados de la siguiente manera: “Tres puntos están alineados si pertenecen a una misma recta” o “Tres puntos están alineados cuando pertenecen a una misma recta”. En realidad, la forma correcta de hacerlo es: “Tres puntos están alineados si, y solo si, pertenecen a una misma recta”. Por convención “si” o “cuando” en las definiciones matemáticas, tendrán el mismo significado que un “si, y solo si,”. Por lo tanto, en tales definiciones, una implicación debe leerse (de forma errónea) como un bicondicional. EJEMPLO 9 Daremos a continuación una muestra reducida de un conjunto de axiomas para la geometría plana. Conceptos primitivos: Punto y recta. (Asumiremos también como conceptos primitivos a las palabras: conjunto, elemento, pertenecer y otros términos como: existe, todo, no, distinto y otros que aparezcan en los axiomas enunciados) Axioma 1: Cada recta es un conjunto de puntos. Axioma 2: Existen por lo menos dos puntos distintos. Definición: Si un punto A es un elemento del conjunto de puntos de una recta r , diremos que A pertenece a r o que la recta r contiene al punto A . Axioma 3: Si A y B son dos puntos distintos, existe y es única la recta que contiene a los puntos A y B . Axioma 4: Si r es una recta, entonces existe un punto que no pertenece a r . Observar que el axioma 1, lejos de ser una definición de recta, establece una relación entre los conceptos primitivos de punto y recta. Los axiomas 2 y 3 nos aseguran la existencia de por lo menos una recta, pero no nos garantiza una geometría en dos dimensiones. Es mediante el axioma 4 que podemos asegurar que no estamos trabajando en una geometría unidimensional. Dado que los conceptos de punto y recta no están definidos, tenemos la libertad de atribuirles diversos significados, siempre y cuando sean consistentescon lo enunciado por los axiomas. Por ejemplo, si llamamos P a un conjunto de personas, podríamos pensar que la palabra “punto” significa “persona del conjunto P ” y la palabra “recta” , “club de P ” , donde un club es un conjunto de personas de P reunidas por un bien común. Si asumimos el hecho que cada persona pertenece a algún club y dadas dos personas del conjunto P existe un único club del cual son miembros, es sencillo verificar que los cuatro axiomas enunciados tienen sentido en este contexto. Una vez que son establecidos los conceptos primitivos y que se enuncian los axiomas de una determinada teoría, se procede a la formulación de nuevas proposiciones. Estas proposiciones, llamadas teoremas, son demostrables y son consecuencia de axiomas o teoremas ya demostrados. La elección de los axiomas de una determinada teoría matemática es en gran medida arbitraria, siempre y cuando se verifiquen las siguientes propiedades: 1) Consistencia: No pueden existir dos axiomas o teoremas que sean contradictorios. 2) Completitud: Todo teorema tiene que deducirse a partir de los axiomas o de teoremas anteriormente demostrados. 3) Independencia: Ningún axioma se debe deducir de los otros. Los axiomas deben verificar necesariamente las propiedades de consistencia y completitud, pero no necesariamente deben verificar la propiedad de independencia. El hecho que el conjunto de axiomas verifique la propiedad de independencia, solo asegura que los axiomas enunciados son los mínimos posibles para el desarrollo de la teoría. TEOREMAS La palabra teorema, proviene del latín theorema, que significa verdad no obvia, pero si demostrable. Un teorema consta de dos proposiciones o predicados H y T llamados hipótesis y tesis respectivamente. La hipótesis de un teorema es una o un conjunto de proposiciones dadas y la tesis, es la o las proposiciones que se deducen lógicamente de la hipótesis, es decir, la conclusión. Muchos de los teoremas adoptan la forma: ,( ( ) ( ))x U H x T x . Demostrar este tipo de teoremas, consiste en verificar que la implicación ( ) ( )H c T c es verdadera cualquiera sea el elemento c perteneciente al universo .U Entendemos por demostración de un teorema a un conjunto finito de secuencias válidas, apoyadas en reglas de la lógica, que permiten establecer la veracidad del teorema. 21 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA Es bastante común, omitir el cuantificador universal en un teorema. Por ejemplo, cuando enunciamos el teorema: “Si n es un número natural par, entonces 2n es par” en realidad queremos decir “Para todo número natural n , si n es par, entonces 2n es par”. Este teorema, que puede simbolizarse de la forma: , ( ( ) ( ))n H n T n , tiene como hipótesis: ( ) :H n “ n es par” y como tesis: ( )T n : “ 2n es par”. El dominio de la variable n es el conjunto de los números naturales. Otro teorema, seguramente conocido por el lector, es el teorema de Pitágoras, que afirma lo siguiente: Si ABC es un triángulo con un ángulo recto en B , entonces 222 BCABAC La hipótesis del teorema es: “ ABC es un triángulo con un ángulo recto en B ” y la tesis: “ 222 BCABAC ” En muchas oportunidades el enunciado del teorema oculta el hecho de ser una implicación. Un ejemplo de ello es el siguiente teorema: Las soluciones de la ecuación 2 0ax bx c con 0 ,a b y c números reales son 2 4 2 b b ac x a Este teorema puede enunciarse de la siguiente forma: Si x es una solución de la ecuación 2 0ax bx c donde ,a b y c son números reales y 0a , entonces 2 4 2 b b ac x a Hay varias palabras que se utilizan para llamar a determinados teoremas. Se llama corolario, a un teorema que es una consecuencia inmediata de un teorema y lema, a un teorema que no tiene interés en sí mismo pero que es útil para demostrar un teorema. La palabra teorema, la reservamos para proposiciones significativas o importantes. EJEMPLO 10 Mostraremos a continuación como a partir de los axiomas enunciados en el ejemplo 9 se puede demostrar el siguiente teorema: “Todo punto pertenece a por lo menos dos rectas distintas”. Para demostrar este teorema procedemos de la siguiente manera: Dado un punto cualquiera P , por el axioma 2, existe otro punto Q , distinto de P . Por el axioma 3, existe una única recta r , que contiene a los puntos P y Q . Por el axioma 4, existe un punto T que no pertenece a r y por el axioma 3, existe una recta s que contiene a P y T . Al encontrar dos rectas r y s que contienen al punto P hemos demostrado el teorema. DISTINTAS FORMAS DE DEMOSTRAR UN TEOREMA La demostración de un teorema es un razonamiento que establece su veracidad. Demostrar un teorema de hipótesis H y tesis T consiste en verificar que la implicación H T es verdadera o lo que es lo mismo que H T . La proposición H T es siempre verdadera a no ser que H sea verdadera y T sea falsa. Existen varias formas de demostrar un teorema y mencionaremos a continuación algunas de las más comunes. DEMOSTRACIÓN DIRECTA En la demostración directa de un teorema asumimos que la hipótesis H es verdadera y usando proposiciones que sabemos son verdaderas (reglas de inferencia, leyes de la lógica, axiomas, definiciones o teoremas ya demostrados), concluimos que la tesis T también lo es. Este tipo de demostraciones está basado en el hecho de que la única forma que la implicación H T sea falsa es que H sea verdadera y T falsa. Se descarta esa posibilidad suponiendo que H es verdadera y demostrando que T también lo es. Debe quedar claro que las hipótesis de un teorema no son ni verdaderas ni falsas. Demostrar que H T quiere decir que siempre que H sea verdadera, T también lo será. 22 TEMA 1 CONCEPTOS BÁSICOS DE LÓGICA EJEMPLO 11 Demostraremos de forma directa el siguiente teorema: Si n es un número entero par, entonces 2n es un número par. (Recordemos que un número entero n es par si, y solo si, existe un número entero a tal que 2n a ) Antes de escribir la demostración del teorema dejemos claro que la hipótesis de este teorema es “ n es un número entero par” y la tesis “ 2n es un número par”. Demostración: n es un número par existe un número entero a tal que 2 2 2 22 4 2(2 )n a n a n a 2n es un número par. Observar que se parte de la verdad de la hipótesis del teorema y se termina concluyendo la verdad de la tesis. Ejercicio 13 Teniendo en cuenta la siguiente definición: Un número entero n es impar si, y solo si, existe un número entero a tal que 2 1n a . Asumiendo que la suma y el producto de números enteros es un número entero, dar una demostración directa de los siguientes teoremas: 1) Si n es un número entero impar, entonces 2n es un número impar. 2) Si m y p son números enteros impares, entonces m p es un número par. DEMOSTRACIÓN INDIRECTA O POR CONTRARRECÍPROCO Muchas veces la demostración directa de un teorema puede ser muy complicada o imposible. Por ejemplo, intente hacer una demostración directa del siguiente teorema: Si n es un número entero y 3 2n es impar, entonces n es impar. En estos casos intentaremos una demostración indirecta, la cual permite demostrar la tesis sin partir de la hipótesis. Las demostraciones indirectas o por contrarrecíproco de un teorema de hipótesis H y tesis T se basan en que la implicación H T y su contrarrecíproca T H son lógicamente equivalentes.
Compartir