Post on 11-Aug-2015
ALGEBRA y ALGEBRA LINEAL
520142Primer Semestre
CAPITULO ILOGICA Y CONJUNTOS.
DEPARTAMENTO DE INGENIERIA MATEMATICA
Facultad de Ciencias Físicas y Matemáticas
Universidad de Concepción1
Lógica
“La lógica es la herramienta con quese construye el edificio llamado Matemática”
Conceptos primitivos
Los valores de verdad VERDADERO (V ) y FALSO (F ) son los conceptosprimitivos de la lógica.
Proposición
Una proposición es una sentencia (expresión) sujeta a un valor de verdad.
Usualmente se denotan por letras minúsculas p, q, r, s, etc.
2
Lógica
Ejemplos
¿ Cuáles de las siguientes afirmaciones son proposiciones ?
¿ Es esto verdadero ?
Hoy es martes
10 es un número primo
El sol y el cielo
Todos los alumnos de este curso son estudiosos
La realidad de la vida
3
Lógica
Conectivos lógicos
Un conectivo lógico es una operación que nos permite obtener nuevasproposiciones a partir de otras dadas. Los conectivos básicos son:
negación (∼) (“no”)
conjunción (∧) (“y”)
disyunción (∨) (“o”)
condicional (→) (“si. . . , entonces”)
bicondicional (↔) (“si y sólo si”)
4
Lógica
Tipos de proposiciones
Las proposiciones se clasifican en simples y compuestas, vale decir, lasque no incluyen conectivos lógicos, y las que sí los incluyen.
Valores posibles de dos proposiciones dadas
p q
V V
V F
F V
F F
5
Lógica
Negación (∼)
Dada una proposición p, se llama negación de p, y se escribe ∼ p, a laproposición “no p”. Esto significa que ∼ p es V si p es F , y ∼ p es F si p
es V .
TABLA DE VERDAD
p ∼ p
V F
F V
6
Lógica
Conjunción (∧)
Dadas dos proposiciones p y q, la conjunción de ellas es la proposición“p y q”, la cual se escribe p∧ q. La proposición p∧ q es V si ambas lo son,y p ∧ q es F si al menos una de ellas lo es.
TABLA DE VERDAD
p q p ∧ q
V V V
V F F
F V F
F F F
7
Lógica
Disyunción (∨)
Dadas dos proposiciones p y q, la disyunción de ellas es la proposición “po q”, la cual se escribe p ∨ q. La proposición p ∨ q es V si al menos unade ellas lo es, y p ∨ q es F si ambas lo son.
TABLA DE VERDAD
p q p ∨ q
V V V
V F V
F V V
F F F
8
Lógica
Condicional (→)
Dadas dos proposiciones p y q, la condicional de ellas es la proposición“si p entonces q”, la cual se escribe p → q. Aquí, p se llama antecedentey q consecuente. También, p → q se lee “p es condición suficiente paraq”, o bien “q es condición necesaria para p”. La proposición p → q es F
sólo si p es V y q es F .
TABLA DE VERDAD
p q p→ q
V V V
V F F
F V V
F F V
9
Lógica
Bicondicional (↔)
Dadas dos proposiciones p y q, la bicondicional de ellas es la proposición“p si y sólo si q”, la cual se escribe p ↔ q. También, p ↔ q se lee “p escondición necesaria y suficiente para q”. La proposición p↔ q es V sólosi ambas proposiciones tienen el mismo valor de verdad.
TABLA DE VERDAD
p q p↔ q
V V V
V F F
F V F
F F V
10
Lógica
Definiciones varias
Una proposición se dice una:
TAUTOLOGIA (o TEOREMA LOGICO), si ella es siempre V ,cualesquiera sean los valores de verdad de las proposicionessimples que la componen, es decir, si su tabla de verdad sólocontiene valores V .
CONTRADICCION, si ella es siempre F .
CONTINGENCIA, si no es tautología ni contradicción.
11
Lógica
Implicación lógica
Dadas dos proposiciones p y q, se dice que p implica lógicamente q, si laproposición p → q es siempre verdadera. En tal caso se escribe p ⇒ q yse lee “p implica q”.
Equivalencia lógica
Dadas dos proposiciones p y q, se dice que ellas son lógicamenteequivalentes, si la proposición p ↔ q es siempre verdadera. En tal casose escribe p⇔ q y se lee “p es equivalente a q”.
12
Lógica
Algunas tautologías importantes
∼ (∼ p) ⇔ p (doble negación)
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↔)
13
Lógica
Algunas tautologías importantes (continuación)
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 De Morgan para ∧)
∼ (p ∨ q) ⇔ ∼ p ∧ ∼ q (Ley de De Morgan para ∨)
∼ (p→ q) ⇔ p∧ ∼ q
p→ q ⇔ ∼ q →∼ p (contrarecíproca)
p→ q ⇔ ∼ p ∨ q
p↔ q ⇔ (p→ q) ∧ (q → p)
p↔ q ⇔ (∼ p ∧ ∼ q) ∨ (p ∧ q)
14
Lógica
Función proposicional
Se llama función proposicional (o enunciado abierto) a una expresión p
que contiene una o más variables, y tal que ella se convierte en unaproposición lógica cuando se le asignan valores específicos a dichasvariables.
Conjunto de validez
Se llama Conjunto de validez de una función proposicional p, y se denotapor Vp, al conjunto de valores (o n-uplas de valores) para los cuales dichafunción es verdadera.
Ejercicio Analice la siguiente proposición:
Si un número natural es divisible por dos y tres, entonces es divisible por
seis.15
Lógica
Cuantificadores lógicos
Para indicar que una función proposicional es verdadera paracualquier elemento de un determinado conjunto A se usa elsímbolo ∀, el cual se llama cuantificador universal.
∀ se lee: “para todo”, “cualquiera sea”, “para cada”.
Para indicar que una función proposicional es verdadera paraalgunos elementos de un determinado conjunto A se usa elsímbolo ∃, el cual se llama cuantificador existencial.
∃ se lee: “existe (un)”, “existe al menos un”, “existe algún”.
Para indicar que una función proposicional es verdadera para unúnico elemento de un determinado conjunto A se usa el símbolo ∃!.
∃! se lee: “existe un único”.
16
Lógica
Más sobre cuantificadores lógicos
Sean A un conjunto y p una función proposicional que depende de unavariable x (en tal caso se escribe p(x)).
∀x ∈ A : p(x) se lee “para todo x en A, p(x) es verdadera”.
∃x ∈ A : p(x) se lee “existe x en A tal que p(x) es verdadera”.
Negaciones importantes
∼ ( ∀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 6= y : p(x) ∧ p(y) )
17
Lógica
Teoremas y demostraciones
Un teorema es una proposición verdadera de cierta relevancia para unateoría y cuya verdad debe ser demostrada.
Algunas estructuras de teoremas
Implicación: Si (hipótesis), entonces (tesis) (H → T )
Métodos de demostración:
Método directo.
Métodos indirectos:contra-recíproca (∼ T →∼ H).reducción al absurdo (H∧ ∼ T )→ (p∧ ∼ p) (contradicción).
18
Lógica
Equivalencia: (Hipótesis) si y sólo si (tesis) (H ↔ T )
Método de demostración: (H → T ) ∧ (T → H)
Equivalencia de n proposiciones:P1 ↔ P2 ↔ · · · ↔ Pn, n > 2
Métodos de demostración
Directo: P1 ↔ P2 y P2 ↔ P3, etc.
Usando transitividad: [(Pi → Pj) ∧ (Pj → Pk)]→ (Pi → Pk).(e.g., mostrar que Pi → Pi+1, i = 1, ...n− 1, y Pn → P1).
Discreto: ∀n ∈ N : p(n)
Método de demostración: Inducción Matemática.
La falsedad de una proposición se puede demostrar usando un contra-ejemplo.
19
Lógica
Ejemplos de demostración:
Proposición 1: Sea a ∈ N. Si a es par entonces a2 es par.Dem. (directa) Hipótesis: a es par
entonces a = 2n para algún n ∈ N,
entonces a2 = (2n)2 = 4n2 = 2(2n2),
entonces a2 es par (pues 2n2 ∈ N), � (Q.E.D.)
Proposición 2: Sea a ∈ N. Si a2 es par entonces a es par.Dem. (contradicción) se supone H∧ ∼ T : a2 es par y a es impar.
entonces a = 2n + 1 para algún n ∈ N,
entonces a2 = (2n + 1)2 = 4n2 + 4n + 1,
entonces a2 es impar (por Prop. 1 y “suma de nros. pares es par”),
entonces a2 par y a2 impar (p∧ ∼ p), CONTRADICCION (→←)
20
Conjuntos
Llamaremos conjunto a cualquier colección de objetos determinados ydistintos. Los objetos los llamaremos elementos del conjunto. Dosconjuntos importantes son el conjunto vacío, que no contiene elementos,y el conjunto universo, que contiene todos los elementos.
Notación
Los conjuntos: A, B, · · ·
Los elementos: a, b, · · ·
a pertenece a A: a ∈ A
a no pertenece a A: a /∈ A
Conjunto vacío: φ
Conjunto universo: U
21
Conjuntos
Observación
Dado x ∈ U y un conjunto A: ¿ x ∈ A ∨ x /∈ A ?Si esta pregunta puede responderse siempre, entoncesse dice que A está bien definido .
Maneras de definir un conjunto
Por extensión, vale decir mostrando los elementos de A.
Ejemplo : A = N := { 1, 2, 3, · · · } (Números naturales)
Por comprensión, esto es dando una propiedad (o proposición) quecaracterice a los elementos del conjunto.
Ejemplo : Q :={ a
b: a, b ∈ Z, b 6= 0
}
(Números racionales)
22
Conjuntos
Inclusión de conjuntos
Dados dos conjuntos A y B, se dice que A es subconjunto de B, y seescribe A ⊆ B, si todos los elementos de A están también en B, esto es:
A ⊆ B ⇔ (∀x ∈ U : x ∈ A ⇒ x ∈ B)
Propiedades de la inclusión
Dados A, B, C conjuntos, se tiene
φ ⊆ A ⊆ U
A ⊆ A
(A ⊆ B ∧ B ⊆ C)⇒ A ⊆ C
23
Conjuntos
Igualdad de conjuntos
Dados dos conjuntos A y B, se dice que A y B son iguales, y se escribeA = B, si los elementos de A y B coinciden, esto es:
A = B ⇔ (A ⊆ B) ∧ (B ⊆ A)
Conjunto de las partes de un conjunto dado
Dado un conjunto A, se define el conjunto de las partes de A, y se denotaP(A), como el conjunto de todos los subconjuntos de A, esto es:
P(A) := {X : X ⊆ A }
Notar que:
i) los elementos de P(A) son conjuntos;
ii) P(A) 6= φ ya que φ, A ∈ P(A).24
Conjuntos
Operaciones entre conjuntos
Sea U el conjunto universo, y sean A, B subconjuntos de U .
La diferencia de A y B es el conjunto
A−B := {x ∈ U : x ∈ A ∧ x 6∈ B }
(otra notación: A \B).El Complemento de A con respecto a U , el cual se denota Ac
(o bien A′, −A), es el conjunto U −A, vale decir:
Ac := U −A = {x ∈ U : x 6∈ A }
Algunas propiedades
Para todo x ∈ U se tiene: x ∈ A ∨ x ∈ Ac
φc = U ∧ U c = φ
(Ac)c = A 25
Conjuntos
Otras operaciones entre conjuntos
Sea U el conjunto universo, y sean A, B subconjuntos de U .
La intersección de A y B, la cual se denota A ∩B, es el conjunto detodos los elementos comunes a A y B, esto es
A ∩B := {x ∈ U : x ∈ A ∧ x ∈ B }
La unión de A y B, la cual se denota A ∪B, es el conjunto de todoslos elementos que están en A o en B, esto es
A ∪B := {x ∈ U : x ∈ A ∨ x ∈ B }
26
Conjuntos
Propiedades de ∩ y ∪
A ∪A = A , A ∩A = A (idempotencia)
A ∪B = B ∪A , A ∩B = B ∩A (conmutatividad de ∪ y ∩)
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 a ∩)
A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C)
(distributividad de ∩ con respecto a ∪)
(A ∪B)c = Ac ∩Bc (Ley de De Morgan)
(A ∩B)c = Ac ∪Bc (Ley de De Morgan)
27
Conjuntos
Más definiciones
Dos conjuntos A y B se dicen disjuntos si y sólo si A ∩B = φ.
Dados dos conjuntos no vacíos A y B, se define el ProductoCartesiano de ellos, el cual se denota por A×B, como el conjuntode todos los pares ordenados (a, b) tales que a pertenece a A y b
pertenece a B, esto es
A×B := { (a, b) : a ∈ A ∧ b ∈ B }
Dados n conjuntos no vacíos A1, A2, ..., An, se define el ProductoCartesiano de ellos, el cual se denota por A1 ×A2 × · · · ×An, comoel conjunto de todas las n-uplas ordenadas (a1, a2, ..., an) tales queai pertenece a Ai para cada i ∈ {1, ..., n}, esto es
A1 ×A2 × · · · ×An := { (a1, a2, ..., an) : ai ∈ Ai , i ∈ {1, ..., n} }
28
Conjuntos
Partición de un conjunto
Sean A1, A2, ..., An subconjuntos de un conjunto B. Se dice que{A1, A2, ..., An } es una PARTICION de B si estos conjuntos son novacíos, disjuntos dos a dos y su unión es el conjunto B, vale decir siy sólo si:
Ai 6= φ, para cada i ∈ {1, ..., n}.
Ai ∩Aj = φ para cada i 6= j.
n⋃
i=1
Ai = B.
29
Conjuntos
Cardinalidad
El número de elementos de un conjunto finito A se llama cardinalidad deA y se denota |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|.
Si A, B y C son conjuntos arbitrarios, entonces
|A∪B∪C| = |A|+ |B|+ |C|−|A∩B|−|A∩C|−|B∩C|+ |A∩B∩C| .
30
Ejemplos
Ejemplo 1
Considere la siguiente proposición:
p : (∀ ǫ > 0)(∃m ∈ N)
(
1
m≤ ǫ −→
1
m+ 1 < ǫ
)
.
a) Niegue la proposición p.
b) Determine si la proposición p es verdadera o falsa.
Solución
a) ∼ p : (∃ ǫ > 0)(∀N ∈ N)
(
1
N≤ ǫ ∧
1
N+ 1 ≥ ǫ
)
.
b) La proposición es falsa, basta considerar ǫ = 1, pues, para todoN ∈ N
1
N≤ 1 = ǫ ∧
1
N+ 1 ≥ 1 = ǫ.
31
Ejemplos
Ejemplo 2
Sean A y B subconjuntos del universo U .
a) Pruebe que Ac ×Bc ⊆ (A×B)c.
b) ¿Por qué no es verdadera la igualdad?.
32
Ejemplos
Solución
a) Probemos que Ac ×Bc ⊆ (A×B)c.Sea (x, y) ∈ Ac ×Bc.
(x, y) ∈ Ac ×Bc =⇒ x ∈ Ac ∧ y ∈ Bc por def. de producto cartesiano
=⇒ x /∈ A ∧ y /∈ B por definición de complemento
=⇒ (x, y) /∈ A×B por def. de producto cartesiano
=⇒ (x, y) ∈ (A×B)c por definición de complemento
∴ Ac ×Bc ⊆ (A×B)c.
b) La igualdad no es válida, basta considerar por ejemplo
U = {1, 2, 3}, A = {1, 2} = B.
33