книги / Математическая логика и теория алгоритмов. Логика предикатов

У праж нение 1.4. Используя равенства (1.1), докажите, что

(о, (b,c,d)) = (a,b,c,d).

У пражнение 1.5. Используя равенства (1.2), докажите, что

{А х В) х {С х D) = А х В х С х D.

Наконец, следует уточнить понятие «универсальное множество». Действительно, если считать, что элементами множества U являются элементы всевозможных рассматриваемых множеств, то все кортежи также будут включены в это множество, а значит, для любого п имеем Un Ç {/, что неудобно хотя бы тем, что в таком случае если множество U не пусто, то оно оказывается бесконечным, поскольку вместе с любым элементом а содержит также (а, а), (а, а, а) и вообще все кортежи вида (а,... , а). Поэтому следует пояснить, что элементами множества U яв­ ляются только предметы, рассматриваемые как кортежи длины 1. Для любого натурального п множество Un составляют все предметы, рас­ сматриваемые как кортежи длины п.

Из возможности убирать в записи кортежей внутренние скобки сле­ дует, что Um х Un = Um+n для любых га,п 6 N. Действительно, эле­ ментами множеств как в левой, так и правой частях этого равенства являются котежи длины т + п.

П ример 1.12. Если а>b}с, d € [/, то ((о, Ь), (с, d)) G (U2)2 = ï/4.

П ример 1.13. Пусть U = {(о, 6), (с, d)}. Тогда

и2 = {(о, b, а, Ь), (а, Ь, с, d), (с, d, a, b), (с, d, с, d)}.

1.5.Многоместные предикаты

Декартово произведение п множеств есть множество, элементами которого являются кортежи длины п. Обратное неверно: не всякое мно­ жество, элементы которого кортежи длины п, является декартовым про­ изведением.

Все декартовы произведения А,- х Aj, где i,j € {0,1, 2 ,3}, нетрудно пе­ речислить:

Кортежи длины 2 из элементов множества U составляют множество U2. Заметим, что не все его подмножества находятся среди перечисленных выше множеств: например, множества {(0,1), (1,0)} там нет. Оно не яв­ ляется декартовым произведением вида А{ х Aj.

У праж нение 1.6 . Докажите, что множество D всех таких корте­ жей (я,?/), что я, г/ е R и х = у, не является множеством вида А х В, где А, В Ç R.

Бели множество кортежей конечно и количество его элементов неве­ лико, то определить его можно перечислением элементов:

Mi = {(1,1,1), (2,4,8), (3,9,27)},

М2 = {(Иван, Мария), (Петр, Екатерина)}.

Но очевидно, что существуют удобные способы определения и некоторых бесконечных множеств: например, описание множества Д приведённое в упражнении 1.6, достаточно ясно и однозначно, чтобы его можно бы­ ло считать определением. Нельзя ли кратко записать его по аналогии с тем, как мы определяли множества с помощью одноместных предика­ тов, в виде

D = {(я, у) е R2 1я = у}?

Забегая вперед, скажем: именно подобным образом мы обычно и будем записывать определения множеств кортежей. А пока разоберёмся в ло­ гической структуре этого выражения.

В первую очередь проясним, какую роль играет равенство х = у. В математике равенство двух объектов — это отношение между ними.

В данном случае объекты обозначены буквами се и у. Поскольку указано, что (х, у) € R2, то х и у — числа. Отношениями между двумя числами х н у являются также, например, «х больше у» и «х кратно у». Если х и у не числа, а, например, люди, то можно рассматривать отношения «х старше у» или «х является родителем у» и т. п.

Любое отношение можно рассматривать как характеристическое свойство кортежей длины 2, составляющих некоторое подмножество мно­ жества С/2. Например, определённое выше множество!) является множе­ ством кортежей (х,у), характеристическим свойством которых является справедливость равенства х = у.

Напомним, что характеристические свойства элементов подмно­ жеств множества U называются одноместными предикатами. Отношения называют двуместными предикатами. Как и одноместные, двуместные предикаты обозначаются предикатными символами. Если символом Р обозначен одноместный предикат, то выражение Р(х) рассматривается как утверждение, что предмет х обладает свойством Р. В этом утвер­ ждении х является подлежащим, а предикат Р описывает его. Выраже­ ние Р(х, у), где символом Р обозначен двуместный предикат, трактуется как утверждение, которое можно перевести на русский язык предложе­ нием вида: «Предметы х и у таковы, что... » Здесь имеется два подлежа­ щих х и у, а предикат Р описывает их. Аналогично вводятся п-местные предикаты и для любого целого п > 2: запись вида Р(хi , ... ,хп), где Р — предикатный символ, трактуется как утверждение, которое можно перевести на русский язык предложением с п подлежащими «Предме­ ты x i , ... , хп таковы, что... » Обратим внимание, что символы x i, ..., хп нельзя, вообще говоря, менять местами, не изменяя при этом смысла предложения. Число тг, которое ставится в соответствие предикатному символу и указывает, что данный предикат является n-местным, назы­ вается местностью предиката. Часто n-местные предикаты называют предикатами местности п.

П ример 1.15. Пусть U = R, а двуместные предикаты Е н М опи­ сывают отношения соответственно «равно» и «больше». Тогда смысл утверждений Е{х,у) и Я(у,х) одинаков, поскольку х = у у = х. Двуместные предикаты, обладающие таким свойством, называют сим­ метричными. Предикат М не является симметричным: М(х, у) означа­ ет, что х > у, а М (у,х) — что у > х.

Пример 1.16. Рассмотрим множество участников танцев из приме­ ра 1.9. Утверждение «я и у составляют пару» определяет симметричный двуместный предикат, но ничего не говорит о том, кто из я и у юноша, а кто девушка. В утверждении «(я, у) G В х G есть пара» нельзя по­ менять местами я и у без изменения смысла утверждения, а значит, оно определяет несимметричный предикат.

Определение множества через указание n-местного предиката как характеристического свойства его элементов записывается в виде

s = {(®1 , •.., я„) I Р (я и . . . . я„)},

где S — определяемое множество; Р — предикатный символ; я ^ ... , хп — переменные. Эта запись предполагает, что универсальное множество U задано и (a?i,... ,я п) G 17Л. Но часто бывает нужно рассматривать мно­ жества не всех кортежей из t/n, удовлетворяющих данному предика­ ту, а только таких, что элементы Я1, . . . , я п принадлежат множествам X i , . . . , X n, соответственно. В таких случаях используется следующая запись определения:

которую нужно понимать так: S есть множество всех таких кортежей (яь ... ,я„), где xi G X i , ... ,я„ € Х п, что Р(хи ... ,я п).

Пример 1.17. Рассмотрим три определения:

Si = {(я, у, z) I х2 + у2 + z2 = Я2};

St = {(я, У,z) 6 [0, +оо)3 \х2+ у2+ z2= Я2};

Si = {(я, у, z) € Ж х [0, +оо) х {0} | я 2 + у2 + 22 = Я2}.

Множество iSi можно считать определённым, только если известно уни­ версальное множество. Поскольку понятно, что я, у и г - действитель­ ные числа, то в определениях, подобных приведённому, обычно предпо­ лагается, что (я, у, z) G R3. В таком случае S\ является сферой радиусаR с центром в начале координат. В определении множества S2 универсаль­ ное множество задано явно — это [0, +оо). Таким образом, S2— это часть сферы (1/ 8), находящаяся в первом октанте. Множество S3 является пе­ ресечением сферы Si со множеством R х [0, +оо) х {0}, которое есть полуплоскость у > 0 в плоскости z = 0; таким образом, S3 является полуокружностью в плоскости Z = 0.

Предикаты часто определяются через другие предикаты, в том чис­ ле через предикаты другой местности. Для этого используются логиче­ ские операции, одну из которых мы уже знаем: конъюнкцию, которая обозначается знаком Л и играет ту же роль, что и союз «и». Например, если определены одноместные предикаты Р и (J, то можно определить двуместные предикаты:

fl(z, у) = Р(х) Л Q{x), S(X, у) = Р(х) Л Q(y).

Поэтому множества кортежей длины п часто удобно определять с помощью предикатов местности меньшей, чем п.

Пример 1.18. Пусть U = R. Обозначим

Р(х) х > 0, Q(x) ^ х < 1.

Рассмотрим множества:

Понятно, что Si = (0,+оо). Элементами множества Sfe, являются все такие пары (я, у) е R2, что х > 0. Предикат Р в данном случае рассмат­ ривается как двуместный, но не зависящий от переменной у} которая может принимать любые значения из U. Таким образом, множество есть полуплоскость х > 0. Элементами множества S3 являются все такие пары (х ,у) € R2, что 0 < х < 1, то есть множество S$ — это полоса ши­ рины 1 на плоскости R2. Элементами множества S4 являются все такие пары (х,у) е R2, что х > 0 и у < 1. Значит, множество S4 — это квад­ рант («четверть» плоскости), отсекаемый перпендикулярными прямыми х = 0 и у = 1.

1.6. Предикаты как отображения

Логические операции применяются к предикатам и определяют но­ вые предикаты, аналогично тому, как операции классической алгебры применяются к функциям и определяют новые функции: например, ес­ ли f(x) = т 2, то можно определить д(х, у) = f{x) + f(y) = х2+у2. Ниже

мы введём представление об отображениях — математических объек­ тах, разновидностями которых являются как числовые функции, так и предикаты.

Слово «функция» используется в двух значениях, которые часто не различают, поскольку они определяют друг друга. Во-первых, так называется число, которое ставится в соответствие другому числу, назы­ ваемому аргументом, согласно некоторому правилу. Во-вторых, функци­ ей называется само такое правило. Его можно определять различными способами: выражением естественного языка, формулой, таблицей, чер­ тежом.

Обычно функции обозначают какими-нибудь символами, чаще всего строчными латинскими или греческими буквами. Если после буквы, обо­ значающей функцию, пишется выражение в скобках, то оно обозначает рассматриваемый в данном случае аргумент. Если аргумент не указыва­ ется, то речь идёт о функции как правиле, согласно которому одно число ставится в соответствие другому.

Пример 1.19. Пусть задано правило, согласно которому числу ста­ вится в соответствие его квадрат. Обозначим это правило буквой / . То­ гда запись f(x ) обозначает значение функции / в точке х — в данном случае квадрат величины х. Вместо х может стоять число, переменная, обозначающая число, или алгебраическое выражение. Таким образом, f(x) = х2, в частности /(2) = 4, f(a -h b) = а2 4- 2ab + b2.

Для каждой функции определяется её область определения — мно­ жество чисел, которые в данный момент рассматриваются как аргумен­ ты, и область значений — множество значений, которые функция может принимать. Например, областью определения функции/(х) = х2обычно полагают множество R, а область её значений — это множество [0, +оо); область определения функции д(х) = arcsinæ есть [—1, 1], а область зна­ чений [—л /2,ти/2].

Переход от понятия «функция» к понятию «отображение» состоит в том, что в качестве области определения и области значений допускается использовать любые множества, а не только множества чисел. Опреде­ ление можно дать следующим образом. Пусть заданы два произвольных множества X и У и правило F, которое каждому элементу множества X ставит в соответствие некоторый элемент множества У В таком случае

говорят, что задано отображение F множества X в множество Y11.

Пример 1 .2 0 . В курсе высшей математики изучаются функции нескольких переменных. В частности, выражение

r(x>y>z) = \/x2+ y2+ z2

определяет функцию г, которая любой точке эвклидова пространствам3 с координатами {x,y>z) ставит в соответствие расстояние от неё до начала координат. Имеем: r: R3 -¥ R. Можно написать и точнее: г: R3 -> [0,-Ьоо).

Пример 1.21. Пусть Rnxn — множество всех действительных мат­ риц размера п х п. Тогда для любой матрицы A G Rnxn существует её определитель det А Имеем: det: Rnxn R.

Пример 1.22. Пусть Со — множество всех заданных на множе­ стве R непрерывных функций, а С\ — заданных на R непрерывно диф­ ференцируемых функций. Тогда для всякой функции / G С\ определена её производная / ' G CQ. Полагая Df = /', определяем отображение

D: Ci —>Со (оператор дифференцирования).

Теперь покажем, что предикаты можно рассматривать как отобра­ жения.

Пусть символ И обозначает понятие «истина*, а символ Л — понятие «ложь*. Задумываться о философском или каком-либо ином смысле этих понятий пока не будем12.

Определим множество® = {И,Л}.

Определение 1.7. Предикатом называется отображение некоторо­ го множества во множество ®.

11Синонимом термина «отображение* является термин «оператор*; говорится: «оператор F действует из X в У*.

12Даже признавая математику высшим проявлением человеческого интеллекта, стоит помнить, что всё-таки она является инструментом в основном «для низкой жизни*, и не трактовать математические понятия слишком широко.

Данное определение необходимо соотнести с понятием о предика­ тах, сложившемся по предыдущим разделам. Это делается следующим образом. Запись

трактуется как утверждение, что элементами множества S являются те и только те элементы множества X, для которых Р(х) = И. Это по­ следнее равенство, таким образом, означает то же самое, что мы имели в виду, когда говорили, что утверждение Р{х) истинно (верно, справед­ ливо, соответствует действительности).

Определение (1.4) можно переписать так:

сильны: они определяют предикат Р и множество S друг через друга. Если определить каким-либо образом один из этих объектов, то окажется определённым и другой.

Пусть универсальное множество U задано. Тогда любой тг-местный предикат является отображением множества Un во множество В. Рас­ смотрим теперь множества: 1) всех подмножеств множества Un) 2) всех n-местных предикатов. Положим X — Un. Выражениями (1.4) и (1.5) между множествами п. 1 и п. 2 устанавливается взаимно однозначное со­ ответствие: каждому множеству S ÇUn соответствует предикат Р , опре­ деляемый формулой (1.4), и наоборот, каждому предикату P: Un -> В соответствует множество S Ç Un) определяемое формулой (1.5).

П ример 1.23. Определим предикат М: R2 -+ В формулой

Тогда SM = {s € R2 | М(х,у)} есть множество всех точек плоскости, лежащих выше прямой х = у.

П ример 1.24. Пусть Rnxn — множество всех действительных мат­ риц размера n x n u N = {А € Rnxn | det Л ф 0}. Определим предикат

PN : Rnxn -> Шформулой

если A 6 N\

PN (A) =

если A £ N.

Имеем: PN (A) = И тогда и только тогда, когда линейная алгебраическая система Ах —у имеет единственное решение,

Задачи

1.1. Пусть а, Ь, с, d £ R, а < b < с < <£ Определим множества

Л х В на координатной плоскости R2?

1.2. В примере 1.14 перечислены все множества вида Ai х Aj Ç {О, I}2, из которых 11 различных. А сколько всего различных подмножеств множества {О, I}2?

1.3.Пусть Л, В и С — произвольные множества. Установите взаимно однозначное соответствие между множествами А х В х С и ВхСхА.

1.4.Докажите, что если множества Л, В, С и D не пусты, то

A Ç B n C Ç D & A x C Ç B x D .

1.5. Используя определение кортежа длины п и равенство (1.1), докажи­ те, что если х = (я?1, ... , Tfc), где х\ G Unit ..., хп € Unk}то я G t/n, где n = ni + ... + п*.

1.6. Пусть множество U содержит 5 элементов. Сколько существует раз­ личных двуместных предикатов P: U2-> В? Больше ста?

Глава II. Логические операции

Логические рассуждения являются неотъемлемой составляющей че­ ловеческого мышления. Средства передачи их содержания имеются в лю­ бом естественным образом сложившемся языке, в частности в русском. Но, будучи универсальным средством общения, язык призван решать и многие другие задачи: выражать чувства, настроения, эмоции и вооб­ ще многое, что к логике не сводится. Для исполнения чисто логических функций используется только небольшая часть языковых средств. По­ этому оказывается, что богатство естественного языка делает его крайне неудобным инструментом передачи информации в случаях, когда требу­ ется только «железная логика».

Здесь имеет место то же явление, что не позволяет человеку успеш­ но соперничать с компьютером в скорости исполнения арифметических действий. Если оценивать возможности компьютера человеческими мер­ ками, его следует признать идеальным работоспособным идиотом: он работает только с крайне узким классом задач, но со своими задача­ ми справляется гораздо лучше человека — для этого его и создавали. Аналогично можно сравнить возможности живого универсального ин­ струмента — человеческой — руки и искусственного узкоспециализиро­ ванного подъёмного крана.

Таким образом, для точной передачи логических рассуждений, и тем более для их построения, имеет смысл создать узкоспециальное искус­ ственное средство. Передача информации должна быть организована по возможности наиболее просто: так, чтобы можно было доверить её авто­ матическому устройству — тому же компьютеру. Представлять инфор­ мацию нужно в доступном для его «понимания» виде, то есть как после­ довательность стандартных сигналов. Следовательно, требуется создать специальный формальный язык, выражения которого представляют со­ бой составленные по строго определённым правилам последовательности элементов некоторого множества, например типографских знаков.

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