Download Matemáticas Discretas TC1003

Matemáticas Discretas
TC1003
POL: Predicados y Cuantificadores
Departamento de Matemáticas
ITESM
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 1/25
Introducción
La Lógica de Predicados o Lógica de Primer
Orden (POL o FOL) es una extensión de Lógica
Proposicional. Todo las las equivalencias y reglas
de inferencia vistas en la lógica proposicional
siguen siendo válidas en la lógica de predicados.
En esta lectura introduciremos dos elementos que
establecen la diferencia entre la lógica
proposicional y la lógica de predicados: el
concepto de predicado y el de cuantificador.
POL: Predicados y Cuantificadores
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
Matemáticas Discretas - p. 2/25
Predicados
Definición
Un predicado es una sentencia declarativa que
contiene un número definido de variables y que se
vuelve en una proposición cuando las variables
son sustituidas por valores. El dominio de un
predicado es el conjunto de todos los valores que
pueden ser sustituidos en las variables.
POL: Predicados y Cuantificadores
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
Matemáticas Discretas - p. 3/25
Ejemplo 1
Ejemplo
Sea P (x) el predicado con dominio los número
reales:
P (x) = x2 ≤ 10
Identifique cuáles opciones contienen
afirmaciones verdaderas:
1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.
2. P (−6) Falsa: (−6)2 = 36 6≤ 10.
3. P ( 21 ) Verdadera: (1/2)2 = 1/4 ≤ 10.
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
4. P (2) Verdadera: (2)2 = 4 ≤ 10.
5. P (−4) Falsa: (−4)2 = 16 6≤ 10.
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 4/25
Ejemplo 2
Ejemplo
Sea P (x, y) el predicado:
P (x, y) = Si x < y, entonces x2 < y 2 .
Con dominio para x y para y todo el conjunto de
los números reales. Identifique cuáles opciones
contienen afirmaciones verdaderas:
1. P (3, 2) : (3 < 2) → (9 < 4): verdadera.
2. P (−2, 1) : (−2 < 1) → (4 < 1): falsa.
3. P (−3, 1) : (−3 < 1) → (9 < 1): falsa.
4. P ( 21 , 1) : (1/2 < 1) → (1/4 < 1): cierta.
5. P (1, −3) : (1 < −3) → (1 < 9): cierta.
POL: Predicados y Cuantificadores
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
Matemáticas Discretas - p. 5/25
Cuantificador Universal: ∀
Definición
Sea Q(x) un predicado y D el dominio de Q. Una
afirmación universal es una declaración de la
forma:
∀ x ∈ D, Q(x)
Y es definida a ser verdadera si y sólo si Q(x) es
verdadera para todo elemento x que está en el
dominio D. La afirmación es falsa si y sólo si Q(x)
es falsa al menos para un elemento x del dominio.
Un elemento x para el cual Q(x) es falsa se llama
contraejemplo a la afirmación universal.
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
Note también que ∀ se traduce en una conjunción:
Si por ejemplo D = {1, a, e} entonces
∀ x ∈ D, Q(x) ≡ Q(1) ∧ Q(a) ∧ Q(e)
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 6/25
Cuantificador existencial: ∃
Definición
Sea Q(x) un predicado con cominio D. Una
afirmación existencial es una declaración de la
forma:
∃ x ∈ D, Q(x)
Y es definida a ser verdadera si y sólo si existe en
el dominio D al menos un valor de x para el cual
Q(x) es verdadera. A este valor lo referiremos a un
ejemplo para la afirmación existencial. La
afirmación será falsa si para todo x en el dominio
Q(x) es falsa.
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
Note también que ∃ se traduce en una disjunción:
Si por ejemplo D = {1, a, e} entonces
∃ x ∈ D, Q(x) ≡ Q(1) ∨ Q(a) ∨ Q(e)
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 7/25
■
■
El símbolo ∀ se llama cuantificador universal.
El símbolo ∃ se llama cuantificador existencial.
Nota
Cuando esté claro cual es el dominio del
predicado se omitirá la referencia al conjunto.
Es decir,
∀x ∈ D, P (x) se escribirá ∀x, P (x)
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
∃x ∈ D, P (x) se escribirá ∃x, P (x)
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 8/25
Ejemplo 3
Veamos un ejemplo que involucra situaciones
simplificadas conocido como el mundo de Tarski.
POL: Predicados y Cuantificadores
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
Matemáticas Discretas - p. 9/25
Indique cuáles afirmaciones
son verdaderas:
Considere:
a
1. ∀ t, Circulo(t) ∨ Rojo(t)
c
b
g
e
2. ∃ t, Cuadrado(t) ∧ Rojo(t)
f
d
3. ∀ t, Cuadrado(t) ∧ Rojo(t)
4. ∀ t, Triangulo(t) ∨ Rojo(t)
5. ∃ t, Cuadrado(t) ∧ Azul(t)
Soluciones:
Y los predicados:
Azul(t)
=
t es de color azul.
Rojo(t)
=
t es de color rojo.
Triangulo(t)
=
t es un triángulo .
Cuadrado(t)
=
t es un cuadrado.
Circulo(t)
=
t es un círculo.
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 10/25
Con los predicados y la figura generamos la tabla:
t
Azul
Rojo
Triangulo
Cuadrado
Circulo
a
T
F
T
F
F
b
T
F
T
F
F
c
F
T
F
F
T
d
F
T
F
T
F
e
F
T
F
T
F
f
F
T
F
T
F
g
F
T
F
F
T
POL: Predicados y Cuantificadores
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
Matemáticas Discretas - p. 11/25
Para la afirmación:
∀ t, Circulo(t) ∨ Rojo(t)
los datos
t
Azul
Rojo
Triangulo
Cuadrado
Circulo
Circulo(t) ∨ Rojo(t)
a
T
F
T
F
F
F
b
T
F
T
F
F
F
c
F
T
F
F
T
T
d
F
T
F
T
F
T
e
F
T
F
T
F
T
f
F
T
F
T
F
T
g
F
T
F
F
T
T
nos indican que la afirmación es falsa: a y b son
contraejemplos.
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 12/25
Para la afirmación:
∃ t, Cuadrado(t) ∧ Rojo(t)
los datos
t
Azul
Rojo
Triangulo
Cuadrado
Circulo
Cuadrado(t) ∧ Rojo(t)
a
T
F
T
F
F
F
b
T
F
T
F
F
F
c
F
T
F
F
T
F
d
F
T
F
T
F
T
e
F
T
F
T
F
T
f
F
T
F
T
F
T
g
F
T
F
F
T
F
nos indican que la afirmación es cierta: d, e y f son ejemplos.
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 13/25
Para la afirmación:
∀ t, Cuadrado(t) ∧ Rojo(t)
los datos
t
Azul
Rojo
Triangulo
Cuadrado
Circulo
Cuadrado(t) ∧ Rojo(t)
a
T
F
T
F
F
F
b
T
F
T
F
F
F
c
F
T
F
F
T
F
d
F
T
F
T
F
T
e
F
T
F
T
F
T
f
F
T
F
T
F
T
g
F
T
F
F
T
F
nos indican que la afirmación es falsa: a, b, c y g son
contraejemplos.
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 14/25
Para la afirmación:
∀ t, Triangulo(t) ∨ Rojo(t)
los datos
t
Azul
Rojo
Triangulo
Cuadrado
Circulo
Triangulo(t) ∨ Rojo(t)
a
T
F
T
F
F
T
b
T
F
T
F
F
T
c
F
T
F
F
T
T
d
F
T
F
T
F
T
e
F
T
F
T
F
T
f
F
T
F
T
F
T
g
F
T
F
F
T
T
nos indican que la afirmación es cierta.
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 15/25
Para la afirmación:
∃ t, Cuadrado(t) ∧ Azul(t)
los datos
t
Azul
Rojo
Triangulo
Cuadrado
Circulo
Cuadrado(t) ∧ Azul(t)
a
T
F
T
F
F
F
b
T
F
T
F
F
F
c
F
T
F
F
T
F
d
F
T
F
T
F
F
e
F
T
F
T
F
F
f
F
T
F
T
F
F
g
F
T
F
F
T
F
nos indican que la afirmación es falsa.
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 16/25
De acuerdo a las preguntas, en este ejemplo
conviene definir los predicados:
M19(t) = t tiene menos de 19 años.
Co(t) = t tiene como hobby correr.
Leer(t) = t tiene como hobby leer.
Mus(t) = t tiene como hobby la música.
H(t) = t es un hombre.
M(t) = t es un mujer.
Letras(t) = t tiene como carrera Letras.
POL: Predicados y Cuantificadores
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
Matemáticas Discretas - p. 19/25
De acuerdo a los predicados, tendríamos la
siguiente tabla:
■
■
■
M19
C
Leer
Mus
H
M
Letras
Juan
F
F
T
F
T
F
F
María
F
F
F
T
F
T
F
Tomás
F
F
F
F
T
F
F
Lalo
F
F
F
F
T
F
F
Luis
F
F
T
F
T
F
F
Soledad
F
F
F
F
F
T
F
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
∃ x, x es menor de 19 años es falsa.
∃ x, x tiene como carrera Letras es falsa.
∃ x, x tiene como hobyy correr es falsa.
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 20/25
Para la afirmación:
∀ x, x tiene como hobby leer o x es hombre
los datos:
t
M19
C
Leer
Mus
H
M
Letras
Leer(t) ∨
Juan
F
F
T
F
T
F
F
T
María
F
F
F
T
F
T
F
F
Tomás
F
F
F
F
T
F
F
T
Lalo
F
F
F
F
T
F
F
T
Luis
F
F
T
F
T
F
F
T
Soledad
F
F
F
F
F
T
F
F
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
H(t)
Ejemplo 4
Conversión
Sumario
indican que es falsa: María y Soledad son los
contraejemplos.
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 21/25
Para la afirmación:
∀ x, si x tiene como hobby la música, entonces x es mujer.
los datos
M19
C
Leer
Mus
H
M
Letras
Mus → M
Juan
F
F
T
F
T
F
F
T
María
F
F
F
T
F
T
F
T
Tomás
F
F
F
F
T
F
F
T
Lalo
F
F
F
F
T
F
F
T
Luis
F
F
T
F
T
F
F
T
Soledad
F
F
F
F
F
T
F
T
indican que es verdadera.
No te que la clave es que F → X es T.
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 22/25
De Texto a FBF: Variantes de ∀ y ∃
■
■
■
■
■
■
■
■
Todos los A son B: ∀x, x es A → x es B
Cada A es B : ∀x, x es A → x es B
Ningún A es B : ∀x, x es A → x no es B
Existe un A que es B : ∃x, x es A ∧ x es B
Hay algún A que es B : ∃x, x es A ∧ x es B
Algún A es B : ∃x, x es A ∧ x es B
Algunos A son B : ∃x, x es A ∧ x es B
Entre todos los A alguno es B :
∃x, x es A ∧ x es B
POL: Predicados y Cuantificadores
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
Matemáticas Discretas - p. 23/25
Ejemplo
Para la afirmación:
∀x, si x es político, entonces x es un buen conversador
Usando los predicados
■ P (x) = x es político y
■ C(x) = x es un buen conversador,
indique cuáles expresiones describen la afirmación:
1. Entre todos los políticos, algunos son buenos
conversadores. No
2. Todo político es un buen conversador. Sí
3. Cada político es un buen conversador. Sí
4. Algunos buenos conversadores son políticos. No
5. Cualquier político es un buen conversador. Sí
POL: Predicados y Cuantificadores
Matemáticas Discretas - p. 24/25
Temas Vistos
■
■
■
■
■
■
■
Concepto de Predicado
Dominio de un Predicado
Cuantificador Universal
Cuantificador Existencial
Cuándo son verdaderas afirmaciones con
cuantificadores
Ejemplos con el Mundo de Tarski y con Bases de
Datos
Conversión de Textos usando cuantificadores
POL: Predicados y Cuantificadores
Introducción
Predicados
Ejemplo 1
Ejemplo 2
Cuantificador
Universal
Cuantificador
Existencial
Ejemplo 3
Ejemplo 4
Conversión
Sumario
Matemáticas Discretas - p. 25/25