Математическое введение в декларативное программирование. Зюзысов В.М. - 18 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Введение кванторов общности и существования приводит снова к противопостав-
лению свободных и связных вхождений переменной в термы и формулы.
Свободные и связные вхождения переменных
а) Всякое вхождение переменной в элементарную формулу или терм свободно.
б) Всякое вхождение переменной в ¬P или в P Q ( − любая пропозициональная связка)
свободно (соответственно связанно) в точности тогда, когда свободно (соответственно
связано) соответствующее вхождение в P или Q.
в) Всякое вхождение переменной x в ∀xP и ∃xP связано. Вхождение остальных перемен-
ных в ∀xP и ∃xP таковы же, как соответствующие вхождения в P.
Пусть дано вхождение квантора ∀ (или ∃) в формулу P. Из определений следует,
что вслед за ним в P входит переменная и некоторая подформула Q (которая является ли-
бо элементарной формулой либо начинается с открывающей скобкой). Выражение xQ, на-
чинающее с этой переменной и кончающееся соответствующей закрывающей скобкой,
называется областью действия данного (вхождения) квантора.
Теперь мы можем ввести важный класс замкнутых формул. По определению, это –
формулы без свободных переменных. Интуитивный смысл понятия замкнутой формулы
таков. Оно отвечает вполне определенному (в частности, в отношении истинности или
ложности) высказыванию: имена неопределенных объектов теории используются только в
контексте «все объекты x удовлетворяют условию ...» или «существует объект x со свой-
ством ...». Наоборот, незамкнутая формула A(x) или ∃x A(x,y) может быть истинной или
ложной в зависимости от того, какие предметы нарекаются именами x (для первой); y (для
второй). Истинность или ложность понимаются здесь для фиксированной интерпретации
языка.
2.4 Теории с языком первого порядка
2.4.1 Интерпретация
Формулы теории имеют смысл только тогда, когда имеется какая-нибудь интерпре-
тация входящих в них символов.
Если T – теория с языком первого порядка, то можно рассматривать различные ин-
терпретации этой теории. Чтобы определить интерпретацию мы должны задать:
универсум M, называемый областью интерпретации; •
•
•
•
соответствие, относящее
o каждому n-местному предикату некоторое n-местное отношение в M,
o каждой функциональной букве, требующей n аргументов, – некоторую
функцию M
n
→ M и
o каждой константе – некоторый элемент из M;
предметные переменные мыслятся пробегающими область интерпретации M;
логическим связкам придаются их обычный смысл.
Для заданной интерпретации всякая формула P без свободных переменных пред-
ставляет собой высказывание, которое истинно или ложно. Если высказывание является
истинным, то говорят, что формула P выполняется в данной интерпретации.
Всякая формула со свободными переменными выражает некоторое отношение на
области интерпретации; это отношение может быть выполнено (истинно) для одних зна-
чений переменных из области интерпретации и не выполнено (ложно) для других.
Формализация задается не только синтаксисом и семантикой формального языка
(эти компоненты как раз чаще всего берутся традиционными, из хорошо известного край-
не ограниченного набора), но и множеством утверждений, которые считаются истинными.
Именно эта формулировка базисных свойств, аксиом, описывающих некоторую предмет-
18

Страницы