Teoría Unidad 1 - Cálculo Prop. y Predicados (2024) PDF

LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA Unidad 1. CÁLCULO PROPOSICIONAL Y DE PREDICADOS Proposiciones. Conectivos lógicos. Operaciones lógicas. Tautología, Contradicciones y Conti...

LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA Unidad 1. CÁLCULO PROPOSICIONAL Y DE PREDICADOS Proposiciones. Conectivos lógicos. Operaciones lógicas. Tautología, Contradicciones y Contingencias. Equivalencia Lógica y Principales Leyes lógicas. Implicaciones lógicas. Razonamientos. Validez de un razonamiento. Principales Reglas de Inferencia. Tipos de demostraciones para validar un razonamiento. Lógica de Primer Orden. Cuantificadores. Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 5 1.1 Introducción La lógica surge desde el momento en que el hombre comienza a observar, experimentar, deducir y razonar sobre los fenómenos naturales de los cuales es testigo. Y es que, en general, se aplica lógica en los quehaceres diarios, ya que cualquier trabajo que se realiza tiene un procedimiento lógico. Lógica es la rama de la Matemática que analiza la forma en la que razonamos. Es la disciplina que por medio de reglas y estrategias determina la validez o no de un argumento. Manejar correctamente los conceptos de lógica es primordial en informática. Su importancia en los diseños curriculares de las carreras de las ciencias de la computación va tomando cuerpo propio debido a sus aplicaciones prácticas en contextos específicos tales como lenguajes de programación, ingeniería de software, bases de datos, inteligencia artificial, entre otros. También desempeña un papel central en muchas otras ciencias, y es ampliamente aplicada por ejemplo en la Filosofía, pues una frase puede tener diferentes interpretaciones y la lógica permite saber el significado correcto; en las Ciencias Física y Naturales, para sacar conclusiones de experimentos; en Estadística y Matemática, para demostrar teoremas e inferir resultados que luego podrán ser aplicados en investigaciones. Por ello, es necesario un correcto uso del lenguaje a los efectos de evitar toda ambigüedad que muchas veces se presenta en el lenguaje corriente, motivo por el cual la Matemática usa el llamado “lenguaje simbólico” mediante la utilización de una colección de significantes (símbolos) que cobran significado en el contexto comunicacional en el que se esté trabajando. En Lógica, la formalización del “lenguaje lógico” nos permite examinar más fácilmente las estructuras del pensamiento y aplicando sus leyes determinar si nuestro pensamiento es correcto. Es por ello que la lógica proposicional es la parte de la Lógica que estudia las formas en que se relacionan unas proposiciones con otras, sin atender a su contenido, y sobre todo, las relaciones que se da entre las proposiciones que integran un razonamiento. Pero ¿Qué es una proposición?  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA 1.2 Proposición  Definición Una proposición es toda oración afirmativa completa de la cual se puede decir que es verdadera o falsa, pero no ambas.  Ejemplos Las siguientes oraciones son proposiciones: “La subrutina S ha terminado” “Einstein fue un físico teórico” “La letra o tiene dos significados” “Marcela ganó en las olimpíadas matemáticas” “10 es número primo” “Hayelem no estudia informática, pero si abogacía” “Los elementos del lenguaje L son las palabras de L” “La lógica se centra en las relaciones entre los enunciados” También son proposiciones todas las leyes científicas, las fórmulas matemáticas y esquemas lógicos, donde se usan literales que tienen sentido en un universo dado. Son proposiciones 𝐸 = 𝑚𝑐 2 y 𝑎2 − 𝑏 2 = (𝑎 + 𝑏)(𝑎 − 𝑏) donde los símbolos intervinientes toman valores de un dominio determinado No son proposiciones las opiniones, proverbios, refranes, modismos, suposiciones o juicios de valor, las oraciones interrogativas, las exhortativas o imperativas, las desiderativas; las exclamativas o admirativas y los enunciados abiertos. En efecto, no son proposiciones porque de ninguna de ellas se puede afirmar verdadero o falso Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 7 sin incurrir en ambigüedades.  Ejemplos Las siguientes expresiones lingüísticas no son proposiciones: i) ‘La concatenación de w con z’ ii) ‘La raíz cúbica de una melodía es igual a una fantasía’ iii) ‘No hay mal que por bien no venga’ iv) ‘¿Qué es la Lógica?’ v) ‘¡Imprime ya!’ vi) ‘Me gustaría que prenda la computadora’ vii) ‘Prolog es bueno’ viii) ‘Eduardo es hermoso’  Observaciones ▪ Un enunciado del tipo “x es un numero entero” no es proposición a pesar de ser una afirmación. No posee valor de verdad. Más adelante se verá este tipo de enunciados, donde pueden aparecer una o más variables sin su especificación. ▪ Hay oraciones distintas en cuanto a su formación pero que tienen el mismo significado, ambas constituyen la misma proposición. Por ejemplo: “El decano de la FRT-UTN visita al Rector de la UTN” “El Rector de la UTN es visitado por el decano de la FRT-UTN” Notación Se utilizan para designar proposiciones, o bien letras mayúsculas o bien letras minúsculas, pero en este texto se usarán 𝑝, 𝑞, 𝑟, … Estas letras son variables de enunciado, por lo que mientras no se les asigne una proposición en particular, pueden representar a cualquiera. Es por ello que a 𝑝, 𝑞, 𝑟, … se les denomina variables proposicionales. Valor de verdad A la cualidad de una proposición de ser verdadera o falsa, se la denomina valor de  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA verdad y se indica: 𝑝 = V si 𝑝 es verdadera y 𝑝 = F si 𝑝 es falsa. “V” y “F” representan los valores de verdad verdadero y falso, respectivamente y se los denomina constantes proposicionales. Siguiendo la notación utilizada en las ciencias de la computación, también se puede representar “verdadero” por el símbolo “1” y “falso” por 0. Ésta es la notación que usaremos más frecuentemente.  Ejemplos Sean las proposiciones 𝑝: “Ayer dejó de funcionar la PC de Gabriel” 𝑞: “2 + 3 = 5” 𝑟: “3 es número primo” 𝑠: “El rector de la UTN fue presidente de Argentina” El valor de verdad de 𝑝 dependerá del día, lugar o momento en que es enunciada, pero una vez fijados estos, el valor de verdad de 𝑝 es único y el mismo para todos. El valor de verdad de 𝑞 y 𝑟 es verdadero, y el de 𝑠 es falso, por lo tanto, los valores de verdad de 𝑞, 𝑟 y 𝑠 son constantes: 𝑞 = 1, 𝑟 = 1 y 𝑠 = 0 Proposición Simple  Definición Una proposición es simple, primitiva o atómica cuando no hay manera de descomponerla en partes que sean a su vez también proposiciones y cuando no es negación de una afirmación. Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 9  Ejemplos Las siguientes oraciones son proposiciones simples: i) “Evangelina programa en C++” ii) “Los ordenadores de 64 bits tienen capacidad de hacer más en menos tiempo” iii) “Lógica es una rama de la Matemática” iv) “La PC de Zoe tiene poca memoria” v) “Euclides y Boole son condiscípulos” vi) “Marcelo e Imanol son hermanos” Son proposiciones simples ya que carecen del adverbio de la negación “no” o sus equivalentes y no se las puede separar en dos proposiciones simples porque carecerían de significado en caso de hacerlo. En el ejemplo v) y vi) la palabra “y” tiene carácter relacional. No se puede descomponer en más de una proposición. Conectivos lógicos Los siguientes enunciados vinculan a una o más proposiciones simples: i) “3 no es par” ii) “Python o Prolog o C++ son lenguajes de programación” iii) “La adición y la multiplicación de números naturales son operaciones asociativas y conmutativas” iv) “Hace unos años se consideraba al computador como una gran ‘calculadora’, pero hoy se habla de sus logros intelectuales” v) “Si la inferencia es inductiva entonces es una inferencia en términos de probabilidad” vi) “8 es divisible por dos si y solo si es par”  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA Cuando se vinculan o combinan proposiciones simples a través de palabras que funcionan como nexos: no, o, y, pero, si...entonces, …si y solo si …., se obtienen otras proposiciones, llamadas proposiciones compuestas. El vínculo se establece a través de los llamados conectivos lógicos.  Definición Los conectivos u operadores lógicos son símbolos o palabras que operan sobre una o más proposiciones generando una nueva proposición. En general los operadores se clasifican en binarios o unarios. - Un operador binario tiene dos alcances: uno hacia la izquierda y otro hacia la derecha, es decir afecta a dos proposiciones. - El operador unario tiene un único alcance que en general se expresa hacia la derecha, es decir afecta a una sola proposición. A continuación, se presentan los principales conectivos lógicos: Nombre Símbolo Se leen Negación  𝑝 , 𝑝 No 𝑝 Conjunción 𝑝 𝑞 𝑝y𝑞 Disyunción inclusiva 𝑝 𝑞 𝑝 o 𝑞 , con sentido incluyente Disyunción exclusiva 𝑝 𝑞 𝑝 o 𝑞 , con sentido excluyente Condicional 𝑝 →𝑞 Si 𝑝 entonces 𝑞 Bicondicional 𝑝 𝑞 𝑝 si y sólo si 𝑞 Tabla 1.1. Conectivos, significado y operación asociada. Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 11 Las nuevas proposiciones así formadas, una o más variables ligadas con al menos un conectivo lógico, reciben el nombre de proposición compuesta y procedemos a analizarlas con más detalle en la siguiente sección. Proposiciones Compuestas  Definición Una proposición es compuesta cuando se obtiene a partir de proposiciones simples ligadas por uno o más conectivos lógicos.  Ejemplos i) “Luis terminó la escuela secundaria y además obtuvo una beca de estudio, entonces se matriculó para cursar una carrera universitaria”. Esta proposición compuesta está formada por tres proposiciones simples y dos conectivos lógicos. Su fórmula sería del tipo: (𝑝 ∧ 𝑞) → 𝑟 ii) “Anoche fuimos al cine y a cenar, pero no viajamos en taxi”. Esta proposición compuesta está formada por tres proposiciones simples y tres conectivos lógicos. Su fórmula sería del tipo: (𝑝 ∧ 𝑞) ∧ ~𝑟 Tabla de Verdad de una Proposición Compuesta  Definición Una tabla de verdad es un arreglo que refleja los posibles valores de verdad de una proposición compuesta a partir de todas las combinaciones posibles de los valores de verdad de las proposiciones simples intervinientes. Si en la proposición compuesta intervienen 𝑛 variables proposicionales entonces la tabla tendrá 2𝑛 renglones. En la Figura 1.1 se representa, a través de un diagrama de árbol, todas las combinaciones posibles de los valores de verdad para dos y tres variables proposicionales. Se representa al valor verdadero con V o con el símbolo 1, y al valor falso con F o con el símbolo 0.  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA Fig.1.1. Valores de verdad para 2 y 3 proposiciones. A continuación, se presenta un análisis exhaustivo de las proposiciones compuestas en las que interviene un único conectivo, considerando los valores de verdad que tomarían y las distintas formas de lectura Negación  Definición Si 𝑝 es una proposición simple, su negación se simboliza con ¬𝑝 y se lee “No 𝑝”. La proposición compuesta ¬𝑝 toma el valor de verdad contrario al valor de verdad de la proposición 𝑝. Esto se refleja en la siguiente tabla de verdad: 𝑝 𝑝 0 1 1 0 Tabla 1.2. Valores de verdad de la Negación. Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 13  Observaciones Otras maneras de leer ¬ 𝑝: “No es cierto que 𝑝”, “Es falso que 𝑝”. “No ocurre 𝑝 “ Ejemplo Sea la proposición 𝑝: “100 es par”, su negación ¬𝑝 puede expresarse como: ✓ “100 no es par” ✓ “No es cierto que 100 sea par” ✓ “Es falso que 100 es par” Conjunción o Producto Lógico  Definición Dadas dos proposiciones cualesquiera 𝑝 y 𝑞, la conjunción de 𝑝 y 𝑞 es la proposición compuesta que se denota simbólicamente “ 𝑝  𝑞” y se lee “𝑝 y 𝑞”, que sólo es verdadera si las dos proposiciones 𝑝 y 𝑞 son verdaderas. En todo otro caso es falsa. La tabla de verdad correspondiente es la tabla 1.3: 𝑝 𝑞 𝑝𝑞 0 0 0 0 1 0 1 0 0 1 1 1 Tabla 1.3. Tabla de verdad para la conjunción  Observaciones Las proposiciones conjuntivas llevan “y”, o sus formas equivalentes como “pero”, “aunque”, “e”, “aun”, “tanto…como…”, “sin embargo”, “además”, etc. La expresión “ni” significa “y no”. Se puede tener la conjunción de dos o más proposiciones: 𝑝  𝑞  𝑟  𝑠… El pasaje de operar con dos proposiciones y luego pasar a un número finito se resuelve introduciendo el uso de "paréntesis" que son los símbolos de  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA puntuación de la lógica. Por ejemplo: (((𝑝 ∧ 𝑞) ∧ 𝑟) ∧ 𝑠), o bien sin considerar los paréntesis y cuando los conectivos son todos iguales, operar de izquierda a derecha para determinar el valor de verdad de esta proposición compuesta.  Ejemplos i) “3 es un número impar y 7 es un número primo” Se trata de la conjunción de las proposiciones: 𝑝: “3 es un número impar” y 𝑞: “7 es un número primo”. Por ser 𝑝 = 1 y 𝑞 = 1, se tiene que ( 𝑝  𝑞) = 1 ii) “Ignacio juega futbol, rugby y vóley” Se trata de la conjunción de las proposiciones 𝑝: “Ignacio juega futbol”; 𝑞: “Ignacio juega rugby” y 𝑟: “Ignacio juega vóley” La proposición dada, en forma simbólica es: 𝑝  𝑞  𝑟. Será falsa si alguna proposición o todas son falsas. Disyunción Inclusiva o Suma Lógica  Definición Dadas dos proposiciones 𝑝 y 𝑞, la expresión simbólica 𝑝  𝑞 denota la disyunción entre 𝑝 y 𝑞. Se lee “𝑝 o 𝑞” la cual es falsa si las dos proposiciones componentes son falsas. En todo otro caso es verdadera. El sentido de la disyunción “o” es incluyente, lo cual significa que para ser verdadera se necesita que al menos una de ellas sea verdadera, pudiendo ocurrir que ambas lo sean. Será falsa solo en el caso en que ambas sean falsas Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 15 La tabla de verdad correspondiente es la tabla 1.4: 𝑝 𝑞 𝑝𝑞 0 0 0 0 1 1 1 0 1 1 1 1 Tabla 1.4. Tabla de verdad para la disyunción incluyente.  Observaciones Otra forma de leer 𝑝  𝑞: “𝑝 y/o 𝑞”, “𝑝 o 𝑞 o ambas” Se puede tener disyunción entre dos o más proposiciones: 𝑝  𝑞  𝑟  𝑠 que, como la conjunción, para evaluarla se opera de izquierda a derecha o respetando paréntesis si hubiera.  Ejemplos i) La frase “Hoy llueve o es un día de sol” representa una disyunción incluyente entre proposiciones simples, su forma simbólica es: 𝑝  𝑞 , considerando 𝑝: “Hoy llueve” y 𝑞: “Hoy es un día de sol”. ii) En “5 es mayor a 2 o 5 es mayor a 4” , si tomamos 𝑞: “5 es mayor a 2” y 𝑟: “5 es mayor a 4”, la expresión dada se simboliza con la fórmula 𝑞  𝑟 Disyunción Excluyente  Definición Dadas dos proposiciones 𝑝 y 𝑞 la expresión simbólica 𝑝  𝑞 denota la disyunción excluyente entre 𝑝 y 𝑞, y se lee “𝑝 o 𝑞, pero no ambas”, siendo una proposición compuesta verdadera si exactamente una de las proposiciones componentes es verdadera. Por ello decimos que esta “o” tiene sentido excluyente. Es falso que sean verdaderas simultáneamente las dos proposiciones que intervienen. La tabla de verdad correspondiente es la tabla 1.5:  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA 𝑝 𝑞 𝑝 𝑞 0 0 0 0 1 1 1 0 1 1 1 0 Tabla 1.5. Tabla de verdad para la disyunción excluyente.  Observaciones 𝑝  𝑞: se lee también como “o bien 𝑝 o bien 𝑞”, “o 𝑝 o 𝑞” o “ 𝑝 o 𝑞 pero no ambas”  Ejemplos i) “El rector se elige por consulta popular o por una comisión del consejo” En esta proposición compuesta es el resultado de una disyunción excluyente de las proposiciones: 𝑝: “El rector se elige por consulta popular” y 𝑞: “El rector se elige por una comisión del consejo” Observe que 𝑝 y 𝑞 no pueden ser simultáneamente verdaderas. Luego, la proposición compuesta expresada simbólicamente es: 𝑝  𝑞. ii) “O el número 2 es par o impar” Considerando 𝑟: “El número 2 es par”; 𝑡: “El número 2 es impar” , la frase dada es el resultado de la disyunción excluyente entre 𝑟 y 𝑡. Simbólicamente la proposición se la expresa como: 𝑟  𝑡 Condicional  Definición Dadas dos proposiciones 𝑝 y 𝑞, la expresión simbólica 𝑝 → 𝑞 denota la condicional Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 17 de 𝑝 a 𝑞. Se lee “Si 𝑝 entonces 𝑞”. Esta proposición compuesta sólo es falsa cuando el antecedente es verdadero y el consecuente es falso. En cualquier otro caso es verdadera. A 𝑝 se le llama antecedente y a 𝑞 consecuente del condicional. La tabla de verdad correspondiente es la tabla 1.6: 𝑝 𝑞 𝑝⟶𝑞 0 0 1 0 1 1 1 0 0 1 1 1 Tabla 1.6. Tabla de verdad del Condicional.  Observaciones El condicional 𝑝 → 𝑞 puede ser leído también de las siguientes maneras: - 𝑞 si 𝑝 - Si 𝑝, 𝑞 - Sólo si 𝑞 , 𝑝 - 𝑝 sólo si 𝑞 - 𝑞 es necesario para 𝑝 - 𝑝 es suficiente para 𝑞 - Cuando 𝑝, 𝑞 - 𝑝 implica 𝑞  Ejemplo “Si Luis circula en moto, entonces usa casco”, es una proposición compuesta del tipo 𝑝 → 𝑞 donde 𝑝: “Luis circula en moto” y 𝑞: “Luis usa casco”. La misma proposición también puede leerse: - “Si Luis circula en moto, usa casco” - “Que Luis circule en moto implica que usa casco” - “Luis circula en moto, solo si usa casco” - “Solo si Luis usa casco, circula en moto” - “Es suficiente que Luis circule en moto para que use casco” - “Es necesario que Luis use casco cuando circule en moto”  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA Bicondicional  Definición Dadas dos proposiciones 𝑝 y 𝑞 , la expresión simbólica 𝑝 ↔ 𝑞 denota al bicondicional entre 𝑝 y 𝑞 , la cual se lee “𝑝 si y solo si 𝑞” y sólo es verdadera en el caso en que ambas proposiciones tengan el mismo valor de verdad, en cualquier otro caso es falsa. La tabla de verdad correspondiente es la tabla 1.7: 𝑝 𝑞 𝑝⟷𝑞 0 0 1 0 1 0 1 0 0 1 1 1 Tabla 1.7. Tabla de verdad del Bicondicional.  Observaciones ▪ 𝑝 ⟷ 𝑞 puede leerse también como: “𝑝 es necesario y suficiente para 𝑞”; “𝑝 siempre y cuando 𝑞”. ▪ “𝑝 si y solo si 𝑞” se abrevia del siguiente modo: “𝑝 sii 𝑞”.  Ejemplos i) “T es equilátero si y sólo si T es equiángulo”, es la doble implicación de las proposiciones, 𝑝: ‘T es equilátero’ y 𝑞: ‘T es equiángulo’, es decir 𝑝 ⟷ 𝑞. ii) “𝑎2 es par siempre y cuando 𝑎 es par”. Expresión que se escribe simbólicamente como: 𝑞 ⟷ 𝑟, donde 𝑞: “𝑎2 es par“ y 𝑟: “𝑎 es par”. Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 19 Actividad 1.1 a) Indicar cuáles de las siguientes expresiones son proposiciones y en los casos afirmativos, clasificar en simple o compuesta, luego expresar simbólicamente i) “No es cierto que 8 es un número par” ii) “6 es múltiplo de 3” iii) “7 es impar y trae suerte” iv) “Si 10 es múltiplo de 2, entonces 10 es par” v) “15 es impar si y solo si 15 es múltiplo de 3 o de 7” b) Sean las proposiciones 𝑝: “Luis circula en moto” y 𝑞: “Luis usa casco”; dar la interpretación coloquial y el valor de verdad, de las fórmulas lógicas: “¬𝑝” , “𝑝 ∧ 𝑞”, “ 𝑝 ∨ 𝑞” , “𝑝 ∨ 𝑞” , “𝑝 → 𝑞” y “𝑝 ↔ 𝑞” 1.3 Expresión Lógica  Definición Una Expresión Lógica es toda proposición lógica ya sea simple o compuesta. Se las denotará con letras mayúsculas: 𝐴, 𝐵, 𝐶, …, etc., por ejemplo: 𝐴∶ 𝑝 𝐵: 𝑝  𝑞 𝐶: 𝑝 → 𝑞 → 𝑟 𝐷: 𝑝 → (𝑞  𝑟) A la hora de confeccionar la tabla de verdad de una expresión lógica con dos o más conectivos lógicos se debe tener en cuenta la presencia de paréntesis para determinar el orden de los cálculos; y en el caso de una expresión sin ellos hay que respetar las prioridades de los conectivos y determinar cuál es el principal. ¿Pero cuál es la prioridad o jerarquía de los conectivos?  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA Es el orden en el que se resuelve una expresión lógica sin paréntesis y está dado por la siguiente regla de prioridad: 1°. Si los conectivos son los mismos, se resuelve de izquierda a derecha, 2°. La prioridad de mayor a menor está dada por el siguiente orden de izquierda a derecha: , , , →,  Conectivo Principal  Definición Se define conectivo principal de una expresión lógica al conectivo que nos da el valor de verdad resultante.  Ejemplos i) En una expresión lógica completamente entre paréntesis como ( ( ¬ ( p  q ) ⟶ r )  q ), es claro quién es el conectivo principal (). ii) En las siguientes expresiones lógicas, se señala el conectivo principal (cp): ¬(𝑝  𝑞) ; (𝑝  𝑞)  𝑠 → 𝑝 ; 𝑝 → 𝑞 → ((𝑟 𝑝) ¬𝑞) cp cp cp iii) El conectivo principal de la expresión lógica: p  (q → q)  p es el bicondicional ( ↔ ); y su correspondiente tabla de verdad es la tabla 1.8: 𝑝 ↔ (𝑞 → 𝑝)  𝑝 1 0 1 0 0 0 1 1 1 0 1 0 1 1 Tabla 1.8. Tabla de verdad para 0 1 1 1 1 0 0 p  (q → q)  p. 0 1 0 1 1 0 0 Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 21 Actividad 1.2 i) Determinar el conectivo principal en las siguientes afirmaciones a) 𝑝  𝑞  ¬ 𝑟 b) ¬ 𝑝  𝑞 ⟶ 𝑟 c) 𝑝  𝑞 ⟷ 𝑟  ¬ 𝑠 ii) Confeccionar la tabla de verdad de 𝑞 ∧ (¬ 𝑟 → 𝑝) y determinar en cuál renglón de la tabla toma el valor verdadero. Para esos casos dar los valores de las variables 𝑝, 𝑞 y 𝑟 correspondientes. iii) Sin realizar la tabla de verdad determinar los valores de verdad de las proposiciones intervinientes sabiendo que: a) [𝑝  𝑞  𝑟 ] = 1 b) [(¬𝑝  𝐹)  𝑞 ] = 1 c) [(𝑝 ∧ 𝑞 ∧ 𝑟) → (𝑠 ∨ 𝑡)] = 0 1.4 Tautologías, Contradicciones y Contingencias  Definiciones Se llama Tautología a una proposición compuesta que es verdadera para todas las asignaciones de valores de verdad para sus proposiciones componentes. Si una proposición es falsa para todas las asignaciones se dice Contradicción y cuando no es tautología ni contradicción se dice Contingencia. Notación Con 𝑇 y 𝐹 se indica a cualquier tautología y a cualquier contradicción, respectivamente.  Ejemplos i) Las expresiones: 𝑝  𝑇 y 𝑝  ¬𝑝 son tautologías. ii) Son contradicciones las expresiones: 𝑝  𝐹, 𝑝 ¬𝑝. iii) Son contingencias las expresiones: 𝑝  𝑇 , 𝑝  𝐹 , 𝑝  𝑝 , 𝑝  𝑞.  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA Actividad 1.3 Determinar si la siguiente proposición compuesta es tautología, contradicción o contingencia: [𝑝 → (𝑞 → 𝑟) ]  [(𝑝 → 𝑞) → (𝑝 → 𝑟)] 1.5 Equivalencias Lógicas  Definición Se dice que dos expresiones lógicas cualesquiera A y B, son lógicamente equivalentes y se denota A ⇔ B (o A  B), cuando ambas expresiones tienen los mismos valores de verdad para cada una de las combinaciones posibles de los valores de verdad de las proposiciones simples intervinientes. Como consecuencia de esta definición se tiene que: A⇔B si y solo si A ⟷ B es tautología  Ejemplo Si 𝐴 = 𝑝  𝑞 y 𝐵 = 𝑞  𝑝 , entonces 𝑝  𝑞 ⇔ 𝑞  𝑝 pues 𝑝  𝑞 ↔ 𝑞  𝑝 es una tautología. Expresión lógica dual  Definición Sea A una expresión lógica tal que no contiene condicionales ni bicondicionales. Se llama expresión lógica dual de A, que se denota Ad, a la expresión que se obtiene de A al reemplazar cada ocurrencia de  por , y viceversa y cada ocurrencia de 𝑇 por F y viceversa. Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 23  Ejemplos Las siguientes expresiones son duales: a) ¬(𝑝  𝑞) y ¬(𝑝  𝑞) b) (𝑝  𝑞)  𝐹 y (𝑝  𝑞)  𝑇 ¿Por qué es importante el conocimiento de las expresiones duales? La respuesta está en la siguiente propiedad:  Propiedad de las expresiones duales Sean A y B dos expresiones lógicas y sean Ad y Bd sus correspondientes duales. Se tiene que A  B si y solo si Ad  Bd Esto significa que si se demuestra la equivalencia entre A y B no será necesario probar la equivalencia entre sus expresiones duales. Principales Leyes Lógicas Las Equivalencias Lógicas más simples son la base del Algebra Proposicional y se denominan Leyes Lógicas. Su estudio es tarea fundamental de la lógica de proposiciones, puesto que ellas constituyen un poderoso instrumento para el análisis de inferencias, que se verá más adelante. A continuación, se da el listado de las principales leyes lógicas las cuales se demuestran confeccionando sus tablas de verdad. Considerando que 𝑝, 𝑞 y 𝑟 son proposiciones simples cualesquiera, V es una proposición siempre verdadera y F una proposición siempre falsa se cumple que: ¬¬𝑝  𝑝 Ley de Doble Negación ¬(𝑝  𝑞)  ¬𝑝  ¬𝑞 ¬(𝑝  𝑞)  ¬ 𝑝  ¬ 𝑞 Leyes de Morgan  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA 𝑝𝑞 𝑞𝑝 𝑝𝑞𝑞𝑝 Leyes conmutativas (𝑝  𝑞)  𝑟  𝑝 (𝑞𝑟) (𝑝  𝑞)  𝑟  𝑝 (𝑞  𝑟) Leyes asociativas (𝑝𝑞)  𝑟 (𝑝𝑟)  (𝑞𝑟) (𝑝𝑞)  𝑟  (𝑝𝑟)  (𝑞𝑟) Leyes distributivas 𝑝𝑝  𝑝 𝑝𝑝  𝑝 Leyes de Idempotencia 𝑝 𝐹  𝑝 𝑝  𝑉 𝑝 Leyes de los Neutros 𝑝  ¬𝑝  𝑉 𝑝  ¬𝑝  𝐹 Leyes de los Inversos 𝑝  𝑉 𝑉 𝑝 𝐹  𝐹 Leyes de Dominación 𝑝  (𝑝  𝑞 )  𝑝 𝑝  (𝑝  𝑞 )  𝑝 Leyes de Absorción Tabla 1.9. Principales Leyes Lógicas. Las siguientes equivalencias, igualmente importantes, tienen que ver con el comportamiento de los conectivos condicional y bicondicional; ellas son: 𝑝  𝑞  (𝑝  ¬𝑞)  (𝑞  ¬ 𝑝) Ley de la disyunción excluyente (𝑝  𝑞 )  𝑟  𝑝  ( 𝑞  𝑟 ) Ley asociativa de la disyunción excluyente 𝑝 →𝑞  ¬𝑝 𝑞 Ley del condicional 𝑝 → 𝑞  ¬𝑞 → ¬ 𝑝 Ley del contrarrecíproco del condicional ¬ (𝑝 → 𝑞)  𝑝  ¬𝑞 Ley de la negación de la condicional 𝑝 ↔ 𝑞  (𝑝 → 𝑞 )  (𝑞 → 𝑝) Ley del bicondicional ¬(𝑝 ↔ 𝑞)  (𝑝  ¬𝑞) (𝑞  ¬ 𝑝) Ley de la Negación del bicondicional Tabla 1.10. Leyes lógicas vinculadas a los conectivos: , → y ↔. Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 25 Actividad 1.4 Usando tablas de verdad demostrar: i) Una de las leyes distributivas. ii) Una de las leyes de absorción. iii) La ley del contrarrecíproco. iv) La ley de la negación de la condicional. v) La ley asociativa de la disyunción excluyente. Uso de las leyes lógicas en la manipulación de las expresiones lógicas Las leyes lógicas se usan para: i) para demostrar otras equivalencias, especialmente donde intervienen muchas variables proposicionales, ii) para encontrar frases equivalentes, que transmitan el mismo mensaje y, por supuesto, conserven el valor de verdad, y iii) para demostrar la validez de un razonamiento. Actividad 1.5 a) Sin realizar tablas de verdad, demostrar las siguientes equivalencias lógicas usando leyes lógicas. Luego escribir la expresión dual, si es que existe. i) (¬𝑝  ¬ 𝑞  ¬𝑟)  (𝑝  𝑞  𝑟)  𝐹 , ii) [(𝑝 → 𝑞)  (𝑝 → 𝑟)]  [𝑝 → (𝑞  𝑟)] iii) ¬ ((𝑟  𝑝) ¬ 𝑝)  ¬ 𝑟  𝑝 b) Llenar la línea de puntos con una frase equivalente, y justificar su respuesta: i) No es cierto que no estudié ........................................................................ ii) No estudie inglés ni francés ..................................................................... iv) No es cierto que, si cobro el dinero viajare al sur ...................................... c) Negar las siguientes expresiones usando las equivalencias correspondientes.  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA Escribir simbólicamente a ambas expresiones i) Aprobaré Algebra y Discreta, ii) Si la universidad brinda becas de estudio, podré estudiar. Aplicaciones Circuitos digitales La lógica proposicional también se utiliza para diseñar circuitos digitales, los que transforman secuencias de señales de 1’s y 0’s en otras secuencias de señales de 1’s y 0’s a través de compuertas (dispositivos electrónicos) que realizan operaciones lógicas. Compuertas Un circuito digital se piensa abstractamente como una caja negra que establece una relación entre ciertas entradas y la salida: Fig.1.2. Representación circuito digital Las operaciones que realiza la caja negra se hallan completamente especificada al construir una tabla entrada/salida que liste todos los posibles valores de entrada con su respectivo valor de salida. En los circuitos digitales se utilizan compuertas lógicas. En la siguiente tabla se Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 27 observa los operadores, su símbolo y la expresión lógica que lo representa: Tipo de compuerta Representación simbólica Acción Entrada Salida Inversora p ¬p NOT 0 1 1 0 Entradas Salida Multiplicadora p q p.q AND 0 0 0 0 1 0 1 0 0 1 1 1 Entradas Salida p q p+q Suma inclusiva 0 0 0 OR 0 1 1 1 0 1 1 1 1 Entradas Salida p q pq Suma exclusiva 0 0 0 XOR 0 1 1 1 0 1 1 1 0 Tabla 1.11. Compuertas Lógicas.  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA La aplicación más directa de las compuertas lógicas es la combinación entre dos o más de ellas para formar circuitos lógicos que responden a funciones booleanas. Hasta la operación más básica en una computadora, como el presionar una tecla, hará que se realicen una serie de operaciones lógicas binarias en microsegundos. Esto es posible gracias a las compuertas lógicas que se encuentran dentro del microprocesador de la computadora. Circuitos lógicos Para interpretar el funcionamiento de las máquinas, se interpretará a las operaciones lógicas mediante circuitos eléctricos. Cada proposición está representada por una llave o interruptor, tal que si es verdadera deja pasar corriente y si es falsa la corta. El resultado de la proposición compuesta se interpreta como el pasaje de corriente de un terminal T1 a T2. Negación Fig. 1.3. Circuito de la Negación. En la Figura 1.3 se ilustran los dos posibles casos, llave cerrada y llave abierta. En el primer caso si ingresa corriente por T1 sale corriente por T2 y en el segundo caso si ingresa corriente por T1 no sale corriente por T2. Conjunción El circuito lógico de la conjunción se interpreta mediante un circuito en serie. Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 29  Fig. 1.4. Circuito de la conjunción. En la Figura 1.4 se ilustra solo el caso en que ambas llaves dejan pasar corriente, esto es, el caso donde 𝑝 = 1 ; 𝑞 = 1 y por lo tanto si ingresa corriente por T1 saldrá corriente por T2. Disyunción Inclusiva El circuito lógico correspondiente se interpreta mediante un circuito en paralelo. En la Figura 1.5 se ilustra solo el caso en que exactamente una llave deja pasar corriente, esto es, el caso donde 𝑝 = 1; 𝑞 = 0 y por lo tanto si ingresa corriente por T1 saldrá corriente por T2. Fig.1.5. Circuito de la disyunción inclusiva. 1.6 Implicación Lógica  Definición Sean A y B dos expresiones lógicas. Se dice que A implica lógicamente a B si y solo si cada vez que A es verdadera, B también lo es. Se denota: A  B. Como consecuencia de esta definición se tiene que: A  B si y solo si A → B es tautología.  Ejemplo Observar los renglones 3° y 4° de la Tabla 1.12, cada vez que el antecedente (𝑝) es verdadero, el consecuente (𝑝  𝑞) también lo es, por lo que 𝑝 𝑝∨𝑞  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA 𝑝 𝑞 𝑝  𝑞 𝑝→ 𝑝 𝑞 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 Tabla 1.12. Valores de verdad de 𝑝 → 𝑝 ∨ 𝑞. Actividad 1.6 Demostrar y analizar el mensaje que transmite cada implicación lógica. Dar un ejemplo coloquial donde se vea su aplicación: a) [(𝑝 ⟶ 𝑞)  ¬𝑞]  ¬𝑝 b) [(𝑝 ⟶ 𝑞)  (𝑞 ⟶ 𝑟)]  (𝑝 ⟶ 𝑟) 1.7 Razonamientos o Argumentos  Definición Un razonamiento o argumento es toda expresión lógica cuya estructura es del tipo 𝑝1 , 𝑝2 , … , 𝑝𝑛 → 𝑞 donde 𝑝1 , 𝑝2 , … , 𝑝𝑛 (premisas) y 𝑞 (conclusión) son proposiciones cualesquiera. Otra forma de notación es en formato vertical: 𝑝1 𝑝2 ⋮ 𝑝𝑛 ∴𝑞 Se lee: “ 𝑝1 , 𝑝2 , … , 𝑝𝑛 , por lo tanto 𝑞”. Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 31  Ejemplo Dado el siguiente argumento: “Esta noche viene Luis. Si viene Luis entonces voy al cine. Por lo tanto, esta noche llueve”. Se tienen dos premisas, 𝑝1 : “Esta noche viene Luis” y 𝑝2 : “Si viene Luis entonces voy al cine” La conclusión 𝑞: “Esta noche llueve” ¿Qué se puede observar de este argumento? ¿La conclusión “esta noche llueve” se deduce de las premisas dadas? La respuesta es que la conclusión no se deduce de las premisas. Este ejemplo nos muestra que existen argumentos no válidos. Validez de un Razonamiento  Definición Se dice que un razonamiento o argumento es válido cuando la conclusión se infiere o se deduce de las premisas. Por lo tanto, una manera de establecer la validez de un argumento es demostrar que la proposición 𝑝1  𝑝2  …  𝑝𝑛 → 𝑞 es una tautología. Simbólicamente 𝑝1 , 𝑝2 , … , 𝑝𝑛 → 𝑞 es un razonamiento válido si y solo si 𝑝1  𝑝2  …  𝑝𝑛  𝑞. De aquí se desprende que toda implicación lógica brinda un razonamiento válido.  Observación De la definición, se desprende que la conclusión es verdadera cada vez que las premisas lo sean, por lo tanto, no hace falta hacer toda la tabla de verdad de (𝑝1 𝑝2  … 𝑝𝑛 ) → 𝑞 , sólo se necesita analizar el/los renglones donde las premisas 𝑝1 , 𝑝2 , … , 𝑝𝑛 son verdaderas y se debe constatar que la conclusión 𝑞 es verdadera también.  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA 1.8 Principales Reglas de Inferencia  Definición: Al conjunto de razonamientos válidos más elementales se les llama Reglas de Inferencia. Ellas son: Regla de Modus Ponens, Regla de Modus Tollens, Regla de Adición disyuntiva, Regla de Combinación Conjuntiva, Regla de Simplificación en la Conjunción, Regla de Silogismo Hipotético y Regla de Silogismo Disyuntivo. A continuación, desarrollaremos una explicación de cada una de ellas Regla de Modus Ponens (MP) La regla de inferencia llamada Modus Ponens tiene como premisas a una implicación y al antecedente de ella; y como conclusión a su consecuente. Esto es: Si se supone que 𝑝 ⟶ 𝑞 y 𝑝 son verdaderas, entonces 𝑞 también lo es. La misma regla se aplica si intervienen proposiciones simples o compuestas. Lo expresaremos mediante la formula (𝑝 ⟶ 𝑞 ) ∧ 𝑝 ⇒ 𝑞 , o en su formato vertical: 𝑝⟶𝑞 𝑝. ∴𝑞  Ejemplos: Los siguientes argumentos son válidos pues tienen la estructura del MP: i) “Si Silvio estudia ISI, entonces cursará Matemática Discreta. Silvio estudia ISI. Luego, Silvio cursará Matemática Discreta.” Considerando 𝑝: “Silvio estudia ISI”, y 𝑞: “Silvio cursará Matemática Discreta”. Su forma simbólica responde a 𝑝⟶𝑞 𝑝. Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 33 ∴𝑞 ii) “Si Juan José no aprueba Matemática I, no cursará Matemática II. Juan José no aprueba Matemática I. Luego, Juan José no cursará Matemática II.” Su forma simbólica es: ¬𝑝 ⟶ ¬𝑞 ¬𝑝. ∴ ¬𝑞 Con 𝑝:” Juan José aprueba Matemática I” y 𝑞:” Juan José cursará Matemática II”. iii) En cada uno de los siguientes argumentos, se aplica la regla Modus Ponens a) 𝑝 b) ¬𝑝 → 𝑞 c) 𝑝  𝑞 → 𝑟 d) 𝑝 𝑝 → ¬𝑞 ¬𝑝 𝑝 𝑞 𝑝 →𝑞𝑟 ∴ ¬𝑞 ∴𝑞 ∴𝑟 ∴𝑞𝑟 Regla de Modus Tollens (MT) La regla de inferencia llamada Modus Tollens tiene como premisas a una implicación y a la negación de su consecuente; de alli infiere que la negación de su antecedente también es verdadera. Esto es: Si se supone que 𝑝 ⟶ 𝑞 y ~𝑞 son verdaderas, entonces ~𝑝 también lo es. La misma regla se aplica si intervienen proposiciones simples o compuestas. Lo expresaremos mediante la formula (𝑝 ⟶ 𝑞 ) ∧ ~𝑞 ⇒ ~𝑝 , o en su formato vertical: 𝑝⟶𝑞 ~𝑞. ∴ ~𝑝  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA  Ejemplos Las deducciones siguientes ejemplifican el uso del Modus Tollens. i) “Si tiene luz propia, entonces el astro es una estrella. El astro no es una estrella. Por tanto, no tiene luz propia.” Si 𝑝: “Tiene luz propia” y 𝑞: “El astro es una estrella”, el argumento se simboliza de la siguiente manera: 𝑝⟶𝑞 ~𝑞 ∴ ~𝑝 ii) “Si la memoria de la PC no es la correcta, el análisis de la base de datos no se podrá realizar. Pero se pudo realizar el análisis de la base de datos. Luego, la memoria de la PC es la correcta.” Tomando 𝑝: “La memoria de la PC es correcta”; 𝑟: “El análisis de la base de datos se puede realizar”, la formula del razonamiento es: ~𝑝 → ~𝑟 _ 𝑟  𝑝 la cual es una estructura de razonamiento válido pues se ajusta al Modus Tollens. iii) En los argumentos siguientes, también se usa la regla MT para inferir su validez: a) 𝑞 b) ¬𝑝 → 𝑞 c) 𝑝𝑞 → 𝑟 d) (𝑞𝑟) 𝑝 → ¬𝑞 ¬𝑞 ¬𝑟 𝑝 → 𝑞𝑟 ∴ ¬𝑝 ∴𝑝 ∴ ¬(𝑝𝑞) ∴ 𝑝 Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 35 Regla de Adición Disyuntiva La regla de Adición Disyuntiva expresa el hecho que si se tiene una proposición verdadera se puede inferir que la disyunción de aquella proposición y otra cualquiera ha de ser también verdadera. En forma simbólica la regla de Adición Disyuntiva quedaría: 𝑝 ∴ 𝑝𝑞  Ejemplos i) Con ejemplos en lenguaje natural u ordinario se ve lo obvia que es esta regla. Si, como premisa cierta, se tiene que: “Daniela aprobó Matemática Discreta” Entonces se puede concluir que las siguientes proposiciones compuestas son ciertas también: “Daniela aprobó Matemática Discreta o Análisis Matemático”. “Daniela aprobó Matemática Discreta o Álgebra”. “Daniela aprobó Matemática Discreta o viajó a China”, y así hay infinitas posibilidades pues la proposición que se agrega haciendo disyunción a la premisa puede ser cualquiera. ii) A continuación se dan otros ejemplos de razonamientos que gracias a la regla de Adición Disyuntiva son también válidos: a) 𝑞 b) 𝑟 c) 𝑝 ¬𝑞 d) ¬𝑝 ∴ 𝑞 ¬ 𝑟 ∴ 𝑝  𝑟 ∴ (𝑝 ¬𝑞) 𝑟 ∴ ¬𝑝  ¬𝑞  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA Regla de Combinación Conjuntiva Es la regla que permite inferir que la conjunción de las premisas es también verdadera. De manera simbólica se puede representar a la regla así: 𝑝 𝑞 ∴𝑝𝑞  Ejemplos i) El número atómico del hidrógeno es 1 El número atómico del helio es 2. ∴ El número atómico del hidrógeno es 1 y del helio es 2 ii) En los siguientes argumentos, se utiliza también la regla de combinación conjuntiva: a) 𝑞𝑟 b) ¬𝑝 c) 𝑝𝑞 d) (𝑞𝑟) 𝑝𝑞 ¬𝑞 ¬𝑟 𝑝 ∴ 𝑝𝑞𝑟 ∴ ¬𝑝¬𝑞 ∴ (𝑝𝑞¬𝑟) ∴ (𝑞𝑟)𝑝 Regla de Simplificación de la Conjunción La regla que teniendo de premisa una conjunción infiere a cualquiera de sus términos se denomina regla de la Simplificación. En forma simbólica la regla de simplificación es: 𝑝𝑞 Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 37  ∴𝑝  Ejemplos i) El número 2 es par y primo ∴ El número 2 es primo ii) El número 2 es par y primo ∴ El número 2 es par iii) A continuación, otros ejemplos del uso de la regla de simplificación: a) 𝑝 ¬𝑞 b) ¬𝑝  ¬𝑞 c) (𝑝  𝑞)  𝑟 d) 𝑝  ( q → 𝑟) ∴ ¬𝑞 ∴ ¬𝑝 ∴ 𝑝𝑞 ∴q→ 𝑟 Regla de Silogismo Hipotético (SH) Si las premisas son dos fórmulas condicionales, donde el consecuente de una es el antecedente de la otra, se infiere que es verdadero un nuevo condicional que vincula a antecedente y consecuente de una y otra premisa, respectivamente. Ésta es la regla llamada Silogismo Hipotético En forma simbólica: 𝑝→𝑞 𝑞→𝑟 ∴𝑝→𝑟  Ejemplos i) El siguiente razonamiento es válido: “3 es mayor que 2 si 4 es mayor que 3. Además 4 es mayor que 2 si 3 es mayor que 2. Luego, si 4 es mayor que 3 entonces 4 es mayor que 2.” Observe que si definimos 𝑝 , 𝑞 y 𝑟 de la siguiente manera; 𝑝: “4 es mayor que 3”;  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA 𝑞: “3 es mayor que 2”; 𝑟: “4 es mayor que 2”, el argumento queda expresado simbólicamente así: 𝑝→𝑞 𝑞→𝑟 ∴𝑝→𝑟 fórmula que coincide con la estructura del SH. ii) Los siguientes argumentos reflejan la regla del Silogismo Hipotético. Obsérvese que algunos de los antecedentes y consecuentes son proposiciones compuestas, sin embargo, la estructura del razonamiento es la misma. a) 𝑝→𝑞 b) ¬𝑝 → 𝑞  𝑟 c) 𝑡→𝑟𝑞 d) 𝑠→ 𝑝 (𝑞  𝑟) → 𝑠 𝑞→𝑟 𝑠→𝑡 𝑞  𝑟 → ¬𝑡 ∴ (𝑞  𝑟) → 𝑝 ∴ 𝑝 → 𝑟 ∴ ∴ 𝑠→𝑟𝑞 ¬𝑝 → ¬𝑡 Regla de Silogismo Disyuntivo (SD) Esta regla que tiene como una de las premisas la disyunción de dos términos y otra premisa afirma lo contrario a uno de ellos, concluye que el otro término ha de ser verdadero para que el razonamiento resulte válido. Simbólicamente, el Silogismo Disyuntivo se expresa así: 𝑝𝑞 ¬𝑝 ∴𝑞 Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 39  Ejemplos Los siguientes razonamientos reflejan el SD: i) “Esta sustancia contiene hidrógeno o contiene oxígeno. Pero esta sustancia no contiene oxígeno. Entonces se infiere que esta sustancia contiene hidrógeno”. Para un mejor entendimiento pasemos a su forma simbólica. Sean 𝑝: “Esta sustancia contiene hidrógeno” y 𝑞: “Esta sustancia contiene oxígeno” Por lo tanto, la fórmula correspondiente a este razonamiento válido es una variante del SD: 𝑝𝑞 ¬𝑞 ∴𝑝 ii) Los siguientes son ejemplos de razonamientos válidos donde aplicamos la regla del Silogismo Disyuntivo (SD) a) b) c) d) (𝑝 → 𝑞) 𝑟 ¬𝑡 (𝑝  𝑞) 𝑠 𝑞 𝑟 ¬𝑝  𝑡 ¬𝑠 𝑞 𝑟 ∴𝑝→𝑞 ∴ ¬𝑝 ∴ (𝑝  𝑞) d ∴ 𝑟  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA Resumen de las principales Reglas de Inferencia Implicación Lógica Regla de Inferencia Nombre asociada 𝑝 𝑝→𝑞 [ 𝑝  ( 𝑝 → 𝑞) ]  𝑞 Modus Ponens (MP) 𝑞 𝑝 →𝑞 [ ( 𝑝→ 𝑞)¬𝑞] ¬𝑝 ¬𝑞 Modus Tollens (MT)  ¬𝑝 𝑝 𝑝 𝑝𝑞 Adición disyuntiva  𝑝𝑞 𝑝 Combinación 𝑞 𝑝 , 𝑞 𝑝 𝑞 Conjuntiva  𝑝𝑞 𝑝𝑞 Simplificación 𝑝 𝑞  𝑝 𝑝 Conjuntiva 𝑝→𝑞 [( 𝑝→𝑞) ( 𝑞→𝑟)]  𝑝→𝑟 Silogismo Hipotético 𝑞→𝑟 (SH)  𝑝→𝑟 𝑝 𝑞 [ ( 𝑝  𝑞)¬𝑞] 𝑝 Silogismo Disyuntivo ¬𝑝 (SD) 𝑞 Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 41  Tabla 1.13. Principales Reglas de Inferencia Actividad 1.7 Escribir una conclusión que se deduzca de las premisas que se dan en cada caso, justificando su respuesta: a) Estudio inglés y francés. Por lo tanto, ……………………. b) Si el banco depositara el dinero, pagaré. El banco depositó el dinero. Por lo tanto, ………………………. c) Si el banco depositara el dinero, pagaré. Pero no pague. Por consiguiente, ………..… 1.9 Tipos de demostraciones para validar un razonamiento Una importante aplicación de los conceptos de equivalencias lógicas y reglas de inferencia se encuentra cuando en Matemática se necesita demostrar teoremas, que son básicamente una implicación lógica del tipo 𝑝 ⟹ 𝑞, donde 𝑝 es la hipótesis (datos o premisas) y 𝑞 es la tesis (o conclusión). En todo teorema 𝑝 ⟹ 𝑞 se requiere que el condicional sea tautológico. Los métodos de demostración usuales en Matemática se clasifican en directos e indirectos. Método directo Es el método de demostración más empleado en Matemática y que consiste en demostrar la verdad de una conclusión o tesis, dadas ciertas premisas o hipótesis que se suponen verdaderas. En la tabla de verdad de la implicación (Tabla 1.14), en los 3° y 4° renglones se puede observar que bajo el supuesto de que 𝑝 sea verdadera la única condición  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA para que la implicación sea verdadera es que 𝑞 sea verdadera. 𝑝 𝑞 𝑝→𝑞 0 0 1 0 1 1 Tabla 1.14. Condicional 1 0 0 1 1 1 En el caso de la demostración de la validez de un razonamiento por este método, se usan reglas de inferencia o leyes lógicas para demostrar que la conclusión se infiere de las premisas. Se recomienda utilizar el formalismo de la Deducción Natural o Derivación Formal para describir y justificar los pasos de la demostración. Procedimiento de Deducción Natural o Derivación Formal 1. Se determina cuáles son las premisas y se escribe cada premisa en una línea numerada, comenzando en 1. 2. Se tiene en cuenta cuál es la conclusión a la que se quiere llegar y se deja aparte. 3. Se aplican leyes lógicas o reglas de inferencia sobre las premisas , no importando el orden, para inferir nuevas proposiciones verdaderas que se deben seguir numerando a continuación de la última premisa. 4. El proceso termina cuando se llega a la conclusión después de haber hecho participar en la deducción a todas las premisas.  Ejemplos Sea el siguiente argumento: Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 43  𝑝 , 𝑝 → 𝑞 , 𝑟 →  𝑞 , 𝑠   𝑟  𝑠 Se demostrará su validez aplicando el procedimiento de Derivación formal, antes descripto. Pasos Razones 1) 𝑝 por ser premisa 2) 𝑝 → 𝑞 por ser premisa 3)  𝑟 →  𝑞 por ser premisa 4) 𝑠   𝑟 por ser premisa 5) 𝑞 por renglones 1 y 2 y aplicando MP 6) (𝑟) por renglones 3 y 5 y aplicando MT 7) 𝑟 por renglón 6 y aplicando ley de la Doble Negación 8) 𝑠 por renglones 4 y 7 y aplicando SD Luego el argumento es válido, pues a partir de las premisas se infiere la conclusión ii) Para demostrar que el siguiente razonamiento es válido se utiliza el proceso de derivación formal ¬𝑝 → 𝑞 ¬𝑝  𝑟 ¬𝑞 → 𝑟 Pasos Razones 1) ¬𝑝 → 𝑞 por ser premisa 2) ¬𝑝  𝑟 por ser premisa 3) 𝑝 → 𝑟 por renglón 2 y aplicando Ley del condicional 4) ¬𝑞 → 𝑝 por renglón 1 y aplicando ley de la Contrarrecíproca y de la Doble negación 5) ¬𝑞 → 𝑟 por renglones 4 y 3 y aplicando S. H. Luego el argumento es válido, pues a partir de las premisas se deduce la conclusión  Observación Para la aplicación de las reglas lógicas se puede utilizar una o más premisas las  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA veces que sean necesarias, siempre y cuando se usen las reglas adecuadamente y se trabajen con todas las premisas al finalizar el proceso. Actividad 1.8 Utilizar las reglas de inferencia y/o las leyes lógicas para determinar la validez de los siguientes razonamientos. a) 𝑝 → 𝑞 b) 𝑝 → 𝑞  𝑟 𝑝 → 𝑞 𝑝 → 𝑞 𝑝 𝑝  𝑟 Puede ocurrir que sea dificultoso o imposible de realizar la demostración de un razonamiento por el Método Directo. En tales casos se pueden intentar otras estrategias utilizando la equivalencia lógica del contrarrecíproco o incorporando la negación de la conclusión. De aquí resultan los Métodos Indirectos. Métodos Indirectos Hay dos métodos indirectos: Método por la Contrarrecíproca (o contraposición) y Método del absurdo. En este curso, sólo veremos el método por la contrarrecíproca Método por la Contrarrecíproca (o contraposición) Este método está basado en la equivalencia lógica del contrarrecíproco, la cual establece que 𝑝 ⟶ 𝑞 ⇔ ¬𝑞 ⟶ ¬𝑝 Romano, Gladys Mónica y Esper, Lidia Beatriz (2023) 45 Entonces demostrar que es verdadera la implicación 𝑝1 𝑝2  … 𝑝𝑛 → 𝑞 será equivalente a demostrar la veracidad de ¬𝑞 → ¬(𝑝1 𝑝2  … 𝑝𝑛 )  Ejemplo 𝑝→𝑞 𝑝→𝑟 ∴𝑝 →𝑞∧𝑟 Para demostrar la validez de este argumento usando el Método Indirecto de la Contrarrecíproca se plantea que lo que hay que demostrar es: ~(𝑝 → 𝑞 ∧ 𝑟) ⇒ ~[(𝑝 → 𝑞) ∧ (𝑝 → 𝑟 )] O su equivalente ~(𝑝 → 𝑞 ∧ 𝑟) ⇒ ~(𝑝 → 𝑞) ∨ ~(𝑝 → 𝑟 ) Pasos Razones 1) ~(𝑝 → 𝑞 ∧ 𝑟) por ser premisa 2) 𝑝 ∧ ~(𝑞 ∧ 𝑟) de 1 por ley de la Negación de la condicional 3) 𝑝 ∧ (~𝑞 ∨ ~𝑟) de 2 por ley de De Morgan 4) (𝑝 ∧ ~𝑞) ∨ (𝑝 ∧ ~𝑟) de 3 por ley Distributiva 5) ~(𝑝 → 𝑞) ∨ ~(𝑝 → 𝑟 ) de 4 por ley de la Negación de la Condicional Queda probado entonces ~(𝑝 → 𝑞 ∧ 𝑟) ⇒ ~(𝑝 → 𝑞) ∨ ~(𝑝 → 𝑟 ) y por lo tanto su equivalente (𝑝 → 𝑞) ∧ (𝑝 → 𝑟 ) ⇒ (𝑝 → 𝑞 ∧ 𝑟) Aplicación Un algoritmo se lo puede ver como una deducción en la cual nuestras premisas son los parámetros de entrada y la conclusión que se quiere deducir son los datos de salida; las reglas que se pueden utilizar serán el conjunto de instrucciones que proporciona el lenguaje. La idea básica y motivacional es observar a "la computación como una forma de  LOGICA Y ESTRUCTURAS DISCRETAS / MATEMATICA DISCRETA deducción". Deducción Computación Premisas valores de entrada Conclusión valores de salida Reglas básicas conjunto de instrucciones del lenguaje fórmulas de las líneas de traza del programa derivación justificaciones de las líneas de líneas (instrucciones) del programa derivación reglas de derivación procedimientos subdeducciones modularización Tabla 1.15. Comparación entre los pasos lógicos y los computacionales.  Ejemplo El siguiente programa tiene como entrada números reales, realiza los cálculos necesarios y devuelve el valor promedio de los datos ingresados: Proceso Promedio Escribir "Ingrese la cantidad de datos:" Leer n acum