Download Lógica y Conjuntos

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