Элементы математической логики. Фролов И.С. - 67 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

частности, с целью получить равносильную формулу, имеющую осо-
бенно простой вид.
Определение 5. Говорят, что формула F находится в пре-
фиксной нормальной форме (сокращенно ПНФ), если она имеет вид
Q
1
x
1
. . . Q
n
x
n
M, где каждое Q
i
x
i
(1 6 i 6 n) есть ∀x
i
или ∃x
i
, а M —
формула, не содержащая кванторов. Q
1
x
1
. . . Q
n
x
n
называется префик-
сом, а формула M — матрицей формулы F .
Теорема 2. Всякая формула логики первого порядка эквива-
лентна некоторой формуле в префиксной нормальной форме.
Для преобразования формулы к ПНФ:
1) используем законы эквивалентности и импликации, чтобы ис-
ключить логические связки ⇒ и ⇔;
2) повторно используем закон двойного отрицания, законы Де
Моргана и свойство (3), чтобы внести символы отрицания внутрь фор-
мулы, до атомов;
3) переименовываем связанные переменные (свойство (2)), если
это необходимо;
4) выносим кванторы за скобки путем применения свойства (4), а
также свойств (5) и (1), они могут дать некоторую экономию кванторов.
Очевидно, что описанная процедура всегда за конечное число ша-
гов приводит к эквивалентной формуле, находящейся в ПНФ.
Пример 9. Приведем формулу ∀xP (x) ⇒ ∃xQ(x) к ПНФ:
∀xP (x) ⇒ ∃xQ(x) ∼ ¬∀xP (x) ∨ ∃xQ(x) ∼ ∃x¬P (x) ∨ ∃xQ(x) ∼
∼ ∃x(¬P (x) ∨ Q(x)).
Вот еще один пример:
∃xP (x, y) ⇒ ∃zQ(x, z) ∼ ¬∃xP (x, y) ∨ ∃zQ(x, z) ∼ ∀x¬P (x, y)∨
∨∃zQ(x, z) ∼ ∀t¬P (t, y) ∨ ∃zQ(x, z) ∼ ∀t(¬P (t, y) ∨ ∃zQ(x, z)) ∼
∼ ∀t∃z(¬P (t, y) ∨ Q(x, z)).
Здесь потребовалось переименовать связанную переменную x, по-
скольку она в данной формуле имела, помимо связанного, также и сво-
бодное вхождение — чтобы после вынесения квантора за скобку это
свободное вхождение не превратилось бы в связанное.
66

Страницы