View
350
Download
0
Category
Preview:
Citation preview
UNIVERSIDAD DE CONCEPCION
Facultad de Ciencias Fısicas y Matem aticas
Introducci on a la Matem atica Universitaria.
520145
Capıtulo 1. L ogica y Conjuntos.
Prof. Antonio Contreras Quilodran.
Logica y Conjuntos 1 . FCFM.UdeC.
Logica
Conceptos primitivos
Los valores de verdad VERDADERO (V ) y FALSO (F ) son los
conceptos primitivos de la logica.
Proposicion
Una proposici on es una sentencia declarativa (que afirma o niega
algo de algun sujeto) que posee un unico valor de verdad, pudiendo
ser verdadera (V) o bien ser falsa (F).
Usualmente se denotan por letras minusculas p, q, r, s, etc.
Logica y Conjuntos 2 . FCFM.UdeC.
Logica
Conectivos logicos
Un conectivo l ogico es un operador que nos permite obtener
nuevas proposiciones a partir de otras dadas. Los conectivos
basicos son:
• negacion (∼) (“no”)
• conjuncion (∧) (“y”)
• disyuncion (∨) (“o”)
• condicional (→) (“si. . . , entonces”)
• bicondicional (↔) (“si y solo si”)
Logica y Conjuntos 3 . FCFM.UdeC.
Logica
Tipos de proposiciones
Las proposiciones se clasifican en simples y compuestas , vale
decir, las que no incluyen conectivos logicos, y las que sı los
incluyen.
Valores posibles de dos proposiciones dadas
p q
V V
V F
F V
F F
Logica y Conjuntos 4 . FCFM.UdeC.
Logica
Negacion (∼)
Dada una proposicion p, se llama negaci on de p, y se escribe
∼ p, a la proposicion “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
Logica y Conjuntos 5 . FCFM.UdeC.
Logica
Conjuncion (∧)
Dadas dos proposiciones p y q, la conjunci on de ellas es la
proposicion “p y q”, la cual se escribe p ∧ q. Ası, 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
Logica y Conjuntos 6 . FCFM.UdeC.
Logica
Disyuncion (∨)
Dadas dos proposiciones p y q, la disyunci on de ellas es la
proposicion “p o q”, la cual se escribe p ∨ q. Ası, p ∨ q es V si al
menos una de 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
Logica y Conjuntos 7 . FCFM.UdeC.
Logica
Condicional (→)
Dadas dos proposiciones p y q, la condicional de ellas es la
proposicion “si p entonces q”, la cual se escribe p→ q. Aquı, p se
llama antecedente y q consecuente. Tambien, p→ q se lee “p es
condicion suficiente para q”, o bien “q es condicion necesaria para
p”. Ası, p→ q es F solo si p es V y q es F .
Logica y Conjuntos 8 . FCFM.UdeC.
Logica
Condicional (→)
TABLA DE VERDAD
p q p→ q
V V V
V F F
F V V
F F V
p q p↔ q
V V V
V F F
F V F
F F V
Logica y Conjuntos 9 . FCFM.UdeC.
Logica
Bicondicional (↔)
Dadas dos proposiciones p y q, la bicondicional de ellas es la
proposicion “p sı y solo sı q”, la cual se escribe p↔ q. Tambien,
p↔ q se lee “p es condicion necesaria y suficiente para q”. Ası,
p↔ q es V solo si ambas proposiciones tienen el mismo valor de
verdad.
Logica y Conjuntos 10 . FCFM.UdeC.
Logica
Definiciones varias
Una proposicion compuesta se dice una:
• TAUTOLOGIA (o TEOREMA LOGICO ), si ella es siempre V ,
cualesquiera sean los valores de verdad de las proposiciones
simples que la componen, es decir, si su tabla de verdad solo
contiene valores V .
• CONTRADICCION, si ella es siempre F .
• CONTINGENCIA, si no es tautologıa ni contradiccion.
Logica y Conjuntos 11 . FCFM.UdeC.
Logica
Implicacion logica
Dadas dos proposiciones p y q, se dice que p implica
logicamente q, si la proposicion p→ q es una tautologıa. En tal
caso se escribe p⇒ q y se lee “p implica q”.
Equivalencia logica
Dadas dos proposiciones p y q, se dice que ellas son logicamente
equivalentes , si la proposicion p↔ q es verdadera. En tal caso
se escribe p⇔ q y se lee “p es equivalente a q”.
Logica y Conjuntos 12 . FCFM.UdeC.
Logica
Algunas tautologıas importantes
• ∼ (∼ p) ⇔ p (doble negacion)
• 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↔)
Logica y Conjuntos 13 . FCFM.UdeC.
Logica
Algunas tautologıas importantes (continuacion)
• 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 ⇔ ∼ q →∼ p (contrarecıproca)
• p→ q ⇔ ∼ p ∨ q
• p↔ q ⇔ (p→ q) ∧ (q → p)
Logica y Conjuntos 14 . FCFM.UdeC.
Logica
Funcion proposicional
Se llama funci on proposicional (o enunciado abierto ) a una
expresion p que contiene una o mas variables, y tal que ella se
convierte en una proposicion logica cuando se le asignan valores
especıficos a dichas variables.
Conjunto de validez
Se llama Conjunto de validez de una funcion proposicional p, y se
denota por Vp, al conjunto de valores (o n-uplas de valores) para
los cuales dicha funcion es verdadera.
Logica y Conjuntos 15 . FCFM.UdeC.
LogicaCuantificadores logicos
• Para indicar que una funcion proposicional es verdadera para
cualquier elemento de un determinado conjunto U se usa el
sımbolo ∀, el cual se llama cuantificador universal .
∀ se lee: “para todo”, “cualquiera sea”, “para cada”.
• Para indicar que una funcion proposicional es verdadera para
algun elemento de un determinado conjunto U se usa el
sımbolo ∃, el cual se llama cuantificador existencial y se lee:
“existe (un)”, “existe al menos un”, “existe algun”.
• Para indicar que una funcion proposicional es verdadera para
un unico elemento de un determinado conjunto U se usa el
sımbolo ∃! y se lee: “existe un unico”.
Logica y Conjuntos 16 . FCFM.UdeC.
Logica
Mas sobre cuantificadores logicos
Sean A un conjunto y p una funcion proposicional que depende de
una variable 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”.
Logica y Conjuntos 17 . FCFM.UdeC.
Logica
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) )
Logica y Conjuntos 18 . FCFM.UdeC.
Logica
Teoremas y demostraciones
Un teorema es una proposicion verdadera de cierta relevancia para
una teorıa y cuya verdad debe ser demostrada.
Algunas estructuras de teoremas
• Implicaci on : Si (hipotesis), entonces (tesis) (H ⇒ T )
Metodos de demostracion:
– Metodo directo.
– Metodos indirectos: contra-recıproca (∼ T ⇒∼ H),
reduccion al absurdo (H∧ ∼ T )⇒ (p∧ ∼ p)
(contradiccion).
Logica y Conjuntos 19 . FCFM.UdeC.
Logica
• Equivalencia : (Hipotesis) si y solo si (tesis) (H ⇔ T )
Metodo de demostracion: (H ⇒ T ) ∧ (T ⇒ H)
• Equivalencia de varias proposiciones :
P1 ⇔ P2 ⇔ P3.
Metodos de demostracion
– Directo: P1 ⇔ P2 y P2 ⇔ P3.
– Usando transitividad. Mostrar que:
P1 ⇒ P2, P2 ⇒ P3, y P3 ⇒ P1.
• Discreto : ∀n ∈ N : p(n)
Metodo de demostracion: Induccion Matematica.
Logica y Conjuntos 20 . FCFM.UdeC.
Logica
La falsedad de una proposicion con cuanfificadores universales se
puede demostrar usando un contra-ejemplo . Es decir, excibiendo
un valor para el cual la funcion proposicional es falsa.
Ahora, la proposicion (∀x : P (x)) es falsa si la negacion
∼ (∀x : P (x))⇐⇒ (∃x :∼ P (x)) es verdadera. Es decir, si
existe un valor de x para el cual P (x) es falsa.
Ejemplo (de contraejemplo). Dada la proposicion
∀x ∈ R : x2 − 4 = 0.
Si x = 1, entonces 12 − 4 6= 0. En consecuencia, hay un valor
para el cual la funcion proposicional x2 − 4 = 0 es falsa. Luego,
x = 1 es un contraejemplo y la proposicion es falsa.
Logica y Conjuntos 21 . FCFM.UdeC.
Logica
Ejemplos de demostracion:
Proposicion 1:
Sea a ∈ N. Si a es par, entonces a2 es par.
Demostracion (directa ). La hipotesis es H : a es par y la tesis es
T : a2 es par.
Ahora, si a es par, entonces por definicion a = 2n para algun
n ∈ N. Ası a2 = (2n)2 = 4n2 = 2(2n2) tambien es par, pues
2n2 ∈ N. En consecuencia, se obtuvo la tesis T .
Logica y Conjuntos 22 . FCFM.UdeC.
Logica
Proposicion 2: Sea a ∈ N. Si a2 es par, entonces a es par.
Demostracion (por contradicci on ). Sea H : a2 es par y sea
∼ T : a impar. Es decir, supongamos H∧ ∼ T .
Ahora, si a impar, entonces por definicion a = 2n + 1 para algun
n ∈ N. Luego,
a2 = (2n + 1)2 = 4n2 + 4n + 1 = 2(2n2 + 2n) + 1.
Es decir, a2 es impar. Se obtuvo H∧ ∼ H , lo que es una
CONTRADICCION (→←).
Logica y Conjuntos 23 . FCFM.UdeC.
Conjuntos
Idea de Conjunto
Llamaremos conjunto a cualquier coleccion bien determinada de
objetos. Se denotan por A,B, ....
Los objetos los llamaremos elementos del conjunto, se denotan por
a, b, c, .... Un objeto a de A se dice que pertenece al conjunto y
se escribe a ∈ A. En caso contrario se escribe a /∈ A
Dos conjuntos importantes son el conjunto vacıo, que no contiene
elementos y se denota por φ, y el conjunto universo, que contiene a
todos los elementos y se denota por U .
Logica y Conjuntos 24 . FCFM.UdeC.
Conjuntos
Definicion de Conjunto.
Dado x ∈ U y un conjunto A, subconjunto de U , se tiene la
pregunta: ¿ x ∈ A ∨ x /∈ A?.
Si esta pregunta se puede responder siempre, entonces se dice
que A esta bien definido .
Los elementos x de A se pueden caracterizar por una propiedad
P (x) y definir el conjunto como A = {x ∈ U : P (x)}, llamada
definicion por comprensi on .
Tambien se puede enumerar los elementos del conjunto
A = {a, b, c, ...}, llamada definicion por extensi on .
Logica y Conjuntos 25 . FCFM.UdeC.
Conjuntos
Ejemplos. Un conjunto esta bien definido por extension o por
comprension si dado x ∈ U es claro que ¿ x ∈ A ∨ x /∈ A?.
• Por extension, vale decir mostrando los elementos de A.
N := { 1, 2, 3, · · · } (Numeros naturales)
• Por comprension, esto es dando una propiedad (o proposicion)
que caracterice a los elementos del conjunto.
Q :={ a
b: a, b ∈ Z, b 6= 0
}
(Numeros racionales).
Logica y Conjuntos 26 . FCFM.UdeC.
Conjuntos
Inclusion de conjuntos
Dados dos conjuntos A y B, se dice que A es subconjunto de B
o que A esta incluido en B, y se escribe A ⊆ B, si todos los
elementos de A estan tambien en B, esto es:
A ⊆ B ⇐⇒ (∀x ∈ U : x ∈ A ⇒ x ∈ B)
Propiedades de la inclusion. Dados A, B, C conjuntos, se tiene
• φ ⊆ A ⊆ U
• A ⊆ A
• (A ⊆ B ∧ B ⊆ C)⇒ A ⊆ C
Logica y Conjuntos 27 . FCFM.UdeC.
Conjuntos
Igualdad de conjuntos
Dados dos conjuntos A y B, se dice que A y B son iguales , y se
escribe A = B, si los elementos de A y B coinciden, esto es:
A = B ⇐⇒ (A ⊆ B) ∧ (B ⊆ A).
Esto es, para un elemento x, se tiene:
(∀x ∈ U : x ∈ A ⇒ x ∈ B)∧(∀x ∈ U : x ∈ B ⇒ x ∈ A).
Logica y Conjuntos 28 . FCFM.UdeC.
Conjuntos
Conjunto de las partes de un conjunto dado
Dado un conjunto A, se define el conjunto de las partes de A, y
se denota P(A), como el conjunto de todos los subconjuntos de
A, esto es:
P(A) := {X : X ⊆ A }
Notar que:
1. Los elementos de P(A) son conjuntos.
B ∈ P(A)⇐⇒ B ⊆ A.
2. P(A) 6= φ ya que φ ∈ P(A) y A ∈ P(A).
3. El conjunto de las partes de A, tambien se denota por 2A.
Logica y Conjuntos 29 . FCFM.UdeC.
ConjuntosOperaciones entre conjuntos
Sea U el conjunto universo, y sean A, B subconjuntos de U . Es
decir, A,B ∈ P(U)).
a) La diferencia de A y B es el conjunto
A−B := {x ∈ U : x ∈ A ∧ x 6∈ B }
(Tambien se escribe A \B).
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 }
Logica y Conjuntos 30 . FCFM.UdeC.
Conjuntos
Algunas propiedades
• ∀x ∈ U : x ∈ A ∨ x ∈ Ac
• φc = U ∧ Uc = φ • A ∪Ac = U
• (Ac)c = A • A ∩Ac = φ
Logica y Conjuntos 31 . FCFM.UdeC.
Conjuntos
Otras operaciones entre conjuntos
Sea U el conjunto universo, y sean A, B subconjuntos de U .
c) La intersecci on de A y B, la cual se denota A ∩B, es el
conjunto de todos los elementos comunes a A y B, esto es
A ∩B := {x ∈ U : x ∈ A ∧ x ∈ B }
d) La uni on de A y B, la cual se denota A ∪B, es el conjunto
de todos los elementos que estan en A o en B, esto es
A ∪B := {x ∈ U : x ∈ A ∨ x ∈ B }
Logica y Conjuntos 32 . FCFM.UdeC.
Conjuntos
Propiedades de ∩ y ∪
• A ∪A = A , A ∩A = A (idempotencia)
• A ∪B = B ∪A , A ∩B = B ∩A (conmutatividad )
• A ∪ (B ∪ C) = (A ∪B) ∪ C (asociatividad de ∪)
• A ∩ (B ∩ C) = (A ∩B) ∩ C (asociatividad de ∩)
• A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C) (distributividad )
• A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C) (distributividad )
• (A ∪B)c = Ac ∩Bc (Ley de De Morgan)
• (A ∩B)c = Ac ∪Bc. (Ley de De Morgan)
Logica y Conjuntos 33 . FCFM.UdeC.
Conjuntos
Mas definiciones
• Dos conjuntos A y B se dicen disjuntos si y solo si
A ∩B = φ.
Por ejemplo, para A ∈ U , A y Ac son disjuntos pues
A ∩Ac = φ.
• Dados dos conjuntos no vacıos A y B, se define el Producto
Cartesiano entre ellos, el cual se denota por A×B, como el
conjunto de 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 }.
Logica y Conjuntos 34 . FCFM.UdeC.
Conjuntos
• Dados n conjuntos no vacıos A1, A2, ..., An, se define el
Producto Cartesiano entre ellos, el cual se denota por
A1 ×A2 × · · · ×An, como el conjunto de todas las n-uplas
ordenadas (a1, a2, ..., an) tales que ai pertenece a Ai para
cada i ∈ {1, ..., n}, esto es
A1×A2×· · ·×An := { (a1, a2, ..., an) : ai ∈ Ai , i ∈ {1, ..., n} }
Por ejemplo,
R×R×R = { (x, y, z) : x ∈ R ∧ y ∈ R∧ z ∈ R},
es el producto cartesiano entre A1, A2 y A3, con A = R, se
denota por R3.
Logica y Conjuntos 35 . FCFM.UdeC.
Conjuntos
Partici on de un conjunto . Sean A1, A2, ..., An subconjuntos de
un conjunto B. Se dice que {A1, A2, ..., An } es una partici on
de B si estos conjuntos son no vacıos, disjuntos dos a dos y su
union es el conjunto B, vale decir si, y solo si:
• Ai 6= φ, para cada i ∈ {1, ..., n}.
• Ai ∩Aj = φ para cada i 6= j.
•n⋃
i=1
Ai = B.
Logica y Conjuntos 36 . FCFM.UdeC.
Conjuntos
Cardinalidad. El numero de elementos de un conjunto finito A se
llama cardinalidad de A y se denota por |A| o por Card(A) o
por #(A).
En particular, Si Card(A) = n, entonces Card(2A) = 2n.
Ejemplo. Si A = {x ∈ N : n es par y n < 10}, entonces su
cardinalidad es
Card(A) = Card({2, 4, 6, 8} = 4.
Ademas,
Card(2A) = Card(P(A)) = 24 = 16.
Logica y Conjuntos 37 . FCFM.UdeC.
Conjuntos
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| .
Logica y Conjuntos 38 . FCFM.UdeC.
Recommended