*Mode d'emploi* : le texte situé en bas des illustrations n'est pas destiné à être lu pendant le visionnage, puisqu'il reprend juste les explications orales. Si une séquence présente un concept que vous ne maîtrisez pas, vous êtes invité à *mettre la vidéo en pause* à la fin des explications orales et à prendre le temps de *lire le texte* et de comprendre les illustrations associées. Cette vidéo représente un cours de deux heures et pour vraiment assimiler son contenu, il faut décortiquer chaque notion pendant plusieurs minutes, prendre des notes, reproduire les figures et les raisonnements.
Monsieur, je ne comprends vraiment pas pourquoi la formule que vous présentez vers 14:00 n'est pas valide. Pour tout x, y, z: (pair(x) et x×y=z) => pair(z). On instancie avec x=6, y=5 et z=5 et cela donne : (pair(6) et 6×5=5) => pair(5). (vrai et faux) => faux. faux => faux. (ex falso sequitur quodlibet) vrai. La formule est donc bien valide, non ?
@@aoe9857 Dans l'interprétation 2, prod(x,y) vaut y (et pas x fois y), donc prod(6,5)=5 est vrai. J'ai changé le sens de prod (pour lui donner celui d'une projection) et le sens de pair (pour lui donner le sens de multiple de 3). On pourrait dire que pour qu’une formule soit valide, il faut que dans tous les mondes alternatifs imaginables où les symboles utilisés ont tous les sens possibles imaginables, la formule reste vraie. Si la formule était valide, alors elle le resterait si on donnait n'importe quel autre noms aux prédicats et termes fonctionnels, comme par exemple « pout tout x,y,z, (p(x) et q(t(x,y),z)) -> p(z) ». Cela supposerait, incidemment, que « (p(x) et q(t(x,y),z)) -> p(z) » soit satisfaite par *toutes* les valuations de x, y et z. Non seulement, x=6, y=5, z=5, mais aussi toutes les autres assignations possibles des trois variables. En résumé, une formule qui est vraie dans un sens particulier des symboles fonctionnels et relationnels utilisés, même si ce sens est un sens usuel ou standard, est une formule cohérente. Pour qu’une formule soit valide, il faut qu’elle soit vraie pour *tous* les sens possibles, même les plus farfelus (si applicable), des symboles utilisés. Par exemple « pour tout x (pair(x) ou non pair(x)) » est valide. Elle reste vraie quel que soit le sens du symbole « pair », ou même si je le remplace par « chocolat », « nul », « père », etc. Mais ce qui ressort de votre remarque, c’est : était-ce une bonne idée pédagogique de prendre comme exemple des symboles ayant un sens standard connus de tous ? D’un coté, l’idée était de marquer les esprits, mais de l’autre, cela peut être un peu trompeur. J’aurais peut-être dû procéder en deux étapes. Enfin, pour aller plus loin, on peut très bien construire un ensemble A de formules toutes satisfaites par l’arithmétique standard, en donnant à pair et prod leur sens usuels - on dira que A est une théorie de l’arithmétique standard - tel que « A -> pout tout x,y,z, (pair(x) et egal(prod(x,y),z)) -> pair(z) » est valide. On pourra alors dire que « pout tout x,y,z, (pair(x) et egal(prod(x,y),z)) -> pair(z) » est démontrable dans A.
D'accord je comprends mieux votre exemple, une formule n'est valide que si elle est vraie pour tout interprétation possible des prédicats et fonctions qu'elle utilise. Peut-être que pour la pédagogie il aurait fallu bien insister sur ce point. Car si j'ai bien compris aussi votre dernière remarque, si on donne explicitement l'interprétation à avoir, les formules deviennent valides. Par exemple on définirait pair(x) (j'utilise la syntaxe Prolog pour que cela soit plus compréhensible) : pair(0). pair(s(X)) :- impair(X). impair(s(X)) :- pair(X). Et on ferait de même pour prod, etc. à l'exception de egal(x, y) qui n'est pas définissable (paramodulation).
@@aoe9857 Le problème, c'est que la logique ne permet pas de donner *explicitement* une interprétation. En particulier, elle ne permet pas de spécifier complètement, par exemple, ce qu'est l'ensemble N des entiers naturels. C'est la fameuse notion d'incomplétude dont je parle dans une de mes vidéos. Ce qu'on peut faire, comme dans votre exemple, c'est donner certains axiomes qui sont satisfaits par l'interprétation qui nous intéresse, comme par exemple A = { "pair(0)" et "pour tout X, pair(X) -> pair(s(s(X))" }. Si on est sûr que l'interprétation qui nous intéresse, par exemple l'arithmétique standard sur les entiers naturels, satisfait nos axiomes, et si on a un énoncé E tel que "A -> E" est une formule valide, alors on peut affirmer que la propriété décrite par E est vérifiée par l'arithmétique standard sur les entiers naturels. Mais ce que nous dit le premier théorème d'incomplétude de Godel, c'est que pour tout ensemble A d'axiomes qui sont satisfaits par l'interprétation standard de l'addition et de la multiplication sur les entiers naturels, il y a des énoncés E qui sont parfaitement vrais pour notre interprétation standard, mais tels que la formule "A -> E" n'est pas valide, mais seulement cohérente. En d'autres termes, bien que vrai dans l'arithmétique standard, un tel énoncé E n'est pas conséquence logique de nos axiomes. D'une certaine façon, ces axiomes ne sont pas suffisamment "complets" pour caractériser toutes les propriétés logiques de l'arithmétique. Je parle de cela dans cette vidéo : ua-cam.com/video/UlZAatzfRE8/v-deo.html Concrètement, on ne peut pas réaliser un ensemble A de règles Prolog tel que pour tout énoncé arithmétique E, "A->E" est valide si et seulement si E est mathématiquement vrai dans l'arithmétique standard. C'est même impossible si on s'autorise un ensemble infini, récursivement énumérable, de règles Prolog.
Il faudrait aller beaucoup plus loin que ce genre d'initiative individuelle, et proposer des ressources en ligne sous forme de "briques de connaissances" (vidéos, supports écrits, exercices...) à partir desquelles il serait possible de construire des parcours d'apprentissage cohérents, utilisables par toute personne voulant progresser en autodidacte dans une matière, mais aussi par les enseignants qui pourraient utiliser ces "briques" pour construire des cours, des préparations de cours à faire par les étudiants et des parcours de révisions. Ce serait un énorme travail, mais dont le résultat serait utilisable par des centaines d'enseignants et des milliers d'étudiants chaque année !
Bonjour Monsieur, Tout d'abord, je voudrais vous remercier pour la qualité et la clarté de vos différentes présentations. Malgré la difficulté de "rentrer" dans ce monde, c'est véritablement passionnant de vous écouter (et de tenter de bien tout comprendre). Je me permets de revenir vers vous concernant une question que je me pose et que je vais tenter de résumer maintenant. Minute 6'28 environ Sujet : la signature Vous écrivez: "nos 2 exemples d'interprétations concernent les mêmes symboles fonctionnels et symboles de prédicats...." Je ne suis pas complètement d'accord dans la mesure où c'est juste leur écriture qui est la même; on aurait, par exemple, pu (ou "du") écrire "pair1" et "pair2" pour avoir une certaine "clarté". Dès lors, les signatures seraient bien différentes puisque les significations ne seraient pas les mêmes. Mon interrogation ne concerne pas simplement cette "précision" qui me semblerait pertinente. Mon interrogation porte sur l'impact de ma remarque sur votre affirmation suivante concernant "l'infinité d'interprétations possibles" Dans l'optique de ma remarque cela est évident puisque les significations des termes utilisés peuvent être différentes. Je soupçonne toutefois, que votre remarque (concernant "l'infinité d'interprétations possibles") est plus ambitieuse. Ne voulez-vous pas dire, plutôt, qu'il y a une infinité de couples "domaine-signature" possibles, pour une même signature? Merci d'avance de votre retour, et encore une fois, tous mes remerciements, Michel Caussanel
Je ne sais pas si je vais réussir à être clair, car c'est un sujet délicat, bien que fondamental et passionnant, qui va au delà de mes enseignements d'initiation. En logique, on distingue deux aspects : l'aspect syntaxique qui concerne la manière dont les formules sont construites, et l'aspect sémantique, qui donne un sens mathématique aux symboles apparaissant dans les formules. Les formules sont des objets mathématiques à part entière : des objets purement syntaxiques, qui peuvent représenter des énoncés mathématiques abstraits grâce au concept d'interprétation. Mais tout cela a une finalité, une utilisation, qui n'est pas présentée dans cette vidéo, mais dont je parle dans ma vidéo intitulée "Des clés pour comprendre l'indécidabilité et l'incomplétude". Cette utilisation consiste à modéliser un objet mathématique grâce à des axiomes, puis à déduire de ces axiomes, à l'aide de règles d'inférence, des propriétés de cet objet mathématique. Mais en général, un ensemble cohérent d'axiomes a une infinité de modèles, et ce qu'on va démontrer à partir de ces axiomes sera vrai pour une infinité d'interprétations des symboles fonctionnels et relationnels apparaissant dans les axiomes, et pas seulement pour l'objet qu'on a voulu modéliser. Dès qu'on veut modéliser des objets mathématiques ayant la puissance d'expression de l'arithmétique standard (entiers naturels, addition et multiplication) si on décide de donner une interprétation unique aux symboles + (l'addition standard) et x (la multiplication standard), alors il n'existe aucun ensemble fini d'axiomes et même de schémas d'axiomes ayant pour unique modèle cette interprétation standard des symboles fonctionnel + et x. On est donc en quelque sorte "obligé" de considérer que ces symboles ont une infinité d'interprétations, dont celle qui nous intéresse. Ceci est directement lié à la notion d'indécidabilité d'une théorie axiomatique. Je tente d'expliquer ça dans la vidéo sus-mentionnée, mais je n'en suis pas satisfait, tout comme de cette réponse. Je n'ai pas le temps de faire mieux en ce moment, mais j'aimerais faire une nouvelle vidéo plus claire sur ce sujet.
@@OlivierBailleux Merci beaucoup pour votre rapide retour. Je vais avoir besoin d'un peu de temps pour bien comprendre ce que vous venez de me dire et revoir (plusieurs fois encore) la vidéo à laquelle vous faites référence. L'indécidabilité et l'incomplétude restent encore pour moi des thèmes non maîtrisés, mais la façon dont vous présentez les choses ouvre des pistes d'appropriation des concepts à explorer. Encore merci pour votre travail.
![Intelligence Artificielle [6.2] : Logique du premier order - syntaxe](http://i.ytimg.com/vi/1PfuTidp-Qk/mqdefault.jpg)
*Mode d'emploi* : le texte situé en bas des illustrations n'est pas destiné à être lu pendant le visionnage, puisqu'il reprend juste les explications orales. Si une séquence présente un concept que vous ne maîtrisez pas, vous êtes invité à *mettre la vidéo en pause* à la fin des explications orales et à prendre le temps de *lire le texte* et de comprendre les illustrations associées. Cette vidéo représente un cours de deux heures et pour vraiment assimiler son contenu, il faut décortiquer chaque notion pendant plusieurs minutes, prendre des notes, reproduire les figures et les raisonnements.
Monsieur, je ne comprends vraiment pas pourquoi la formule que vous présentez vers 14:00 n'est pas valide.
Pour tout x, y, z: (pair(x) et x×y=z) => pair(z).
On instancie avec x=6, y=5 et z=5 et cela donne :
(pair(6) et 6×5=5) => pair(5).
(vrai et faux) => faux.
faux => faux. (ex falso sequitur quodlibet)
vrai.
La formule est donc bien valide, non ?
@@aoe9857 Dans l'interprétation 2, prod(x,y) vaut y (et pas x fois y), donc prod(6,5)=5 est vrai. J'ai changé le sens de prod (pour lui donner celui d'une projection) et le sens de pair (pour lui donner le sens de multiple de 3).
On pourrait dire que pour qu’une formule soit valide, il faut que dans tous les mondes alternatifs imaginables où les symboles utilisés ont tous les sens possibles imaginables, la formule reste vraie.
Si la formule était valide, alors elle le resterait si on donnait n'importe quel autre noms aux prédicats et termes fonctionnels, comme par exemple « pout tout x,y,z, (p(x) et q(t(x,y),z)) -> p(z) ».
Cela supposerait, incidemment, que « (p(x) et q(t(x,y),z)) -> p(z) » soit satisfaite par *toutes* les valuations de x, y et z. Non seulement, x=6, y=5, z=5, mais aussi toutes les autres assignations possibles des trois variables.
En résumé, une formule qui est vraie dans un sens particulier des symboles fonctionnels et relationnels utilisés, même si ce sens est un sens usuel ou standard, est une formule cohérente. Pour qu’une formule soit valide, il faut qu’elle soit vraie pour *tous* les sens possibles, même les plus farfelus (si applicable), des symboles utilisés. Par exemple « pour tout x (pair(x) ou non pair(x)) » est valide. Elle reste vraie quel que soit le sens du symbole « pair », ou même si je le remplace par « chocolat », « nul », « père », etc.
Mais ce qui ressort de votre remarque, c’est : était-ce une bonne idée pédagogique de prendre comme exemple des symboles ayant un sens standard connus de tous ? D’un coté, l’idée était de marquer les esprits, mais de l’autre, cela peut être un peu trompeur. J’aurais peut-être dû procéder en deux étapes.
Enfin, pour aller plus loin, on peut très bien construire un ensemble A de formules toutes satisfaites par l’arithmétique standard, en donnant à pair et prod leur sens usuels - on dira que A est une théorie de l’arithmétique standard - tel que « A -> pout tout x,y,z, (pair(x) et egal(prod(x,y),z)) -> pair(z) » est valide. On pourra alors dire que « pout tout x,y,z, (pair(x) et egal(prod(x,y),z)) -> pair(z) » est démontrable dans A.
D'accord je comprends mieux votre exemple, une formule n'est valide que si elle est vraie pour tout interprétation possible des prédicats et fonctions qu'elle utilise. Peut-être que pour la pédagogie il aurait fallu bien insister sur ce point. Car si j'ai bien compris aussi votre dernière remarque, si on donne explicitement l'interprétation à avoir, les formules deviennent valides.
Par exemple on définirait pair(x) (j'utilise la syntaxe Prolog pour que cela soit plus compréhensible) :
pair(0).
pair(s(X)) :- impair(X).
impair(s(X)) :- pair(X).
Et on ferait de même pour prod, etc. à l'exception de egal(x, y) qui n'est pas définissable (paramodulation).
@@aoe9857 Le problème, c'est que la logique ne permet pas de donner *explicitement* une interprétation. En particulier, elle ne permet pas de spécifier complètement, par exemple, ce qu'est l'ensemble N des entiers naturels. C'est la fameuse notion d'incomplétude dont je parle dans une de mes vidéos.
Ce qu'on peut faire, comme dans votre exemple, c'est donner certains axiomes qui sont satisfaits par l'interprétation qui nous intéresse, comme par exemple A = { "pair(0)" et "pour tout X, pair(X) -> pair(s(s(X))" }. Si on est sûr que l'interprétation qui nous intéresse, par exemple l'arithmétique standard sur les entiers naturels, satisfait nos axiomes, et si on a un énoncé E tel que "A -> E" est une formule valide, alors on peut affirmer que la propriété décrite par E est vérifiée par l'arithmétique standard sur les entiers naturels.
Mais ce que nous dit le premier théorème d'incomplétude de Godel, c'est que pour tout ensemble A d'axiomes qui sont satisfaits par l'interprétation standard de l'addition et de la multiplication sur les entiers naturels, il y a des énoncés E qui sont parfaitement vrais pour notre interprétation standard, mais tels que la formule "A -> E" n'est pas valide, mais seulement cohérente. En d'autres termes, bien que vrai dans l'arithmétique standard, un tel énoncé E n'est pas conséquence logique de nos axiomes. D'une certaine façon, ces axiomes ne sont pas suffisamment "complets" pour caractériser toutes les propriétés logiques de l'arithmétique. Je parle de cela dans cette vidéo : ua-cam.com/video/UlZAatzfRE8/v-deo.html
Concrètement, on ne peut pas réaliser un ensemble A de règles Prolog tel que pour tout énoncé arithmétique E, "A->E" est valide si et seulement si E est mathématiquement vrai dans l'arithmétique standard. C'est même impossible si on s'autorise un ensemble infini, récursivement énumérable, de règles Prolog.
Un énorme Merci. C'est une excellente et très claire explication.
C'est toujours apprécié de trouver du contenu vidéo en supplément lorsqu'on fait une L3 à distance, Merci !
Il faudrait aller beaucoup plus loin que ce genre d'initiative individuelle, et proposer des ressources en ligne sous forme de "briques de connaissances" (vidéos, supports écrits, exercices...) à partir desquelles il serait possible de construire des parcours d'apprentissage cohérents, utilisables par toute personne voulant progresser en autodidacte dans une matière, mais aussi par les enseignants qui pourraient utiliser ces "briques" pour construire des cours, des préparations de cours à faire par les étudiants et des parcours de révisions. Ce serait un énorme travail, mais dont le résultat serait utilisable par des centaines d'enseignants et des milliers d'étudiants chaque année !
Frznchment agréable. Merci beaucoup 😘
Merci beaucoup! Ça permet à mon cerveau d'avoir une vue d'ensemble!
merci, c'est claire et bien expliqué
Bonjour Mr, j'ai bien votre cours. Pourriez vous nous donner une leçon sur le calcul des séquents.
Merci.
Merci Mr
Super merci !
Bonjour Monsieur,
Tout d'abord, je voudrais vous remercier pour la qualité et la clarté de vos différentes présentations. Malgré la difficulté de "rentrer" dans ce monde, c'est véritablement passionnant de vous écouter (et de tenter de bien tout comprendre).
Je me permets de revenir vers vous concernant une question que je me pose et que je vais tenter de résumer maintenant.
Minute 6'28 environ
Sujet : la signature
Vous écrivez: "nos 2 exemples d'interprétations concernent les mêmes symboles fonctionnels et symboles de prédicats...."
Je ne suis pas complètement d'accord dans la mesure où c'est juste leur écriture qui est la même;
on aurait, par exemple, pu (ou "du") écrire "pair1" et "pair2" pour avoir une certaine "clarté".
Dès lors, les signatures seraient bien différentes puisque les significations ne seraient pas les mêmes.
Mon interrogation ne concerne pas simplement cette "précision" qui me semblerait pertinente.
Mon interrogation porte sur l'impact de ma remarque sur votre affirmation suivante concernant "l'infinité d'interprétations possibles"
Dans l'optique de ma remarque cela est évident puisque les significations des termes utilisés peuvent être différentes.
Je soupçonne toutefois, que votre remarque (concernant "l'infinité d'interprétations possibles") est plus ambitieuse.
Ne voulez-vous pas dire, plutôt, qu'il y a une infinité de couples "domaine-signature" possibles, pour une même signature?
Merci d'avance de votre retour, et encore une fois, tous mes remerciements,
Michel Caussanel
Je ne sais pas si je vais réussir à être clair, car c'est un sujet délicat, bien que fondamental et passionnant, qui va au delà de mes enseignements d'initiation. En logique, on distingue deux aspects : l'aspect syntaxique qui concerne la manière dont les formules sont construites, et l'aspect sémantique, qui donne un sens mathématique aux symboles apparaissant dans les formules. Les formules sont des objets mathématiques à part entière : des objets purement syntaxiques, qui peuvent représenter des énoncés mathématiques abstraits grâce au concept d'interprétation.
Mais tout cela a une finalité, une utilisation, qui n'est pas présentée dans cette vidéo, mais dont je parle dans ma vidéo intitulée "Des clés pour comprendre l'indécidabilité et l'incomplétude". Cette utilisation consiste à modéliser un objet mathématique grâce à des axiomes, puis à déduire de ces axiomes, à l'aide de règles d'inférence, des propriétés de cet objet mathématique. Mais en général, un ensemble cohérent d'axiomes a une infinité de modèles, et ce qu'on va démontrer à partir de ces axiomes sera vrai pour une infinité d'interprétations des symboles fonctionnels et relationnels apparaissant dans les axiomes, et pas seulement pour l'objet qu'on a voulu modéliser. Dès qu'on veut modéliser des objets mathématiques ayant la puissance d'expression de l'arithmétique standard (entiers naturels, addition et multiplication) si on décide de donner une interprétation unique aux symboles + (l'addition standard) et x (la multiplication standard), alors il n'existe aucun ensemble fini d'axiomes et même de schémas d'axiomes ayant pour unique modèle cette interprétation standard des symboles fonctionnel + et x. On est donc en quelque sorte "obligé" de considérer que ces symboles ont une infinité d'interprétations, dont celle qui nous intéresse. Ceci est directement lié à la notion d'indécidabilité d'une théorie axiomatique.
Je tente d'expliquer ça dans la vidéo sus-mentionnée, mais je n'en suis pas satisfait, tout comme de cette réponse. Je n'ai pas le temps de faire mieux en ce moment, mais j'aimerais faire une nouvelle vidéo plus claire sur ce sujet.
@@OlivierBailleux Merci beaucoup pour votre rapide retour. Je vais avoir besoin d'un peu de temps pour bien comprendre ce que vous venez de me dire et revoir (plusieurs fois encore) la vidéo à laquelle vous faites référence. L'indécidabilité et l'incomplétude restent encore pour moi des thèmes non maîtrisés, mais la façon dont vous présentez les choses ouvre des pistes d'appropriation des concepts à explorer. Encore merci pour votre travail.