stringtranslate.com

Demostrador del teorema Z3

Z3 , también conocido como demostrador de teoremas Z3 , 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) en Microsoft Research Redmond y está orientado 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 extensivas, tipos de datos, funciones no interpretadas y cuantificadores . Sus principales aplicaciones son la comprobación estática extendida , la generación de casos de prueba y la abstracción de predicados . [ cita requerida ]

Z3 se convirtió en 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 crear utilizando Visual Studio , un makefile o utilizando CMake y se ejecuta en Windows , FreeBSD , Linux y macOS .

El formato de entrada predeterminado para Z3 es SMTLIB2 . También tiene enlaces admitidos 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, se comprueban las afirmaciones de lógica proposicional mediante funciones para representar las proposiciones a y b. El siguiente script Z3 comprueba si :

(declarar-fun a() Bool)(declarar-fun b() Bool)(afirmar (no (= (no (y ab)) (o (no a)(no b)))))(cheque-sat)

Resultado:

insatisfecho

Nótese que el guión afirma la negación de la proposición de interés. El resultado no satisfactorio 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 un Int)(declarar-const b Int)(afirmar (= (+ ab) 20))(afirmar (= (+ a (* 2 b)) 10))(cheque-sat)(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 contribuciones destacadas 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 4.13.3". 11 de octubre de 2024. Consultado el 27 de octubre de 2024 .
  2. ^ "Uso del solucionador SMT Z3" (PDF) . Archivado desde el original (PDF) el 2020-11-17 . Consultado el 2019-12-01 .
  3. ^ "Cronología de Visual Studio de Microsoft y Z3 Theorem Prover, Google Cloud Launcher, Fresco de Facebook: resumen de noticias del SD Times: 27 de marzo de 2015". 27 de marzo de 2015.
  4. ^ "GitHub - Z3Prover/z3: El demostrador del teorema Z3". 1 de diciembre de 2019 – vía GitHub.
  5. ^ Bjørner, 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 de Software de Lenguajes de Programación". www.sigplan.org .
  7. ^ El demostrador de teoremas Z3 de Microsoft gana un premio
  8. ^ Premio Prueba del Tiempo ETAPS 2018
  9. ^ La magia interna detrás del demostrador del teorema Z3 - Microsoft Research
  10. ^ Premio Herbrand

Lectura adicional

Enlaces externos