Metraipolis › archive › dc_d07bca46c446
Logique monadique du second ordre — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Logique_monadique_du_second_ordre
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-10T13:48:50.326Z
- SHA-256 of the archived text
31a8b8990ac4c7adddfe335ccfb1b815fb43723255753a6e416564ab68d65950- Stable URL of this page
https://metraipolis.com/documento/dc_d07bca46c446
How to cite
Logique monadique du second ordre — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Logique_monadique_du_second_ordre (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_d07bca46c446 (Metraipolis archive dc_d07bca46c446, sha256 31a8b8990ac4c7adddfe335ccfb1b815fb43723255753a6e416564ab68d65950)
BibTeX
@misc{dcd07bca46c446,
title = {Logique monadique du second ordre — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Logique_monadique_du_second_ordre},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_d07bca46c446; sha256 31a8b8990ac4c7adddfe335ccfb1b815fb43723255753a6e416564ab68d65950},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Logique_monadique_du_second_ordre. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En logique mathématique et en informatique théorique, la logique monadique du second ordre (abrégé en MSO pour monadic second order) est l'extension de la logique du premier ordre avec des variables dénotant des ensembles. De manière équivalente, c'est le fragment de la logique du second ordre où les quantifications du second ordre ne portent que sur des prédicats unaires (d'où le terme monadique), c'est-à-dire sur des ensembles. Par exemple : ∃ Z ( ∃ u , u ∈ Z ) ∧ ∀ x , ( x ∈ Z → ∃ y , ( fils ( x , y ) ∧ y ∈ Z ) ) {\displaystyle \exists Z(\exists u,u\in Z)\land \forall x,(x\in Z\rightarrow \exists y,({\text{fils}}(x,y)\land y\in Z))} est une formule de MSO et elle se lit « il existe un ensemble Z tel qu'il existe un élément u qui appartient à Z et pour tout x, si x est dans Z, alors il existe y tel que y est fils de x et y est dans Z ». Ce n'est pas une formule de la logique du premier ordre car il y a une quantification du second ordre sur Z ; Toutes les formules de la logique du premier ordre sont des formules de MSO ; La formule ∃ R , ∃ x , ∀ y , R ( x , y ) {\displaystyle \exists R,\exists x,\forall y,R(x,y)} n'est pas une formule de MSO car il y a une quantification sur un prédicat binaire R. Le problème de satisfiabilité de la logique du premier ordre étant indécidable, comme MSO est une extension conservatrice de la logique du premier ordre, le problème de satisfiabilité de MSO est aussi indécidable. Mais selon Yuri Gurevich, MSO est une source de théories logiques à la fois expressives et décidables.
Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Logique monadique du second ordre» — https://fr.wikipedia.org/wiki/Logique_monadique_du_second_ordre
Wikidata Q26899137: «form of second‐order logic in which one can quantify over sets but not over predicates» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q26899137
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Logique_monadique_du_second_ordre?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 215094476, consultata il 2026-11-10T13:45:23.797Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 3867d5824f7b76458a4505b04808d5b77c9b06602447c46afeecd417a1a9199b