Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Élimination des quantificateurs

En logique mathématique, ou plus précisément en théorie des modèles, l'élimination des quantificateurs est l'action consistant à trouver une formule sans quantificateur équivalente à une formule donnée contenant éventuellement des quantificateurs dans la théorie considérée d'un certain langage. Ainsi, si l'on considère la théorie des corps réels clos, le langage de cette théorie est L={+,•,

Source officielle

https://fr.wikipedia.org/wiki/Élimination_des_quantificateurs

À 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 (1)

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 use formal verification tools and explain the theory and ...

Séances de cours associées (15)

Élimination de l'arithmétique et des quantificateurs de Presbourg

Couvre l'arithmétique de Presbourg, l'élimination des quantificateurs et la transformation des formules en forme normale disjonctive.

La logique des prédicats : les équivalences, les négations et les lois de De Morgan

Explore la distribution des quantificateurs, des équivalences logiques et des négations dans la logique des prédicats.

Introduction à l'élimination des quantificateurs pour l'arithmétique de Presbourg

Introduit une méthodologie de vérification formelle et l'arithmétique de Presburger pour la vérification de programme et le raisonnement automatisé.

Afficher plus

Publications associées (22)

Interpolation and Quantifiers in Ortholattices

Viktor Kuncak, Simon Guilloud, Sankalp Gambhir

We study quantifiers and interpolation properties in ortho- logic, a non-distributive weakening of classical logic that is sound for formula validity with respect to classical logic, yet has a quadratic-time decision procedure. We present a sequent-based p ...

2024

Interpolation and Quantifiers in Ortholattices

Viktor Kuncak, Simon Guilloud, Sankalp Gambhir

We study quantifiers and interpolation properties in orthologic, a non-distributive weakening of classical logic that is sound for formula validity with respect to classical logic, yet has a quadratic-time decision procedure. We present a sequent-based pro ...

Springer International Publishing Ag2024

Decision Procedures for Power Structures

Rodrigo Raya

We study the decision problem for the existential fragment of the theory of power structures. We prove complexity results that parallel the decidability results of Feferman-Vaught for the theories of product structures thereby showing that the construction ...

EPFL2023

Afficher plus

Personnes associées (1)

Viktor Kuncak

Viktor Kunčak joined EPFL in 2007, after receiving a PhD degree from MIT. Since then has been leading the Laboratory for Automated Reasoning and Analysis and supervised at least 12 completed PhD theses. His works on languages, algorithms and systems for verification and automated reasoning. He served as an initiator and one of the coordinators of a European network (COST action) in the area of automated reasoning, verification, and synthesis. In 2012 he received a 5-year single-investigator European Research Council (ERC) grant of 1.5M EUR. His invited talks include those at Lambda Days, Scala Days, NFM, LOPSTR, SYNT, ICALP, CSL, RV, VMCAI, and SMT. A paper on test generation he co-authored received an ACM SIGSOFT distinguished paper award at ICSE. A PLDI paper he co-authored was published in the Communications of the ACM as a Research Highlight article. His Google Scholar profile reports an over-approximate H-index of 38. He was an associate editor of ACM Transactions on Programming Languages and Systems (TOPLAS) and served as a co-chair of conferences on Computer-Aided Verification (CAV), Formal Methods in Computer Aided Design (FMCAD), Workshop on Synthesis (SYNT), and Verification, Model Checking, and Abstract Interpretation (VMCAI). At EPFL he teaches courses on functional and parallel programming, compilers, and verification. He has co-taught the MOOC "Parallel Programming" that was visited by over 100'000 learners and completed by thousands of students from all over the world.

Unités associées (1)

Laboratoire d'analyse et de raisonnement automatisés

Source officielle

https://fr.wikipedia.org/wiki/Élimination_des_quantificateurs

À propos de ce résultat

Cours associés (1)

CS-550: Formal verification

Séances de cours associées (15)

Élimination de l'arithmétique et des quantificateurs de Presbourg

Couvre l'arithmétique de Presbourg, l'élimination des quantificateurs et la transformation des formules en forme normale disjonctive.

La logique des prédicats : les équivalences, les négations et les lois de De Morgan

Explore la distribution des quantificateurs, des équivalences logiques et des négations dans la logique des prédicats.

Introduction à l'élimination des quantificateurs pour l'arithmétique de Presbourg

Introduit une méthodologie de vérification formelle et l'arithmétique de Presburger pour la vérification de programme et le raisonnement automatisé.

Afficher plus

Publications associées (22)

Interpolation and Quantifiers in Ortholattices

Viktor Kuncak, Simon Guilloud, Sankalp Gambhir

2024

Interpolation and Quantifiers in Ortholattices

Viktor Kuncak, Simon Guilloud, Sankalp Gambhir

Springer International Publishing Ag2024

Decision Procedures for Power Structures

Rodrigo Raya

EPFL2023

Afficher plus

Personnes associées (1)

Viktor Kuncak

Unités associées (1)

Laboratoire d'analyse et de raisonnement automatisés

Concepts associés (7)

Théorie complète

En logique mathématique, une théorie complète est une théorie qui est équivalente à un ensemble maximal cohérent de propositions ; ceci signifie qu'elle est cohérente et que toute extension propre ne l'est plus. Pour des théories logiques qui contiennent la logique propositionnelle classique, ceci équivaut à la condition que pour toute proposition φ du langage de la théorie, soit elle contient φ, soit elle contient sa négation ¬φ.

Théorie axiomatique

Quand on parle de théorie mathématique, on fait référence à une somme d'énoncés, de définitions, de méthodes de preuve, etc. La théorie de la calculabilité en est un exemple. Par théorie axiomatique, on fait référence à quelque chose de plus précis, des axiomes et leurs conséquences, les théorèmes, énoncés dans un langage précis. Dans la suite on dira le plus souvent théorie pour théorie axiomatique, ce qui est d'usage courant en logique mathématique.

Model complete theory

In model theory, a first-order theory is called model complete if every embedding of its models is an elementary embedding. Equivalently, every first-order formula is equivalent to a universal formula. This notion was introduced by Abraham Robinson. A companion of a theory T is a theory T* such that every model of T can be embedded in a model of T* and vice versa. A model companion of a theory T is a companion of T that is model complete. Robinson proved that a theory has at most one model companion.

Afficher plus