En informatique et en logique mathématique, un problème de satisfiabilité modulo des théories (SMT) est un problème de décision pour des formules de logique du premier ordre avec égalité (sans quantificateurs), combinées à des théories dans lesquelles sont exprimées certains symboles de prédicat et/ou certaines fonctions. Des exemples de théories incluent la théorie des nombres réels, la théorie de l’arithmétique linéaire, des théories de diverses structures de données comme les listes, les tableaux ou les tableaux de bits, ainsi que des combinaisons de celles-ci. Formellement, une instance de SMT est une formule du premier ordre sans quantificateur. Par exemple : Le problème SMT est de déterminer si une telle formule est satisfiable par rapport à une théorie sous-jacente. Par exemple, on peut se demander si la formule ci-dessus est satisfiable par rapport à la théorie des nombres réels. Autrement dit, il s'agit de savoir si l'on peut trouver des nombres réels pour les variables x et y qui rendent la formule ci-dessus vraie. On peut voir une instance d'un problème SMT comme une instance du problème de satisfiabilité de la logique propositionnelle dans laquelle les variables booléennes sont remplacées par des formules atomiques. Par exemple, la formule ci-dessus est la formule propositionnelle dans laquelle on a remplacé les variables booléennes p, q, r, s par des formules atomiques. Un solveur SMT fonctionne autour de deux cœurs principaux : un solveur SAT et une ou plusieurs procédures de décision de la théorie. L'idée est de tester si la formule propositionnelle correspondante (obtenue en remplaçant les prédicats par des variables booléennes) est satisfiable via un solveur SAT. Mais une instance de SMT, même si elle est satisfiable lorsqu’elle est vue comme une instance de SAT, n'est pas forcément satisfiable modulo une certaine théorie. Par exemple, n'est pas satisfiable par rapport à la théorie des réels, pourtant l'instance de SAT correspondante, p, est satisfiable.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (3)
CS-550: Formal verification
We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u
COM-516: Markov chains and algorithmic applications
The study of random walks finds many applications in computer science and communications. The goal of the course is to get familiar with the theory of random walks, and to get an overview of some appl
CS-320: Computer language processing
We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in
Séances de cours associées (31)
La satisfaction et les clusters
Couvre le seuil de satisfaisabilité, les clusters de solutions, le paramètre alpha et le calcul de cluster moyen.
Introduction à la résolution SMT
Introduit la résolution de théories modulo de satisfaction (SMT), couvrant la logique propositionnelle, les fonctions non interprétées et l'instanciation de quantificateur.
Optimisation quantitative adiabatique : problèmes combinatoires
Explore Quantum Optimisation approximative Algorithme pour résoudre efficacement les problèmes combinatoires.
Afficher plus
Publications associées (73)
Concepts associés (7)
Satisfaisabilité
En logique mathématique, la satisfaisabilité ou satisfiabilité et la validité sont des concepts élémentaires de sémantique. Une formule est satisfaisable s'il est possible de trouver une interprétation (modèle), une façon d'interpréter tous les éléments constitutifs de la formule, qui rend la formule vraie. Une formule est universellement valide, ou en raccourci valide si, pour toutes les interprétations, la formule est vraie.
Constraint logic programming
Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clauses. An example of a clause including a constraint is . In this clause, is a constraint; A(X,Y), B(X), and C(Y) are literals as in regular logic programming. This clause states one condition under which the statement A(X,Y) holds: X+Y is greater than zero and both B(X) and C(Y) are true.
Problème de satisfaction de contraintes
Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l'objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle. De nombreux CSP nécessitent la combinaison d'heuristiques et de méthodes d'optimisation combinatoire pour être résolus en un temps raisonnable.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.