Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

Тема 3. Логика предикатов

Логика высказываний обладает довольно слабыми выразительными возможностями. В ней нельзя выразить даже очень простые с математической точки зрения рассуждения. Рассмотрим, например, следующее умозаключение. «Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число». Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логика предикатов первого порядка или короче: логика первого порядка.

§1. Предикаты и операции над ними

§2. Формулы логики первого порядка

§3. Интерпретация в логике первого порядка

§4. Равносильность, законы логики первого порядка

§6. Логическое следствие

§7. Нормальные формы

§8. Невыразимость в логике первого порядка

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

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


Определение. Пусть S(x,y) – двухместный предикат, заданный на множестве М. Предикат S+(x,y) называется транзитивным замыканием предиката S(x,y), если для любых a,bÎM выполняется условие:


высказывание S+(a,b) истинно Û существует натуральное число n и элементы c0,…,cn множества М такие, что a=c0,…, cn=b и все высказывания S(c0,c1), S(c1,c2),…, S(cn-1,cn) истинны.

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

Рассмотрим пример. Пусть М – множество натуральных чисел, а S(x,y) – предикат «x непосредственно предшествует y», т.е. «y=x+1». Тогда транзитивным замыканием предиката S(x,y) будет предикат «x меньше y».


Оказывается, что не существует формулы логики первого порядка, которая выражала бы транзитивное замыкание двухместного предиката. Более точная формулировка содержится в следующем утверждении.


Теорема 3.5 Пусть P – символ двухместного предиката. Не существует формулы F(x,y) логики первого порядка такой, что для любой интерпретации j с областью М предикат (jF)(x,y) есть транзитивное замыкание предиката (jP)(x,y).

Доказательство теоремы 3.5 опирается на одно известное в логике первого порядка утверждение, которое называется теоремой компактности. В формулировке теоремы компактности используется понятие логического следствия бесконечного множества формул. Определение этого понятия легко получается из определения логического следствия множества формул F1,…,Fk из §6 и поэтому не приводится.


Теорема компактности. Если формула G является логическим следствием бесконечного множества формул K, то G является логическим следствием некоторого конечного подмножества K′ множества K.

Доказательство теоремы компактности является довольно сложным, поэтому здесь не излагается. С ним можно познакомиться по книге Ерщова Ю.Л. и Палютина Е., включенной в список литературы.


Приведем доказательство теремы 3.5. Предположим противное, т.е. предположим, что существует формула F(x,y) логики первого порядка такая, что для любой интерпретации j с областью М и любых a,bÎM выполняется эквиваленция


(jF)(a,b)Û(jP)+(a,b).


Рассмотрим следующее множество формул


K={E0(x,y), E1(x,y),…, En(x,y),…}:

E0=(x,y)=ØP(x,y)

E1(x,y)=Ø($z1)[P(x,z1)&P(z1,y)],

E2(x,y)=Ø($z1)($z2)[P(x,z1)&P(z,z2)&P(z2,y)],

En(x,y)=Ø($z1)…($zn)[p(x,z1)&P(x,z2)&…&P(zn,y)],

. . .

Используя определение транзитивного замыкания и предположение о том, что формула F(x,y) определяет транзитивное замыкание, получаем, что формула ØF(x,y) есть логическое следствие множества формул K. По тереме компактности ØF(x,y) есть логическое следствие некоторого конечного подмножества K′ множества K. Можно считать, что


K′={E0(x,y), E1(x,y),…, Ed(x,y)}


для некоторого d.

Пусть М={0,1,…,d+1,d+2}. На множестве М определим двухместный предикат S следующим образом:


S(u,v)Ûu+1 равно v


Например, высказывания S(0,1), S(1,2) истинны, а высказывание S(0,2) ложно. Отметим, что высказывание S+(0,d+2) истинно. Рассмотрим интерпретацию j, для которой (jP)(u,v)=S(u,v). Все высказывания (jE0)(0,d+2), (jE1)(0,d+2),…(jEd)(0, d+2) истинны. Так как формула ØF(x,y) есть логическое следствие множества формул K′, то истинно высказывание Ø(jF)(0, d+2). С другой стороны, поскольку F(x,y) определяет транзитивное замыкание и истинно высказывание S+(0, d+2) (другими словами, высказывание (jP+)(0, d+2)), то истинно высказывание (jF)(0, d+2). Мы доказали, что истинно и последнее высказывание, и его отрицание. Полученное противоречие показывает, что не существует формулы логики первого порядка, определяющей транзитивное замыкание предиката.

Теорема доказана.

§9. Многосортная логика первого порядка

Задачи

Ответы, указания и решения

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru