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