Cuantificadores y predicados

Diagrama de matematicas discretas: grafo con nodos conectados, puertas logicas y diagramas de Venn. — Temas centrales de matematicas discretas: logica, conjuntos, grafos y conteo.

Mapa conceptual

Matematicas Discretas
- Logica
  - Proposicional
  - Cuantificadores
  - Demostracion
- Conjuntos
  - Operaciones
  - Cardinalidad
  - Relaciones
- Conteo
  - Permutaciones
  - Combinaciones
  - Recurrencias
- Grafos
  - Nodos aristas
  - BFS DFS
  - Arboles
- Modular
  - Congruencias
  - Criptografia
  - Euclides

∀x P(x) afirma que TODOS los objetos del dominio cumplen P. ∃x P(x) afirma que AL MENOS UNO lo cumple. El orden de los cuantificadores cambia el significado: ∀x∃y (para cada x hay un y) no es lo mismo que ∃y∀x (hay un y que sirve para todos los x).

Nótese que «ningún» se escribe negando un existencial: ¬∃ = «no existe ninguno».
Enunciado	Formalización	Dominio
Todos los datos son numéricos	∀d Numérico(d)	datos
Algún registro tiene nulos	∃r Nulo(r)	registros
Ningún modelo es perfecto	¬∃m Perfecto(m)	modelos
Todo usuario tiene un correo	∀u ∃c Tiene(u,c)	usuarios/correo

Negar cuantificadores: la regla de oro

Al negar, ∀ y ∃ se intercambian y el predicado se niega. Es la contrapartida de De Morgan para cuantificadores:

¬(∀x P(x)) ≡ ∃x ¬P(x): «no todos cumplen» = «alguien NO cumple».
¬(∃x P(x)) ≡ ∀x ¬P(x): «no existe ninguno» = «todos fallen».

¿Cuál es la negación de «Todo entero n cumple n² ≥ n» (∀n, n² ≥ n)?

∀x∃y (y = x + 1) y ∃y∀x (y = x + 1) significan lo mismo.

Clasifica cada enunciado formal por el tipo de cuantificador principal.

Arrastra cada ficha a su categoría (o tócala y luego toca la categoría). También puedes usar el teclado.

Errores al formalizar

Usar ∧ con ∀: «∀x (Estudiante(x) ∧ Apueba(x))» afirma que TODO es estudiante; lo correcto es ∀x (Estudiante(x) → Aprueba(x)).
Usar → con ∃: «∃x (Estudiante(x) → ... )» se satisface con cualquier no-estudiante; con ∃ se usa ∧.
Perder el dominio: la verdad de ∀x (x ≥ 0) depende de si x recorre ℕ, ℤ o ℝ; hay que fijarlo.

Ejemplo resuelto

Formaliza: «Algunos clientes no han dejado reseña».
Predicados: Cliente(x), Reseña(x).
«Algunos» = existe: ∃x.
«…que NO dejaron reseña»: ¬Reseña(x).
Resultado: ∃x (Cliente(x) ∧ ¬Reseña(x)).

La lógica de predicados es el esqueleto de las consultas: SQL con EXISTS, las reglas de un motor de inferencia o las restricciones de integridad de una base de datos se escriben literalmente con ∀ y ∃. Negar bien una condición compuesta evita devolver exactamente las filas equivocadas.

Cuantificadores en ocho

∀

para todo

∃

existe al menos uno

¬∀x P

∃x ¬P

¬∃x P

∀x ¬P

∀ con

→ (implicación)

∃ con

∧ (conjunción)

orden ∀∃

importa

dominio

conjunto que recorre x

Toca una tarjeta para ver la respuesta.

Lógica de predicados (repaso formal)Cuantificadores, traducción y negación con ejemplos resueltos.

Video complementario

Recurso audiovisual para reforzar los conceptos.

Niega, primero en español y luego de forma simbólica, la afirmación «Todo error del modelo se puede corregir con más datos». Indica qué tendría que encontrar un escéptico para demostrar que es falsa.

Tu texto se guarda sólo en este dispositivo.

Reflexiona: ¿como se relaciona este tema con los demas temas del curso? ¿Que ejemplo practico podrias dar?

Tu texto se guarda sólo en este dispositivo.

MIT OCW 6.042JMatematicas para Ciencias de la Computacion (MIT OpenCourseWare).

Cuantificadores y predicados

Herramientas de la lección

Sobre este contenido

Ir a