Le calcul des prédicats, quantificateurs, récurrences

Résumé du document

Cours de Mathématiques sur le calcul des prédicats, quantificateurs, récurrences.

Extraits

[...] Au contraire, si les quantificateurs sont les mêmes, l'ordre n'a pas d'importance. La négation d'une proposition Il suffit de remplacer les quantificateurs par et par Puis de remplacer le prédicat par sa négation Exemple : Ecrire la négation de : Et de : : : Page 3 : SIXIEME PARTIE - PREDICATS QUANTIFICATEURS RECURRENCES Le principe de récurrence De nombreuses propositions qui concernent les nombres entiers sont construites au moyen d'un prédicat de poids 1 et du quantificateur universel Exemple : Pour tout entier n on a l'égalité suivante : = / 2 Cette affirmation est la proposition En fait, de telles propositions se démontrent par récurrence. [...]

[...] Donc les deux étapes doivent être vérifiées Donc : Exemple : = / 2 on cherche à savoir si l'on a qui est égal à / 2 si = à / 2 si = à ncarré+3n-4 / 2 si l'on ajoute un rang de plus aux deux membres de l'égalité : .+n + = + =ncarré-2n+3n-6+2n+2 / 2 = ncarré+3n-4 est vraie donc on a bien pourtant = = 3x-2 = fausse, donc on n'a pas Cas de n ! (factorielle L'on sait que n ! [...]

[...] Il faut introduire la notion de Prédicat. Les Prédicats L'affirmation n est pair ne peut pas être acceptée comme une proposition car, ne sachant pas combien vaut on ne peut pas dire si elle est vraie ou fausse. Cependant, chaque fois que l'on remplace n par un entier, on obtient une proposition (vraie pour n=2 ou fausse pour Cette affirmation donc, a sa valeur de vérité qui dépend de n ; on dit que c'est un Prédicat On peut voir un prédicat comme une application P qui associe une proposition à chaque élément x d'un ensemble U appelé univers du prédicat. [...]

[...] c'est ce que l'on va chercher à savoir en ajoutant un rang de plus aux deux membres, il vient : x n x x x1 = x n x ! = x n ! qui n'est autre que donc on vérifie bien Page 5 SIXIEME PARTIE - PREDICATS QUANTIFICATEURS RECURRENCES Variantes de l'induction faible Théorème Soient un prédicat de poids 1 sur N et d un entier naturel Si est vraie et si vraie, alors n la proposition est vraie. [...]

[...] Simplement selon les situation l'un est plus pratique que l'autre Chacun des deux principes d'induction est une conséquence de l'autre. De même que pour le principe d'induction faible, on retrouve le théorème : Soient un prédicat de poids 1 sur N et d un entier naturel Si est vraie et si la proposition Quel que soit n et et et . Et implique est vraie, alors la proposition est vraie quelque soit n d Signification profonde du principe de récurrence Le principe de récurrence équivaut au fait que ℕ, l'ensemble des entiers naturels est bien ordonné (sinon on ne pourrait pas travailler le principe de récurrence). [...]