Математическая логика и теория алгоритмов. Стенюшкина В.А. - 37 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

Пример – Имеется формула ∀ x ∃ y ∃ z (( Р (x, y) ∧ Q (x, z))∨ R (x, y, z).
Ее ССФ может выглядеть так:
∀ x (( Р(x, f(x) ) ∨ R (x), g(x))) ∧ Q (x, g(x)) ∨ R
(x, f(x), g(x)))), которую можно представить множеством
 Р (x, f(x)) ∨ R (x,
f(x), g(x)), Q (x, g(x))
∨ R (x, f(x), g(x)).
Следующая теорема – основа метода.
Теорема Пусть S – множество дизъюнктов, которые представляют стан-
дартную форму формулы F. Тогда F противоречива тогда и только тогда , ког-
да S противоречива. 
       Пример – Имеется формула ∀ x ∃ y ∃ z (( Р (x, y) ∧ Q (x, z))∨ R (x, y, z).
Ее ССФ может выглядеть так: ∀ x (( Р(x, f(x) ) ∨ R (x), g(x))) ∧ Q (x, g(x)) ∨ R
(x, f(x), g(x)))), которую можно представить множеством  Р (x, f(x)) ∨ R (x,
f(x), g(x)), Q (x, g(x)) ∨ R (x, f(x), g(x)).
       Следующая теорема – основа метода.
       Теорема Пусть S – множество дизъюнктов, которые представляют стан-
дартную форму формулы F. Тогда F противоречива тогда и только тогда , ког-
да S противоречива.

Страницы