Download IMD-IS. Lógica. Conjuntos
Document related concepts
Transcript
Lógica Conjuntos Álgebras de Boole IMD-IS. Lógica. Conjuntos Emmanuel Briand ETSII. Universidad de Sevilla. 2012 Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Proposiciones 2 + 3 = 4 Hoy es lunes Si x =2 entonces x 2 = 4 Ojalá no llueva hoy ! x >0 y x < 1. Existe una innidad de números primos p tal que p es primo. Emmanuel Briand IMD-IS. Lógica. Conjuntos +2 Lógica Conjuntos Álgebras de Boole Proposiciones compuestas Proposición simple / Proposición compuesta. Hoy es lunes y llueve Si llueve, no salgo 5 ≥3 y 5 ≤ 6 Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Conectores lógicos y o no si . . . entonces . . . . . . si y solo si . . . ... Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Conectores lógicos y tablas de verdad p q V V V F F V F F p y q p o p q V V V V p no F V F V V F F F V V F V F F F F Emmanuel Briand q p p q p ⇔q V V V V F F F V F F F V IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Hay simbolos para estos conectores lógicos . . . Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Razonamiento por equivalencia +2y +4y =0 =1 +2y −2y =0 =1 x 3x x +2y x y −1 x y x y Emmanuel Briand =0 = −1/2 =0 = −1/2 =1 = −1/2 IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole El conector de implicación p q p ⇒q V V V F V F F V V F F V Si hay vida extraterrestre entonces 1 + 1 = 2 Si 1 + 1 = 3 entonces todos los estudiantes excepto uno aprobarán la asignatura Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Formulas lógicas Conoceis formulas como: x 2 +y −1 Las letras x e y son variables que representan números incógnitos. Aquí está una formula lógica: p ∨ (¬p ∧ q ) Las letras p y q representan proposiciones incógnitas. Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Ejercicios ¾ Cuál es la negación de: 1234567 es primo y 7654321 es primo? Si Grouchy hubiese llegado a tiempo, Napoleón habría ganado la batalla de Waterloo ? Simplicar: p ∨ (¬p ∧ q ) Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Una equivalencias lógicas importantes Equivalencia = doble implicación p ⇔ q es lógicamente equivalente a (p ⇒ q ) ∧ (q ⇒ p ). p implica q cuando la hipotesis no se cumple, o cuando la conclusión se cumple. p ⇒ q es lógicamente equivalente a (¬p ) ∨ q Una implicación es equivalente a su contrarreciproco p ⇒ q es lógicamente equivalente a (¬q ) Emmanuel Briand ⇒ (¬p ) IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Contrarreciproco y reciproco La implicación p ⇒ q como reciproco: q tiene: ⇒ p. como contrarreciproco (¬q ) ⇒ (¬p ). La implicación: Si tengo hambre entonces estoy de mal humor. tiene: como reciproco: Si estoy de mal humor entonces tengo hambre. como contrarreciproco: Si no estoy de mla humor, entonces no tengo hambre. La implicación es lógicamente equivalente a su contrarrecíproco, NO es lógicamente equivalente a su reciproco. Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Las leyes de la lógica p∨q p∧q p∨q p∧q (p ∨ q ) ∨ r ≡ (p ∧ q ) ∧ r ≡ p ∧ (q ∨ r ) p ∨ (q ∧ r ) ≡ ≡ p≡p ff p∧q p∨q ≡ ≡ q∨p q∧p p ∨ (q ∨ r ) p ∧ (q ∧ r ) ≡ (p ∧ q ) ∨ (p ∧ r ) ≡ (p ∨ q ) ∧ (p ∨ r ) p∨p p∧p ≡ ≡ p p p∨f p∧v ≡ ≡ p p p∨v p∧f ≡ ≡ v f ≡ ≡ v f p∨p p∧p Ley de la doble negación Leyes de De Morgan ff Conmutatividad de ∨ y y ∧ ∧ ff Asociatividad de ∨ ff Distributividad de cada una de las operaciones con respecto a la otra ff Leyes de idempotencia ff vyf son neutros para ∧ y ∨ respectivamente. ff Leyes de dominación ff p Leyes de los inversos p ∨ (p ∧ q ) ≡ p Leyes de absorción p ∧ (p ∨ q) Emmanuel ≡ p Briand IMD-IS. Lógica. ff Conjuntos Lógica Conjuntos Álgebras de Boole Y las paréntesis Sean a, b, c tres enteros. a es primo y b es primo o c no es primo ¾ Qué signica ? a es primo y (b es primo o c no es primo) (a es primo y b es primo) o c no es primo Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Ejemplos de conjuntos {(1, 2), (3, 2), (1, 1)} {x , y , z } {exp, cos} {{1}, {1, 2}, {2, 5}} {1, exp, {1}, {1, 2}} un conjunto de pares de números un conjunto de variables un conjunto de funciones un conjunto de conjuntos un conjunto de varios tipos de objetos. ½ El orden no cuenta ! Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Denir un conjunto por medio de una propiedad caractéristica Sea B el conjunto de todos los números enteros pares n que cumplen n B = {n | ≥2 n y n < 9 es un entero par y B n ≥2y n < 9} = {2, 4, 6, 8} Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Subconjuntos. El conjunto vacío Los subconjuntos de {1 , 2 } son: Emmanuel Briand ∅, {1 }, {2 } y {1, 2}. IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Unión, intersección, Diferencia Emmanuel Briand x ∈A∪B ssi (x ∈A o x ∈ B) x ∈A∩B ssi (x ∈A y x ∈ B) x ∈A\B ssi (x ∈A y x 6∈ B ) x ∈A ssi (x 6∈ A) IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Conectores lógicos y conjuntos Union ↔ o: x Intersection ↔ Compleentario Incluido en Iguales x ↔ ↔ ∈A∪B y: x ↔ ssi (x ∈A∩B negación: x implica: A o x ∈A =B ∈ B) ∈A ssi (x ⊂B equivalentes: A ∈A ssi (x ssi (x ∈A ssi (x y x ∈ B) 6∈ A) implica x ∈A es equivalente a ∈ B) Emmanuel Briand ∈ B) IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Las leyes de la teoría de conjuntos A=A ff A∪B =A∩B A∩B =A∪B A∪B =B∪A A∩B =B∩A (A ∪ B ) ∪ C = (A ∩ B ) ∩ C = A ∪ (B ∪ C ) A ∩ (B ∩ C ) A ∩ (B ∪ C ) = ( A ∩ B ) ∪ (A ∩ C ) A ∪ (B ∩ C ) = ( A ∪ B ) ∩ (A ∪ C ) A∪A=A A∩A=A A∪∅=A A∩X =A A∪X =A A∩∅=∅ A∪A=X A∩A=∅ Ley del doble complemento Leyes de De Morgan ff Conmutatividad de ∪ y y ∩ ∩ ff Asociatividad de ∪ ff Distributividad de cada una de las operaciones con respecto a la otra ff A es idempotente para ambas operaciones ff X neutros X absorbentes y ∅ son respectivamente. ff y ∅ son respectivamente. ff ff A ∪ (A ∩ BEmmanuel )=A para para ∩ ∪ A es inversa de A para ∪ y ∩ Briand IMD-IS. Lógica. Conjuntos y y ∪ ∩ Lógica Conjuntos Álgebras de Boole Conjuntos y diagramas A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C ) Intuición: diagrama Demostración formal: ver apuntes. Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Un ejemplo de demsotración: A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C ) Idea 1: x ∈ A ∩ (B ∪ C ) ⇔ (x ∈ A) ∧ (x ∈ (B ∪ C )) ⇔ ... Idea 2: para demostrar que dos listas de nombres tienen exactamente el mismo contenido (pero a lo mejor no en el mismo orden), comprobo que cada nombre en la primera lista aparece en la segunda y luego que cada nombre en la segunda lista aparece en la primera. Esta idea se aplica a conjuntos (incluso innitos): X =Y ⇔X ⊂Y y Y ⊂X Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Leyes de lógica, leyes de conjuntos Emmanuel Briand IMD-IS. Lógica. Conjuntos Lógica Conjuntos Álgebras de Boole Álgebras de Boole Cualquier conjunto equipado con tres operaciones +, ×, 0 y con dos elementos distinguidos 0 y 1, que satisface las 10 propiedades del cuadro. (Pero basta comprobar cinco de ellas) Conjunto operaciones Los subconjutos de ∪, ∩, elementos especiales complementario ∅ y X un conjunto X {V , F } ∨, ∧, ¬ F y V {0, 1} +, ×, 0 0 y 1 Álgebra de Boole de la lógica = álgebra de conmutación (mutatis mutandis) Emmanuel Briand IMD-IS. Lógica. Conjuntos