Метатеоретические свойства классического исчисления предикатов первого порядка

???????? Свойства исчисления предикатов (аксиоматического исчисления предикатов: + - обладает этим свойством, - - не обладает).

+1. Характеристика с точки зрения семантики

Свойства семантической непротиворечивости: V˚ A (S|--A > ˚ T |= A)

Все теоремы классического исчисления предикатов общезначимы. Надо показать, что все аксиомы общезначимы и правила вывода сохраняют общезначимость (т е если их применить к общезначимым формулам, то в рез-те получится тоже общезначимая формула).

+2. Свойство семантической полноты: V˚ A (T |= A > ˚ S|--A)

Если любая общезначимая формула доказуема в этом исчислении.

Если исчисление двумя этими свойствами обладает (а оно ими обладает), то исчисление предикатов адекватно формализует классическую логику предикатов.

+3. Синтаксическая непротиворечивость: ┐ ˚ E˚ (S |--A & ˚ S |-- ┐ A). Доказывается так же, как и в классическом исчислении высказываний (см. вопрос 5).

- 4. Свойство синтаксической полноты (или максимальности): V˚ A (S |-/-A > ˚ E˚ B ( S+A |-- B & ˚ S+A |-- ┐ B).

Этим свойством исчисление предикатов не обладает. Т. е. есть возможность расширения исчисления предикатов за счет утверждений не являющихся логическими законами (например, законы какой-то научной теории). Значит, на основе этого исчисления можно строить прикладные конкретные теории (см. вопрос 12).

- 5. Разрешимость. Исчисление называется разрешимым, если существует алгоритм, позволяющий в конечное число шагов для любой формулы языка установить, является ли она теоремой исчисления или нет.

Исчисление предикатов неразрешимо.

В частных случаях логики предикатов это свойство есть. 1). Логика одноместных предикатов разрешима. (Логика одноместных предикатов – если разрешить использовать в языке только одноместные предикаты и запретить использование многоместных. Т. е. только анализ свойств). 2). Логика предикатов. Понятие модели < U, I> U – непустое. Можно сузить класс моделей – рассматривать только такие модели в которых универсум имеет конечное число объектов. В этом случае существует эффективное решение вопроса о том яв-ся ли формула общезначимой или нет.

Кванторы могут быть устранены

U = {a1, a2, ... an}

V α A ≡ A(a1) & А(а2) …. А(аn)

E α A ≡ A(a1) v A(a2).... A (an)

 

 

Логика предикатов с равенством. Прикладные первопорядковые теории.

Введение а язык константы равенства ( = )

Пр. Среди студентов нашей группы только Петр является отличником

Р(а) & S(a) & V ((S(x) & ┐ (x=a)) > ┐ P(x))

 

Волга длиннее всех других европейских рек.

Vx (S(x) > R2(a, x))

Vx (S(x) & ┐ (x=a))> R2(a, x))

Равенство как тождество объектов

Логику предикатов можно расширить за счет введения равенства

 

Классическая логика предикатов первого порядка с равенством

В алфавит добавляется предикатор = (двухместная предикаторная константа)

В понятии формулы: добавляется еще одна атомарная формула t1=t2

I(=) – функция должна приписать множество пар объектов, где первая и вторая компонента совпадают.

I(=) =˚ {< d, d>: d ( U}

|t1=t2|φ =˚ и ↔ |t1| φ =˚ |t2| φ

Все остальные отношение между формулами те же.

Исчисление для этой теории тоже строится как расширение. Добавляются 2 новые схемы аксиом

Vα (α =α ) – Отношение равенства рефлексивно

Vα Vβ ((α =β ) > (A (α )> A(β )) – закон замены равного равным. A (α ) – некоторая формула содержащая α в качестве свободной переменной. A(β ) – результат замены некоторого числа свободных вхождений переменной α в формулу A (α ) на переменную β, причем замещаемые вхождения α не находятся в области действия квантора по β. Чтобы не возникало новых связанных вхождений.

Можно показать семантическую непротиворечивость и полноту.

Теоремы:

t1=t2 (рефлексивное отношение)

t1=t2 > t2=t1 (симметричное отношение)

(t1=t2& t2=t3) > t1=t3 (транзитивное отношение)

t1=t2 > (A(t1) ≡ A(t2)) (принцип взаимозаменимости, экстенсиональности). Есть некоторые ограничения. Если терм замкнут – ограничений нет. Если там содержатся некие переменные, то ограничения есть: 1) Замещаемые вхождения t1 не содержат связанных вхождений переменных. 2) Замещаемые вхождения t1 не находятся в области действия кванторов по переменным входящим в терм t2, т е после замены не должно появиться новых связанных вхождений.

 

Можно ввести квантор – существует единственный

Е! α А(α ) ≡ Df Еα (А (α ) & Vβ (A(β ) > α = β ))

 

Прикладные первопорядковые теории

Классическое исчисление предикатов можно непротиворечиво расширять.

Логику предикатов можно использовать как основу для построения конкретных теорий. Можем в язык вместо абстрактных параметров (констант) вводить конкретные нелогические термины, термины конкретной науки, конкретные предикаторы (быть четным, быть городом, государством, горой), конкретных предметных функций. В остальном структура языка остается той же.

 

Расстояние от Москвы до Петербурга больше, чем расстояние от Москвы до Одессы.

Больше (расстояние (М, П), расстояние(М, О))

 

Эверест – самая высокая гора

Vx (Гора (x) & ┐ (x=Эверест))> выше (Эверест, х))

 

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

Теории, которые получаются за счет введения в язык конкретных знаков отношений (Логики отношений)

 

Логика отношения эквивалентности

(знак отношения эквивалентности – это знак = а сверху еще одна волнистая линия, здесь обозначу этот знак так ≈ )

Язык. Добавляется к дедуктивным постулатам аксиомы:

1. Рефлексивности Vα (α ≈ α )

2. Симметричность Vα Vβ (α ≈ β > β ≈ α )

3. Vα Vβ Vγ ((α ≈ β & β ≈ γ ) > α ≈ γ ) (например, родиться в одном и том же году)

Равенство тоже этим свойством обладает (но равенство еще обладает свойством взаимозаменимости)

 

Отношение частичного порядка

В язык вводится предикатор ≤

Присоединяется еще 3 схемы аксиом:

1. Vα (α ≤ α ) – рефлексивность

2. Vα Vβ Vγ ((α ≤ β & β ≤ γ ) > α ≤ γ ) – транзитивность

3. Антисимметричность Vα Vβ ((α ≤ β & β ≤ α ) > α = β )

 

Отношение строгого порядка

В язык вводится <

1. Антирефлексивность Vα ┐ (α < α )

2. Транзитивность Vα Vβ Vγ ((α < β & β < γ ) > α < γ )

Примеры: <, старше

 

Отношение строгого линейного порядка

В язык вводится <

1. Антирефлексивность Vα ┐ (α < α )

2. Транзитивность Vα Vβ Vγ ((α < β & β < γ ) > α < γ )

3. Vα Vβ (α < β v β < γ v α =β )

 

Формальная арифметика (Пеано)

Исходные термины: имя 0

Вводятся знаки предметных функций (один одноместный и 2 двухместных):

' – прибавление 1 к числу

+

·

Выделенный предикатор =

Дефиниции: 1 ≡ Df 0'

2 ≡ Df 1'

Постулаты (аксиомы):

х1=х2 > x'1=x'2

┐ (0= x')

x'1=x'2 > х1=х2

x+0=x

x1+x'2 = (x1+x2)'

x · 0 = 0

x1 · x'2 = (x1 · x2) + x1

A(0) > (Vx (A(x)> A(x')) > Vx A(x))

 

В этой теории можно доказать очень много теорем. Но не все арифметические истины доказуемы в этой теории. Гедель – о неполноте арифметики. Класс истин в арифметике невозможно формализовать.

Логика точными методами может указать свои собственные границы.

 

Первый порядок – квантификация только предметных переменных.

Но в языке часто говорится о свойствах, об отношениях между свойствами. ---- Логика предикатов второго порядка

 

Логика предикатов второго порядка

Квантификация по свойствам и по отношениям между индивидами и по предметным функциям.

В старый язык вводятся новые переменные.

Вводятся предикаторные переменные и предметно-функциональные переменные.

Pⁿ Qⁿ Rⁿ fⁿ gⁿ kⁿ

Определение терма и формулы, их изменения.

Терм:

1. Терм – любая предметная константа

2. любая предметная переменная

3. Фⁿ (t1, t2,...tn) если, t1, t2,...tn – термы, Ф^{n -} или n-местная предметно-функциональная константа (как и раньше) или n-местная предметно-функциональная переменная.

Формула:

1. Пⁿ (t1, t2,...tn). Пⁿ - не только предикаторная константа, но может быть предикаторной переменной.

2. Если А – формула, а α – предметная переменная, то Vα A и Еα A – формулы. Теперь α может быть не только предметной, но и предикаторной и предметно-функциональной переменной.

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

а – Земля

b – Марс

P¹ - свойство

Е P¹ (P¹ (а) & P¹(b))

Медь обладает всеми свойствами, присущими любому металлу (R)

V P (Vx ( R(x) > P (x)) > P (a))

Теория:

Понятие модели сохраняется < U, I>

φ: φ (α ) ( U

φ (Пⁿ) ( Uⁿ

φ (Фⁿ) есть функция Uⁿ à U

Приписывание значения переменным: |Фⁿ (t1, t2,...tn) |φ = [ I(Фⁿ)] ( |t1| _{φ ,} |t2| _{φ , ....}|tn| _φ ) – если Ф – предметная-функц. константа

- //---// --- // φ (Фⁿ) ---//----// - если Ф – предметно-функц. переменная

Значения формул.

|Пⁿ (t1, t2,...tn)|φ = и ↔ < |t1| _{φ ,} |t2| _{φ , ....}|tn| _φ > ( I (Пⁿ), если Пⁿ - предикаторная константа

-----//------------------//----------------// --------- φ (Пⁿ), если Пⁿ – предикаторная переменная

 

Все остальные понятия остаются прежними.

 

Эта теория не обладает свойством семантической полноты.

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

t1=t2 ≡ Df V P (P (t1) ≡ P (t2) (тождественность неразличимых (Лейбниц))

Эту теорию тоже можно расширять. Можно вводить признаки признаков (предикаторы от предикаторов): свойства свойств, свойства отношений, отношения между свойствами. Получается ступенчатое исчисление. И так далее – логика третьего порядка.

Рассел. Теория типов.

В рамках логической теории можно определить число. Натуральные числа трактуются как свойства свойств.

0 (P) ≡ Df ┐ Ех P (х)

1 (P ) ≡ Df Е! х P (х)

2 (P)≡ Df ЕхЕy (┐ (x=y) & P (x) & P (y) & Vz (P (z) > (z=x v z=y)))

 

⇐ Предыдущая123Следующая ⇒

Поделиться: