Definición
El número de alternancias entre cuantificadores existenciales y universales en la secuencia alternada más larga de una fórmula; equivalente al número de cambios de ∃ a ∀ o de ∀ a ∃ a lo largo de un camino maximal a través de las ocurrencias de cuantificadores.
Principio
Principio
La profundidad de alternancia organiza la estructura cuantificada de una fórmula midiendo cuántas veces cambia el tipo de cuantificador; se usa para clasificar la complejidad lógica y para relacionar fórmulas con capas de jerarquías descriptivas o computacionales.
Demostración
Demostración
En la forma prenexa ∃x ∀y ∃z P(x,y,z), el patrón de cuantificadores ∃→∀→∃ contiene dos alternancias (∃ a ∀ y ∀ a ∃), por lo que la profundidad de alternancia es 2; una fórmula ∀∀∃∃ tiene una sola alternancia.
Aplicación incorrecta
Aplicación incorrecta
Tratar la profundidad de alternancia como idéntica a la profundidad de anidamiento de cuantificadores o contar cuantificadores idénticos adyacentes como alternancias (por ejemplo considerar ∃∃ como alternancia) es un uso indebido que sobreestima la estructura real de alternancia.
Consecuencia
Consecuencia
Una profundidad de alternancia correctamente identificada predice la fuerza expresiva y suele correlacionar con un aumento de la complejidad decisional o computacional: más alternancias pueden situar una especificación en una capa superior de una jerarquía y cambiar los métodos de prueba o algoritmos aplicables.
Inversión
Inversión
El concepto inverso es un prefijo de cuantificadores sin alternancias (todos del mismo tipo), que no presenta alternancias y corresponde a fragmentos puramente existenciales o puramente universales cuyo comportamiento y complejidad difieren notablemente de los prefijos alternantes.
Límite
Límite
Se aplica a las secuencias de cuantificadores (habitualmente consideradas en forma prenexa) y a las secuencias alternantes a lo largo de caminos sintácticos; excluye contar bloques de cuantificadores separados y no interactuantes en subfórmulas distintas y depende de la convención para llevar fórmulas a forma prenexa.
Tensión semántica
Tensión semántica
La profundidad de alternancia compite con medidas relacionadas como el rango de cuantificadores (profundidad de anidamiento), la longitud de la fórmula y el número de bloques de cuantificadores; dos fórmulas pueden tener la misma profundidad de alternancia pero diferir mucho en rango o longitud, lo que dificulta elegir la medida de complejidad más pertinente.
Síntesis
Síntesis
La profundidad de alternancia es el recuento de cambios de tipo entre ∃ y ∀ a lo largo del camino cuantificado más largo de una fórmula; resume cómo alternan los cuantificadores y actúa como un indicador sintáctico focalizado de la complejidad expresiva y computacional.