Download IMD-IS. Lógica. Conjuntos

Lógica
Conjuntos
Álgebras de Boole
IMD-IS. Lógica. Conjuntos
Emmanuel Briand
ETSII. Universidad de Sevilla.
2012
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Proposiciones
2
+ 3 = 4
Hoy es lunes
Si x
=2
entonces x
2
= 4
Ojalá no llueva hoy !
x
>0
y x
< 1.
Existe una innidad de números primos p tal que p
es primo.
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
+2
Lógica
Conjuntos
Álgebras de Boole
Proposiciones compuestas
Proposición simple / Proposición compuesta.
Hoy es lunes y llueve
Si llueve, no salgo
5
≥3
y 5
≤ 6
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Conectores lógicos
y
o
no
si . . . entonces . . .
. . . si y solo si . . .
...
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Conectores lógicos y tablas de verdad
p
q
V
V
V
F
F
V
F
F
p
y
q
p
o
p
q
V
V
V
V
p
no
F
V
F
V
V
F
F
F
V
V
F
V
F
F
F
F
Emmanuel Briand
q
p
p
q
p
⇔q
V
V
V
V
F
F
F
V
F
F
F
V
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Hay simbolos para estos conectores lógicos . . .
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Razonamiento por equivalencia
+2y
+4y
=0
=1
+2y
−2y
=0
=1
x
3x
x
+2y
x
y
−1
x
y
x
y
Emmanuel Briand
=0
= −1/2
=0
= −1/2
=1
= −1/2
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
El conector de implicación
p
q
p
⇒q
V
V
V
F
V
F
F
V
V
F
F
V
Si hay vida extraterrestre entonces 1 + 1 = 2
Si 1 + 1 = 3 entonces todos los estudiantes excepto uno
aprobarán la asignatura
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Formulas lógicas
Conoceis formulas como:
x
2
+y −1
Las letras x e y son variables que representan números incógnitos.
Aquí está una formula lógica:
p
∨ (¬p ∧ q )
Las letras p y q representan proposiciones incógnitas.
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Ejercicios
¾ Cuál es la negación de:
1234567 es primo y 7654321 es primo?
Si Grouchy hubiese llegado a tiempo, Napoleón habría
ganado la batalla de Waterloo ?
Simplicar: p
∨ (¬p ∧ q )
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Una equivalencias lógicas importantes
Equivalencia = doble implicación
p
⇔ q
es lógicamente equivalente a (p
⇒ q ) ∧ (q ⇒ p ).
p implica q cuando la hipotesis no se cumple, o cuando la
conclusión se cumple.
p
⇒ q
es lógicamente equivalente a
(¬p ) ∨ q
Una implicación es equivalente a su contrarreciproco
p
⇒ q
es lógicamente equivalente a (¬q )
Emmanuel Briand
⇒ (¬p )
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Contrarreciproco y reciproco
La implicación p
⇒ q
como reciproco: q
tiene:
⇒ p.
como contrarreciproco (¬q )
⇒ (¬p ).
La implicación: Si tengo hambre entonces estoy de mal humor.
tiene:
como reciproco: Si estoy de mal humor entonces tengo
hambre.
como contrarreciproco: Si no estoy de mla humor, entonces
no tengo hambre.
La implicación es lógicamente equivalente a su contrarrecíproco,
NO es lógicamente equivalente a su reciproco.
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Las leyes de la lógica
p∨q
p∧q
p∨q
p∧q
(p ∨ q ) ∨ r ≡
(p ∧ q ) ∧ r ≡
p ∧ (q ∨ r )
p ∨ (q ∧ r )
≡
≡
p≡p
ff
p∧q
p∨q
≡
≡
q∨p
q∧p
p ∨ (q ∨ r )
p ∧ (q ∧ r )
≡ (p ∧ q ) ∨ (p ∧ r )
≡ (p ∨ q ) ∧ (p ∨ r )
p∨p
p∧p
≡
≡
p
p
p∨f
p∧v
≡
≡
p
p
p∨v
p∧f
≡
≡
v
f
≡
≡
v
f
p∨p
p∧p
Ley de la doble negación
Leyes de De Morgan
ff
Conmutatividad de
∨
y
y
∧
∧
ff
Asociatividad de
∨
ff
Distributividad de cada una de las operaciones
con respecto a la otra
ff
Leyes de idempotencia
ff
vyf
son
neutros para ∧ y ∨ respectivamente.
ff
Leyes de dominación
ff
p Leyes de los inversos
p ∨ (p ∧ q ) ≡ p
Leyes de absorción
p ∧ (p ∨ q) Emmanuel
≡ p
Briand
IMD-IS. Lógica.
ff
Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Y las paréntesis
Sean a, b, c tres enteros.
a es primo y b es primo o c no es primo
¾ Qué signica ?
a es primo y (b es primo o c no es primo)
(a es primo y b es primo) o c no es primo
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Ejemplos de conjuntos
{(1, 2), (3, 2), (1, 1)}
{x , y , z }
{exp, cos}
{{1}, {1, 2}, {2, 5}}
{1, exp, {1}, {1, 2}}
un conjunto de pares de números
un conjunto de variables
un conjunto de funciones
un conjunto de conjuntos
un conjunto de varios tipos de objetos.
½ El orden no cuenta !
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Denir un conjunto por medio de una propiedad
caractéristica
Sea B el conjunto de todos los números enteros pares n
que cumplen n
B
= {n |
≥2
n
y n
< 9
es un entero par y
B
n
≥2y
n
< 9}
= {2, 4, 6, 8}
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Subconjuntos. El conjunto vacío
Los subconjuntos de
{1 , 2 }
son:
Emmanuel Briand
∅, {1 }, {2 }
y
{1, 2}.
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Unión, intersección, Diferencia
Emmanuel Briand
x
∈A∪B
ssi (x
∈A
o x
∈ B)
x
∈A∩B
ssi (x
∈A
y x
∈ B)
x
∈A\B
ssi (x
∈A
y x
6∈ B )
x
∈A
ssi (x
6∈ A)
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Conectores lógicos y conjuntos
Union
↔
o: x
Intersection
↔
Compleentario
Incluido en
Iguales
x
↔
↔
∈A∪B
y: x
↔
ssi (x
∈A∩B
negación: x
implica: A
o x
∈A
=B
∈ B)
∈A
ssi (x
⊂B
equivalentes: A
∈A
ssi (x
ssi (x
∈A
ssi (x
y x
∈ B)
6∈ A)
implica x
∈A
es equivalente a
∈ B)
Emmanuel Briand
∈ B)
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Las leyes de la teoría de conjuntos
A=A
ff
A∪B =A∩B
A∩B =A∪B
A∪B =B∪A
A∩B =B∩A
(A ∪ B ) ∪ C =
(A ∩ B ) ∩ C =
A ∪ (B ∪ C )
A ∩ (B ∩ C )
A ∩ (B ∪ C ) = ( A ∩ B ) ∪ (A ∩ C )
A ∪ (B ∩ C ) = ( A ∪ B ) ∩ (A ∪ C )
A∪A=A
A∩A=A
A∪∅=A
A∩X =A
A∪X =A
A∩∅=∅
A∪A=X
A∩A=∅
Ley del doble complemento
Leyes de De Morgan
ff
Conmutatividad de
∪
y
y
∩
∩
ff
Asociatividad de
∪
ff
Distributividad de cada una de las operaciones con respecto a la otra
ff
A es idempotente para ambas operaciones
ff
X
neutros
X
absorbentes
y ∅ son
respectivamente.
ff
y ∅ son
respectivamente.
ff
ff
A ∪ (A ∩ BEmmanuel
)=A
para
para
∩
∪
A es inversa de A para ∪ y ∩
Briand
IMD-IS. Lógica. Conjuntos
y
y
∪
∩
Lógica
Conjuntos
Álgebras de Boole
Conjuntos y diagramas
A
∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
Intuición: diagrama
Demostración formal: ver apuntes.
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Un ejemplo de demsotración:
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
Idea 1:
x
∈ A ∩ (B ∪ C ) ⇔ (x ∈ A) ∧ (x ∈ (B ∪ C ))
⇔ ...
Idea 2: para demostrar que dos listas de nombres tienen
exactamente el mismo contenido (pero a lo mejor no en el mismo
orden),
comprobo que cada nombre en la primera lista aparece en la
segunda
y luego que cada nombre en la segunda lista aparece en la
primera.
Esta idea se aplica a conjuntos (incluso innitos):
X
=Y ⇔X ⊂Y y
Y
⊂X
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Leyes de lógica, leyes de conjuntos
Emmanuel Briand
IMD-IS. Lógica. Conjuntos
Lógica
Conjuntos
Álgebras de Boole
Álgebras de Boole
Cualquier conjunto equipado con tres operaciones
+, ×,
0 y con dos
elementos distinguidos 0 y 1, que satisface las 10 propiedades del
cuadro. (Pero basta comprobar cinco de ellas)
Conjunto
operaciones
Los subconjutos de
∪, ∩,
elementos especiales
complementario
∅
y X
un conjunto X
{V , F }
∨, ∧, ¬
F y V
{0, 1}
+, ×,
0
0 y 1
Álgebra de Boole de la lógica =
álgebra de conmutación (mutatis mutandis)
Emmanuel Briand
IMD-IS. Lógica. Conjuntos