La búsqueda de pruebas es la exploración sistemática del espacio de posibles derivaciones para localizar una prueba válida de una aserción especificada, empleando algoritmos, estrategias y límites de recursos.

Principio

Organizar la exploración con estrategias de búsqueda (profundidad, amplitud, best-first, encadenamiento hacia atrás dirigido por objetivo, encadenamiento hacia adelante), heurísticas y poda, equilibrando completitud, corrección y restricciones de recursos.

Demostración

Ejecutar una búsqueda encadenada hacia atrás con límite de profundidad en un cálculo de secuentes para encontrar una derivación de un objetivo, o realizar búsqueda basada en resolución con unificación y heurísticas de selección de cláusulas para refutar la negación de la conjetura.

Aplicación incorrecta

Aplicar búsqueda de fuerza bruta sin poda ni heurísticas lleva a una explosión combinatoria; usar heurísticas que sesgan excesivamente la búsqueda puede sacrificar la completitud y pasar por alto pruebas existentes.

Consecuencia

Una búsqueda de pruebas eficaz localiza pruebas o refutaciones certificables, informa sobre la complejidad y sustenta probadores de teoremas automáticos y la selección de tácticas en entornos interactivos.

Inversión

La inversión es la búsqueda dirigida de modelos o contraejemplos (refutación mediante contraejemplos) o confiar únicamente en la intuición humana para construir una prueba sin exploración sistemática.

Límite

La búsqueda de pruebas se refiere a la exploración sintáctica de derivaciones e incluye procedimientos completos e incompletos; excluye métodos puramente semánticos que no recorren espacios sintácticos de derivación salvo que se formulen como búsqueda.

Tensión semántica

Existe tensión entre la búsqueda hacia atrás dirigida por el objetivo (centrada en la conclusión) y la saturación hacia adelante (derivación amplia de consecuencias); cada una tiene compensaciones en aplicabilidad y rendimiento.

Síntesis

La búsqueda de pruebas es el recorrido algorítmico y orientado por estrategia del espacio de derivaciones que aplica reglas de inferencia, heurísticas y gestión de recursos para descubrir una derivación válida o una refutación para una aserción objetivo.