Clase Bernays-Schönfinkel

La clase Bernays-Schönfinkel (también conocida como clase Bernays-Schönfinkel-Ramsey ) de fórmulas, llamada así en honor a Paul Bernays , Moses Schönfinkel y Frank P. Ramsey , es un fragmento de fórmulas lógicas de primer orden donde la satisfacibilidad es decidible .

Es el conjunto de oraciones que, cuando se escriben en forma normal de prenexo , tienen un prefijo cuantificador y no contienen ningún símbolo de función . ${\displaystyle \exists ^{*}\forall ^{*}}$

Ramsey demostró que, si es una fórmula de la clase Bernays-Schönfinkel con una variable libre, entonces es finita o es finita. ^[1] ${\displaystyle \phi }$ ${\displaystyle \{x\in \mathbb {N} :\phi (x)\}}$ ${\displaystyle \{x\in \mathbb {N} :\neg \phi (x)\}}$

Esta clase de fórmulas lógicas a veces también se denomina efectivamente proposicional ( EPR ), ya que puede traducirse efectivamente en fórmulas lógicas proposicionales mediante un proceso de fundamentación o creación de instancias.

El problema de satisfacibilidad para esta clase es NEXPTIME -completo. ^[2]

Aplicaciones

Se han integrado algoritmos eficientes para decidir la satisfacibilidad de EPR en los solucionadores SMT . ^[3]

Ver también

• Forma normal de Prenex

Notas

1. Pratt-Hartmann, Ian (30 de marzo de 2023). Fragmentos de lógica de primer orden. Prensa de la Universidad de Oxford. pag. 186.ISBN​ 978-0-19-196006-2.
2. Lewis, Harry R. (1980), "Resultados de complejidad para clases de fórmulas cuantificacionales", Journal of Computer and System Sciences , 21 (3): 317–353, doi :10.1016/0022-0000(80)90027-6, Señor  0603587
3. de Moura, Leonardo; Bjorner, Nikolaj (2008). Armando, Alejandro; Baumgartner, Peter; Dowek, Gilles (eds.). "Decidir eficazmente la lógica proposicional utilizando DPLL y conjuntos de sustitución". Razonamiento automatizado . Apuntes de conferencias sobre informática. Berlín, Heidelberg: Springer: 410–425. doi :10.1007/978-3-540-71070-7_35. ISBN 978-3-540-71070-7.

Referencias

• Ramsey, F. (1930), "Sobre un problema de lógica formal", Proc. Matemáticas de Londres. Soc. , 30 : 264–286, doi : 10.1112/plms/s2-30.1.264
• Piskac, R.; de Moura, L.; Bjorner, N. (diciembre de 2008), "Decidir eficazmente la lógica proposicional con igualdad" (PDF) , Informe técnico de investigación de Microsoft (2008–181)