Pourquoi est l'unification si important pour les moteurs d'inférence?

Question

^{J'apprends automatisé Théorème Proving / SMT solveurs / Assistants de preuve par moi-même et publier une série de questions sur le processus, à partir Unification algorithme .}

• Qu'est-ce et pourquoi il est si important de Inference moteurs ?
• Pourquoi est-il si important à l'informatique?

Answer 1

L'unification est un concept fondamental dans la science informatique qui peut-être à temps, nous prenons même pour acquis. Chaque fois que nous avons une règle ou équation ou modèle et que vous souhaitez appliquer à certaines données, l'unification est utilisée pour spécialiser la règle aux données. Ou si l'on veut combiner deux règles générales mais qui se chevauchent, l'unification nous donne la règle la plus générale mixte. Unification est au cœur de

• et les assistants prouveurs de théorèmes preuve, comprennent certains sont basés sur l'unification d'ordre supérieur.
• implémentations Prolog (comme la résolution).
• algorithmes d'inférence de type.
• linguistique informatique / traitement du langage naturel.
• systèmes de réécriture tels que Maude, qui peut être utilisé comme base de la programmation sémantique du langage.
• BDD.
• Les systèmes experts ou plus généralement l'intelligence artificielle.
• systèmes d'algèbre informatique.
• correspondance de motifs dans les langages fonctionnels (au moins en partie ... correspondant uniquement).
• Certains parsing approche.
• Certains langages de requête, impliquant notamment le Web sémantique.

Answer 2

Assistants de preuve tels que le travail Isabelle / HOL au niveau syntactique sur un calcul logique. Imaginez que vous avez modus ponens règle (MP)

$ \ qquad \ displaystyle P \ Q, P \ \ Longrightarrow \ Q $

et l'objectif preuve

$ \ qquad \ displaystyle (a \ b Lor) \ à (c \ terre d), a \ b lor \ \ {overset!} {\ Longrightarrow} c \ terre d $

Nous, les humains voir immédiatement que cette suite avec modus ponens, mais la machine doit correspondre objectif à la règle syntaxiquement (Que vous faites apply rule mp ou apply simp), ce qui est ce que l'unification fait. L'algorithme trouve $ \ varphi $ à $ \ phi (P) = a \ lor b $ et $ \ varphi (Q) = c \ terre d $, instancie la règle et l'applique.

La bonne chose au sujet des méthodes d'assistants comme simp est maintenant que si votre objectif est

$ \ qquad \ displaystyle (a \ b Lor) \ à (c \ terre d), un \ \ {overset!} {\ Longrightarrow} $ d

qu'ils trouveront une séquence appropriée des applications de règles MP, $ P \ terre Q \ Longrightarrow P $ et $ P \ Longrightarrow P \ lor Q $ avec unifications compatibles pour les étapes respectives et résoudre le but.

---

Notation: Avec $ \ Gamma = \ {\ varphi_1, \ points, \ varphi_n \} $ un ensemble de formules logiques, la notation

$ \ qquad \ Gamma \ Longrightarrow \ psi $

signifie ce qui suit:

  

Si j'ai dérivé / prouvé toutes les formules de $ \ Gamma $ (à savoir qu'ils sont valide ), alors cette règle affirme que $ \ psi $ est valide.

Dans un sens, la règle $ \ Gamma \ Longrightarrow de $ de psi est la dernière étape dans un (long) pour preuve $ \ psi $. Ne sont que des preuves chaînes de ces applications règle.

Notez que règles contiennent généralement des variables schématiques ($ P $ et $ Q $ dans le ci-dessus) qui peuvent être remplacés par arbitraire formules aussi longtemps que la même variable est remplacé par la même formule dans tous les cas; le résultat de ce format est l'instance de règle de béton (ou de manière intuitive, une étape de la preuve). Ce remplacement est ci-dessus notée $ \ varphi $ qui a été trouvé par l'unification.

Souvent, les gens utilisent \ $ modèles $ au lieu de $ \ Longrightarrow $.

Answer 3

Je ne pense pas qu'il est important de moteurs d'inférence . L'algorithme d'unification est cependant très utile pour les inférence de type . Ce sont deux types d'inférence très différentes.

L'inférence de type est important à l'informatique parce que types sont importants dans la théorie des langages de programmation, ce qui est une partie importante de la science informatique. Les types sont également proches de la logique et sont utilisés de façon intensive dans démonstration automatique. Il existe des implémentations des algorithmes d'unification dans un grand nombre, sinon tous, assistants de preuve et solveurs SMT.

moteurs Inference sont liés à l'intelligence artificielle, ce qui est également important, mais très différent. (Je l'ai vu des liens entre l'apprentissage et la logique, mais cela semble tiré par les cheveux.)