Читайте также:
|
До сих пор мы рассматривали синтаксис языков первого порядка, то
есть точные правила для построения термов, формул, задания аксиом и
теорем. Наряду с синтаксическим аспектом будем рассматривать семан-
тический аспект теории. Переход от синтаксиса к семантике совершается
тогда, когда вместо функциональных и предикатных символов, рассмат-
риваемых как буквы и только, мы начинаем изучать конкретные функции
и предикаты на некотором множестве M. Множество M будем называть
универсумом, а его элементы – индивидами.
Представим, что мы рассматриваем одну из теорий первого порядка—
теорию групп и изучаем семантический аспект. Следовательно, мы долж-
ны рассмотреть конкретную группу. Это означает, что нужно задать кон-
кретное множество, элементы которого являются элементами группы, ко-
торую мы представляем. Вместо бинарного предикатного символа ·, рас-
сматриваемой как знак в языке теории групп, мы должны ввести кон-
кретное умножение на множестве M. В общем случае мы должны вместо
функциональных символов f, g, h,... рассматривать конкретные функции
на множестве M. Вместо предикатных символов p, q, нужно рассмотреть
конкретные предикаты на множестве M.
Сформулируем обсуждаемые понятия более точно.
Структура для языка первого порядка. Пусть L — язык первого
порядка. Структура A для языка L состоит из следующего.
1. Непустого множества M, называемого универсумом структуры A
(элементы из M называются индивидами структуры);
2. n -арной функции fA из M в M для каждого n -арного функциональ-
ного символа f из L;
3. n -арного предиката pA на M для каждого n -арного предикатного
символа p из L, отличного от =.
Напомним определение функций и предикатов, кото-
рое мы применяем. Пусть M — некоторое множество и
Mn = M ×... × M — n -ая степень множества M. Элемен-
тами Mn являются всевозможные строки (a 1 ,..., an), то есть
Mn = { (a 1 ,..., an) | ai ∈ M}.
Если f —некоторая n -арная функция на множестве M, то она являет-
ся сопоставлением (a 1 ,..., an) _→ a ∈ M. Таким образом, a 1 ,..., an —
значения аргумента, a —значение функции, т.е. f (x 1 ,..., xn) = a при
x 1 = a 1 ,..., xn = an. Аргументы и значения функции берутся из одно-
го и того же множества M.
n -арным предикатом на множестве M называется произвольное под-
множества R из декартова произведения Mn = M × M × M... × M.
Если (a 1 ,..., an) ∈ R, то говорят, что элементы a 1,..., an находится в
отношении R. При n = 2 записываем a 1 R a 2.
Поскольку мы имеем конкретные функции и предикаты на множестве,
то мы сможем приписывать нашим формулам значения истина или ложь.
Вформуле A заменяем значения переменных на конкретные индивиды из
M и приписываем формуле значение Иили Л (истина или ложь). При
этом мы будем говорить, что формула A была истинна в A, если все ее
значения истинны.
Пример. Рассмотрим формулу x + y = 3. Возьмем в качестве универ-
сума множество натуральных чисел, функциональный символ + истол-
ковываем как обычное сложение. Заменяем значение переменной x на 2,
а значение переменной y на 1. Значения формулы равно И. При x = 2,
y = 3 значение формулы равно Л.
Опишем процедуру приписывания значение формуле A более точно.
Пусть L — язык первого порядка и A – структура для языка L с уни-
версумом M, n -арными функциями fA, gA,... и n -арными предикатами
pA, qA,...
Заменим произвольным образом значения переменных x, y, ... языка L
на конкретные индивиды a, b, ... из M
x = a, y = b,... (29)
По существу это равенство задает отображение переменных языка пер-
вого порядка L в универсум M. Назовем такое отображение интерпрета-
цией.
Рассмотрим произвольный терм u. Он имеет запись fu 1 u 2 un, где
u 1 ,..., un — ранее построенные термы и f – n -арный функциональный
символ. По теореме об однозначности построения терма части u 1 ,..., un
определены однозначно. Далее разберем однозначно на части каждый
из термов u 1 ,..., un и т.д. В результате получим сборку u из его ча-
стей. Части, с которых начинается сборка терма u имеют некоторый вид
g (x 1, x 2 ,...), где x 1, x 2 ,... — переменные. Они должны заменяться на
конкретные индивиды a 1, a 2 ,... из M в соответствие с интерпретацией
(29). В терме g (x 1, x 2 ,...) заменим функциональный символ g на функцию
gA, а переменные x 1, x 2 ,... на a 1, a 2 ,.... Получим индивид gA (a 1, a 2 ,...)
из M. Подставим это значение в качестве аргумента в следующий терм,
участвующий в сборке терма u. Повторив действие несколько раз, полу-
чим значение a ∈ M терма u при интерпретации (29).
Рассмотрим атомную формулу p (u 1, u 2 ,..., un), где p – n -арный пре-
дикатный символ. Заменим символ p на предикат pA, т.е. на некоторое
подмножества R из декартова произведения Mn = M ×M ×M... ×M.
При интерпретации (29) вместо термов u 1, u 2 ,..., un получатся элементы
a 1 ,..., an из M.
Если n -ка элементов (a 1 ,..., an) содержится в R, то приписываем
атомной формуле p (u 1 ,..., un) значение И, в противном случае – значе-
ние Л.
Рассмотрим процесс приписывания значений И,Л произвольной фор-
муле X.
Напомним, что
1. Атомная формула является формулой
2. Если A и B - произвольные формулы, то ￢A, ∨AB - формулы.
3. Если A - формула, то ∃xA - формула
4. Выражение является формулой тогда и только тогда, когда оно по-
лучено несколькими применениями правил 1-3.
По теореме построения сборка формулы X из ее частей A, B, ... одно-
значна. Исходный элемент для сборки формулы X —атомные формулы.
При каждой интерпретации (29) атомная формула принимает значение И
или Л. Поэтому нужно лишь указать, как вычислять значение формулы
Y из значений ее частей при построениях вида (2), (3),(4). Обозначаем
значение произвольной формулы Y через V(Y).
• Пусть Y = ￢A. Тогда значение формулы Y противоположно значе-
нию формулы A, т.е. V (Y) = ￢V (A) (если V (A) =И, то V (Y) =–Л
и наоборот);
• Пусть Y = A ∨ B. Тогда V (Y) = V (A) ∨ V (B).
• Пусть Y = ∃xA. Наряду с интерпретацией (29), рассматриваем ин-
терпретации, где значения переменных, отличных от x, те же, что и
в интерпретации (29). Эти значения переменных, отличных от x, со-
четаем с произвольным выбором x = a, x = b, ... и вычисляем зна-
чение формулы A. Если хотя бы один раз получается значение И,
то формуле Y = ∃xA приписываем значение И, в противном случае
приписываем значение Л.
Пусть T — теория с языком L и A — структура для языка первого
порядка. Тем самым задан универсум M, заданы n -арные функции fA и
n -арные предикаты pA для каждого n -арного функционального символа
f для каждого n -арного предикатного символа p из L. При каждой ин-
терпретации каждая формуле принимает значение Иили Л.
ОПРЕДЕЛЕНИЕ 11 Формула A теории T, называется истинной
в структуре A если при каждой интерпретации формула A при-
нимает значение И.
Структура A для языка L теории T называется моделью теории T, если
при каждой интерпретации все нелогические аксиомы из T принимают
значение И.
Другими словами структура A для языка L теории T —модель теории
T, если все нелогические аксиомы из T истинны в структуре A.
В определении речь идет лишь о нелогических аксиомах, т.к. логиче-
ские аксиомы истинны в любой структуре.
ТЕОРЕМА 14 Пусть A структура для языка L теории T и X —
логическая аксиома теории T. Тогда X истинна в A.
Доказательство. По определению логическая аксиома X имеет один из
видов:
пропозициональная аксиома ￢A ∨ A;
аксиома равенства, имеющая один из видов a) или б)
a) x 1 = y 1 → x 2 = y 2 →· · ·→fx 1 ...xn = fy 1 ...yn,
б) x 1 = y 1 → x 2 = y 2 →· · ·→px 1 ...xn = py 1 ...yn;
аксиома подстановки Ax [ u ] → ∃xA;
аксиома тождества x = x.
Рассмотрим произвольную интерпретацию, т.е. заменим значения пере-
менных x, y, ... на конкретные индивиды a, b, ... из M; x = a, y = b, ....
Вычислим истинностное значение V (X) формулы X.
1 случай, X = ￢A∨A. Тогда V (X) = ￢V (A) ∨ V (A). Если истинност-
ное значение V (A) формулы A равно И, то V (X) = ￢V (A) ∨ И=И. Если
V (A)=Л, то V (X) = ￢ Л ∨V (A) =И ∨V (A)= И.
В случае 2, предположим противное, т.е. при некоторой замене в фор-
мула X значений переменных: x 1 = a 1, y 1 = b 1 ,... истинностное зна-
чение V (X) равно Л. Тогда посылка a 1 = b 1 истинна, а заключение
a 2 = b 2 → · · · → f (a 1 ...an) = f (b 1 ... bn) ложно (напомним, что A → B
–сокращение для ￢A ∨ B и, поэтому, имеет такое правило для приписы-
вания И, Л).
Получили совпадение элементов a 1 и b 1. Аналогично получаем a 2 =
b 2 ,.... и ложность равенства f (a 1 ...an) = f (b 1 ... bn).
Тогда совпадение элементов a 1 = b 1, a 2 = b 2 ,... влечет совпадение
значений функции f (a 1 ...an) = f (b 1 ...), противоречие с допущением
f (a 1 ...an) _ = f (b 1 ... bn)
В случае 2 б) поступаем аналогично.
Случай 3, X имеет вид Ax [ a ] → ∃xA. Предположим противное, т.е. при
некоторой интерпретации формула X имеет значение Л. Тогда V (Ax [ u ])
равно И, V (∃xA) равно Л. Терм u при заменяется при интерпретации на
некоторый элемент a ∈ M. Замена x на этот элемент приводит к значе-
нию V (Ax [ a ]) равному И. Итак, существует значение переменной x, ко-
торое которое вместе со значениями переменных, отличных от x, таково,
что значение V (A равное И. Тогда значение формулы V (∃xA) равно И,
что противоречит допущению.
Случай 4, X имеет вид x = x. Подставим индивид a переменной x.
Получим a = a.
Предикат= по своему определению должен быть таковым, что резуль-
тат замены a = a имеет значение И. Теорема доказана.
Дата добавления: 2015-01-12; просмотров: 130 | Поможем написать вашу работу | Нарушение авторских прав |