Logique et raisonnement scientifique cours transversal Collège Doctoral Pr. Alain Lecomte

Logique et raisonnement scientifique

cours transversal

Collège Doctoral

Pr. Alain Lecomte

8- La logique et les processus

Logique linéaire

mathématisation3

bilan

Hilbert méthodes finitistes pour fonder la cohérence des mathématiques, vers les théorèmes d’incomplétude (Gödel, 1931)

Brouwer une exigence de constructibilité– cf. fameuse question: « existe-t-il deux irrationnels x et y

tels que xy soit un rationnel? » Essayons avec x = y =

– Si xy est un rationnel, on a répondu positivement– Sinon (xy)y = 2 et on a répondu positivement

2

La logique et l’informatique

Modèles de calcul

mathématisation5

Un autre problème posé par Hilbert:l’Entscheidungsproblem

Le problème de la décision est résolu si l’on connaît une procédure qui permette de déterminer, en utilisant un nombre fini d’opérations, la validité, respectivement la satisfaisabilité d’une expression logique donnée (1928)

mathématisation6

Turing (1936)

Machines de Turing Machine de Turing universelle Indécidabilité du problème de l’arrêt

mathématisation7

Ruban

Tête de lecture/écriture

mathématisation8

qi

Alphabet : = {#, a0, a1, a2, …, an} , symboles admis sur le ruban# : le blanc, - {#}, symboles d’entréeEnsemble d’états : Q = {q0, q1, …, qm} q0 : état initialF Q : ensemble d’états finaux (peut être vide)

ai1 ai2 ai3 ai4 ai5 ai6 ai7 ai8… … aik

mathématisation9

Règles de transition

Une règle de transition est un quintuplet

(qi, ai, qj, aj, Dir) où Dir{G, D}

écrit aussi: (qi, ai) (qj, aj, Dir)

mathématisation10

exemple

= {0, 1, X, Y, #} = {0, 1} Q = {q0, q1, q2, q3, q4}

F = {q4} Transitions (quintuplets)

(q0, 0, q1, X, D), (q0, Y, q3, Y, D), (q1, 0, q1, 0, D), (q1, 1, q2, Y, G), (q1, Y, q1, Y, D), (q2, 0, q2, 0, G), (q2, X, q0, X, D), (q2, Y, q2, Y, G), (q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation11

diagramme

mathématisation12

q0

0 0 0 1 1 1

(q0, 0, q1, X, D)

(q0, 0, q1, X, D), (q0, Y, q3, Y, D), (q1, 0, q1, 0, D), (q1, 1, q2, Y, G),

(q1, Y, q1, Y, D), (q2, 0, q2, 0, G), (q2, X, q0, X, D), (q2, Y, q2, Y, G),

(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation13

q1

X 0 0 1 1 1

(q1, 0, q1, 0, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation14

q1

X 0 0 1 1 1

(q1, 0, q1, 0, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation15

q1

X 0 0 1 1 1

(q1, 1, q2, Y, G)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation16

q2

X 0 0 Y 1 1

(q2, 0, q2, 0, G)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation17

q2

X 0 0 Y 1 1

(q2, 0, q2, 0, G)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation18

q2

X 0 0 Y 1 1

(q2, X, q0, X, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation19

q0

X 0 0 Y 1 1

(q0, 0, q1, X, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation20

q1

X X 0 Y 1 1

(q1, 0, q1, 0, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation21

q1

X X 0 Y 1 1

(q1, Y, q1, Y, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation22

q1

X X 0 Y 1 1

(q1, 1, q2, Y, G)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation23

q2

X X 0 Y Y 1

(q2, Y, q2, Y, G)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation24

q2

X X 0 Y Y 1

(q2, 0, q2, 0, G)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation25

q2

X X 0 Y Y 1

(q2, X, q0, X, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation26

q0

X X 0 Y Y 1

(q0, 0, q1, X, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation27

q1

X X X Y Y 1

(q1, Y, q1, Y, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation28

q1

X X X Y Y 1

(q1, Y, q1, Y, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation29

q1

X X X Y Y 1

(q1, 1, q2, Y, G)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation30

q2

X X X Y Y Y

(q2, Y, q2, Y, G)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation31

q2

X X X Y Y Y

(q2, Y, q2, Y, G)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation32

q2

X X X Y Y Y

(q2, X, q0, X, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation33

q0

X X X Y Y Y

(q0, Y, q3, Y, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation34

q3

X X X Y Y Y

(q3, Y, q3, Y, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation35

q3

X X X Y Y Y

(q3, Y, q3, Y, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation36

q3

X X X Y Y Y

(q3, #, q4, #, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation37

q4

X X X Y Y Y

(q3, #, q4, #, D)



(q3, Y, q3, Y, D), (q3, #, q4, #, D)

mathématisation38

Le -calcul de Church1934 - 1936

formuler avec précision le problème de la substitution des variables dans une expression qui représente une fonction– Application– Abstraction

Équivalence avec MdT Théorème de Church-Rosser Une condition pour la normalisation : termes

« typés »

mathématisation39

Le calcul des séquents (Gentzen, 1934)comme méthode de décision pour la logique classique et la logique intuitionniste

Prouver:

(A B) ((B C) (A C))

mathématisation40

démonstration

A B, B C, A, B | B, C A B, B C, A, B, C | C

A B, B C, A | A, C A B, B C, A, B | C

A B, B C, A | C

A B, B C | A C

A B | (B C) (A C)

| (A B) ((B C) (A C))

mathématisation41

axiome :

[ D] : A, |- , B [ G] : |- , A B, |- |- , AB A B, |-

[ D] : A, |- [ G] : |- , A

|- , A A, |-

Règles logiques

A, |- , A

coupure : |- , A A, |- ’

, |- , ’

mathématisation42

Règles structurelles

Affaiblissement :à gauche : |- à droite : |-

, A |- |- A, Contraction :à gauche : , A, A |- à droite : |- A, A,

, A |- |- A, Permutationà gauche : , A, B, |- à droite : |- ’, A, B,

, B, A, |- |- ’, B, A,

mathématisation43

Gentzen - suite

Hauptsatz : Le système sans coupure permet de prouver

les mêmes séquents que le système avec coupure !

Alors… La règle de coupure ne sert à rien? Si!

mathématisation44

Calcul intuitionniste

dissymétriser le calcul: les séquents ont au plus une formule en partie droite

empêche tiers exclu et double négation

Isomorphisme de Curry-Howard – types = formules -termes = preuves– réduction = élimination de la coupure

mathématisation45

Pourquoi casser les symétries?

En logique classique, |- A, ’|- B, ’

, ’ |- A B, , ’

et

|- A, |- B, |- A B,

sont équivalentes (à cause des règles de contraction et d’affaiblissement)

mathématisation46


Mais si on supprime ces règles?

mathématisation47


La logique linéaire (1985) : 1- partie conjonctive

[ G] , A, B |- [ D] |- A, ’|- B, ’, A B |- , ’ |- A B, , ’

[& G]1 , A |- [& D] |- A, |- B,

, A & B |- |- A & B,

[& G]2 , B |- , A & B |-

mathématisation48

Logique linéaire – 2partie disjonctive

[ G] |- A, B, [ D] , A |- ’, B |- ’ |- A B, , ’, A B |- , ’

[ D]1 |- A, [ G] , A |- , B|-

|- A B, , A B |-

[ D]2 |- B, |- A B,

[ D] : A, |- [ G] : |- , A |- , A A, |-

NB : A –o B A B

mathématisation49

Logique linéaire - 3

Retrouver la logique classique?

A B !A –o B Le rôle des exponentielles : réintroduire localement

les règles structurelles

, A |- [intro !] , !A, !A |- [contraction]

, !A |- , !A |-

|- [affaiblissement]

, !A |-

mathématisation50

Le menu….

Prix : 16 € Entrée : au choix jambon ou salade Plat de résistance : entrecôte Accompagnement : frites à volonté Déssert : au choix

fromage ou fruit de saison selon arrivage (pêche ou

pomme)

mathématisation51

Le menu….

Prix : 16 € Entrée : au choix jambon ou salade Plat de résistance : entrecôte Accompagnement : frites à volonté Déssert : au choix

fromage ou fruit de saison selon arrivage (pêche ou

pomme)

mathématisation52

La formule…

16 €

--o

(jambon & salade)

(entrecôte !frites)

(fromage & (pomme pêche))

mathématisation53

Autre exemple

Il y a un siège disponible sur Londres – Bruxelles Marie est à Londres John est à Londres

En principe:

Marie peut prendre l’avion pour Bruxelles

John peut prendre l’avion pour Bruxelles

Donc : Marie et John peuvent prendre l’avion pour Bruxelles

mathématisation54

En réalité…

Soit les prémisses :x (Londres(x) –o Brux(x))

pour tout individu x, s’il est à Londres, il peut aller à Bruxellesmais cette formule est utilisable une seule fois

Londres(Marie)Londres(John)Elles ne permettent pas de déduire Brux(Marie) et

Brux(John)

mathématisation55

déduction

x (Londres(x) –o Brux(x))Londres(Marie) –o Brux(Marie)Londres(Marie) Brux(Marie)

Donc : x (Londres(x) –o Brux(x)), Londres(Marie) Brux(Marie)Londres(John) Londres(John)

Donc : x (Londres(x) –o Brux(x)), Londres(Marie), Londres(John) Brux(Marie) Londres(John)

Ou bien : x (Londres(x) –o Brux(x)), Londres(Marie), Londres(John) Brux(John) Londres(Marie)

mathématisation56

Plus sérieux…

!(e (electron(e) –o z position(e, z)))

!(e (electron(e) –o z’ vitesse(e, z’)))

Impossible de prouver :

!(e (electron(e) –o z position(e, z) z’ vitesse(e, z’)))

mathématisation57

déduction

!(e (electron(e) –o z position(e, z)))

electron(i)

electron(i) –o z position(i, z)

z position(i, z)

Mais electron(i) a été consommé, on ne peut pas le réutiliser pour prouver z’ vitesse(e, z’)

mathématisation58

Réseaux de preuves

C’est ce qui remplace les -termes Soit à démontrer le séquent suivant:

CBCABA ,

mathématisation59

CBCABA ,

mathématisation60

CBCABA

CBCABA

,

,,

mathématisation61

CBCABACBCABACBCBAA

,,,

,

mathématisation62

CBCABACBCABACBCBCCBB

AA

,,,

,

mathématisation63


AA

,,,

,

mathématisation64

mais on aurait pu faire autrement

CBCABA

CBCABA

,

,,

mathématisation65

CBCABA

CBCABABBCCAA

,

,,,

mathématisation66

CBCABA

CBCABABBCCAA

CCAA

,

,,,

mathématisation67

CBCABA

CBCABABBCCAA

CCAA

,

,,,

mathématisation68

CBCABA

CBCABABBCCAA

CCAA

,

,,,


AA

,,,

,

mathématisation69


AA

,,,

,

CBCABA

CBCABABBCCAA

CCAA

,

,,,

i

mathématisation70

BACABA

CBCCB

A

BA

CBBABCCA

CA

i

mathématisation71

BACABA

CBCCB

A

BA

CBBABCCA

CA

i

mathématisation72

BACABA

CBCCB

A

BA

CBBABCCA

CA

mathématisation73

BA C CBA

BA CA CB

mathématisation74

BA C CBA

BA CA CB

: a « right » conjunction

: a « left » conjunction

: a « left » disjunctionA B A B

o oi oi i

i i o

mathématisation75

symmetries

left conjunction = right disjunction right conjunction = left disjunction right formula = negation of left formula left formula = negation of right formula

mathématisation76

BA C CBA

BA CA CB


: a « right » disjunction (between neg.)


mathématisation77

BA C CBA

BA CA CB

mathématisation78

BA C CBA

BA CA CB

mathématisation79

correctness criterion

connectivity switches : no cycle in any graph obtained by

removing one edge to each par link

Une « géométrisation » de la logique

mathématisation80

Prouver c’est aussi planifier

cf. une action produit un changement dans le monde

utilise des ressources se réalise par combinaison d’actions plus

élémentaires

mathématisation81

a

c

poser c sur la table

mathématisation82

a

c


mathématisation83

a

c


mathématisation84

a

c


mathématisation85

a c


mathématisation86

ca


mathématisation87

Passer de l’état du monde: main vide (V) c en haut de pile (donc accessible) (H(c)) c sur a (S(c, a))à main vide c en haut de pile c en bas de pile (B(c)) a en haut de pile

mathématisation88

décrit par le séquent :V, H(c), S(c, a) VH(c)B(c)H(a)

mathématisation89

Actions élémentaires

prendre(x) : V, H(x), B(x) T(x) poser(x) : T(x) VH(x)B(x) oter(x, y) : V, H(x), S(x, y) T(x)H(y) mettre(x, y) : T(x), H(y) VH(x)S(x,

y)

mathématisation90

preuve

T(c) V H(c) B(c) H(a) H(a)------------------------------------------------- -

droiteT(c), H(a) V H(c) B(c) H(a)----------------------------------------------- -

gaucheV, H(c), S(c, a) T(c) H(a) T(c) H(a) V H(c) B(c)

H(a)-----------------------------------------------------------------------------------coupureV, H(c), S(c, a) V H(c) B(c) H(a)

mathématisation91

preuve

poser(c) H(a) H(a)-------------------------------------- -

droiteT(c), H(a) V H(c) B(c)

H(a)------------------------------------ -

gaucheoter(c, a) T(c) H(a) V H(c) B(c) H(a)-----------------------------------------------------------------------------------coupureV, H(c), S(c, a) V H(c) B(c) H(a)

mathématisation92

preuve action?

On peut extraire une composition d’actions d’une preuve

comme on peut extraire un programme d’une preuve (informatique théorique)

mathématisation93

interaction

& : choix « actif » (vous avez le choix entre … et …)

: choix « passif » (l’un ou l’autre, vous ne décidez pas)

: les deux, dans un ordre séquentiel non déterminé

: les deux, en parallèle, par exemple l’échange (l’un contre l’autre)

: le changement de point de vue

mathématisation94

interprétation

Interaction la logique n’est plus seulement interprétable comme

« décrivant un extérieur », elle s’interprète « par rapport à elle-même »,

autrement dit elle réfère à ses propres procédures : l’interprétation des règles se fait dans un dialogue interne et le système se voit ainsi doté d’une dynamique des preuves

mathématisation95

La logique et les processus

une science formelle des processus informationnels convergents

Applications:– Linguistique– Biologie – Sciences cognitives (Krivine)

mathématisation96

biologie

Antoine Danchin: « la cellule est un ordinateur vivant »– Physique : matière, énergie, temps…– Biologie : Physique + information, codage, contrôle…– Arithmétique : chaînes d’entiers, récursivité, codage…– Informatique : arithmétique + programme + machine… »– « comme dans le cas de la construction d’une machine, dans celui

de la construction d’une cellule, on a besoin d’un livre de recettes… cela demande ensuite qu’on soit capable de changer le texte de la recette en quelque chose de concret : ceci consiste dans le « transfert d’information ». Dans une cellule, ce transfert d’information est assuré par le programme génétique »

mathématisation97

conclusion

au cœur d’un processus contemporain de mathématisation à propos d’objets qui n’ont pas pu jusqu’à présent être l’objet d’un tel processus, faute d’outils mathématiques adéquats

il était assez imprévisible et il reste curieux que ce soit la logique, dans son propre développement interne, qui donne aujourd’hui de tels outils, via l’intégration qu’elle opère des lois de fonctionnement de machines abstraites.

Documents

Logique et raisonnement scientifique cours transversal Collège Doctoral Pr. Alain Lecomte