Processing math: 100%
Saltar al contenido principal
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
LibreTexts Español

3.4: Cuantificadores

  • Bob Dumas and John E. McCarthy
  • University of Washington and Washington University in St. Louis

( \newcommand{\kernel}{\mathrm{null}\,}\)

DejarP(x) ser una fórmula en una variable. Si sustituimos una constanteaU,,x pues llegamos a un comunicadoP(a). No obstante, supongamos que nos interesaP(x) con respecto a algún conjuntoXU, más que a un elemento particular deU. En particular, preguntamos siP(a) es una verdadera declaración para todosaX. Recordemos que uno de los roles de una fórmula es definir conjuntos. Para cualquier fórmulaP(x), universoU yXU,P(x) particionesX en dos conjuntos - aquellos elementos deX para los cualesP es cierto, y aquellos para los queP es falso. En este sentido, preguntar si seP sostiene para todosxX, o si se sostiene para algunosxX (lo que es complementario a preguntar si se¬P mantiene para todosxX) es preguntar siP define una nuevo o interesante subconjunto deX.

Así como se introdujeron los conectivos proposicionales para formalizar el comportamiento lingüístico de ciertos conectivos de lenguaje natural ampliamente empleados (y, o, implica, no), también formalizaremos la “cuantificación” sobre conjuntos.

Definición. Cuantificador universal,(xX)P(x) LetP(x) be una fórmula en una variable, con universoU. VamosXU. QSea el enunciado(xX)P(x) EntoncesQ es cierto si por cadaaX,P(a) es cierto. De lo contrarioQ es falso.

La notación(xX)P(x) es una taquigrafía para(x)([xX][P(x)]) La declaración "(xX)P(x)"se lee “para todosx enX,P(x)". Tenemos(xX)P(x)XχP DEFINICIÓN. Cuantificador existencial,(xX)P(x) LetP(x) Ser una fórmula en una variable con universoU. LetXU,X. QSea el enunciado(xX)P(x). EntoncesQ es cierto si hay algunoaX, para lo cualP(a) es cierto. De lo contrarioQ es falso.

La expresión(xX)P(x) es una taquigrafía para(x)[(xX)P(x)] La declaración(xX)P(x) "" se lee “existex enX, tal queP(x)”. El cuantificador "" es el equivalente formal de la expresión del lenguaje natural “para todos” o “cada”. El cuantificador "" es el equivalente formal de “para algunos” o “existe... tal que...”.

Siempre que el universo de una variable sea claro, o no relevante para la discusión, es común suprimir el universo en la expresión del enunciado. Por ejemplo, siP(x) es una fórmula con universoU, podemos escribir(x)P(x) en lugar de(xU)P(x).

3.4.1. Cuantificadores Múltiples.

DejarP(x1,,xn) ser una fórmula enn2 variables. Entonces la fórmula(x1)P(x1,,xn) es una fórmula en lasn1 variablesx2,,xn. De igual manera, la fórmula(x1)P(x1,,xn) es una fórmula enn1 variables.

EJEMPLO 3.10. Considera la fórmula en cinco variablesP(x,x0,L,ε,δ):=(0<|xx0|<δ)(|sin(x)L|<ε) con todas las variables teniendo universoR. Entonces(x0)P(x,x0,L,ε,δ) es una fórmula en cuatro variables,(x0)(L)P(x,x0,L,ε,δ) es una fórmula en tres variables, y(x0)(L)(ε)P(x,x0,L,ε,δ) es una fórmula en dos variables.

Definición. Variable abierta, Variable enlazada En la fórmulaP(x),x es una variable abierta. En las fórmulas(x)P(x),(x)P(x),(x)Q(x,y),(x)Q(x,y)x hay una variable enlazada o cuantificada, y en las dos últimas,y es una variable abierta.

3.4.2. Orden del cuantificador.

En la discusión a continuación, necesitamos discutir los cuantificadores genéricamente, es decir, sin tener en cuenta si el cuantificador en discusión es universal o existencial. Por lo que vamos a introducir alguna notación conveniente sólo para esta sección.

Notación. (Qx)P(x)Utilizamos la notación (Q Qx)P(x) para representar genéricamente(x)P(x) y(x)P(x) LetQ1,,Qn be cuantificadores lógicos yP(x1,,xn) ser una fórmula con variables abiertasx1,,xn. Entonces(Q1x1)(Q2x2)()(Qnxn)P(x1,,xn) es una declaración.

EJEMPLO 3.11. Considerar una declaraciónS en la formaS=(xX)(yY)P(x,y).S es verdadera si para cada unoaX,(yY)P(a,y) es verdad. Esto se satisface siempre que para cada unoaX, haya un elemento deY (llamémosloba para recordarnos que este elemento particular deY está asociado con la elección anterior, a) tal queP(a,ba) es cierto. Asíba se selecciona teniendoa en mente. Las declaraciones en esta forma son especialmente importantes en matemáticas porque la definición del límite en el cálculo es una declaración en la forma de este ejemplo.

Volvamos al enunciado(Q1x1)()(Qnxn)P(x1,,xn) El orden de los cuantificadores es significativo. Si1i<jn,xi se comporta como un parámetro desde el punto de vista dexj (es decir,xi se fija desde el punto de vista dexj). Dicho de otra manera,xj se elige con respecto a las sustituciones dex1,,xj1, pero sin consideración paraxj+1,,xn.

Siempre se lee desde la izquierda. El enunciado(x1)(Q2x2)()(Qnxn)P(x1,,xn) es el mismo que(x1)[(Q2x2)()(Qnxn)P(x1,,xn)] o, en otras palabras, para cada elección dex1, la afirmación(Q2x2)()(Qnxn)P(x1,,xn) es cierta. De igual manera, la afirmación(x1)(Q2x2)()(Qnxn)P(x1,,xn) es la misma que(x1)[(Q2x2)()(Qnxn)P(x1,,xn)] o en otras palabras que hay alguna elección dex1 para la cual la afirmación(Q2x2)()(Qnxn)P(x1,,xn) sobre lasn1 variablesx2,,xn es verdadera.

EJEMPLO 3.12. El orden de los cuantificadores es importante, como se puede ver en lo siguiente: no(xX)(yY)P(x,y) es equivalente a(yY)(xX)P(x,y). Por ejemplo, la afirmación(xR)(yR)(y=x2) es verdadera. Pero(yR)(xR)(y=x2) es falso. El enunciado[(yY)(xX)P(x,y)][(xX)(yY)P(x,y)] es cierto. Lo contrario claramente falla.

3.4.3. Negación de Cuantificadores.

En un sentido importante, y son complementarios. Por las identidades de Morgan (3.3) y (3.4), la negación de una simple conjunción es una disyunción de negaciones. De igual manera, la negación de una disyunción simple es una conjunción de negaciones. Los cuantificadores universales y existenciales también son complementarios. Observamos que[¬(x)P(x)][(x)¬P(x)] para cualquier fórmula,P(x). Similarmente Por[¬(x)P(x)][(x)¬P(x)]. supuesto,P(x) en sí misma puede ser una fórmula que tenga numerosos cuantificadores y variables enlazadas. Supongamos queP(x)=(y)Q(x,y). Entonces las siguientes declaraciones son equivalentes (para cualquier elecciónP yQ satisfacción de la identidad (3.13)):¬(x)P(x)(x)¬P(x)¬(x)(y)Q(x,y)(x)¬(y)Q(x,y)(x)(y)¬Q(x,y). Este ejemplo sugiere que es permisible permutar una negación y un cuantificador por cambiando el tipo de cuantificador, y de hecho esto es así.

DejarQi ser un cuantificador, para1in. Para cada unoQi, dejaQi ser el cuantificador complementario. Es decir, siQi=, entonces vamosQi=; siQi=, entonces vamosQi=. Entonces,¬(Q1x1)()(Qnxn)P(ˉx)(Q1x1)()(Qnxn)¬P(ˉx).


This page titled 3.4: Cuantificadores is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Bob Dumas and John E. McCarthy via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?