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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

x, один унарный функциональный символ f, один унарный предикат-
ный символ P и один бинарный предикатный символ Q. В качестве
предметной области D возьмем множество из двух элементов {α, β}.
Зададим интерпретацию I таблицами
a x f(x) x P (x) x y Q(x, y)
α α β α 0 α α 1
β α β 1 α β 1
β α 0
β β 1
Рассмотрим подформулу F
1
= (P (x) ⇒ Q(f(x), a)) и расширение ин-
терпретации I при помощи присваивания значений переменной x.
Если |x| = α, то |F
1
| = |P (α) ⇒ Q(f(α), α)| = | 0 ⇒ Q(β, α)| = 1.
Если |x| = β, то |F
1
| = |P (β) ⇒ Q(f(β), β)| = |1 ⇒ Q(α, β)| = 1.
Так как F
1
истинно для всех расширений I, затрагивающих x, то фор-
мула F истинна в интерпретации I.
Упражнение 2. Докажите следующие утверждения:
1) никакая формула не может быть одновременно истинной и ложной в одной
и той же интерпретации;
2) формула F истинна в данной интерпретации тогда и только тогда, когда в
этой интерпретации истинно ∀x
1
. . . ∀x
n
F , где x
1
, . . . , x
n
— все свободные перемен-
ные формулы F (формула ∀x
1
. . . ∀x
n
F называется замыканием формулы F );
3) формула F , полученная из тавтологии логики высказываний подстановкой
вместо ее атомов произвольных формул, истинна в любой интерпретации;
4) если свободные переменные формулы F содержатся среди переменных
x
i
1
, . . . , x
i
n
и у последовательностей s и s
0
компоненты с номерами i
1
, . . . , i
n
сов-
падают, то формула F выполнена на I
s
тогда и только тогда, когда она выполнена
на I
s
0
;
5) если формула F замкнута, то в любой интерпретации F либо истинна, либо
ложна.
Замкнутая формула хотя и принимает в любой интерпретации
определенное истинностное значение, но в одних интерпретациях мо-
жет быть истинной, а в других — ложной. Незамкнутая формула может
в некоторой интерпретации быть не истинной и не ложной.
Формула F называется:
— общезначимой, если она истинна в каждой интерпретации
( |= F );
— противоречивой, если ¬F является общезначимой или, что то
же самое, если F ложна в каждой интерпретации;
— выполнимой, если существует расширенная интерпретация, в
которой она выполнена;
— опровержимой, если существует расширенная интерпретация,
в которой выполнено ¬F .
62

Страницы