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

De lo abierto a lo verdadero Un predicado P(x) es una frase con una variable, ni verdadera ni falsa hasta que asignas x: «x es par». Los cuantificadores convierten predicados en proposiciones: ∀x (para todo x) y ∃x (existe al menos un x).

∀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».

El error de negación por excelencia Para negar «todos los alumnos aprobaron» no digas «ninguno aprobó». Lo correcto es «algún alumno NO aprobó» (basta uno para romper el «todos»). Este error es facilísimo y está en casi todos los exámenes.

¿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.

Universal (∀)

Existencial (∃)

Mixto (ambos)

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

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

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.

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

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