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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Это можно записать как |F
1
|, . . . , |F
n
| 6 |G|, или |F
1
∧ . . . ∧ F
n
| 6 |G|,
что равносильно общезначимости формулы F
1
∧ . . . ∧ F
n
⇒ G.
Еще один способ проверки логического следования заключается
в рассуждении от противного.
Теорема 5. F
1
, . . . , F
n
|= G тогда и только тогда, когда формула
F
1
∧ . . . ∧ F
n
∧ ¬G тождественно ложна.
Действительно, ¬(F
1
∧ . . . ∧ F
n
∧ ¬G) ∼ ¬(F
1
∧ . . . ∧ F
n
) ∨ G ∼
∼ F
1
∧ . . . ∧ F
n
⇒ G.
Пример 7. Проверим логическое следование
A ⇒ (B ⇒ C), ¬A ⇒ ¬D |= B ∧ D ⇒ C .
Предположим, что конъюнкция формул A ⇒ (B ⇒ C), ¬A ⇒ ¬D
и отрицания формулы B ∧ D ⇒ C выполнима. Тогда должно быть
|A ⇒ (B ⇒ C)| = 1, |¬A ⇒ ¬D| = 1 и |B ∧ D ⇒ C| = 0. Из последнего
равенства заключаем, что |C| = 0, |B| = |D| = 1, а из первого равенства
(поскольку теперь ясно, что |B ⇒ C| = 0) следует |A| = 0. Подстав-
ляя найденные значения во второе равенство, получим противоречие:
|¬A ⇒ ¬D| = 0.
Теорема 6. F ∼ G тогда и только тогда, когда F |= G и G |= F .
Вытекает из закона эквивалентности.
Логическое следование допускает ясное описание с помощью со-
вершенных нормальных форм.
Теорема 7. Если F и G — формулы в СДНФ от одних и тех же
переменных, то F |= G тогда и только тогда, когда множество дизъ-
юнктивных членов F содержится в множестве дизъюнктивных членов
G.
Согласно следствию 2 из теоремы 1 § 2, каждый дизъюнктивный
член в СДНФ соответствует некоторому единичному набору для F.
По определению логического следования, каждый единичный набор
для F должен быть единичным набором и для G. Отсюда вытекает
заключение теоремы.
Теорема 8. Если F и G — формулы в СКНФ от одних и тех же
переменных, то F |= G тогда и только тогда, когда множество конъ-
юнктивных членов F содержит множество конъюнктивных членов G.
Согласно следствию 2 из теоремы 3 § 2, каждый конъюнктивный
член в СКНФ соответствует некоторому нулевому набору для F . Из
определения логического следования можно заключить, что каждый
26

Страницы