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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Функцией арности n будем называть отображение, ставящее в
соответствие списку из n констант некоторую константу. Совершен-
но аналогично предикат — это отображение, ставящее в соответствие
списку констант истинностное значение {истина, ложь}.
Пример 1. E(x), «x — четное число» — унарный (одноместный)
предикат; P (x, y), «прямые x и y параллельны» — бинарный (двумест-
ный) предикат; S(x, y, z), «z = x + y » — тернарный (трехместный)
предикат.
Определение 1. Терм определяется рекурсивно следующим об-
разом:
1) всякая предметная константа есть терм;
2) всякая предметная переменная есть терм;
3) если f — n-арный функциональный символ и t
1
, t
2
, . . . , t
n
—
термы, то f(t
1
, t
2
, . . . , t
n
) — терм.
Определение 2. Если P — n-арный предикатный символ и
t
1
, t
2
, . . . , t
n
— термы, то P (t
1
, t
2
, . . . , t
n
) — атом (элементарная фор-
мула).
Определение 3. Формула определяется рекурсивно следующим
образом:
1) всякий атом есть формула;
2) если G и H — формулы, то (¬G), (G ∧ H), (G ∨ H),
(G ⇒ H), (G ⇔ H) — формулы;
3) если F — формула и x — предметная переменная, то (∀xF )
и (∃xF ) — формулы.
Пример 2. Пусть g, h, f — соответственно унарный, бинар-
ный и тернарный функциональные символы;
Q
и
P
— унарный и
бинарный предикатные символы. Тогда f(g(x), h(a, g(y)), z) — терм,
P (x, h(a, g(y))) — атом, ∀x(∃yP (x, y) ⇒ Q(x)) — формула.
Для опускания избыточных скобок в формулах будем пользовать-
ся соглашением, что кванторы обладают наивысшим приоритетом в
связывании выражений. Например, запись ∀xF ∨ G в полной форме
выглядит как ((∀xF ) ∨G).
В формулах ∀xF и ∃xF подформула F называется областью дей-
ствия квантора ∀ (∃). Вхождение переменной x в формулу называется
связанным, если оно является вхождением в кванторный комплекс ∀x
или ∃x или находится в области действия квантора; в противном случае
вхождение переменной называется свободным.
Переменная x свободна в формуле F , если хотя бы одно вхождение
x в F свободно. Переменная x связана в формуле F , если хотя бы одно
вхождение x в F связано.
59

Страницы