Teoria De Coinjuntos

´ CAP´ ITULO 1. FUNDAMENTOS DE LOGICA Y TEOR´ DE CONJUNTOS IA

1. L´gica o
1.1 Definici´n. Una proposici´n es una oraci´n declarativa de la cual se puede o o o decir sin ambig¨edad si es verdadera o falsa. u 1.2 Definici´n. Sea p y q proposiciones. Vamos a definir nuevas proposiciones a o partir de ´stas: e i) Definimos la proposici´n ¬p como “no p”. Esta es verdadera si p es falsa y falsa si o pes verdadera. o a ii) Definimos la proposici´n p ∨ q como “p o q”. Esta ser´ verdadera cuando p, q o ambas son verdaderas y falsa cuando p y q lo son. iii) Definimos p ∧ q como “p y q”. Esta es verdadera cuando p y q lo son y falsa en otro caso. iv) Definimos p ⇒ q como “si p entonces q”. Esta es verdadera excepto cuando p es verdadera y q es falsa. v) Definimos p ⇔ q como “p si y s´lo si q”. Esta esverdadera cuando ambas son o verdaderas o ambas falsas y falsa en otro caso. Si p ⇔ q es verdadera diremos que p y q son equivalentes. La proposici´n p ⇔ q coincide con (p ⇒ q) ∧ (q ⇒ p). o Si 1 representa verdadero y 0 falso, lo anterior se puede resumir en la siguiente tabla: 1

Juan Medina Molina

Universidad Polit´cnica de Cartagena e

p 1 1 0 0

q 1 0 1 0

p∨q

1 1 1 0

p∧q1 0 0 0

p⇒q

1 0 1 1

p⇔q

1 0 0 1

Notas. Sean p y q proposiciones: i) p ⇒ q es verdadera ⇔ ¬q ⇒ ¬p es verdadera. La proposici´n ¬q ⇒ ¬p recibe el o nombre de contrarec´ ıproco de p ⇒ q. e ii) p ⇒ q es verdadera ⇔ p ∧ ¬q ⇒ ¬p es verdadera. Tambi´n p ⇒ q es verdadera ⇔ p ∧ ¬q ⇒ q es verdadera. Cuando para demostrar que p ⇒ q es verdadera se prueba la veracidad de una de lasproposiciones anteriores, se dice que que se demuestra p ⇒ q por reducci´n al absurdo y cuando se logra, se dice que hemos llegado a contradicci´n. o o Demostraci´n. i) o (⇒) Si p ⇒ q es verdadera entonces: p es verdadera y q es verdadera. Entonces ¬q es falsa luego ¬q ⇒ ¬p es verdadera. p es falsa y q es verdadera. Entonces ¬q es falsa luego ¬q ⇒ ¬p es verdadera. p es falsa y q es falsa. Entonces ¬q esverdadera y ¬p es verdadera luego ¬q ⇒ ¬p es verdadera. (⇐) ejercicio. ii) (⇒) Si p ⇒ q es verdadera veamos en primer lugar que p ∧ ¬q ⇒ ¬p es verdadera. Si p es verdadera y q es verdadera entonces ¬q es falsa luego p ∧ ¬q es falsa y entonces p ∧ ¬q ⇒ ¬p es verdadera. Si p es falsa y q es verdadera entonces p ∧ ¬q es falsa luego p ∧ ¬q ⇒ ¬p es verdadera. Si p es falsa y q es falsa entonces p ∧ ¬q esfalsa luego p ∧ ¬q ⇒ ¬p es verdadera. 2

Juan Medina Molina

Universidad Polit´cnica de Cartagena e

(⇐) y lo dem´s, ejercicio. a 1.3 Definici´n. Un teorema es una proposici´n de uno de los tipos siguientes: o o (I) p ⇒ q verificando: a) p ⇒ q es verdadera. b) p es verdadera. c) Existe una relaci´n de causa y efecto entre p y q. o (II) (p ⇒ q) ∧ (q ⇒ p) cuando p ⇒ q y q ⇒ p son teoremas. Sedenota por p ⇔ q. El teorema p ⇒ q se lee p implica q o p es condici´n suficiente para q o q es o condici´n necesaria para p. o Si p ⇒ q es un teorema, a la proposici´n p se le llama hip´tesis y a la proposici´n q o o o se le llama tesis. As´ una proposici´n p ⇒ q es teorema si se deduce la veracidad de q de que p es ı, o verdadera. El teorema p ⇔ q se lee p si y s´lo si q o p es condici´n necesaria ysuficiente o o para q. 1.4 Ejemplos. 1. Sean p = “2 + 2 = 5” y q = “2 + 3 = 5”. Aunque la proposici´n p ⇒ q es verdadera, p ⇒ q no es teorema dado que p no es o verdadera. 2. Supongamos que la proposici´n p = “Yo tengo un perro” es verdadera y q = o “2 + 2 = 4”. Entonces p ⇒ q es verdadera, p es verdadera pero no es un teorema dado o que no existe una relaci´n de causa y efecto entre p y q. 3.Supongamos que la pasada noche estuve en el cine de las 10:00 a las 12:00. Sea p =“ Estuve en el cine de 10:00 a 12:00” y q =“No estuve en el bar a las 10:30 de la noche”. Entonces p ⇒ q es un teorema.

3

Juan Medina Molina

Universidad Polit´cnica de Cartagena e

2. Conjuntos
Damos la definici´n de conjunto dada por G. Cantor: o 2.1 Definici´n. Un conjunto es la reuni´n en un todo de...