UNIVERSIDAD DEL BIO BIO FACULTAD DE CIENCIAS

DEPARTAMENTO DE MATEMATICAS J.G./jg

LOGICA Y TEORIA DE CONJUNTO

LOGICA: Es el cimiento sobre el cual se construye la MATEMTICA. Conceptos: Proposicin: Corresponde a una frase, oracin o sentencia a la cual se le puede asignar un valor de verdad. Valor de Verdad: Corresponde al valor lgico de una expresin, esto es Verdadero Falso. Conectivos Lgicos: Son palabras claves u operadores que permiten enlazar dos o ms proposiciones simples formando as proposiciones ms complejas o compuestas. Los conectivos ms frecuentes son: Palabras Claves "No " "Y " O "Si entonces " " si y slo si " Operador P. Compuesta Negacin Conjuncin Disjuncin Condicional Bicondicional

Tipos de proposiciones Las proposiciones se clasican en simples y compuestas, esto es, las que no incluyen conectivos lgicos y las que si los incluyen. Combinaciones posibles de los valores de verdad segn el nmero de proposiciones Para lo que sigue, sean p, q, r, . proposiciones y V:=Verdadero , F:= Falso 1. n = 1 Unica proposicin p V F 2. n = 2 Dos proposiciones p q V V F V V F F F

3. n = 3 Tres proposiciones p V F V F V F V F q V V F F V V F F r V V V V F F F F

Obs.: El nmero de combinaciones de los valotres de verdad de n proposiciones simples viene dado por 2n Negacin (): Dada una proposicin p, se llama negacin de p y se escribe p, a la proposicin "No p", lo cual implica que p es Falsa cuando p es Verdadera, p es Verdadera cuando p es Falsa. Por lo anterior su tabla de verdad es p p V F F V Conjuncin (): Dadas dos proposiciones p y q, la conjuncin de ellas es la proposicin p y q, la cual se escribe p q. La conjuncin es Verdadera slo cuando ambas son Verdaderas en los otros casos siempre es Falsa. Por lo anterior la tabla de verdad es p q pq V V V F V F V F F F F F Disjuncin (): Dadas dos proposiciones p y q, la disjuncin de ellas es la proposicin p o q, la cual se escribe p q. La disjuncin es Falsa slo cuando ambas son Falsas en los otros casos siempre es Verdadera. Por lo anterior la tabla de verdad es p q pq V V V F V V V F V F F F Condicional (): Dadas dos proposiciones p y q, la condicional de ellas es la proposicin Si p entonces q, la cual se escribe p q. La condicional es Falsa slo cuando p es Verdadera y q es Falsa, en los otros casos siempre es Verdadera. Por lo anterior la tabla de verdad es

p q pq V V V F V V V F F F F V Obs: De la condicional p q se distinguen p antecedente, q consecuente. Tambin se lee "p es condicin suciente para q" "q es condicin necesaria para p" Bicondicional (): Dadas dos proposiciones p y q, la bicondicional de ellas es la proposicin p si y slo si q, la cual se escribe p q. La bicondicional es Verdadera cuando p y q coinciden en su valor de verdad. Por lo anterior la tabla de verdad es p q pq V V V F V F V F F F F V Obs: La bicondicional p q tambin se lee "p es condicin necesaria y suciente para q". Deniciones: Una proposicin se dice Tautologa ( o Teorema Lgico ) Si ella es siempre Verdadera cualquieran sean los valores de verdad de las proposiciones que la componen, es decir, si su tabla de verdad slo contiene valores Verdaderos. Contradiccin Si ella es siempre Falsa cualquiera sean los valores de verdad de las proposiciones que la componen, es decir, si su tabla de verdad slo contine valores Falsos. Contingencia Si ella contiene valores Verdaderos y valores Falsos. Implicacin Lgica Dadas dos proposiciones p y q, se dice que p implica lgicamente a q, si la proposicin p q es siempre Verdadera. En tal caso se escribe p q y se lee p implica q. Equivalencia Lgica Dadas dos proposiciones p y q, se dice que ellas son lgicamente equivalentes, si la proposicin p q es siempre Verdadera. En tal caso se escribe p q y se lee p es equivalente a q. Algunas Tautologas Importantes ( p) p (Doble Negacin) p q q p (Conmutatividad de ) p q q p (Conmutatividad de ) p q q p (Conmutatividad de ) (p q) r p (q r) (Asociatividad de ) (p q) r p (q r) (Asociatividad de ) (p q) r p (q r) (Asociatividad de )

p (q r) (p q) (p r) (Distributividad de con respecto a ) p (q r) (p q) (p r) (Distributividad de con respecto a ) (p q) p q ( Ley de DeMorgan para ) (p q) p q ( Ley de DeMorgan para ) (p q) p q p q q p ( Contrarecproca ) p q p q p q (p q) (q p) p q ( p q) (p q) Funcin Proposicional Se llama funcin proposicional ( f.p.) o enunciado abierto a una expresin p que contiene a una o ms variables y tal que ella se convierte en una proposicin lgica cuando se le asignan valores especcos a dichas variables. Conjunto de validez de una f.p. Llamaremos conjunto de validez de la f.p. p y lo denotaremos por Vp al conjunto de valores para los cuales la proposicin es verdadera. Cuanticadores Lgicos Para indicar que una f.p. es verdadera para cualquier elemento de un determinado conjunto, usaremos el smbolo el cual se lee para todo y se denomina cuanticador universal. Para indicar que una f.p. es verdadera para algunos elemento de un determinado conjunto, usaremos el smbolo el cual se lee existe y se denomina cuanticador existencial. Para indicar que una f.p. es verdadera para un nico elemento de un determinado conjunto, usaremos el smbolo ! el cual se lee existe un nico y se denomina cuanticador existencial unitario. Sean A un conjunto y p una f.p. que depende de una variable x, en tal caso escribiremos p(x) y se tienen las siguientes nomenclaturas: x A : p(x) lo cual se lee para todo x en A, p(x) es verdadera. x A : p(x) lo cual se lee existe x en A tal que p(x) es verdadera. Las negaciones de las proposiciones anteriores vienen dadas por: (x A : p(x)) (x A : p(x)) (!x A : p(x)) x A : p(x) x A : p(x) (x A : p(x)) (x A, y A, x = y : p(x) p(y))

Teoremas y Demostraciones Un teorema es una proposicin verdadera en la cual se debe mostrar su veracidad. Un teorema tiene la estructura Si H entonces T donde H corresponde a la Hiptesis la cual se asume verdadera y T es la tesis la cual debe ser demostrada. Estructura de Teoremas Implicacin: Si (hiptesis) entonces (tesis). (H T ) Los mtodos de demostracin son los siguientes: Mtodo Directo. Mtodos Indirectos. Contra-Recproca ( T H) Reduccin al absurdo (H T (H H) ( Contradiccin) Equivalencia: (Hiptesis ) si y slo si (Tesis). ( H T ) El mtodo de demostracin es (H T ) (T H) Equivalencia de n proposiciones: p1 p2 p3 pn , Directo p1 p2 p2 p3 . Usando transitividad [(pi pj ) (pj pk )] (pi pk ) Discreto: n N : p(n) El mtodo de demostracin es mediante Induccin Matemtica. Obs.: La falsedad de una proposicin se puede demostrar usando un ejemplo que muestre aquello, el cual se denomina Contraejemplo Ejemplos de demostracin: Proposicin 1: Para a N. Si a es par, entonces a2 es par. Demostracin Directa: Indenticamos H:= a es par ; T:= a2 es par. Si a es par entonces n N tal que a = 2n Si a = 2n entonces a2 = (2n)2 = 4n2 = 2 2n2 es decir a2 es par. 2 Proposicin 2: Sea a N. Si a es par entonces a es par. Demostracin por Contradiccin: Indenticamos H:= a2 es par ; T:= a es par. Supongamos H T , es decir a2 es par y a impar, en tal caso se tendr Si a es impar entonces a = 2n + 1 para algn n N Si a = 2n + 1 entonces a2 = (2n + 1)2 = 4n2 + 4n + 1 = 2(2n2 + 2n) + 1 es decir a2 es impar. Por lo tanto a2 es par y a2 es impar (H H) (contradiccin) Conjuntos Llamaremos conjunto al agrupamiento de entes. A los entes les llamaremos elementos. Llamaremos conjunto Universo o Referencial y lo denotaremos por U a aquel conjunto que contiene a todos los elementos, llamaremos conjunto vaco a aquel que no tiene elementos. Denotaremos a los conjuntos por letras maysculas y a los elementos por letras minsculas. n > 2 Mtodo de demostracin

Conjuntos Numricos N := Nmeros Naturales. Denidos por N = { 1 o sumas reiteradas de 1} = {1, 2, 3, } N0 := Nmeros Cardinales. Denidos por N0 = N {0} = {0, 1, 2, 3, } Z := Nmeros Enteros. Denidos por Z = N {0} N = { , 3, 2, 1, 0, 1, 2, 3, } a Q := Nmeros Racionales. Denidos por Q = { ; a, b R b = 0} b I := Nmeros Irracionales. Denidos por I = {x; x no se puede escribir como racional} R := Nmeros Reales. Denidos por R = Q I. Su grca es la recta real. Obs.: Notar que N N0 Z Q ; QI= ; QI=R

Inclusin de Conjuntos Dados dos conjuntos A y B, se dice que A es subconjunto de B y en tal caso se escribe A B, si todos los elementos de A se encuentran dentro de B, es decir A B (x U : x A x B) Algunas propiedades de la inclusin Dados A, B y C conjuntos cualquiera, entonces se tiene: AU AA (A B B C) A C ley de transitividad. Igualdad de Conjuntos Dados dos conjuntos A y B, se dir que ellos son iguales y en tal caso se denotar por A = B, si los elementos de A coinciden con los elementos de B y viceversa, esto es A = B (A B) (B A) Conjunto de las Partes de un Conjunto Dado Dado un conjunto A, se dene el conjunto de las partes de A y se denota por P (A), como el conjunto cuyos elementos son todos los subconjuntos del conjunto A, es decir P (A) := {X : X A} Obs.: Los elementos de P (A) son conjuntos. P (A) = pues A son subconjuntos de A. Operaciones entre conjuntos Sean U el conjunto Universo y A , B dos subconjutos de U La Unin de A y B Esta es denotada por A B y corresponde a la coleccin de todos los elementos que estn en A o en B, esto es A B := {x U : x A x B} La Interseccin de A y B Esta es denotada por A B y corresponde a la coleccin de todos los elementos comunes entre A y B, esto es A B := {x U : x A x B}

Propiedades de la Unin e Interseccin AA=A , A A = A Idempotencia. A B = B A Conmutatividad de y .

AB =BA ,

A (B C) = (A B) C Asociatividad de . A (B C) = (A B) C Asociatividad de . A (B C) = (A B) (A C) Distributividad de con respecto de . A (B C) = (A B) (A C) Distributividad de con respecto de . (A B)c = Ac B c Ley de DeMorgan. (A B)c = Ac B c Ley de DeMorgan. La Diferencia entre A y B, denotado por A B, corresponde al conjunto A B := {x U : x A x B} / El Complemento de A con respecto a U , el cual se denota por Ac , es el conjunto U A, o ms precisamente Ac := {x U : x A} / Obs.: x U se tiene x A c = U Uc = (Ac )c = A Deniciones Dos conjuntos A y B se dicen disjuntos si y slo si A B = Dados dos conjuntos no vacos A y B se dene el producto Cartesiano entre ellos, el cual es denotado por A B, al nuevo conjunto cuyos elementos son pares ordenados de la forma (a, b) tal que a pertenece a A y b pertenece a B, esto es A B = {(a, b) : a A b B} Dados n conjuntos no vacos A1 , A2 , , An se dene el producto cartesiano entre ellos, el cual es denotado por A1 A2 An , como el conjunto de todas las nuplas ordenadas de la forma (a1 , a2 , , an )tal que ai pertenece a Ai , es decir A1 A2 An := {(a1 , a2 , , an ) : ai Ai , i {1, , n}} Particin de un conjunto Sean A1 , A2 , , An subconjuntos de un conjunto B. Diremos que {A1 , A2 , , An } es una particin del conjunto B, si ellos son no vacos, disjuntos dos a dos y su unin es el conjunto B, es decir, si y slo si Ai = , para cada i {1, 2, , n} Ai Aj = para cada i = j x Ac

Ai = B
i=1

Cardinalidad Corresponde al nmero de elementos que tiene un conjunto, es denotado por |A|. Propiedades Si A y B son conjuntos disjuntos, entonces |A B| = |A| + |B| Si A y B son conjuntos arbitrarios, entonces |A B| = |A| + |B| |A B|

Micelaneas 1. Determine el valor de verdad de cada una de las proposiciones p, q, r y s, sabiendo que la proposicin compuesta [(p q) r] (s p) es falsa. Justique adecuadamente. 2. Se sabe que la proposicin compuesta ( pq) (F p) es verdadera, siendo p y q proposiciones simples. Determine el valor de verdad de la proposicin p q 3. Considere las siguientes proposiciones: P Q R S Se pide: a) Determine y justique el valor de verdad de las proposiciones dadas. b) Determine el valor de verdad de la proposicin "P R Q S". c) Escriba la proposicin contrareciproca de Q. d ) D un ejemplo de las proposiciones falsas. 4. Considere la proposicin p := ( > o)(n N)( Se pide: Niege la proposicin p. Determine el valor de verdad de la proposicin p. 5. Deduzca una frmula para |A B C| 6. Para A y B conjuntos cualquiera. Muestre que: Ac B c (A B)c Mediante un ejemplo muestre que la igualdad no es verdadera. 7. Dados los conjuntos: U = {n Z/|n| 5} , A = {n U/n + 3 U } ; B = {n U/1 < |n 1| 2} y C = {n U/ n Z}. Se pide: a) Muestre por extensin los conjuntos anteriores. b) Determine los conjuntos i.- (A B) (C B)c ii.- (Ac C)c 1 1 +1< ) n n := := := := Si x A B entonces x A x B / / / c c Si A B entonces B A Si A B = entonces B = xAB xA / /

8. Dados los conjuntos: U = {n Z/ 1 n1 < 1} , A = {n U/n es primo } ; B = {n 4 U/9 < n2 25} y C = {|n| : n U }. Se pide: a) Muestre por extensin los conjuntos anteriores. b) Determine los conjuntos i.- (A B) (C c A) ii.- (Ac C)c

9. Considere los siguientes conjuntos A = x R / (x2 + 1)(x + 2)(x2 3)(x + 1)2 = 0 B = {x Z / 2x + 6 > 0 y 3x 3 0} C = {x R / x es cardinal par menor que 9}

a) Escriba los conjuntos A, B y C por extensin. b) Construya un nico diagrama de Venn que muestre los conjuntos A, B y C. c) Determine los conjuntos i.-) A B ii.-) B C iii.-) (A C) (B C)

10. Demuestre las siguientes igualdades de conjuntos (A B) (B A) = (A B) (A B) [Ac (B c C)]c (C c B)c = A(BC) 11. Se encuestan a alumnos de primer ao de ingeniera sobre los efectos del terremoto en sus hogares, despus de la primera semana, obtenindose la siguiente informacin: 15 slo no tenan luz; 5 no tenan agua ni luz; 6 no tenan agua ni combustible; 20 no tenan luz; 8 no tenan agua ; a 9 slo les falto combustible y 3 no tenan ni agua ni luz ni combustible. De los encuestados slo 8 no sufrieron ningn problema por encontrarse fuera de la zona damnicada. se pide: a) Represente la situacin en un nico diagrama de Venn. b) Cuntos alumnos fueros encuestados?. c) A cuntos les falt slo agua?. Represntelos en trminos de conjunto. d ) A cuntos les falto luz o agua , pero no combustible?. Represntelos en trminos de conjuntos. 12. En un grupo de 100 estudiantes, 49 no llevan el curso de clculo y 53 no siguen el curso de lgebra. Si 27 alumnos no siguen clculo ni lgebra, Cuntos alumnos llevan exactamente uno de tales cursos?. 13. Un club deportivo consta de 79 socios, de los cuales 52 practican futbol, 36 basket, 49 tenis, 63 ftbol o basket. si 15 practican solamente ftbol y basket y 16 solamente tenis: a) Cuntos socios practican los tres deportes? b) Cuntos socios practican a lo menos dos de los tres deportes?.