Нормальные формулы с предикатами

Определение: предваренная нормальная форма для формулы F называется форма, которая содержит цепочку кванторов: F = K₁x₁,K₂x₂,... K_nx_n (префикс)

М ® матрица, и следующую за ней формулу без квантора.

Любая формула с кванторами может быть преобразована в ПНФ с применением тождественных подстановок:

1) импликация и эквивалентность заменяются дизъюнкцией и конъюнкцией:

Пример: К_х(p(x)®q(x)) º K_x(ùp(x) Ú q(x))

2) применение правила де Моргана для устранения инверсий перед кванторами:

ùVx p(x) = $x ùp(x)

3) применение замены переменных:

K_х p(x) º K_y p(y)

4) применение правил расширения области действия квантора.

Общие формулы расширения области действия:

Kx p(x) Ú Kx p(x) = Kx Ky (p(x) Ú p(y))

Область действия расширяется.

Это справедливо всегда, если кванторы одинаковы (т.е. оба $$ или ""), порядок кванторов любой.

Если кванторы разные:

"х p(x) Ú $x q(x) º "x $y (p(x) Ú q(y))

для одноместных предикатов

кванторы коммутативны

Для многоместных предикатов коммутативность не выполняется. Проверим это:

"x $y p(x,y) º l(i,j) = (a Ú c)(b Ú d) = F

$y"x p(x,y) º l(i,y) = ab Ú cd Þ (a Ú c)(a Ú d)(b Ú c)(b Ú d) = f F

f F ® F

Строго соблюдать порядок применения расширения области действия квантора.

Пример:

"x p(x) Ú $x q(x,y) & "z r(z) = "x p(x) Ú "z($x q(x,y) & r(z)) =

= "z("x p(x) Ú $x q(x,y) & r(z)) = "z("x p(x) Ú $t q(t,y) & r(z)) =

= "z "x(p(x) Ú $t q(t,y) & r(z)) = "z"x$t(p(x) Ú q(t,y) & r(z))

Логический вывод в исчислений предикат.

Исчисление предикат рассматривается, как аксиоматическая теория, в которой может быть выведены все общезначимые формулы.

Аксиомами являются обобщенные схемы Гильберта и Анкермана, а также правила вывода.