Лекции по дискретной математике. Математическая логика. Зарипова Э.Р - 58 стр.

UptoLike

ВУЗ: 

РУДН | Москва

Составители: 

Рубрика: 

58
)())((:
))(())((:
aRafPC
afQafPC
2
1
∨
∨
Здесь ))(( afP и
))(( afP являются контрарными.
Определение
. Подстановка – это конечное множество вида
{t
1
|
v
1
,…,t
n
|
v
n
}, где каждая v
i
- переменная, каждый t
i
- терм,
отличный от v
i
, все v
i
различны.
Пример 13.2
.
{f(z)/x,y/z}, {a/x,g(y)/y,f(g(b))/z}.
Определение
. Пусть
θ
={t
1
/v
1
,…,t
n
/v
n
} - подстановка и E -
выражение. Тогда E
θ
- выражение, полученное из E заменой
одновременно всех вхождений переменной v
i
,
n1i ,=
в E на терм t
i
.
E
θ
называют примером E.
Пример 13.3.
θ
={a/x, f(b)/y, c/z}, E=P(x,y,z), E
θ
= P(a, f(b), c).
Определение
. Пусть
θ
= {t
1
/x
1
,…,t
n
/x
n
} и
λ
= {u
1
/y
1
,…,u
m
/y
m
} - две
подстановки. Тогда композиция
θ
и
λ
(обозначается
θ°λ
) есть
подстановка, которая получается из множества
{t
1
λ
/x
1
,…,t
n
λ
/x
n
, u
1
/y
1
,…,u
m
/y
m
}
вычеркиванием всех элементов t
j
λ
/x
j
, для которых t
j
λ
=x
j
и всех
элементов u
i
/y
i
таких, что y
i
∈
{x
1
,…,x
n
}.
Пример 13.4.
θ
={t
1
/x
1
, t
2
/x
2
}={f(y)/x, z/y}
λ
= {u
1
/y
1
, u
2
/y
2
, u
3
/y
3
}= {a/x, b/y, y/z}
Тогда
{t
1
λ
/x
1
, t
2
λ
/x
2
, u
1
/y
1
, u
2
/y
2
, u
3
/y
3
}={f(b)/x, y/y, a/x, b/y, y/z}.
Однако, т.к. t
2
λ
=x
2
, то t
2
λ
/x
2
(т.е. y/y) необходимо вычеркнуть.
Также нужно вычеркнуть u
1
/y
1
и u
2
/y
2
, т.к. y
1
и y
2
∈
{x
1
,x
2
}. Таким
образом получаем
θ°λ
= {f(b)/x, y/z}.
Определение
. Подстановка
θ
называется унификатором для
множества {E
1
,…,E
k
} тогда и только тогда, когда E
1
θ
= … = E
k
θ
.
Говорят, что множество унифицируемо, если для него существует
унификатор.
Определение
. Множество рассогласований непустого

Страницы