Le langage de la Logique Propositionnelle : Alphabets et chaînes de symboles

Commençons avec un seul symbole

Pour construire le langage de la Logique Propositionnelle, nous débuterons notre étude à partir de l’alphabet le plus simple : celui qui possède un unique symbole. Peu importe sa forme, ce qui compte, c’est qu’il est unique. Si nous écrivons en utilisant un tel alphabet, ce qui distingue une chaîne de symboles d’une autre est le nombre de fois que ce symbole est répété. Ainsi, si nous avons la capacité d’écrire des chaînes de symboles jusqu’à une longueur N, nous ne pourrons écrire que N chaînes différentes. Comme vous pouvez le voir, cet alphabet est très limité et il n’y a pas grand-chose d’autre à en dire.

Ajoutons donc un second symbole

Si nous ajoutons un second symbole à notre alphabet, l’écriture devient plus riche qu’avec l’alphabet précédent. Nous pouvons maintenant apprécier la manière dont les symboles sont ordonnés, par exemple si 0 et 1 sont nos symboles, nous pouvons distinguer 01 de 10. Les deux chaînes impliquent les mêmes symboles, mais dans un ordre différent. Si la chaîne la plus longue que nous pouvons écrire a une longueur N =1,2,3,\cdots, alors nous pouvons écrire 2^1=2 chaînes de longueur 1, 2^2=4 chaînes de longueur 2, 2^3=8 chaînes de longueur 3, et ainsi de suite jusqu’à 2^N chaînes différentes de longueur N.

Exercice : On écrit sur une feuille toutes les chaînes distinctes que l’on peut écrire avec entre 1 et N symboles. Combien de chaînes sont écrites au total ?

Solution :
Si S_N est la somme de toutes les chaînes, de longueur 1, 2, 3, etc., jusqu’à N, alors nous avons déjà vu que :

\displaystyle S_N=2^1 + 2^2 + \cdots + 2^{N-1} + 2^N

En multipliant l’expression précédente par 2, on obtient :

\displaystyle 2 S_N=2^2 + 2^3 + \cdots + 2^N + 2^{N+1}

Et par conséquent :

\displaystyle S_N=2 S_N - S_N = 2^{N+1} - 1

En conséquence, le nombre total de chaînes écrites sur la feuille sera 2^{N+1} - 1.

Le langage de la Logique Propositionnelle : Syntaxe

Nous avons vu qu’avec deux symboles, nous pouvons distinguer une chaîne d’une autre par sa longueur et par l’ordre dans lequel les symboles sont disposés. Ceci est important car cela nous permet de définir une syntaxe pour l’alphabet que nous avons construit. Une syntaxe est un ensemble de règles qui séparent les chaînes de symboles en deux catégories : Expressions et Non-Expressions. Si \mathcal{L}_2 est l’ensemble de toutes les chaînes qui peuvent être construites avec les symboles 0 et 1, alors la syntaxe de \mathcal{L}_2 est un sous-ensemble \mathcal{SL}_2\subset\mathcal{L}_2.

Nous pouvons définir l’ensemble \mathcal{SL}_2 avec les règles récursives suivantes :

1. 00, 11 \in \mathcal{SL}_2
2. Si \alpha, \beta \in \mathcal{SL}_2, alors 01\alpha\beta \in \mathcal{SL}_2

Avec ces deux règles, nous pouvons construire des expressions de la langue et vérifier si une chaîne donnée est une expression de la langue. Une langue est un alphabet avec une syntaxe associée. À la langue qui est présentée ici, nous donnerons le nom de « Langue de Base à deux Symboles », ou \mathcal{B}_2.

Exemples de révision de syntaxe

Pour rendre ces idées un peu plus faciles à comprendre, examinons les exemples suivants :

Exemple : Étant donné que 00 et 11 sont contenus dans \mathcal{SL}_2, il s’ensuit que 010000, 010011, 011100 et 011111 sont dans \mathcal{SL}_2 ; par conséquent, ce sont des expressions de \mathcal{B}_2. Cela est démontré en appliquant les règles que nous venons d’introduire.

Fin de l’exemple \blacksquare

Exercice : Dans l’exemple précédent, nous avons vu comment construire des expressions à partir de deux autres expressions élémentaires. En soi, cela n’est pas une tâche compliquée ; cependant, dans le processus inverse, qui consiste à démontrer si une certaine expression est ou non une expression, nous pourrions rencontrer quelque chose d’un peu plus difficile.

Déterminez, en utilisant les règles de syntaxe, si les chaînes suivantes sont ou non des expressions de \mathcal{B}_2 :

1. {}012100

2. 101100

3. {}0100010000

4. 0101000011

5. {}01010000010000

6. 01010010000100101000011

Solution :
Avant de voir la solution, je te recommande d’essayer d’abord par toi-même et ensuite comparer les résultats. Si tu l’as déjà fait, alors allons-y 👍

1. 012100.

   Comme nous pouvons le voir, cela inclut le symbole 2, qui n’est pas contenu dans \mathcal{L}_2 ; cette chaîne ne peut pas être contenue dans \mathcal{SL}_2 et par conséquent n’est pas une expression de \mathcal{B}_2.

2. 101100.

   Ici on voit que cette chaîne commence par 10. Des règles de syntaxe, nous pouvons déduire que toutes les chaînes de longueur supérieure à 2 commencent nécessairement par 01, par conséquent, elle ne peut pas être une expression de \mathcal{B}_2.

3. 0100010000

   Cette chaîne commence par 01, donc elle passe le premier test. A partir de là, pour qu’elle soit une expression de \mathcal{L}_2, il est nécessaire que ce qui est marqué en bleu puisse être décomposé de manière unique en deux expressions.

   0100010000

   Si même en respectant les règles de syntaxe la décomposition n’est pas unique, alors la syntaxe qui a été définie est ambiguë et doit donc être corrigée.
   

   En analysant la partie bleue, on a les séparations possibles suivantes :

   00010000	00010000	00010000
   00010000	00010000	00010000
   00010000

   En observant la partie verte et en notant le fait que si ce n’est pas 00 ou 11, alors cela doit commencer par 01 pour être une expression, il est possible d’effectuer les rejets suivants

   0{}0010000❌	00010000	000{}10000❌
   00010000❌	00010000❌	00010000❌
   00010000❌

   La seule chaîne qui survit à cette analyse est 00010000, où la partie verte est une expression et la bleue se sépare de manière unique et cohérente avec la syntaxe comme : 010000 ; c’est-à-dire, un 01 suivi de deux 00, ce qui constitue une expression. Par conséquent, la chaîne 0100010000 se décompose de manière unique dans ses composants fondamentaux selon les lois de syntaxe, donc c’est une expression de \mathcal{B}_2

4. 0101000011

   Pour cette chaîne, nous pouvons faire la séparation suivante, que je marque avec des couleurs :

   0101000011

   Selon les règles de syntaxe, pour qu’une chaîne de longueur supérieure à 2 soit une expression, il est nécessaire qu’elle commence par 01, et après cela doivent suivre deux expressions, que j’ai marquées en bleu et vert. Il est facile de voir que cette séparation est unique, car si la zone bleue ou verte change de longueur, n’importe quel changement que ce soit, les deux parties ne seront plus des expressions en même temps.

5. 01010000010000

   En vérifiant de droite à gauche, nous pouvons trouver la séparation suivante :

   
   \underbrace{01\underbrace{01\overbrace{00}\overbrace{00}}_{{expression}}\underbrace{01\overbrace{00}\overbrace{00}}_{{expression}}}_{{expression}}

6. 01010010000100101000011

   Un œil averti remarquera que cette chaîne a une longueur de 23 et qu’il est impossible de construire une chaîne de longueur impaire à travers les lois de syntaxe de \mathcal{L}_2, qui construit des expressions en juxtaposant des chaînes de longueur paire. Toutes les chaînes de \mathcal{SL}_2 ont une longueur paire, donc 01010010000100101000011 n’est pas une expression de \mathcal{B}_2.

Fin de l’exercice \blacksquare

Conventions de Notation

Travailler avec des zéros et des uns peut être déroutant pour notre perception et peut nous conduire à faire des erreurs. Pour rendre le processus plus convivial pour la manière dont les humains interprètent les choses, nous pouvons utiliser des conventions de notation et certains méta-symboles.

Méta-variables et le connecteur \downarrow

Un méta-symbole est un symbole utilisé pour représenter des chaînes de symboles d’un langage cible. Par exemple, lors de la définition de la syntaxe \mathcal{SL}_2 de \mathcal{L}_2, les symboles \alpha et \beta ont été utilisés pour représenter des expressions de \mathcal{B}_2. Ces symboles sont appelés méta-variables de \mathcal{B}_2 : des méta-symboles qui, lorsqu’ils sont tous remplacés par des expressions du langage, génèrent à travers la syntaxe une autre expression du langage, comme l’établit la deuxième règle sur les éléments de \mathcal{SL}_2 :

Si \alpha,\beta \in \mathcal{SL}_2, alors 01\alpha\beta \in\mathcal{SL}_2

Pour cette raison, on dit que ces méta-variables sont méta-expressions de \mathcal{B}_2.

Pour faciliter notre écriture à l’avenir, nous utiliserons le méta-symbole \downarrow pour représenter la chaîne 01. Ce méta-symbole est ce que nous appelons un connecteur et est connu sous le nom de Négation Conjointe pour des raisons sémantiques.

Avec cela, nous pouvons exprimer la syntaxe \mathcal{SL}_2 de manière métalinguistique à travers les règles récursives suivantes :

1. Toutes les méta-variables de \mathcal{B}_2 sont des méta-expressions \mathcal{B}_2

2. Si \alpha et \beta sont des méta-variables de \mathcal{B}_2, alors \downarrow\alpha\beta est une méta-expression de \mathcal{B}_2

Avec ces règles, nous pouvons écrire des méta-expressions qui, lorsque toutes leurs méta-variables sont remplacées par des expressions et des connecteurs sous leur forme représentée par des zéros et des uns, donnent une expression de \mathcal{B}_2. Chaque méta-expression de ce type fait référence à une famille infinie d’expressions de \mathcal{B}_2 : l’ensemble de toutes les expressions de \mathcal{B}_2 qui peuvent être représentées avec cette structure. C’est exactement ce que signifie avoir un langage formel.

Exemples de l’utilisation de la négation conjointe

Exemple : À partir de la méta-expression \downarrow\alpha\downarrow\beta\gamma, on peut obtenir, par remplacements, les expressions suivantes :

1. En remplaçant \alpha := 00, \beta := 011100 et \gamma := 010011

   On arrive à l’expression :

   010001011100010011

2. Si on substitue \alpha := 011100, \beta := 0111011100 et \gamma := 0111010011

   On génère :

   010111000101110111000111010011

La méta-expression \downarrow\alpha\downarrow\beta\gamma n’est pas seulement plus facile à assimiler que toute autre expression qui satisfait sa forme, mais elle représente également toutes les expressions qui peuvent être obtenues à partir de celle-ci en remplaçant ses méta-variables par des expressions.

Fin de l’exemple \blacksquare

Lorsqu’on remplace une méta-variable, on la remplace dans tous les endroits où elle apparaît

Exemple : Considérons la méta-expression \downarrow\downarrow\alpha\beta\downarrow\alpha\gamma

1. Si on remplace \alpha:=11, alors on obtient :

   \downarrow\downarrow 11\beta\downarrow 11\gamma

2. Si maintenant on fait \beta:=011100, le résultat sera :

   \downarrow\downarrow 11011100\downarrow 11\gamma

3. Et si maintenant on effectue le changement \gamma:=011111, il nous restera :

   \downarrow\downarrow 11011100\downarrow 11011111

4. Finalement, en changeant \downarrow:=01, nous conclurons avec cette expression :

   0101110111000111011111

Fin de l’exemple \blacksquare

Réarrangement et parenthèses

Vérifier que ceci est une méta-expression n’est pas particulièrement difficile, mais cela nécessite de compter les symboles sans risquer de perdre le compte en cours de route. Ce risque augmente rapidement avec l’allongement de la méta-expression. Existe-t-il une manière de la représenter de façon plus lisible ? Oui, nous pouvons utiliser des parenthèses et réarranger la méta-expression selon notre manière naturelle de grouper les choses. Pour établir ce point, examinons la méta-expression suivante :

\downarrow\alpha\downarrow\downarrow\alpha\beta\alpha

Il s’avère que, bien qu’il ne soit pas particulièrement difficile de vérifier que ceci est une méta-expression, ce n’est pas quelque chose que nous pouvons faire sans être forcés de compter les symboles sans risquer de perdre le compte en cours de processus, et le risque augmente rapidement à mesure que la longueur de la méta-expression s’accroît. Y aurait-il une manière de représenter la même chose d’une manière plus confortable à lire ? La vérité est que cette méthode existe et est configurée selon notre manière naturelle de grouper les choses. Pour cela, les parenthèses et le réarrangement sont introduits à travers la convention de notation suivante :

\downarrow\alpha\beta := (\alpha\downarrow\beta)

Exemple : Considérons la méta-expression \downarrow\alpha\downarrow\downarrow\beta\gamma\delta. Si nous appliquons l’introduction de parenthèses et le réarrangement, alors elle se transformera de la manière suivante :

Cette dernière méta-expression est bien plus facile à lire et à réviser que l’originale, car chaque bloc de parenthèses est une méta-expression qui se compose d’éléments faciles à distinguer : une négation conjointe au centre et une méta-expression de chaque côté.

Fin de l’exemple \blacksquare

Connecteurs Dérivés

Tant en logique qu’en mathématiques en général, il existe certaines combinaisons de connecteurs qui sont fréquemment utilisées. C’est pour cette raison que, pour rendre l’écriture (pour les humains) encore plus confortable, on introduit les connecteurs dérivés à travers les conventions de notation suivantes :

Ce métalangage que nous avons construit sur la langue de base de deux symboles est ce qui est connu comme Langage d’Ordre Zéro de la Logique Propositionnelle. C’est à travers ce langage que toutes les expressions de la logique propositionnelle sont représentées de manière précise et sans ambiguïtés.

Vocalisation des expressions de la logique propositionnelle

Bien qu’il ne soit pas nécessaire pour pratiquer la logique, il est important de garder à l’esprit que notre communication ne repose pas uniquement sur des symboles écrits, mais que nous avons aussi une tendance naturelle à vocaliser les choses dans notre langue naturelle. C’est pourquoi, pour les expressions du langage de la logique propositionnelle, il existe des vocalisations qui évoquent des idées similaires à celles traitées par leurs homologues dans la logique propositionnelle. Ces vocalisations sont les suivantes :

Synthèse et réflexions sur le langage de la logique propositionnelle

Avec cette dernière partie s’achève la construction du langage de la logique propositionnelle, que nous pouvons synthétiser comme un métalangage permettant de produire des expressions valides dans la langue de base à partir de deux symboles. Le langage de la logique propositionnelle est un langage formel, car il définit la structure (ou la forme) des expressions dans la langue de base, et chacune de ses expressions détermine la forme d’une famille infinie d’expressions dans la langue de base. Comme nous l’avons mentionné précédemment, la syntaxe d’un langage formel est extrêmement rigide, mais en retour elle est précise et exacte : elle n’a pas d’ambiguïté.

La Matrice derrière la Matrice et la compréhension de toutes choses

Encore une chose. La logique propositionnelle et les mathématiques reposent en grande partie sur la logique propositionnelle, qui est à son tour construite sur une langue de base formée de un et de zéro. Cela signifie-t-il que nous avons atteint la « Matrice » derrière la logique et les mathématiques ? C’est possible. Mais il est également envisageable de considérer une langue de base pour cette langue de base, à partir de laquelle il serait possible de reconstruire tout le reste ; cependant, pour trouver une telle langue, nous aurions besoin de découvrir des notions encore plus fondamentales que les concepts d’ordre et de quantité (ceux qui ont été utilisés pour établir la première langue de base). Trouver une langue de base de la base implique de réfléchir sur les aspects les plus fondamentaux de ce que signifie « comprendre les choses ». Si vous creusez plus profondément, si vous parvenez à aller au fond des choses, nous pourrions dire que vous avez réussi à voir « la Matrice derrière la Matrice derrière la compréhension de toutes les choses », et il est possible que ce processus de fondation puisse se poursuivre à l’infini, ajoutant une nouvelle couche de profondeur de connaissance à chaque étape fondamentale.