Comptage quantification - Counting quantification

Un quantificateur de comptage est un terme mathématique désignant un quantificateur de la forme "il existe au moins k éléments qui satisfont la propriété X ", parfois désigné par . Dans la logique du premier ordre avec égalité, les quantificateurs de comptage peuvent être définis en termes de quantificateurs ordinaires, donc dans ce contexte, ils sont un raccourci notation. Cependant, ils sont intéressants dans le contexte de logiques telles que la logique à deux variables avec comptage , qui restreignent le nombre de variables dans les formules. De plus, les quantificateurs de comptage généralisés qui disent «il existe une infinité» ne sont pas exprimables en utilisant un nombre fini de formules en logique du premier ordre.

Voir également

Les références

  1. ^ "Liste complète des symboles logiques" . Math Vault . 2020-04-06 . Récupéré 04/09/2020 .
  2. ^ Cohen, Mark (2004). "Chapitre 14: Plus d'informations sur la quantification" (PDF) . faculty.washington.edu . Récupéré le 4 septembre 2020 .
  3. ^ Helman, Glen (1er août 2013). "8.3. Quantification numérique" (PDF) . persweb.wabash.edu . Récupéré le 4 septembre 2020 .

Bibliographie

  • Erich Graedel, Martin Otto et Eric Rosen. "La logique à deux variables avec comptage est décidable." In Proceedings of 12th IEEE Symposium on Logic in Computer Science LICS `97 , Warschau. 1997. Fichier Postscript OCLC  282402933