Hispanopedia Wiki
Articulo de referencia

Demostrador de teoremas Z3

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

Hispanopedia WikiContenido en espanolLectura gratuita

Z3 , también conocido como Z3 Theorem Prover , es un solucionador de satisfacibilidad módulo teorías (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á diseñado para 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 .

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

El formato de entrada predeterminado para Z3 es SMTLIB2 . También cuenta con enlaces compatibles oficialmente 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 aserciones de lógica proposicional se verifican utilizando funciones para representar las proposiciones a y b. El siguiente script Z3 verifica sia∧b¯≡a¯∨b¯{\displaystyle {\overline {a\land b}}\equiv {\overline {a}}\lor {\overline {b}}}:

(declarar-fun a () Bool) (declarar-fun b () Bool) (afirmar (no (= (no (y ab)) (o (no a)(no b))))) (verificación-sábado)

Resultado:

insatisfecho

Nótese que el script afirma la negación de la proposición de interés. El resultado insatisfacible significa que la proposición negada no es satisfacible, lo que demuestra 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 a Int) (declarar-const b Int) (afirmar (= (+ ab) 20)) (afirmar (= (+ a (* 2 b)) 10)) (verificación-sábado) (obtener-modelo)

Resultado:

se sentó (modelo (define-fun b () Int -10) (define-fun a () Int 30) )

Premios

En 2015, Z3 recibió el premio Programming Languages ​​Software Award de ACM SIGPLAN . [ 6 ] [ 7 ] En 2018, Z3 recibió el premio Test of Time Award de las European Joint Conferences on Theory and Practice of Software (ETAPS). [ 8 ] Los investigadores de Microsoft Nikolaj Bjørner y Leonardo de Moura recibieron el premio Herbrand 2019 por sus destacadas contribuciones al razonamiento automatizado en reconocimiento a su trabajo en el avance de la demostración de teoremas con Z3. [ 9 ] [ 10 ]

Véase también

Referencias

  1. ↑ "Versión 5.0.0" . 17 de julio de 2026. Consultado el 17 de julio de 2026 .
  2. ↑ "Uso del solucionador SMT Z3" (PDF) . Archivado del original (PDF) el 17/11/2020 . Consultado el 01/12/2019 .
  3. ↑ "Cronología de Visual Studio de Microsoft y Z3 Theorem Prover, 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 de teoremas Z3" . 1 de diciembre de 2019 – vía GitHub.
  5. ↑ Bjørner, Nikolaj; de Moura, Leonardo; Nachmanson, Lev; Wintersteiger, Christoph (2019). "Programming Z3" . Programming Z3 . Archivado del original el 9 de febrero de 2023. Recuperado el 21 de mayo de 2023 .
  6. ↑ "Premio de Software de Lenguajes de Programación" . www.sigplan.org .
  7. ↑ El demostrador de teoremas Z3 de Microsoft gana un premio
  8. ↑ "Premio ETAPS 2018 a la trayectoria" . Archivado del original el 8 de agosto de 2020. Consultado el 21 de diciembre de 2019 .
  9. ↑ La magia interna detrás del demostrador de teoremas Z3 - Microsoft Research
  10. ↑ Premio Herbrand

Lecturas adicionales

  • Leonardo De Moura; Nikolaj Bjørner (2008). "Z3: un solucionador SMT eficiente". Herramientas y algoritmos para la construcción y el análisis de sistemas . 4963 : 337–340 .
  • La magia interna detrás del demostrador de teoremas Z3
  • Sitio web oficial
  • Parque infantil oficial