stringtranslate.com

Demostrador del teorema Z3

Z3 , también conocido como Z3 Theorem Prover , es un solucionador de teorías de módulo de satisfacibilidad (SMT) desarrollado por Microsoft . [2]

Descripción general

Z3 fue desarrollado en el grupo de Investigación en Ingeniería de Software (RiSE) de Microsoft Research Redmond y está dirigido a resolver problemas que surgen en la verificación de software y el análisis de programas . Z3 admite aritmética, vectores de bits de tamaño fijo, matrices extensionales, tipos de datos, funciones no interpretadas y cuantificadores . Sus principales aplicaciones son la verificación estática extendida , la generación de casos de prueba y la abstracción de predicados . [ cita necesaria ]

Z3 fue de código abierto a principios de 2015. [3] El código fuente tiene la licencia MIT y está alojado en GitHub . [4] El solucionador se puede construir usando Visual Studio , un archivo MAKE o usando CMake y se ejecuta en Windows , FreeBSD , Linux y macOS .

El formato de entrada predeterminado para Z3 es SMTLIB2 . También tiene enlaces oficialmente compatibles para varios lenguajes de programación , incluidos C , C++ , Python , .NET , Java y OCaml . [5]

Ejemplos

Lógica proposicional y de predicados

En este ejemplo, las afirmaciones de lógica proposicional se verifican utilizando funciones para representar las proposiciones a y b. El siguiente script Z3 comprueba si :

(declarar-divertido un () Bool)(declarar-divertido b() Bool)(afirmar (no (= (no (y ab)) (o (no a)(no b)))))(check-sat)

Resultado:

insatisfecho

Nótese que el guión afirma la negación de la proposición de interés. El resultado insatisfecho significa que la proposición negada no es satisfacible, demostrando así el resultado deseado ( ley de De Morgan ).

Resolver ecuaciones

El siguiente script resuelve las dos ecuaciones dadas, encontrando valores adecuados para las variables a y b:

(declarar-const un Int)(declarar-const b Int)(afirmar (= (+ ab) 20))(afirmar (= (+ a (* 2 b)) 10))(check-sat)(obtener-modelo)

Resultado:

se sentó(modelo (definir-diversión b() Int -10) (definir-diversión a () Int 30))

Premios

En 2015, Z3 recibió el Premio Software de Lenguajes de Programación de ACM SIGPLAN . [6] [7] En 2018, Z3 recibió el premio Test of Time de las Conferencias Conjuntas Europeas sobre Teoría y Práctica del Software (ETAPS). [8] Los investigadores de Microsoft Nikolaj Bjørner y Leonardo de Moura recibieron el Premio Herbrand 2019 por Contribuciones Distinguidas al Razonamiento Automatizado en reconocimiento a su trabajo en el avance de la demostración de teoremas con Z3. [9] [10]

Ver también

Referencias

  1. ^ "Versión 4.13.0". 7 de marzo de 2024 . Consultado el 26 de marzo de 2024 .
  2. ^ "Uso del solucionador SMT Z3" (PDF) . Archivado desde el original (PDF) el 17 de noviembre de 2020 . Consultado el 1 de diciembre de 2019 .
  3. ^ "Cronología de Visual Studio de Microsoft y probador del teorema Z3, Google Cloud Launcher, Fresco de Facebook: resumen de noticias de SD Times: 27 de marzo de 2015". 27 de marzo de 2015.
  4. ^ "GitHub - Z3Prover/z3: el demostrador del teorema de Z3". 1 de diciembre de 2019 – vía GitHub.
  5. ^ Bjorner, Nikolaj; de Moura, Leonardo; Nachmanson, Lev; Wintersteiger, Christoph (2019). "Programación Z3". Programación Z3 . Archivado desde el original el 9 de febrero de 2023 . Consultado el 21 de mayo de 2023 .
  6. ^ "Premio Software de Lenguajes de Programación". www.sigplan.org .
  7. ^ El demostrador del teorema de Microsoft Z3 gana el premio
  8. ^ Premio Prueba del Tiempo ETAPS 2018
  9. ^ La magia interior detrás del demostrador del teorema Z3 - Microsoft Research
  10. ^ Premio Herbrand

Otras lecturas

enlaces externos