Upload
trinhtu
View
228
Download
1
Embed Size (px)
Citation preview
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 1/25
Matemáticas DiscretasTC1003
POL: Predicados y CuantificadoresDepartamento de Matemáticas
ITESM
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 2/25
Introducción
La Lógica de Predicados o Lógica de PrimerOrden (POL o FOL) es una extensión de LógicaProposicional. Todo las las equivalencias y reglasde inferencia vistas en la lógica proposicionalsiguen siendo válidas en la lógica de predicados.En esta lectura introduciremos dos elementos queestablecen la diferencia entre la lógicaproposicional y la lógica de predicados: elconcepto de predicado y el de cuantificador.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 3/25
Predicados
Definici onUn predicado es una sentencia declarativa quecontiene un número definido de variables y que sevuelve en una proposición cuando las variablesson sustituidas por valores.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 3/25
Predicados
Definici onUn predicado es una sentencia declarativa quecontiene un número definido de variables y que sevuelve en una proposición cuando las variablesson sustituidas por valores. El dominio de unpredicado es el conjunto de todos los valores quepueden ser sustituidos en las variables.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 4/25
Ejemplo 1
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
P (x) = x2 ≤ 10
Identifique cuáles opciones contienenafirmaciones verdaderas:1. P (−2)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 4/25
Ejemplo 1
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
P (x) = x2 ≤ 10
Identifique cuáles opciones contienenafirmaciones verdaderas:1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.2. P (−6)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 4/25
Ejemplo 1
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
P (x) = x2 ≤ 10
Identifique cuáles opciones contienenafirmaciones verdaderas:1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.2. P (−6) Falsa: (−6)2 = 36 6≤ 10.
3. P (1
2)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 4/25
Ejemplo 1
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
P (x) = x2 ≤ 10
Identifique cuáles opciones contienenafirmaciones verdaderas:1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.2. P (−6) Falsa: (−6)2 = 36 6≤ 10.
3. P (1
2) Verdadera: (1/2)2 = 1/4 ≤ 10.
4. P (2)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 4/25
Ejemplo 1
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
P (x) = x2 ≤ 10
Identifique cuáles opciones contienenafirmaciones verdaderas:1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.2. P (−6) Falsa: (−6)2 = 36 6≤ 10.
3. P (1
2) Verdadera: (1/2)2 = 1/4 ≤ 10.
4. P (2) Verdadera: (2)2 = 4 ≤ 10.5. P (−4)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 4/25
Ejemplo 1
Ejemplo
Sea P (x) el predicado con dominio los númeroreales:
P (x) = x2 ≤ 10
Identifique cuáles opciones contienenafirmaciones verdaderas:1. P (−2) Verdadera: (−2)2 = 4 ≤ 10.2. P (−6) Falsa: (−6)2 = 36 6≤ 10.
3. P (1
2) Verdadera: (1/2)2 = 1/4 ≤ 10.
4. P (2) Verdadera: (2)2 = 4 ≤ 10.5. P (−4) Falsa: (−4)2 = 16 6≤ 10.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 5/25
Ejemplo 2
Ejemplo
Sea P (x, y) el predicado:
P (x, y) = Si x < y, entonces x2 < y2.
Con dominio para x y para y todo el conjunto delos números reales. Identifique cuáles opcionescontienen afirmaciones verdaderas:1. P (3, 2)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 5/25
Ejemplo 2
Ejemplo
Sea P (x, y) el predicado:
P (x, y) = Si x < y, entonces x2 < y2.
Con dominio para x y para y todo el conjunto delos números reales. Identifique cuáles opcionescontienen afirmaciones verdaderas:1. P (3, 2) : (3 < 2) → (9 < 4): verdadera.2. P (−2, 1)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 5/25
Ejemplo 2
Ejemplo
Sea P (x, y) el predicado:
P (x, y) = Si x < y, entonces x2 < y2.
Con dominio para x y para y todo el conjunto delos números reales. Identifique cuáles opcionescontienen afirmaciones verdaderas:1. P (3, 2) : (3 < 2) → (9 < 4): verdadera.2. P (−2, 1) : (−2 < 1) → (4 < 1): falsa.3. P (−3, 1)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 5/25
Ejemplo 2
Ejemplo
Sea P (x, y) el predicado:
P (x, y) = Si x < y, entonces x2 < y2.
Con dominio para x y para y todo el conjunto delos números reales. Identifique cuáles opcionescontienen 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 (1
2, 1)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 5/25
Ejemplo 2
Ejemplo
Sea P (x, y) el predicado:
P (x, y) = Si x < y, entonces x2 < y2.
Con dominio para x y para y todo el conjunto delos números reales. Identifique cuáles opcionescontienen 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 (1
2, 1) : (1/2 < 1) → (1/4 < 1): cierta.
5. P (1,−3)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 5/25
Ejemplo 2
Ejemplo
Sea P (x, y) el predicado:
P (x, y) = Si x < y, entonces x2 < y2.
Con dominio para x y para y todo el conjunto delos números reales. Identifique cuáles opcionescontienen 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 (1
2, 1) : (1/2 < 1) → (1/4 < 1): cierta.
5. P (1,−3) : (1 < −3) → (1 < 9): cierta.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 6/25
Cuantificador Universal: ∀
Definici onSea Q(x) un predicado y D el dominio de Q.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 6/25
Cuantificador Universal: ∀
Definici onSea Q(x) un predicado y D el dominio de Q. Unaafirmación universal es una declaración de laforma:
∀x ∈ D,Q(x)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 6/25
Cuantificador Universal: ∀
Definici onSea Q(x) un predicado y D el dominio de Q. Unaafirmación universal es una declaración de laforma:
∀x ∈ D,Q(x)
Y es definida a ser verdadera si y sólo si Q(x) esverdadera para todo elemento x que está en eldominio D.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 6/25
Cuantificador Universal: ∀
Definici onSea Q(x) un predicado y D el dominio de Q. Unaafirmación universal es una declaración de laforma:
∀x ∈ D,Q(x)
Y es definida a ser verdadera si y sólo si Q(x) esverdadera para todo elemento x que está en eldominio D. La afirmación es falsa si y sólo si Q(x)es falsa al menos para un elemento x del dominio.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 6/25
Cuantificador Universal: ∀
Definici onSea Q(x) un predicado y D el dominio de Q. Unaafirmación universal es una declaración de laforma:
∀x ∈ D,Q(x)
Y es definida a ser verdadera si y sólo si Q(x) esverdadera para todo elemento x que está en eldominio 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 llamacontraejemplo a la afirmación universal.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 6/25
Cuantificador Universal: ∀
Definici onSea Q(x) un predicado y D el dominio de Q. Unaafirmación universal es una declaración de laforma:
∀x ∈ D,Q(x)
Y es definida a ser verdadera si y sólo si Q(x) esverdadera para todo elemento x que está en eldominio 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 llamacontraejemplo a la afirmación universal.
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)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 7/25
Cuantificador existencial: ∃
Definici onSea Q(x) un predicado con cominio D.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 7/25
Cuantificador existencial: ∃
Definici onSea Q(x) un predicado con cominio D. Unaafirmación existencial es una declaración de laforma:
∃x ∈ D, Q(x)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 7/25
Cuantificador existencial: ∃
Definici onSea Q(x) un predicado con cominio D. Unaafirmación existencial es una declaración de laforma:
∃x ∈ D, Q(x)
Y es definida a ser verdadera si y sólo si existe enel dominio D al menos un valor de x para el cualQ(x) es verdadera.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 7/25
Cuantificador existencial: ∃
Definici onSea Q(x) un predicado con cominio D. Unaafirmación existencial es una declaración de laforma:
∃x ∈ D, Q(x)
Y es definida a ser verdadera si y sólo si existe enel dominio D al menos un valor de x para el cualQ(x) es verdadera. A este valor lo referiremos a unejemplo para la afirmación existencial.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 7/25
Cuantificador existencial: ∃
Definici onSea Q(x) un predicado con cominio D. Unaafirmación existencial es una declaración de laforma:
∃x ∈ D, Q(x)
Y es definida a ser verdadera si y sólo si existe enel dominio D al menos un valor de x para el cualQ(x) es verdadera. A este valor lo referiremos a unejemplo para la afirmación existencial. Laafirmación será falsa si para todo x en el dominioQ(x) es falsa.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 7/25
Cuantificador existencial: ∃
Definici onSea Q(x) un predicado con cominio D. Unaafirmación existencial es una declaración de laforma:
∃x ∈ D, Q(x)
Y es definida a ser verdadera si y sólo si existe enel dominio D al menos un valor de x para el cualQ(x) es verdadera. A este valor lo referiremos a unejemplo para la afirmación existencial. Laafirmación será falsa si para todo x en el dominioQ(x) es falsa.
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)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 8/25
■ El símbolo ∀ se llama cuantificador universal.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 8/25
■ El símbolo ∀ se llama cuantificador universal.■ El símbolo ∃ se llama cuantificador existencial.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 8/25
■ El símbolo ∀ se llama cuantificador universal.■ El símbolo ∃ se llama cuantificador existencial.Nota
Cuando esté claro cual es el dominio delpredicado se omitirá la referencia al conjunto.Es decir,
∀x ∈ D,P (x) se escribirá ∀x, P (x)
∃x ∈ D,P (x) se escribirá ∃x, P (x)
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 9/25
Ejemplo 3
Veamos un ejemplo que involucra situacionessimplificadas conocido como el mundo de Tarski.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 10/25
Considere:a
b c
d
g
e
f
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.
Indique cuáles afirmacionesson verdaderas:1. ∀ t, Circulo(t) ∨ Rojo(t)
2. ∃ t, Cuadrado(t) ∧ Rojo(t)
3. ∀ t, Cuadrado(t) ∧ Rojo(t)
4. ∀ t, Triangulo(t) ∨ Rojo(t)
5. ∃ t, Cuadrado(t) ∧ Azul(t)
Soluciones :
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 11/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 Matemáticas Discretas - p. 12/25
Para la afirmación:
∀ t, Circulo(t) ∨ Rojo(t)
los datost 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
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 12/25
Para la afirmación:
∀ t, Circulo(t) ∨ Rojo(t)
los datost 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
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 12/25
Para la afirmación:
∀ t, Circulo(t) ∨ Rojo(t)
los datost 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 soncontraejemplos.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 13/25
Para la afirmación:
∃ t, Cuadrado(t) ∧ Rojo(t)
los datost 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
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 13/25
Para la afirmación:
∃ t, Cuadrado(t) ∧ Rojo(t)
los datost 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
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 13/25
Para la afirmación:
∃ t, Cuadrado(t) ∧ Rojo(t)
los datost 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. 14/25
Para la afirmación:
∀ t, Cuadrado(t) ∧ Rojo(t)
los datost 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
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 14/25
Para la afirmación:
∀ t, Cuadrado(t) ∧ Rojo(t)
los datost 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
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 14/25
Para la afirmación:
∀ t, Cuadrado(t) ∧ Rojo(t)
los datost 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 soncontraejemplos.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 15/25
Para la afirmación:
∀ t, Triangulo(t) ∨ Rojo(t)
los datost 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
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 15/25
Para la afirmación:
∀ t, Triangulo(t) ∨ Rojo(t)
los datost 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. 16/25
Para la afirmación:
∃ t, Cuadrado(t) ∧ Azul(t)
los datost 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
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 16/25
Para la afirmación:
∃ t, Cuadrado(t) ∧ Azul(t)
los datost 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.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 17/25
Ejemplo 4
Veamos un ejemplo que involucra bases de datos.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 18/25
Ejemplo
Considere los datos:Nombre Carrera Edad Hobby
Juan ITEC 21 Leer
María IMA 20 Música
Tomás IIS 23 Futbol
Lalo LATI 22 Anime
Luis IFI 21 Leer
Soledad LCC 24 Futbol
Nuestro dominio consiste delas personas Juan, María, To-más, Lalo, Luis, y Soledad.
Indique cuáles afirmacionesson verdaderas:1. ∃x, x es menor de 19 años.
2. ∃x, x tiene como hobby el correr.
3. ∀x, x tiene como hobby leer o x eshombre.
4. ∀x, si x tiene como hobby la músicaentonces x es mujer.
5. ∃x, x tiene como carrera Letras.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 19/25
De acuerdo a las preguntas, en este ejemploconviene 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.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 20/25
De acuerdo a los predicados, tendríamos lasiguiente 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
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 20/25
De acuerdo a los predicados, tendríamos lasiguiente 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
■ ∃x, x es menor de 19 años es falsa.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 20/25
De acuerdo a los predicados, tendríamos lasiguiente 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
■ ∃x, x es menor de 19 años es falsa.■ ∃x, x tiene como carrera Letras es falsa.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 20/25
De acuerdo a los predicados, tendríamos lasiguiente 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
■ ∃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.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 21/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) ∨ H(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
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 21/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) ∨ H(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
indican que es falsa: María y Soledad son loscontraejemplos.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 22/25
Para la afirmación:
∀x, si x tiene como hobby la música, entonces x es mujer.
los datosM19 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
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 22/25
Para la afirmación:
∀x, si x tiene como hobby la música, entonces x es mujer.
los datosM19 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.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 22/25
Para la afirmación:
∀x, si x tiene como hobby la música, entonces x es mujer.
los datosM19 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.
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/25
De Texto a FBF: Variantes de ∀ y ∃
■ Todos los A son B:
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/25
De Texto a FBF: Variantes de ∀ y ∃
■ Todos los A son B: ∀x, x es A → x es B
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/25
De Texto a FBF: Variantes de ∀ y ∃
■ Todos los A son B: ∀x, x es A → x es B
■ Cada A es B :
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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 :
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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 :
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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 :
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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 :
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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 :
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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 :
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 23/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 Matemáticas Discretas - p. 24/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.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 24/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.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 24/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. No2. Todo político es un buen conversador. Sí3. Cada político es un buen conversador.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 24/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. No2. Todo político es un buen conversador. Sí3. Cada político es un buen conversador. Sí4. Algunos buenos conversadores son políticos.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 24/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. No2. Todo político es un buen conversador. Sí3. Cada político es un buen conversador. Sí4. Algunos buenos conversadores son políticos. No5. Cualquier político es un buen conversador.
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 24/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. No2. Todo político es un buen conversador. Sí3. Cada político es un buen conversador. Sí4. Algunos buenos conversadores son políticos. No5. Cualquier político es un buen conversador. Sí
IntroduccionPredicadosEjemplo 1Ejemplo 2CuantificadorUniversalCuantificadorExistencialEjemplo 3Ejemplo 4ConversionSumario
POL: Predicados y Cuantificadores Matemáticas Discretas - p. 25/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