Основные равносильности для предикатов

⇐ ПредыдущаяСтр 3 из 6Следующая ⇒

Для нас имеют смысл и значение только интерпретированные предикаты. То есть предикаты, которым поставлены в соответствия некоторые отношения (одномерным предикатам – свойства). В результате, предикаты дают некоторые содержательные высказывания относительно объектов рассматриваемых областей. Если соответствующее высказывание истинно, то говорят, что оно выполняется в данной интерпретации.

Предикат называется общезначимым, если он истинен в любой интерпретации.

1. " x P(x) º $x P(x)

2.$x P(x) º " x P(x)

3. " x P(x) º $x P(x)

4. $x P(x) º " x P(x)

5. " x P(x) Ú Q ) (предикат Q не зависит от x.)

6. " x P(x) & Q º " x ( P(x) & Q )

7. $x P(x) Ú Q º $x ( P(x) Ú Q )

8. $x P(x) & Q º $x ( P(x) & Q )

9. " x Q º Q

10. $x Q º Q

11. " xP(x) & " xR(x) º " x ( P(x) & R(x) )

12. $xP(x) Ú $xR(x) º $x ( P(x) Ú R(x) )

13. " xP(x) Ú " xR(x) ® " x ( P(x) Ú R(x) )

14. $x (P(x) & R(x) ) ® $xP(x) & $xR(x)

15. " x P(x) º " yP(y) (х, у - из одной предметной области)

16. $x P(x) º $y P(y)

17. " x$y P(x, y) º $x" y P(x, y)

18. " x" y P(x, y) º " x" y P(x, y)

19. $x$y P(x, y) º $x$y P(x, y)

Получение дизъюнктов

Важное замечание. Рассматриваем только замкнутые предикаты, то естьпредикаты, не содержащие свободных вхождений переменных.

В общем случае необходимо пройти три этапа:

1. Получить предваренную нормальную форму.

2. Произвести сколемизацию.

3. Получить дизъюнкты.

Предваренная нормальная форма - такая форма представления предиката, когда все кванторы вынесены в начало за скобки (кванторная приставка), а в скобках есть только операции дизъюнкции, конъюнкции и отрицания. При этом символы отрицания, если таковые имеются, стоят непосредственно перед символами предикатов.

Сколемизация (от фамилии математика - Skö lem)позволяет получать запись замкнутого предиката в форме без кванторов.

Избавляемся от кванторов существования:

1) Если левее нет кванторов общности, то

соответствующая переменная заменяется константой сколема;

2) Иначе переменная заменяется функцией сколема от переменных, на которые навешаны кванторы общности, стоящие левее данного квантора существования.

После чего кванторы общности просто отбрасываются.

Пример:

" x ( " yP(x, y) Ú $zR(z) ® Q(x) & " yM(x, y)) º

º " x ( $yP(x, y) & $zR(z) Ú Q(x) & " yM(x, y) ) º

º $x ( (" yP(x, y) Ú " zR(z)) & (Q(x) Ú $yM(x, y)) ) º

º $x ( " yz (P(x, y) Ú R(z)) & $y( Q(x) Ú M(x, y)) ) º

º $x" y" z$h ( (P(x, y) Ú R(z)) & ( Q(x) Ú M(x, h)) ) º

º (P(a^c, y) Ú R(z)) & (Q(a^c) Ú M(a^c, f^c(y, z)))

Каждая элементарная дизъюнкция в полученном выражении является дизъюнктом.

Дифференциальным уравнением называется уравнение, связывающее независимую переменную х, искомую функцию у = f (x) и ее производные различных порядков.

Порядком дифференциального уравнения называется порядок старшей производной, входящей в это уравнение.

Дифференциальное уравнение n-го порядка в общем виде записывается так:

F (x, y, y', y'', ... y⁽ⁿ⁾) = 0.

Решением дифференциального уравнения называется любая функция y = φ (x),

обращающая это уравнение в тождество.

Решение F (x, y) = 0, заданное в неявном виде, называется интегралом дифференциального уравнения.

График решения дифференциального уравнения называется интегральной кривой.

Общим решением дифференциального уравнения n - го порядка называется функция

у = φ (х, С₁, С₂,..., С_n),

зависящая от х и n произвольных независимых постоянных С₁, С₂,..., С_n, обращающая это уравнение в тождество.

Общее решение, заданное в неявном виде

Ф (х, y, С₁, С₂,..., С_n) = 0,

называется общим интегралом.

Частным решением дифференциального уравнения называется решение, которое получается из общего, если придать определенные значения произвольным постоянным, т.е. решение вида:

у = φ (х, С⁰₁, С⁰₂,..., С⁰_n),

где С⁰₁, С⁰₂,..., С⁰_n - фиксированные числа.

Частным интегралом называется интеграл, полученный из общего путем

фиксирования произвольных постоянных:

Ф (х, y, С⁰₁, С⁰₂,..., С⁰_n) = 0,

где С⁰₁, С⁰₂,..., С⁰_n - фиксированные числа.

Дифференциальные уравнения первого порядка.

Краткая теория

Общий вид дифференциального уравнения первого порядка:

F (x, у, у') = 0. (12.1)

Если это уравнение разрешимо относительно у', то

у' = f(х, у) или dу = f(x, y)dx. (12.2)

Это уравнение можно записать так:

P(x, y)dx + Q(x, y)dy = 0. (12.3)

Общим решением уравнения (12.1) называется функция

y = φ (x, C) (12.4)

от х и произвольной постоянной С, обращающая это уравнение в тождество.

Общее решение, заданное в неявном виде

Ф (x, y, C ) = 0, (12.5)

называется общим интегралом.

Геометрически общее решение (и общий интеграл) представляет собой семейство интегральных кривых на плоскости, зависящих от одного параметра С.

Частным решением уравнения (12.1) называется решение, полученное из общего решения (12.4) при фиксированном значении С:

y = φ (x, C⁰) (12.6)

где C⁰ - фиксированное число.

Частным интегралом уравнения (1) называется интеграл, полученный из общего интеграла (5) при фиксированном значении С:

Ф (x, y, C⁰) = 0. (12.7)

Теорией первого порядка или просто теорией называется формальная

система Т такая, что:

• языком формальной системы является язык первого порядка;

• аксиомами формальной системы являются логические аксиомы

языка теории T и некоторые другие аксиомы, называемые нелоги-

ческими аксиомами;

• правилами вывода формальной системы являются правило расши-

рения, правило сокращения, правило ассоциативности, правило се-

чения и правило ∃ введения.

Теперь разъясним эти понятия подробно.

Язык первого порядка. Чтобы задать язык первого порядка нужно

определить символы языка и определить формулы языка.

Символами языка первого порядка является:

1. переменные x, y, z, x_, y_, ..., x1, y1, z1, ... ;

2. n-арные функциональные символы f, g, h, ... и n-арные предикат-

ные символы p, q, r, ..., где n _ 0;

3. символы ￢, ∨, ∃ .

Следующие символы называются

логическими символами: переменные, знаки ￢, ∨, ∃ и знак =.

Функциональные и предикатные символы, отличные от знака =, являют-

ся нелогическими символами. Они зависят от теории. Логические сим-

волы одни и те же во всех теориях. У каждой теории свой, индивидуаль-

ный набор функциональных и предикатных символов, отражающих поня-

тия данной теории. Число n-арных функциональных и предикатных сим-

волов для данного n произвольно и в, частности, может равняться 0. Од-

нако среди предикатных символов должен быть символ =.

Рассмотрим предназначение каждого типа знаков.

Символ = будет использоваться для обозначения равенства. Пере-

менные служат для обозначения произвольных объектов теории T. На-

пример, x может означать в арифметике число, в геометрии вектор, пря-

мую и т.п. Функциональные символы является знаками для обозначения

функций, а предикатные символы является знаками для обозначения пре-

дикатов.

Рассмотрим на примере арифметики необходимость каждого из трех

типов знаков. Допустим, что мы описываем свойства натуральных чисел,

относящиеся к сложению, умножению, отношению > и отношению «сле-

довать за». Тогда мы запишем следующую систему аксиом.

N1. Sx _= 0. N6. x · Sy = (x · y) + x.

N2. Sx = Sy → x = y. N7. ￢ (x < 0).

N3. x + 0 = x. N8. x < Sy ↔ x < y ∨ x = y.

N4. x + Sy = S(x + y). N9. x < y ∨ x = y ∨ y < x.

N5. x · 0 = 0.

Смысл некоторых выражений уточним ниже, а пока рассмотрим симво-

лы, которые нам потребовались. Мы использовали следующие логиче-

ские символы: переменные x, y, знаки ￢, ∨ и знак =. Нелогические сим-

волы следующие: унарный функциональный символ S для обозначения

функции следования, бинарные функциональные символы + и · для вы-

ражения понятий сложения и умножения, бинарный предикатный символ

< для выражения понятия меньше, константа 0 для обозначения конкрет-

ного элемента.

Чтобы определить язык математической теории, заданной в виде фор-

мальной системы, нужно определить не только символы, но и формулы.

Рассмотрим вначале пример, а затем точное определения формулы.

Пример. Рассмотрим формулу N2: Sx = Sy → x = y, изображающую

следующее свойство. Если последующее число для x равно последующе-

му числу для y , то число x равно числу y.

Построение формулы начинается следующим образом: рассматрива-

ется x - это переменная, она предназначена для обозначения конкретных

натуральных чисел. Переменная x— это терм. Далее используем знак S

- это знак для функции «последующий элемент». Выражение Sx — это

терм. Терм изображает значение функции S от элемента x. Заметим, что

вместо традиционного S(x) мы записываем это выражение без скобок.

Дадим точное определение терма.

1. Переменная является термом;

2. если u1, ...un —термы и f —n-арный функциональный символ, то

fu1u2 ...un —терм;

3. то, что выражение является термом устанавливается несколькими

применениями правил 1 и 2.

Скобки и запятые отсутствуют среди символов теории первого поряд-

ка и поэтому их нет в определении терма. Однако для наглядности мы бу-

дем употреблять запись f(u1, u2, ..., un), подразумевая вместо нее запись

fu1u2 ...un.

Отдельный нульарный функциональный символ - это терм. Действи-

тельно, выражение fu1u2 ...un при n = 0 имеет вид f. Нульарный функ-

циональный символ f можно отождествить с некоторым предметом, т.к.

значение функции от 0 переменных не может изменяться. Символ 0 в N1

– это терм.

Вернемся к рассмотрению предыдущего примера – формулы из N2

Sx = Sy → x = y отражающей мысль: если объект Sx совпадает с объ-

ектом Sy, т.е. последующий элемент за x равен последующему элементу

за y, то x = y. Эта формула построена в несколько шагов сборки 1–5.

1. Рассмотрим переменную x. Это – терм.

2. Рассмотрим переменную y. Это – терм.

3. Рассмотрим выражение Sx, образованное из унарного предикатного

символа y и ранее построенного терма x. Это выражение – терм.

4. Возьмем Sy. Это выражение – терм.

5. Рассмотрим символ бинарный предикатный символ =. Построим

выражения Sx = Sy и x = y. Эти выражения является атомными

формулами. Построим окончательное выражение Sx = Sy → x = y.

с помощью определяемого знака → . Это выражение является фор-

мулой, но не атомной формулой.

Введем точные определения атомной формулы и формулы в языке 1-го

порядка.

Атомной формулой называется выражение вида pu1u2 ...un, где

p—n-арный предикатный символ, u1, ..., un—термы.

Определение формулы.

1. Атомная формула является формулой.

2. Если A и B - произвольные формулы, то ￢ A, ∨ AB - формулы.

3. Если A - формула, то ∃ xA - формула.

4. Выражение является формулой тогда и только тогда, когда оно по-

лучено несколькими применениями правил 1-3.

Задание символов и формул, полностью определяет язык 1-го порядка.

Отметим, что в пункте 2 речь идет о способе построении формул таком

же, как в исчислении высказываний. В пункте 3 добавляется новая кон-

струкция ∃ xA. Она предназначена для отражения высказываний следую-

щего вида: существует x, для которого верно A. Например (∃ x x2 > 4)

существует число с условием x2 > 4).

Соглашения о записях. Мы продолжаем использовать соглашения

из исчисления высказываний: вместо ∨ AB для удобства восприятия за-

писываем A ∨ B, применяем определяемые знаки →, ↔, ∧ и т.п. Со-

храняем соглашение о скобках из исчисления высказываний. Заметим,

что у нас нет квантора ∀ . Это обусловлено следующей равносильностью:

∀ x P(x) ≡ ￢ ∃ x￢ P(x), рассматривавшейся во вводном курсе математи-

ки. Поэтому ∀ – определяемый знак и запись ∀ xP(x) является сокраще-

нием для записи ￢ ∃ x￢ P(x).

Вместо puv и fuv где p - бинарный предикатный символ, а f - бинар-

ный функциональный символ, записываем upv, и ufv. Кроме того, форму-

лу ￢ upv будем записывать перечеркивая знак p, например, Sx _= 0 изоб-

ражает формулу ￢ Sx = 0.

До сих пор мы рассматривали синтаксис языков первого порядка, то

есть точные правила для построения термов, формул, задания аксиом и

теорем. Наряду с синтаксическим аспектом будем рассматривать семан-

тический аспект теории. Переход от синтаксиса к семантике совершается

тогда, когда вместо функциональных и предикатных символов, рассмат-

риваемых как буквы и только, мы начинаем изучать конкретные функции

и предикаты на некотором множестве 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 являются всевозможные строки (a1, ..., an), то есть

Mn = {(a1, ..., an) | ai ∈ M}.

Если f—некоторая n-арная функция на множестве M, то она являет-

ся сопоставлением (a1, ..., an) _→ a ∈ M. Таким образом, a1, ..., an—

значения аргумента, a—значение функции, т.е. f(x1, ..., xn) = a при

x1 = a1, ..., xn = an. Аргументы и значения функции берутся из одно-

го и того же множества M.

n-арным предикатом на множестве M называется произвольное под-

множества R из декартова произведения Mn = M × M × M... × M.

Если (a1, ..., an) ∈ R , то говорят, что элементы a1, ..., an находится в

отношении R. При n = 2 записываем a1 R a2.

Поскольку мы имеем конкретные функции и предикаты на множестве,

то мы сможем приписывать нашим формулам значения истина или ложь.

В формуле 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. Он имеет запись fu1u2un, где

u1, ..., un — ранее построенные термы и f –n-арный функциональный

символ. По теореме об однозначности построения терма части u1, ..., un

определены однозначно. Далее разберем однозначно на части каждый

из термов u1, ..., un и т.д. В результате получим сборку u из его ча-

стей. Части, с которых начинается сборка терма u имеют некоторый вид

g(x1, x2, ...), где x1, x2, ... — переменные. Они должны заменяться на

конкретные индивиды a1, a2, ... из M в соответствие с интерпретацией

(29). В терме g(x1, x2, ...) заменим функциональный символ g на функцию

gA, а переменные x1, x2, ... на a1, a2, .... Получим индивид gA(a1, a2, ...)

из M. Подставим это значение в качестве аргумента в следующий терм,

участвующий в сборке терма u. Повторив действие несколько раз, полу-

чим значение a ∈ M терма u при интерпретации (29).

Рассмотрим атомную формулу p(u1, u2, ..., un), где p– n-арный пре-

дикатный символ. Заменим символ p на предикат pA, т.е. на некоторое

подмножества R из декартова произведения Mn = M × M × M... × M.

При интерпретации (29) вместо термов u1, u2, ..., un получатся элементы

a1, ..., an изM.

Если n-ка элементов (a1, ..., an) содержится в R, то приписываем

атомной формуле p(u1, ..., 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) x1 = y1 → x2 = y2 → · · ·→ fx1 ...xn = fy1 ...yn,

б) x1 = y1 → x2 = y2 → · · ·→ px1 ...xn = py1 ...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 значений переменных: x1 = a1, y1 = b1, ... истинностное зна-

чение V (X) равно Л. Тогда посылка a1 = b1 истинна, а заключение

a2 = b2 → · · · → f(a1 ...an) = f(b1 ... bn) ложно (напомним, что A → B

–сокращение для ￢ A ∨ B и, поэтому, имеет такое правило для приписы-

вания И, Л).

Получили совпадение элементов a1 и b1. Аналогично получаем a2 =

b2, .... и ложность равенства f(a1 ...an) = f(b1 ... bn).

Тогда совпадение элементов a1 = b1, a2 = b2, ... влечет совпадение

значений функции f(a1 ...an) = f(b1 ... ), противоречие с допущением

f(a1 ...an) _= f(b1 ... 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 имеет значение И. Теорема доказана.

⇐ Предыдущая 1 234 5 6 Следующая ⇒