Download Lógica y Conjuntos
Document related concepts
Transcript
Universidad Nacional de Colombia Sede Palmira Matemática Fundamental ___________________________ LÓGICA La lógica es 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 en particular. Por ejemplo, considérese el siguiente argumento: Todos los matemáticos utilizan sandalias Cualquier persona que utilice sandalias es algebrista Por tanto, todos los matemáticos son algebristas Desde el punto de vista técnico, la lógica no permite determinar si estos enunciados son verdaderos; sin embargo, si los dos primeros enunciados fuesen verdaderos, la lógica garantizará que el enunciado Todos los matemáticos son algebristas. También es verdadero. Proposición: Es una afirmación que es verdadera o falsa, pero no ambas Es un enunciado del cual se puede establecer si es verdadero o falso Proposiciones compuestas: Resultan de combinar proposiciones mediante coactivos lógicos. Conectivos Lógicos: ü ü ü ü ü ü Negación ~ Conjunción ∧ Disyunción ∨ Or exclusiva ⊕ Condicional → Bicondicional ↔ Las proposiciones las denotaremos con letras minúsculas p, q, r, w El número de combinaciones posibles es 2 n donde n, es el número de proposiciones Si tenemos dos proposiciones p y q, sus tablas de verdad son las siguientes Negación: p V F ~p F V Profesor: José Alfredo Martínez Valdés 1 Universidad Nacional de Colombia Sede Palmira Matemática Fundamental ___________________________ Conjunción: p V V F F q V F V F p ∧ q V F F F Disyunción: p V V F F q V F V F p∨ q V V V F Or Exclusiva: p V V F F q V F V F p⊕ q F V V F Condicional: p V V F F q V F V F p→q V F V V Bicondicional: p V V F F q V F V F p↔q V F F V Profesor: José Alfredo Martínez Valdés 2 Universidad Nacional de Colombia Sede Palmira Matemática Fundamental ___________________________ TABLA DE VERDAD PARA Conjunción, Disyunción y Or – Exclusiva x F F V V y F V F V x∨ y F V V V x∧ y F F F V x⊕ y F V V F Equivalencia proposicional: Teorema 1: Sea P y Q proposiciones para la cuales P ↔ Q es siempre verdadera. Entonces P y Q son lógicamente equivalentes. Por otro lado, si P y Q son lógicamente equivalentes, entonces P ↔ Q es siempre verdadera P ⇔ Q Se lee P es lógicamente equivalente a Q Tautología: Una proposición es una tautología si es siempre verdadera Contradicción: Es una proposición que es siempre falsa Contingencia: Cuando no es Tautología ni Contradicción Una frase abie rta o función proposicional es una proposición que contiene una variable. Por ejemplo, la frase “x2 + 2x + 16 = 0” contiene la variable x, al igual que la frase “x fue el primer presidente de los Estados Unidos”. La colección de objetos que pueden ser sustituidos por una frase abierta se llama conjunto de significados de esa variable. Llamaremos conjunto de verdad de la frase abierta, al conjunto de objetos de significados para los cuales la frase abierta se convierte en una proposición verdadera de la frase abierta, al conjunto de objetos pertenecientes al conjunto de significados para la frase abierta x2 + 2x + 16 = 0 es el de los números reales, entonces el conjunto de verdad es vacío. Si el conjunto de significados incluye además -1 ± i 15 entonces el conjunto de verdad tiene algún elemento. Si P es una frase abierta que contiene la variable x, se escribe P(x). Generalmente, cuando se muestra una frase abierta, el conjunto de significados para la(s) variable(s) que contiene es explícitamente declarado o se deduce fácilmente del contexto, Ciertos operadores indican la forma de seleccionar elementos del conjunto de significados. Esos operadores son los cuantificadores universal y existencial. Una frase de la forma “para todo x del conjunto de significados P(x) es verdadera” se dice que es una frase universalmente cuantificada. Esto indica que el conjunto de verdad de P(x) está compuesto por todos los objetos pertenecientes al conjunto de significados de x. Esto, en forma abreviada, se escribe ∀xP( x) , lo cual se lee “para todo x, P(x)”. Fíjese que ∀xP( x) ya no es una frase abierta puesto que su verdad o falsedad Profesor: José Alfredo Martínez Valdés 3 Universidad Nacional de Colombia Sede Palmira Matemática Fundamental ___________________________ puede ser determinada. Por ejemplo, si P(x) es la frase abierta “x + 1 > x” y el conjunto de significados es la colección de todos los números reales, entonces ∀xP( x) es una proposición verdadera. Una frase de la forma “existe un x en el conjunto de significados P(x) es verdadera” se dice que está cuantificada existencialmente. Esto indica que algún elemento del conjunto de significados es un valor que, al sustituir a x, hace que P(x) sea verdadera. Lo cual quiere decir que algún elemento del conjunto de significados está también en el conjunto de verdad de P(x). Esto en forma abreviada, se escribe ∃xP( x) y se lee “Existe un x tal que P(x) ”, o “para algún x, P(x) “. Tenga en cuenta que ∃xP( x) ya no es una frase abierta. Teorema 2: ~ ( ∀xP( x) ) es equivalente a ∃x ~ P( x) Ejemplo: “Si n es primo entonces 2n – 1 es primo. Cuando n = 11, no se cumple. Ejemplos: Suponga que P(x) denote el enunciado “x > 3.” ¿Cuáles son los valores de verdad para P (4) y P (2)? Suponga que Q(x, y) denote el enunciado “x = y + 3” ¿Cuáles son los valores de verdad de Q (1, 2) y Q (3,0)? Suponga que R(x, y, z) denote el enunciado “x + y = z” ¿Cuáles son los valores de verdad de R (1, 2, 3) y R (0, 0, 1)? Cual es el valor de verdad de ∀xP( x) , donde P(x) es el enunciado “x2 < 10 “ y el universo del discurso consiste de los enteros positivos que no exceden a 4? Solución: El enunciado ∀xP( x) es lo mismo que la conjunción P (1) ∧ P (2) ∧ P (3) ∧ P (4). El enunciado “ 42 < 10” es falso, por tanto P(4) es falso y , la conjunción es falsa. Suponga que Q(x) denote el enunciado “x > 3.” Cuál es el valor de verdad de ∃xP( x) , donde el universo del discurso es el conjunto de los números reales? Profesor: José Alfredo Martínez Valdés 4 Universidad Nacional de Colombia Sede Palmira Matemática Fundamental ___________________________ CONJUNTOS: DEFINICIÓN 1: Los objetos en un conjunto son también llamados los elementos o miembros del conjunto. Se dice que un conjunto A, contiene sus elementos. DEFINICIÓN 2: Dos conjuntos son iguales si y solo si ellos tienen los mismos elementos. DEFINICIÓN 3: Se dice que el conjunto A es subconjunto del conjunto B si y solo si cada elemento de A es también un elemento de B. Usaremos A⊆ B para indicar que A es subconjunto del conjunto B DEFINICIÓN 4: Supongamos que S es un conjunto. Si hay exactamente n elementos distintos en S donde n es un entero no negativo, nosotros diremos que S es un conjunto finito y que n es el cardinal de S. El Cardinal de S es denotado por | S |. DEFINICIÓN 5: Un conjunto A se dice que es infinito, cuando no es finito DEFINICIÓN 6: Dado un conjunto S, la potencia de S es el conjunto de todos los subconjuntos del conjunto S. El conjunto potencia de S es denotado por P(S). DEFINICIÓN 7: La n-tupla ordenada (a1 , a2 , …,an ) es la colección ordenada que tiene a a1 como su primer elemento, a a2 como su segundo elemento, … , an como su n ésimo elemento. DEFINICIÓN 8: Si A y B son conjuntos. El producto cartesiano de A y B, denotado por A x B, es el conjunto de todos las parejas ordenadas (a, b) donde a ∈ A y b ∈ B. De aquí, que A X B = {(a, b) | a ∈ A y b ∈ B}. DEFINICIÓN 9: El producto cartesiano de los conjuntos A1 , A2 ,…, An , denotado por A1 x A2 x….xAn es el conjunto de n – tuplas ordenadas (a1 , a2 , …,an ), donde ai pertenece al conjunto Ai para i = 1, 2, 3, … , n. En otras palabras A1 x A2 x …xAn = {(a1 , a2 , …,an )| ai ∈ Ai para i = 1, 2, 3, … , n. OPERACIONES CON CONJUNTOS: § § § § § Unión Intersección Diferencia Diferencia Simétrica Complemento Profesor: José Alfredo Martínez Valdés 5 Universidad Nacional de Colombia Sede Palmira Matemática Fundamental ___________________________ Profesor: José Alfredo Martínez Valdés 6