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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Пример 8. Составим таблицу значений формулы F = P (a)∨
∨∀x(P (x) ⇒ Q) на предметной области D = {α, β}. При этом нам
надо исходить из некоторой интерпретации предиката P — логической
функции одной переменной, заданной на D. Таких логических функ-
ций может быть четыре, как в п. 2, b § 2:
x l
1
(x) l
2
(x) l
3
(x) l
4
(x)
α 0 0 1 1
β 0 1 0 1
Помимо выбора |P | из {l
1
, l
2
, l
3
, l
4
}, необходимо также выбрать истин-
ностное значение Q и предметное значение a. (Для экономии места
вместо таблицы с 16 строками, каждая из которых отвечает отдельной
интерпретации, составим таблицу 4 × 4 с двумя входами.)
Q a l
1
l
2
l
3
l
4
(= P )
0 α 1 0 1 1
0 β 1 1 0 1
1 α 1 1 1 1
1 β 1 1 1 1
Так как в логике первого порядка число интерпретаций бесконеч-
но, метод таблиц значений в общем случае неприменим для проверки
формул на общезначимость (или противоречивость). В отдельных слу-
чаях применяются другие средства анализа формул.
3. Свойства кванторов и префиксная
нормальная форма
Помимо основных логических законов (п. 3 § 1), которые сохраня-
ют силу в логике первого порядка, эффективным является использо-
вание свойств кванторов, основные из которых мы сейчас рассмотрим.
Теорема 1. Имеют место следующие логические эквивалентно-
сти:
(1) ∀x∀yF (x, y) ∼ ∀y∀xF (x, y) (перестановка одно-
∃x∃yF (x, y) ∼ ∃y∃xF (x, y) именных кванторов),
(2) ∀xF (x) ∼ ∀yF(y) (переименование
∃xF (x) ∼ ∃yF(y) связанных переменных),
(3) ¬∀xF (x) ∼ ∃x¬F (x)
¬∃xF (x) ∼ ∀x¬F (x) (отрицание кванторов),
64

Страницы