Задача №2.

Найти формулу исчисления предикатов, истинную на алгебраической системе Y и ложную на системе Z .

Y = < N, ∙ > , Z = < Q, ∙ >

РЕШЕНИЕ.

Формулы исчисления предикатов, истинной на алгебраической системе Y и ложной

на системе Z не существует. Так как

Y = < N, ∙ > , Z = < Q, ∙ > - группы без кручения. Имеют одинаковые множества

выполнимых формул И.П., т.е. они элементарно эквивалентны.

Задача №3.

Построить доказательство формулы в исчислении предикатов.

( х Р(х) Λ х Q(х)) ↔ х ( Р(х) Λ Q(х))

РЕШЕНИЕ.

Построим доказательство по правилам вывода.

Пусть

Р(х) = φ

Q(х) = ψ

φ ├ φ ; ψ ├ ψ φ ├ φ ; ψ ├ ψ

13 12

φ ├ х φ ; ψ ├ х ψ φ, ψ ├ φ ; φ, ψ ├ ψ

12 1

φ, ψ ├ х φ ; φ, ψ ├ х ψ φ, ψ ├ φ Λ ψ

1 13

φ, ψ ├ х φ Λ х ψ φ, ψ ├ х (φ Λ ψ)

х φ Λ х ψ ├ х (φ Λ ψ)

φ ├ φ ; ψ ├ ψ φ ├ φ ; ψ ├ ψ

12 13

φ, ψ ├ φ ; φ, ψ ├ ψ φ ├ х φ ; ψ ├ х ψ

1 12

φ, ψ ├ φ Λ ψ φ, ψ ├ х φ ; φ, ψ ├ х ψ

13 1

φ, ψ ├ х (φ Λ ψ) φ, ψ ├ х φ Λ х ψ

х (φ Λ ψ) ├ х φ Λ х ψ

Задача №4. Установить, выполнима ли следующая формула и если выполнима, то построить модель этой формулы .

х у ( х ∙ S (у) = S ( х ∙ у )) Λ х у ¬ ( х ∙ у = у ∙ х )

РЕШЕНИЕ.

Проверим выполнимость формулы с помощью метода резолюций.

х у ( х ∙ S (у) = S ( х ∙ у )) Λ х у ¬ ( х ∙ у = у ∙ х )

х у ( х ∙ S (у) = S ( х ∙ у )) Λ ¬ ( С₁ ∙ С₂ = С₂ ∙ С₁ )

Рассмотрим множество дизъюнктов:

{ х ∙ S (у) = S ( х ∙ у ); ¬ ( С₁ ∙ С₂ = С₂ ∙ С₁ ) }

res ( 1,2 ) = 0

c₁ /x; c₂ /S(y); c ₂ ∙ c₁/S(x ∙ y)

Так как существует резолютивный вывод нуля, то формула невыполнима.

Задача №5.

Привести к пренексной и клазуальной нормальной формам следующую формулу.

¬(( х у Р(х,у) v х у (х,у)) v х у R(х,у)

РЕШЕНИЕ.

¬(( х у Р(х,у) v х у (х,у)) v х у R(х,у)

(¬( х у Р(х,у) Λ ¬( х у (х,у)) v х у R(х,у)

х у ¬Р(х,у) Λ х у ¬ (х,у)) v х у R(х,у)

х ( у ¬Р(х,у) Λ у ¬ (х,у)) v х у R(х,у)

х z u (( ¬Р(х,z) Λ у ¬ (х,у)) v у R(u,у))

х z u y (( ¬Р(х,z) Λ ¬ (х,у)) v R(u,у)) – пренексная форма.

х z u y (( ¬Р(х,z) v R(u,у)) Λ (¬ (х,у) v R(u,у)) – клазуальная форма.