This HTML5 document contains 73 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
n7http://g.co/kg/g/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
n11http://fr.dbpedia.org/resource/Modèle:
n4http://fr.dbpedia.org/resource/Fichier:
n9http://commons.wikimedia.org/wiki/Special:FilePath/
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n12http://ma-graph.org/entity/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/

Statements

Subject Item
dbpedia-fr:Logique_monadique_du_second_ordre
rdfs:label
Logique monadique du second ordre
rdfs:comment
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 :
owl:sameAs
wikidata:Q26899137 n7:11bwdwb2gl n12:2776241933 dbpedia-de:Monadische_Prädikatenlogik_zweiter_Stufe dbr:Monadic_second-order_logic
dbo:wikiPageID
10287884
dbo:wikiPageRevisionID
184483847
dbo:wikiPageWikiLink
n4:Mso.svg dbpedia-fr:Théorème_de_Rabin_sur_les_arbres n4:Mso_graphenonconnexe.svg dbpedia-fr:Logique_monadique_du_premier_ordre dbpedia-fr:Langage_sans_étoile dbpedia-fr:Logique_modale dbpedia-fr:Langage_rationnel n4:Petersen_graph_3-coloring.svg dbpedia-fr:Formule_logique dbpedia-fr:Théorie_des_graphes dbpedia-fr:Axiomatisation dbpedia-fr:Prédicat_(logique_mathématique) dbpedia-fr:Largeur_arborescente dbpedia-fr:Convexité category-fr:Informatique_théorique dbpedia-fr:Quantificateur_(logique) dbpedia-fr:Factorielle dbpedia-fr:Graphe_connexe dbpedia-fr:Calcul_des_prédicats dbpedia-fr:Ensemble_définissable dbpedia-fr:Problème_NP-complet dbpedia-fr:Complexité dbpedia-fr:Schéma_d'axiomes_de_compréhension dbpedia-fr:Quantification_existentielle dbpedia-fr:Théorème_de_compacité dbpedia-fr:Logique_d'ordre_supérieur dbpedia-fr:Classe_(mathématiques) dbpedia-fr:Bisimulation dbpedia-fr:Décidabilité dbpedia-fr:Informatique_théorique dbpedia-fr:Théorie_des_modèles_finis dbpedia-fr:Arithmétique_de_Presburger dbpedia-fr:Théorie_des_modèles dbpedia-fr:Puissance_d'un_nombre dbpedia-fr:Julius_Richard_Büchi dbpedia-fr:Théorème_de_Courcelle dbpedia-fr:Algorithmique dbpedia-fr:Groupe_(mathématiques) dbpedia-fr:Axiomes_de_Peano dbpedia-fr:Structure_(mathématiques) dbpedia-fr:Langage_formel dbpedia-fr:Mu-calcul dbpedia-fr:Coloration_de_graphe dbpedia-fr:Logique_mathématique dbpedia-fr:Yuri_Gurevich dbpedia-fr:Théorie_de_la_calculabilité dbpedia-fr:Arité dbpedia-fr:Ensemble
dbo:wikiPageLength
21721
dct:subject
category-fr:Informatique_théorique
prop-fr:wikiPageUsesTemplate
n11:Portail n11:Références n11:Section_vide_ou_incomplète n11:, n11:Section_à_sourcer n11:Formule n11:Langue
prov:wasDerivedFrom
wikipedia-fr:Logique_monadique_du_second_ordre?oldid=184483847&ns=0
foaf:depiction
n9:Petersen_graph_3-coloring.svg n9:Mso.svg n9:Mso_graphenonconnexe.svg
dbo:thumbnail
n9:Mso.svg?width=300
foaf:isPrimaryTopicOf
wikipedia-fr:Logique_monadique_du_second_ordre
dbo:abstract
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 : * 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 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 , MSO est une source de théories logiques à la fois expressives et décidables.