Apprendre la logique
Bonjour à tous, du bas de mon petit niveau mi-L2 en maths, j'essaie de m'intéresser un peu à la logique en ce moment.:-D
En effet, je m'interroge pas mal sur "qu'est-ce que la logique", quel est le formalisme mathématique de cette logique, comment on définit les quantificateurs, qu'est-ce qu'une théorie mathématique (genre théorie des ensembles), comment on peut la définir formellement ... etc.
Problème : Je ne sais pas du tout comment, ni par quoi commencer.
Je serais bien en peine d'expliquer réellement ce que je cherche à comprendre, puisque j'ai déjà l'impression de ne pas réellement comprendre ce que j’essaie de comprendre.
Mon premier réflexe à été de me rendre sur les pages Wikipédia consacrées à la logique. En plus d'être perdu entre tous les mots que je vois défiler (théorie des modèles, théorie de la démonstration, logique du premier ordre... etc), il y a quelque chose qui m'embête : on retrouve la notion d'ensemble partout. Quasiment à chaque fois, les notions sont définies en utilisant le terme "ensemble". Ça me gène un peu, j'ai l'impression que ça fait un peu cercle vicieux. Pour parler des ensembles, on utilise des notions de logiques, des quantificateurs ... etc, et pour parler de ses choses, on parle d'ensembles.
Enfin voilà, donc si vous pouviez m'aiguiller un peu, me dire par quoi commencer et pourquoi, ainsi que tout ce qui vous paraîtrait utile, ce serait avec plaisir.
Merci d'avance.
En effet, je m'interroge pas mal sur "qu'est-ce que la logique", quel est le formalisme mathématique de cette logique, comment on définit les quantificateurs, qu'est-ce qu'une théorie mathématique (genre théorie des ensembles), comment on peut la définir formellement ... etc.
Problème : Je ne sais pas du tout comment, ni par quoi commencer.
Je serais bien en peine d'expliquer réellement ce que je cherche à comprendre, puisque j'ai déjà l'impression de ne pas réellement comprendre ce que j’essaie de comprendre.
Mon premier réflexe à été de me rendre sur les pages Wikipédia consacrées à la logique. En plus d'être perdu entre tous les mots que je vois défiler (théorie des modèles, théorie de la démonstration, logique du premier ordre... etc), il y a quelque chose qui m'embête : on retrouve la notion d'ensemble partout. Quasiment à chaque fois, les notions sont définies en utilisant le terme "ensemble". Ça me gène un peu, j'ai l'impression que ça fait un peu cercle vicieux. Pour parler des ensembles, on utilise des notions de logiques, des quantificateurs ... etc, et pour parler de ses choses, on parle d'ensembles.
Enfin voilà, donc si vous pouviez m'aiguiller un peu, me dire par quoi commencer et pourquoi, ainsi que tout ce qui vous paraîtrait utile, ce serait avec plaisir.
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Mais pour la logique, honnêtement je suis comme toi, je suis assez débutant en maths mais un truc m’a vraiment beaucoup aidé c’est ce topic: http://www.les-mathematiques.net/phorum/read.php?16,1579286,page=1
Ça ne répondra peut-être pas imédiatement à tes questionnements vis-à-vis du "cercle vicieux", mais celui-ci est à peu près inévitable (il faut avoir un truc de départ, après on peut essayer de le rendre plus faible, par exemple de l'aritgmétique, et là on rentre dans les reverse mathematics)
Cela dit, si tu en es au début, tu as de la chance, car il y a 2 sortes de cours de logique, dont un qui est assez décontractant pour les débutant, il s'agit de la logique propositionnelle. Je te donne les définitions et quelques exos, ça te chauffera un peu pour poser des questions plus précises. Je fais semblant de croire que tu comprends "si..alors.." et $<<X\to Y>>$ est une abréviation de $<<$ si $X$ alors $Y>>$
[large]Vocabulaire:[/large]
1/ $<< X$ est un séquent est une abréviation de $<<$ il existe un couple $(u,v)$ tel que $X=(u,v)$ et $u$ est un ensemble** de phrases et $v$ est un ensemble de phrases $>>$.
2/ J'appelle déduction atomique une fraction (au sens syntaxique), avec au numérateur 1 ou 2 séquents (quand il y en a 2 je les sépare par un signe $+$) et au dénominateur 1 séquent.
3/ Les seules déductions autorisées sont celles d'une des deux formes suivantes:
$$ \frac{( \{A;B;... ; X \}, \{U;V;W \} ) }{ ( \{A;B;...\}, \{X\to U; V; W;...\} ) }$$
$$ \frac{ (\{X;Y;...\}, \{A; L;M...\}) + (\{X;Y;...\}, \{A\to B; ...\}) } { (\{X;Y;...\}, \{B; L;M...\}) }$$
4/ Une preuve classique est un "arbre" présenté comme un "enchainement de fractions" du style:
[size=x-large]$$ \frac{ \frac{ bidule + Olive }{blic } + { \frac{ Gertrude }{ Yvette }} }{ truc} $$[/size]
où toutes les déductions utilisées sont autorisées.
5/ Les "hauts" (ici bidule, Olive, et Gertrude) sont appelés "les feuilles" (ou encore les axiomes) de la preuve.
6/ Les seuls axiomes autorisés par les maths comme pouvant être "des feuilles indiscutables sont les séquents $(X,Y)$ tels que $X\cap Y \neq \emptyset$.
7/ Le théorème prouvé par une preuve en n'utilisant que les axiomes autorisés par (6) est la conclusion (dans l'exemple, c'est "truc") de l'arbre (on dit la racine de l'arbre, mais peu importe).
La "présentation polie" d'un théorème (n'oublie pas qu'un théorème est un séquent) s'obtient en transformant en phrase le séquent comme suit:
$(\{a_1;...;a_n\}, \{b_1;...;b_p\} )$ est transformé en $<<$ si $a_1$ et $a_2$ et ... et $a_n$ alors $(b_1$ ou ... ou $b_n)>>$
[large]Exercice:[/large]
1/ prouver les deux théorèmes suivants:
$$ A\ ou \ (A\to $$
$$ ((A\to \to A)\to ((A\to \to $$
2/ prouver les mêmes théorèmes, mais sans utiliser de coupure (une coupure consiste à utiliser la déduction de la première forme ) , ie :
$$ \frac{( \{A;B;... ; X \}, \{U;V;W \} ) }{ ( \{A;B;...\}, \{X\to U; V; W;...\} ) }$$
alors qu'il existe une preuve du séquent $(\{A;B;... \}, \{U;V;W \} )$. Autrement dit, "sans coupure" signifie que tu ne peux passer $X$ de gauche à droite que si $X$ ne peut pas être prouvé avec les autres hypothèses de gauche.
Remarque: tape "calcul des séquents" sur wikipedia pour te familiariser avec la disposition (j'ai utilisé des couples $(machin, truc)$, mais l'usage est d'utiliser plutôt $machin\vdash truc$.
[large]Suite:[/large]
Pose de nouvelles question quand tu auras réussi ces exos.
** tu peux, ici, considérer qu'on n'a affaire qu'à des ensembles finis, ce n'est pas grave.
Quelques explications supplémentaires sur ce que tout ça veut dire n'aurait pas été de trop je crois.
Merci pour la réponse cela dit.
Essaie de suivre des liens par google après avoir tapé "calcul des séquents" et après je répondrai à tes questions. Là, je ne sais pas par où commencer, car je ne sais pas ce que tu connais d'avance.
Ce qui caractérise les choses logiques qu'on peut raconter à un débutant, c'est juste la compacité et la complétude: ie quelque soit le truc, ou bien on peut le prouver, ou bien on peut (facilement) construire un modèle où il est faux.
Mais acquiers un peu de pratique des séquents pour te motiver. Je te rappelle les 3 formes de déductions autorisées, les choses apparaissant à gauche et à droite de $\vdash$ ont le droit d'être des ensembles quelconques de phrases:
option1:
$$ \frac{(L\vdash (\{A\} \cup K)) + (M\vdash (\{(A\to \} \cup K')}{ (L\cup M)\vdash (\{B\}\cup K\cup K' ) } $$
option2:
$$ \frac{(L\cup \{A\}) \vdash (\{B\} \cup K) }{ L \vdash (\{A\to B\} \cup K) } $$
option3:
$$ \frac{L\vdash K}{L'\vdash K'}$$
Seulement quand $L\subset L'$ et $K\subset K'$.
Les axiomes sont les séquents $X\vdash Y$ tels que $X\cap Y\neq \emptyset$.