MA265 Sesión 1.1 Teoría de conjuntos [Diapo]

UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 1 Lógica Proposicional CONTENIDO Unidad 2: LÓGICA Y ALGORITMOS 2.1 Lógica proposicional ▪ Introducción ▪ Lógica y proposición ▪ Operadores lógicos ▪ Tipos de proposición ▪ Tabla de verdad ▪ Clases de fórmulas lógicas ▪ Equivalencias UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 2 Lógica Introducción Los primeros grandes tratados de lógica fueron escritos por el filósofo griego Aristóteles. Eran un conjunto de reglas para el razonamiento deductivo que estaban destinadas a servir de base para el estudio de todas las ramas del conocimiento. En el siglo XVII, el filósofo y matemático alemán Gottfried Leibniz concibió la idea de utilizar símbolos para mecanizar el proceso del razonamiento deductivo de la misma manera que la notación algebraica había mecanizado el proceso de razonamiento de los números y sus relaciones. La idea de Leibniz se concretó en el siglo XIX por los matemáticos ingleses George Boole y Augustus De Morgan, quienes fundaron el moderno tema de la lógica simbólica. Con investigación continúa hasta nuestros días, la lógica simbólica ha proporcionado, entre otras cosas, la base teórica para muchas áreas de la ciencia computacional, tales como el diseño de circuitos lógicos digitales, la teoría de base de datos relacionales, la teoría de autómatas y la computabilidad y la inteligencia artificial. Lógica Es la disciplina que trata de los métodos de razonamiento. En un nivel elemental, la Lógica proporciona reglas y técnicas para determinar si es o no válido un argumento. Proposición Es una oración que declara que algo es verdadero o falso. Una proposición se expresa como una oración declarativa y no como pregunta, orden, exclamación, etc. Notación Para representar a las proposiciones en Lógica se emplean las letras 𝑝 , 𝑞 , 𝑟 , etc., llamadas variables propositivas (o proposicionales). UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 3 Operadores Lógicos Son expresiones o símbolos que se utilizan para crear nuevas proposiciones a partir de proposiciones dadas. Nombre del Operador Palabra que la define Símbolo Negación No es cierto que ~ Conjunción ... y ...  Disyunción ... o ...  Condicional Si ... entonces ... → Bicondicional ... s i y solo s i ...  Tipos de proposiciones Proposición Simple: Cuando es su definición no aparece operador lógico alguno. Ejemplo: 1. Raúl y Marcos son muy buenos amigos 2. El menor número natural es uno. Proposición Compuesta: Cuando en su definición aparece al menos un operador lógico. Ejemplo: 1. El menor número entero no es cero 2. El numero 21 es impar pero no primo. Fórmula Lógica: Es una combinación adecuada de variables propositivas y operadores lógicos. Ejemplo: • [𝑝 ⟶ (𝑞 ∧ 𝑟)] • (𝑝 ∨∼ 𝑞) ⟷ (∼ 𝑟 ∨ 𝑠) • 𝑝 ≡ El elemento 21 es impar. Y 𝑞 ≡ El elemento 21 es primo. Entonces 𝑝 ∧ 𝑞 ≡ El numero 21 es impar pero no primo UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 4 Tabla de verdad 𝒑 𝒒 ~𝒑 𝒑 ∧ 𝒒 𝒑 ∨ 𝒒 𝒑 ⟶ 𝒒 𝒑 ⟷ 𝒒 V V V F F V F F F F V V V F F F V V V F V F V V V F F V Ejemplo 1 Considere las proposiciones siguientes: a. El agua y el aceite no se pueden mezclar. b. Es falso que el agua y el aceite no se pueden mezclar. c. El agua y el aceite se mezclan. • b. y c. son, cada una, la negación de a. • Puesto que a. es verdadera, b. y c. son falsas Ejemplo 2 Considere las proposiciones siguientes: a. 2 + 3 = 7 b. Es falso que 2 + 3 = 7 c. 2 + 3 ≠ 7 • b. y c. son, cada una, la negación de a. • puesto que a. es falsa, b. y c. son verdaderas. Clases de fórmulas lógicas • Tautología: Una fórmula lógica es una tautología si su tabla de verdad solamente contiene valores de verdad VERDADEROS. • Contradicción o Falacia: Una fórmula lógica es una contradicción si su tabla de UPC – Departamento de Ciencias – MATEMÁTICA DISCRETA (MA265) Profesores MA265 5 verdad solamente contiene valores de verdad FALSOS. •…