Prerrequisito – Predicados y cuantificadores – Conjunto 1 , Conjunto 2
Los cuantificadores son expresiones que indican el alcance del término al que se unen, aquí predicados. Un predicado es una propiedad que puede tener el sujeto del enunciado.
Por ejemplo, en el enunciado “la suma de x e y es mayor que 5” , el predicado ‘Q’ es la suma es mayor que 5,
y el enunciado se puede representar como Q(x, y) donde x e y son variables
El alcance de un cuantificador o una cuantificación es el rango en la fórmula en la que se involucra el cuantificador.
Tipos de cuantificación o alcances:
- Universal(∀) – El predicado es verdadero para todos los valores de x en el dominio.
- Existencial(∃) – El predicado es verdadero para al menos una x en el dominio.
Para conocer el alcance de un cuantificador en una fórmula, simplemente haga uso de los árboles de Parse . Dos cuantificadores están anidados si uno está dentro del alcance del otro.
- Ejemplo 1:
∀x ∃y (x+y=5)
Aquí ‘∃’ (léase como existe) y ‘∀’ (léase como para todo) son cuantificadores para las variables x e y.
La declaración se puede representar como-
∀x Q(x)
Q(x) es ∃y P(x, y) Q(x)-el predicado es una función de solo x porque el cuantificador se aplica solo a la variable x.
P(x, y) es (x + y = 5) - Ejemplo-2
∀x ∀y ((x> 0)∧(y< 0) → (xy< 0))
(en inglés)
Para cada número real x e y, si x es positivo e y es negativo, implica que xy es negativo.
de nuevo,
∀x Q(x)
donde Q(x) es ∀y P(x, y)
Ejemplo para convertir una declaración en una fórmula de cuantificadores anidados:
«Hay un alumno en esta lección que ha tomado al menos un curso en Matemáticas discretas».
Una declaración consta de cuantificadores y predicados, divídala en sus dos constituyentes.
Aquí x e y son el alumno y el curso y sus respectivos cuantificadores se adjuntan delante de ellos.
Escríbelo como-
Para algún x alumno, existe un curso de Matemáticas Discretas tal que x ha tomado y.
∃x ∃y P (x, y), donde P (x, y) es «x ha tomado y».
- Teorema-1: El orden de los cuantificadores existenciales anidados se puede cambiar sin cambiar el significado de la declaración.
- Teorema-2: El orden de los cuantificadores universales anidados se puede cambiar sin cambiar el significado de la declaración.
- Ejemplo-3:
Supongamos que P(x, y) es xy=8,
∃x ∃y P(x, y) dominio: enteros Se
traduce en-
Hay un entero x para el cual hay un entero y tal que xy = 8,
que es lo mismo que-
Hay un par de enteros x, y para los cuales xy = 8. Lo que
significa que ∃x ∃y P(x, y) es equivalente a ∃y ∃x P(x, y).Similarmente,
Suponga que P(x, y) es (xy = yx).
∀x ∀y P(x, y) dominio: números reales Se
traduce en-
Para todos los números reales x, para todos los números reales y, xy = yx o,
para cada par de números reales x, y, xy = yx.
nuevamente ∀x ∀y P(x, y) es equivalente a ∀y ∀x P(x, y).Sin embargo, cuando los cuantificadores anidados no son los mismos, cambiar el orden cambia el significado de la declaración.
- Ejemplo-4:
Suponga que P(x, y, z) es (x + y = z).
∀x ∀y ∃z P(x, y, z) dominio: números reales Se
traduce como-
Para todos los números reales x e y hay un número real z tal que x + y = z (Verdadero)
∀z ∃x ∃y Dominio P(x, y, z): números reales
Existe un número real z tal que para todos los números reales x e y, x + y = z (Falso)
Negación de cuantificadores anidados:
- Teorema 3
Para negar una secuencia de cuantificadores anidados, cambia cada cuantificador en la secuencia al otro tipo y luego niega el predicado.
Entonces la negación de ∀x ∃y : P(x, y) es ∃x ∀y : ~P(x, y)
- Ejemplo-5:
» ∃x en Cornell, x tiene al menos 18 años».
Para no estar de acuerdo con esto, está negando la declaración cambiando ∃ a ∀ y luego
negando el predicado:
» ∀x en Cornell tal que x no tiene al menos 18 años».