Algorithme de Robinson

L’algorithme de Robinson est un algorithme qui permet de vérifier si une formule logique est vraie ou fausse. Une formule logique est une expression qui utilise des symboles comme des variables, des constantes, des opérateurs logiques (et, ou, non, implique, équivaut) et des quantificateurs (pour tout, il existe). Par exemple, la formule “Pour tout x, il existe y tel que x + y = 0” est une formule logique qui exprime que tout nombre a un opposé. L’algorithme de Robinson consiste à transformer la formule logique en une forme normale conjonctive, c’est-à-dire une conjonction (un et) de clauses, qui sont des disjonctions (un ou) de littéraux, qui sont des variables ou des constantes, éventuellement négées. Par exemple, la formule “(A ou B) et (non A ou C)” est une forme normale conjonctive. Ensuite, l’algorithme de Robinson applique des règles d’inférence pour déduire de nouvelles clauses à partir des clauses existantes, jusqu’à ce qu’il trouve une contradiction ou qu’il n’ait plus de règles applicables. Si l’algorithme trouve une contradiction, cela signifie que la formule logique est fausse. Si l’algorithme n’a plus de règles applicables, cela signifie que la formule logique est vraie.

Imaginez que vous vouliez savoir si une rumeur est vraie ou fausse. Vous avez entendu dire que “Tous les élèves de la classe de 3ème A ont eu 20/20 au contrôle de maths”. Vous pouvez utiliser l’algorithme de Robinson pour vérifier cette rumeur. Voici comment procéder :

• Vous transformez la rumeur en une forme plus simple, en remplaçant les noms des élèves par des lettres. Par exemple, vous pouvez dire que “A, B, C, D et E ont eu 20/20 au contrôle de maths”.
• Vous cherchez des informations qui peuvent confirmer ou infirmer la rumeur. Par exemple, vous pouvez demander à vos amis, regarder les copies, consulter le cahier de notes, etc. Chaque information que vous trouvez est une clause, qui est une affirmation qui peut être vraie ou fausse. Par exemple, vous pouvez trouver les clauses suivantes :
  • “A a eu 20/20 au contrôle de maths” (vraie)
  • “B a eu 18/20 au contrôle de maths” (fausse)
  • “C a eu 20/20 au contrôle de maths” (vraie)
  • “D a eu 19/20 au contrôle de maths” (fausse)
  • “E a eu 20/20 au contrôle de maths” (vraie)
• Vous appliquez des règles de logique pour déduire de nouvelles clauses à partir des clauses existantes. Par exemple, vous pouvez utiliser la règle suivante : si “A et B sont vrais” et “B est faux”, alors “A est faux”. Vous pouvez aussi utiliser la règle suivante : si “A ou B est vrai” et “A est faux”, alors “B est vrai”. Vous pouvez ainsi obtenir les clauses suivantes :
  • “A, B, C, D et E ont eu 20/20 au contrôle de maths” (fausse)
  • “B, D et E ont eu 20/20 au contrôle de maths” (fausse)
  • “D et E ont eu 20/20 au contrôle de maths” (fausse)
  • “E a eu 20/20 au contrôle de maths” (vraie)
• Vous répétez ce processus jusqu’à ce que vous trouviez une contradiction ou que vous n’ayez plus de règles applicables. Si vous trouvez une contradiction, cela signifie que la rumeur est fausse. Si vous n’avez plus de règles applicables, cela signifie que la rumeur est vraie.
• Dans cet exemple, vous trouvez une contradiction, car la clause “E a eu 20/20 au contrôle de maths” est incompatible avec la clause “D et E ont eu 20/20 au contrôle de maths”. Cela signifie que la rumeur est fausse, et que tous les élèves de la classe de 3ème A n’ont pas eu 20/20 au contrôle de maths.

Retourner à l'index du lexique