ВУЗ:
Составители:
Рубрика:
53
предваренной нормальной форме рассмотрим ряд
эквивалентностей, содержащих кванторы.
Пусть F - формула, содержащая свободную переменную x
(обозначим этот факт как F[x]). Пусть G -формула, не содержащая
переменную x. Пусть Q есть или
∀ или ∃ . Тогда имеют место
следующие эквивалентности:
)][)((][)( GxFQxGxFQx
∨=∨ (12.1)
)][)((][)( GxFQxGxFQx
∧
=∧ (12.2)
][)(][)( xFxxFx ∃=∀ (12.3)
][)(][)( xFxxFx ∀=∃ (12.4)
Эквивалентности (12.1) и (12.2) очевидны, т.к. G не содержит x
и, следовательно, может быть внесена в область действия квантора
Q. Докажем эквивалентности (12.3) и (12.4). Пусть I -
произвольная интерпретация с областью D . Если
][)( xFx∀
истинна в I, то (
∀x)F[x] ложна в I. Это означает, что существует
такой элемент e в D, что F[e] ложна, т.е.
][eF истинна в I.
Следовательно,
][)( xFx∃ истинна в I. С другой стороны, если
][)( xFx∀ ложна в I, то (∀x)F[x] истинна в I. Это означает, что F[x]
истинна для каждого элемента x в D, т.е.
][xF ложна для каждого
элемента x в D. Следовательно,
][)( xFx∃ ложна в I. Т.к. ][)( xFx∀
и
][)( xFx∃ всегда принимают одно и то же истинностное значение
при произвольной интерпретации, то по определению
][)(][)( xFxxFx ∃=∀ . Таким образом (12.3) доказано. Аналогично
можно доказать и (12.4).
Предположим далее, что F[x] и H[x] - две формулы,
содержащие свободную переменную x . Нетрудно доказать, что
(
∀x)F[x] ∧ (∀x)H[x] = (∀x)(F[x] ∧H[x]), (12.5)
(
∃x)F[x] ∨ (∃x)H[x] = (∃x)(F[x] ∨ H[x]), (12.6)
т.е. квантор всеобщности
∀ и квантор существования ∃ можно
распределять по
∧
и
∨
соответственно.
Однако
∀ и ∃ нельзя распределять по
∨
и
∧
соответственно, т.е.
Страницы
- « первая
- ‹ предыдущая
- …
- 51
- 52
- 53
- 54
- 55
- …
- следующая ›
- последняя »
