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