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

pRIMER 4. dLQ x 2 R , y 2 R NAJTI OBLASTX ISTINNOSTI PREDI-

KATA P (y) = (y 6 1) 8x(y 6 x2) .

rE[ENIE. pREDIKAT A(y) = (y 6 1) QWLQETSQ ISTINNYM DLQ y 2 (;1; 1] , A B(y) = 8x(y 6 x2) | ISTINNYJ DLQ y 2 (;1; 0] ,

TOGDA PREDIKAT P (y) = A(y) B(y) BUDET ISTINNYM DLQ y 2 (0; 1] .

x20. pREDWARENNAQ I SKOLEMOWSKAQ FORMA PREDIKATA

pUSTX P(x)	| PREDIKAT, ZAWISQ]IJ OT PEREMENNOJ x , A PRE-
DIKAT Q NE ZAWISIT OT x (MY NE BUDEM ZDESX, DLQ PROSTOTY, UKA-
ZYWATX OSTALXNYE PEREMENNYE, OT KOTORYH ZAWISQT P I Q ).
sWOJSTWO 1.	Q _ 9x P (x) = 9x(Q _ P (x)) .
sWOJSTWO 2.	Q ^ 9x P (x) = 9x(Q ^ P (x)) .
sWOJSTWO 3.	Q _ 8x P (x) = 8x(Q _ P (x)) .
sWOJSTWO 4.	Q ^ 8x P (x) = 8x(Q ^ P (x)) .

sWOJSTWA 1 { 4 LEGKO DOKAZYWA@TSQ RAZBOROM SLU^AEW Q = 0 I

Q = 1 .

oPREDELENIE 1. gOWORQT, ^TO PREDIKAT PRIWEDEN K PREDWARENNOJ FORME, ESLI ON QWLQETSQ REZULXTATOM NAWE[IWANIQ KWANTOROW K NEKOTOROMU BESKWANTORNOMU PREDIKATU, NAZYWAEMOMU MATRICEJ. dLQ PRIWEDENIQ PREDIKATA K PREDWARENNOJ FORME DOSTATO^NO

PRODELATX SLEDU@]IE PREOBRAZOWANIQ.

1. iSKL@^ITX OPERACII ; ; ! PO FORMULAM:

b = ab _ ab , a b = ab _ ab , a ! b = a _ b .

2.pRIMENQQ ZAKONY DE mORGANA, DOBITXSQ ^TOBY OTRICANIQ BYLI LI[X OT \LEMENTARNYH PREDIKATOW.

3.wYNESTI WSE KWANTORY WLEWO PO SWOJSTWAM 1 | 4, PEREIMENOWYWAQ, ESLI NUVNO, SWQZANNYE PEREMENNYE.

iZ PREDWARENNOJ FORMY PREDIKATA A MOVNO POLU^ITX EGO SKOLEMOWSKU@ FORMU SA , ISKL@^IW IZ A WSE KWANTORY SU]ESTWOWANIQ I, PREOBRAZOWAW MATRICU PREDIKATA SLEDU@]IM OBRAZOM.

pUSTX, NAPRIMER, A = 9u 8v 9w 8x 8y 9z M(u; v; w; x; y; z) , TOGDA EGO SKOLEMOWSKAQ FORMA SA = 8v 8x 8y M(c; v; f1(v); x; y; f2(v; x; y)) ,

GDE PEREMENNYE u; w; z , PO KOTORYM W A NAWE[ENY KWANTORY SU-

]ESTWOWANIQ ZAMENENY: u | NA KONSTANTU c , w | NA FUNKCI@

31

f1(v) OT PEREMENNOJ v , PO KOTOROJ NAWE[EN KWANTOR 8v , NAHODQ- ]IJSQ LEWEE, ^EM w ; z | NA FUNKCI@ f2(v; x; y) OT PEREMENNYH v; x; y , PO KOTORYM NAWE[ENY KWANTORY 8v , 8x , 8y , NAHODQ]IESQ LEWEE, ^EM z . pRI \TOM, OKAZYWAETSQ, ^TO SU]ESTWUeT KONSTANTA c I FUNKCII f1 , f2 TAKIE, ^TO A = 1 , SA = 1 .

pRIMER 1. pRIWESTI K PREDWARENNOJ I SKOLEMOWSKOJ FORME PRE-

DIKAT A = 8x(P (x; z) ^ 8y 9x(Q(y; z) ! 8z R(t; x; z))) .

rE[ENIE. pOSLE ISKL@^ENIQ ! I PEREIMENOWANIQ NEKOTORYH SWQZANNYH PEREMENNYH, PREDIKAT A PREOBRAZUETSQ TAK:

A = 8x(P(x; z) ^ 8y 9x1(Q(y; z) _ 8z1 R(t; x1; z1))) .

wYNOSQ KWANTORY WLEWO, POLU^AEM PREDWARENNU@ FORMU:

A = 8x 8y 9x1 8z1(P (x; z) ^ (Q(y; z) _ R(t; x1; z1))) .

iSKL@^AQ 9x1 , POLU^AEM SKOLEMOWSKU@ FORMU PREDIKATA A :

A = 8x 8y 8z1(P (x; z) ^ (Q(y; z) _ R(t; f(x; y); z1))) .

zAMETIM, ^TO A IMEET SWOBODNYE PEREMENNYE t; z .

32

g l a w a 2 mnovestwa i otno{eniq

x1. pONQTIE MNOVESTWA. pODMNOVESTWO

pOD MNOVESTWOM A PONIMAETSQ SOWOKUPNOSTX OB_EKTOW PROIZWOLXNOJ PRIRODY, ONI NAZYWA@TSQ \LEMENTAMI MNOVESTWA A . s^I- TAETSQ, ^TO \LEMENTY MNOVESTWA POPARNO RAZLI^NY. eSLI x QWLQETSQ \LEMENTOM MNOVESTWA A , TO PI[UT: x 2 A , W PROTIWNOM SLU- ^AE PI[UT: x 2= A . mNOVESTWO, NE IME@]EE \LEMENTOW, NAZYWAETSQ PUSTYM I OBOZNA^AETSQ SIMWOLOM ? . dRUGAQ KRAJNOSTX: MNOVESTWO WSEH \LEMENTOW, RASSMATRIWAEMYH W DANNYJ MOMENT, NAZYWAETSQ UNIWERSUMOM I OBOZNA^AETSQ BUKWOJ U . mNOVESTWO MOVNO ZADAWATX LIBO PERE^ISLENIEM EGO \LEMENTOW, NAPRIMER, TAK: fa; b; cg , LIBO WYDELITX EGO IZ DRUGOGO MNOVESTWA S POMO]X@ NEKOTOROGO SWOJSTWA, NAPRIMER, fx 2 A j P(x)g OZNA^AET MNOVESTWO \LEMENTOW x 2 A , UDOWLETWORQ@]IH SWOJSTWU (PREDIKATU) P (x) .

oPREDELENIE 1. mNOVESTWA A I B RAWNY, ESLI ONI SOSTOQT IZ ODNIH I TEH VE \LEMENTOW, OBOZNA^AETSQ A = B .

sWOJSTWO 1. pUSTOE MNOVESTWO EDINSTWENNO.

dOKAZATELXSTWO. pUSTX ?1 I ?2 { PUSTYE MNOVESTWA, TOGDA UTWERVDENIQ x 2 ?1 I x 2 ?2 RAWNOSILXNY, T.K. ONI OBA QWLQ@TSQ LOVNYMI. sLEDOWATELXNO, ?1 = ?2 PO OPREDELENI@ 1.

dLQ OBOZNA^ENIQ STANDARTNYH ^ISLOWYH MNOVESTW BUDEM PRIMENQTX SLEDU@]IE OBOZNA^ENIQ:

N = f1; 2; 3; : : : ; n; : : : g | MNOVESTWO NATURALXNYH ^ISEL, Z = f0; 1; 2; : : : ; n; : : : g | MNOVESTWO CELYH ^ISEL,

Q = fmn j m 2 Z; n 2 Ng | MNOVESTWO RACIONALXNYH ^ISEL, R = (;1; +1) | MNOVESTWO DEJSTWITELXNYH ^ISEL,

C = fa + bi j a 2 R; b 2 Rg | MNOVESTWO KOMPLEKSNYH ^ISEL. 33

A = fx j 9 (x 2 A )g:

2I

oPREDELENIE 2. mNOVESTWO A QWLQETSQ PODMNOVESTWOM MNOVESTWA B , OBOZNA^AETSQ A B ILI A B , ESLI WSE \LEMENTY A PRINADLEVAT TAKVE I MNOVESTWU B , T.E. x 2 A ! x 2 B .

sWOJSTWO 2. ? A , A A .

sWOJSTWO 3. eSLI A B I B A , TO A = B . sWOJSTWO 4. eSLI A B I B C , TO A C .

pRIWEDEM DOKAZATELXSTWO SWOJSTWA 4. pOSKOLXKU A B , TO IZ x 2 A SLEDUET, ^TO x 2 B . t.K. B C , TO IZ x 2 B SLEDUET, ^TO x 2 C . tAKIM OBRAZOM, IZ x 2 A WYTEKAET, ^TO x 2 C , A \TO OZNA^AET, ^TO A C .

dLQ KAVDOGO MNOVESTWA A SU]ESTWUET MNOVESTWO WSEH EGO PODMNOVESTW, OBOZNA^AEMOE P (A) ; TAKIM OBRAZOM P (A) = fx j x Ag

I x 2 P (A) , x A .

pRIMER 1. P (?) = f?g , P (fxg) = f?; fxgg .

x2. oPERACII OB_EDINENIQ I PERESE^ENIQ MNOVESTW

oPREDELENIE 1. oB_EDINENIEM MNOVESTW A I B NAZYWAETSQ

MNOVESTWO A [ B ,			SOSTOQ]EE IZ \LEMENTOW, PRINADLEVA]IH HOTQ
BY ODNOMU IZ \TIH MNOVESTW, T.E. A [ B = fx j x 2 A _ x 2 Bg , SM.
RIS. 13.		[	[			##
sWOJSTWO 1. A			? = A , A	A = A .	A	B
sWOJSTWO 2.	A [ B = B [ A .					""!!
sWOJSTWO 3.	A	[	(B [ C) = (A [ B) [ C .
sWOJSTWO 4.	A	[ B = A , B		A .
dOKAZATELXSTWO SWOJSTW 1 { 4 NEPOSREDSTWENNO						rIS. 13

SLEDUET IZ OPREDELENIQ OPERACII OB_EDINENIQ MNOVESTW. oB_EDINENIEM MNOVESTW A , GDE 2 I , NAZYWAETSQ MNOVESTWO

[2I

oPREDELENIE 2. pERESE^ENIEM MNOVESTW A I B NAZYWAETSQ MNOVESTWO A\B , SOSTOQ]EE IZ \LEMENTOW, PRINADLEVA]IH KAVDOMU IZ DANNYH MNOVESTW A I B , T.E. A \ B = fx j x 2 A ^ x 2 Bg , SM. RIS. 14.

34

A \ ? = ? , A \ A = A .

A

B

sWOJSTWO 5.

##

sWOJSTWO 6.

A \ B = B \ A .

sWOJSTWO 7.

A \ (B \ C) = (A \ B) \ C .

sWOJSTWO 8.

A \ B = A

, A

B .

pERESE^ENIEM MNOVESTW

A

,

GDE

2 I ,

rIS

NAZYWAETSQ MNOVESTWO

""!!. 14

A =

x

(x

A ) .

f

I

2

g

I

j 8

2

2

) SWOJSTWA SWQZYWA@T OPERACII

sLEDU@]IE (DISTRIBUTIWNYET

PERESE^ENIQ I OB_EDINENIQ:

sWOJSTWO 9.

A [ (B \ C) = (A [ B) \ (A [ C) ,

sWOJSTWO 10.

A \ (B [ C) = (A \ B)

[ (A \ C) .

pRIWEDEM DOKAZATELXSTWO SWOJSTWA 10 PO OPREDELENI@ RAWENSTWA

MNOVESTW. rAWNOSILXNOSTX PREDIKATOW x

2 LP I x 2 RP DOKAZY-

WAEM, ISPOLXZUQ OPREDELENIQ PERESE^ENIQ I OB_EDINENIQ MNOVESTW:

x 2 LP = x 2

A ^ x 2 (B [ C) = x

2

A

^ (x

2

B _ x

2

C) =

= (x 2 A ^ x 2

B) _ (x 2

A ^ x

2

C) = x 2 A \ B _ x 2

A

\ C =

= x 2 (A \ B) [

(A \ C) = x 2 RP .

~TO I TREBOWALOSX DOKAZATX.

x3. oPERACII RAZNOSTI I SIMMETRI^ESKOJ RAZNOSTI MNOVESTW

oPREDELENIE 1.

rAZNOSTX@

A n

B MNOVESTW

A I B NAZY-

WAETSQ MNOVESTWO TEH \LEMENTOW IZ

A ,

KOTORYE NE PRINADLEVAT

MNOVESTWU B ,

T.E. A

n

B =

f

x

j

x

2

A

^

x = B

gA

(SM. RIS. 15).

2

B

##

sWOJSTWO 1.

A n ? = A , A n A = ? .

sWOJSTWO 2.

A n B = A n (A \ B) .

sWOJSTWO 3.

A n B = ? , A

B .

sWOJSTWO

?

rIS

4.

A n B = A , A

\ B = .

""!!. 15

oPREDELENIE

2. dOPOLNENIEM MNOVESTWA A NAZYWAETSQ MNO-

VESTWO A , RAWNOE

U n A , GDE U | UNIWERSUM (SM. RIS. 16).

sWOJSTWO 5.

A

[ B = A \ B .

A

sWOJSTWO 6.

A

\ B = A [ B .

A#

sWOJSTWA 5 I 6 NAZYWA@TSQ ZAKONAMI

DE mORGANA I LEGKO DOKAZYWA@TSQ METODOM

"!

KRUGOW |JLERA, SM. NIVE.

rIS. 16

35

oPREDELENIE 3. sIMMETRI^ESKOJ RAZNOSTX@ MNOVESTW A I B

NAZYWAETSQ MNOVESTWO A4B ,

RAWNOE

A

B

(A n B)

[ (B n A) (SM. RIS. 17).

##

sWOJSTWO

7.

A4B = (A

[ B) n (A \ B) .

sWOJSTWO 8.

A4B = B4A .

sWOJSTWO 9. A4? = A ,

A4A = ? .

sWOJSTWO

10. A4(B4C) = (A4B)4C .

rIS

""!!. 17

pRIWEDEM DOKAZATELXSTWO SWOJSTWA

10. rAWNOSILXNOSTX PREDI-

KATOW x 2

LP

I x 2

RP

DOKAVEM , ISPOLXZUQ METOD ISTINNOST-

NYH TABLIC, SDELAW RAZBOR PO WSEWOZMOVNYM ZNA^ENIQM PREDIKATOW

x 2 A , x 2 B ,

x 2 C . uDOBNO, ODNAKO, WMESTO ISTINNOSTNOJ TAB-

LICY ISPOLXZOWATX METOD KRUGOW |JLERA

(SM. RIS. 18), IZOBRAZIW DANNYE MNOVESTWA

A

B

KRUGAMI TAK, ^TOBY ONI RAZBIWALI PLOS-

M6

M4

##

KOSTX NA 8

^ASTEJ, OTWE^A@]IH STRO^KAM

M2

M7

ISTINNOSTNOJ TABLICY. nAPRIMER, ^ASTX

M5

M3

#

M6 =

f

x

j

x

2

A

^

x

2

B

^

x = C

g

SO-

M1

2

C

M0

OTWETSTWUET STROKE (110) .

wYRAZIM ^EREZ

""!!

M0 | M7

MNOVESTWA LP = A (B

4

C) I

rIS. 18

4

"!

RP = (A4B)4C . LP = (M4; M5 ; M6 ; M7)4(M1; M2; M5 ; M6) =

= (M1 ; M2; M4; M7) , RP = (M2; M3; M4; M5)4(M1; M3; M5; M7) =

= (M1; M2; M4 ; M7) , ZDESX ZAPQTYE MEVDU MNOVESTWAMI OZNA^A@T OB_EDINENIE. iTAK, OBA MNOVESTWA SOSTOQT IZ ODNIH I TEH ^ASTEJ M1; M2; M4 I M7 , ^TO I DOKAZYWAET IH RAWENSTWO.

x4. dEKARTOWO PROIZWEDENIE MNOVESTW, BINARNYE OTNO[ENIQ

oPREDELENIE 1. dEKARTOWYM (PRQMYM) PROIZWEDENIEM MNOVESTW A1; A2; : : : ; An NAZYWAETSQ MNOVESTWO WSEH UPORQDO^ENNYH

NABOROW (x1; x2; : : : ; xn)		TAKIH, ^TO xi	2	Ai		PRI i = 1;2; : : : n , OBO-
										n
ZNA^AETSQ DEKARTOWO PROIZWEDENIE TAK: A1						A2		: : : An ILI			Ai .
										i=1
w ^ASTNOSTI	, A B	= f(x; y) j x	2 A; y 2					Bg ;	ZAMETIM		^TO
										Q,
z 2 A B = 9x 2 A 9y 2 B (z = (x; y)) .
		36

pRIMER 1. eSLI DANY MNOVESTWA A = f1; 2g I B = f1; 2; 3g , TO

A B = f(1; 1); (1; 2); (1; 3); (2; 1); (2; 2); (2; 3)g .

oPREDELENIE 2. bINARNYM OTNO[ENIEM MEVDU MNOVESTWAMI A I B NAZYWAETSQ PODMNOVESTWO R A B . w ^ASTNOM SLU^AE, PRI A = B , GOWORQT O BINARNOM OTNO[ENII R NA MNOVESTWE A .

oPREDELENIE 3. oBLASTX@ OPREDELENIQ OTNO[ENIQ R

A B

NAZYWAETSQ MNOVESTWO D(R) = fx

2

A j 9y 2 B ((x; y)

2

R)g ,

QWLQ@]EESQ PROEKCIEJ R NA A . oBLASTX@ ZNA^ENIJ R NAZYWAETSQ

MNOVESTWO

V (R) = fy 2 B j 9x 2 A ((x; y) 2 R)g | PROEKCIQ R

NA B .

oPREDELENIE 4. pUSTX

1R A B . oBRATNYM K R NAZYWAET-

SQ BINARNOE OTNO[ENIE

R; = f(y; x)

j

(x; y)

2

Rg ,

ZAMETIM

,

^TO

R;

1

B

A

.

dOPOLNENIEM BINARNOGO OTNO[ENIQ

R

NAZYWAETSQ

OTNO[ENIE

R = (A

B1 ) n R .

1

) = D(R) .

sWOJSTWO 1.

D(R; ) = V (R) , V (R;

dOKAVEM, ^TO D(R;1) = V (R) . |TI MNOVESTWA RAWNY, POSKOLX-

KU

1

1

y 2

D(R; )

() 9x ((y; x) 2

R; )

() 9x ((x; y) 2

R)

()

() y

2 V (R) . wTOROE RAWENSTWO DOKAZYWAETSQ ANALOGI^NO.

oPREDELENIE 5. kOMPOZICIQ R1 A B I R2 B C { \TO

OTNO[ENIE

R1

R2

= f(x; z)

j 9y

2 B ((x; y) 2 R1 ^ (y; z) 2 R2)g ,

PRI \TOM R1

R2 A C .

sWOJSTWO

2. R1

(R2 R3) = (R1 R2) R3 .

dOKAZATELXSTWO

.

zAMETIM

,

^TO

(x; y)

2 R1 (R2 R3) ()

() 9p ((x; p) 2 R1

^ (p; y)

2 R2 R3) ()

() 9p

9q ((x; p)

2 R1

^

(p; q)

2 R2

^ (q; y)

2 R3) .

aNALOGI^NO

,

UBEVDAEMSQ

,

^TO

(x; y) 2

(R1 R2) R3 ()

() 9p

9q ((x; p)

2 R1 ^

(p;

1q)

2 R21

^

(q; y1)

2 R3) .

sWOJSTWO 3. (R1

R2);

=

R;

R; .

dOKAZATELXSTWO

2

1

1

.

zAMETIM

,

^TO

(x; y)

2 (R1

R2); ()

(y; x)

()

R1

R2

() 9

p ((y; p)

R1

^

(p; x)

2

R2)

() 1

p

2

1

1 2

(x; y)

R;

1

.

() 9

((p; y)

2

R;

^

(x; p)

2

R; )

()

2

R;

1

2

2

1

x5. oTNO[ENIQ \KWIWALENTNOSTI I PORQDKA oPREDELENIE 1. bINARNOE OTNO[ENIE R NA A NAZYWAETSQ

37

A) REFLEKSIWNYM, ESLI 8a 2 A ((a; a) 2 R) ,

B) SIMMETRI^NYM, ESLI IZ (x; y) 2 R SLEDUET, ^TO (y; x) 2 R , W) TRANZITIWNYM, ESLI (x; y) 2 R , (y; z) 2 R =) (x; z) 2 R , G) ANTISIMMETRI^NYM, ESLI (x; y) 2 R , (y; x) 2 R =) x = y .

eSLI BINARNOE OTNO[ENIE R NA A QWLQETSQ REFLEKSIWNYM, SIMMETRI^NYM I TRANZITIWNYM, TO EGO NAZYWA@T OTNO[ENIEM \K- WIWALENTNOSTI NA A I PI[UT x y WMESTO (x; y) 2 R . uSLOWIQ REFLEKSIWNOSTI, SIMMETRI^NOSTI I TRANZITIWNOSTI MOVNO PEREPISATX TAK:

A) 8a 2 A (a a) ,

B) x y =) y x ,

W) x y , y z =) x z .

eSLI DANO OTNO[ENIE \KWIWALENTNOSTI NA MNOVESTWE A , TO KLASSOM \KWIWALENTNOSTI, POROVDAEMYM \LEMENTOM x 2 A NAZYWAETSQ MNOVESTWO Kx = fy 2 A j y xg .

tEOREMA O RAZBIENII MNOVESTWA NA KLASSY \KWIWALENT-

NOSTI. kAVDOE OTNO[ENIE \KWIWALENTNOSTI NA A POROVDAET RAZBIENIE A NA NEPERESEKA@]IESQ KLASSY \KWIWALENTNOSTI.

dOKAZATELXSTWO. pUSTX Kx I Kz { KLASSY \KWIWALENTNOSTI.

rAZBEREM DWA WOZMOVNYH SLU^AQ.
1.	pUSTX	x z .	w \TOM SLU^AE	y 2 Kx	() y x ;			POSKOLXKU
x z , TO y x () y z () y 2 Kz , T.E.					y	2 Kx () y 2 Kz I,
ZNA^IT, Kx = Kz .
2. pUSTX		x 6 z . w \TOM SLU^AE Kx \ Kz				= ? ,	T.K. ESLI BY
SU]ESTWOWAL \LEMENT y TAKOJ, ^TO y 2 Kx					I y 2 Kz , TO BYLO BY
y x I y z =) x			z , ^TO PROTIWORE^IT USLOWI@.
tEOREMA DOKAZANA.
pRIMER 1. nA MNOVESTWE CELYH ^ISEL Z RASSMOTRIM BINARNOE
OTNO[ENIE R = f(x; y) j (x;y) . 3g . dOKAZATX, ^TO R | OTNO[ENIE
\KWIWALENTNOSTI, NAJTI WSE KLASSY \KWIWALENTNOSTI.							; x = 0 . 3 ,
rE[ENIE.		(x; x)	2 R PRI L@BOM x 2 Z ,			T.K. x
PO\TOMU R | REFLEKSIWNO. eSLI (x; y) 2					R , TO (x		; y) . 3 , T.E.
x;y = 3k , GDE k 2 Z . oTS@DA SLEDUET, ^TO y ;x = ;3k								I, ZNA^IT,
(y; x) 2 R , PO\TOMU R | SIMMETRI^NO. nAKONEC, PUSTX (x; y) 2 R

I (y; z) 2 R , TOGDA x ; y = 3k I y ; z = 3l . oTS@DA SLEDUET, ^TO

38

{ ^ASTI^NO UPORQDO^ENNOE MNOVES-

K0; K1 ; K2

x ; z = 3(k + l) I, ZNA^IT, (x; z) 2 R , PO\TOMU R | TRANZITIWNO. mY DOKAZALI, ^TO R | OTNO[ENIE \KWIWALENTNOSTI.

nAJDEM KLASSY \KWIWALENTNOSTI. Kx = fy j y xg , T.E. y 2 Kx

OZNA^AET, ^TO (y;x). 3 () y = 3k+ x , GDE k 2 Z . oTS@DA SLEDUET, ^TO Kx = f3k + xj k 2 Zg . oSTALOSX ZAMETITX, ^TO

RAZBIWA@T Z NA NEPERESEKA@]IESQ KLASSY \KWIWALENTNOSTI. oPREDELENIE 2. bINARNOE OTNO[ENIE R NA MNOVESTWE M NA-

ZYWAETSQ ^ASTI^NYM PORQDKOM, ESLI ONO REFLEKSIWNO, ANTISIMMETRI^NO I TRANZITIWNO, PI[UT x 6 y WMESTO (x; y) 2 R . tAKIM OBRAZOM, OTNO[ENIE 6 UDOWLETWORQET USLOWIQM

1) 8x 2 M (x 6 x) | REFLEKSIWNOSTX,

2) (x 6 y ^ y 6 x) =) (x = y) | ANTISIMMETRI^NOSTX, 3) (x 6 y ^ y 6 z) =) (x 6 z) | TRANZITIWNOSTX.

pREDIKAT x < y OPREDELQETSQ KAK x 6 y ^ x =6 y .

mNOVESTWO, NA KOTOROM ZADAN ^ASTI^NYJ PORQDOK, NAZYWAETSQ ^ASTI^NO UPORQDO^ENNYM ILI UPORQDO^ENNYM.

pRIMER 2. mNOVESTWO P (M) ^ASTI^NO UPORQDO^ENO OTNO[ENIEM PODMNOVESTWA.

w ^ASTI^NO UPORQDO^ENNOM MNOVESTWE MOGUT BYTX NESRAWNIMYE \LEMENTY, TAK W PRIMERE 2, ESLI M = f1; 2; 3; 4g , TO PODMNOVESTWA f1; 2; 3g I f2; 3; 4g NESRAWNIMY.

oPREDELENIE 3. ~ASTI^NO UPORQDO^ENNOE MNOVESTWO M NAZYWAETSQ LINEJNO UPORQDO^ENNYM, ESLI W NEM NET NESRAWNIMYH \LEMENTOW, T.E. DLQ L@BYH x; y 2 M WYPOLNQETSQ ODNO IZ USLOWIJ:

x < y , x = y ILI y < x .

pRIMER 3. mNOVESTWA N;Z; Q; R S ESTESTWENNYM PORQDKOM NA NIH QWLQ@TSQ LINEJNO UPORQDO^ENNYMI.

oPREDELENIE 4. pUSTX M

TWO, A { PODMNOVESTWO M .

1. |LEMENT a 2 A NAZYWAETSQ MAKSIMALXNYM W PODMNOVESTWE A , ESLI 8x 2 A (x 6 a ILI x NESRAWNIM S \LEMENTOM a ).

2. |LEMENT a 2 A NAZYWAETSQ NAIBOLX[IM W PODMNOVESTWE A , ESLI 8x 2 A (x 6 a) .

3. |LEMENT a 2 M NAZYWAETSQ WERHNEJ GRANX@ DLQ PODMNOVESTWA A , ESLI 8x 2 A(x 6 a) .

39

aNALOGI^NO DAETSQ OPREDELENIE MINIMALXNOGO \LEMENTA, NAIMENX[EGO \LEMENTA I NIVNEJ GRANI PODMNOVESTWA A ^ASTI^NO UPORQDO^ENNOGO MNOVESTWA M .

iZ DANNOGO OPREDELENIQ WYTEKA@T SLEDU@]IE SWOJSTWA. sWOJSTWO 1. eSLI PODMNOVESTWO A IMEET NESKOLXKO MAKSIMALX-

NYH \LEMENTOW, TO ONI NESRAWNIMY MEVDU SOBOJ.

sWOJSTWO 2. eSLI W PODMNOVESTWE A IMEETSQ NAIBOLX[IJ \LEMENT, TO ON QWLQETSQ I EDINSTWENNYM MAKSIMALXNYM \LEMENTOM \TOGO PODMNOVESTWA.

sWOJSTWO 3. |LEMENT a 2 A { NAIBOLX[IJ W PODMNOVESTWE A TOGDA I TOLXKO TOGDA, KOGDA ON QWLQETSQ ODNIM IZ WERHNIH GRANEJ \TOGO PODMNOVESTWA.

x6. fUNKCII

oPREDELENIE 1. fUNKCIEJ f , OTOBRAVA@]EJ MNOVESTWO X WO

MNOVESTWO Y , OBOZNA^AETSQ f : X ! Y , NAZYWAETSQ PRAWILO, PO
KOTOROMU KAVDOMU x				2 X STAWITSQ W SOOTWETSTWIE \LEMENT y 2 Y ,
KOTORYJ S^ITAETSQ ZNA^ENIEM FUNKCII f									I OBOZNA^AETSQ f(x) .
mNOVESTWO		X NAZYWAETSQ OBLASTX@ OPREDELENIQ, A MNOVESTWO
V (f) = ff(x) j x 2			Xg	QWLQETSQ OBLASTX@ ZNA^ENIJ FUNKCII f .
mNOVESTWO		;f	=	f(x; y) j x 2 X; y =					f(x)g	NAZYWAETSQ GRA-
FIKOM FUNKCII f :				X	!	Y	. zAMETIM, ^TO ;f			QWLQETSQ BINAR-
NYM OTNO[ENIEM MEVDU					X	I Y , DLQ KOTOROGO WYPOLNENO USLOWIE
		;						tAKIE BINARNYE OTNO[ENIQ NAZYWA
8x 2 X 9! y	2 Y (x; y) 2				;f .						-
@T FUNKCIONALXNYMI I ^ASTO OTOVDESTWLQ@T PONQTIQ FUNKCII I
FUNKCIONALXNOGO OTNO[ENIQ.
oPREDELENIE 2. fUNKCIQ f : X ! Y									NAZYWAETSQ
A) S@R_EKTIWNOJ, ESLI 8y 2 Y								9x 2 X (y = f(x)) ,
B) IN_EKTIWNOJ, ESLI				8x1; x2			2 X (x1 6= x2		! f(x1) 6= f(x2)) ,
W) BIEKTIWNOJ, ESLI ONA S@R_EKTIWNA I IN_EKTIWNA, ^TO MOVNO ZA-
PISATX TAK:	8y	2 Y 9! x 2 X (y = f(x)) .
pRIMER	1. fUNKCIQ				E :			X ! X , WY^ISLQEMAQ PO PRAWILU

E(x) = x DLQ L@BOGO x 2 X , NAZYWAETSQ TOVDESTWENNOJ. o^E- WIDNO, E | BIEKCIQ.

40