Теория алгоритмов. Зюзысов В.М. - 34 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

теории, выбирается язык с подходящей сигнатурой. Использование языка первого порядка
для записи утверждений, относящейся к данной математической теории, становится
возможным, если все основные понятия теории удается разбить на три категории:
«объекты», «функции» и «предикаты». При этом функции и предикаты должны быть
определены только на объектах, а значениями функций являются только
объекты. В
частности, не допускается рассматривать предикаты, заданные на функциях, или функции,
заданные на предикатах.
2
Затем для некоторых конкретных, замечательных в том или
ином отношении объектов, функций и предикатов, фиксируются их обозначения, которые
и образуют сигнатуру языка.
В математической логике разработаны языки для многих математических теорий.
Два из них играют наиболее важную роль в математике. Это язык формальной
(элементарной) арифметики (о нем речь пойдет в
разделе 5) и язык теории множеств.
Сигнатура языка теории множеств (точнее, языка теории множеств Цермело–
Френкеля) содержит только два двуместных предиката: ∈ (отношение принадлежности)
и = (отношение равенства) и константу ∅ (пустое множество). Вместо ∈(t
1
, t
2
) и = (t
1
, t
2
)
пишут t
1
∈ t
2
и t
1
= t
2
, соответственно. Термами этого языка являются только переменные.
Вот примеры формул языка теории множеств:
1. ∀z (z∈x ⊃ z∈y). Имея в виду естественный подразумеваемый смысл символов
языка, для этой формулы можно ввести сокращенное обозначение x ⊆ y.
2. ¬ (x = y). Эта формула имеет сокращенное обозначение x ≠ y.
3. ¬∃y (y∈x). Эта формула обычно записывается как x =
∅.
Синтаксические свойства истинности теорий с языком первого
порядка
Пусть нам даны некоторая формальная теория T с языком первого порядка и задана
интерпретация этой теории. Через F множество всех формул теории T, истинных в данной
интерпретации. Перечислим те свойства F, которые отражают заложенные в языки
первого порядка логику, независящую от конкретных особенностей интерпретации.
• Для любой замкнутой формулы P, либо
P∈F, либо ¬P∈F.
• Множество F не содержит противоречия, т. е. ни для какой формулы P не может быть,
чтобы одновременно выполнялось P∈F и ¬P∈F.
• Множество F содержит все тавтологии.
• Множество F содержит следующие общезначимые формулы (называемые «логические
аксиомы с кванторами»):
∀x A(
x) ⊃A(t),
где A(t) есть формула теории T и t есть терм теории T, свободный для x в A(x).
Заметим, что t может совпадать с x, и тогда мы получаем аксиому ∀xA(x) ⊃A(x).
∀x (A ⊃ B(x)) ⊃ (A⊃∀x B(x)),
где
A не содержит свободных вхождений переменной x.
• Множество F замкнуто относительно правил вывода modus ponens и обобщения. По
определению это означает, что если A∈F и A⊃B ∈F, то также B∈F; если A∈F, то
∀xA∈F для любой переменной x.
Определение теории первого порядка
Нам понадобится следующее понятие. Пусть дана формула P, свободное
вхождение переменной x в P и терм t. Мы говорим, что данное вхождение x не
2
Из-за этих ограничений язык называется языком логики предикатов первого порядка (или просто языком
первого порядка).

Страницы