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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

∼ (A ∨ B) ∧ (A ∨ ¬B) ∧ (B ∨ A) ∧ (B ∨ ¬A) ∼
∼ (A ∨ B) ∧ (A ∨ ¬B) ∧ (¬A ∨ B).
Упражнение 3. Что можно сказать относительно формулы A∧B — находится
ли она в ДНФ, КНФ, СДНФ? Почему это не СКНФ?
4. Логическое следование
Рассмотрим приложения совершенных нормальных форм к поня-
тию логического следования.
Пусть F
1
, . . . , F
n
, G — логические формулы. Будем говорить,
что G логически следует из F
1
, . . . , F
n
, если в любой интерпретации,
при которой истинны все формулы F
1
, . . . , F
n
, формула G также ис-
тинна. Для логического следования будем использовать обозначение
F
1
, . . . , F
n
|= G. Это согласуется с обозначением |= G, которое мы при-
няли для тождественно истинной формулы. Формулы F
1
, . . . , F
n
назы-
ваются посылками следствия G.
Всегда можно проверить, является ли G следствием из F
1
, . . . , F
n
,
составив общую таблицу значений.
Пример 6. Проверим, что A ⇒ B, A ⇒ C |= A ⇒ B ∧ C :
F
1
F
2
G
A B C B ∧ C A ⇒ B A ⇒ C A ⇒ B ∧ C
0 0 0 0 1 1 1
0 0 1 0 1 1 1
0 1 0 0 1 1 1
0 1 1 1 1 1 1
1 0 0 0 0 0 0
1 0 1 0 0 1 0
1 1 0 0 1 0 0
1 1 1 1 1 1 1
Действительно, во всех строках, в которых на пересечении со
столбцами, соответствующими F
1
и F
2
, стоят 1 (первые четыре стро-
ки и последняя строка), на пересечении с последним столбцом тоже
стоит 1.
Теорема 4. Логическое следование F
1
, . . . , F
n
|= G имеет место
тогда и только тогда, когда |= F
1
∧ . . . ∧ F
n
⇒ G.
/ Согласно определению, F
1
, . . . , F
n
|= G означает, что для каждой
интерпретации I имеет место следующее:
если |F
1
| = . . . = |F
n
| = 1, то |G| = 1.
25

Страницы