@prefix rdf: . @prefix yago: . rdf:type yago:WikicatRewritingSystems , yago:Object100002684 . @prefix dbo: . rdf:type dbo:Election , yago:Whole100003553 , yago:System104377057 , yago:PhysicalEntity100001930 , yago:Instrumentality103575240 , yago:Artifact100021939 . @prefix rdfs: . rdfs:label "\u5408\u4E00"@zh , "\u0423\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F (\u0456\u043D\u0444\u043E\u0440\u043C\u0430\u0442\u0438\u043A\u0430)"@uk , "Unificaci\u00F3n (ciencias de la computaci\u00F3n)"@es , "Unifikacja (informatyka)"@pl , "Unifica\u00E7\u00E3o"@pt , "Unification"@fr , "\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3"@ja , "Unifikace (logika)"@cs , "Unification (computer science)"@en , "Unifikation (Logik)"@de , "\u0427\u0430\u0441\u0442\u043D\u044B\u0439 \u0441\u043B\u0443\u0447\u0430\u0439 \u0444\u043E\u0440\u043C\u0443\u043B\u044B"@ru ; rdfs:comment "\u0415\u0441\u043B\u0438 \u0432 \u0444\u043E\u0440\u043C\u0443\u043B\u0443 \u0432\u043C\u0435\u0441\u0442\u043E \u043F\u0435\u0440\u0435\u043C\u0435\u043D\u043D\u044B\u0445 \u043F\u043E\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044C \u0441\u043E\u043E\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043D\u043D\u043E \u0444\u043E\u0440\u043C\u0443\u043B\u044B \u0442\u043E \u043F\u043E\u043B\u0443\u0447\u0438\u0442\u0441\u044F \u0444\u043E\u0440\u043C\u0443\u043B\u0430 , \u043A\u043E\u0442\u043E\u0440\u0430\u044F \u043D\u0430\u0437\u044B\u0432\u0430\u0435\u0442\u0441\u044F \u0447\u0430\u0441\u0442\u043D\u044B\u043C \u0441\u043B\u0443\u0447\u0430\u0435\u043C \u0444\u043E\u0440\u043C\u0443\u043B\u044B : \u041A\u0430\u0436\u0434\u0430\u044F \u0444\u043E\u0440\u043C\u0443\u043B\u0430 \u043F\u043E\u0434\u0441\u0442\u0430\u0432\u043B\u044F\u0435\u0442\u0441\u044F \u0432\u043C\u0435\u0441\u0442\u043E \u0432\u0441\u0435\u0445 \u0432\u0445\u043E\u0436\u0434\u0435\u043D\u0438\u0439 \u043F\u0435\u0440\u0435\u043C\u0435\u043D\u043D\u043E\u0439 . \u041D\u0430\u0431\u043E\u0440 \u043F\u043E\u0434\u0441\u0442\u0430\u043D\u043E\u0432\u043E\u043A \u043D\u0430\u0437\u044B\u0432\u0430\u0435\u0442\u0441\u044F \u0443\u043D\u0438\u0444\u0438\u043A\u0430\u0442\u043E\u0440\u043E\u043C."@ru , "En l\u00F3gica y en ciencias de la computaci\u00F3n, la unificaci\u00F3n es un proceso algor\u00EDtmico para resoluci\u00F3n de ecuaciones con expresiones simb\u00F3licas. Se pueden determinar diferentes esquemas de unificaci\u00F3n dependiendo de: qu\u00E9 expresiones (tambi\u00E9n llamadas t\u00E9rminos) est\u00E1n permitidas en un conjunto de ecuaciones (tambi\u00E9n llamado problema de unificaci\u00F3n), y de cu\u00E1les expresiones son consideradas hom\u00F3logas. Si variables de orden superior, esto es, variables que representan funciones, son permitidas en una expresi\u00F3n, el proceso es llamado unificaci\u00F3n de orden superior, si no se llama unificaci\u00F3n de primer orden. Si una soluci\u00F3n requiere hacer ambos lados de cada ecuaci\u00F3n literalmente iguales entonces el proceso se llama sint\u00E1ctico o unificaci\u00F3n libre, de lo contrario sem\u00E1ntico o unificaci\u00F3n ecuacional,"@es , "Unifikacja (ang. unification) \u2013 operacja na dw\u00F3ch lub wi\u0119cej drzewach, kt\u00F3ra znajduje takie przyporz\u0105dkowanie zmiennych, \u017Ce drzewa te s\u0105 r\u00F3wne. Np. (w notacji lispowej): (+ x 2) i (+ (+ z 7) y) s\u0105 unifikowalne dla y=2 i x=(+ z 7). (+ x 2) i (+ y 3) nie s\u0105 unifikowalne. Podobnie unifikowalne nie s\u0105 (* x 2) i (+ x x) ani (+ 2 3) i (+ 3 2) \u2013 unifikacja dotyczy tylko symboli, a nie ich znaczenia. Unifikator to wygenerowany w ten spos\u00F3b zbi\u00F3r przyporz\u0105dkowa\u0144. Algorytm wygl\u0105da tak:"@pl , "En informatique et en logique, l'unification est un processus algorithmique qui, \u00E9tant donn\u00E9s deux termes, trouve une substitution qui appliqu\u00E9e aux deux termes les rend identiques. Par exemple, et peuvent \u00EAtre rendus identiques par la substitution et , qui donne quand on l'applique \u00E0 chacun de ces termes le terme . Dit autrement, l'unification est la r\u00E9solution d'une \u00E9quation dans l'alg\u00E8bre des termes (unification syntaxique) ou dans une alg\u00E8bre quotient par un ensemble d'identit\u00E9s (unification modulo une th\u00E9orie) ; la solution de l'\u00E9quation est la substitution qui rend les deux termes identiques et que l'on appelle l'unificateur.L'unification a des applications en inf\u00E9rence de types, programmation logique, en d\u00E9monstration automatique de th\u00E9or\u00E8mes, en syst\u00E8me de r\u00E9\u00E9criture, en traitem"@fr , "\u0423\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u0432 \u043B\u043E\u0433\u0456\u0446\u0456 \u0442\u0430 \u0456\u043D\u0444\u043E\u0440\u043C\u0430\u0442\u0438\u0446\u0456 \u2014 \u0446\u0435 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0456\u0447\u043D\u0438\u0439 \u043F\u0440\u043E\u0446\u0435\u0441 \u0440\u043E\u0437\u0432'\u044F\u0437\u0430\u043D\u043D\u044F \u0440\u0456\u0432\u043D\u044F\u043D\u044C \u043C\u0456\u0436 \u0441\u0438\u043C\u0432\u043E\u043B\u0456\u0447\u043D\u0438\u043C\u0438 . \u0417\u0430\u043B\u0435\u0436\u043D\u043E \u0432\u0456\u0434 \u0442\u043E\u0433\u043E, \u044F\u043A\u0438\u043C \u0432\u0438\u0440\u0430\u0437\u0430\u043C (\u0442\u0435\u0440\u043C\u0430\u043C) \u0434\u043E\u0437\u0432\u043E\u043B\u0435\u043D\u043E \u0437'\u044F\u0432\u043B\u044F\u0442\u0438\u0441\u044C \u0432 \u043D\u0430\u0431\u043E\u0440\u0456 \u0440\u0456\u0432\u043D\u044F\u043D\u044C (\u0442\u0430\u043A\u043E\u0436 \u043D\u0430\u0437\u0438\u0432\u0430\u0454\u0442\u044C\u0441\u044F \u043F\u0440\u043E\u0431\u043B\u0435\u043C\u043E\u044E \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457), \u0456 \u044F\u043A\u0456 \u0432\u0438\u0440\u0430\u0437\u0438 \u0432\u0432\u0430\u0436\u0430\u044E\u0442\u044C\u0441\u044F \u0440\u0456\u0432\u043D\u0438\u043C\u0438, \u0432\u0438\u0434\u0456\u043B\u044F\u044E\u0442\u044C \u043A\u0456\u043B\u044C\u043A\u0430 \u0441\u0442\u0440\u0443\u043A\u0442\u0443\u0440 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457. \u042F\u043A\u0449\u043E \u0443 \u0432\u0438\u0440\u0430\u0437\u0456 \u0434\u043E\u043F\u0443\u0441\u043A\u0430\u044E\u0442\u044C\u0441\u044F \u0437\u043C\u0456\u043D\u043D\u0456 \u0432\u0438\u0449\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443, \u0442\u043E\u0431\u0442\u043E \u0437\u043C\u0456\u043D\u043D\u0456, \u0449\u043E \u043F\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043B\u044F\u044E\u0442\u044C \u0444\u0443\u043D\u043A\u0446\u0456\u0457, \u043F\u0440\u043E\u0446\u0435\u0441 \u043D\u0430\u0437\u0438\u0432\u0430\u0454\u0442\u044C\u0441\u044F \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u0432\u0438\u0449\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443, \u0456\u043D\u0430\u043A\u0448\u0435, \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443. \u042F\u043A\u0449\u043E \u043F\u043E\u0442\u0440\u0456\u0431\u043D\u043E, \u0449\u043E\u0431 \u043E\u0431\u0438\u0434\u0432\u0456 \u0441\u0442\u043E\u0440\u043E\u043D\u0438 \u043A\u043E\u0436\u043D\u043E\u0433\u043E \u0440\u0456\u0432\u043D\u044F\u043D\u043D\u044F \u0431\u0443\u043B\u0438 \u0431\u0443\u043A\u0432\u0430\u043B\u044C\u043D\u043E \u0440\u0456\u0432\u043D\u0438\u043C\u0438, \u0446\u0435\u0439 \u043F\u0440\u043E\u0446\u0435\u0441 \u043D\u0430\u0437\u0438\u0432\u0430\u0454\u0442\u044C\u0441\u044F \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u043D\u0438\u043C \u0430\u0431\u043E \u0432\u0456\u043B\u044C\u043D\u0438\u043C \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F, \u0432 \u0456\u043D\u0448\u043E\u043C\u0443 \u0432\u0438\u043F\u0430\u0434\u043A\u0443 \u2014 \u0441\u0435\u043C\u0430\u043D\u0442\u0438\u0447\u043D\u0435 \u0430\u0431\u043E \u0440\u0456\u0432\u043D\u043E\u043F\u0440\u0430\u0432\u043D\u0430 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F, \u0430\u0431\u043E \u0415-\u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u0430\u0431\u043E \u0442\u0435\u043E\u0440\u0456\u044F \u043C\u043E\u0434\u0443\u043B\u0456\u0432 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457."@uk , "In logic and computer science, unification is an algorithmic process of solving equations between symbolic expressions. Depending on which expressions (also called terms) are allowed to occur in an equation set (also called unification problem), and which expressions are considered equal, several frameworks of unification are distinguished. If higher-order variables, that is, variables representing functions, are allowed in an expression, the process is called higher-order unification, otherwise first-order unification. If a solution is required to make both sides of each equation literally equal, the process is called syntactic or free unification, otherwise semantic or equational unification, or E-unification, or unification modulo theory."@en , "\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\uFF08\u82F1: unification\uFF09\u306F\u6570\u7406\u8AD6\u7406\u5B66\u3084\u8A08\u7B97\u6A5F\u79D1\u5B66\u306E\u7528\u8A9E\u3067\u3042\u308A\u3001\u554F\u984C\u3092\u89E3\u304F\u969B\u306E\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u7684\u30D7\u30ED\u30BB\u30B9\u3067\u3042\u308B\u3002\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u306F\u3001\u898B\u305F\u76EE\u306E\u7570\u306A\u308B2\u3064\u306E\u304C\u540C\u4E00\u307E\u305F\u306F\u540C\u7B49\u3067\u3042\u308B\u3053\u3068\u3092\u793A\u3059\u3092\u6C42\u3081\u308B\u306E\u304C\u76EE\u7684\u3067\u3042\u308B\u3002\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u306F\u81EA\u52D5\u63A8\u8AD6\u3001\u8AD6\u7406\u30D7\u30ED\u30B0\u30E9\u30DF\u30F3\u30B0\u3001\u30D7\u30ED\u30B0\u30E9\u30DF\u30F3\u30B0\u8A00\u8A9E\u306E\u578B\u30B7\u30B9\u30C6\u30E0\u306E\u5B9F\u88C5\u306A\u3069\u306B\u5E45\u5E83\u304F\u7528\u3044\u3089\u308C\u3066\u3044\u308B\u3002 \u306A\u304A\u3001\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u3092\u5358\u4E00\u5316\u3042\u308B\u3044\u306F\u7D71\u4E00\u5316\u3068\u3082\u547C\u3076\u3002 \u4E3B\u306A\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u306F\u6570\u7A2E\u985E\u3042\u308B\u3002\u7B49\u53F7\u3092\u6301\u305F\u306A\u3044\u8AD6\u7406\uFF08\u7406\u8AD6\uFF09\u306B\u304A\u3044\u3066\u30012\u3064\u306E\u9805\u304C\u540C\u4E00\u3067\u3042\u308B\u3053\u3068\u3092\u793A\u3059\u305F\u3081\u306E\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u306F\u7D71\u8A9E\u8AD6\u7684\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u3068\u547C\u3070\u308C\u308B\u3002\u7A7A\u3067\u306A\u3044\u7B49\u53F7\u3092\u6301\u3064\u8AD6\u7406\uFF08\u7406\u8AD6\uFF09\u30672\u3064\u306E\u9805\u306E\u540C\u7B49\u6027\u3092\u793A\u3059\u5834\u5408\u3001\u305D\u308C\u3092\u610F\u5473\u8AD6\u7684\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u3068\u547C\u3076\u3002\u7F6E\u63DB\u306F\u9806\u5E8F\u96C6\u5408\u3068\u3057\u3066\u9806\u5E8F\u4ED8\u3051\u3089\u308C\u308B\u306E\u3067\u3001\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u306F\u675F\u306B\u304A\u3051\u308B\u7D50\u3073\u3092\u6C42\u3081\u308B\u624B\u7D9A\u304D\u3068\u3057\u3066\u89E3\u91C8\u3067\u304D\u308B\u3002 \u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u306F\u30B8\u30E3\u30C3\u30AF\u30FB\u30A8\u30EB\u30D6\u30E9\u30F3\u306B\u3088\u3063\u3066\u6700\u521D\u306B\u767A\u898B\u3055\u308C\u305F\u304C\u3001\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u3092\u521D\u3081\u3066\u5F62\u5F0F\u7684\u306B\u7814\u7A76\u3057\u305F\u306E\u306F\u3067\u3001\u4E00\u968E\u8FF0\u8A9E\u8AD6\u7406\u306E\u5C0E\u51FA\u624B\u7D9A\u304D\u3092\u69CB\u7BC9\u3059\u308B\u969B\u306B\u4E00\u968E\u306E\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u3092\u57FA\u76E4\u3068\u3057\u3066\u4F7F\u3044\u3001\u7D44\u5408\u305B\u7206\u767A\u306E\u539F\u56E0\u306E1\u3064\uFF08\u9805\u3092\u4F8B\u5316\u3057\u305F\u3082\u306E\u306E\u63A2\u7D22\uFF09\u3092\u6392\u9664\u3059\u308B\u3053\u3068\u3067\u81EA\u52D5\u63A8\u8AD6\u6280\u8853\u3078\u306E\u5927\u304D\u306A\u4E00\u6B69\u3068\u3057\u305F\u3002"@ja , "Unifica\u00E7\u00E3o, em ci\u00EAncia da computa\u00E7\u00E3o e na l\u00F3gica, \u00E9 um processo algor\u00EDtmico de solu\u00E7\u00E3o de equa\u00E7\u00F5es entre express\u00F5es simb\u00F3licas. Dependendo de quais express\u00F5es (tamb\u00E9m chamadas de termos) s\u00E3o permitidas ocorrer em um conjunto de equa\u00E7\u00F5es (tamb\u00E9m chamado de problema da unifica\u00E7\u00E3o), e quais express\u00F5es s\u00E3o consideradas iguais, diversas estruturas de unifica\u00E7\u00E3o s\u00E3o distinguidas. Se vari\u00E1veis de alta ordem, isto \u00E9, vari\u00E1veis que representam fun\u00E7\u00F5es, s\u00E3o permitidas em uma express\u00E3o, o processo \u00E9 chamado de unifica\u00E7\u00E3o de alta ordem, ou, caso contr\u00E1rio, \u00E9 chamado de unifica\u00E7\u00E3o de primeira ordem. Se exige-se uma solu\u00E7\u00E3o que fa\u00E7a com que ambos os lados de cada equa\u00E7\u00E3o sejam literalmente iguais, o processo \u00E9 chamado de unifica\u00E7\u00E3o sint\u00E1tica, ou, caso contr\u00E1rio, unifica\u00E7\u00E3o sem\u00E2ntica, ou unifica\u00E7\u00E3o equac"@pt , "\u5728\u6570\u7406\u903B\u8F91\u4E2D\uFF0C\u7279\u522B\u662F\u5E94\u7528\u4E8E\u8BA1\u7B97\u673A\u79D1\u5B66\u4E2D\uFF0C\u4E24\u4E2A\u9879\u7684\u540C\u4E00\u662F\u5C31\u7279\u6B8A\u5316\u6B21\u5E8F\u800C\u8A00\u7684\u5E76(\u683C\u7684\u6700\u5C0F\u4E0A\u754C), \u5C31\u662F\u8BF4\uFF0C\u6211\u4EEC\u5728\u9879\u7684\u96C6\u5408\u4E0A\u5047\u5B9A\u4E00\u4E2A\u9884\u5E8F\uFF0C\u5176\u4E2D t* \u2264 t \u610F\u5473\u7740 t* \u662F\u901A\u8FC7\u4EE3\u6362(substitute)\u5728 t \u4E2D\u67D0\u4E9B\u9879\u7684\u4E00\u4E2A\u6216\u591A\u4E2A\u81EA\u7531\u53D8\u91CF\u800C\u4ECE t \u83B7\u5F97\u7684\u3002s \u548C t \u7684\u540C\u4E00 u\uFF0C\u5982\u679C\u5B58\u5728\u7684\u8BDD\uFF0C\u662F s \u548C t \u4E8C\u8005\u7684\u4EE3\u6362\u5B9E\u4F8B\u7684\u4E00\u4E2A\u9879\u3002s \u548C t \u7684\u4EFB\u4F55\u516C\u5171\u7684\u4EE3\u6362\u5B9E\u4F8B\u4E5F\u662F u \u7684\u5B9E\u4F8B\u3002 \u4F8B\u5982\uFF0C\u5BF9\u4E8E\u591A\u9879\u5F0F X2 \u548C Y3 \u53EF\u4EE5\u901A\u8FC7\u91C7\u7EB3 X = Z3 \u548C Y = Z2 \u800C\u540C\u4E00\u5230 Z6\u3002"@zh , "Unifikation ist eine Methode zur Vereinheitlichung pr\u00E4dikatenlogischer Ausdr\u00FCcke. Zwei Ausdr\u00FCcke werden unifiziert, indem ihre Variablen so durch geeignete Terme ersetzt werden, dass die resultierenden Ausdr\u00FCcke gleich sind. Die Unifikation hat insbesondere in der Computerlogik und Computerlinguistik eine gr\u00F6\u00DFere Bedeutung erlangt. So nutzt etwa die Inferenzmaschine des Prolog-Interpreters Unifikation. In der Computerlinguistik gibt es sogenannte Unifikationsgrammatiken, die sich auf dieses Konzept st\u00FCtzen. Auch beim Theorembeweisen spielt Unifikation eine gro\u00DFe Rolle."@de , "Unifikace je v logice , po jej\u00ED\u017E aplikaci na mno\u017Einu term\u016F dostaneme jeden term. Form\u00E1ln\u011B, je-li a t a s dva termy, je substituce jejich unifikac\u00ED, pokud .Algoritmus unifikace term\u016F predik\u00E1tov\u00E9 logiky byl poprv\u00E9 formulov\u00E1n Alanem Robinsonem v roce 1965 a pou\u017Eit pro rezoluci v predik\u00E1tov\u00E9 logice. Pou\u017E\u00EDv\u00E1 se nap\u0159\u00EDklad v unifika\u010Dn\u00EDch gramatik\u00E1ch."@cs . @prefix foaf: . foaf:depiction , , . @prefix dcterms: . @prefix dbc: . dcterms:subject dbc:Rewriting_systems , dbc:Automated_theorem_proving , dbc:Logic_programming , , dbc:Type_theory , dbc:Logic_in_computer_science ; dbo:wikiPageID 54432 ; dbo:wikiPageRevisionID 1105017744 ; dbo:wikiPageWikiLink . @prefix dbr: . dbo:wikiPageWikiLink dbr:Finite_terms , dbr:Lambda_calculus , dbr:Computer_science , dbr:Overloading_in_programming_languages , dbr:Conor_McBride , dbr:Postfix_notation , , , dbr:Undecidable_problem , dbr:Semantic_equivalence , dbr:Subsumption_lattice , , dbr:Jean-Pierre_Jouannaud , dbr:Nachum_Dershowitz , dbr:Free_theory , , dbr:Alpha_equivalent , dbr:Jacques_Herbrand , , dbr:Ontology_alignment , dbr:First-order_terms , dbr:Semi-decidable , , dbr:Gilles_Dowek , dbr:Convergent_term_rewriting_system , dbr:Dependently_typed , dbr:Congruence_closure , dbr:Prolog , dbr:Franz_Baader , dbr:Identity_function , , dbr:Occurs_check , , , , dbr:Cryptographic_protocol , dbr:Explicit_substitution , dbr:Syntactic_unification , dbr:Syntactically_unifying , dbr:Type_system , , dbr:Free_object , dbr:Elliptical_construction , dbr:Jan_van_Leeuwen , dbr:LambdaProlog , dbr:Equation_solving , dbr:Equations , dbc:Rewriting_systems , dbr:Boolean_ring , , dbr:Equation , dbr:Logic_programming , , dbr:Rewriting , dbr:Handbook_of_Theoretical_Computer_Science , dbr:Term_rewriting , dbr:Commutative_ring , dbr:Power_set , , dbr:Directed_acyclic_graph , dbr:Empty_theory , dbr:Algebraic_specification , dbr:Twelf , dbr:Admissible_rule , dbr:Algorithms , dbr:Solving_equations , dbr:Abelian_group , dbr:Andrei_Voronkov , , , dbr:Lambda_terms , dbr:Type_inference , dbr:Christoph_Walther , dbr:Equivalence_relation , dbr:Uninterpreted_function , , , dbr:Equalities , , dbr:Semigroup , dbr:SMT_solver , dbr:First-order_logic , dbr:Order-sorted_logic , dbr:Handbook_of_Automated_Reasoning , dbr:Renamed_copy , , dbr:Recursive_on_the_number_of_variables , dbr:Idempotent , dbr:Lambda-term_bound_variables , dbc:Automated_theorem_proving , dbr:Automated_reasoning , dbc:Logic_programming , dbr:Wayne_Snyder , dbr:Commutative , dbr:Commutative_property , , dbr:Logic , , dbr:Lexicographically , , dbr:Cons , dbr:Associative , dbr:Subterm , , dbr:Modal_algebra , , dbr:Subterms , dbr:Lexicographical_order , dbr:Parametric_polymorphism , , dbr:Feature_structure , dbr:Tobias_Nipkow , dbc:Type_theory , dbr:Arities , dbc:Logic_in_computer_science , dbr:Kripke_semantics , dbr:John_Alan_Robinson , dbr:Constant_function ; dbo:wikiPageExternalLink , , , , , , , . @prefix owl: . owl:sameAs , , , . @prefix dbpedia-no: . owl:sameAs dbpedia-no:Unifikasjon , , , , . @prefix dbpedia-fr: . owl:sameAs dbpedia-fr:Unification , , . @prefix wikidata: . owl:sameAs wikidata:Q609057 , , , , , , , . @prefix dbp: . @prefix dbt: . dbp:wikiPageUsesTemplate dbt:Mvar , , , dbt:Reflist , dbt:Refn , dbt:Dead_link , dbt:Quote_box , dbt:Tmath , dbt:Main , dbt:Underset , dbt:Ill , dbt:Prime , , dbt:Mset , dbt:Webarchive , dbt:Pipe , dbt:Cite_journal , dbt:Expand_section , dbt:Cite_book , dbt:Color , dbt:Hidden_end , dbt:Hidden_begin , dbt:Math ; dbo:thumbnail . @prefix xsd: . dbp:date "2015-06-08"^^xsd:date ; dbp:quote "Symbols are ordered such that variables precede function symbols.\nTerms are ordered by increasing written length; equally long terms \nare ordered lexicographically. For a set T of terms, its disagreement \npath p is the lexicographically least path where two member terms \nof T differ. Its disagreement set is the set of subterms starting at p, \nformally: }.\n\nAlgorithm:"@en ; dbp:title "Robinson's 1965 unification algorithm"@en ; dbp:url ; dbo:abstract "Unifikacja (ang. unification) \u2013 operacja na dw\u00F3ch lub wi\u0119cej drzewach, kt\u00F3ra znajduje takie przyporz\u0105dkowanie zmiennych, \u017Ce drzewa te s\u0105 r\u00F3wne. Np. (w notacji lispowej): (+ x 2) i (+ (+ z 7) y) s\u0105 unifikowalne dla y=2 i x=(+ z 7). (+ x 2) i (+ y 3) nie s\u0105 unifikowalne. Podobnie unifikowalne nie s\u0105 (* x 2) i (+ x x) ani (+ 2 3) i (+ 3 2) \u2013 unifikacja dotyczy tylko symboli, a nie ich znaczenia. Unifikator to wygenerowany w ten spos\u00F3b zbi\u00F3r przyporz\u0105dkowa\u0144. Algorytm wygl\u0105da tak: \n* je\u015Bli po jednej stronie jest zmienna, dorzucamy j\u0105 do unifikatora i zamieniamy wszystkie jej wyst\u0105pienia na to co wyst\u0119puje po drugiej stronie. Nale\u017Cy zaj\u0105\u0107 si\u0119 te\u017C przypadkiem szczeg\u00F3lnym, kiedy druga strona zawiera wyst\u0105pienie tej zmiennej \u2013 zale\u017Cnie od implementacji x i (+ x 1) mog\u0105 si\u0119 unifikowa\u0107, nie unifikowa\u0107, b\u0105d\u017A te\u017C powodowa\u0107 niezamierzone zap\u0119tlenie. \n* je\u015Bli po obu stronach s\u0105 te same sta\u0142e, unifikacja si\u0119 powiod\u0142a \n* je\u015Bli po obu stronach s\u0105 te same relacje n-arne, unifikacja si\u0119 powiod\u0142a o ile powiod\u0142a si\u0119 unifikacja wszystkich n-poddrzew, przy czym unifikator dotyczy wszystkich poddrzew. \n* je\u015Bli po obu stronach s\u0105 r\u00F3\u017Cne sta\u0142e b\u0105d\u017A relacje, unifikacja si\u0119 nie powiod\u0142a."@pl , "Unifikace je v logice , po jej\u00ED\u017E aplikaci na mno\u017Einu term\u016F dostaneme jeden term. Form\u00E1ln\u011B, je-li a t a s dva termy, je substituce jejich unifikac\u00ED, pokud .Algoritmus unifikace term\u016F predik\u00E1tov\u00E9 logiky byl poprv\u00E9 formulov\u00E1n Alanem Robinsonem v roce 1965 a pou\u017Eit pro rezoluci v predik\u00E1tov\u00E9 logice. Pou\u017E\u00EDv\u00E1 se nap\u0159\u00EDklad v unifika\u010Dn\u00EDch gramatik\u00E1ch."@cs , "\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\uFF08\u82F1: unification\uFF09\u306F\u6570\u7406\u8AD6\u7406\u5B66\u3084\u8A08\u7B97\u6A5F\u79D1\u5B66\u306E\u7528\u8A9E\u3067\u3042\u308A\u3001\u554F\u984C\u3092\u89E3\u304F\u969B\u306E\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u7684\u30D7\u30ED\u30BB\u30B9\u3067\u3042\u308B\u3002\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u306F\u3001\u898B\u305F\u76EE\u306E\u7570\u306A\u308B2\u3064\u306E\u304C\u540C\u4E00\u307E\u305F\u306F\u540C\u7B49\u3067\u3042\u308B\u3053\u3068\u3092\u793A\u3059\u3092\u6C42\u3081\u308B\u306E\u304C\u76EE\u7684\u3067\u3042\u308B\u3002\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u306F\u81EA\u52D5\u63A8\u8AD6\u3001\u8AD6\u7406\u30D7\u30ED\u30B0\u30E9\u30DF\u30F3\u30B0\u3001\u30D7\u30ED\u30B0\u30E9\u30DF\u30F3\u30B0\u8A00\u8A9E\u306E\u578B\u30B7\u30B9\u30C6\u30E0\u306E\u5B9F\u88C5\u306A\u3069\u306B\u5E45\u5E83\u304F\u7528\u3044\u3089\u308C\u3066\u3044\u308B\u3002 \u306A\u304A\u3001\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u3092\u5358\u4E00\u5316\u3042\u308B\u3044\u306F\u7D71\u4E00\u5316\u3068\u3082\u547C\u3076\u3002 \u4E3B\u306A\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u306F\u6570\u7A2E\u985E\u3042\u308B\u3002\u7B49\u53F7\u3092\u6301\u305F\u306A\u3044\u8AD6\u7406\uFF08\u7406\u8AD6\uFF09\u306B\u304A\u3044\u3066\u30012\u3064\u306E\u9805\u304C\u540C\u4E00\u3067\u3042\u308B\u3053\u3068\u3092\u793A\u3059\u305F\u3081\u306E\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u306F\u7D71\u8A9E\u8AD6\u7684\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u3068\u547C\u3070\u308C\u308B\u3002\u7A7A\u3067\u306A\u3044\u7B49\u53F7\u3092\u6301\u3064\u8AD6\u7406\uFF08\u7406\u8AD6\uFF09\u30672\u3064\u306E\u9805\u306E\u540C\u7B49\u6027\u3092\u793A\u3059\u5834\u5408\u3001\u305D\u308C\u3092\u610F\u5473\u8AD6\u7684\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u3068\u547C\u3076\u3002\u7F6E\u63DB\u306F\u9806\u5E8F\u96C6\u5408\u3068\u3057\u3066\u9806\u5E8F\u4ED8\u3051\u3089\u308C\u308B\u306E\u3067\u3001\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u306F\u675F\u306B\u304A\u3051\u308B\u7D50\u3073\u3092\u6C42\u3081\u308B\u624B\u7D9A\u304D\u3068\u3057\u3066\u89E3\u91C8\u3067\u304D\u308B\u3002 \u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u306F\u30B8\u30E3\u30C3\u30AF\u30FB\u30A8\u30EB\u30D6\u30E9\u30F3\u306B\u3088\u3063\u3066\u6700\u521D\u306B\u767A\u898B\u3055\u308C\u305F\u304C\u3001\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u3092\u521D\u3081\u3066\u5F62\u5F0F\u7684\u306B\u7814\u7A76\u3057\u305F\u306E\u306F\u3067\u3001\u4E00\u968E\u8FF0\u8A9E\u8AD6\u7406\u306E\u5C0E\u51FA\u624B\u7D9A\u304D\u3092\u69CB\u7BC9\u3059\u308B\u969B\u306B\u4E00\u968E\u306E\u30E6\u30CB\u30D5\u30A3\u30B1\u30FC\u30B7\u30E7\u30F3\u3092\u57FA\u76E4\u3068\u3057\u3066\u4F7F\u3044\u3001\u7D44\u5408\u305B\u7206\u767A\u306E\u539F\u56E0\u306E1\u3064\uFF08\u9805\u3092\u4F8B\u5316\u3057\u305F\u3082\u306E\u306E\u63A2\u7D22\uFF09\u3092\u6392\u9664\u3059\u308B\u3053\u3068\u3067\u81EA\u52D5\u63A8\u8AD6\u6280\u8853\u3078\u306E\u5927\u304D\u306A\u4E00\u6B69\u3068\u3057\u305F\u3002"@ja , "En l\u00F3gica y en ciencias de la computaci\u00F3n, la unificaci\u00F3n es un proceso algor\u00EDtmico para resoluci\u00F3n de ecuaciones con expresiones simb\u00F3licas. Se pueden determinar diferentes esquemas de unificaci\u00F3n dependiendo de: qu\u00E9 expresiones (tambi\u00E9n llamadas t\u00E9rminos) est\u00E1n permitidas en un conjunto de ecuaciones (tambi\u00E9n llamado problema de unificaci\u00F3n), y de cu\u00E1les expresiones son consideradas hom\u00F3logas. Si variables de orden superior, esto es, variables que representan funciones, son permitidas en una expresi\u00F3n, el proceso es llamado unificaci\u00F3n de orden superior, si no se llama unificaci\u00F3n de primer orden. Si una soluci\u00F3n requiere hacer ambos lados de cada ecuaci\u00F3n literalmente iguales entonces el proceso se llama sint\u00E1ctico o unificaci\u00F3n libre, de lo contrario sem\u00E1ntico o unificaci\u00F3n ecuacional, o E-Unificaci\u00F3n o teor\u00EDa de unificaci\u00F3n modular. Una soluci\u00F3n de un problema de unificaci\u00F3n se denota como una , esto es, un mapeo asignando un valor simb\u00F3lico a cada una de las variables en las expresiones del problema. Un algoritmo de unificaci\u00F3n debe calcular un conjunto de sustituciones completo y m\u00EDnimo para un problema dado; esto es, un conjunto que cubra todas las soluciones y que no contenga miembros redundantes. De acuerdo con el marco de referencia, un conjunto de sustituciones completo y m\u00EDnimo puede que tenga a lo m\u00E1s un miembro, a lo sumo una cantidad finita, o posiblemente infinito n\u00FAmero de miembros, o no tener ninguno del todo.\u200B\u200B En algunos marcos de referencia es generalmente imposible decidir siquiera si existe alguna soluci\u00F3n. Para unificaciones sint\u00E1cticas de primer orden, Martelli y Montanari\u200B brindaron un algoritmo que reporta insolubilidd o calcula un conjunto completo y m\u00EDnimo de sustituciones unitario que contiene el as\u00ED llamado unificador m\u00E1s general. Por ejemplo, usando x,y,z como variables, el conjunto de ecuaciones unitario { (x,cons(x,)) = cons(2,y) } es un problema de unificaci\u00F3n sint\u00E1ctico de primer orden que tiene la sustituci\u00F3n { x \u21A6 2, y \u21A6 cons(2,nil) } como \u00FAnica soluci\u00F3n. El problema de unificaci\u00F3n sint\u00E1ctico de primer orden { y = cons(2,y) } no tiene soluci\u00F3n en el conjunto ; sin embargo, tiene una soluci\u00F3n \u00FAnica { y \u21A6 cons(2,cons(2,cons(2,...))) } en el conjunto de . El problema de unificaci\u00F3n sem\u00E1ntica de primer orden { a\u22C5x = x\u22C5a } tiene cualquier sustituci\u00F3n de la forma { x \u21A6 a\u22C5...\u22C5a } como soluci\u00F3n en un semigrupo, en otras palabras, si (\u22C5) es asociativa; el mismo problema, visto en un grupo abeliano donde (\u22C5) tambi\u00E9n es considerada conmutativa, tiene cualquier sustituci\u00F3n como una soluci\u00F3n. El conjunto unitario { a = y(x) } es un problema de unificaci\u00F3n sint\u00E1ctico de segundo orden dado que y es una variable que representa una funci\u00F3n. Una soluci\u00F3n es { x \u21A6 a, y \u21A6 (funci\u00F3n identidad) }; otra soluci\u00F3n es { y \u21A6 (funci\u00F3n constante asociando cada valor con a), x \u21A6 (cualquier valor) }. Los algoritmos de unificaci\u00F3n fueron descubiertos por Jacques Herbrand,\u200B\u200B\u200B pero la primera investigaci\u00F3n formal puede ser atribuida a ,\u200B\u200B quien utiliz\u00F3 unificaci\u00F3n sint\u00E1ctica de primer orden como base en su procedimiento de resoluci\u00F3n de l\u00F3gica de primer orden, un gran paso adelante en la tecnolog\u00EDa de razonamiento automatizado al eliminar una de las fuentes de explosi\u00F3n combinatoria: la b\u00FAsqueda de instanciaci\u00F3n de t\u00E9rminos. El razonamiento autom\u00E1tico es todav\u00EDa el \u00E1rea donde la unificaci\u00F3n es aplicada mayormente. Unificaci\u00F3n sint\u00E1ctica de primer orden es usada en programaci\u00F3n l\u00F3gica y en la implementaci\u00F3n de lenguajes de programaci\u00F3n que usan , especialmente en algoritmos de inferencia de tipos basados en . Unificaci\u00F3n sem\u00E1ntica es utilizada en solucionadores de satisfacibilidad m\u00F3dulo (SMT por las siglas en ingl\u00E9s), algoritmos para la (reescritura de t\u00E9rminos) y en an\u00E1lisis de protocolos criptogr\u00E1ficos. Unificaci\u00F3n de orden superior es utilizado en asistentes para la demostraci\u00F3n de teoremas, por ejemplo Isabelle and , y formas restringidas de unificaci\u00F3n de orden superior (unificaci\u00F3n de patrones de nivel orden superior) son utilizadas en la implementaci\u00F3n de algunos lenguajes de programaci\u00F3n, tales como , porque pese a que los patrones de orden superior son expresivos, su procedimiento de unificaci\u00F3n asociado conserva propiedades te\u00F3ricas m\u00E1s cercanas a la unificaci\u00F3n de primer orden."@es , "\u5728\u6570\u7406\u903B\u8F91\u4E2D\uFF0C\u7279\u522B\u662F\u5E94\u7528\u4E8E\u8BA1\u7B97\u673A\u79D1\u5B66\u4E2D\uFF0C\u4E24\u4E2A\u9879\u7684\u540C\u4E00\u662F\u5C31\u7279\u6B8A\u5316\u6B21\u5E8F\u800C\u8A00\u7684\u5E76(\u683C\u7684\u6700\u5C0F\u4E0A\u754C), \u5C31\u662F\u8BF4\uFF0C\u6211\u4EEC\u5728\u9879\u7684\u96C6\u5408\u4E0A\u5047\u5B9A\u4E00\u4E2A\u9884\u5E8F\uFF0C\u5176\u4E2D t* \u2264 t \u610F\u5473\u7740 t* \u662F\u901A\u8FC7\u4EE3\u6362(substitute)\u5728 t \u4E2D\u67D0\u4E9B\u9879\u7684\u4E00\u4E2A\u6216\u591A\u4E2A\u81EA\u7531\u53D8\u91CF\u800C\u4ECE t \u83B7\u5F97\u7684\u3002s \u548C t \u7684\u540C\u4E00 u\uFF0C\u5982\u679C\u5B58\u5728\u7684\u8BDD\uFF0C\u662F s \u548C t \u4E8C\u8005\u7684\u4EE3\u6362\u5B9E\u4F8B\u7684\u4E00\u4E2A\u9879\u3002s \u548C t \u7684\u4EFB\u4F55\u516C\u5171\u7684\u4EE3\u6362\u5B9E\u4F8B\u4E5F\u662F u \u7684\u5B9E\u4F8B\u3002 \u4F8B\u5982\uFF0C\u5BF9\u4E8E\u591A\u9879\u5F0F X2 \u548C Y3 \u53EF\u4EE5\u901A\u8FC7\u91C7\u7EB3 X = Z3 \u548C Y = Z2 \u800C\u540C\u4E00\u5230 Z6\u3002"@zh , "En informatique et en logique, l'unification est un processus algorithmique qui, \u00E9tant donn\u00E9s deux termes, trouve une substitution qui appliqu\u00E9e aux deux termes les rend identiques. Par exemple, et peuvent \u00EAtre rendus identiques par la substitution et , qui donne quand on l'applique \u00E0 chacun de ces termes le terme . Dit autrement, l'unification est la r\u00E9solution d'une \u00E9quation dans l'alg\u00E8bre des termes (unification syntaxique) ou dans une alg\u00E8bre quotient par un ensemble d'identit\u00E9s (unification modulo une th\u00E9orie) ; la solution de l'\u00E9quation est la substitution qui rend les deux termes identiques et que l'on appelle l'unificateur.L'unification a des applications en inf\u00E9rence de types, programmation logique, en d\u00E9monstration automatique de th\u00E9or\u00E8mes, en syst\u00E8me de r\u00E9\u00E9criture, en traitement du langage naturel. Souvent, on s'int\u00E9resse \u00E0 l'unification syntaxique o\u00F9 il faut que les termes obtenus par application de l'unificateur soient syntaxiquement \u00E9gaux, comme dans l'exemple ci-dessus. Par exemple, le probl\u00E8me d'unification syntaxique ayant pour donn\u00E9es et n'a pas de solution. Le filtrage par motif (ou pattern matching) est une restriction de l'unification o\u00F9 l'unificateur n'est appliqu\u00E9e qu'\u00E0 un seul des deux termes. Par exemple, et sont rendus \u00E9gaux par la substitution . La fin de l'article pr\u00E9sente aussi l'unification modulo une th\u00E9orie, qui est le cas o\u00F9 on dispose de connaissances suppl\u00E9mentaires sur les fonctions (par exemple, est commutatif)."@fr , "\u0423\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u0432 \u043B\u043E\u0433\u0456\u0446\u0456 \u0442\u0430 \u0456\u043D\u0444\u043E\u0440\u043C\u0430\u0442\u0438\u0446\u0456 \u2014 \u0446\u0435 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0456\u0447\u043D\u0438\u0439 \u043F\u0440\u043E\u0446\u0435\u0441 \u0440\u043E\u0437\u0432'\u044F\u0437\u0430\u043D\u043D\u044F \u0440\u0456\u0432\u043D\u044F\u043D\u044C \u043C\u0456\u0436 \u0441\u0438\u043C\u0432\u043E\u043B\u0456\u0447\u043D\u0438\u043C\u0438 . \u0417\u0430\u043B\u0435\u0436\u043D\u043E \u0432\u0456\u0434 \u0442\u043E\u0433\u043E, \u044F\u043A\u0438\u043C \u0432\u0438\u0440\u0430\u0437\u0430\u043C (\u0442\u0435\u0440\u043C\u0430\u043C) \u0434\u043E\u0437\u0432\u043E\u043B\u0435\u043D\u043E \u0437'\u044F\u0432\u043B\u044F\u0442\u0438\u0441\u044C \u0432 \u043D\u0430\u0431\u043E\u0440\u0456 \u0440\u0456\u0432\u043D\u044F\u043D\u044C (\u0442\u0430\u043A\u043E\u0436 \u043D\u0430\u0437\u0438\u0432\u0430\u0454\u0442\u044C\u0441\u044F \u043F\u0440\u043E\u0431\u043B\u0435\u043C\u043E\u044E \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457), \u0456 \u044F\u043A\u0456 \u0432\u0438\u0440\u0430\u0437\u0438 \u0432\u0432\u0430\u0436\u0430\u044E\u0442\u044C\u0441\u044F \u0440\u0456\u0432\u043D\u0438\u043C\u0438, \u0432\u0438\u0434\u0456\u043B\u044F\u044E\u0442\u044C \u043A\u0456\u043B\u044C\u043A\u0430 \u0441\u0442\u0440\u0443\u043A\u0442\u0443\u0440 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457. \u042F\u043A\u0449\u043E \u0443 \u0432\u0438\u0440\u0430\u0437\u0456 \u0434\u043E\u043F\u0443\u0441\u043A\u0430\u044E\u0442\u044C\u0441\u044F \u0437\u043C\u0456\u043D\u043D\u0456 \u0432\u0438\u0449\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443, \u0442\u043E\u0431\u0442\u043E \u0437\u043C\u0456\u043D\u043D\u0456, \u0449\u043E \u043F\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043B\u044F\u044E\u0442\u044C \u0444\u0443\u043D\u043A\u0446\u0456\u0457, \u043F\u0440\u043E\u0446\u0435\u0441 \u043D\u0430\u0437\u0438\u0432\u0430\u0454\u0442\u044C\u0441\u044F \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u0432\u0438\u0449\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443, \u0456\u043D\u0430\u043A\u0448\u0435, \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443. \u042F\u043A\u0449\u043E \u043F\u043E\u0442\u0440\u0456\u0431\u043D\u043E, \u0449\u043E\u0431 \u043E\u0431\u0438\u0434\u0432\u0456 \u0441\u0442\u043E\u0440\u043E\u043D\u0438 \u043A\u043E\u0436\u043D\u043E\u0433\u043E \u0440\u0456\u0432\u043D\u044F\u043D\u043D\u044F \u0431\u0443\u043B\u0438 \u0431\u0443\u043A\u0432\u0430\u043B\u044C\u043D\u043E \u0440\u0456\u0432\u043D\u0438\u043C\u0438, \u0446\u0435\u0439 \u043F\u0440\u043E\u0446\u0435\u0441 \u043D\u0430\u0437\u0438\u0432\u0430\u0454\u0442\u044C\u0441\u044F \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u043D\u0438\u043C \u0430\u0431\u043E \u0432\u0456\u043B\u044C\u043D\u0438\u043C \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F, \u0432 \u0456\u043D\u0448\u043E\u043C\u0443 \u0432\u0438\u043F\u0430\u0434\u043A\u0443 \u2014 \u0441\u0435\u043C\u0430\u043D\u0442\u0438\u0447\u043D\u0435 \u0430\u0431\u043E \u0440\u0456\u0432\u043D\u043E\u043F\u0440\u0430\u0432\u043D\u0430 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F, \u0430\u0431\u043E \u0415-\u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u0430\u0431\u043E \u0442\u0435\u043E\u0440\u0456\u044F \u043C\u043E\u0434\u0443\u043B\u0456\u0432 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457. \u0420\u0456\u0448\u0435\u043D\u043D\u044F \u043F\u0440\u043E\u0431\u043B\u0435\u043C\u0438 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u043F\u043E\u0437\u043D\u0430\u0447\u0430\u0454\u0442\u044C\u0441\u044F \u044F\u043A , \u0442\u043E\u0431\u0442\u043E \u0432\u0456\u0434\u043E\u0431\u0440\u0430\u0436\u0435\u043D\u043D\u044F, \u0449\u043E \u043F\u0440\u0438\u0441\u0432\u043E\u044E\u0454 \u0441\u0438\u043C\u0432\u043E\u043B\u0456\u0447\u043D\u0435 \u0437\u043D\u0430\u0447\u0435\u043D\u043D\u044F \u043A\u043E\u0436\u043D\u0456\u0439 \u0437\u043C\u0456\u043D\u043D\u0456\u0439 \u0432\u0438\u0440\u0430\u0437\u0456\u0432 \u0437\u0430\u0434\u0430\u0447\u0456. \u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u043F\u043E\u0432\u0438\u043D\u0435\u043D \u043E\u0431\u0447\u0438\u0441\u043B\u0438\u0442\u0438 \u0434\u043B\u044F \u0437\u0430\u0434\u0430\u043D\u043E\u0457 \u0437\u0430\u0434\u0430\u0447\u0456 \u043F\u043E\u0432\u043D\u0438\u0439 \u0456 \u043C\u0456\u043D\u0456\u043C\u0430\u043B\u044C\u043D\u0438\u0439 \u043D\u0430\u0431\u0456\u0440 \u043F\u0456\u0434\u0441\u0442\u0430\u043D\u043E\u0432\u043E\u043A, \u0442\u043E\u0431\u0442\u043E \u043D\u0430\u0431\u0456\u0440, \u0449\u043E \u043E\u0445\u043E\u043F\u043B\u044E\u0454 \u0432\u0441\u0456 \u0439\u043E\u0433\u043E \u0440\u0456\u0448\u0435\u043D\u043D\u044F, \u0456 \u043D\u0435 \u043C\u0456\u0441\u0442\u0438\u0442\u044C \u0437\u0430\u0439\u0432\u0438\u0445 \u0447\u043B\u0435\u043D\u0456\u0432. \u0417\u0430\u043B\u0435\u0436\u043D\u043E \u0432\u0456\u0434 \u0441\u0442\u0440\u0443\u043A\u0442\u0443\u0440\u0438, \u043F\u043E\u0432\u043D\u0438\u0439 \u0442\u0430 \u043C\u0456\u043D\u0456\u043C\u0430\u043B\u044C\u043D\u0438\u0439 \u043D\u0430\u0431\u0456\u0440 \u0437\u0430\u043C\u0456\u043D\u0438 \u043C\u043E\u0436\u0435 \u043C\u0430\u0442\u0438 \u043D\u0435 \u0431\u0456\u043B\u044C\u0448\u0435 \u043E\u0434\u043D\u043E\u0433\u043E, \u043D\u0435 \u0431\u0456\u043B\u044C\u0448\u0435 \u043D\u0456\u0436 \u043A\u0456\u043D\u0446\u0435\u0432\u043E\u0433\u043E \u0447\u0438\u0441\u043B\u0430 \u0430\u0431\u043E, \u043C\u043E\u0436\u043B\u0438\u0432\u043E, \u043D\u0435\u0441\u043A\u0456\u043D\u0447\u0435\u043D\u043D\u043E \u0431\u0430\u0433\u0430\u0442\u043E \u0447\u043B\u0435\u043D\u0456\u0432 \u0430\u0431\u043E \u043C\u043E\u0436\u0435 \u043D\u0435 \u0456\u0441\u043D\u0443\u0432\u0430\u0442\u0438 \u0437\u043E\u0432\u0441\u0456\u043C. \u0412 \u0434\u0435\u044F\u043A\u0438\u0445 \u0440\u0430\u043C\u043A\u0430\u0445 \u0432\u0437\u0430\u0433\u0430\u043B\u0456 \u043D\u0435\u043C\u043E\u0436\u043B\u0438\u0432\u043E \u0432\u0438\u0440\u0456\u0448\u0438\u0442\u0438, \u0447\u0438 \u0456\u0441\u043D\u0443\u0454 \u044F\u043A\u0435\u0441\u044C \u0440\u0456\u0448\u0435\u043D\u043D\u044F. \u0414\u043B\u044F \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u043D\u043E\u0457 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443 \u041C\u0430\u0440\u0442\u0435\u043B\u043B\u0456 \u0442\u0430 \u041C\u043E\u043D\u0442\u0430\u043D\u0430\u0440\u0456 \u043F\u043E\u0434\u0430\u043B\u0438 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C, \u044F\u043A\u0438\u0439 \u043F\u043E\u0432\u0456\u0434\u043E\u043C\u043B\u044F\u0454 \u043F\u0440\u043E \u043D\u0435\u0440\u043E\u0437\u0432'\u044F\u0437\u043D\u0456\u0441\u0442\u044C, \u0430\u0431\u043E \u043E\u0431\u0447\u0438\u0441\u043B\u044E\u0454 \u043F\u043E\u0432\u043D\u0438\u0439 \u0456 \u043C\u0456\u043D\u0456\u043C\u0430\u043B\u044C\u043D\u0438\u0439 \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u043D\u0438\u0439 \u043D\u0430\u0431\u0456\u0440, \u044F\u043A\u0438\u0439 \u043C\u0456\u0441\u0442\u0438\u0442\u044C \u0442\u0430\u043A \u0437\u0432\u0430\u043D\u0438\u0439 \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448 \u0437\u0430\u0433\u0430\u043B\u044C\u043D\u0438\u0439 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0442\u043E\u0440. \u041D\u0430\u043F\u0440\u0438\u043A\u043B\u0430\u0434, \u0432\u0438\u043A\u043E\u0440\u0438\u0441\u0442\u043E\u0432\u0443\u044E\u0447\u0438 x,y,z \u044F\u043A \u0437\u043C\u0456\u043D\u043D\u0456, \u0432\u0441\u0442\u0430\u043D\u043E\u0432\u043B\u044E\u0454\u0442\u044C\u0441\u044F \u0440\u0456\u0432\u043D\u044F\u043D\u043D\u044F: { cons(x,cons(x, nil)) = cons (2, y) } \u2014 \u0446\u0435 \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u043D\u0430 \u043F\u0440\u043E\u0431\u043B\u0435\u043C\u0430 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443 \u0449\u043E \u043C\u0430\u0454 \u0454\u0434\u0438\u043D\u0435 \u0440\u0456\u0448\u0435\u043D\u043D\u044F \u0434\u043B\u044F \u0437\u0430\u043C\u0456\u043D\u0438 { x \u21A6 2, y \u21A6 cons(2, nil)}. \u0421\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u043D\u0430 \u043F\u0440\u043E\u0431\u043B\u0435\u043C\u0430 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443 ( y = cons (2, y)} \u043D\u0435 \u043C\u0430\u0454 \u0432\u0438\u0440\u0456\u0448\u0435\u043D\u043D\u044F \u043D\u0430\u0434 \u043D\u0430\u0431\u043E\u0440\u043E\u043C \u043A\u0456\u043D\u0446\u0435\u0432\u0438\u0445 \u0432\u0438\u0440\u0430\u0437\u0456\u0432; \u043E\u0434\u043D\u0430\u043A \u0443 \u043D\u044C\u043E\u0433\u043E \u0454 \u0454\u0434\u0438\u043D\u0435 \u0440\u0456\u0448\u0435\u043D\u043D\u044F { y \u27E9 cons (2, cons (2, cons (2, \u2026)))} \u043D\u0430\u0434 \u043D\u0430\u0431\u043E\u0440\u043E\u043C \u043D\u0435\u0441\u043A\u0456\u043D\u0447\u0435\u043D\u043D\u0438\u0445 \u0434\u0435\u0440\u0435\u0432. \u0421\u0435\u043C\u0430\u043D\u0442\u0438\u0447\u043D\u0430 \u043F\u0440\u043E\u0431\u043B\u0435\u043C\u0430 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443 {a\u22C5x = x\u22C5a} \u043C\u0430\u0454 \u043A\u043E\u0436\u043D\u0443 \u043F\u0456\u0434\u0441\u0442\u0430\u043D\u043E\u0432\u043A\u0443 \u0444\u043E\u0440\u043C\u0438 { x \u21A6 \"'a' ' \u22C5 \u2026 \u22C5a } \u044F\u043A \u0440\u0456\u0448\u0435\u043D\u043D\u044F \u0432 \u043D\u0430\u043F\u0456\u0432\u0433\u0440\u0443\u043F\u0438, \u0442\u043E\u0431\u0442\u043E \u044F\u043A\u0449\u043E (\u22C5) \u0432\u0432\u0430\u0436\u0430\u0454\u0442\u044C\u0441\u044F \u0430\u0441\u043E\u0446\u0456\u0430\u0442\u0438\u0432\u043D\u0430; \u0442\u0430 \u0436 \u043F\u0440\u043E\u0431\u043B\u0435\u043C\u0430, \u0440\u043E\u0437\u0433\u043B\u044F\u043D\u0443\u0442\u0430 \u0432 \u0430\u0431\u0435\u043B\u0435\u0432\u0456\u0439 \u0433\u0440\u0443\u043F\u0456, \u0434\u0435 (\u22C5) \u0442\u0430\u043A\u043E\u0436 \u0432\u0432\u0430\u0436\u0430\u0454\u0442\u044C\u0441\u044F \u043A\u043E\u043C\u0443\u0442\u0430\u0442\u0438\u0432\u043D\u0430, \u043C\u0430\u0454 \u0432\u0437\u0430\u0433\u0430\u043B\u0456 \u0431\u0443\u0434\u044C-\u044F\u043A\u0443 \u0437\u0430\u043C\u0456\u043D\u0443 \u044F\u043A \u0440\u0456\u0448\u0435\u043D\u043D\u044F.\u0421\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u043D\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u0434\u0440\u0443\u0433\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443, \u043E\u0441\u043A\u0456\u043B\u044C\u043A\u0438 y \u2014 \u0444\u0443\u043D\u043A\u0446\u0456\u043E\u043D\u0430\u043B\u044C\u043D\u0430 \u0437\u043C\u0456\u043D\u043D\u0430, \u0454 \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u043D\u043E\u044E \u0437\u0430\u0434\u0430\u0447\u0435\u044E { a = y ( x ) }.\u041E\u0434\u043D\u0438\u043C \u0456\u0437 \u0440\u0456\u0448\u0435\u043D\u044C \u0454 {x \u21A6 a, y \u21A6 (\u0442\u043E\u0442\u043E\u0436\u043D\u0456\u0441\u0442\u044C \u0444\u0443\u043D\u043A\u0446\u0456\u0457)}; \u0456\u043D\u0448\u0438\u0439 \u0454 {y \u21A6 (\u0441\u0442\u0430\u043B\u0430 \u0444\u0443\u043D\u043A\u0446\u0456\u044F, \u0449\u043E \u0432\u0456\u0434\u0441\u043B\u0456\u0434\u043A\u043E\u0432\u0443\u0454 \u043A\u043E\u0436\u043D\u0435 \u0437\u043D\u0430\u0447\u0435\u043D\u043D\u044F \u0434\u043E a), x \u21A6 (\u0431\u0443\u0434\u044C-\u044F\u043A\u0435 \u0437\u043D\u0430\u0447\u0435\u043D\u043D\u044F)}. \u041F\u0435\u0440\u0448\u0435 \u0444\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u0435 \u0434\u043E\u0441\u043B\u0456\u0434\u0436\u0435\u043D\u043D\u044F \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u043C\u043E\u0436\u043D\u0430 \u0432\u0456\u0434\u043D\u0435\u0441\u0442\u0438 \u0434\u043E \u0414\u0436\u043E\u043D \u0410\u043B\u0430\u043D \u0420\u043E\u0431\u0456\u043D\u0441\u043E\u043D,, \u044F\u043A\u0438\u0439 \u0437\u0430\u0441\u0442\u043E\u0441\u0443\u0432\u0430\u0432 \u0441\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u043D\u0435 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443 \u044F\u043A \u0431\u0430\u0437\u043E\u0432\u0438\u0439 \u0431\u0443\u0434\u0456\u0432\u0435\u043B\u044C\u043D\u0438\u0439 \u0431\u043B\u043E\u043A \u0439\u043E\u0433\u043E \u0440\u0456\u0448\u0435\u043D\u043D\u044F \u043F\u0440\u043E\u0446\u0435\u0434\u0443\u0440\u0438 \u043B\u043E\u0433\u0456\u043A\u0438 \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443, \u0432\u0435\u043B\u0438\u043A\u0438\u0439 \u043A\u0440\u043E\u043A \u0432\u043F\u0435\u0440\u0435\u0434 \u0432 \u0430\u0432\u0442\u043E\u043C\u0430\u0442\u0438\u0437\u043E\u0432\u0430\u043D\u0435 \u043E\u0431\u0491\u0440\u0443\u043D\u0442\u0443\u0432\u0430\u043D\u043D\u044F \u0442\u0435\u0445\u043D\u043E\u043B\u043E\u0433\u0456\u0457, \u043E\u0441\u043A\u0456\u043B\u044C\u043A\u0438 \u0432\u043E\u043D\u0430 \u0443\u0441\u0443\u0432\u0430\u0454 \u043E\u0434\u043D\u0435 \u0434\u0436\u0435\u0440\u0435\u043B\u043E \u043A\u043E\u043C\u0431\u0456\u043D\u0430\u0442\u043E\u0440\u043D\u043E\u0433\u043E \u0432\u0438\u0431\u0443\u0445\u0443: \u043F\u043E\u0448\u0443\u043A \u043E\u0431'\u0454\u043A\u0442\u0456\u0432 \u0442\u0435\u0440\u043C\u0456\u043D\u0456\u0432. \u0421\u044C\u043E\u0433\u043E\u0434\u043D\u0456 \u0430\u0432\u0442\u043E\u043C\u0430\u0442\u0438\u0437\u043E\u0432\u0430\u043D\u0456 \u043C\u0456\u0440\u043A\u0443\u0432\u0430\u043D\u043D\u044F \u0437\u0430\u043B\u0438\u0448\u0430\u044E\u0442\u044C\u0441\u044F \u0433\u043E\u043B\u043E\u0432\u043D\u043E\u044E \u043E\u0431\u043B\u0430\u0441\u0442\u044E \u0437\u0430\u0441\u0442\u043E\u0441\u0443\u0432\u0430\u043D\u043D\u044F \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457. \u0421\u0438\u043D\u0442\u0430\u043A\u0441\u0438\u0447\u043D\u0435 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443 \u0432\u0438\u043A\u043E\u0440\u0438\u0441\u0442\u043E\u0432\u0443\u0454\u0442\u044C\u0441\u044F \u0434\u043B\u044F \u0437\u0434\u0456\u0439\u0441\u043D\u0435\u043D\u043D\u044F \u043B\u043E\u0433\u0456\u0447\u043D\u043E\u0433\u043E \u043F\u0440\u043E\u0433\u0440\u0430\u043C\u0443\u0432\u0430\u043D\u043D\u044F \u0442\u0430 \u0440\u0435\u0430\u043B\u0456\u0437\u0430\u0446\u0456\u0457 \u043C\u043E\u0432\u0438 \u043F\u0440\u043E\u0433\u0440\u0430\u043C\u0443\u0432\u0430\u043D\u043D\u044F \u0442\u0438\u043F\u0430 \u0434\u0430\u043D\u0438\u0445, \u043E\u0441\u043E\u0431\u043B\u0438\u0432\u043E \u0432 \u043D\u0430 \u043E\u0441\u043D\u043E\u0432\u0456 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0443 \u0432\u0438\u0432\u0435\u0434\u0435\u043D\u043D\u044F \u0442\u0438\u043F\u0443.\u0421\u0435\u043C\u0430\u043D\u0442\u0438\u0447\u043D\u0435 \u043E\u0431'\u0454\u0434\u043D\u0430\u043D\u043D\u044F \u0432\u0438\u043A\u043E\u0440\u0438\u0441\u0442\u043E\u0432\u0443\u0454\u0442\u044C\u0441\u044F \u0432 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0430\u0445 Satisfiability Modulo Theories, \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0430\u0445 \u0440\u0435\u0440\u0430\u0439\u0442\u0438\u043D\u0433 \u0442\u0430 \u0430\u043D\u0430\u043B\u0456\u0437\u0456 \u043A\u0440\u0438\u043F\u0442\u043E\u0433\u0440\u0430\u0444\u0456\u0447\u043D\u043E\u0433\u043E \u043F\u0440\u043E\u0442\u043E\u043A\u043E\u043B\u0443.\u041E\u0431'\u0454\u0434\u043D\u0430\u043D\u043D\u044F \u0431\u0456\u043B\u044C\u0448 \u0432\u0438\u0441\u043E\u043A\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443 \u0432\u0438\u043A\u043E\u0440\u0438\u0441\u0442\u043E\u0432\u0443\u0454\u0442\u044C\u0441\u044F \u0432 \u0430\u0441\u0438\u0441\u0442\u0435\u043D\u0442\u0430\u0445-\u0434\u043E\u043A\u0430\u0437\u0430\u0445, \u043D\u0430\u043F\u0440\u0438\u043A\u043B\u0430\u0434 , \u0430 \u0442\u0430\u043A\u043E\u0436 \u043E\u0431\u043C\u0435\u0436\u0435\u043D\u0456 \u0444\u043E\u0440\u043C\u0438 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u0431\u0456\u043B\u044C\u0448 \u0432\u0438\u0441\u043E\u043A\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443 (\u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u044F \u0448\u0430\u0431\u043B\u043E\u043D\u0456\u0432 \u0432\u0438\u0449\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443) \u0432\u0438\u043A\u043E\u0440\u0438\u0441\u0442\u043E\u0432\u0443\u044E\u0442\u044C\u0441\u044F \u0432 \u0434\u0435\u044F\u043A\u0438\u0445 \u0440\u0435\u0430\u043B\u0456\u0437\u0430\u0446\u0456\u044F\u0445 \u043C\u043E\u0432 \u043F\u0440\u043E\u0433\u0440\u0430\u043C\u0443\u0432\u0430\u043D\u043D\u044F, \u0442\u0430\u043A\u0438\u0445 \u044F\u043A , \u043E\u0441\u043A\u0456\u043B\u044C\u043A\u0438 \u0448\u0430\u0431\u043B\u043E\u043D\u0438 \u0432\u0438\u0449\u0438\u0445 \u043F\u043E\u0440\u044F\u0434\u043A\u0456\u0432 \u0454 \u0435\u043A\u0441\u043F\u0440\u0435\u0441\u0438\u0432\u043D\u0438\u043C\u0438, \u043F\u0440\u043E\u0442\u0435 \u0457\u0445 \u043F\u043E\u0432'\u044F\u0437\u0430\u043D\u0430 \u043F\u0440\u043E\u0446\u0435\u0434\u0443\u0440\u0430 \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u0437\u0431\u0435\u0440\u0456\u0433\u0430\u0454 \u0442\u0435\u043E\u0440\u0435\u0442\u0438\u0447\u043D\u0456 \u0432\u043B\u0430\u0441\u0442\u0438\u0432\u043E\u0441\u0442\u0456 \u0431\u043B\u0438\u0436\u0447\u0435 \u0434\u043E \u0443\u043D\u0456\u0444\u0456\u043A\u0430\u0446\u0456\u0457 \u043F\u0435\u0440\u0448\u043E\u0433\u043E \u043F\u043E\u0440\u044F\u0434\u043A\u0443."@uk , "\u0415\u0441\u043B\u0438 \u0432 \u0444\u043E\u0440\u043C\u0443\u043B\u0443 \u0432\u043C\u0435\u0441\u0442\u043E \u043F\u0435\u0440\u0435\u043C\u0435\u043D\u043D\u044B\u0445 \u043F\u043E\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044C \u0441\u043E\u043E\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043D\u043D\u043E \u0444\u043E\u0440\u043C\u0443\u043B\u044B \u0442\u043E \u043F\u043E\u043B\u0443\u0447\u0438\u0442\u0441\u044F \u0444\u043E\u0440\u043C\u0443\u043B\u0430 , \u043A\u043E\u0442\u043E\u0440\u0430\u044F \u043D\u0430\u0437\u044B\u0432\u0430\u0435\u0442\u0441\u044F \u0447\u0430\u0441\u0442\u043D\u044B\u043C \u0441\u043B\u0443\u0447\u0430\u0435\u043C \u0444\u043E\u0440\u043C\u0443\u043B\u044B : \u041A\u0430\u0436\u0434\u0430\u044F \u0444\u043E\u0440\u043C\u0443\u043B\u0430 \u043F\u043E\u0434\u0441\u0442\u0430\u0432\u043B\u044F\u0435\u0442\u0441\u044F \u0432\u043C\u0435\u0441\u0442\u043E \u0432\u0441\u0435\u0445 \u0432\u0445\u043E\u0436\u0434\u0435\u043D\u0438\u0439 \u043F\u0435\u0440\u0435\u043C\u0435\u043D\u043D\u043E\u0439 . \u041D\u0430\u0431\u043E\u0440 \u043F\u043E\u0434\u0441\u0442\u0430\u043D\u043E\u0432\u043E\u043A \u043D\u0430\u0437\u044B\u0432\u0430\u0435\u0442\u0441\u044F \u0443\u043D\u0438\u0444\u0438\u043A\u0430\u0442\u043E\u0440\u043E\u043C."@ru , "In logic and computer science, unification is an algorithmic process of solving equations between symbolic expressions. Depending on which expressions (also called terms) are allowed to occur in an equation set (also called unification problem), and which expressions are considered equal, several frameworks of unification are distinguished. If higher-order variables, that is, variables representing functions, are allowed in an expression, the process is called higher-order unification, otherwise first-order unification. If a solution is required to make both sides of each equation literally equal, the process is called syntactic or free unification, otherwise semantic or equational unification, or E-unification, or unification modulo theory. A solution of a unification problem is denoted as a substitution, that is, a mapping assigning a symbolic value to each variable of the problem's expressions. A unification algorithm should compute for a given problem a complete and minimal substitution set, i.e., a set containing all of the problem's solutions and no redundant members. Depending on the framework, a complete and minimal substitution set may have at most one, at most finitely many, or possibly infinitely many members, or may not exist at all. In some frameworks it is generally impossible to decide whether any solution exists. For first-order syntactical unification, Martelli and Montanari gave an algorithm that reports unsolvability or computes a complete and minimal singleton substitution set containing the so-called most general unifier. For example, using x,y,z as variables, the singleton equation set { cons(x,cons(x,nil)) = cons(2,y) } is a syntactic first-order unification problem that has the substitution { x \u21A6 2, y \u21A6 cons(2,nil) } as its only solution.The syntactic first-order unification problem { y = cons(2,y) } has no solution over the set of finite terms; however, it has the single solution { y \u21A6 cons(2,cons(2,cons(2,...))) } over the set of infinite trees.The semantic first-order unification problem { a\u22C5x = x\u22C5a } has each substitution of the form { x \u21A6 a\u22C5...\u22C5a } as a solution in a semigroup, i.e. if (\u22C5) is considered associative; the same problem, viewed in an abelian group, where (\u22C5) is considered also commutative, has any substitution at all as a solution.The singleton set { a = y(x) } is a syntactic second-order unification problem, since y is a function variable.One solution is { x \u21A6 a, y \u21A6 (identity function) }; another one is { y \u21A6 (constant function mapping each value to a), x \u21A6 (any value) }. A unification algorithm was first discovered by Jacques Herbrand, while a first formal investigation can be attributed to John Alan Robinson, who used first-order syntactical unification as a basic building block of his resolution procedure for first-order logic, a great step forward in automated reasoning technology, as it eliminated one source of combinatorial explosion: searching for instantiation of terms. Today, automated reasoning is still the main application area of unification.Syntactical first-order unification is used in logic programming and programming language type system implementation, especially in Hindley\u2013Milner based type inference algorithms.Semantic unification is used in SMT solvers, term rewriting algorithms and cryptographic protocol analysis.Higher-order unification is used in proof assistants, for example Isabelle and Twelf, and restricted forms of higher-order unification (higher-order pattern unification) are used in some programming language implementations, such as lambdaProlog, as higher-order patterns are expressive, yet their associated unification procedure retains theoretical properties closer to first-order unification."@en , "Unifica\u00E7\u00E3o, em ci\u00EAncia da computa\u00E7\u00E3o e na l\u00F3gica, \u00E9 um processo algor\u00EDtmico de solu\u00E7\u00E3o de equa\u00E7\u00F5es entre express\u00F5es simb\u00F3licas. Dependendo de quais express\u00F5es (tamb\u00E9m chamadas de termos) s\u00E3o permitidas ocorrer em um conjunto de equa\u00E7\u00F5es (tamb\u00E9m chamado de problema da unifica\u00E7\u00E3o), e quais express\u00F5es s\u00E3o consideradas iguais, diversas estruturas de unifica\u00E7\u00E3o s\u00E3o distinguidas. Se vari\u00E1veis de alta ordem, isto \u00E9, vari\u00E1veis que representam fun\u00E7\u00F5es, s\u00E3o permitidas em uma express\u00E3o, o processo \u00E9 chamado de unifica\u00E7\u00E3o de alta ordem, ou, caso contr\u00E1rio, \u00E9 chamado de unifica\u00E7\u00E3o de primeira ordem. Se exige-se uma solu\u00E7\u00E3o que fa\u00E7a com que ambos os lados de cada equa\u00E7\u00E3o sejam literalmente iguais, o processo \u00E9 chamado de unifica\u00E7\u00E3o sint\u00E1tica, ou, caso contr\u00E1rio, unifica\u00E7\u00E3o sem\u00E2ntica, ou unifica\u00E7\u00E3o equacional, ou unifica\u00E7\u00E3o E, ou unifica\u00E7\u00E3o m\u00F3dulo uma teoria. A solu\u00E7\u00E3o de um problema de unifica\u00E7\u00E3o \u00E9 denotada como uma , isto \u00E9, um mapeamento atribuindo um valor simb\u00F3lico a cada vari\u00E1vel das express\u00F5es do problema. Um algoritmo de unifica\u00E7\u00E3o deve computar, para um dado problema, um conjunto de substitui\u00E7\u00E3o completo e m\u00EDnimo, isto \u00E9, um conjunto cobrindo todas as solu\u00E7\u00F5es e com nenhum membro redundante. Dependendo da estrutura, um conjunto de substitui\u00E7\u00E3o completo e m\u00EDnimo talvez contenha nenhum, ou uma quantidade finita, ou infinita de membros. [nota1] Em algumas estruturas \u00E9 geralmente imposs\u00EDvel decidir se existe alguma solu\u00E7\u00E3o. Para a unifica\u00E7\u00E3o sint\u00E1tica de primeira ordem, Martelli e Montanari desenvolveram um algoritmo capaz de informar a inexist\u00EAncia de uma solu\u00E7\u00E3o ou computar um \u00FAnico conjunto de substitui\u00E7\u00E3o completo e m\u00EDnimo contendo o chamado unificador mais geral. Por exemplo, usando x, y, z como vari\u00E1veis e o \u00FAnico conjunto de equa\u00E7\u00E3o { (x,cons(x,nil)) = cons(2,y) } \u00E9 um problema unifica\u00E7\u00E3o sint\u00E1tica de primeira ordem que tem a substitui\u00E7\u00E3o { x \u21A6 2, y \u21A6 cons(2,nil) } como uma \u00FAnica solu\u00E7\u00E3o. O problema da unifica\u00E7\u00E3o sint\u00E1tica de primeira ordem { y = cons(2,y) } n\u00E3o possui uma solu\u00E7\u00E3o sobre o conjunto de termos finitos; contudo, possui como solu\u00E7\u00E3o \u00FAnica { y \u21A6 cons(2,cons(2,cons(2,...))) } sobre o conjunto de \u00E1rvores infinitas. O problema da unifica\u00E7\u00E3o sem\u00E2ntica de primeira ordem { a\u22C5x = x\u22C5a } possui toda substitui\u00E7\u00E3o da forma { x \u21A6 a\u22C5...\u22C5a } como uma solu\u00E7\u00E3o em um semi grupo, isto \u00E9, se (\u22C5) \u00E9 considerado associativo; o mesmo problema, visto em um grupo abeliano, onde (\u22C5) \u00E9 considerado tamb\u00E9m como comutativo, tem qualquer substitui\u00E7\u00E3o como uma solu\u00E7\u00E3o. O \u00FAnico conjunto { a = y(x) } \u00E9 um problema se unifica\u00E7\u00E3o sint\u00E1tico de segunda ordem, desde que y seja uma fun\u00E7\u00E3o vari\u00E1vel. Uma solu\u00E7\u00E3o \u00E9 { x \u21A6 a, y \u21A6 (fun\u00E7\u00E3o identidade) }; outra solu\u00E7\u00E3o \u00E9 { y \u21A6 ( mapeando cada valor para a), x \u21A6 (qualquer valor) }. A primeira investiga\u00E7\u00E3o formal de unifica\u00E7\u00E3o pode ser atribu\u00EDda a , quem usou a unifica\u00E7\u00E3o sint\u00E1tica de primeira ordem como um bloco b\u00E1sico de constru\u00E7\u00E3o em seu processo de resolu\u00E7\u00E3o para a l\u00F3gica de primeira ordem, um bom avan\u00E7o na tecnologia de , uma vez que isso eliminou uma fonte de explos\u00E3o combinat\u00F3ria: busca por instancia\u00E7\u00E3o de termos. Hoje, o racioc\u00EDnio automatizado continua sendo a principal \u00E1rea de aplica\u00E7\u00E3o da unifica\u00E7\u00E3o. A unifica\u00E7\u00E3o sint\u00E1tica de primeira ordem \u00E9 usada na l\u00F3gica de programa\u00E7\u00E3o e na implementa\u00E7\u00E3o de sistema de tipos na linguagem de programa\u00E7\u00E3o, especialmente nos tipos de algoritmos de infer\u00EAncia baseados em . A unifica\u00E7\u00E3o sem\u00E2ntica \u00E9 usada em e em algoritmos de reescrita de termos. Unifica\u00E7\u00E3o de alta ordem \u00E9 usada em assistentes de provas, por exemplo, Isabelle e , e formas restritas da unifica\u00E7\u00E3o de alta ordem (padr\u00E3o de unifica\u00E7\u00E3o de alta ordem) s\u00E3o usadas em algumas implementa\u00E7\u00F5es de linguagens de programa\u00E7\u00E3o, no caso de lambdaProlog. Como padr\u00F5es de alta ordem s\u00E3o expressivos, seu processo de unifica\u00E7\u00E3o associada ainda ret\u00EAm propriedades te\u00F3ricas pr\u00F3ximas a unifica\u00E7\u00E3o de primeira ordem."@pt , "Unifikation ist eine Methode zur Vereinheitlichung pr\u00E4dikatenlogischer Ausdr\u00FCcke. Zwei Ausdr\u00FCcke werden unifiziert, indem ihre Variablen so durch geeignete Terme ersetzt werden, dass die resultierenden Ausdr\u00FCcke gleich sind. Die Unifikation hat insbesondere in der Computerlogik und Computerlinguistik eine gr\u00F6\u00DFere Bedeutung erlangt. So nutzt etwa die Inferenzmaschine des Prolog-Interpreters Unifikation. In der Computerlinguistik gibt es sogenannte Unifikationsgrammatiken, die sich auf dieses Konzept st\u00FCtzen. Auch beim Theorembeweisen spielt Unifikation eine gro\u00DFe Rolle. Als Basisoperation liegt der Unifikation die Substitution zu Grunde. Im Rahmen der Pr\u00E4dikatenlogik bedeutet eine Substitution \u03C3 innerhalb eines gegebenen Ausdrucks die Ersetzung einer Variablen durch einen Term, in dem diese Variable nicht vorkommen darf. Die Variable wird gewisserma\u00DFen durch den Term \u201Einstanziiert\u201C. Wird eine Menge von Ausdr\u00FCcken durch eine Substitution \u03C3 zu einem \u00E4quivalenten Ausdruck substituiert, d. h. , so bezeichnet man \u03C3 als Unifikator dieser Ausdrucksmenge. Die Anwendung eines Unifikators auf diese Menge bezeichnet man als Unifikation. Nicht alle Ausdrucksmengen k\u00F6nnen unifiziert werden."@de . @prefix gold: . gold:hypernym dbr:Process . @prefix prov: . prov:wasDerivedFrom ; dbo:wikiPageLength "66751"^^xsd:nonNegativeInteger ; foaf:isPrimaryTopicOf .