Файл: Журавлев Флеров Дискретный анализ МФТИ 1991.pdf

46

ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ

ìíîæåñòâà (

v

øòóê), à òàêæå ìíîæåñòâî

S

r

îáðàçóþò

v

+ 1

ìíîæåñòâî, êî-

òîðûå ñîäåðæàò òîëüêî

v

ðàçëè÷íûõ ýëåìåíòîâ, òàêèì îáðàçîì ìû íàøëè

ìíîæåñòâà, íàðóøàþùèå óñëîâèå C.

Åñëè æå èìååò ìåñòî ñëó÷àé 1, ìû íà íåêîòîðîì ýòàïå íàõîäèì ýëå-

ìåíò

b

i

=

b

i

1

(

i

1

> t

)

, êîòîðûé âõîäèò âî ìíîæåñòâî

S

j

1

, ïðåäñòàâèòåëåì

êîòîðîãî ÿâëÿåòñÿ âûáðàííûé ðàíåå äðóãîé ýëåìåíò

b

i

2

, ïðè÷åì

i

2

< i

1

.

Åñëè

i

2

> t

, òî çíà÷èò

b

i

2

∈

S

j

2

, à ïðåäñòàâèòåëåì ìíîæåñòâà

S

j

2

ÿâëÿåòñÿ

b

i

3

∈

S

j

3

(

i

3

< i

2

)

è òàê äàëåå. Òàêèì îáðàçîì, âîçíèêàåò ïîñëåäîâàòåëü-

íîñòü

b

i

1

, b

i

2

, . . . , b

i

m

, èíäåêñû êîòîðîé óáûâàþò

(

i

m

≤

t

)

, ïðè÷åì â ýòîé

ïîñëåäîâàòåëüíîñòè êàæäûé åå ÷ëåí âõîäèò âî ìíîæåñòâî, ïðåäñòàâèòå-

ëåì êîòîðîãî ÿâëÿåòñÿ ñëåäóþùèé ÷ëåí. Íî òåïåðü ìû ìîæåì çàìåíèòü

ïðåäñòàâèòåëåé: âîçüìåì

b

i

1

â êà÷åñòâå ïðåäñòàâèòåëÿ

S

j

1

,

b

i

2

 â êà÷å-

ñòâå ïðåäñòàâèòåëÿ

S

j

2

, . . . , b

i

m

−

1

 äëÿ

S

j

m

−

1

. Ýëåìåíò

b

i

m

â ðåçóëüòà-

òå òàêîé çàìåíû îñâîáîæäàåòñÿ äëÿ âûáîðà â êà÷åñòâå ïðåäñòàâèòåëÿ

S

r

.

Èòàê, ìû, äåéñòâóÿ òåì æå ïóòåì, íàéäåì ïðåäñòàâèòåëÿ

S

r

+1

è òàê äàëåå.

Íàøè ïîñòðîåíèÿ çàêîí÷àòñÿ ëèáî âûáîðîì ñèñòåìû ðàçëè÷íûõ ïðåäñòà-

âèòåëåé, ëèáî ìû îáíàðóæèì ñèñòåìó ìíîæåñòâ, äëÿ êîòîðîé íàðóøàåòñÿ

óñëîâèå Ñ.

1.21. Ïðèìåð. Ïóñòü èìååòñÿ ñëåäóþùàÿ ñèñòåìà ìíîæåñòâ:

S

1

=

{

1

,

2

}

;

S

2

=

{

2

,

3

}

;

S

3

=

{

3

,

4

}

;

S

4

=

{

5

,

2

}

;

S

5

=

{

4

,

6

}

;

S

6

=

{

1

,

5

}

.

Áóäåì îáîçíà÷àòü âûáîð ýëåìåíòà

b

â êà÷åñòâå ïðåäñòàâèòåëÿ ìíîæå-

ñòâà

S

çàïèñüþ

b

=

P

(

S

)

.

Ïîñëåäîâàòåëüíî âûáåðåì ñëåäóþùèõ ïðåäñòàâèòåëåé ìíîæåñòâ:

1 =

P

(

S

1

); 2 =

P

(

S

2

); 3 =

P

(

S

3

); 5 =

P

(

S

4

); 4 =

P

(

S

5

)

.

Äîéäÿ òàêèì îáðàçîì äî ìíîæåñòâà

S

6

, ìû îáíàðóæèâàåì, ÷òî âñå ýëåìåí-

òû ìíîæåñòâà

S

6

óæå èñïîëüçîâàíû êàê ïðåäñòàâèòåëè äðóãèõ ìíîæåñòâ.

Ñòðîèì ïîñëåäîâàòåëüíîñòü ìíîæåñòâ

T

0

, T

1

, . . .

:

T

0

=

{

1

,

5

}

T

1

=

S

(1)

\

T

0

=

{

2

}

T

0

=

{

1

,

5

,

2

}

T

2

=

S

(5)

\

T

0

=

∅

T

3

=

S

(2)

\

T

0

=

{

3

}

T

0

=

{

1

,

5

,

2

,

3

}

T

4

=

S

(3)

\

T

0

=

{

4

}

T

0

=

{

1

,

5

,

2

,

3

,

4

}

T

5

=

S

(4)

\

T

0

=

{

6

}

T

0

=

{

1

,

5

,

2

,

3

,

4

,

6

}

Òàêèì îáðàçîì, ïåðåäâèãàÿñü ïî ýëåìåíòàì ìíîæåñòâà

T

0

=

{

1

,

5

|{z}

S

6

,

2

|{z}

S

1

,

3

|{z}

S

2

,

4

|{z}

S

3

,

6

|{z}

S

5

}

1.6. ÑÈÑÒÅÌÛ ÏÐÅÄÑÒÀÂÈÒÅËÅÉ ÌÍÎÆÅÑÒÂ

47

ìû, íàêîíåö, äîñòèãàåì ýëåìåíòà 6, êîòîðûé íå ÿâëÿåòñÿ ïðåäñòàâèòåëåì

íèêàêîãî ìíîæåñòâà. Ìû íàøëè ïîñëåäîâàòåëüíîñòü ýëåìåíòîâ 1, 5, 2, 3,

4, 6, òàêóþ ÷òî:

•

ýëåìåíò

6

∈

S

5

, à

P

(

S

5

) = 4

;

•

ýëåìåíò 4 âîøåë â ïîñëåäîâàòåëüíîñòü êàê ýëåìåíò ìíîæåñòâà

S

3

,

4

∈

S

3

, à

P

(

S

3

) = 3

;

•

ýëåìåíò 3 âîøåë â ïîñëåäîâàòåëüíîñòü êàê ýëåìåíò ìíîæåñòâà

S

2

,

3

∈

S

2

, à

P

(

S

2

) = 2

;

•

ýëåìåíò 2 âîøåë â ïîñëåäîâàòåëüíîñòü êàê ýëåìåíò ìíîæåñòâà

S

1

,

2

∈

S

1

, à

P

(

S

1

) = 1

.

Òåïåðü ìû ìîæåì çàìåíèòü ïðåäñòàâèòåëåé, ïîëîæèâ

6 =

P

(

S

5

); 4 =

P

(

S

3

); 3 =

P

(

S

2

); 2 =

P

(

S

1

)

îñâîáîäèâøèéñÿ ýëåìåíò

1

ìîæåò áûòü èñïîëüçîâàí â êà÷åñòâå ïðåäñòàâè-

òåëÿ ìíîæåñòâà

S

6

.

1.6.2 Ñèñòåìû îáùèõ ïðåäñòàâèòåëåé

Èäåÿ çàìåíû ìíîæåñòâ èõ ïðåäñòàâèòåëÿìè îêàçàëàñü ïëîäîòâîðíîé è ïî-

ëó÷èëà ïîñëåäóþùåå ðàçâèòèå. Ñèñòåìû ïðåäñòàâèòåëåé âûäåëÿþòñÿ ñ ó÷å-

òîì óñëîâèé çàäà÷ èëè öåëåé òåîðåòè÷åñêèõ îáîáùåíèé. Íàïðèìåð, çàäà÷è

î ðàçáèåíèè ìíîæåñòâ ïðèâåëè ê ïîíÿòèþ ñèñòåì îáùèõ (îäíîâðåìåííûõ)

ïðåäñòàâèòåëåé.

Ïóñòü äàíû äâà ðàçëè÷íûõ ðàçáèåíèÿ îäíîãî è òîãî æå ìíîæåñòâà S íà

n íåïåðåñåêàþùèõñÿ íåïóñòûõ ïîäìíîæåñòâ:

S

=

A

1

∪

. . .

∪

A

n

=

B

1

∪

. . .

∪

B

n

;

A

i

∩

A

j

=

∅

, i

6

=

j, i, j

∈

[

n

];

B

i

∩

B

j

=

∅

, i

6

=

j, i, j

∈

[

n

]

.

Îïðåäåëåíèå. Åñëè ñóùåñòâóåò ïîäìíîæåñòâî

O

⊆

S

, ñîñòîÿùåå èç

n

ðàç-

ëè÷íûõ ýëåìåíòîâ

x

1

, . . . , x

n

, êîòîðûå ÿâëÿþòñÿ îäíîâðåìåííûìè ïðåäñòà-

âèòåëÿìè ìíîæåñòâ

A

i

è

B

j

òî îíî íàçûâàåòñÿ ñèñòåìîé îáùèõ ïðåäñòà-

âèòåëåé (ñ.î.ï.).

48

ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ

Òåîðåìà 1.22. Äâà ðàçáèåíèÿ ìíîæåñòâà

S

,

S

=

A

1

∪

A

2

∪

. . .

∪

A

n

è

S

=

B

1

∪

. . .

∪

B

n

òîãäà è òîëüêî òîãäà èìåþò ñ.î.ï., êîãäà ëþáûå

m

èç

ìíîæåñòâ

B

i

ñîäåðæàòñÿ íå ìåíåå, ÷åì â

m

èç ìíîæåñòâ

A

j

,

m

≤

n

.

Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü, êàê è â ñëó÷àå c.ð.ï., î÷åâèäíà. Äîñòà-

òî÷íîñòü äîêàçûâàåòñÿ ïðîñòûì ñâåäåíèåì ê òåîðåìå î ñ.ð.ï..

Ðàññìîòðèì

A

1

, . . . , A

n

⊆

S

.

Äëÿ êàæäîãî

B

i

,

i

= 1

,

2

, . . . , m

îïðåäåëèì ìíîæåñòâî

S

i

, ñîñòîÿùåå

èç

A

j

(

j

= 1

, . . . , m

)

ñ òàêèìè èíäåêñàìè

j

, ÷òî

A

j

∩

B

i

íå ïóñòî:

S

i

=

{∪

A

j

|

A

j

∩

B

i

6

=

∅

}

.

Ïîëó÷èì

M

(

S

) =

{

S

1

, S

2

, . . . , S

n

}

.

Äëÿ

M

(

S

)

ñóùåñòâóåò ñ.ð.ï. .

Âûáîð ðàçëè÷íûõ ïðåäñòàâèòåëåé äëÿ êàæäîãî

B

i

äàåò ñâîå

A

j

, ïðè÷åì

ïåðåñå÷åíèå ìåæäó íèìè íå ïóñòî. Â ýòîì ïåðåñå÷åíèè ìîæíî âûáðàòü õîòÿ

áû îäèí ýëåìåíò, îáùèé äëÿ

A

j

è

B

i

, ò.å. îáùåãî ïðåäñòàâèòåëÿ.

Ãëàâà 2

Ôóíêöèè àëãåáðû ëîãèêè

Ñîãëàñíî îäíîìó èç ñàìûõ ðàñïðîñòðàíåííûõ îïðåäåëåíèé, ëîãèêà åñòü

àíàëèç ìåòîäîâ ðàññóæäåíèé. Èçó÷àÿ ýòè ìåòîäû, ëîãèêà ïðåæäå âñåãî

èíòåðåñóåòñÿ ôîðìîé äîâîäîâ, à íå èõ ñîäåðæàíèåì â òîì èëè èíîì ðàñ-

ñóæäåíèè. Ïðàêòè÷åñêèå ïðèëîæåíèÿ ìåòîäîâ ìàòåìàòè÷åñêîé ëîãèêè ê

ïðîåêòèðîâàíèþ è ýêñïëóàòàöèè âû÷èñëèòåëüíûõ è óïðàâëÿþùèõ ñèñòåì

õîðîøî èçâåñòíû.

¾Âûòåêàåò ëè èñòèííîñòü çàêëþ÷åíèÿ èç èñòèííîñòè ïîñûëîê?¿  òà-

êîâ îñíîâíîé âîïðîñ ìàòåìàòè÷åñêîé ëîãèêè. Íåîáõîäèìî èññëåäîâàòü ÿçûê

ëîãèêè è ìàòåìàòèêè, ÷òîáû ðàçîáðàòüñÿ â òîì, êàêèå â íåé ìîãóò áûòü

óïîòðåáëåíû ñèìâîëû, êàê èç ýòèõ ñèìâîëîâ ñîñòàâëÿþòñÿ óòâåðæäåíèÿ è

äîêàçàòåëüñòâà, ÷òî ìîæåò è ÷òî íå ìîæåò áûòü äîêàçàíî, åñëè èñõîäèòü

èç òåõ èëè èíûõ àêñèîì è ïðàâèë âûâîäà. Ñîäåðæàíèåì ìàòåìàòè÷åñêîé

ëîãèêè ÿâëÿåòñÿ èçó÷åíèå ÿçûêà ìàòåìàòèêè. Ðàçóìååòñÿ, çàáîòà î ÿçûêå è

ïîñòîÿííàÿ åãî ïåðåñòðîéêà äëÿ ïðèâåäåíèÿ â ñîîòâåòñòâèå ñ ìåíÿþùèìñÿ

ñîñòîÿíèåì çíàíèé õàðàêòåðíà äëÿ ëþáîé åñòåñòâåííîé íàóêè (äîñòàòî÷íî

âñïîìíèòü ¾ôëîãèñòîí¿ è ¾ìèðîâîé ýôèð¿ â ôèçèêå). Òåì íå ìåíåå, òî

ïðèñòàëüíîå êðèòè÷åñêîå ðàññìîòðåíèå, êîòîðîìó ìàòåìàòèêà ïîäâåðãëà

ñâîè ñðåäñòâà âûðàæåíèÿ è ñàìîå ñåáÿ, ïðåäñòàâëÿåòñÿ óíèêàëüíûì.

Ïðè÷èíà ýòîãî çàêëþ÷àåòñÿ, êîíå÷íî, â òîì, ÷òî âñå îñòàëüíûå íàóêè

èìåþò ïðåäìåòîì èçó÷åíèÿ âíåøíèé ïî îòíîøåíèþ ê íèì ðåàëüíûé ìèð,

è ýâîëþöèÿ ÿçûêà íàóêè îïðåäåëÿåòñÿ ïîñòîÿííûì ñðàâíåíèåì íàó÷íîãî

îïèñàíèÿ ñ îïèñûâàåìîé ðåàëüíîñòüþ. Ïîïûòêà ïðèìåíèòü ýòó æå ñõåìó ê

ìàòåìàòèêå ñðàçó íàòàëêèâàåòñÿ íà ïðèíöèïèàëüíûå òðóäíîñòè: â êàêîì

ñìûñëå ÷èñëà è ìíîæåñòâà ðåàëüíû? Ñòîëü æå íåÿñíûì ïðè âíèìàòåëüíîì

49

50

ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ

ðàññìîòðåíèè ñòàíîâèòñÿ îòâåò íà âîïðîñ, ÷òî åñòü èñòèííîñòü ìàòåìàòè-

÷åñêîãî ðàññóæäåíèÿ. Ïîëîæåíèå äåë çäåñü ìîæíî ñðàâíèòü ñ ïîíÿòèåì

¾ýëåìåíòàðíîé ÷àñòèöû¿ â ôèçèêå. Ýëåìåíòàðíûå ÷àñòèöû  ýòî íå òå

÷àñòèöû, êîòîðûå ÿâëÿþòñÿ ïîñëåäíèìè êèðïè÷èêàìè àíàëèçà, ñêîðåå

ýòî òå îáúåêòû, äàëüíåéøèé àíàëèç êîòîðûõ îáíàðóæèâàåò ñóùåñòâåííîå

ïîâûøåíèå óðîâíÿ ñëîæíîñòè âìåñòî åãî ïîíèæåíèÿ. ¾Ýëåìåíòàðíîñòü¿

ïîíÿòèÿ èñòèíû èìååò ñõîäíûå ÷åðòû.

Ôóíäàìåíòàëüíûå ðåçóëüòàòû Ã¼äåëÿ è äðóãèõ àâòîðîâ íàçûâàþòñÿ òåî-

ðåìàìè î íåïîëíîòå, íåðàçðåøèìîñòè, íåçàâèñèìîñòè. Òàêîãî òèïà ðåçóëü-

òàòû, ïðåäñòàâëÿþùèå î÷åâèäíûé îáùåãóìàíèòàðíûé èíòåðåñ, íå èìåëè

ïðåöåäåíòîâ â ðàçâèòèè ôèëîñîôñêîé ìûñëè äî XX âåêà, è ÿâëÿþòñÿ ñóùå-

ñòâåííûì âêëàäîì åñòåñòâåííûõ íàóê â ôîíä ãóìàíèòàðíûõ, ïîä÷åðêèâàÿ

íåâîçìîæíîñòü ïîëíîé ôîðìàëèçàöèè ìàòåìàòèêè è îáíàæàÿ åå ãëóáîêèé

ãóìàíèòàðíûé ñìûñë.

Ôèçè÷åñêîå ðàññóæäåíèå ïðàâèëüíî, åñëè ïîëó÷åííûå ñ åãî ïîìîùüþ

âûâîäû ñîâïàäàþò ñ ðåàëüíî íàáëþäàåìûìè ôàêòàìè. Êðèòåðèåì èñòèí-

íîñòè ìàòåìàòè÷åñêîãî ðàññóæäåíèÿ ÿâëÿåòñÿ ëèøü åãî ëîãè÷åñêàÿ áåç-

óêîðèçíåííîñòü, âûïîëíåíèå íà âñåõ ýòàïàõ ðàññóæäåíèÿ óñòàíàâëèâàåìûõ

ñàìèì ìàòåìàòèêîì ïðàâèë âûâîäà, îòíîñÿùèõñÿ ê âïîëíå îïðåäåëåííîé

âåòâè ìàòåìàòè÷åñêîé íàóêè  ìàòåìàòè÷åñêîé ëîãèêå. Ïðè ýòîì íà ñåãî-

äíÿøíèé äåíü ìû èìååì âîâñå íå îäèí-åäèíñòâåííûé íàáîð ïðàâèë âûâî-

äà, à ìíîãî ðàçíûõ òàêèõ íàáîðîâ (àíàëîãè÷íî ñóùåñòâîâàíèþ ãåîìåòðèè

Åâêëèäà, ãåîìåòðèè Ëîáà÷åâñêîãî, ãåîìåòðèè Ðèìàíà â ëîãèêå ñóùåñòâóþò

òàêèå ïîäõîäû ê ôîðìàëèçàöèè êàê êîíñòðóêòèâèçì, èíòóèöèîíèçì). Ñâîå-

îáðàçíàÿ ïðèðîäà ìàòåìàòèêè, óïðàâëÿåìîé çàêîíàìè åþ æå ñàìîé ñåáå

óêàçûâàåìûìè, õàðàêòåðèçóåò îñîáåííîñòü ýòîé âåòâè ÷åëîâå÷åñêîé êóëü-

òóðû, íî íå åå åäèíñòâåííîñòü. Èñêóññòâî òàêæå ñàìî ñåáå äèêòóåò ïðàâèëà

èãðû: ðàçðàáîòàííûå Ëåîíàðäî äà Âèí÷è è Äþðåðîì ïðàâèëà ïåðñïåêòè-

âû, êàíîíû ïîñòðîåíèÿ âèçàíòèéñêèõ èëè ðóññêèõ èêîí, ïðàâèëà ¾èêåáà-

íà¿. Ýòè êàíîíû íå ìåíåå íåïðåëîæíû è æåñòêè, ÷åì àêñèîìû ãåîìåòðèè,

è èçìåíèòü ýòè ïðàâèëà ìîæåò ëèøü âûäàþùèéñÿ õóäîæíèê, ïîäîáíî òîìó

êàê íîâûå îáëàñòè ¾ìàòåìàòè÷åñêîé âñåëåííîé¿ íàì îòêðûâàëè Íüþòîí,

Ãèëüáåðò, Ëîáà÷åâñêèé, Áðàóýð.

Îäíèì èç îñíîâíûõ ïðîÿâëåíèé ïðîèñõîäÿùåãî â íàøè äíè îáùåíà-

ó÷íîãî ïåðåâîðîòà, ñâÿçàííîãî ñ âíåäðåíèåì ÝÂÌ è ïîëó÷èâøåãî ó æóð-

íàëèñòîâ êîäîâîå íàèìåíîâàíèå ¾íàó÷íî-òåõíè÷åñêàÿ ðåâîëþöèÿ¿, ÿâëÿåò-

ñÿ êîëîññàëüíàÿ ìàòåìàòè÷åñêàÿ ýêñïàíñèÿ, âòîðæåíèå ìàòåìàòèêè âî âñå

íîâûå, ðàíåå åþ íèêàê íåêîíòðîëèðóåìûå òåððèòîðèè. Ìàòåìàòè÷åñêèìè

ìåòîäàìè øèðîêî ïîëüçóþòñÿ ïðåäñòàâèòåëè ñàìûõ ðàçíûõ  êàê åñòå-