Aller au contenu
Topos Uranos
Français

Le langage de la logique propositionnelle

Résumé

Cette leçon construit, à partir de rien, le langage dans lequel s’écriront toutes les formules du cours. Elle introduit d’abord l’indispensable sur les ensembles (appartenance, ensembles définis en extension et en compréhension, inclusion et réunion) et l’applique aux chaînes de symboles : leur longueur, leur concaténation et leurs préfixes, et le dénombrement des chaînes que l’on peut écrire avec deux symboles. Sur l’alphabet à deux symboles, le cercle et le disque, elle définit la langue de base : une infinité de variables, une seule règle de formation et une clause de clôture, dont on déduit un principe pour démontrer des propriétés de toutes les formules. Elle montre ensuite comment décider si une chaîne est une formule, énonce la lecture unique et, enfin, construit sur la langue de base le métalangage avec lequel on travaillera désormais : les métavariables, la négation conjointe écrite avec des parenthèses et les abréviations officielles des autres connecteurs, avec leur lecture en français.

Objectifs d’apprentissage

  1. Décrire des ensembles de chaînes en extension et en compréhension, et décider des relations d’appartenance, d’inclusion et de réunion entre eux.
  2. Dénombrer les chaînes d’une longueur donnée et celles de longueur bornée sur un alphabet à deux symboles.
  3. Décider si une chaîne de cercles et de disques est une formule et, lorsqu’elle l’est, reconstituer la façon dont elle a été formée.
  4. Démontrer que toutes les formules ont une propriété au moyen du principe de clôture, et utiliser ces propriétés pour écarter des chaînes.
  5. Distinguer le langage objet du métalangage, déplier une abréviation jusqu’à la chaîne de la langue de base et lire les formules en français.

Ce qu’il faut savoir des ensembles

Un langage formel est, avant tout, une collection de chaînes de symboles : s’il en est ainsi, pour en parler avec précision, il faut un vocabulaire pour les collections. Ce vocabulaire est celui des ensembles, dont cette leçon ne retient que ce dont le cours se servira. Un ensemble est une collection d’objets, appelés ses éléments, qui est déterminée par eux : deux ensembles qui ont les mêmes éléments sont le même ensemble. Qu’un objet aa soit élément de l’ensemble AA s’écrit a∈Aa \in A et se lit « aa appartient à AA » ; qu’il ne le soit pas s’écrit a∉Aa \notin A.

Un ensemble peut être donné de deux manières. En extension, en nommant un à un ses éléments entre accolades, sans que l’ordre ni les répétitions importent ; et en compréhension, en énonçant la condition que remplissent ses éléments et eux seuls, avec deux-points qui se lisent « tels que ». Ainsi, les entiers naturels inférieurs à 55 forment l’ensemble

{1,2,3,4}={n∈N:n<5}\{1, 2, 3, 4\} = \{ n \in \mathbb{N} : n < 5 \}

Une variante de la compréhension, très fréquente dans la suite, décrit les éléments par la forme qu’ils ont : {2n:n∈N}\{ 2n : n \in \mathbb{N} \} est l’ensemble des nombres de la forme 2n2n avec nn naturel, c’est-à-dire celui des nombres pairs. Un ensemble défini en extension est nécessairement fini ; en compréhension, on peut aussi donner des ensembles infinis, comme celui des nombres pairs.

On dit que AA est inclus dans BB, et l’on écrit A⊆BA \subseteq B, lorsque tout élément de AA est élément de BB. Il s’ensuit que deux ensembles sont égaux si et seulement si chacun est inclus dans l’autre, car ils ont alors les mêmes éléments ; et c’est là, en effet, la manière habituelle de démontrer une égalité d’ensembles : prouver les deux inclusions. Enfin, la réunion A∪BA \cup B est l’ensemble des objets qui appartiennent à AA, à BB ou aux deux ; d’où chacun des deux ensembles est inclus dans leur réunion.

ExempleAppartenance, inclusion et réunion

Soient A={1,2,3}A = \{1, 2, 3\}, B={2,4,6,8}B = \{2, 4, 6, 8\} et P={2n:n∈N}P = \{ 2n : n \in \mathbb{N} \}. On a 2∈A2 \in A et 4∉A4 \notin A ; de plus, B⊆PB \subseteq P, car chaque élément de BB est le double d’un entier naturel, tandis que AA n’est pas inclus dans PP, car 1∈A1 \in A et 1∉P1 \notin P. La réunion de AA et BB est {1,2,3,4,6,8}\{1, 2, 3, 4, 6, 8\} : le 22, qui est dans les deux, n’y figure qu’une fois.