A) Théorème de Fagin, 1974 B) Théorème de Shapiro, 2000 C) Théorème de Henkin, 1950 D) Théorème de Büchi-Elgot-Trakhtenbrot, 1960
A) PSPACE B) co-NP C) NP D) PH
A) NP B) co-NP C) PSPACE D) EXPTIME
A) PH B) REG C) EXPTIME D) NP
A) EXPTIME B) NP C) PSPACE D) PH
A) NP B) co-NP C) EXPTIME D) PSPACE
A) L’ajout d’un opérateur de point fixe minimal ne la rendrait pas plus expressive. B) Cela rendrait la logique du second ordre moins expressive. C) Cela rendrait la logique du second ordre équivalente à la logique du premier ordre. D) L’ajout d’un opérateur de fermeture transitive ne la rendrait pas plus expressive.
A) Väänänen, J. (2001) B) Hinman, P. (2005) C) Shapiro, S. (2000) D) Quine, W. V. (1970)
A) Henkin, L. B) Shapiro, S. C) Väänänen, J. D) Quine, W. V.
A) Väänänen, J. (2001) B) Quine, W. V. (1970) C) Hinman, P. (2005) D) Shapiro, S. (2000)
A) Théorème de Büchi-Elgot-Trakhtenbrot, 1960 B) Théorème de Shapiro, 2000 C) Henkin, L. (1950) D) Théorème de Fagin, 1974
A) Le théorème de Fagin B) Le théorème de Shapiro C) Le théorème de Henkin D) Le théorème de Büchi-Elgot-Trakhtenbrot
A) Classes de complexité computationnelle B) Structures finies C) Langages réguliers D) Tables de Cayley
A) Si PH = PSPACE, l'ajout d'un opérateur de point fixe minimal n'augmente pas la capacité d'expression. B) PSPACE est toujours plus expressif que PH. C) PH est toujours plus expressif que PSPACE. D) Si PH = PSPACE, l'ajout d'un opérateur de fermeture transitive n'augmente pas la capacité d'expression.
A) Un langage EXPTIME B) Un langage régulier C) Une table de Cayley d’une structure finie D) Une chaîne finie w = w1···wn dans un alphabet fini A
A) Henkin, L. (1950) B) Hinman, P. (2005) C) Shapiro, S. (2000) D) Quine, W. V. (1970)
A) Elles sont équivalentes à la logique du second ordre. B) Elles peuvent être codées par une chaîne de caractères finie. C) Elles caractérisent la classe NP. D) Elles définissent des langages réguliers.
A) Uniquement sur les sous-ensembles du domaine. B) Uniquement sur les fonctions dont le domaine est fini. C) Sur tous les ensembles ou toutes les fonctions du type approprié. D) Uniquement sur les ensembles finis.
A) Uniquement l'ensemble vide B) Un sous-ensemble propre de tous les ensembles ou fonctions de ce type C) L'ensemble des parties complet de la partie d'ordre 1 du modèle D) Uniquement les ensembles finis
A) L'existence d'interprétations non standard des domaines d'ordre supérieur B) La complétude de la logique du second ordre C) La compacité de la logique du second ordre D) L'unicité de l'interprétation standard
A) Son utilisation de domaines finis B) Sa capacité à quantifier sur des ensembles C) Sa capacité à quantifier uniquement sur des éléments individuels D) Sa dépendance à la logique du premier ordre
A) Tout ensemble est fini. B) Tout ensemble borné et non vide possède un supremum. C) Tout ensemble est dénombrable. D) Tout ensemble possède un élément maximal.
A) L'existence d'ensembles infinis B) La finitude et la dénombrabilité du domaine C) L'existence de nombres réels D) La non dénombrabilité du domaine
A) La logique du premier ordre avec les quantificateurs de Henkin B) La logique existentielle du second ordre (ESO) C) La logique du second ordre complète D) La logique du premier ordre avec le théorème d’incomplétude de Gödel
A) ↔ B) → C) ∃ D) ∀
A) « P(0) » B) « P(n) » C) « P(n+1) » D) « P(n-1) »
A) Oui B) Non C) Elle n’est pas décidable D) Uniquement sous certaines conditions
A) Décidable sous certaines conditions B) Décidable uniquement pour les ensembles finis C) Décidable D) Indécidable
A) Hiérarchie computationnelle B) Hiérarchie logique C) Hiérarchie arithmétique D) Hiérarchie analytique
A) Un nombre infini de modèles. B) Aucun modèle. C) De nombreux modèles, y compris des modèles dénombrables. D) Un seul modèle.
A) Le théorème de Löwenheim-Skolem. B) Le théorème d’incomplétude de Gödel. C) Il n’existe qu’un seul corps ordonné archimédien complet. D) Le théorème de Cantor.
A) Une théorie qui caractérise les nombres réels comme un corps ordonné archimédien complet, auquel s’ajoute un axiome concernant la cardinalité du domaine. B) Une théorie qui n’inclut que des axiomes de logique du premier ordre. C) Une théorie qui suppose que l’hypothèse du continu est fausse. D) Une théorie qui définit les nombres réels sans aucune référence à la cardinalité.
A) Gottlob Frege B) Gödel C) Skolem D) C. S. Peirce
A) Le paradoxe de Skolem B) Le théorème de Löwenheim-Skolem C) Le paradoxe de Russell D) Le théorème d'incomplétude de Gödel
A) George Boolos B) Gottlob Frege C) C. S. Peirce D) W. V. Quine |