Centro de Estudios Superiores del Oriente de Michoacán

CENTRO DE ESTUDIOS SUPERIORES DEL ORIENTE DE MICHOACÁN

{

OBJETIVO LICENCIATURA: ASIGNATURA: CATEDRÁTICO: TEMÁTICA: NOMBRE DEL ALUMNO:

Matemáticas para Computación

Discutir el uso y aplicación de la Lógica Proposicional en las Ciencias Computacionales

Sistemas Computacionales Matemáticas para Computación Ing. Luis Alberto Resendiz Quintana Lógica Proposicional

CUATR.: 2 SISTEMA: CLAVE DE LA ASIGNATURA: FECHA LÍMITE DE ENTREGA: GUÍA No:

Mixto LSC0212 2

MATRÍCULA:

I. Instrucciones. La guía didáctica que tienes en tus manos, tiene el objetivo de ser un andamiaje para desarrollar en ti los conocimientos, habilidades y actitudes necesarios para acreditar la asignatura de Matemáticas para Computación. Esto mediante comprensión de lectura y actividades que registrarás al final de este documento. A su vez, es necesario que te apoyes en las sesiones clase, láminas y material adicional disponible en la plataforma educativa. II. Temas y Subtemas. 2. Lógica Proposicional. 2.1 Proposiciones, tipos y enlaces. 2.2 Tablas de verdad. 2.3 Fórmulas lógicas. 2.4 Reglas de inferencia. III. Introducción. Enfatizando específicamente en la Filosofía, encontramos que esta tiene tres ramas principales, de las cuales una es la base de las ciencias computacionales. La Lógica es la rama de la filosofía que se encarga del estudio de lo verdadero y lo falso, lo cual a su vez, es la base de todo razonamiento matemático. Aunque también, la Lógica suele definirse como el estudio del razonamiento; en particular, se analiza si un razonamiento es correcto. La lógica se centra en las relaciones entre los enunciados y no en el contenido de un enunciado particular (Johnsonbaugh, 1999). Las reglas de la lógica le dan un significado preciso a los enunciados matemáticos. Estas reglas se usan para distinguir entre argumentos válidos y no válidos, sin dejar a un lado la aplicación en el diseño de circuitos electrónicos para ordenadores, elaboración de programas informáticos, entre otras (Rosen, 2004). Los métodos lógicos se usan en matemáticas para demostrar teoremas y, en las ciencias computacionales, para probar que los programas hacen lo que deben hacer. Supongamos que se asigna a un estudiante el desarrollo de un programa para calcular las trayectorias más cortas entre ciudades. Es necesario que el programa acepte como entrada un número arbitrario de ciudades y las distancias entre las ciudades con conexión directa por carretera, y que produzca como salida las trayectorias (rutas) más cortas entre cada par distinto de ciudades. Después de escribir el programa, es fácil para el estudiante probarlo con un número reducido de ciudades. Con papel y lápiz, puede enumerar todas las trayectorias posibles entre pares de ciudades y encontrar las más cortas. Ing. Luis Alberto Resendiz Quintana

Página 1 de 11

Centro de Estudios Superiores del Oriente de Michoacán

Matemáticas para Computación

Esta solución por “fuerza bruta” se compara con la salida del programa. Sin embargo, para un número grande de ciudades, la técnica de la “fuerza bruta” sería tardada. ¿Cómo puede el estudiante estar seguro de que el programa trabaja bien para muchos datos? Él tendrá que usar la Lógica para argumentar que el programa es correcto. El argumento puede ser informal o formal usando las técnicas presentadas en el siguiente tema; pero se requerirá un argumento lógico. Entender la lógica también resulta útil para aclarar la escritura común. Por ejemplo, en una ocasión, se publicó el siguiente decreto en Naperville, Illinois: “Será ilegal que una persona tenga más de tres perros y tres gatos en su propiedad dentro de la ciudad”. Un ciudadano que tenía cinco perros y ningún gato, ¿violaba el decreto? IV. Teoría. 2.1 Proposiciones, tipos y enlaces. Una proposición1 es una oración o afirmación declarativa, susceptible de ser evaluada como verdadera o como falsa, pero no ambas a la vez. Todas las oraciones que se muestran a continuación, son proposiciones, con la diferencia que la primera y la tercera son verdaderas, mientras que las restantes son falsas. a. Morelia es la capital de Michoacán. b. Japón está en América. c. 1+1=2 d. 2+2=3. La rama de la Lógica que se encarga de tratar con proposiciones se denomina Lógica Proposicional o Cálculo Proposicional, desarrollada por Aristóteles hace casi 2300 años. Es común que una proposición se exprese como una oración declarativa y no como pregunta, orden o exclamación2. Las proposiciones son los bloques básicos de construcción de cualquier teoría de lógica. Es común usar variables tales como p, q y r, para representar las proposiciones, casi como se usan letras en álgebra para representar números. Al hablar y escribir de forma normal3, dos proposiciones (denominadas simples) se pueden combinan usando conectores como y u o. Por ejemplo, las proposiciones “está lloviendo” y “hace frío” se pueden combinar para formar la proposición “está lloviendo y hace frío”. Al momento de que se adoptan ambas proposiciones y se combinan, esta se conoce como una proposición lógica compuesta. Se dice que una proposición es primitiva si no es posible separarla en proposiciones más simples; es decir, si no es compuesta. Los métodos para producir proposiciones nuevas a partir de las ya existentes fueron estudiados por el matemático ingles George Boole en 1854. Esta combinación de proposiciones se logra mediante símbolos conocidos como operadores lógicos, los cuales realizan operaciones lógicas como la conjunción (∧), disyunción (˅), negación (￢), implicación (→), doble implicación o bicondicional (↔) y disyunción exclusiva ( ). Estos indican en lenguaje natural “y”, “o”, “no”, “si… entonces”, “si y sólo si” y “o… o”. 2.2 Tablas de verdad. La propiedad fundamental de una proposición compuesta es que su valor de verdad lo determinan los valores de verdad de sus subproposiciones junto con la forma en que se conectan para formar las proposiciones compuestas.

1

También conocida como declaración o argumento. Cuando las proposiciones son oraciones declarativas se conocen como proposiciones válidas de lo contrario se indican como no válidas. 3 Conocido también como lenguaje natural. 2

Ing. Luis Alberto Resendiz Quintana

Página 2 de 11

Centro de Estudios Superiores del Oriente de Michoacán

Matemáticas para Computación

Dos proposiciones arbitrarias se combinan mediante la palabra “y” para formar una proposición compuesta que se denomina conjunción de las proposiciones originales (Lipschutz y Lipson, 2009), dicha combinación suele denotarse como p ∧ q, que se lee “p y q”, denotando la conjunción de la proposición lógicas p con q. El valor de verdad de p ∧ q tiene una forma equivalente de definición mediante la tabla 2.1. La primera fila indica que si p es verdadera y q es verdadera, entonces p ∧ q también es verdadera. Mientras que la segunda establece que si p es verdadera y q es falsa, entonces p ∧ q es falsa. Tabla 2.1: Tabla de verdad4 del operador lógico ∧.

Dos proposiciones arbitrarias se combinan mediante el conectivo “o” para formar una proposición compuesta denominada disyunción de las proposiciones originales (Lipschutz y Lipson, 2009), p ∨ q, que se lee “p o q”, denotando la disyunción de p y q. Tabla 2.2: Tabla de verdad del operador lógico ˅.

Dada cualquier proposición p, es posible indicar una negación de la misma, esto se indica como “no es verdad que. . .” o “es falso que. . .” antes de p, o bien, de ser posible al insertar en p la palabra “no”. El símbolo de la negación de p se lee “no p”, representado como￢p. Tabla 2.3: Tabla de verdad del operador lógico￢.

Estas tres primeras operaciones se conocen como básicas en el campo de la lógica, aunque tal y como se mencionó en el objetivo 2.1, existen aún más procedimientos. Muchas proposiciones, específicamente las 4

La tabla de verdad de una proposición P, consiste en una tabla formada por las proposiciones individuales p1, . . . , pn, la cual enumera todas las posibles combinaciones de los valores de verdad para p1, . . . , pn, donde V denota verdadero y F denota falso (Johnsonbaugh, 2005).

Ing. Luis Alberto Resendiz Quintana

Página 3 de 11

Centro de Estudios Superiores del Oriente de Michoacán

Matemáticas para Computación

llevadas a cabo en el campo de las matemáticas y la programación, son de la forma “si p entonces q”. Dichas proposiciones se denominan condicionales, p→q, leyéndose “p implica q” o “p sólo si q”. Otra proposición común es de la forma “p si y sólo si q”, denominadas bicondicionales, p↔q. Tabla 2.4: Tabla de verdad del operador lógico →.

Tabla 2.5: Tabla de verdad del operador lógico ↔.

Algunas implicaciones relacionadas con p→q puede formarse a través de esta. Por ejemplo, la proposición q→p se denomina recíproca de p→q, Por otro lado, la contrarrecíproca de p→q será ￢q→￢p, mientras que la proposición ￢p→￢q es la inversa de p→q. Para finalizar, el conectivo lógico o exclusivo p q, indica que dicha proposición es verdadera únicamente cuando una de las proposiciones p y q es verdadera y falsa en cualquier otro caso. Tabla 2.6: Tabla de verdad del operador lógico

.

Todos los lenguajes del ser humano son a menudo ambiguos, traducir estas expresiones del lenguaje natural a proposiciones o expresiones lógicas, evita estas ambigüedades5. Por ejemplo, si quisiéramos formalizar la frase “puedes estudiar una licenciatura sólo si concluiste tu bachillerato y tienes tu certificado de estudios”, debemos utilizar variables proposicionales y determinar los conectivos u operadores lógicos que intervienen y que son apropiados para ellas. Específicamente las frases “puedes estudiar una licenciatura”, “concluiste tu bachillerato” y “tienes tu certificado de estudios” por p, q y r respectivamente; considerando a

5

A esta “traducción” se le conoce como lenguaje formal o formalización.

Ing. Luis Alberto Resendiz Quintana

Página 4 de 11

Centro de Estudios Superiores del Oriente de Michoacán

Matemáticas para Computación

su vez que “sólo si” indica una implicación. Por lo que la transformación de la frase a lógica proposicional quedaría como p→(q∧r). Si encontráramos la recíproca, contrarrecíproca e inversa de la implicación “el equipo halcones gana siempre que llueve”, quedaría como “si llueve, entonces el equipo halcones gana”, “si no lleve, entonces el equipo halcones no gana” y “el equipo halcones no gana, no llueve” La propiedad más importante de una proposición es que su valor de verdad depende exclusivamente de los valores de verdad de cada una de sus variables (Lipschutz y Lipson, 2009). Una manera extremadamente útil para mostrar esta relación es como ya se ha visto, con una tabla de verdad, por ejemplo, la proposición ￢(p∧￢q) origina la tabla 2.7. Debe tomarse en cuenta que para construirla es específicamente importante comenzar con la fórmula 2n, donde n indica el número de variables lógicas. Esto da origen al número de filas de nuestra tabla de verdad donde cada columna de cada proposición lógica simple tendrá la mitad de verdaderos y de falsos que la columna anterior. Esta tabla indicará bajo que combinación puede presentarse una verdad o una falsedad. Cabe mencionar que si todas las combinaciones dan como resultado valores verdaderos, se estará hablando de una tautología6, aunque también suele ser una contradicción si a todos los valores de salida corresponde un falso. Se estará hablando de una indeterminación si resulta combinación de verdaderos y falsos. Tabla 2.7: Ejemplo de una tabla de verdad.

2.3 Fórmulas lógicas. En algunas ocasiones, dos proposiciones lógicas compuestas tienen los mismos valores de verdad. Cuando esto sucede decimos que son proposiciones equivalentes o lógicamente equivalentes, denotado por el símbolo “≡”. Por ejemplo, las tablas de verdad de las proposiciones ￢(p∧q) y ￢p∨￢q que se muestran a continuación son lógicamente equivalentes. Obsérvese que ambas tablas de verdad son la misma; es decir, ambas proposiciones son falsas en el primer caso y verdaderas en los otros tres casos. En consecuencia, puede escribirse que ￢(p∧q) ≡ ￢p∨￢q, lo que indica que las proposiciones son lógicamente equivalentes. Tabla 2.8: Ejemplo de una equivalencia lógica.

6

Verdad absoluta incuestionable.

Ing. Luis Alberto Resendiz Quintana

Página 5 de 11

Centro de Estudios Superiores del Oriente de Michoacán

Matemáticas para Computación

Las siguientes tablas permiten dar solución a una implicación lógica, aplicando las reglas indicadas. Cabe mencionar que dar solución a una implicación conlleva a que al utilizar una o más fórmulas lógicas, nos dé un resultado verdadero o falso únicamente. Tabla 2.9: Equivalencias lógicas comunes (Rosen 2004).

Tabla 2.10: Equivalencias lógicas relacionadas con implicaciones (Rosen 2004).

Ing. Luis Alberto Resendiz Quintana

Página 6 de 11

Centro de Estudios Superiores del Oriente de Michoacán

Matemáticas para Computación

Tabla 2.11: Equivalencias lógicas relacionadas con bicondicionales (Rosen 2004).

2.4 Reglas de inferencia. En matemáticas, un sistema consiste en axiomas, definiciones y términos no definidos. Se supone que los axiomas suelen ser verdaderos. Las definiciones se usan para crear nuevos conceptos en términos de los existentes. Algunos términos no están definidos de forma explícita por los axiomas. Dentro de un sistema matemático es posible derivar teoremas. Un teorema es una proposición que se ha probado que es verdadera. Algunos tipos especiales de teoremas reciben el nombre de lemas y corolarios. Un lema es un teorema que no suele ser muy interesante por sí mismo, pero que resulta útil para probar otro teorema. Un corolario es un teorema que se deriva con facilidad de otro teorema. Un argumento que establece la verdad de un teorema se llama demostración o prueba (Johnsonbaugh, 1999). La lógica es la herramienta para el análisis de las demostraciones, específicamente el uso de las reglas de inferencia, nos ayudará a deducir conclusiones a partir de otras afirmaciones o proposiciones. Dicho proceso de extracción de una conclusión a partir de una serie de proposiciones de denomina razonamiento deductivo, sólo que en lugar de nombrarlas proposiciones las llamaremos hipótesis o premisas, donde la proposición que se sigue de las hipótesis, es la conclusión. Un argumento deductivo consta de una serie de ciertas hipótesis con una conclusión. Un argumento tiene la forma p1 ∧ p2 ∧ p3 ∧ … ∧ pn → q, y es válido7 si las conclusiones se siguen de la hipótesis; es decir, si p1, p2, p3 y pn son verdaderas, entonces la conclusión q también debe ser verdadera, es caso contrario el argumento no es válido y se considera como una falacia8. Lo anterior puede verificarse empleando las tablas de verdad o las equivalencias lógicas. Al deducir conclusiones podemos hacerlo mediante tres métodos. El primero de ellos se denomina directo o prueba directa, este supone que si la proposición p(x1, x2,..., xn) es verdadera, y después, usando p(x1, x2, . . . , xn) junto con otros axiomas, definiciones y teoremas derivados antes, se demuestra directamente que q(x1, x2, . . . , xn) es verdadera. Una segunda técnica de demostración es por contradicción9, la cual establece que suponiendo que la hipótesis p es cierta y que la conclusión q es falsa en si p(x1, x2,..., xn), entonces q(x1, x2,..., xn), usando p y ￢q junto con otros axiomas, definiciones y teoremas derivados antes, llega a una contradicción. La única diferencia entre las suposiciones en una prueba directa y una prueba por contradicción, es la conclusión negada. En una prueba directa no se supone la conclusión negada, mientras que en una prueba por contradicción la conclusión negada es una suposición. La prueba por contradicción se justifica observando que las proposiciones p→q y (p￢q)→( r∧￢r) son equivalentes. Por último, la demostración por casos se emplea cuando la hipótesis original se divide de manera natural en varios casos. El objetivo es probar la implicación

7

Un argumento es válido debido a su forma más no a su contenido. Argumento incorrecto que trata esta proposición como si fuera una tautología. 9 Una contradicción es una proposición de la forma r∧￢r (r puede ser cualquier proposición). Una prueba por contradicción en ocasiones se llama prueba indirecta ya que para establecer p(x1, x2,..., xn), entonces q(x1, x2,..., xn) usando la prueba por contradicción, se sigue una ruta indirecta: se deriva r ∧ ￢r y después se concluye que p(x1, x2,..., xn), entonces q(x1, x2,..., xn) es verdadera. 8

Ing. Luis Alberto Resendiz Quintana

Página 7 de 11

Centro de Estudios Superiores del Oriente de Michoacán

Matemáticas para Computación

p→q y que p es equivalente a p1∨p2∨...∨pn, donde p1,..., pn son los casos. En lugar de probar (p1∨p2∨...∨ pn) → q, se prueba (p1→q)∧(p2→q)∧...∧(pn→q). Las reglas de inferencia permiten obtener la conclusion de varios argumentos de la siguiente forma, donde el símbolo indica o se lee “por lo tanto”. Recordando que las proposiciones p1, p2, . . . , pn se conocen como hipótesis (o premisas), y la proposición q recibe el nombre de conclusión. El argumento es válido siempre y cuando, si p1 y p2 y . . . y pn son todas verdaderas, entonces q también es verdadera; de otra manera, el argumento es inválido (o una falacia).

Estas reglas son argumentos válidos breves que se utilizan dentro de argumentos más largos como una demostración. Tabla 2.12: Reglas de inferencia (Rosen 2004).

Ing. Luis Alberto Resendiz Quintana

Página 8 de 11

Centro de Estudios Superiores del Oriente de Michoacán

Matemáticas para Computación

V. Conceptos y Palabras Clave. Los conceptos que se enlistan enseguida te ayudarán a identificar aspectos específicos de la lectura anterior, por ello, es importante que investigues el significado de cada uno de ellos en el contexto estricto de la asignatura, anotando dichas definiciones en una hoja independiente, indicando a su vez la(s) fuente(s) bibliográfica(s) en donde consultaste la información preferentemente en formato APA. - Lógica. - Proposición. - Variable proposicional. - Argumento. - Valor de verdad. - Tautología. - Contradicción. - Indeterminación. - Deducción. - Inducción. VI. Preguntas de Repaso. Las preguntas que se formulan enseguida te ayudarán a comprender de mejor manera la temática del bloque, por ello, es importante que respondas a cada una de ellas con tus propias palabras. Si lo requieres, puedes apoyarte en la tercera y cuarta sección de tu guía. Anota tus respuestas en una hoja independiente. 1. ¿Qué es una tabla de verdad? 2. ¿Qué es la conjunción de p y q? ¿Cómo se denota? 3. ¿Qué es la disyunción de p y q? ¿Cómo se denota? 4. ¿Qué es la negación de p? ¿Cómo se denota? 5. ¿Qué es un axioma, un teorema y un lema? 6. ¿Qué es una demostración? Y ¿Cuáles son los tres métodos para obtenerla? 7. ¿En qué consisten las tres variantes de una implicación? 8. ¿Qué es el razonamiento deductivo? 9. ¿Qué es una hipótesis y una premisa en un argumento? 10. ¿Qué es un argumento válido y no válido? VII. Actividades. Las actividades mencionadas a continuación te serán de ayuda para asentar los conocimientos adquiridos durante el segundo bloque de la asignatura, por esta razón es importante que completes cada una de ellas con la información y datos que se te piden. 1. Existen dos operadores lógicos adicionales conocidos como NAND y NOR. La proposición p NAND q es verdadera cuando p o q, o ambas, son falsas, y es falsa cuando tanto p como q son verdaderas. La proposición p NOR q es verdadera cuando p o q, o ambas, son falsas, y es falsa en cualquier otro caso. Las proposiciones p NAND q y p NOR q, se denotan por p | q y p ↓ q, respectivamente. Los operadores | y ↓, se denominan barra de Shefer y flecha de Peirce, por H. M. Sheffer y C. S. Peirce. Construye la tabla de verdad de los operadores anteriores donde a su vez demuestres que: a. p | q ≡ ￢(p∧q) b. p | q ≡ q | p c. p ↓ q ≡ ￢(p∧q) d. (p ↓ q ) ↓ (p ↓ q ) ≡ p ˅ q e. p ↓ q ≡ ￢p Encuentra una proposición equivalente a p→q usando sólo el operador lógico ↓. Ing. Luis Alberto Resendiz Quintana

Página 9 de 11

Centro de Estudios Superiores del Oriente de Michoacán

Matemáticas para Computación

VIII. Problemas de Aplicación. Los siguientes problemas de aplicación reforzarán las actividades teóricas vistas hasta el momento, por ello es necesario resolver todos y cada uno de ellos empleando tu ingenio y lo aprendido durante las sesiones clase. a. Representa simbólicamente la proposición definiendo: p: Hay huracán. q: Está lloviendo. 1. No hay huracán. 2. Hay huracán y está lloviendo. 3. Hay huracán, pero no está lloviendo. 4. No hay huracán y no está lloviendo. 5. Hay huracán o está lloviendo (o ambas). 6. Hay huracán o está lloviendo, pero no hay huracán. b. Determina la recíproca, contrarrecíproca e inversa las siguientes proposiciones: - Si Eric es poeta, entonces es pobre. - Sólo si Marcos estudia aprobará el examen. c. Demuestra que el siguiente argumento es una falacia: p→q, ￢ p ￢q. d. Usando tablas de verdad, determina la validez de los siguientes argumentos: 1. p→q, ￢ p

￢p.

2. p→￢q, r→q, r ￢p. 3. Si 7 es menor que 4, entonces 7 no es un número primo. 7 no es menor que 4. 7 es un número primo. 4. Si dos lados de un triángulo son iguales, entonces los ángulos opuestos son iguales. Dos lados de un triángulo no son iguales. Los ángulos opuestos de un triángulo no son iguales. e. Determina lo que se indica:

Ing. Luis Alberto Resendiz Quintana

Página 10 de 11

Centro de Estudios Superiores del Oriente de Michoacán

Matemáticas para Computación

IX. Referencias Bibliográficas. - Johnsonbaugh, R. (2005). Matemáticas Discretas. México: Pearson. - Lipschutz, S. y Lipson, M. (2009). Matemáticas Discretas. México: McGraw Hill. - Rosen, K. H (2004). Matemática Discreta y sus Aplicaciones. Diseño Digital. Madrid: McGraw Hill.

Firma del Alumno

______________________________

Ing. Luis Alberto Resendiz Quintana

Página 11 de 11