NOCIONES DE LGICA (1).pdf

Nociones de Lógica La lógica es muy importante; ya que permite resolver problemas a los que nunca se ha enfrentado el ser humano utilizando solamente su inteligencia y apoyándose de algunos conocimientos acumulados. La lógica matemática es la disciplina que trata de mét...

Nociones de Lógica La lógica es muy importante; ya que permite resolver problemas a los que nunca se ha enfrentado el ser humano utilizando solamente su inteligencia y apoyándose de algunos conocimientos acumulados. La lógica matemática es la disciplina que trata de métodos de razonamiento. En un nivel elemental, la lógica proporciona reglas y técnicas para determinar si es o no valido un argumento dado. El razonamiento lógico se emplea en matemáticas para demostrar teoremas; en ciencias de la computación para verificar si son o no correctos los programas; en las ciencias física y naturales, para sacar conclusiones de experimentos; y en las ciencias sociales y en la vida cotidiana, para resolver una multitud de problemas. Ciertamente se usa en forma constante el razonamiento lógico para realizar cualquier actividad. La lógica simbólica, en matemática, tiene como finalidad reducir procedimientos verbales complicados a simples dispositivos de letras y símbolos. Exactamente lo mismo que los números son los elementos básicos de un conjunto numérico, las proposiciones simples son los elementos de la lógica. En lógica comenzamos con las proposiciones simples, las cuales usaremos para formar proposiciones más complicadas. El tema que nos ocupa es el de la lógica usada en matemática. Aquí trabajamos con elementos básicos llamados proposiciones. Proposiciones Definición: Una proposición es toda oración respecto de la cual puede decirse si es verdadera o falsa, pero no ambas cosas a la vez. Ejemplo 1: 4 es múltiplo de 2. Los números pares son divisibles por 2. Son las cuatro de la tarde con cuarenta y cinco minutos. El 12 es el duplo de 6. (5). (9) = 59 Dada una proposición, cabe preguntar entonces si es verdadera o falsa. La veracidad o falsedad de una proposición es lo que se llama su valor de verdad. Llamaremos 𝑉 (verdadero) o 𝐹(falso) a los valores de verdad de las proposiciones. 1 Esp. Colodro Rosana Mabel Si la proposición es verdadera, diremos que su valor de verdad es 𝑉 y si es falsa, diremos que su valor de verdad es 𝐹. Así, por ejemplo, el valor de verdad de es 𝑉 y el valor de verdad de es 𝐹. Por otro lado, expresiones que no cumplen esta propiedad no son proposiciones lógicas. Ejemplo 2: 1) Ven a verme. 2) ¡Viva la libertad! 3) ¿Está lloviendo? 4) Él está triste. La primera y segunda frase tampoco son proposiciones lógicas porque no están afirmando nada y no podemos asignarles un valor de cierto o falso. La tercera es una pregunta y aunque se pueda responder con un cierto o falso, la pregunta en si no tiene un valor de verdad por lo que tampoco cuenta como proposición lógica. La cuarta podría ser una proposición lógica, pero "él está" es una afirmación muy ambigua y cualquier persona podría ocupar la posición de "él", por lo que la proposición tendría el valor de cierto o falso dependiendo de la persona a la que se aplicara, debido a esto no puede tener un valor de verdad absoluto y no puede ser una proposición lógica. Notación: Se suelen representar las proposiciones mediante las letras minúsculas 𝑝, 𝑞, 𝑟, 𝑠, … Si 𝑝 es una proposición, su valor de verdad se denotara con 𝑣(𝑝). Si queremos expresar que 𝑝 es verdadera, escribiremos 𝑣(𝑝) = 𝑉 y si es falsa 𝑣(𝑝) = 𝐹. Ejemplo 3: Sea la proposición: 𝑝: “𝐿𝑎 𝑟𝑎í𝑧 𝑐𝑢𝑎𝑑𝑟𝑎𝑑𝑎 𝑑𝑒 25 𝑒𝑠 5, 𝑜 − 5” Su valor de verdad es falso, es decir 𝑣൫𝑝൯ = 𝐹. Operaciones con proposiciones Así como en aritmética y en álgebra se estudian operaciones entre números, en lógica se estudian operaciones entre proposiciones. Definiremos las operaciones entre proposiciones en el sentido siguiente: dadas una o dos proposiciones, cuyos valores de verdad se conocen, se trata de caracterizar la proposición resultante a través de su valor de verdad. Para ello se ha de tener en cuenta el “buen sentido”. Es decir, se puede operar entre proposiciones y para ello se utilizan ciertos símbolos, llamados conectivos lógicos. 2 Esp. Colodro Rosana Mabel  Conectivos lógicos Combinando proposiciones simples obtenemos proposiciones compuestas mediante operaciones lógicas. Las principales operaciones lógicas son: negación, conjunción, disyunción, condicional y bicondicional. Consideremos los siguientes símbolos y sus operaciones asociadas: Conectivo Operación asociada Significado ~ Negación No 𝑝, no es cierto que 𝑝 ˄ Conjunción o producto 𝑝y𝑞 lógico ˅ Disyunción o suma lógico 𝑝o𝑞 ⇒ Implicación o condicional Si 𝑝 entonces 𝑞 o 𝑝 implica 𝑞 ⇔ Doble implicación 𝑝 si y solo si 𝑞 A continuación, desarrollaremos cada una de estas operaciones: Negación Se llama 𝑛𝑒𝑔𝑎𝑐𝑖ó𝑛 de la proposición 𝑝 a la que se obtiene colocando la palabra “𝑛𝑜” antes de la misma. En símbolos: ~𝑝, se lee 𝑛𝑜 𝑝 o 𝑛𝑜 𝑒𝑠 𝑐𝑖𝑒𝑟𝑡𝑜 𝑞𝑢𝑒 𝑝. Si 𝑝 es una proposición , ~𝑝 también lo es y su valor de verdad es 𝑉 si 𝑣(𝑝) = 𝐹 y es 𝐹 si 𝑣(𝑝) = 𝑉 Podemos construir la tabla de valor de verdad siguiente: 𝒑 ~𝒑 𝑽 𝑭 𝑭 𝑽 La negación es una operación unitaria puesto que opera sobre una sola proposición 𝑝 , a quien le hace corresponder la proposición ~𝑝. Nota: El arreglo que nos permite tener los posibles valores de verdad de una proposición compuesta a partir de los valores de verdad de las proposiciones componentes se llama una tabla de verdad. 3 Esp. Colodro Rosana Mabel  Ejemplo 4: Sea la proposición 𝑝: 39 𝑒𝑠 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑟𝑖𝑚𝑜 Cuyo valor de verdad es 𝑣(𝑝) = 𝐹, entonces su negación es: ~𝑝: 39 𝑛𝑜 𝑒𝑠 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑟𝑖𝑚𝑜 Cuyo valor de verdad es 𝑣(~𝑝) = 𝑉 Observación: Si bien es cierto que, de acuerdo a la definición, para formar la negación basta con anteponer la palabra “𝑛𝑜” a la proposición, en el lenguaje cotidiano la costumbre es colocar la palabra “𝑛𝑜” junto al verbo o si se quiere tenerla al principio podemos recurrir a giros como “𝑛𝑜 𝑒𝑠 𝑐𝑖𝑒𝑟𝑡𝑜 𝑞𝑢𝑒”. Conjunción La 𝑐𝑜𝑛𝑗𝑢𝑛𝑐𝑖ó𝑛 es un enunciado compuesto en el que dos proposiciones se relacionan con el conectivo lógico ˄. Ejemplo 5: Sean las siguientes proposiciones 𝑝: 39 𝑒𝑠 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑟𝑖𝑚𝑜 𝑞: 25 𝑒𝑠 𝑢𝑛 𝑐𝑢𝑎𝑑𝑟𝑎𝑑𝑜 𝑝𝑒𝑟𝑓𝑒𝑐𝑡𝑜 A partir de estas dos proposiciones, uniéndolas mediante la conjunción obtenemos una nueva proposición: 𝑝˄𝑞: 39 𝑒𝑠 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑟𝑖𝑚𝑜 𝑦 25 𝑒𝑠 𝑢𝑛 𝑐𝑢𝑎𝑑𝑟𝑎𝑑𝑜 𝑝𝑒𝑟𝑓𝑒𝑐𝑡𝑜 Tiene sentido afirmar que 𝑝˄𝑞 es verdadero o falso, pues es una proposición. En este caso podemos decir que 𝑝˄𝑞 es una proposición falsa pues para que sea verdadera la conjunción exige el cumplimiento de ambas proposiciones, entonces 𝑣(𝑝˄𝑞) = 𝐹 La tabla de valores de verdad de la conjunción es la siguiente: 𝒑 𝒒 𝒑˄𝒒 𝑽 𝑽 𝑽 𝑽 𝑭 𝑭 𝑭 𝑽 𝑭 𝑭 𝑭 𝑭 4 Esp. Colodro Rosana Mabel  Disyunción Es un enunciado compuesto en el que dos proposiciones se relacionan con el conectivo lógico ˅. La disyunción solo es falsa cuando las dos proposiciones componentes son falsas. En el uso habitual del lenguaje, esta operación establece una alternativa: alguna de las dos componentes debe cumplirse. Ejemplo 6: Sean las siguientes proposiciones 𝑝: 39 𝑒𝑠 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑟𝑖𝑚𝑜 𝑞: 25 𝑒𝑠 𝑢𝑛 𝑐𝑢𝑎𝑑𝑟𝑎𝑑𝑜 𝑝𝑒𝑟𝑓𝑒𝑐𝑡𝑜 A partir de estas dos proposiciones, uniéndolas mediante la disyunción obtenemos una nueva proposición: 𝑝˅𝑞: 39 𝑒𝑠 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑟𝑖𝑚𝑜 𝑜 25 𝑒𝑠 𝑢𝑛 𝑐𝑢𝑎𝑑𝑟𝑎𝑑𝑜 𝑝𝑒𝑟𝑓𝑒𝑐𝑡𝑜 La tabla de valores de verdad de la disyunción es la siguiente: 𝒑 𝒒 𝒑˅𝒒 𝑽 𝑽 𝑽 𝑽 𝑭 𝑽 𝑭 𝑽 𝑽 𝑭 𝑭 𝑭 Observación: La conjunción y la disyunción son operaciones binarias, en el sentido de que cada dos proposiciones 𝑝 y 𝑞 le asignan una nueva proposición. Implicación o Condicional Dos proposiciones simples 𝑝 y 𝑞 relacionadas por el conectivo lógico ⇒ conforman la proposición compuesta llamada condicional o implicación. Al relacionar dos proposiciones con este conectivo es muy importante distinguir lo que queda a la izquierda del signo “⇒” a la cual se llama 𝑎𝑛𝑡𝑒𝑐𝑒𝑑𝑒𝑛𝑡𝑒, de la que queda a la derecha del signo, a la que se llama 𝑐𝑜𝑛𝑠𝑒𝑐𝑢𝑒𝑛𝑡𝑒: 𝑝 ณ ⇒ 𝑞 ณ 𝑎𝑛𝑡𝑒𝑐𝑒𝑑𝑒𝑛𝑡𝑒 𝑐𝑜𝑛𝑠𝑒𝑐𝑢𝑒𝑛𝑡𝑒 El sentido de este conectivo es señalar que, si la proposición 𝑎𝑛𝑡𝑒𝑐𝑒𝑑𝑒𝑛𝑡𝑒 es verdadera, también lo es la proposición 𝑐𝑜𝑛𝑠𝑒𝑐𝑢𝑒𝑛𝑡𝑒; es decir, basta o es 5 Esp. Colodro Rosana Mabel  suficiente que el antecedente sea verdadero, para que el consecuente también sea verdadero. De aquí que una proposición compuesta en la que el conectivo es el condicional, será falsa si siendo verdadero el antecedente, es falso el consecuente. La proposición será verdadera en los demás casos, en los que no ocurre que el antecedente es verdadero y el consecuente falso. La tabla de verdad de la implicación es, entonces: 𝒑 𝒒 𝒑⇒𝒒 𝑽 𝑽 𝑽 𝑽 𝑭 𝑭 𝑭 𝑽 𝑽 𝑭 𝑭 𝑽 Nota: la implicación tiene una importancia relevante en matemática pues muchas de sus propiedades o teoremas están enunciadas en función de la misma. Y es por ello que los métodos de demostración están basados en ella. Distintas formas de leer una implicación: Existen diferentes maneras de enunciar una implicación. Todas las afirmaciones siguientes significan lo mismo: 𝑝⇒𝑞 Si 𝑝 entonces 𝑞 𝑝 es suficiente para 𝑞 𝑞 es necesario para 𝑝 𝑞 si 𝑝 𝑝 solo si 𝑞 Ejemplo 7: Sean las siguientes proposiciones 𝑝: 𝐿𝑎 𝑠𝑢𝑚𝑎 𝑑𝑒 𝑙𝑎𝑠 𝑐𝑖𝑓𝑟𝑎𝑠 𝑑𝑒 426 𝑒𝑠 𝑚ú𝑙𝑡𝑖𝑝𝑙𝑜 𝑑𝑒 3 𝑞: 426 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 3 La proposición compuesta condicional es: 𝒑 ⇒ 𝒒: "𝑆𝑖 𝑙𝑎 𝑠𝑢𝑚𝑎 𝑑𝑒 𝑙𝑎𝑠 𝑐𝑖𝑓𝑟𝑎𝑠 𝑑𝑒 426 𝑒𝑠 𝑚ú𝑙𝑡𝑖𝑝𝑙𝑜 𝑑𝑒 3 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 3" 6 Esp. Colodro Rosana Mabel  Ejemplo 8: Sea la proposición: 𝑆𝑖 28 𝑒𝑠 𝑝𝑎𝑟 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 2 Donde: antecedente → 𝑝: "28 𝑒𝑠 𝑝𝑎𝑟" consecuente → 𝑞: "28 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 2" La misma proposición también puede leerse: 1. 28 𝑒𝑠 𝑝𝑎𝑟 𝑖𝑚𝑝𝑙𝑖𝑐𝑎 𝑞𝑢𝑒 28 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 2 2. 28 𝑒𝑠 𝑝𝑎𝑟 𝑠𝑜𝑙𝑜 𝑠𝑖 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 2 3. 28 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 2 𝑠𝑖 𝑒𝑠 𝑝𝑎𝑟 4. 𝐸𝑠 𝑠𝑢𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑒 𝑞𝑢𝑒 28 𝑠𝑒𝑎 𝑝𝑎𝑟 𝑝𝑎𝑟𝑎 𝑞𝑢𝑒 𝑠𝑒𝑎 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 2 5. 𝐸𝑠 𝑛𝑒𝑐𝑒𝑠𝑎𝑟𝑖𝑜 𝑞𝑢𝑒 28 𝑠𝑒𝑎 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 2 𝑝𝑎𝑟𝑎 𝑞𝑢𝑒 𝑠𝑒𝑎 𝑝𝑎𝑟 Doble implicación o bicondicional o equivalencia Dadas dos proposiciones cualesquiera 𝑝 y 𝑞 la doble implicación bicondicional o equivalencia es la proposición 𝑝 ⇔ 𝑞 que se lee “𝑝 si y solo sí 𝑞 ”. Esta proposición significa que si 𝑝 es verdadera, entonces 𝑞 también es verdadera y si 𝑞 es verdadera, entonces 𝑝 también es verdadera. A continuación, definimos la tabla de valores de verdad de la doble implicación y además construimos la tabla de valores de verdad de la conjunción de dos implicaciones: 𝒑 𝒒 𝒑⇔𝒒 𝒑 𝒒 𝒑⇒𝒒 𝒒⇒𝒑 (𝒑 ⇒ 𝒒)˄(𝒒 ⇒ 𝒑) 𝑽 𝑽 𝑽 𝑽 𝑽 𝑽 𝑽 𝑽 𝑽 𝑭 𝑭 𝑽 𝑭 𝑭 𝑽 𝑭 𝑭 𝑽 𝑭 𝑭 𝑽 𝑽 𝑭 𝑭 𝑭 𝑭 𝑽 𝑭 𝑭 𝑽 𝑽 𝑽 Observemos que los valores de la última columna de ambas tablas son exactamente los mismos, como era de esperarse, ya que definimos la doble implicación como la conjunción de dos implicaciones que, según veremos en seguida, llamaremos directa y recíproca, la una de la otra. Cuando dos expresiones tienen la misma tabla de verdad, para los distintos valores asignados a sus letras, se dice que son lógicamente equivalentes. 7 Esp. Colodro Rosana Mabel  Ejemplo 9: Sea la proposición: 𝑇 𝑒𝑠 𝑒𝑞𝑢𝑖𝑙á𝑡𝑒𝑟𝑜 𝑠𝑖 𝑦 𝑠𝑜𝑙𝑜 𝑠𝑖 𝑇 𝑒𝑠 𝑒𝑞𝑢𝑖á𝑛𝑔𝑢𝑙𝑜 Es la doble implicación de las proposiciones: 𝑝: 𝑇 𝑒𝑠 𝑒𝑞𝑢𝑖𝑙á𝑡𝑒𝑟𝑜 𝑞: 𝑇 𝑒𝑠 𝑒𝑞𝑢𝑖á𝑛𝑔𝑢𝑙𝑜 En símbolos: 𝑝 ⇔ 𝑞 Las proposiciones compuestas pueden combinarse o conectarse con otras para formar proposiciones aún más complejas. Es claro que el valor de verdad de una proposición, por compleja que sea, depende de los valores de verdad de las proposiciones que las componen en sus formas más simples. Para hacer la tabla de verdad de una proposición asignamos una columna a cada proposición que interviene, sea ésta simple o compuesta, normalmente comenzando con las más simples y progresando en el orden de complejidad de las proposiciones componentes. El número de filas de la tabla queda dado por la potencia 𝟐𝒏 , donde 𝒏 es el número de proposiciones en la forma más simple que constituyen la proposición dada. Para asignar los valores de verdad a dichas proposiciones se procede de esta forma: la primera columna se llena asignando valores 𝑉 a la mitad de las filas y valores 𝐹 a la segunda mitad. La segunda columna se llena asignando valores 𝑉 a un cuarto de las filas, valores 𝐹 al segundo cuarto, valores 𝑉 al tercer cuarto y valores 𝐹 al último cuarto. La tercera columna se llena asignando valores 𝑉 a un octavo de las filas, valores 𝐹 al segundo octavo, valores 𝑉 al tercer octavo, etcétera. Así, se continúa hasta que terminen las columnas de las proposiciones más simples. Las columnas de las otras proposiciones se llenan a partir de las columnas de las proposiciones más simples que éstas. Tautología, contradicción y contingencia Las fórmulas cuyo valor de verdad es siempre verdadero cualquiera sea el conjunto de valores de sus proposiciones componentes, se llaman tautologías. Las fórmulas cuyo valor de verdad es siempre falso, se llaman contradicciones. Aquellas fórmulas que no son tautologías ni contradicciones se denominan contingencias. Ejemplo 10: Determina si las siguientes formulas son tautologías, contradicciones o contingencias: a) 𝒑˅~𝒑 b) 𝒒˄~𝒒 c) ~(~𝒑) 8 Esp. Colodro Rosana Mabel Solución: Para determinar lo solicitado se debe construir las correspondientes tablas de valores de verdad a). b). c). 𝑝 ~𝑝 𝒑˅~𝒑 𝑞 ~𝑞 𝒒˄~𝒒 𝑝 ~𝑝 ~(~𝒑) 𝑉 𝐹 𝑽 𝑉 𝐹 𝑭 𝑉 𝐹 𝑽 𝐹 𝑉 𝑽 𝐹 𝑉 𝑭 𝐹 𝑉 𝑭 Observamos que la primera fórmula es una tautología, la segunda es una contradicción y la tercera es una contingencia. Implicaciones asociadas Dada la implicación 𝑝 ⇒ 𝑞 , que llamaremos directa, se definen las siguientes implicaciones asociadas a la dada: 𝑪𝒐𝒏𝒕𝒓𝒂𝒓𝒊𝒂: ~𝑝 ⇒ ~𝑞 𝑹𝒆𝒄í𝒑𝒓𝒐𝒄𝒂: 𝑞 ⇒ 𝑝 𝑪𝒐𝒏𝒕𝒓𝒂𝒓𝒆𝒄í𝒑𝒓𝒐𝒄𝒂: ~𝑞 ⇒ ~𝑝 Mostraremos a continuación que la directa y la contrarecíproca son lógicamente equivalentes, para ello se construye la tabla de valores de verdad respectiva: 𝒑 𝒒 𝒑⇒𝒒 𝒑 𝒒 ~𝒒 ~𝒑 ~𝒒 ⇒ ~𝒑 𝑽 𝑽 𝑽 𝑽 𝑽 𝑭 𝑭 𝑽 𝑽 𝑭 𝑭 𝑽 𝑭 𝑽 𝑭 𝑭 𝑭 𝑽 𝑽 𝑭 𝑽 𝑭 𝑽 𝑽 𝑭 𝑭 𝑽 𝑭 𝑭 𝑽 𝑽 𝑽 Vemos que, para todas las combinaciones posibles de valores de verdad de 𝑝 y 𝑞 , las implicaciones directa y contrarecíproca tienen exactamente los mismos valores de verdad. Lo mismo ocurre si se realizan las tablas de verdad de la contraria y de la reciproca: ambas resultan equivalentes. Tarea: mostrar esta última afirmación. Ejemplo 11: Escribe las implicaciones asociadas a la dada y analice su valor de verdad “𝑆𝑖 2 𝑒𝑠 𝑟𝑎𝑐𝑖𝑜𝑛𝑎𝑙 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 0 𝑒𝑠 𝑝𝑎𝑟” 9 Esp. Colodro Rosana Mabel 𝑎𝑛𝑡𝑒𝑑𝑒𝑐𝑒𝑛𝑡𝑒 → 𝑝: 2 𝑒𝑠 𝑟𝑎𝑐𝑖𝑜𝑛𝑎𝑙 𝑐𝑜𝑛𝑠𝑒𝑐𝑢𝑒𝑛𝑡𝑒 → 𝑞: 0 𝑒𝑠 𝑝𝑎𝑟 Solución: 𝑅𝑒𝑐í𝑝𝑟𝑜𝑐𝑎(𝑞 ⇒ 𝑝): 𝑆𝑖 0 𝑒𝑠 𝑝𝑎𝑟 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 2 𝑒𝑠 𝑟𝑎𝑐𝑖𝑜𝑛𝑎𝑙 𝐶𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑎(~𝑝 ⇒ ~𝑞): 𝑆𝑖 2 𝑛𝑜 𝑒𝑠 𝑟𝑎𝑐𝑖𝑜𝑛𝑎𝑙 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 0 𝑛𝑜 𝑒𝑠 𝑝𝑎𝑟 𝐶𝑜𝑛𝑡𝑟𝑎𝑟𝑒𝑐í𝑝𝑟𝑜𝑐𝑎(~𝑞 ⇒ ~𝑝): 𝑆𝑖 0 𝑛𝑜 𝑒𝑠 𝑝𝑎𝑟 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 2 𝑛𝑜 𝑒𝑠 𝑟𝑎𝑐𝑖𝑜𝑛𝑎𝑙 𝑣൫𝑝 ⇒ 𝑞൯ = 𝑉 𝑣൫𝑞 ⇒ 𝑝൯ = 𝑉 𝑣൫~𝑝 ⇒ ~𝑞൯ = 𝑉 𝑣൫~𝑞 ⇒ ~𝑝൯ = 𝑉 Negación de una implicación Se observa, a través de la tabla que se mostrará a continuación, que las proposiciones ~(𝒑 ⇒ 𝒒) y 𝒑˄~𝒒 son lógicamente equivalentes 𝒑 𝒒 𝒑 ⇒ 𝒒 ~(𝒑 ⇒ 𝒒) ~𝒒 𝒑˄~𝒒 𝑽 𝑽 𝑽 𝑭 𝑭 𝑭 𝑽 𝑭 𝑭 𝑽 𝑽 𝑽 𝑭 𝑽 𝑽 𝑭 𝑭 𝑭 𝑭 𝑭 𝑽 𝑭 𝑽 𝑭 Observamos que la negación de una implicación no es una implicación sino la conjunción entre el antecedente y la negación del consecuente. Formas proposicionales y cuantificadores Una forma proposicional en una variable o indeterminada 𝑥 es toda oración en la que figura 𝑥 como sujeto u objeto directo, es decir es un enunciado abierto, que tiene la propiedad de convertirse en proposición al ser sustituida la variable 𝑥 por una constante especifica. Se denota así: 𝑝(𝑥), 𝑞(𝑥), 𝑟(𝑥), 𝑒𝑡𝑐 10 Esp. Colodro Rosana Mabel Ejemplo 12: Sea 𝑝(𝑥): 𝑥 + 5 = 12 Donde: o si reemplazamos 𝑥 por 3 la proposición es falsa o si reemplazamos 𝑥 por 7 la proposición es verdadera 𝑝(3): 3 + 5 = 12 es falsa 𝑝(7): 7 + 5 = 12 es verdadera Es decir, una forma proposicional se convierte en un proposición verdadera para algunos valores de 𝑥 y en una propocision falsa para otros valores de 𝑥. Cuantificadores Son expresiones “PARA TODO” o “ALGUNOS”, etc que se anteponen a una forma proposicional para transformarla en proposición. El cuantificador universal PARA TODO se denota por el símbolo: ∀  Si utilizamos el cuantificador universal podemos escribir la proposición de la siguiente manera: ∀𝑥 ∶ 𝑝 (𝑥) o bien ∀𝑥 , 𝑝 (𝑥) y se puede leer de las siguientes formas:  Para todo 𝑥, 𝑝 (𝑥)  Todo 𝑥, 𝑝 (𝑥)  Ningún 𝑥 cumple 𝑝 (𝑥) Ejemplo 13: ∀𝒙 ∈ 𝑹: 𝒙𝟐 ≥ 𝟎 Se lee: “Para todo 𝑥 perteneciente a los reales, 𝑥 al cuadrado es mayor o igual a cero” El cuantificador existencial ALGUNOS se denota por: ∃  Si utilizamos el cuantificador existencial podemos escribir ∃𝑥 ∶ 𝑝 (𝑥) o ∃𝑥 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑝 (𝑥) y se puede leer de las siguientes maneras:  Existe 𝑥 , tal que 𝑝 (𝑥)  Hay un 𝑥, tal que 𝑝 (𝑥)  Algún 𝑥 , tal que 𝑝 (𝑥)  Algunos 𝑥 cumplen con 𝑝 (𝑥) Ejemplo 14: ∃𝒙 ∈ 𝑹: 𝟐𝒙𝟐 − 𝟖 = 𝟎 Se lee: “Existe algún 𝑥 perteneciente a los reales tal que 2 por 𝑥 al cuadrado menos 8 es igual a cero” 11 Esp. Colodro Rosana Mabel Negación de los cuantificadores Veremos ahora la negación de proposiciones que contienen cuantificadores, la negación de dichas proposiciones se realiza negando la proposición 𝑝(𝑥) y cambiando el cuantificador universal por el cuantificador existencial, o viceversa. Así: ~ ቀ∀𝑥 ∶ 𝑝 (𝑥 )ቁ ⇔ ∃𝑥 ∶ ~𝑝 (𝑥) ~ ቀ∃𝑥 ∶ 𝑝 (𝑥 )ቁ ⇔ ∀𝑥 ∶ ~𝑝 (𝑥) Observación: cuando hablamos de negar un cuantificador, cometemos un abuso de lenguaje, porque lo que se niega es la proposición obtenida cuando a la forma proposicional le anteponemos un cuantificador. Métodos de demostración En matemáticas no se acepta una proposición como verdadera hasta que se construye su demostración formal, aunque la proposición sea válida para un número finito de casos no significa que sea válida para todo el universo. El problema de la construcción de una demostración consiste en preparar una serie de pasos que conduzcan a la proposición deseada. No hay caminos automáticos para hacerlo, es algo que se adquiere con la práctica. Es decir, a demostrar se aprende demostrando, no hay algoritmos de demostración, solo métodos generales, cuyo conocimiento nos puede servir para realizar una demostración. Como los teoremas matemáticos tienen generalmente formas de implicaciones, vamos a ver los métodos de demostrar implicaciones. Los métodos de demostración que vamos a estudiar aquí son los siguientes: Método directo de demostración Métodos indirectos de demostración:  por reducción al absurdo  por contrarecíproca Método del contraejemplo Detallaremos a continuación cada uno de ellos: Método directo(𝑝 ⇒ 𝑞 ) Este método es aplicado cuando se desea mostrar la veracidad del consecuente 𝑞, a partir de una proposición que es considerada como verdadera. La tabla de verdad de la implicación muestra que, si queremos demostrar la veracidad de 12 Esp. Colodro Rosana Mabel  𝑝 ⇒ 𝑞, es suficiente con demostrar que 𝑞 es verdadera siempre que 𝑝 lo sea, pues se ve que 𝑝 ⇒ 𝑞 siempre es verdadera cuando 𝑝 es falsa. Ejemplo 15: Demuestra por el método directo la siguiente implicación: “𝑆𝑖 𝑎 𝑦 𝑏 𝑠𝑜𝑛 𝑛ú𝑚𝑒𝑟𝑜𝑠 𝑝𝑎𝑟𝑒𝑠 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑎 + 𝑏 𝑒𝑠 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑎𝑟” Demostración: 𝑎 y 𝑏 𝑠𝑜𝑛 𝑛ú𝑚𝑒𝑟𝑜𝑠 𝑝𝑎𝑟𝑒𝑠 por hipótesis 𝑎 = 2𝑛, 𝑛 ∈ 𝑍 por def.de número par 𝑏 = 2𝑘, 𝑘 ∈ 𝑍 por def.de número par 𝑎 + 𝑏 = 2𝑛 + 2𝑘 ley uniforme de la suma 𝑎 + 𝑏 = 2(𝑛 + 𝑘), 𝑛 + 𝑘 ∈ 𝑍 prop. distributiva del producto 𝑎 + 𝑏 𝑒𝑠 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑎𝑟 por def. de número par 𝑐. 𝑞. 𝑑 Método Indirecto  Por contrarecíproca La siguiente equivalencia (𝒑 ⇒ 𝒒) ⇔ (~𝒒 ⇒ ~𝒑) da lugar a una variante del método directo, que se utiliza mucho en matemáticas y es conocido como método del contrarecíproco. Este método puede resumirse así: supongamos que se quiere demostrar que una proposición específica es teorema o propiedad y al intentar su demostración por el método directo no logramos obtener la conclusión deseada. Se procede entonces a demostrar por el método directo su contrarecíproca, si se consigue este objetivo entonces queda establecida la validez de 𝑝 ⇒ 𝑞 al hacer sustitución por equivalencia. Ejemplo 16: Demuestra el siguiente teorema: “𝑆𝑖 𝑒𝑙 ⏟ 𝑐𝑢𝑎𝑑𝑟𝑎𝑑𝑜 𝑑𝑒 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑒𝑠 𝑖𝑚𝑝𝑎𝑟 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 ⏟ 𝑒𝑙 𝑛ú𝑚𝑒𝑟𝑜 𝑒𝑠 𝑖𝑚𝑝𝑎𝑟” 𝑥2 𝑥 Solución: Si se emplea el método directo, se tiene: 𝑥 2 es impar por hipótesis 𝑥 2 = 2𝑛 + 1, 𝑛 ∈ 𝑍 por def. de número par 𝑥 = √2𝑛 + 1 Pero, ¿qué podemos decir de √2𝑛 + 1? No podemos decir que este número es par ni tampoco que es impar. Esta imposibilidad de obtener la conclusión buscada nos lleva a cambiar la estrategia. 13 Esp. Colodro Rosana Mabel  Procedamos ahora a demostrar su contrarrecíproco por el método directo. El enunciado del contrarecíproco corresponde a: 𝑆𝑖 𝑥 𝑒𝑠 𝑝𝑎𝑟 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑥 2 𝑒𝑠 𝑝𝑎𝑟 Demostración: 𝑥 es un número par por hipótesis 𝑥 = 2𝑛, 𝑛 ∈ 𝑍 por def. de numero par 𝑥 2 = (2𝑛)2 = 4𝑛2 = 2(2𝑛2 ), 𝑘 = 2𝑛2 ∈ 𝑍 por prop. uniforme y Asociatividad del producto 𝑥 2 = 2𝑘 por def. de número par Por tanto 𝑥 2 es par 𝑐. 𝑞. 𝑑. Como se ha demostrado la contrarecíproca de la proposición dada, entonces se concluye que la misma es verdadera.  Método por reducción al absurdo Para demostrar una proposición de la forma 𝑝 ⇒ 𝑞 mediante la técnica por reducción al absurdo, es necesario poder construir una contradicción en el cuerpo de la demostración. Recordemos que una contradicción es una proposición que resulta siempre falsa, independientemente del valor de verdad de las proposiciones que la componen. Esta contradicción puede lograrse de varias formas. Por ejemplo:  Un número que sea positivo y negativo a la vez  Un número real que sea la raíz cuadrada de un número negativo Este método consiste en negar la implicación dada, es decir suponer la verdad de 𝑝˄~𝑞 (negación de 𝑝 ⇒ 𝑞) y analizar las consecuencias de dicha negación. Si llegamos a obtener una contradicción es decir si mostramos que 𝑝˄~𝑞 es falsa, diremos 𝑝 ⇒ 𝑞 es verdadera. Este método también se enuncia del siguiente modo: “Para demostrar que 𝑝 ⇒ 𝑞 es verdadera, se construye un absurdo suponiendo que la tesis 𝑞 es falsa y usando la veracidad de la hipótesis 𝑝” Ejemplo 17: Demostrar que “𝑆𝑖 √2 𝑒𝑠 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑟𝑒𝑎𝑙 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 √2 𝑒𝑠 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑖𝑟𝑟𝑎𝑐𝑖𝑜𝑛𝑎𝑙” 14 Esp. Colodro Rosana Mabel  Solución: Supongamos por reducción al absurdo que √2 es un número racional(negación de la tesis), entonces escribimos: 𝑎 √2 = 𝑐𝑜𝑛 𝑎 𝑦 𝑏 𝑝𝑟𝑖𝑚𝑜𝑠 𝑒𝑛𝑡𝑟𝑒 𝑠𝑖 𝑏 Elevando al cuadrado a ambos miembros 𝑎2 2= 2 𝑏 Entonces 2𝑏 2 = 𝑎2 Sabemos que 𝑎2 es par, por definición de número par. Luego 𝑎 también es par, es decir: 𝑎 = 2𝑐 Sustituimos en la formula anterior, tenemos: 2𝑏 2 = 𝑎2 = (2𝑐)2 = 4𝑐 2 2𝑏 2 = 4𝑐 2 Simplificando 𝑏 2 = 2𝑐 2 De esta última igualdad concluimos que 𝑏 2 es un número par, es decir 𝑏 es par al igual que 𝑎 lo cual CONTRADICE que 𝑎 y 𝑏 son primos entre si Con lo cual la hipótesis de partida: √2 es un número racional es FALSA , es decir √2 es un número irracional 𝑐. 𝑞. 𝑑. Método del contraejemplo Este método se aplica de manera muy particular para demostrar la falsedad de proposiciones cuya hipótesis está construida mediante un “cuantificador universal”. Esto es, se aplica para demostrar la falsedad de una proposición que tenga una conclusión referida para “todos los elementos de un cierto conjunto”. Ejemplo 18: 𝑇𝑜𝑑𝑜 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑟𝑖𝑚𝑜 𝑒𝑠 𝑖𝑚𝑝𝑎𝑟. Demostración: Para demostrar que esta generalización es falsa; debe presentarse un número que sea primo y no sea impar. Contraejemplo: 2 es un número primo y no es impar 15 Esp. Colodro Rosana Mabel Bibliografía 1. Rojo Armando. (2006). Álgebra I. Editorial El Ateneo. 2. Zill D., Dewar J. (2012). Álgebra, trigonometría y geometría analítica. Editorial Mc Graw Hill. 3. Diaz E., Zapata L., Puga C. (2008). Notas de Introducción a la Matemática. UNSa. 16 Esp. Colodro Rosana Mabel