Читайте также: |
|
Если D1/ – пример дизъюнкта D1,
D2/ – пример дизъюнкта D2 и
D/ – резольвента D1/ и D2/,
то существует обобщенная резольвента D дизъюнктов D1 и D2,
такая что D/ – пример D.
Примечание. Обобщенная резольвента – это резольвента склеек посылок.
Доказательство. Если D1 и D2 имеют общие переменные, то заменой переменных в одном из дизъюнктов можно добиться того, что переменные дизъюнкта D1 отличны от переменных дизъюнкта D2. Будем поэтому считать, что D1 и D2 не имеют общих переменных.
Так как D1 / – пример D1 и D2/ – пример D2, то существуют подстановки α1 и α2 такие, что D1/=(D1)α1 и D2/=(D2)α2. Последовательность α =(α1,α2) также будет подстановкой и поскольку D1 и D2 не имеют общих переменных, то D1/= (D1)α и D2/= (D2)α.
Дизъюнкт D/ является резольвентой дизъюнктов D1/ и D2/. Это означает, что существуют литералы L1/єD1/ и L2/єD2/ и подстановка τ такие, что τ - наиболее общий унификатор L1/ и L2/ и
D/=((D1/)τ -(L1/)τ) U ((D2/)τ -(L2/)τ) (1)
Пусть L11,…,L1r – литералы дизъюнкта D1, которые подстановкой α переводятся L1/, а L21,…,L2s – литералы дизъюнкта D2, которые подстановкой α переводятся в L2/. Следовательно, литералы L11,…,L1r, унифицируемы, а поэтому существует наиболее общий унификатор β1 для этого множества. Дизъюнкт (L11)β1 (равный (L12)β1,…, (L1r)β1) обозначим через L1. По определению наиболее общего унификатора найдется подстановка γ1, для которой выполняется равенство α1= β1 ◦ γ1.
По аналогичным соображениям, существуют подстановки β2 и γ2 такие, что β2 – наиболее общий унификатор множества литералов L21,…,L2s и α2= β 2◦ γ2. Литерал (L21) β2 обозначим через L2.
Легко видеть, что L1 и L2 не имеют общих переменных. Поскольку дизъюнкты D1 и D2 также не имеют общих переменных, то можно считать, что (β1, β2)= β, (γ1, γ2)= γ и α= β ◦ γ. Сказанное в этом абзаце иллюстрируется рисунками 4.1 и 4.2.
Рис. 4.1 | Рис. 4.2 |
Литералы L1′ и L2′, как отмечено выше, унифицируемы подстановкой τ. Следовательно, литералы L1 и L2 также унифицируемы (подстановкой γ◦τ). Отсюда следует, что существует наиболее общий унификатор σ множества {L1, L2} (см.рис.4.3). Возьмем в качестве D дизъюнкт
D=[ ((D1) β) σ – (L1)σ] U [((D2) β) σ – (L2)σ] (2)
Ясно, что D – резольвента дизъюнктов D1 и D2.
Осталось показать. Что D′ –пример D.
Рис. 4.3
Так как σ – наиболее общий унификатор L1 и L2, то существует подстановка δ такая, что γ◦τ =σ◦δ. В таком случае из последнего равенства, равенств (1), (2) и α= β ◦ γ следует, что
D′=((D1′)τ – (L1′)τ) U ((D2′)τ –(L2′)τ)=
[((D1) α) τ –((L11) α) τ] U [((D2) α) τ –((L21) α) τ] =
[(D1) α◦τ –(L11) α◦τ] U [(D2) α◦τ –(L21) α◦τ]=
[(D1) β ◦ γ ◦ τ –(L11) β ◦ γ ◦τ] U [(D2) β ◦ γ ◦τ –(L21) β ◦ γ ◦τ]=
[(D1) β ◦ σ ◦ δ – (L11) β ◦ σ ◦ δ] U [(D2) β ◦ σ ◦ δ – (L21) β ◦ σ ◦ δ ]=
[(D1) β ◦ σ – (L1) σ] δ U [(D2) β ◦ σ – (L2) σ] δ =
(D) δ.
Мы доказали, что D′ – пример D.
Дата добавления: 2015-11-30; просмотров: 53 | Нарушение авторских прав