stringtranslate.com

Cuantificador (lógica)

En lógica , un cuantificador es un operador que especifica cuántos individuos en el dominio del discurso satisfacen una fórmula abierta . Por ejemplo, el cuantificador universal en la fórmula de primer orden expresa que todo en el dominio satisface la propiedad denotada por . Por otro lado, el cuantificador existencial en la fórmula expresa que existe algo en el dominio que satisface esa propiedad. Una fórmula en la que un cuantificador tiene el alcance más amplio se denomina fórmula cuantificada. Una fórmula cuantificada debe contener una variable ligada y una subfórmula que especifique una propiedad del referente de esa variable.

Tabla de verdad para cuantificadores existenciales y universales. [1]

Los cuantificadores más utilizados son y . Estos cuantificadores se definen de manera estándar como duales ; en la lógica clásica , son interdefinibles mediante la negación . También se pueden utilizar para definir cuantificadores más complejos, como en la fórmula que expresa que nada tiene la propiedad . Otros cuantificadores solo se pueden definir dentro de la lógica de segundo orden o lógicas de orden superior . Los cuantificadores se han generalizado a partir del trabajo de Mostowski y Lindström .

En un enunciado de lógica de primer orden, las cuantificaciones del mismo tipo (ya sean cuantificaciones universales o cuantificaciones existenciales) pueden intercambiarse sin cambiar el significado del enunciado, mientras que el intercambio de cuantificaciones de diferentes tipos cambia el significado. A modo de ejemplo, la única diferencia en la definición de continuidad uniforme y continuidad (ordinaria) es el orden de las cuantificaciones.

Los cuantificadores de primer orden se aproximan a los significados de algunos cuantificadores del lenguaje natural, como "algunos" y "todos". Sin embargo, muchos cuantificadores del lenguaje natural solo pueden analizarse en términos de cuantificadores generalizados .

Relaciones con la conjunción y disyunción lógicas

Para un dominio finito del discurso , la fórmula cuantificada universalmente es equivalente a la conjunción lógica . Dualmente, la fórmula cuantificada existencialmente es equivalente a la disyunción lógica . Por ejemplo, si es el conjunto de dígitos binarios , la fórmula abrevia , que evalúa como verdadero .

Dominio infinito del discurso

Considere la siguiente afirmación ( usando la notación de puntos para la multiplicación ):

1 · 2 = 1 + 1, y 2 · 2 = 2 + 2, y 3 · 2 = 3 + 3, ..., y 100 · 2 = 100 + 100, y ..., etc.

Esto tiene la apariencia de una conjunción infinita de proposiciones. Desde el punto de vista de los lenguajes formales , esto es inmediatamente un problema, ya que se espera que las reglas sintácticas generen palabras finitas .

El ejemplo anterior tiene la suerte de que existe un procedimiento para generar todos los conjuntivos. Sin embargo, si se hiciera una afirmación sobre cada número irracional , no habría forma de enumerar todos los conjuntivos, ya que los irracionales no se pueden enumerar. Una formulación sucinta y equivalente que evita estos problemas utiliza la cuantificación universal :

Para cada número natural n , n · 2 = n + n .

Un análisis similar se aplica a la disyunción ,

1 es igual a 5 + 5, o 2 es igual a 5 + 5, o 3 es igual a 5 + 5, ..., o 100 es igual a 5 + 5, o ..., etc.

que puede reformularse utilizando la cuantificación existencial :

Para algún número natural n , n es igual a 5+5.

Enfoques algebraicos para la cuantificación

Es posible diseñar álgebras abstractas cuyos modelos incluyan lenguajes formales con cuantificación, pero el progreso ha sido lento [ es necesaria una aclaración ] y el interés en dichas álgebras ha sido limitado. Hasta la fecha se han diseñado tres enfoques:

Notación

Los dos cuantificadores más comunes son el cuantificador universal y el cuantificador existencial. El símbolo tradicional para el cuantificador universal es " ∀ ", una letra " A " rotada, que significa "para todos" o "todos". El símbolo correspondiente para el cuantificador existencial es " ∃ ", una letra " E " rotada, que significa "existe" o "existe". [2] [3]

Un ejemplo de traducción de una declaración cuantificada en un lenguaje natural como el inglés sería el siguiente. Dada la declaración, "A cada uno de los amigos de Peter le gusta bailar o le gusta ir a la playa (o ambas cosas)", se pueden identificar aspectos clave y reescribir utilizando símbolos que incluyan cuantificadores. Por lo tanto, sea X el conjunto de todos los amigos de Peter, P ( x ) el predicado " a x le gusta bailar", y Q ( x ) el predicado " a x le gusta ir a la playa". Entonces la oración anterior se puede escribir en notación formal como , que se lee, "para cada x que es un miembro de X , P se aplica a x o Q se aplica a x ".

Algunas otras expresiones cuantificadas se construyen de la siguiente manera:

[4]    

para una fórmula P . Estas dos expresiones (usando las definiciones anteriores) se leen como "existe un amigo de Peter al que le gusta bailar" y "a todos los amigos de Peter les gusta bailar", respectivamente. Las notaciones variantes incluyen, para el conjunto X y los miembros del conjunto x :

    [5]     [6]                            

Todas estas variaciones se aplican también a la cuantificación universal. Otras variaciones del cuantificador universal son:

[ cita requerida ]     [7] [8]    

Algunas versiones de la notación mencionan explícitamente el rango de cuantificación. El rango de cuantificación siempre debe especificarse; para una teoría matemática dada, esto puede hacerse de varias maneras:

Se puede utilizar cualquier variable como variable cuantificada en lugar de cualquier otra, con ciertas restricciones en las que no se produce captura de variables . Incluso si la notación utiliza variables tipificadas, se pueden utilizar variables de ese tipo.

De manera informal o en lenguaje natural, "∀ x " o "∃ x " pueden aparecer después o en el medio de P ( x ). Sin embargo, formalmente, la frase que introduce la variable ficticia se coloca al frente.

Las fórmulas matemáticas mezclan expresiones simbólicas para cuantificadores con cuantificadores de lenguaje natural como,

Para cada número natural x , ...
Existe una x tal que...
Para al menos un x, ....

Las palabras clave para la cuantificación de la unicidad incluyen:

Para exactamente un número natural x , ...
Hay uno y sólo un x tal que....

Además, x puede reemplazarse por un pronombre . Por ejemplo,

Para cada número natural, su producto con 2 es igual a su suma consigo mismo.
Algún número natural es primo.

Orden de cuantificadores (anidamiento)

El orden de los cuantificadores es fundamental para el significado, como lo ilustran las dos proposiciones siguientes:

Para cada número natural n , existe un número natural s tal que s = n 2 .

Esto es claramente cierto; simplemente afirma que todo número natural tiene un cuadrado. El significado de la afirmación en la que se invierte el orden de los cuantificadores es diferente:

Existe un número natural s tal que para cada número natural n , s = n 2 .

Esto es claramente falso, ya que afirma que existe un único número natural s que es el cuadrado de todos los números naturales, ya que la sintaxis indica que ninguna variable puede ser función de variables introducidas posteriormente.

Un ejemplo menos trivial del análisis matemático se refiere a los conceptos de continuidad uniforme y puntual , cuyas definiciones difieren sólo por un intercambio en las posiciones de dos cuantificadores. Una función f de R a R se llama

En el primer caso, el valor particular elegido para δ puede ser una función tanto de ε como de x , las variables que lo preceden. En el segundo caso, δ puede ser una función solo de ε (es decir, debe elegirse independientemente de x ). Por ejemplo, f ( x ) = x 2 satisface la continuidad puntual, pero no la continuidad uniforme (su pendiente no está acotada). Por el contrario, intercambiar los dos cuantificadores universales iniciales en la definición de continuidad puntual no cambia el significado.

Como regla general, intercambiar dos cuantificadores universales adyacentes con el mismo alcance (o intercambiar dos cuantificadores existenciales adyacentes con el mismo alcance) no cambia el significado de la fórmula (ver Ejemplo aquí ), pero intercambiar un cuantificador existencial y un cuantificador universal adyacente puede cambiar su significado.

La profundidad máxima de anidamiento de cuantificadores en una fórmula se denomina " rango de cuantificador ".

Expresiones equivalentes

Si D es un dominio de x y P ( x ) es un predicado dependiente de la variable objeto x , entonces la proposición universal puede expresarse como

Esta notación se conoce como cuantificación restringida, relativizada o acotada . De manera equivalente, se puede escribir:

La proposición existencial puede expresarse con cuantificación acotada como

o equivalentemente

Junto con la negación, solo se necesita uno de los cuantificadores universal o existencial para realizar ambas tareas:

lo que demuestra que para refutar una proposición "para todo x ", no se necesita más que encontrar una x para la cual el predicado sea falso. De manera similar,

Para refutar una proposición del tipo "existe una x ", es necesario demostrar que el predicado es falso para todo x .

En la lógica clásica , cada fórmula es lógicamente equivalente a una fórmula en forma normal prenex , es decir, una cadena de cuantificadores y variables ligadas seguida de una fórmula sin cuantificadores.

Eliminación de cuantificadores

La eliminación de cuantificadores es un concepto de simplificación utilizado en lógica matemática , teoría de modelos y ciencias de la computación teórica . De manera informal, una afirmación cuantificada " tal que " puede verse como una pregunta "¿Cuándo existe un tal que ?", y la afirmación sin cuantificadores puede verse como la respuesta a esa pregunta. [9]

Una forma de clasificar las fórmulas es por la cantidad de cuantificación. Las fórmulas con menor profundidad de alternancia de cuantificadores se consideran más simples, y las fórmulas sin cuantificadores son las más simples.

Una teoría tiene eliminación de cuantificadores si para cada fórmula , existe otra fórmula sin cuantificadores que es equivalente a ella ( módulo esta teoría).

Rango de cuantificación

Toda cuantificación implica una variable específica y un dominio de discurso o rango de cuantificación de esa variable. El rango de cuantificación especifica el conjunto de valores que toma la variable. En los ejemplos anteriores, el rango de cuantificación es el conjunto de números naturales. La especificación del rango de cuantificación nos permite expresar la diferencia entre, por ejemplo, afirmar que un predicado se cumple para algún número natural o para algún número real . Las convenciones expositivas a menudo reservan algunos nombres de variable como " n " para números naturales y " x " para números reales, aunque confiar exclusivamente en las convenciones de nomenclatura no puede funcionar en general, ya que los rangos de variables pueden cambiar en el curso de un argumento matemático.

Una fórmula cuantificada universalmente sobre un rango vacío (como ) siempre es vacuamente verdadera . Por el contrario, una fórmula cuantificada existencialmente sobre un rango vacío (como ) siempre es falsa.

Una forma más natural de restringir el dominio del discurso utiliza la cuantificación cautelosa . Por ejemplo, la cuantificación cautelosa

Para algún número natural n , n es par y n es primo

medio

Para algún número par n , n es primo.

En algunas teorías matemáticas se supone que existe un único dominio del discurso fijado de antemano. Por ejemplo, en la teoría de conjuntos de Zermelo-Fraenkel , las variables abarcan todos los conjuntos. En este caso, se pueden utilizar cuantificadores protegidos para imitar un rango de cuantificación más pequeño. Así, en el ejemplo anterior, para expresar

Para cada número natural n , n ·2 = n + n

En la teoría de conjuntos de Zermelo-Fraenkel, se escribiría

Para cada n , si n pertenece a N , entonces n ·2 = n + n ,

donde N es el conjunto de todos los números naturales.

Semántica formal

La semántica matemática es la aplicación de las matemáticas para estudiar el significado de las expresiones en un lenguaje formal. Tiene tres elementos: una especificación matemática de una clase de objetos a través de la sintaxis , una especificación matemática de varios dominios semánticos y la relación entre ambos, que generalmente se expresa como una función de objetos sintácticos a objetos semánticos. Este artículo solo aborda la cuestión de cómo se interpretan los elementos cuantificadores. La sintaxis de una fórmula puede darse mediante un árbol sintáctico. Un cuantificador tiene un alcance y una ocurrencia de una variable x es libre si no está dentro del alcance de una cuantificación para esa variable. Por lo tanto, en

La ocurrencia de x e y en C ( y , x ) es libre, mientras que la ocurrencia de x e y en B ( y , x ) está limitada (es decir, no es libre).

Árbol sintáctico de la fórmula que ilustra el alcance y la captura de variables. Las ocurrencias de variables libres y limitadas están coloreadas en rojo y verde, respectivamente.

Una interpretación para el cálculo de predicados de primer orden supone como dado un dominio de individuos X . Una fórmula A cuyas variables libres son x 1 , ..., x n se interpreta como una función de valor booleano F ( v 1 , ..., v n ) de n argumentos, donde cada argumento abarca el dominio X . De valor booleano significa que la función supone uno de los valores T (interpretado como verdad) o F (interpretado como falsedad). La interpretación de la fórmula

es la función G de n -1 argumentos tales que G ( v 1 , ..., v n -1 ) = T si y solo si F ( v 1 , ..., v n -1 , w ) = T para cada w en X . Si F ( v 1 , ..., v n -1 , w ) = F para al menos un valor de w , entonces G ( v 1 , ..., v n -1 ) = F . De manera similar, la interpretación de la fórmula

es la función H de n -1 argumentos tales que H ( v 1 , ..., v n -1 ) = T si y solo si F ( v 1 , ..., v n -1 , w ) = T para al menos un w y H ( v 1 , ..., v n -1 ) = F en caso contrario.

La semántica para la cuantificación de unicidad requiere un cálculo de predicados de primer orden con igualdad. Esto significa que se da un predicado de dos lugares distinguido "="; la semántica también se modifica en consecuencia de modo que "=" siempre se interpreta como la relación de igualdad de dos lugares en X . La interpretación de

entonces es la función de n -1 argumentos, que es la lógica y de las interpretaciones de

Cada tipo de cuantificación define un operador de cierre correspondiente en el conjunto de fórmulas, añadiendo, para cada variable libre x , un cuantificador para unir x . [10] Por ejemplo, el cierre existencial de la fórmula abierta n > 2 ∧ x n + y n = z n es la fórmula cerrada ∃ nxyz ( n > 2 ∧ x n + y n = z n ); se sabe que esta última fórmula, cuando se interpreta sobre los enteros positivos, es falsa por el Último Teorema de Fermat . Como otro ejemplo, los axiomas ecuacionales, como x + y = y + x , suelen estar destinados a denotar su cierre universal , como ∀ xy ( x + y = y + x ) para expresar conmutatividad .

Paucal, multal y otros cuantificadores de grado

Ninguno de los cuantificadores discutidos anteriormente se aplica a una cuantificación como

Hay muchos números enteros n < 100, tales que n es divisible por 2, 3 o 5.

Un posible mecanismo de interpretación se puede obtener de la siguiente manera: Supongamos que además de un dominio semántico X , hemos dado una medida de probabilidad P definida en X y números de corte 0 < ab ≤ 1. Si A es una fórmula con variables libres x 1 ,..., x n cuya interpretación es la función F de las variables v 1 ,..., v n entonces la interpretación de

es la función de v 1 ,..., v n -1 que es T si y sólo si

y F en caso contrario. De manera similar, la interpretación de

es la función de v 1 ,..., v n -1 que es F si y sólo si

y T en caso contrario.

Otros cuantificadores

A lo largo del tiempo se han propuesto algunos otros cuantificadores. En particular, el cuantificador de solución, [11] : 28  anotado § ( signo de sección ) y leído "aquellos". Por ejemplo,

se lee "aquellos n en N tales que n 2 ≤ 4 están en {0,1,2}". La misma construcción se puede expresar en la notación de constructor de conjuntos como

A diferencia de los demás cuantificadores, § produce un conjunto en lugar de una fórmula. [12]

Algunos otros cuantificadores que a veces se utilizan en matemáticas incluyen:

Historia

La lógica aristotélica, también llamada lógica de término , trata la cuantificación de una manera más cercana al lenguaje natural y también menos adecuada para el análisis formal. La lógica aristotélica trató el Todo , el Algo y el No en el siglo IV a. C., en un relato que también toca las modalidades aléticas .

En 1827, George Bentham publicó su Esquema de un nuevo sistema de lógica: con un examen crítico de los elementos de lógica del Dr. Whately , en el que describía el principio del cuantificador, pero el libro no tuvo una amplia difusión. [13]

Augustus De Morgan (1806–1871) fue el primero en utilizar "cuantificador" en el sentido moderno.

William Hamilton afirmó haber acuñado los términos "cuantificar" y "cuantificación", probablemente en sus conferencias de Edimburgo en torno a 1840. Augustus De Morgan lo confirmó en 1847, pero su uso moderno comenzó con De Morgan en 1862, cuando hace afirmaciones como "Debemos tomar tanto " todo" como "algo-no-todo" como cuantificadores". [14]

Gottlob Frege , en su Begriffsschrift de 1879 , fue el primero en emplear un cuantificador para vincular una variable que se extendía sobre un dominio del discurso y aparecía en predicados . Cuantificaba universalmente una variable (o relación) escribiendo la variable sobre un hoyuelo en una línea que de otro modo sería recta y que aparecía en sus fórmulas diagramáticas. Frege no ideó una notación explícita para la cuantificación existencial, sino que empleó su equivalente de ~∀ x ~, o contraposición . El tratamiento de Frege de la cuantificación pasó en gran medida desapercibido hasta los Principios de las matemáticas de Bertrand Russell de 1903 .

En un trabajo que culminó en Peirce (1885), Charles Sanders Peirce y su alumno Oscar Howard Mitchell inventaron de forma independiente cuantificadores universales y existenciales, y variables ligadas . Peirce y Mitchell escribieron Π x y Σ x donde ahora escribimos ∀ x y ∃ x . La notación de Peirce se puede encontrar en los escritos de Ernst Schröder , Leopold Loewenheim , Thoralf Skolem y lógicos polacos hasta la década de 1950. En particular, es la notación del artículo de referencia de Kurt Gödel de 1930 sobre la completitud de la lógica de primer orden y el artículo de 1931 sobre la incompletitud de la aritmética de Peano .

El enfoque de Peirce para la cuantificación también influyó en William Ernest Johnson y Giuseppe Peano , quienes inventaron otra notación, a saber ( x ) para la cuantificación universal de x y (en 1897) ∃ x para la cuantificación existencial de x . Por lo tanto, durante décadas, la notación canónica en filosofía y lógica matemática fue ( x ) P para expresar "todos los individuos en el dominio del discurso tienen la propiedad P ", y "(∃ x ) P " para "existe al menos un individuo en el dominio del discurso que tiene la propiedad P ". Peano, que era mucho más conocido que Peirce, en efecto difundió el pensamiento de este último en toda Europa. La notación de Peano fue adoptada por los Principia Mathematica de Whitehead y Russell , Quine y Alonzo Church . En 1935, Gentzen introdujo el símbolo ∀, por analogía con el símbolo ∃ de Peano. ∀ no se convirtió en canónico hasta la década de 1960.

Alrededor de 1895, Peirce comenzó a desarrollar sus gráficos existenciales , cuyas variables pueden considerarse cuantificadas tácitamente. El hecho de que la instancia más superficial de una variable sea par o impar determina si la cuantificación de esa variable es universal o existencial. (La superficialidad es lo contrario de la profundidad, que está determinada por la anidación de negaciones). La lógica gráfica de Peirce ha atraído cierta atención en los últimos años por parte de quienes investigan el razonamiento heterogéneo y la inferencia diagramática .

Véase también

Referencias

  1. ^ Kashef, Arman. (2023), En busca de la lógica universal: una breve descripción general de la evolución de la lógica formal, doi :10.13140/RG.2.2.24043.82724/1
  2. ^ "Predicados y cuantificadores". www.csm.ornl.gov . Consultado el 4 de septiembre de 2020 .
  3. ^ "1.2 Cuantificadores". www.whitman.edu . Consultado el 4 de septiembre de 2020 .
  4. ^ KR Apt (1990). "Programación lógica". En Jan van Leeuwen (ed.). Modelos formales y semántica . Manual de informática teórica. Vol. B. Elsevier. págs. 493–574. ISBN 0-444-88074-7.Aquí: p.497
  5. ^ Schwichtenberg, Helmut; Wainer, Stanley S. (2009). Pruebas y cálculos. Cambridge: Cambridge University Press. doi :10.1017/cbo9781139031905. ISBN 978-1-139-03190-5.
  6. ^ John E. Hopcroft y Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Lectura/MA: Addison-Wesley. ISBN 0-201-02988-X.Aquí: pp344
  7. ^ Hans Hermes (1973). Introducción a la lógica matemática . Hochschultext (Springer-Verlag). Londres: Springer. ISBN 3540058192. ISSN  1431-4657.Aquí: Def. II.1.5
  8. ^ Glebskii, Yu. V.; Kogan, DI; Liogon'kii, MI; Talanov, VA (1972). "Rango y grado de realizabilidad de fórmulas en el cálculo de predicados restringido". Cibernética . 5 (2): 142–154. doi :10.1007/bf01071084. ISSN  0011-4235. S2CID  121409759.
  9. ^ Marrón 2002.
  10. ^ en general, para un cuantificador Q , el cierre tiene sentido solo si el orden de cuantificación de Q no importa, es decir, si Q x Q y p ( x , y ) es equivalente a Q y Q x p ( x , y ). Esto se satisface para Q ∈ {∀,∃}, cf. #Orden de cuantificadores (anidamiento) arriba.
  11. ^ Hehner, Eric CR , 2004, Teoría práctica de la programación, 2.ª edición, pág. 28
  12. ^ Hehner (2004) utiliza el término "cuantificador" en un sentido muy general, incluyendo también, por ejemplo, la suma .
  13. ^ George Bentham, Esquema de un nuevo sistema de lógica: con un examen crítico de Elementos de lógica del Dr. Whately (1827); Thoemmes; Edición facsímil (1990) ISBN 1-85506-029-9 
  14. ^ Peters, Stanley; Westerståhl, Dag (27 de abril de 2006). Cuantificadores en lenguaje y lógica. Clarendon Press. pp. 34–. ISBN 978-0-19-929125-0.

Bibliografía

Enlaces externos