Vulgarisation

Comme nos quatre amis juristes ont l'air de ne pas trouver de sujet de vulgarisation, je leur soumets celui-ci : le droit spatial.

Ils n'ont vraiment pas l'air motivés.

Je vais pour ma part présenter des articles en lien avec mon projet de mathématique actuel : la théorie de Galois, pour deux raisons : 1) c'est intéressant et abordable et 2) réfléchir à comment vous présenter ça m'aide à l'ancrer dans mon esprit.

Je vais parler de la résolution d'équations polynomiales. Ce problème est aussi vieux que la civilisation humaine et très présent, ne serait-ce à la base que pour des problèmes d'ordre commerciaux ou agricoles, et plus tard pour des objets plus complexes.
Commençons par la résolution des équations de degré 1 et 2.

Le degré 1 est presque évident, mais il me permet d'introduire les termes et une partie de la méthode.
L'équation est ax +b = 0. Le coefficient de plus haut degré (ici c'est a) est toujours non nul, sinon l'équation serait de degré inférieur (ici b = 0, en quelque sorte le degré zéro). x est appelé variable et c'est sa valeur que nous recherchons en fonction des coefficients.
On peut ramener l'équation à la forme x - c = 0 en divisant par a et en notant c = -b/a, puis nous obtenons x = c.
Donc l'équation n'admet qu'une solution : x = -b/a.
Les coefficients choisis sont des nombres réels, ce qui signifie qu'il y aura toujours moins ou autant de solutions réelles que le degré de l'équation. Ici l'équation est de degré 1, et il y a une solution.
En s'autorisant des solutions complexes, le nombre de solution est égal au degré de l'équation.
(Pour les connaisseurs, cela vient du fait que C est la clôture algébrique de R et donc que le polynôme de l'équation est scindé et admet donc autant de racines que le degré du polynôme.)
Ceci étant fait, passons au degré 2.

La plus vieille résolution d'équation quadratique (de degré 2) nous vient de la Mésopotamie, vers -1700.
Le problème est le suivant : soit s et p deux nombres donnés, trouvez x et y tels que s = x +y et p = xy.
Ils trouvent l'algorithme suivant :

Prendre la moitié de s.
Mettre le résultat au carré.
Retirer p.
Prendre la racine (oui, ils savaient faire, j'en ai parlé dans "Un peu de mathématiques" me semble-t-il).
Ajouter la moitié de s.
Cela donne un des nombres, l'autre s'obtient en retirant le premier de s.

Disons que x est le premier, nous avons :

x = racine((s/2)² -p), y = s -x.
En récrivant les résultats, nous avons la forme moderne :
x = 1/2(s +racine(s² -4p)), y = 1/2(s -racine(s² -4p))

Rappelons que la solution (prouvée en cours de lycée) de l'équation ax² +bx +c = 0 est 1/2(-b +ou-racine (b² -4ac)).
En identifiant les coefficients, nous obtenons que x et y sont solutions de l'équation x² -sx +p = 0.

Cela n'a rien d'étonnant, en effet :
s = x +y implique sx = x² +xy = x² +p, d'où x² -sx +p = 0.

Ainsi, le problème mésopotamien est équivalent à trouver les solutions d'une équation du second degré.



Note : preuve de la formule de lycée.
Par équivalence :
ax² +bx +c = 0
x² +(b/a)x +(c/a) = 0
(x +(b/2a))² -b²/4a² +c/a = 0
(x +(b/2a))² - (b² -4ac)/4a² = 0 (1)
Si b² -4ac est négatif, alors (x +(b/2a))² = (b² -4ac)/4a² négatif, ce qui est absurde pour un carré, et il n'y a pas de solution réelle.
Dans les complexes, nous écririons b² -4ac = (-1)*-(b² -4ac) et la racine complexe est i*racine( -(b² -4ac) ).
Dans le cas où b² -4ac est positif ou nul, ou que nous autorisons les racines complexes, continuons et notons D sa racine.
(1) est de la forme A² - B² = 0, donc nous pouvons utiliser une identité remarquable : (A +B)(A -B) = 0 :
(x +(b/2a) +D/2a)(x +(b/2a) -D/2a) = 0
qui est de la forme (x -A)(x -B) = 0 donc nous avons que x = A ou B, et l'équation étant de degré 2 il n'y a que deux solutions à attendre. Ces solutions sont donc :
- ( (b/2a) +D/2a ) = (-b -D)/2a
- ( (b/2a) -D/2a ) = (-b +D)/2a
Et on peut écrire que x = (-b +ou-D)/2a où D = racine(b² -4ac).

L'algorithme mésopotamien est très vieux, mais il a fallu attendre l'introduction des nombres négatifs au moyen âge, puis l'introduction des nombres imaginaires à la renaissance pour pouvoir résoudre tous les cas possibles du degré 2.


J'espère que ça vous aura plu.

Les arabes découvrirent quelques solutions géométriques des degrés 3, mais c'est la méthode systématique occidentale qui permit d'aller plus loin.

Une fois que les mathématiciens utilisèrent les nombres imaginaires, ils purent trouver toutes sortes d'astuce pour résoudre les degrés 3 et 4 assez rapidement. Voici ce qu'ils savaient faire vers cette époque (1500 pour le degré 3 et un peu après pour le degré 4), exprimé en langage moderne :


D'abord le degré 3 :

Une équation de degré 3 est de la forme ax^3 +bx² +cx +d = 0 où a différent de 0.
Ramenons l'équation à la forme canonique x^3 +px +q = 0.

ax^3 +bx² +cx +d = 0
=> x^3 +(b/a)x² +(c/a)x +(d/a) = 0
=> (x +b/3a)^3 -(b²/3a²)x -b^3/27a^3 +(c/a)x +(d/a) = 0
=> (x +b/3a)^3 +((3ac-b²)/3a²)x +(27a²d-b^3)/27a^3 = 0
=> (x +b/3a)^3 +((3ac-b²)/3a²)(x +b/3a) +(27a²d-b^3)/27a^3 -(b/3a)(3ac-b²)/3a²) = 0
En posant p = (3ac-b²)/3a² et q = (27a²d-b^3)/27a^3 -(b/3a)(3ac-b²)/3a²) nous avons :
(x +b/3a)^3 +p(x +b/3a) +q = 0
Et en faisant le changement de variable y = x +b/3a :
y^3 +py +q = 0

Ainsi, toute équation de degré 3 peut se ramener à cette forme plus simple x^3 +px +q = 0, que nous allons résoudre.
L'astuce consiste à introduire deux nouvelles variables a et b telles que x = a -b et 3ab = p, ce qui est possible si p est différent de 0, mais le cas p=0 est facile car alors nous avons x^3 = -q et il suffit de prendre la racine cubique.
Nous supposons donc p=0 et alors :
x^3 +px +q = 0
=> (a -b)^3 +p(a -b) +q = 0
=> a^3 -3a²b +3ab² -b^3 +p(a -b) +q = 0
=> a^3 -b^3 -3ab(a -b) +p(a -b) +q = 0
=> a^3 -b^3 +(-3ab +p)(a -b) +q = 0 (d'où le choix de l'équation 3ab = p)
=> a^3 -b^3 +q = 0
=> 27a^6 -(3ab)^3 +27qa^3 = 0
=> 27(a^3)² +27q(a^3) -p^3 = 0
qui est une équation de degré 2 où la variable est a^3, donc nous trouvons a^3 et donc a.
Nous déduisons b avec 3ab = p, soit b = p/3a.
Avec a et b nous déduisons x = a -b.

Ouf ^^


Passons au degré 4 :

Nous avons utilisé le degré 2 pour trouver le degré 3, et de même nous allons utiliser les degrés 2 et 3 pour trouver le degré 4, que je ne vais présenter que brièvement.
Une équation de degré 4 de la forme ax^4 +b^3 +cx² +dx +e = 0 peut se mettre (en factorisant et en faisant un changement de variable comme pour le degré 2) en une forme plus canonique : x^4 +px² +qx +r = 0, soit x^4 = -px² -qx -r. En prenant une nouvelle variable a, nous avons :
(x² +a)² = x^4 +2ax² +a² = -px² -qx -r +2ax² +a² = (2a -p)x² -qx +(a² -r) qui est un polynôme du second degré en x.
Nous voulons mettre le membre de droite sous forme A(x +B)², ce qui signifie que x est racine double de l'équation (2a -p)x² -qx +(a² -r), donc le déterminant du polynôme doit être nul, soit :
(q² -4(2a -p)(a² -r))/2(2a -p) = 0, d'où il faut que q² -4(2a -p)(a² -r) = 0, ce qui est une équation de degré 3 en a, que nous pouvons résoudre.
Donc en prenant comme étant une racine de cette dernière équation, nous pouvons écrire (x² +a)² = A(x +B)², où A est le coefficient de x², soit (2a -p), et B est le coefficient de x divisé divisé par 2A, soit -q/2A. D'où :
(x² +a)² = (2a -p)(x -q/2(2a -p))² (remarquons que 2a -p est nécessairement positif)
=> x²+a = (+ou-)racine(2a -p)*(x -q/2(2a -p)) qui est une équation de degré 2, que nous pouvons résoudre.
Ce qui nous donne bien x.


A ce stade, on s'attendrait à pouvoir résoudre le degré 5 en utilisant les degrés précédents, quitte à introduire des variables, faire des changements de variables, extraire des racines et tout le bataclan, ce qui serait vraisemblablement immonde, mais qui semble a priori faisable (et donc de nos jours on se dépêcherait... de le faire calculer par un ordi, non mais !), et c'est naturellement ce qu'espéraient les mathématiciens du XVIème siècle.
Et bien en fait il fallut attendre près de trois siècles pour que des mathématiciens comme Abel et Galois démontrent qu'il est impossible de résoudre les équations de degré 5 par cette méthode, c'est à dire en n'usant que des opérations élémentaires et des racines, ce qui fut le résultat de découvertes plus fondamentales en algèbre.

Mon projet, portant sur la théorie de Galois, montrera pourquoi résoudre les équations de degré 5 de cette façon est impossible.
Affaire à suivre, donc ^^

Pas de remarque ? Trop technique ?


Bon, passons à autre chose... la mathématique des origamis. ^^
(article tiré en partie de Wikipedia)
En occident nous sommes partis de la construction à la règle et au compas pour définir nombres et objets géométriques, mais il y a d'autres façons de faire. Ici je vais partir d'une construction basée sur les origamis et développer un peu autour de ça.


Petit rappel historique :

Les Grecs (notamment Euclide dans ses Eléments) formalisèrent la notion de démonstration mathématique et furent les premiers (à notre connaissance) à proposer une construction systématique basée sur des axiomes et la preuve formelle de théorèmes pour les appliquer à des études algébriques et géométriques.
Au départ, l'école pythagoricienne pensait que toutes les mesures pouvaient se ramener à des nombres rationnels, (positifs, les nombres négatifs n'ayant été introduits qu'au moyen âge), c'est à dire les fractions, mais durent se rendre à l'évidence que ce n'était pas possible, par exemple racine de 2 n'est pas un nombre rationnel. Ils s'autorisèrent donc les racines mais cela n'était pas suffisant. Ainsi trois problèmes leur résistèrent : la quadrature du cercle, la trisection de l'angle et la duplication du cube, qui ne furent résolus que plus tard.
La quadrature du cercle revenait en fait à se demander le statut du nombre pi, qui est un réel transcendant, c'est à dire qu'il n'est racine d'aucune équation polynomiale.
La duplication du cube revenait en fait à se demander le statut du nombre racine cubique de 2, qui n'est ni un rationnel ni même combinaison de racine carrée et de rationnels. Néanmoins, il n'est pas transcendant (on dit qu'il est algébrique) car il est racine de l'équation x² -2 = 0. De même, résoudre la trisection de l'angle revient à trouver des racines cubiques.


Avant de passer à la suite, j'aimerai introduire des notions qui ne sont pas indispensables ici mais que j'utiliserai très souvent : les groupes, les anneaux et les corps. Il est possible de passer ce paragraphe, mais il y aura des remarques qui n'auront alors pas de sens.

Un groupe c'est un ensemble G muni d'un loi notée + qui :
- est interne : si a et b sont dans G alors a+b est dans G.
- est associative : a+(b+c) = (a+b)+c
- admet un élément neutre noté 0 : a+0 = 0+a = a
- est inversible (l'inverse de a est noté -a) : a+(-a) = (-a)+a = 0
De plus, si + est commutative (a+b = b+a), G est dit commutatif.

Un anneau est un ensemble A muni de deux lois notées + et * telles que :
- A est un groupe commutatif pour +
- * est interne, associative, admet un élément neutre noté 1 et distributive par rapport à + ( a(b+c) = ab+ac ).
Si * est commutative, A est dit commutatif.
Par exemple, Z l'ensemble des entiers (positifs et négatifs) est un anneau commutatif.

Un corps est un ensemble K muni de deux lois notées + et * telles que K est un anneau commutatif et * est inversible.
Par exemple Q l'ensemble des fractions est un corps. C'est le plus petit corps de nombre.

Par la suite je parlerai notamment de "plus petit corps stable pour une fonction f", cela signifie que l'ensemble considéré sera un corps, que si a est un élément de ce corps alors f(a) est également un élément de ce corps, et de plus ce corps est inclus dans tous les corps stables pour cette fonction.

Je précise également pour la suite que construire un segment ou deux points c'est construire un nombre, en prenant la longueur séparant les deux points.


Passons maintenant au vif du sujet !

Nous partons par défaut de deux points de base, séparés par une longueur 1 (quitte à définir le nombre 1 comme la longueur les séparant ^^) et nous nous nous donnons des axiomes autorisant des plis, de façon à pouvoir utiliser ces plis pour construire de nouveaux points (et donc de nouvelles longueurs, de nouveaux nombres) à partir des deux points de base.
Axiome 1. Un unique pli passe par deux point p1 et p2 specifiés.
Axiome 2. Un unique pli amène un point p1 sur un point p2.
Axiome 3. Un pli superpose deux droites l1 et l2.
Axiome 4. Un unique pli passe par un point p1 et est orthogonal à une droite l1.
Axiome 5. Soient une droite l1 et deux points p1 et p2 ; un pli passe par p2 et amène p1 sur l1.
Axiome 6. Soient deux droites l1 et l2 et deux points p1 et p2 ; un pli amène p1 sur l1 et p2 sur l2.
(les dessins : http://fr.wikipedia.org/wiki/Math%C3%A9matiques_des_origamis#Formalisation_des_origamis )

Géométriquement parlant, on peut interpréter les quatre premiers axiomes de la façon suivante :
Axiome 1. une droite passant par deux points constructibles est constructible.
Axiome 2. la médiatrice d'un segment dont les extrémités sont constructibles est constructible.
Axiome 3. la bissectrice de deux droites constructibles est constructible.
Axiome 4. la perpendiculaire passant un point constructible à une droite constructible est constructible.
Les nombres constructibles avec ces plis sont les nombres constructibles à la règle et au compas à pointe sèche, le compas à pointe sèche permettant de reporter les longueurs sur des droites, mais pas de tracer des arcs de cercle.
Algébriquement, c'est le plus petit corps contenant les rationnels stable par la fonction racine(1+x²), ce qui signifie par exemple qu'il est possible de construire la racine de la somme de deux carrés mais pas de leur différence. Par exemple il est possible de construire un triangle rectangle connaissant la longueurs des côtés adjacents à l'angle droit, mais pas connaissant un côté et l'hypoténuse.
Par exemple, racine de 2 est constructible à la règle et au compas à pointe sèche.
Au passage, ces nombres sont aussi les nombres constructibles à la règle et à l'empan, où l'empan ne permet que de reporter des longueurs entières, car avec la règle et l'empan on peut de mener une parallèle à une droite passant par un point, et donc reporter une longueur quelconque.

L'axiome 5 est équivalent à chercher l'intersection d'une droite et d'un cercle.
Les nombres constructibles avec ces plis sont les nombres constructibles à la règle et au compas, les nombres que connaissaient les Grecs. Il y a d'ailleurs un théorème (de Mohr-Mascheroni) énonçant que si un nombre est constructible à la règle et au compas alors il est constructible au compas seul. Ce n'est pas possible avec la règle, par exemple il est impossible avec la règle seule de construire le milieu d'un segment ou de mener par un point une parallèle à une droite. Néanmoins, en se donnant un cercle et son centre (ou deux cercles sécants, ou trois cercles), il est possible avec la règle seule de construire tout point constructible à la règle et au compas (Théorème de Poncelet-Steiner).
Algébriquement, il s'agit du plus petit corps contenant les rationnels stable par racine carrée. On les obtient avec les fractions, les quatre opérations élémentaires et la racine carrée. Ce corps permet de résoudre les équations de degré 2 (vous vous doutiez qu'il devait y avoir un rapport avec l'article précédent quand même...).

L'axiome 6 offre des procédés de construction particulièrement puissants. Il revient à construire la tangente aux deux paraboles de foyers p1 et p2 et de directrices respectives l1 et l2.
Algébriquement, il s'agit du plus petit corps contenant les rationnels stable par racines carrée et cubique. On peut par exemple y construire la racine cubique de 2, et donc dupliquer un cube. De même, on peut trissecter un angle. Pi étant transcendant, la quadrature du cercle résiste toujours, mais au moins deux problèmes de l'antiquité sur les trois sont tombés. On peut même y construire l'heptagone régulier, ce qui est impossible à la règle et au compas seuls.


Je mentionne en passant qu'n peut également faire des pliages fractals avec les origamis, notamment pour faire apparaître le nombre d'or, et qu'il y a également une méthode de construction censée être un peu plus puissante : la construction à la règle graduée et au compas, mais que je ne développerai pas ces points ici, l'article étant déjà assez long.
Un dernier mot néanmoins pour mentionner un article intéressant sur les origamis, plein de jolies images : http://web-japan.org/nipponia/nipponia41/fr/feature/feature09.html

Mathématiquement votre !

Bon j'avais dit que je ferais un article concernant le rapprochement entre le cancer et les individus égoïstes d'une société, alors le voila. Je vais commencer par des explications sur le cancer, puis je mettrais cela en parallèle avec les égoïstes.

Un cancer, c'est une prolifération clonale et anarchique de cellules au sein d'un organisme. Il faut imaginer que chaque organe d'un organisme se compose comme un écosystème semi-fermé (à cause de la circulation sanguine) où le nombre de différent types de cellules sont en équilibre. Les cellules se multiplient peu, juste ce qu'il faut pour compenser les décès naturel des cellules (sauf exception comme le cerveau et le muscle). Ce faible niveau de multiplication cellulaire fait intervenir une foultitude de facteur (molécules de communication) de régulation : des facteurs de croissance, des facteurs d'inhibitions, des facteurs d'apoptose (mort cellulaire programmé); mais aussi l'inhibition de contacte. L'inhibition de contacte est la capacité des cellules à stopper leur croissance lorsqu'elles sont en contacte avec de nombreuses cellules voisines, comme c'est le cas dans les tissus.

Les cellules cancéreuses sont des cellules qui ne sont plus régis par ces systèmes de régulation, elles ont subit des mutations qui leurs donnent des avantage en terme de reproduction sur les autre cellules. La formation d'un cancer s'étale généralement sur plusieurs années, voir plusieurs décennies. En effet une seul mutation ne suffit pas à créer un cancer, il faut en accumuler plusieurs pour que l'avantage réplicatif de la cellule puisse dépasser les mécanismes de protection de l'organisme, et il faut également que les cellules cancéreuses acquièrent la capacité (toujours par mutation) de quitter leur organe d'origine et d'émigrer ailleurs dans l'organisme.

Une fois que la cellule cancéreuse a acquis toutes ces caractéristiques, elle va se développer très rapidement et s'installer dans différents tissus de l'organisme (métastase), tout en résistant au système immunitaire. Les cellules cancéreuses se reproduisant plus vite que les cellules saines, elles vont bouleverser l'écosystème des organes dans lesquels elles se trouvent en prenant la place des cellules saines, ce qui induit une perte de fonctionnalité de l'organe touché. Le cellule cancéreuses vont également détourner les ressources de l'organisme à leur profil en détournant le système sanguin de manière à ce qu'il vienne abondamment irriguer les tumeurs.

J'en viens maintenant à l'égoïsme, même si vous devez à présent commencer à voir où je veux en venir .

Dans un organisme sain, chaque cellule travail pour la collectivité, parfois au détriment d'eux-même (le communisme avant l'heure!), cela dans le but de maintenir le corps en vie. Dans un cancer, certaines cellules vont arrêter de travailler pour la collectivité pour produire un résultat commun et vont développer des tactiques pour obtenir une ascendance sur les autres cellules. Les cellules égoïstes vont ainsi acquérir un avantage sur les autres cellules : elles seront plus forte et plus nombreuses (pas par rapport au corps, mais par rapport aux cellules saine du type dont elles sont issus). L'égoïsme a donc porté ses fruits dans un premier temps puisqu'il a avantagé ses "disciples". Mais cet avantage se crée au détriment du support de vie des cellules, ce qui a pour conséquence d'aboutir à la mort du corps, et donc à la mort de toute les cellules de l'organisme, y compris les cellules cancéreuses. Donc même si elles ont acquis un avantage à court terme, les cellules égoïstes sont morte plus tôt que si elles avaient continué à faire leur travail.

Je trouve que cela ressemble fortement aux comportement des individus égoïstes au sein d'une société (à ceci près qu'a l'échelle des individus, la conscience joue aussi), à savoir que les égoïstes vont acquérir une ascendance sur les autres mais en mettant en péril le support vital du tous.

Qu'en pensez-vous?

Deux choses.
Dans le corps l'intérêt "personnel" n'a pas à exister car l'existence d'une cellule en tant que telle n'a pas vraiment de sens, contrairement à l'existence de l'individu. Aussi, il ne faudrait pas tomber dans l'excès inverse : je trouve intéressant de condamner l'égoïsme, mais pas l'individualisme.
Ensuite, vu la mort programmée des cellules et le temps que met une cellule cancéreuse à mourir, il n'est pas évident qu'elle vive moins longtemps qu'en faisant son travail, de même que dans la société où pourrir l'existence des génération n'a pas d'importance pour celui qui pense que le monde n'est intéressant que dans la mesure il y vit.

Le corps fonctionne en mode "total communiste" dans la mesure où les cellules n'ont pas de conscience. Effectivement il ne peux pas servir de modèle d'étude exacte pour notre société mais je trouve intéressant la manière dont il montre les effets d'un groupe grattant la base de vie pour gagner un avantage sur les autres. Cela dit je ne condamne pas l'individualiste pour autant.

Ensuite les cellules cancéreuses sont immortelles dans le sens où sans agression extérieur elle continuerons à vivre éternellement. Et comme elles ont tendance à berner le système immunitaire, les cellules cancéreuses vivent plus longtemps que les cellules saines dont elles sont issus (sauf cas rare de cellules qui sont censé vivre aussi longtemps que l'individu comme les cellules cardiaques ou les neurones, mais ces cellules ne provoquent presque jamais de cancer). Quand je dit que les cellules égoïstes meurent plus tôt que si elles avaient continuer à faire leur travail, je parle de la ligné des cellules, pas des cellules individuellement.

En somme, les cellules auraient "intérêt" à être cancéreuse car elles prolongeraient leur espérance de vie... quitte à tuer le corps.

Intro à la logique intuitionniste

Donc, comme l'indique le titre, je vais vous faire une brève intro à la logique intuitionniste, et vous présenter ma vision.


Déjà une brève intro pour vous donner une vision globale de la chose:

La logique que vous employez tout les jours en sciences, en maths, dans la vie courante, s'appelle la logique classique. Cette logique s'attache plus à ce qui est vrai ou faux. A contraire, la logique intuitionniste s'attache à ce qui est prouvable constructivement, c'est à dire toutes les preuves dont les objets sont construits à partir des données de l'énoncé. En pratique, la seule différence avec la logique classique est que l'on a pas le raisonnement par l'absurde (si on suppose (non A), (blablabla) contradiction! C'est donc qu'en fait on a A), qui est équivalent à avoir pour toute proposition A, (A ou (non A))... Sinon, pour le reste, si on arrive à prouver quelque chose avec la logique intuitionniste, la même démonstration marche aussi en logique classique.

"Oui, mais dans ce cas, pourquoi s'embêter à étudier une nouvelle logique, surtout si on arrive à prouver moins de théorèmes et qu'on est plus limité?".
En fait, le principal intérêt de la logique intuitionniste est que toutes ses preuves sont constructives. Du coup, dans la démonstration mathématique, on décrit comment traiter les hypothèses, les combiner entre elles au moyen de théorèmes pour ensuite obtenir un objet avec les propriétés voulues. Donc, on donne en fait une sorte d'algorithme d'agencement des hypothèses pour tomber sur l'objet qui nous intéresse. On a donc une équivalence entre preuves constructives et algorithmes, et cette équivalence s'appelle l'"isomorphisme de Curry-Howard".

Un petit exemple: si on veut prouver que A & (A -> B) -> B (lire: "Le fait que l'on a A et (A -> B) implique que l'on a B aussi" "Si on a A et que l'on sait que (A->B), alors on a B"). Pour prouver ça, on récupère les hypothèses: A et (A -> B), et on veut prouver B. Là, l'exemple est trivial: on donne l'hypothèse A à la proposition (A -> B) et (comme par hasard) on a prouvé B!
Bref: on a construit B à partir de A et de (A->B) et la preuve est équivalente à l'algorithme: "appliquer A à (A->B) et rendre le résultat".
(je peux aussi faire une version avec des carotes et des lapins, mais le B risque d'être ... )

Une autre vision de la chose: on peut lire "A & (A -> B) -> B" comme "si on a une preuve de A, et une preuve de (A->B), alors on a une preuve de B", l'algorithme correspondant étant "On prend la preuve de A, on y ajoute la preuve de (A->B), on applique A à (A->B) et on obtient une preuve de B".

Du coup, on peut extraire de manière automatique des programmes pour chaque preuve mathématiques que l'on prouve constructivement. Donc, en fait, faire des maths (constructive) ou programmer, ça revient au final à la même chose... 0:-D

Bon, fin de l'intro, on passe au choses sérieuses... (ie, avant que vous fuyez, la même chose, mais avec le formalisme en plus )

-------------------------------------------------------------------------------------------------
Déjà quelques précisions avec le vocabulaire:
Au niveau des propositions:
* A /\ B veut dire "A et B"
* A \/ B veut dire "A ou B"
* ¬A veut dire "non A" (Alt-gr + N pour ceux qui sont sous Linux, au moins)
* A -> B veut dire "A implique B"
* T veut dire vrai
* F veut dire faux (le symbole usuel est un T retourné pour que sa barre horizontale soit en bas, appelé aussi "bottom")
Je précise qu'en fait, ¬A est un raccourci d'écriture pour (A -> F) (mais, comme on ne peut pas prouver faux, heureusement pour nous, on ne peut pas prouver A, donc on a "non A"). Je laisse tomber les "il existe" (symbole: E retourné) et les "pour tout" (symbole: A retourné), qui ne sont pas essentiels dans un premier temps...
Une formule s'écrit donc: P ::= X | P1 /\ P2 | P1 \/ P2 | P1 -> P2 | ¬ P1 | T | F (se lit: "P est soit une vairable propositionnelle "X", soit "P1 et P2" avec P1 et P2 d'autres formules, soit "P1 ou P2" ...)

Donc, pour écrire des formules, c'est fait... Maintenant, il va falloir opter pour des conventions pour les preuves. Là, il existe plusieurs "systèmes de preuves" qui sont en fait des moyens de représenter une démonstration et de décrire comment elle se déroule... Il en existe plusieurs, plus ou moins pratiques, avec des propriétés plus ou moins intéressante... La plus connue s'appelle "calcul des séquents", est assez pratique et est jolie à utiliser (parce que tout plein de symétries), donc on est parti...

Un "séquent" s'écrit "A, B, C ... |- P" avec A, B, C, P des propositions (avec la syntaxe que je vous ai décris ci-dessus). Le |- se lit "prouve". Au niveau sémantique, comment ça marche? A gauche du |- , on met les hypothèses et à droite le but à prouver. Le séquent est considéré comme prouvé dès que l'une de nos hypothèses correspond au but. On peut donc interpréter intuitivement le séquent comme "Si on a les hypothèses A, B, C... alors, on peut prouver P". L'ordre des hypothèses est bien sûr interchangeables... (avec certaines logiques tordues, ce n'est pas forcément le cas... }:-D )

Maintenant, on va agencer les séquents entre eux pour qu'ils décrivent une preuve, tout ça de manière cohérente. L'agencement porte le nom d'"arbre de dérivation" ou "arbre de preuve". Déjà, il faut savoir que notre logique admet certaines règles qui lui donne son sens et régisse sa cohérence (du genre, pour éviter de se retrouver à prouver faux, et donc n'importe quoi). Pour la logique intuitionniste, ces règles exprimées sous forme d'arbre de dérivation sont les suivantes:

------------ (Hyp) ou (Ax), appelé aussi "axiome d'hypothèse"
D1, A |- A

avec D1 liste d'hypothèse et A une proposition.

Avant de continuer, je précise que dans les arbres de dérivations la proposition à prouver se trouve en bas et les hypothèses en haut. Il est donc plus commode de lire de bas en haut. La régle précédente s'appelle "l'axiome d'hypothèse". Elle ne demande pas de séquent au dessus d'elle et correspond du coup à une feuille de l'arbre de dérivation. Bref, la suite:
D1 |- B
------------ (Weak G)
A, D1 |- B

D1 |-
---------- (Weak D)
D1 |- A

A, A, D1 |- B
----------------- (Dupl G)
A, D1 |- B

D1 |-
------------ (F D)
D1 |- F

----------- (T D)
D1 |- T


--------------- (F G)
D1, F |- A

D1 |- A
------------ (T G)
D1, T |- A

D1, A |- B
------------------ (-> D)
D1 |- A -> B


D1 |- A ...... D1, B |- C
----------------------------- (-> G) , appelé aussi le "modus ponens"
D1, A -> B |- C


D1, |- A
------------- (¬ G)
D1, ¬A |-


D1, A |-
------------ (¬ D)
D1 |- ¬A


D1, A, B |- C
------------------ (/\ G)
D1, A /\ B |- C

D1 |- A ... D1 |- B
------------------- (/\ D)
D1 |- A /\ B

D1, A |- C ... D1, B |- C
-------------------------- (\/ G)
D1, A\/B |- C

D1 |- A
-------------- (\/ D1)
D1 |- A \/ B

D1 |- B
------------ (\/ D2)
D1 |- A \/ B

Et voilà pour les règles! On peut voir que à quelques exceptions près (qui est l'axiome d'hypothèse et les règles d'affaiblissement), chacune des règles correspond à un opérateur et à un côté du séquent. On dit qu'une formule F est "prouvable en logique intuitionniste" si son séquent correspondant " |- F " est prouvable, ie admet un arbre de dérivation respectant les règles décrites ci-dessus et se finissant à chaqu'un de ses embranchements par une feuille.

Maintenant, un petit exemple pour vous montrer comment ça s'agence... On va donc essayer de prouver F = ( (A -> B) -> ((B -> C) -> (A -> C)) ) pour commencer. L'arbre de preuve correspondant est:

..................................----------(Hyp) ------------(Hyp)
...................................A,B |- B..........A,B,C |- C
---------------- (Hyp) .... ------------------------------ (-> G) sur B->C
B -> C, A |- A ............. B -> C, A, B |- C
---------------------------------------------- (-> G) sur A->B
A -> B, B -> C, A |- C
------------------------------- (-> D)
A -> B, B -> C |- A -> C
----------------------------------- (-> D)
A -> B |- (B -> C) -> (A -> C)
------------------------------------------ (-> D)
|- (A -> B) -> ((B -> C) -> (A -> C))

(note: l'arbre de preuve se construit de bas en haut: c'est beaucoup plus pratique que d'essayer de prévoir les séquents sur lesquels on va tomber ^^ )

[Note: les ..... n'apparaissent pas d'habitude, c'est juste que le forum contracte automatiquement plusieurs espaces successifs en un seul, cassant toute ma présentation...]

L'arbre de preuve se termine bien, donc F est prouvable. CQFD !


Comme je l'ai fait remarqué, le calcul des séquents est juste un moyen de représenter une preuve, c'est un "système de preuve". Certain de ces systèmes portent des noms. Par exemple, le calcul des séquents appliqué à la logique intuitionniste porte le nom (LJ), le calcul des séquent appliqué à la logique classique porte le nom de (LK)...

----------------------------------------------------------------------------------------------------

Voilà donc pour le calcul des séquents et son application pour la logique intuitionniste. Il y a quelques propriétés amusantes entre (LJ) et (LK) (notamment, de décidabilité que l'on perd quand on passe en logique classique, etc etc). Mais bon, si déjà vous avez tenu jusqu'à là, c'est déjà très bien...

Si vous voulez creuser la question, il existe d'autres systèmes de preuves que le calcul des séquents, d'autre logiques que la logique intuitionniste et classique (ex: la logique linéaire, qui s'intéresse à l'utilisation des hypothèses lors d'une preuve). Je vous invite également à tenter de prouver avec (LJ) plusieurs formules de plus en plus grosses, histoire de faire mumuse avec des jolis arbres (et de se rendre compte que l'on a encore commencé trop haut sur le papier).

Intéressant, mais ce serait peut-être plus lisible en mettant les preuves dans une image plutôt que d'utiliser les symboles du forum.

Et sinon... les séquents se lisent de haut en bas ou de bas en haut ? (gros doute peut-être dû à la fatigue)

Les arbres de dérivations s'écrivent de bas en haut (vu que c'est difficile de deviner sur quel séquent on va tomber au niveau des feuilles de l'arbre). Après, un séquent est juste "L |- A" avec L une liste de proposition et A le but à prouver...

Pour les images, je connais un package latex qui permet de faire des arbres de dérivation (je m'en suis servi pour le rapport de mon premier stage), donc si j'ai du temps (ie un autre week-end sans Wifi), j'éditerais mon texte précédent...

Ah, et j'en profite pour dire que des erreurs potentielles se sont probablement glissées dans le texte précédent (ça fait 8 mois que je n'ai pas fait de preuve avec (LJ), et je n'avais pas internet sous la main pour vérifier)...

Oki, pour ma part je suis en train de revoir la partie introductive de mon projet, donc je pourrais te passer une version d'ici quelques jours (qui sera mieux que la version de ma soutenance...).

Théorie des langages

La théorie des langages est la branche de l'informatique / mathématique qui cherche a produire des algorithmes capables de reconnaitre si une suite de caractères (le "mot") respecte un "motif" donné, c'est a dire une règle de construction.
Note: Je ne m'intéresse ici qu'aux langages réguliers.


Motifs

Pour écrire les motifs, on utilise les symboles (généralement une serie de lettre de l'alphabet) d'un langage (appelons le "Q"), couplés a des caractères de contrôle. Bien entendus, il est possible de parenthésé les motifs (et c'est même indispensable 99% du temps) car il y a une priorité implicite entre les symboles.
Pour tout les exemples, j'utilise Q = {a, b} (c'est a dire que l'alphabet Q est constitué des symboles a et b).

Le "." est le symbole qui fait la liaison entre deux caractères qui se suivent. Par exemple, "a.b" signifie "le symbole a puis le symbole b".
Note: Le point est implicite, donc l'exemple est notable plus simplement "ab".

Le "ε" est le symbole vide, c'est a dire qui ne demande aucun symbole (on passe directement a la suite). Par exemple, "aεb" est strictement équivalent a "ab". Il est beaucoup plus utile qu'il en a l'air, mais j'y reviendrais plus tard.
Note: le mot "" (ou "ε") se note "∅"

Le "|" est le symbole "ou". Il qui autorise un des deux caractères autours de lui. Par exemple, "a|b" signifie "le symbole a ou le symbole b".
Le point a la priorité sur le ou: ab|b = (ab)|b = "(a suivis de b) ou b".

Le "*" est le symbole de la mise a l'étoile. Un motif mis a l'étoile est reconnus s'il est présent un nombre quelconque de fois. Par exemple, "a*" reconnais "a", "aa", "aaa"... et même "ε" !
Et là, c'est vachement plus drôle quand on tombe sur des trucs comme "(ab|b)*", par ce que "abbbab" (ab.b.b.ab) est reconnus, tout comme "bbab" (b.b.ab) mais pas "bba". Bref, notre motifs reconnais une infinité de mots s'il a au moins une mise a l'étoile.
La mise a l'étoile a la priorité maximale: a*b|b = ((a*)b)|b

Note: on définis aussi "+" (en exposant) comme étant une mise a l'étoile avec au moins une fois le motif.


Automates a états finis (AEF)

Notions préliminaires sur les graphes

Un graphe est un ensemble de points (qu'on appelle "sommets") reliés entre-eux par des liaisons (qu'on appelle "arcs"). On numérote généralement les sommets, et quand on parle d'un arc, on le désigne par les deux chiffres des sommets. Au passage, comme je parle de graphes orientés avec mes automates, les arcs vont avoir un sens.
Exemple de graphe:


Parfois, il y a des "couts" sur les arcs (dans notre cas, il va s'agir de symboles), auquel cas on note l'arc (p, ω, q), avec p le numéro du sommet d'origine, ω le cout et q le numéro du sommet de destination.

Quand on passe d'un sommet a un autre, on fait un "chemin". Un chemin peut passer par des sommets intermédiaires, on note alors le chemin sous la forme d'une succession de (sommet, arc, sommet). On note parfois les chemins sous la forme d'une succession de sommets s'il n'y a qu'un arc au maximum dans le graphe (on parle de "graphe d'ordre 1").
Par exemple:

Sur l'exemple, on peut faire deux chemins "simples" de a vers f: (a, 2, e), (e, 5, f) ou (a, 1, b), (b, 4, f). Ou encore "aef" ou "abf".
Un chemin peut faire des boucles, c'est a dire partir d'un sommet pour revenir sur lui même (il y a alors une infinité de chemins dans le graphe: si "aba" existe, alors "ababa" existe aussi, de même que "ababababababa", ect...).

Automate

Un automate est un graphe orienté. Les sommets représentent les "états" d'un automate et les arcs sont les liaisons entre les états. Les arcs ont des couts: il s'agit des symboles que doit lire l'automate pour passer d'un état a un autre.
L'automate commence dans un unique état initial et doit finir la lecture du mot en étant dans un des états finaux pour valider la lecture du mot.
Si l'automate tombe sur un caractère qu'il ne peut pas lire (pas de liaisons), alors il ne valide pas le mot.

En gros, voila ce que ça donne:

L'automate en exemple reconnais (ab|bca)+bb(ab|cb)*a. Le triangle est l'état initial et le carré est l'état final.

On remarque que le point est une liaison entre deux états, le ou est représenté par plusieurs liaisons d'un état vers d'autres états, et la mise a l'étoile est une boucle dans le graphe.

Enfin dernière remarques: dans certains automates, on a parfois plusieurs choix de valide avec un même caractère lu, et seule la lecture du reste du mot indiquera la bonne branche a prendre. On parle d'automate non déterministe, et franchement... c'est une plaie a codé.


L'Algorithme

Le but de cet algorithme est de lire un automate et de pondre le motif qu'il reconnais. Rien que ça.

Notations:
Je note "R" ou "Δ" l'ensemble des états, et un état en particulier "r".
Je note "s" l'état initial, "F" l'ensemble des états finaux et "f" un état final en particulier.


Langage (Q, Δ, s, F)
  res <- ∅
  Pour tout état f de F faire
    res <- res | Lang_rec (s, Q, Δ, f)
  Fin pour
  Si s ∈ Q alors
    res <- res | ε
  Fin si
  renvoyer res
Fin Langage

Lang_rec (p, R, Δ, q)
  Si R = ∅ alors
    renvoyer { ω ∈ Z*, (p, ω, q) ∈ Δ }
  Sinon
    choisir r ∈ R
    res1 <- Lang_rec (p, R \ {r}, Δ, q)
    res2 <- Lang_rec (p, R \ {r}, Δ, r)
    res3 <- Lang_rec (r, R \ {r}, Δ, r)
    res4 <- Lang_rec (r, R \ {r}, Δ, q)
    renvoyer res1 ∪ res2 ∪ res3 ∪ res4
  Fin si
Fin Lang_rec