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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Другой способ вычисления логических значений состоит в следу-
ющем. Будем обозначать |F |
I
или просто |F | значение формулы F при
заданной интерпретации I. В предположении, что логические значения
формул суть числа 0 или 1, легко проверить, что
|¬A| = 1 − |A|,
|A ∧ B| = |A| · |B| = min(|A|, |B|),
|A ∨ B| = |A| + |B| − |A| ·|B| = max(|A|, |B|),
|A ⇒ B| = 1 −|A| + |A| · |B| =
½
1, если |A| 6 |B|,
0, если |A| > |B|,
|A ⇔ B| = 1 −
¯
¯
¯
|A| − |B|
¯
¯
¯
=
½
1, если |A| = |B|,
0, если |A| 6= |B|.
Пример 3. Найдем логическое значение формулы F
3
=
(A ⇒ B) ⇔ (¬A ∨ B):
|F
3
| = 1 −
¯
¯
¯
|A ⇒ B| − |¬A ∨ B|
¯
¯
¯
= 1 −
¯
¯
¯
(1 − |A| + |A| · | B|) − ((1 − | A|)+
+|B|−(1 −|A|) ·|B|)
¯
¯
¯
= 1 −
¯
¯
¯
(1 −|A|+ |A|·|B|) −(1 −|A|+ |A|·|B|)
¯
¯
¯
= 1,
т.е. формула F
3
всегда истинна.
Формула называется тождественно истинной (или общезначи-
мой) формулой, если она получает значение истина при любой ин-
терпретации. Другое название общезначимой формулы — тавтология.
Общезначимость формулы G обозначается |= G.
Формула называется тождественно ложной формулой (или про-
тиворечием), если ее значение при любой интерпретации — ложь.
Пример 4. Формула A ⇒ A является тавтологией, формула
A∧¬A — противоречием, как показывает следующая таблица значений:
A A ⇒ A A ∧ ¬ A
0 1 0
1 1 0
Формула называется выполнимой, если существует интерпрета-
ция, при которой она истинна (такая интерпретация называется мо-
делью формулы), и опровержимой, если найдется интерпретация, при
которой она ложна. Например, для формулы F
2
(см. пример 2) име-
ется пять моделей, соответствующих строкам с единицей в последней
колонке — одна из них представляет собой интерпретацию I(A, B, C) =
(0, 0, 1); остальные: (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 1).
Упражнение 1. Что является отрицанием высказываний: «Формула F об-
щезначима», «Формула F выполнима»?
10

Страницы