Представление и обработка знаний

74 Применение подстановки  к выражению E состоит в замене всех вхождений переменных x ( x  V ) термом  ( x ). Результат под- становки обозначают  [ E ]. Выражение E 1 =  [ E ] – называется кон- кретизацией выражения E . Например: E = P ( g ( f ( x ), g ( f ( z ), y ))), P  предикатная переменная:   = {( x  f ( x )), ( y  g ( x , y )), E 1 = P ( g ( f ( f ( x )), g ( f ( z ), g ( x , y ))) = =  [ P ( g ( f ( x ), g ( f ( z ), y )))]. Обозначим множество переменных терма t через var ( t ) . Терм t вполне конкретизирован, если | var ( t ) | = 0. Композицией (3.1) подстановок  1 и  2 является подстановка:  2 *  1 =  2 [  1 [ t ]]. Рассмотрим пример. Применим два раза подстановку сигма предыдущего примера к терму g ( x , y ): g ( f ( x ), g ( x , y )) =  [ g ( x , y )] и g ( f ( f ( x )), g ( f ( x ), g ( x , y ))) =   [ g ( f ( x ), g ( x , y ))] . Таким образом, получаем результат композиции равных под- становок применительно к терму g ( x , y ): g ( f ( f ( x )), g ( f ( x ), g ( x , y )) = (   *  )[ g ( x , y )]. Будем считать, что терм t 1 выводим из t 2 , если существует подстановка t 1 =  [ t 2 ]. Отношение выводимости обозначим через «<<», т.е. t 1 << t 2 . Рассмотрим некоторую подстановку  = {( x  y ), ( z  v )} по отношению к терму t 1 = g ( x , y ). В результате применения подста- новки получим t 2 = g ( y , v ). Построим обратную перестановку:  –1 = {( y  x ), ( v  z )} и t 1 =  –1 [ t 2 ]. Таким образом, для термов t 1 и t 2 отношение выводимости обладает симметрией. Отметим, что t 1 << t 2 и t 2 << t 1 , когда термы