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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

(4) G ∧ ∀xF (x) ∼ ∀x(G ∧ F (x))
G ∨ ∀xF (x) ∼ ∀x(G ∨ F (x))
G ∧ ∃xF (x) ∼ ∃x(G ∧ F (x)) (вынесение кванторов
G ∨ ∃xF (x) ∼ ∃x(G ∨ F (x)) за скобки),
(5) ∀xF (x) ∧ ∀xG(x) ∼ ∀x(F (x) ∧ G(x)) (группирование
∃xF (x) ∨ ∃xG(x) ∼ ∃x(F (x) ∨ G(x)) кванторов)
для произвольных формул F и G при условии, что в формулах (4) G
не содержит свободных вхождений переменной x, а в формулах (2) y
не свободна в F (x), но свободна для x в F (x).
Согласно определению логической эквивалентности, нам необхо-
димо показать, что во всякой расширенной интерпретации, в которой
выполнена одна из частей эквивалентности, выполнена и другая.
Для доказательства эквивалентностей (1) достаточно заметить,
что их левая и правая части одновременно выполнены в расширенной
интерпретации, в которой F (x, y) выполнено при всех возможных зна-
чениях x и y — для случая ∀ (при некоторых значениях x и y — для
случая ∃).
Соотношения (2) следуют из того, что процедура проверки вы-
полнения ∀xF (x) относится к переменной x в F (x), а ∀yF (y) — к пере-
менной y в F (y), что дает один и тот же результат. То же справедливо
для случая ∃.
Докажем первую из эквивалентностей (3). Выполнение ¬∀xF (x)
означает, что не при всех возможных значениях x выполнено F (x),
т.е. при некотором |x| ∈ D имеет место |F (|x|)| = 0. Но то же самое
выражает выполнение ∃x¬F (x): при некотором |x| ∈ D имеет место
|¬F (|x|)| = 1.
Вторая эквивалентность следует из первой и из закона двойного
отрицания: ¬∃xF (x) ∼ ¬∃x¬¬F (x) ∼ ¬¬∀x¬F (x) ∼ ∀x¬F (x).
Упражнение 3. Докажите эквивалентности (4) и (5).
Заметим, что если унарный предикат P (x) определен на конеч-
ном множестве D = {a
1
, . . . , a
n
}, то ∀xP (x) ∼ P (a
1
) ∧ . . . ∧ P(a
n
), а
∃xP (x) ∼ P (a
1
) ∨ . . . ∨ P (a
n
). В общем случае кванторы общности
и существования можно понимать как «бесконечную конъюнкцию» и
«бесконечную дизъюнкцию». Тогда соотношения (3) оказываются обоб-
щениями законов Де Моргана, а соотношения (5) — обобщениями свой-
ства произвольного группирования членов конъюнкции (дизъюнкции).
Упражнение 4. Покажите, что ∀xF (x)∨∀xG(x) ∀x(F (x)∨G(x)) и ∃xF (x)∧
∧∃xG(x) ∃x(F (x) ∧ G(x)).
Пользуясь соотношениями (1)–(5), мы можем производить экви-
валентные преобразования над формулами логики первого порядка, в
65

Страницы