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