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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

члены в конъюнкции и дизъюнкции, опускать скобки в выражениях
вида (A ∨ B) ∨ C и A ∧ (B ∧ C), раскрывать скобки и т.д. Рассмотрим
теперь средства получения новых эквивалентностей.
Теорема 2. Если |= F и |= F ⇒ G, то |= G.
Зафиксируем произвольную интерпретацию I. По условию |F | =
1 и |F ⇒ G| = 1, т.е. |F | 6 |G|. Отсюда заключаем, что |G| = 1.
Теорема 3. F ∼ G тогда и только тогда, когда формулы F и G
имеют одинаковые таблицы значений.
Если F ∼ G, то при любой интерпретации I имеем |F ⇔ G|
I
= 1,
т.е. |F |
I
= |G|
I
. Справедливо и обратное.
Пример 5. Запишем закон импликации в виде A ⇒ B ∼ ¬A ∨
B. Для его доказательства, согласно теореме 3, достаточно проверить
совпадение таблиц истинности формул A ⇒ B и F = ¬A ∨ B:
A B A ⇒ B ¬A F
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 1 0 1
Упражнение 3. Проверьте аналогичным образом другие логические законы.
Теорема 4. Если F ∼ G и G ∼ H, то F ∼ H.
Действительно, в силу теоремы 3 все три формулы F , G и H
должны иметь одинаковые таблицы истинности.
Вместе с очевидными свойствами: a) F ∼ F, b) если F ∼ G, то
G ∼ F , теорема 4 означает, что логическая эквивалентность определя-
ет на множестве всех логических формул отношение эквивалентности.
В частности, из теоремы 4 непосредственно вытекает правило цепи эк-
вивалентностей:
Если F
1
∼ F
2
, F
2
∼ F
3
, . . . , F
n−1
∼ F
n
, то F
1
∼ F
n
.
В данном случае обычно используют запись F
1
∼ F
2
∼ F
3
∼ . . . ∼ F
n
и говорят, что формула F
n
получена из F
1
эквивалентными преобразо-
ваниями.
Упражнение 4. Сформулируйте и докажите правило цепи импликаций, со-
ответствующее принятой в математике записи F
1
⇒ F
2
⇒ F
3
⇒ . . . ⇒ F
n
. Исполь-
зуйте теорему 2.
Пусть F — формула, содержащая атом A. Обозначим F
A
H
фор-
мулу, получаемую из F подстановкой вместо A (всякий раз, когда A
встречается) формулы H, становящейся, таким образом, подформулой
в F
A
H
.
12

Страницы