Construction de la logique propositionnelle dans le λ-calcul

mercredi 27 mai 2015
par  Alain BUSSER

Dans le λ-calcul, les propositions sont représentées par des fonctions (puisque dans le λ-calcul, tout est fonction) et les opérations booléennes sont donc représentées par des fonctionnelles (fonctions de fonctions). Plutôt abstrait comme représentation, mais ça marche ! Le jeu des alligators permet de mieux voir ce qui se passe. Voici les carnets de voyage d’un explorateur ayant survécu à ces aventures au pays des alligators.

HTML - 10.3 ko
version Coffeescript
le fichier html, à ouvrir dans un autre onglet

Le λ-calcul est issu de la logique

Le paradoxe de Richard et sa variante le paradoxe de Berry [1] sont liés au fait que

  • le vocabulaire des mathématiques est fini ;
  • donc les productions du langage des mathématiques sont en quantité dénombrable ;
  • a fortiori, il y a une quantité au plus dénombrable de réels qui peuvent être nommés ;
  • donc la plupart des réels sont innommables.

Or, l’ensemble des fonctions de R dans R a un cardinal nettement plus grand que celui de R donc ce qui est écrit ci-dessus est encore plus vrai pour les fonctions que pour les réels. Et encore plus pour les fonctionnelles [2] : L’immense majorité des fonctions sont innommables. Le λ-calcul est justement basé sur cette idée de manipuler des fonctions anonymes ; par exemple on débaptise la fonction « carré » en la notant λx. x² sans lui donner de nom.

Deux familles remarquables

Lorsque Dundee arriva dans le pays des alligators cannibales, il commença par vérifier son paquetage puis sans même se reposer, partit pour une exploration des environs. Sitôt qu’il se fût habitué aux moustiques, il découvrit le premier exemplaire d’une famille répandue dans la région :

Cette famille est constituée du patriarche, dans une couleur (ici le bleu correspondant au type a), lequel veille sur un juvénile d’une autre couleur que lui (ici, en rouge correspondant au type b) et, via ce juvénile, sur un œuf de même couleur que le patriarche. Dans le jeu, cette famille peut s’obtenir à partir de la console, en cliquant sur « true ». Le langage de script de ce jeu décrit alors la famille par λa.λb.a ou toute autre combinaison de lettres à la place de a et b (du moment que ce sont des lettres différentes. Dundee comprit vite le comportement de la famille true en présence de deux sources de nourriture, par exemple deux œufs de couleurs respectives c et d (expression (λa.λb.a) c d dans le langage de script du jeu) :

L’alligator bleu commence par manger le premier œuf (c) ce qui a deux effets immédiats :

  • il meurt d’indigestion et disparaît du tableau
  • l’œuf bleu qu’il protégeait subit une mutation et devient un œuf identique à celui qui a été ingéré.

Mais le juvénile, devenu nouveau patriarche, a maintenant accès à la source de nourriture qui reste, l’œuf de type d, et ingère celui-ci, avant de mourir à son tour d’indigestion :

Dans ce cas, il n’y a pas eu de mutation génétique parce que l’ancienne couleur de l’œuf n’est pas la même que la couleur de son protecteur. Plus généralement, lors du décès du patriarche par indigestion, l’œuf que celui-ci gardait indirectement éclot, et produit une famille identique à celle que le patriarche vient d’ingérer. Dundee comprit alors

  • qu’en réalité l’œuf ne changeait pas de couleur, mais subissait une éclosion qui révélait son nouveau contenu, qui est un œuf de la nouvelle couleur dans le cas présent
  • que face à deux sources de nourriture, une famille de type true laissait toujours une copie de la première après son orgie cannibalistique.

Plus loin, Dundee aperçut une autre famille d’alligators, dans laquelle l’œuf est de la même couleur que le juvénile : La famille false (notée λa.λb.b) :

Son comportement alimentaire n’est pas le même que celui de la famille true, à cause de la couleur de l’œuf que n’est pas la même. Mise en présence de deux œufs de type c et d,

au début il se passe la même chose qu’avec la famille true : L’alligator bleu mange l’œuf de type c et meurt d’indigestion :

Mais cette fois-ci, comme l’œuf du bas n’est pas de la même couleur que l’ex patriarche, il ne se passe rien à son niveau. Du moins pour l’instant parce qu’une fois que le nouveau patriarche voit son repas, et comme il est de la même couleur que l’œuf qu’il protégeait, celui-ci va, après le décès de son gardien par indigestion, devenir ce que son protecteur a ingéré juste avant indigestion :

Plus généralement, une famille de type false, placée devant deux repas, devient non plus le premier d’entre eux (comme la famille true), mais le second.

Comme Dundee a aperçu ces deux familles d’alligators le premier jour (ou jour 1), au bout de la zone d’exploration, il les a baptisés « les bouts les 1 », anglicisé en « booléens »...

retour en haut des onglets

Négation

Le second jour de son exploration, Dundee a découvert une famille d’alligators dans le lac de la négation les Né-gators :

Cette famille a un comportement intéressant lorsqu’elle mange un booléen. Par exemple, située près d’une famille true :

C’est le moment de (re)découvrir une autre règle du jeu : La règle de la couleur. Les alligators sont peut-être cannibales parce qu’il mangent des alligators (ou leurs œufs) mais pas ceux de la même couleur qu’eux. Alors les proies se comportent comme des caméléons qui changent de couleur quand ils ont peur. Ici les a deviennent des c et les b deviennent des d :

En fait λc.λd.c est autant une description du booléen vrai que λa.λb.a. Alors, l’alligator p dévore, des yeux puis pour de bon, toute la famille vrai qui est devant lui. Ce qui va évidemment le tuer d’indigestion et, comme il surmonte un œuf de la même couleur que lui, cet œuf va éclore et donner naissance à une nouvelle famille true :

Les alligators adultes ont de plus en plus faim, mais il n’y a plus rien à manger devant eux. Par contre le jeune patriarche qui chapeaute la sous-famille true voit devant lui deux œufs (le b et le a) et mange le premier d’entre eux :

Ses deux gardiens ne pouvant le protéger de l’indigestion, il disparaît à son tour, laissant son protégé l’alligator d devant un œuf appétissant, qu’il dévore à son tour, avant de disparaître. Comme il ne surplombe aucun œuf de sa propre couleur, tout finit à ce point :

Ainsi, Dundee note dans son carnet ce fait intéressant :

Lorsqu’une famille né-gator mange une famille true, il en résulte une famille false.

Mais l’histoire ne s’arrête pas là : Lorsque la même famille né-gator mange une famille false il en résulte une famille true selon les étapes suivantes (extraits du carnet d’esquisses de Dundee) :

Les deux familles côte à côte :

La même situation après renommage des éléments de la famille false (λa.λb.b devenu λc.λd.c) :

Puis après l’ingestion-indigestion par l’alligator p, de la famille false, et éclosion de l’œuf de la même couleur :

Après le repas-suicide de l’alligator c :

Puis celui de l’alligator d :

Effectivement le résultat final est une famille vrai. Ainsi, cette famille opère sur un booléen en le transformant en l’autre booléen, exactement comme le fait la négation en logique propositionnelle [3].

retour en haut des onglets

Conjonction

Dans la console du jeu, en cliquant sur « And » on voit λp.λq.p q p qui donne cette famille :

Elle est plus vorace que la famille né-gator, puisqu’elle mange deux booléens (l’un après l’autre). Par exemple, face à deux familles ( une true et une false, données par (λp.λq.p q p) (λa.λb.a) (λc.λd.d)) :

Comme d’habitude, l’alligator p est le premier à passer à table (et à disparaître). Les œufs qui portent sa couleur vont donc éclore en donnant naissance à deux familles true au complet :

L’alligator mauve va alors manger la famille false de droite, qui est la seule à sa portée. Il disparaît et l’œuf mauve éclot en donnant naissance à une nouvelle famille false :

On a alors une situation rare : Trois familles booléennes côte à côte (true, false, true). C’est la première qui va se régaler, d’abord en laissant son patriarche dévorer la famille false (ce qui fait naître une autre famille false placée sous sa protection) :

Puis en laissant le juvénile avaler la famille true restante :

Le résultat, stable, est une famille booléenne : Une famille false [4] λc.λd.d

Ainsi, la famille and avale deux booléens et produit un booléen : C’est une opération. Dundee a consigné dans son carnet les résultats possibles :

situation de départ résultat produit

C’est la version crocodilienne de la table de vérité de la conjonction, cette famille d’alligators implémente donc la conjonction booléenne...

Disjonctions

La famille or (ou inclusif) ressemble à la famille and (onglet précédent). Pas étonnant puisqu’il s’agit là aussi d’un opérateur booléen :

Elle va donc elle aussi manger deux familles booléennes, comme par exemple une famile true et une famile false (script (λp.λq.p p q) (λa.λb.a) (λc.λd.d) après avoir renommé les variables de la famille false en c et d) :

Mais cette fois-ci, après le repas crocodilo-cannibalistique, il reste cette famille :

Ce n’est pas une famille false comme en laissait l’opérateur and, mais une famille true reconnaissable à ce que l’œuf est de la même couleur que le patriarche et non celle du juvénile.

Après avoir passé quelques jours à se faire piquer par les moustiques étudier cette famille et ses mœurs alimentaires, Dundee a noté ceci dans son carnet :

situation de départ restes des repas

On reconnaît là, la table de vérité de la disjonction inclusive, qui est donc représentée par cette famille.

Une expression représentant la disjonction exclusive est

(λm.λn.  m  ( (λp.λa.λb.p b a) n) n))

Voici cette famille, telle que découverte par Dundee :

Et voici ce que Dundee a noté dans son carnet, sur cet opérateur :

situation avant repas restes

On reconnaît la table de vérité du ou exclusif.

retour en haut des onglets

implication

En définissant m⇒n comme ¬m∨n, on a la λ-expression suivante :

λm.λn ((λp.λq.p p q)( (λp.λa.λb.p b a) m) n)

La famille représentée est celle-ci [5] :

Dundee s’est beaucoup impliqué dans l’observation de cette famille, et voici ses carnets :

situation avant repas restes des repas

Avec l’interpréteur CoffeeScript ci-joint, on peut tester le script suivant :

affichage = (booleen) ->
    booleen "2+2=4", "2+2=5"
vrai = (a,b) -> a
faux = (a,b) -> b
leContraireDe = (booleen) ->
    (a,b) -> booleen b, a
laDisjonctionDe = (a,b) ->
    b b, a
implication = (a,b) ->
    laDisjonctionDe (leContraireDe a), b
alert affichage implication vrai, vrai
alert affichage implication vrai, faux
alert affichage implication faux, vrai
alert affichage implication faux, faux

En fait, toute opération logique peut se définir à partir des opérations de base suivantes :

  • la négation
  • la conjonction
  • la disjonction inclusive [6]

Mais à partir de la négation et l’implication aussi on peut définir les autres opérations logiques. Par exemple on peut définir la disjonction p∨q comme ¬p⇒q. On peut même définir la négation à partir de l’implication, ¬p étant un synonyme de p⇒⊥.

retour en haut des onglets

La version CoffeeScript (...)

La version CoffeeScript

Logique en λ-calcul

Une pincée de Curry

Pour Church, la fonctionnelle qui, à deux fonctions a et b, associe la première des deux, est vraie. La fonctionnelle qui, à deux fonctions a et b, associe la seconde, est fausse. On les note respectivement

  • λab.a
  • λab.b
Mais elles sont peut-être plus faciles à rédiger en CoffeeScript:

L'affichage montre la fonction vrai, compilée en JavaScript. En effet, il s'agit bien d'une fonction...

On a donc besoin d'un affichage plus performant. Pas besoin de Churcher trop loin, l'image du couple ("vrai","faux") par chacune des fonctions donne le résultat affiché. On construit une fonction affichage (qui n'est donc pas une λ-fonction puisqu'elle porte un nom) et il suffit de l'invoquer pour afficher un booléen de Church:

La curryfication consiste à écrire une fonctionnelle portant sur deux fonctions, en une fonctionnelle de fonctionnelle:

Du coup les notations deviennent, dans l'ordre

  • λa.λb.a
  • λa.λb.b

Négation

La seule fonction booléenne portant sur une seule variable (à part l'identité) est la négation, définie pour une proposition p par λpab.p b a ou λp.λab.p b a ou λp.λa.λb.p b a. C'est la deuxième version qu'on va adopter ici:

En fait puisqu'une proposition est une fonction des deux variables "vrai" et "faux", sa négation est une fonction des deux mêmes variables mais en inversant leurs positions. Géométriquement, la fonction "vrai" est l'abscisse (première coordonnée d'un point du plan) et la fonction "faux" est l'ordonnée (seconde coordonnée). La négation ayant pour effet d'échanger l'abscisse et l'ordonnée, est la symétrie axiale par rapport à la droite d'équation y=x. Et le tiers exclu correspond au fait que le plan est de dimension 2.

Test

Un booléen étant construit comme une fonction qui choisit entre deux élements, la variante de la négation consistant à ne pas inverser les deux entrées du booléen fait un test. C'est donc la base de la construction d'algorithmes en λ-calcul. Alors que la négation était λp.λa.λb.p b a, le test est λp.λa.λb.p a b. Mais ce n'est pas une opération sur les propositions, on va donc le décurryfier en λpab.p a b plutôt qu'en λp.λab.p a b:

On peut donc choisir entre les deux fonctions cos et sin selon la valeur de vérité de la proposition. Comme dans le λ-calcul, tout est fonction, on peut choisir entre deux fonctions quelconques, et donc, entre deux objets quelconques du λ-calcul.

Opérations logiques

Conjonction

La conjonction, comme toute opération logique (binaire), est une fonctionnelle portant sur deux booléens a et b. On constate que

  • Si b est faux, alors a∧b l'est aussi (une antilogie est élément absorbant pour la conjonction);
  • si b est vrai, alors a∧b a la même valeur de vérité que a (une tautologie est élément neutre pour la conjonction).
Autrement dit, a∧b a la valeur de vérité de a si b est vrai et celle de b s'il est faux. On obtient donc cette valeur de vérité en appliquant le booléen b à a et b: λab.b a b qu'on peut curryfier en λa.λb.b a b. Mais ici on utilise la version curryfiée:

Disjonction inclusive

Pour la disjonction, ce sont les tautologies qui sont absorbantes (a∨b est vrai dès que b est vrai) et les antilogies qui sont neutres (a∨b a la même valeur de vérité que a si b est vrai). Donc

  • Si b est vrai, a∨b a la valeur de vérité de b (soit, le vrai);
  • si b est faux, a∨b a la valeur de vérité de a
Alors la disjonction inclusive s'écrit en λ-calcul λab.b b a:

La curryfication de cette disjonction donne λa.λb.b a b.

Disjonction exclusive

Remarque: Une opération logique étant définie par trois choix de a ou b comme ci-dessus, il y a 23=8 opérations possibles:

λ-expressionOpération
λab.a a apremier terme (a)
λab.a a bOu inclusif
λab.a b aEt
λab.a b bSecond terme (b)
λab.b a aPremier terme
λab.b a bEt
λab.b b aOu inclusif
λab.b b bSecond terme

On constate que cela ne permet pas de définir l'opérateur de Sheffer ni l'implication ni même le "ou exclusif". Mais en rajoutant une négation, on peut définir ce dernier:

Cette expression s'écrit, sans curryfication, λab. a leContraireDe(b) b ou λab. a (b (λc.λd d c) (λc.λd c d)) b

Logique trivalente

Le tiers inclus

Avec la comparaison géométrique ci-dessus, la logique ternaire de Łukasiewicz revient à rajouter une troisième dimension, et la symétrie représentant la négation se fait maintenant par rapport au plan d'équation x=z:

Logique ternaire

Les recherches du début du vingtième siècle, et en particulier la logique intuitionniste et les théorèmes d’incomplétude de Gödel ont amené Łukasiewicz, dès le début des années 1920, à douter du tiers exclu : Il se peut qu’une proposition ne soit ni vraie ni fausse puisque sa valeur de vérité est inaccessible : Pour répondre à Aristote :

Nécessairement il y aura demain une bataille navale ou il n’y en aura pas ; mais il n’est pas nécessaire qu’il y ait demain une bataille navale, pas plus qu’il n’est nécessaire qu’il n’y en ait pas. Mais qu’il y ait ou qu’il n’y ait pas demain une bataille navale, voilà qui est nécessaire.

Łukasiewicz, suivant Brouwer, estime au contraire que cette alternative n’est pas nécessaire, et étudie une logique trivalente dans laquelle une valeur de vérité intermédiaire entre le vrai et le faux correspond à « indéfini » [7]. L’adaptation du codage des booléens à la Church est facile, il suffit de créer des familles à trois niveaux au lieu de 2. Cela donne les trois valeurs de vérité possibles :

vrai indécidable faux

Alors la négation devient ceci :

Et voici sa table de vérité, telle que notée par Dundee :

situation avant le massacre survivants

On voit que, alors que le contraire d’une proposition vraie est faux, et le contraire d’une proposition fausse est vraie, le contraire d’une proposition indécidable est, lui, indécidable...

Par contre, les opérations de conjonction et disjonction de la logique ternaire sont beaucoup plus complexes. En effet, il n’y a pas dans les tables de vérité ternaires, que des colonnes aussi simples que des constantes ou l’identité, ce qui oblige à des tests. Et les tests de la logique ternaire sont à trois entrées !

Par exemple voici la définition fonctionnelle de la conjonction ternaire (à tester dans un des interpréteurs CoffeeScript ci-dessus) :

affichage = (booleen) ->
    booleen "2+2=4", "chépô", "2+2=5"
vrai = (a,b,c) -> a
fou = (a,b,c) -> b
faux = (a,b,c) -> c
laConjonctionDe = (b1,b2) ->
    switch b1
        when vrai then b2
        when fou
            if b2 is faux then b2 else b1
        when faux then b1
alert (affichage laConjonctionDe vrai, x for x in [vrai,fou,faux])
alert (affichage laConjonctionDe fou, x for x in [vrai,fou,faux])
alert (affichage laConjonctionDe faux, x for x in [vrai,fou,faux])

Et la disjonction :

affichage = (booleen) ->
    booleen "2+2=4", "chépô", "2+2=5"
vrai = (a,b,c) -> a
fou = (a,b,c) -> b
faux = (a,b,c) -> c
laDisjonctionDe = (b1,b2) ->
    switch b1
        when vrai then b1
        when fou
            if b2 is vrai then b2 else b1
        when faux then b2
alert (affichage laDisjonctionDe vrai, x for x in [vrai,fou,faux])
alert (affichage laDisjonctionDe fou, x for x in [vrai,fou,faux])
alert (affichage laDisjonctionDe faux, x for x in [vrai,fou,faux])

[1celui-là par contre est lié à la supposition selon laquelle tout ensemble récursivement énumérable a un plus petit élément ; il est donc également lié à l’arithmétique

[2fonctions de fonctions, comme par exemple la dérivation, qui à une fonction f associe sa dérivée f’

[3Par contre, le modèle présenté dans la version CoffeeScript, présentant la négation comme symétrie axiale, laisse penser que la négation de la négation est l’identité. Ce n’est pas le cas dans le λ-calcul puisque « not not », une fois réduit, devient λa.(λb.(λc.(b c a))) qui n’est pas l’identité : Le λ-calcul est de la logique intuitionniste.

[4En fait il s’agit d’un cas particulier de ce qu’on a vu dans le premier onglet, sur le comportement de la famille true : Elle choisit le premier repas qui s’offre à elle.

[5En fait, on peut la laisser évoluer toute seule pour aboutir à une version simplifiée λm.(λn.( m n λd.(λe.(m e d)))) ; c’est d’ailleurs cette version qui est utilisée dans l’article sur le paradoxe de Curry.

[6celle-ci pouvant d’ailleurs se définir à partir des deux autres, avec les lois de De Morgan.

[7La sortie à trois états de l’électronique numérique permet de matérialiser cette notion.


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

Décès de Raymond Smullyan

mercredi 15 mars

Le logicien Raymon Smullyan est décédé en février 2017, à l’âge respectable de 97 ans : Il avait eu Alonzo Church comme professeur ! Pour en savoir plus, voir cet article

Travailler à plusieurs

lundi 19 décembre 2016

Les enseignements d’exploration au lycée imposent aux enseignants de travailler ensemble. Chantal Tuffery-Rochdi a analysé dans sa thèse les pratiques des enseignants de MPS (méthodes et pratiques scientifiques). Elle répond aux questions des Cahiers pédagogiques.

Un document sur Eduscol

mardi 19 mai 2015

Un document clarifiant bien la façon dont les mêmes concepts vivent en mathématiques et dans les sciences « exactes » les utilisant, publié par Eduscol en octobre 2014. Citons-les :
« Le document proposé ci-dessous s’adresse aux professeurs de mathématiques, physique-chimie et sciences de l’ingénieur intervenant dans le segment [Bac-3 ; Bac+3]. Il vise à les informer des différences de présentation et d’interprétation qui sont faites de certains concepts mathématiques dans les autres disciplines. Ces éclaircissements peuvent contribuer à harmoniser et à clarifier l’utilisation de ces notions auprès des élèves. »

Histoire de la comptabilité

vendredi 28 décembre 2012

Sur ce site (en anglais) dédié à la comptabilité, on trouve des informations intéressantes sur l’histoire et les pratiques de ce domaine, qui peuvent être utiles aux professeurs enseignant des mathématiques financières (et aussi aux autres...).

La CGE et la réforme des lycées

lundi 16 janvier 2012

La Conférence des Grandes Écoles publie 19 préconisations pour la réforme du lycée.

Sur le Web : Les 19 préconisations

Pratique des mathématiques en série STD2A

lundi 16 janvier 2012

Le site de l’IGEN offre des recommandations et des ressources pour enseigner les mathématiques en série STD2A. Les thèmes abordés (couleurs et nuances de gris, arcs et architecture, jeux vidéos, photo et tableur, perspectives parallèles...) sont de nature à donner aussi des idées d’activités aux enseignants des autres séries !

En cheminant avec Kakeya

lundi 16 janvier 2012

Un livre (à télécharger) de Vincent Borelli et Jean-Luc Rullière qui présente le calcul intégral et la dérivation en s’appuyant sur la question de Kakeya. Pour les lycéens, les étudiants et tous les esprits curieux qui souhaitent voir les mathématiques sous un jour différent.

Sur le Web : Livre à télécharger

Bicentenaire Galois

lundi 12 septembre 2011

À l’occasion du bicentenaire de la naissance d’Évariste Galois (1811-2011), l’Institut Henri Poincaré et la Société mathématique de France organisent un ensemble de manifestations et proposent un site contenant diverses ressources documentaires susceptibles d’intéresser les enseignants.

Statistiques

Dernière mise à jour

mercredi 9 août 2017

Publication

760 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

198 aujourd'hui
510 hier
2075114 depuis le début
12 visiteurs actuellement connectés