Непейвода Н.Н. Прикладная логика

Подождите немного. Документ загружается.

8.2. ТЕОРИЯ, МОДЕЛЬ, ЛОГИЧЕСКОЕ СЛЕДСТВИЕ

201

Для учета изменения фактов и выводов по умолчанию в искусственном

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

И наконец, если наши действия необратимы (для этого достаточно,

чтобы в рассмотрение было введено время), то не всегда целесообразно

сохранять рефлексивность следования.

Вернемся к классической логике. Как видно, все, что следует из те-

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

следует из любой теории данной сигнатуры. И наоборот, если теория

вообще не имеет моделей, то из нее следует все, что угодно. Эти два

важных частных случая отражаются следующим определением.

Определение 8.2.3. (Логика предикатов, тавтологии, противоречия)

Логика предикатов сигнатуры

— теория с пустым множеством ак-

сиом.

Тавтология

— теорема логики.

Противоречивая теория — теория, не имеющая моделей.

Противоречие — такая формула

, что

{A}

противоречива.

Формулы

B логически эквивалентны

, если

A ⇔ B

— тавтоло-

гия.

Итак, противоречие ложно в любой интерпретации. В противоре-

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

Эквивалентные формулы имеют одинаковые значения в любой интер-

претации.

Отметим несколько часто используемых отношения между интер-

претациями.

Определение 8.2.4.

Если

— интерпретации одной и той же сиг-

натуры, универсы

являются подмножествами соответствующих уни-

версов

, интерпретации констант совпадают, а интерпретации функ-

ций и предикатов в

являются сужениями соответствующих интерпре-

таций в

, то

—

подинтерпретация

(соответственно,

подмодель

)

—

расширение

(

надинтерпретация

надмодель

)

. В этом случае

пишут

M ⊂ N

Если все множества сигнатуры

вложены в соответствующие мно-

жества из

, то

называется

сужением

(

подсигнатурой

обеднением

)

, а

—

расширением

(

обогащением

надсигнатурой

)

. Обозначает-

ся

σ ⊂ σ

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

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

202

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

Интерпретация

сигнатуры

является сужением (обеднением) ин-

терпретации

сигнатуры

, такой, что

σ ⊂ σ

, если для всех понятий

из

интерпретации в

совпадают. В этом случае

называется

обогащением M

Подытожим:

Семантика чаще всего определяет функцию, задающую зна-

чения формул в интерпретации.

Интерпретация называется моделью теории

Th, если в ней

истинны все аксиомы Th.

Семантика задает между теорией и формулой отношение,

называемое семантическим следованием: формула следует

из теории, если она истинна во всех ее моделях.

Основные свойства следования — рефлексивность, моно-

тонность, транзитивность и теорема дедукции. Все они ино-

гда нарушаются в современных неклассических системах,

но для их нарушения нужны серьезные основания.

Чтобы применять классическую логику, необходимо быть

уверенным как минимум в том, что имеющиеся ресурсы до-

статочно велики либо расходуемые достаточно малы, чтобы

пренебречь их ограниченностью; что новое знание не может

перечеркнуть старое, что мы можем пренебречь временем

либо, по крайней мере, его необратимостью.

Практическая работа

Работа с программой “Мир Тарского”. Работа со сложными высказыва-

ниями и их интерпретацией, составление многокванторных высказыва-

ний и миров, их опровергающих либо подтверждающих.

Упражнения к § 8.2

8.2.1. Студентка Примерная задала теорию со следующей единствен-

ной аксиомой:

∃x (A(x) ⇒ B(x)). Опишите модели этой теории.

Следует ли из нее ∃x A(x) ∨ ∃x B(x)?

8.2.2. Следует ли из теории

{∀x ∃y A(x, y)} формула

∃y ∀x A(x, y)?

8.2. ТЕОРИЯ, МОДЕЛЬ, ЛОГИЧЕСКОЕ СЛЕДСТВИЕ

203

8.2.3. Следует ли из теории {¬∀x ∃yA(x, y), ∀x A(x, x)} формула

∃x ∀y A(x, y)?

8.2.4. Если множество констант есть {0, 1, . . . , n, . . . } для всех нату-

ральных чисел,то следует ли из теории {A(0), A(1), . . . , A(n), . . . }

формула ∀xA(x)?

8.2.5. Рассмотрим теорию

Q сигнатуры h0, S(), +(, ), ∗(, ), = (, )i, где

0 — константа, S, +, ∗ — функции, равенство — предикат, c ак-

сиомами:

∀x ∀y (S(x) = S(y) ⇒ x = y) ; ∀x ∀y (x + S(y) = S(x + y)) ;

∀x ¬S(x) = 0; ∀x (x ∗ 0 = 0) ;

∀x (¬x = 0 ⇒ ∃y (x = S(y))) ; ∀x ∀y (x ∗S(y) = x ∗y + x) ;

∀x (x + 0 = x) .

a) Показать, что множество натуральных чисел N c обычными

0, +, ∗ и S(x) = x + 1 является моделью Q.

b) Показать, что

N является подмоделью любой модели Q.

c) Построить модель

Q с универсом N ∪ {ω}, ω /∈ N.

d) Аналогично предыдущему с добавлением двух элементов.

e) Аналогично с добавлением бесконечного числа элементов.

f) Докажите, что

∀x ¬(x = S(x)) не является теоремой Q.

g) Аналогично для

∀x ∀y (x + y = y + x).

8.2.6. Рассмотрим теорию

OS со следующими аксиомами.

∀x, y, z(x ◦ (y ◦ z) = (x ◦ y) ◦z),

∀x, y, z, u(x ◦ y = z ⇒ y ◦ z 6= x),

∀x, y(x < y ⇔ ∃z x ◦ z = y).

Противоречива ли данная теория?

8.2.7. Покажите, что всякая модель

OS является обогащением модели

теории частичного порядка. Почему данное упражнение практи-

чески независимо от предшествующего (точнее, почему нет усло-

вия «Если теория OS непротиворечива, то...»)?

8.2.8. Могут ли быть у теории

OS конечные модели, если могут, то ка-

кие? От какого из предыдущих упражнений зависит данное?

204

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

§ 8.3. ТЕОРЕМА О ЗАМЕНЕ ЭКВИВАЛЕНТНЫХ

Теорема 8.1. (Теорема о замене эквивалентных) Пусть A, B — фор-

мулы, имеющие одни и те же свободные переменные x

, ..., x

, и

∀x

. . . ∀x

(A(x

, . . . , x

) ⇔ B(x

, . . . , x

))

—теорема Th.Пусть C{A}—формула с выделенным вхождением под-

формулы A; C{B} — результат замены в ней этого вхождения A на

B. Пусть y

,..., y

— список всех свободных переменных C{A}. Тогда

∀y

. . . ∀y

(C{A} ⇔ C{B}) является теоремой

Доказательство. Индукцией по построению

Базис индукции

. Если C элементарна, то C{A} есть A, C{B} есть

B, свободные переменные C{A} — это x

, ..., x

; следовательно,

∀y

. . . ∀y

(C{A} ⇔ C{B})

есть сама

∀x

. . . ∀x

(A (x

, . . . , x

) ⇔ B (x

, . . . , x

)) .

Шаг индукции

. Пусть теорема доказана для компонент C. Если A

совпадает с самой C, то поступаем как в базисе индукции. Если же нет,

то разбираем случаи, соответствующие построению C. Пусть C есть

& C

). Тогда A входит либо в C

, либо в C

. В первом случае поль-

зуемся тавтологией (4.50),во втором —аналогичной ей с перестановкой

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

ются подобно же.

Доказанная теорема может показаться слишком тривиальной,но рас-

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

шить. Другое дело, что наличие свойства замены эквивалентных явля-

ется весьма желательным для любой логики, а если уж его нет, надо

подумать, чем его заменить. Например, можно ввести понятие “сильно-

го отрицания”, когда предикат задается парой непересекающихся мно-

жеств — множества истинности и множества опровержимости. В этом

случае эквивалентность формул не означает их взаимозаменяемости,

поскольку при совпадении множеств истинности множества опровер-

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

мость таких формул

A, B, что

(A ⇔ B) & (∼ A ⇔∼ B),

8.4. БУЛЕВЫ АЛГЕБРЫ

205

где ∼— операция взятия опровержения формулы. Такие формулы есте-

ственно назвать сильно эквивалентными. Итак, если нарушается свой-

ство замены эквивалентных, ищите, какую сильную эквивалентность

нужно ввести для его спасения.

Упражнения к § 8.3

8.3.1. Покажите, что формула

∀x (A(x) ⇒ ∃z(B(z)&C(x, z))) ∨

∃x (A(x)& ∀z(B(z) ⇒

C(x, z)))

является тавтологией.

§ 8.4. БУЛЕВЫ АЛГЕБРЫ И

АЛГЕБРАИЧЕСКАЯ СЕМАНТИКА

Систему булевых операций можно охарактеризовать аксиоматически.

Определение 8.4.1. Булева алгебра

— множество

c бинарными опе-

рациями

∪

∩

и унарной

−

, удовлетворяющими следующим аксиомам:

A ∪ B = B ∪ A; A ∩ B = B ∩ A;

A ∪ (B ∪ C) = (A ∪B) ∪ C; A ∩ (B ∩ C) = (A ∩ B) ∩ C;

(A ∩ B) ∪ B = B; (A ∪ B) ∩ B = B;

A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪C); A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C);

(A ∩ −A) ∪B = B; (A ∪ −A) ∩ B = B.

Мы стремились не к формальной минимальности системы аксиом,

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

ет система всех подмножеств некоторого множества и, более того, лю-

бая алгебра множеств, т. е. система множеств, замкнутая относительно

обычных операций объединения,пересечения и дополнения.Если опре-

делены пересечения и объединения произвольного (в том числе и бес-

конечного) множества элементов, то булева алгебра называется полной.

Теорема 8.2. (Теорема Стоуна о представлении) Любая булева алге-

бра изоморфна некоторой алгебре множеств.

В курсе математической логики эта теорема доказываться не будет.

Для нас важнее другое соотношение, установленное польскими логика-

ми Линденбаумом и Тарским.

206

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

Рассмотрим отношение Th ` A ⇔ B. Оно транзитивно, рефлексив-

но, симметрично и, согласно теореме о замене эквивалентных, согла-

суется с логическими операциями. Таким образом, можно определить

алгебру Линденбаума-Тарского теории Th как фактор-множество мно-

жества замкнутых формул сигнатуры

по отношению

Th ` A ⇔ B

Пересечению соответствует в ней

&, объединению — ∨, дополнению —

отрицание. Отметим, что конструкция алгебры Линденбаума-Тарского

переносится и на неклассические логики, лишь бы сохранялась теорема

о замене эквивалентных.

Очевидно, что алгебра Линденбаума-Тарского классической теории

является булевой. И обратно, любая булева алгебра может быть исполь-

зована, чтобы интерпретировать классические теории.

Определение 8.4.2. Булевозначная модель

сигнатуры

— пятерка

(U, B, C, P, F ),

где

— полная булева алгебра, универс, константы и функции — как в

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

булеву алгебру истинностных значений

. Определение значений фор-

мул аналогично определению истинности, соответствие операциям —

как в алгебре Линденбаума-Тарского, квантору всеобщности соответ-

ствует бесконечное пересечение, квантору существования — бесконеч-

ное объединение.

Преимущество булевозначных моделей в том, что они дают возмож-

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

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

лей не удается построить даже для теории {A ⇒ B, B ⇒ C}. Заодно бу-

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

предполагает наличие всего двух значений истинности. Хорошее и глу-

бокое изложение взаимосвязи булевых алгебр с логикой можно найти в

книге [26].

Подытожим

Классическая логика не обязательно требует двузначности

интерпретаций. Достаточно, чтобы множество истинност-

ных значений образовывало булеву алгебру.

Наоборот, если множество истинностных значений — бу-

лева алгебра, то логика данной интерпретации — классиче-

ская либо ее расширение дополнительными связками.

8.4. БУЛЕВЫ АЛГЕБРЫ

207

Любая логика (не только классическая),в которой есть свой-

ство замены эквивалентных, задает для каждой теории свою

алгебру логических значений — алгебру Линденбаума-Тар-

ского, алгебру эквивалентных формул.

Для того, чтобы строить точную модель, в которой форму-

ла истинна тогда и только тогда, когда следует из аксиом,

необходимо переходить к булевым алгебрам. Для этой цели

двузначных моделей недостаточно.

Упражнения к § 8.4

8.4.1. Построить булеву алгебру с четырьмя элементами.

8.4.2. Студент Интеллектуалов построил булеву алгебру с четырьмя эле-

ментами следующим образом: он взял диаграмму Эйлера

и сказал, что изображенные на ней три множества плюс пустое

составляют такую алгебру. Сравните его решение с Вашим.

8.4.3. Доказать, что отношение

X ∪ Y = X (обозначается Y 6 X)

является отношением порядка в булевой алгебре.

8.4.4. Доказать, что в булевой алгебре имеются наибольший элемент

и наименьший элемент

8.4.5. Доказать, что в алгебре Линденбаума-Тарского единица соответ-

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

8.4.6. Доказать, что

(A ⇒ B) тогда и только тогда, когда B > A в алге-

бре Линденбаума-Тарского.

8.4.7. Доказать, что

X ∩ Y является точной нижней гранью X и Y от-

носительно определенного нами порядка.

8.4.8. Показать, что нет булевых алгебр с тремя элементами.

8.4.9. Построить точную модель для теории

{A ⇒ B, A ⇒ C ∨ D, B ⇒ H&K}.

208

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

8.4.10. Пусть A — алгебра, удовлетворяющая следующим аксиомам:

−(A ∩ B) = −A ∪ −B; A ∪ B = B ∪ A;

A ∪ (B ∪ C) = (A ∪B) ∪ C; (A ∩ B) ∪ (A ∩ −B) = A.

Тогда A — булева алгебра.

8.4.11. Чтобы непустое подмножество булевой алгебры было ее подал-

геброй, достаточно его замкнутости относительно ∩ и −.

8.4.12. Постройте булевозначную модель, в которой для некоторых A,

B формула A ∨ B истинна, но ни одна из элементарных формул

истинной не является.

8.4.13. Какое минимальное количество элементов должна иметь булева

алгебра логических значений для точной модели теории

{A ⇒ B, B ⇒ C}?

8.4.14. Можно ли для всех пропозициональных теорий в данной сиг-

натуре подобрать единую булеву алгебру, которая может служить

алгеброй логических значений для их точных моделей? В каких

случаях эту булеву алгебру можно взять конечной?

8.4.15. Во время математического боя студент Гениалькис, обосновы-

вая свое решение, заявил, что поскольку булева алгебра B конеч-

на, она полна. Ссылки на книгу, откуда он взял эту теорему, он не

дал. Будете ли Вы опротестовывать его доказательство на основа-

нии данного утверждения?

§ 8.5. ЯЗЫКИ ВЫСШИХ ПОРЯДКОВ

Рассмотрим еще один вид языков, занимающих промежуточное положе-

ние между чистой логикой и теорией множеств. Обычно их тоже счита-

ют логическими языками.

Разберемся в разнице между конкретной теорией и логикой. Почему

теорию множеств безоговорочно считают конкретной, а вот язык преди-

катов — логическим? Для этого рассмотрим множество интерпретаций,

в которых истинны теоремы теории множеств и множество интерпрета-

ций, в которых истинны логические теоремы. Логические теоремы —

8.5. ЯЗЫКИ ВЫСШИХ ПОРЯДКОВ

209

тавтологии, и поэтому истинны в любых интерпретациях. Теоремы те-

ории множеств истинны лишь в ее моделях. Очевидно, что класс всех

интерпретаций намного шире и намного проще определен, чем класс

моделей теории множеств.

Проницательный читатель может заявить: а ведь формулируя опре-

деление интерпретации, мы также принимали целый ряд предположе-

ний! Приведем два наиболее явственных: логических значений лишь

два, универс непуст... А сколько еще неявных предположений пролезло

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

ории множеств я еще могу согласиться, что это — слишком конкретная

теория, но чем хуже, например, отношение порядка, чем отношение ра-

венства?Почему теория частичного порядка считается математической,

а не логической?

Как часто бывает, кое в чем читатель прав. В вопросе стоит разо-

браться с другой стороны. Чем же помешает отношение порядка? Рас-

смотрим простую теорему, явившуюся одним из первых строго устано-

вленных свойств классической логики.Пусть

A(x

, . . . , x

) —формула.

Определим предикатор как выражение вида $x

, . . . , x

A(x

, . . . , x

Здесь $ служит квантором, связывающим переменные x

, . . . , x

. Пре-

дикатор служит синтаксическим объектом для подстановки вместо пре-

дикатов.Теперь можно определить подстановку предикатора вместо пре-

диката аналогично тому, как мы делали для термов и переменных. За-

меняются лишь базисные шаги.

Subst (P (t

, . . . , t

), P, $x

, . . . , x

)

= Subst (A, (x

, . . . , x

), (t

, . . . , t

)) .

Как и для термов, подстановку часто сокращенно обозначают

A{P |

B}.

Следующее свойство выполнено лишь для тавтологий и практиче-

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

ром смысле характеристическим свойством логики вообще, в отличие

от частных теорий; гранью, отделяющей логические теории от приклад-

ных. Логические теории рассчитаны на весьма общий класс интерпре-

таций. Прикладные имеют в виду конкретный класс моделей со специ-

фичной интерпретацией предикатов и функций

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

жеств и теория категорий, называются в логике прикладными.

210

ГЛАВА 8. СЕМАНТИКА КЛАССИЧЕСКОЙ ЛОГИКИ

Теорема 8.3. (Теорема о подстановке вместо предикатов)Если C явля-

ется тавтологией классической логики, P — n-арный предикат,

, . . . , x

A(x

, . . . , x

, x

n+1

, . . . , x

) −

-местный предикатор со свободными переменными x

n+1

, ..., x

, то

тавтологией является и формула C{P |

A}}

Доказательство. Рассмотрим два случая. Пусть сначала P не входит

в A. Поскольку P не входит в C{P |

A}, по любой интерпретации

этой формулы строится интерпретация самой C, в которой она имеет

то же значение, определяя P (t

, . . . , t

) через значение A(t

, . . . , t

). А

по предположению C — тавтология. Значит, результат замены истинен

во всех интерпретациях.

Пусть теперь

P входит в подставляемый предикатор. Тогда любое

вхождение P в C{P |

A} является результатом одной из замен, и по

любой интерпретации M формулы C{P|

A} строим другую интер-

претацию M

для C, такую, что

(C{P |

A}) = ζ

Для этого заменяем значение P на соответствующее значение A.

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

ром сохраняется теорема о подстановке вместо предикатов. Разрешим

всевозможные конечные типы, построенные из исходных типов

o и t

(объекты и логические значения), и выдающие результатом логические

значения. Таким образом, теперь аргументами предикатов могут быть

предикаты. Разрешим переменные по каждому типу и обычные кванто-

ры всеобщности и существования по каждому типу. Итак, теперь у нас

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

местным обычным предикатам, переменные по предикатам, первым ар-

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

значение, третьим — объект и т. д., и т. п. Но поскольку язык строго ти-

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

аргументного места предиката точно указывается тип соответствующе-

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

конечных типов.

Определенная нами интерпретация языков конечных типов естест-

венно переносится на данный язык и составляет семантику для него.