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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Очевидно, что формула общезначима тогда и только тогда, когда
она не опровержима, и выполнима тогда и только тогда, когда она не
противоречива.
Если формула F истинна в интерпретации I, то говорят, что I есть
модель формулы F ( |=
I
F ). Формула G называется логическим след-
ствием формул F
1
, . . . , F
n
, если для всякой расширенной интерпрета-
ции, в которой выполнены F
1
, . . . , F
n
, выполнена и G (F
1
, . . . , F
n
|= G).
Формулы F и G называются (логически) эквивалентными, если каж-
дая из них является логическим следствием другой (F ∼ G).
Пример 6. Докажем общезначимость формулы
F = P (f(x)) ⇒ ∃xP (x).
Рассмотрим произвольную интерпретацию I. Формула F в ней бу-
дет истинна, если в каждом ее расширении либо не выполнено P (f(x)),
либо выполнено ∃xP (x). Но, если P (f(x)) выполнено при некотором
значении |x| переменной x, то существует элемент предметной обла-
сти, равный |f(|x|)|, который обладает свойством P , и, следовательно,
выполнено ∃xP (x).
Пример 7. Пусть F
1
= ∀x(P (x) ⇒ Q(x)) и F
2
= P (a). Докажем
логическое следование F
1
, F
2
|= Q(a).
Рассмотрим любую расширенную интерпретацию, в которой вы-
полнены формулы F
1
и F
2
. В ней, очевидно, |P (a)| = 1. Из |F
1
| = 1
вытекает, что |P (x) ⇒ Q(x)| = 1, каким бы ни было значение x. Выби-
рая |x| = |a|, получим |P (a) ⇒ Q(a)| = 1 и, следовательно, |Q(a)| = 1.
63

Страницы