ВУЗ:
Составители:
Рубрика:
52
F
1
: (∀x)(P(x)
→
Q(x))
F
2
: P(a)
_________________
G: Q(a)
Рассмотрим любую интерпретацию I, в которой истинна
формула F
1
∧
F
2
, т.е. формула (∀x)(P(x)
→
Q(x))
∧
P(a). Тогда в этой
интерпретации P(a)=И и (
∀x)(P(x)
→
Q(x))=И, т.е. P(x)
→
Q(x)=И
для всех x из D, в том числе и для x=a. Следовательно,
P(a)
→
Q(a)=И. Значит, т.к. P(a)=И, то и Q(a)=И.
Так как в исчислении предикатов имеется бесконечное число
областей, которые в свою очередь могут быть бесконечны, то,
вообще говоря, имеется бесконечное число интерпретаций
формулы исчисления предикатов. Следовательно, в отличие от
исчисления высказываний, невозможно доказать общезначимость
или противоречивость формулы оценкой формулы при
всех
возможных интерпретациях.
В настоящее время разработаны и разрабатываются процедуры
для проверки невыполнимости формул исчисления предикатов.
12. Предваренная нормальная форма. Алгоритм
преобразования формул в предваренную нормальную
форму.
Предваренная нормальная форма.
В исчислении высказываний существуют две нормальные
формы – конъюнктивная и дизъюнктивная. В исчислении
предикатов также имеется нормальная форма, называемая
предваренной нормальной формой.
Определение
. Формула F исчисления предикатов находится в
предваренной нормальной форме тогда и только тогда, когда
формула F имеет вид
(Q
1
x
1
)…(Q
n
x
n
)(M),
где каждое (Q
i
x
i
),
n1i ,=
, есть или (∀x
i
) или (∃x
i
), а M есть формула,
не содержащая кванторов. (Q
1
x
1
)…(Q
n
x
n
) называется префиксом, а
M - матрицей формулы F.
Для приведения формулы исчисления предикатов к
Страницы
- « первая
- ‹ предыдущая
- …
- 50
- 51
- 52
- 53
- 54
- …
- следующая ›
- последняя »
