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

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

5.1. МНОЖЕСТВА

5.1.1. Независима ли следующая система множеств:

X Y

5.1.2. Мы научились проверять на диаграммах булевы равенства. А как

с булевыми вложениями (утверждениями формы X ⊂ Y, где X и

Y — булевы выражения)?

5.1.3. Построить независимые системы из четырех и пяти множеств.

5.1.4. (Для тех, кто хорошо знает геометрию.) Доказать, что нет незави-

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

кости.

5.1.5. (Для тех, кто очень хорошо знает геометрию.)

1. Сколько независимых множеств может быть изображено ша-

рами в

n-мерном пространстве?

2. Докажите,что нет независимой системы пяти выпуклых мно-

жеств на плоскости.

3. Сколько независимых множеств может быть изображено вы-

пуклыми областями в

n-мерном пространстве?

5.1.6. Проверить булевы тождества:

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

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

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

(A \ B) \ C = (A \ C) \B;

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

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

(A4(B4C)) = (A ∪B ∪ C) \ (A ∩ B) \ (A ∩ C) \ (B ∩ C);

(A4B) ∪ (B4C) ∪ (C4A) = (A ∪B ∪ C) \ (A ∩ B ∩ C);

(A4B)4(B4C)4(C4A) = (A \

B) ∩ (B \

C) ∩ (C \

A);

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

10. (A \ B) ∪ (B \ C) = (A \ C) ∪ (C \ B);

11.

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

12.

(

B) ∪(

C) ∪(

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

13.

((A \B) \C) ∪((B \C) \A) ∪((C \A) \B) = (A ∪B ∪C) \

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

14.

(A \ B) ∪(B \ C) ∪(C \ D) ∪ (D \A) = (A ∪B ∪ C ∪D) \

(A ∩ B ∩ C ∩ D);

15.

(A4B)4(C4D) = (A4D)4(C4B);

16.

(A \ B \ C) ∪ (B \ C \ D) ∪ (C \ D \ A) ∪ (D \ A \ B) =

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

17.

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

18.

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

19.

((A ∪B)4(A ∪C))4(B ∪C) = (A ∪B ∪C)4(A ∩B ∩C).

5.1.7. Построить диаграмму Эйлера для следующей совокупности по-

нятий:

{горожане, селяне, рабочие, пенсионеры, безработные}.

5.1.8. Постройте диаграмму Эйлера для понятий, встречающихся в пе-

речисленных ниже предложениях, в предположении, что все вы-

сказанные утверждения истинны. Универс — участники олимпи-

ад по физике, математике и программированию.

Ни один парень не стал призером всех трех олимпиад.

Ни одна девушка не стала призером не менее чем двух олим-

пиад.

Никто из симпатичных участников не вошел в число призе-

ров ни по математике, ни по программированию.

5.1.9. Аналогично для следующих предложений.

Поэты — хорошие люди.

Все хорошие люди — поэты либо отшельники.

Ни поэты, ни отшельники не могут быть палачами.

Палач — художник тогда и только тогда, когда он — китаец.

5.1. МНОЖЕСТВА

Китайцы — хорошие палачи.

Китайские отшельники — поэты.

5.1.10. (Порецкий) Относительно девиц, бывших на некоем бале, из-

вестны следующие 14 утверждений:

1. Каждая из девиц была или благовоспитанна, или весела, или

молода, или красива;

2. все нетанцующие девицы были некрасивы, каждая из танцу-

ющих была или молода, или красива, или благовоспитанна;

3. когда пожилые девицы образовали отдельный кружок, о ка-

ждой из оставшихся можно было сказать, что она или краси-

ва, или весела, или благовоспитанна;

4. если выделить всех девиц немолодых и некрасивых, то оста-

нутся лишь благовоспитанные и веселые девицы;

5. если же выделить всех девиц невеселых, то останутся благо-

воспитанные, молодые и красивые;

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

бы вдобавок ни красотой, ни благовоспитанностью, на балу

не было;

7. между молодыми девицами не было таких, которые, обладая

красотой и веселостью, были бы не благовоспитанны;

8. каждая благовоспитанная девица была или молода, или ве-

села, или красива;

9. все девицы, соединявшие красоту с благовоспитанностью,

были одни веселы, другие молоды;

10. каждой невеселой девице недоставало или молодости, или

красоты, или благовоспитанности;

11. все те веселые девицы, которые, не отличаясь молодостью,

обладали благовоспитанностью, были красивы;

12. немолодые девицы были одни не благовоспитанны, другие

не веселы, третьи не красивы;

13. между некрасивыми девицами не было таких, которые с бла-

говоспитанностью соединяли бы молодость и веселость;

14. и,наконец, когда уехали все неблаговоспитанные, невеселые,

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

лось.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Возможно ли такое? Если возможно, постройте диаграмму Эйлера

для девиц бала и выведите из нее отношения между различными

их категориями.

5.1.11. Разработайте способ проверки условных тождеств следующего

вида:

если

X = Y , то U = V

на диаграммах, подобных диаграммам Эйлера и Венна.

§ 5.2. КОРТЕЖИ,

-КИ, НАБОРЫ, ПРЯМЫЕ

ПРОИЗВЕДЕНИЯ, ПРЯМЫЕ СУММЫ

Если бы роль множеств исчерпывалась тем, что они превращают логи-

ческие операции в математические, это понятие не играло бы столь важ-

ную роль в современной математике. Понятия переводят в объекты за-

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

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

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

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

важным для приложений и в обыденной жизни, и в программировании.

В программировании и искусственном интеллекте кортежи часто пута-

ют с множествами

Определение 5.2.1. Кортеж

—конечная последовательность объектов,

называемых его

членами

. Кортеж с членами

, . . . , a

, расположен-

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

, . . . , a

]

. В математической

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

шинстве приложений — начиная с первого

Таким образом, в отличие от множеств, кортеж может содержать и

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

рядок, в котором они расположены. Итак,

[a, b] 6= [b, a], [a, a] 6= [a].

Что служит неисчерпаемым источником ошибок, в том числе и тонких. Особенно

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

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

Так что не поленитесь выяснить это, если Вам говорят о кортежах!

5.2. КОРТЕЖИ,

-КИ, НАБОРЫ

Как и в других случаях (в частности, для множеств), принято рас-

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

просто [ ]. Кортеж из одного элемента обозначается [x] и строго разли-

чается от самого x. Для кортежей определены следующие стандартные

функции: длина кортежа

x lh(x)

— число членов в кортеже. Функция

выделения

i-той компоненты:(x)

, где i 6 lh(x) (если счет членов начи-

нают с нуля, то неравенство становится строгим). Операция соединения

(либо конкатенации) двух кортежей:

, . . . , a

] ∗ [b

, . . . , b

] = [a

, . . . , a

, b

, . . . , b

Стоит выделить как фундаментальную еще одну операцию, которая от-

личается от предыдущей по типам данных: присоединение объекта к

кортежу. Обычно для нее используют заимствованный из языка ЛИСП

идентификатор APPEND:

APPEND([a

, . . . , a

], a) = [a

, . . . , a

, a]. (5.3)

Множество всех кортежей из элементов множества

U обозначается U

∞

В литературе оно часто обозначается также U

∗

. Мы используем данное

обозначение для более общего множества; см. ниже.

Пример 5.2.1.

Строки в языках программирования могут рассматривать-

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

машинном представлении математического понятия накладываются ре-

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

волов.

Другое, более адекватное представление кортежа — линейные спис-

ки. Они могут быть заданы следующими описаниями языка Паскаль

(

data

— некоторый ранее определенный тип данных):

type

record

element: data;

next: ^t

end

;

Рассмотрим более сложное построение. Кортежи могут строиться

из других кортежей и т. п. Такое представление интенсивно использу-

ется, в частности, в языке ЛИСП. Хочется иметь универс, включающий

все кортежи кортежей... Чтобы аккуратно его определить, прибегают к

следующей конструкции.

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

Пусть U

= U . Тогда для всякого i определим U

i+1

= U

∪ U

∞

. Та-

ким образом, U

будет множеством всех элементов и кортежей, постро-

енных из элементов, к U

, соответственно, добавятся кортежи кортежей

и элементов и т. д. Теперь определим

∗

∞

[

i=0

(5.4)

Частный случай кортежей —

n-ки, или кортежи с фиксированным

числом членов. Они обозначаются (a

, . . . , a

). Простейший случай

n-ок — пары (a, b). Для n-ок обычно о конкатенации не говорят, при-

меняют лишь проекции.

Операция образования множества всех

n-ок из совокупности мно-

жеств X

, . . . , X

гораздо более элементарна и фундаментальна, чем

операция взятия множества всех кортежей. Она носит название декар-

това (прямого) произведения множеств.

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

Прямое произведение

множеств

, . . . , X

—

множество

×∙∙∙×X

всех

-ок

, . . . , x

, таких, что

∈ X

, ...,

∈ X

Стоит указать еще одну условность, отличающую n-ки от кортежей.

Очевидно, что [a, b, c], [[a, b], c] и [a, [b, c]] — разные кортежи. Но декар-

товы произведения A × B × C, (A × B) × C, A × (B × C), как прави-

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

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

дано определением 5.2.2

Есть еще одна условность. Если принимается ассоциативность пря-

мого произведения и одновременно принимается, что элементарной опе-

рацией является построение пары

(a, b),то тройка (a, b, c) представляет-

ся как ((a, b), c), четверка (a, b, c, d) — как (((a, b), c), d) и т. д. Как гово-

рят, скобки группируются влево

. Если множество R ⊂ X

× ∙∙∙ × X

(т. е. его элементы — n-ки), то на R переносятся операции взятия про-

Да, и математики порою грешат “двоемыслием”: пишется одно, имеется в виду дру-

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

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

в 60-х гг. нашего века. См. § 5.7.

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

торной логике.

5.2. КОРТЕЖИ,

-КИ, НАБОРЫ

екции по любому компоненту i от 1 до n.

R =



x ∈ X

& ∃x

. . . ∃x

i−1

∃x

i+1

. . . ∃x

, . . . , x

i−1

, x, x

i+1

, . . . , x

) ∈ R



(5.5)

Таким образом, проекция отношения состоит из всех объектов, стоящих

на

i-том месте в n-ках из данного отношения.

Важный и выделяемый отдельно случай декартова произведения —

когда все его компоненты одинаковы. Прямое произведение n сомножи-

телей U называется декартовой степенью и обозначается U

. U

ото-

ждествляется с U, так что n-ка (x), состоящая из одного элемента, ото-

ждествляется с самим x

n-ки (и даже пары) позволяют выразить еще одну операцию над

множествами, полезную, в частности, при интерпретации структур про-

граммирования. Это — прямая сумма. Всем бы хорошо объединение

множеств, да в том случае, если нужно сохранить информацию, от ка-

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

для непересекающихся множеств. Поэтому еще с начала нашего века

начала проскальзывать операция непересекающегося объединения, ко-

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

а уже затем объединяли.

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

Прямая сумма

множеств

, . . . , X

— множе-

ство

⊕ ∙∙∙ ⊕ X

всех пар

(i, x)

, таких, что

x ∈ X

Другими словами,

⊕ ∙∙∙ ⊕ X

= {(i, x) | 1 6 i 6 n & x ∈ X

}. (5.6)

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

понента, от которого он произошел. Это дает возможность определять

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

соот-

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

ствующего X

, и обратно, определять по любому отображению прямой

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

как декартово произведение двух прямых, а пространство — трех. Более общих поня-

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

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

математическому понятию, а целой науке — искусственному интеллекту, восприняв-

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

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

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

суммы, что же оно делает на каждом из X

. Если для прямого произ-

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

вложения in

каждого из ее членов в данную сумму. Если подмножества

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

то подмножества прямой суммы можно разбить на непересекающееся

объединение подмножеств компонент.

Далее, если задано отображение каждого из

, то можно опреде-

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

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

зультаты в n-ку. И наоборот, если задано отображение, результатами ко-

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

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

ждое из X

. А имея n таких отображений, можно задать отображение в

прямую сумму.

В современном программировании концепция прямого произведе-

ния породила структуру данных запись (recordв Паскале.) Прямая сум-

ма породила записи с вариантами. А запись с вариантами порождает

соответствующий ей оператор выбора case, разбирающий случаи в со-

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

несколько вариантов действий в один оператор.

Прямые суммы также считаются ассоциативными.

Другие операции над множествами описаны,например,в книге [20].

Напомним еще одно из базовых понятий прикладной математики,

практически игнорируемое в теоретической. Это — набор (или муль-

тимножество). Набор отличается от множества тем, что в нем могут

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

кортежа тем, что в нем несуществен порядок элементов. Два набора рав-

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

Естественно, что порядок элементов в наборе не имеет значения. Набор

обозначается ba

, . . . , a

c, но эта запись не столь общеупотребительна,

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

, . . . , a

, если это явно оговорено в контексте

Операция объединения распадается для наборов на две: аналог тео-

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

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

борах, и соединения ⊕, когда число экземпляров равно сумме чисел в

Во всяком случае, кортежи и множества так не обозначаются.

5.2. КОРТЕЖИ,

-КИ, НАБОРЫ

исходных наборах. Очевидно, что соединение

уже не есть

. Для

наборов

ba, bc = bb, ac, ba, ac 6= bac.

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

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

имеет собственное имя, и нет двух элементов с одинаковыми именами.

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

5.2.1. Пусть

S — трехместное отношение между студентами, универ-

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

находятся. Как Вы выразите его проекцию по третьему компонен-

ту?

5.2.2. Докажите, что имеется взаимно-однозначное отображение

A ×

B × C на A ×(B × C), сохраняющее pr

и переводящее pr

(x) в

(pr

(x)), a pr

(x) в pr

(pr

(x)).

5.2.3. Сравнив определение декартовой степени и множества всех кор-

тежей,объясните,почему множество всех кортежей получило обо-

значение

∞

5.2.4. Для кортежей и множеств одноэлементные структуры строго от-

личаются от самих объектов;для

n-ок они отождествляются с объ-

ектами. А как для наборов? Обоснуйте свое мнение.

5.2.5. Можно ли выразить через наши фундаментальные операции над

кортежами операцию

λx .[x], переводящую каждое x в соответ-

ствующий одноэлементный кортеж.

5.2.6. Часто в математических определениях используют понятие “не-

упорядоченная пара”. Компоненты неупорядоченной пары не раз-

личаются по месту, так что

(a, b) = (b, a). Определите это понятие

через одно из имеющихся у нас.

5.2.7. Определите именованные множества через множества пар.

5.2.8. Верно ли для кортежей a ∗b = b ∗a? Если да, докажите, если нет,

приведите опровергающий пример

Как говорилось во Введении, мы часто ставим задачи в форме “Верно ли?” Такая

постановка предполагает не меньшую, чем здесь, строгость и обоснованность ответа:

мы математики!

ГЛАВА 5. БАЗОВЫЕ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

5.2.9. Верно ли для наборов A ⊕ B = B ⊕ A?

5.2.10. Определите операцию пересечения наборов.

5.2.11. Что могло бы играть роль универса для наборов и как опреде-

лить дополнение?

5.2.12. Пусть задано отображение

A × B в C. Всегда ли из него можно

получить пару отображений: из A в C и из B в C?

5.2.13. Верно ли, что

(X ∪ Y ) = pr

X ∪ pr

Y ?

5.2.14. Верно ли, что

(X ∩ Y ) = pr

X ∩ pr

Y ?

5.2.15. Студент Интеллектуалов определил неупорядоченное произве-

дение n множеств X

, . . . , X

как множество всех n-членных

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

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

5.2.16. Аргументируйте, можно ли принимать коммутативность прямо-

го произведения или прямой суммы?

§ 5.3. ОТНОШЕНИЯ

Среди прямых произведений особенно важную роль играют произведе-

ния двух множеств, и соответственно, среди n-ок — пары.

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

Подмножество

прямого произведения

X ×Y

на-

зывается

отношением (соответствием) между X

R ⊂ X × X

называется

отношением (соответствием) на X

Два термина, приведенных в данном определении, соответствуют

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

ношение, нас интересуют взаимосвязи между x ∈ X и y ∈ Y . Если мы

говорим про соответствие, то в некотором смысле мы рассматриваем R

как описание возможностей преобразовать x в y.

Осторожнее! При ответе на одну из двух последних задач ошибся знаменитый фран-

цузский математик А. Пуанкаре.

Даже если Вы считаете, что опровергли данное определение или поставили его под

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