Дискретная математика. Кулабухов С.Ю. - 32 стр.

   x   5.   oTNO ENIE PORQDKA
       oTNOENIE PORQDKA ~ASTI^NO UPORQDO^ENNYE MNOVESTWA mINIMALXNYE MAKSIMALXNYE I
                        .                                        .           (            )

       NAIMENXIE NAIBOLXIE \LEMENTY UPORQDO^ENNOGO MNOVESTWA pOKRYWA@]IE \LEMENTY
                  (           )                                          .                    .

       lINEJNO I WPOLNE UPORQDO^ENNYE MNOVESTWA rEETKI
                                                .        .




  5.1. oSNOWNOE OPREDELENIE.
oPREDELENIE 1. pUSTX % BINARNOE OTNOENIE NA A
                            |                                .


  1.  % NAZYWAETSQ ANTISIMMETRI^NYM, ESLI IZ TOGO, ^TO (a
 b) 2 % I (b
 a) 2 % SLEDUET a = b.
  2. % NAZYWAETSQ OTNOENIEM PORQDKA, ESLI % REFLEKSIWNO, ANTISIMMETRI^NO I TRANZITIW-
      NO.
  3. mNOVESTWO A S ZAFIKSIROWANNYM NA NEM OTNOENIEM PORQDKA % NAZYWAETSQ UPORQDO^EN-
      NYM: hA
 %i.
pRIMER 1. pUSTX A = f1
 2
 3g.
   1. %1 = EA = f(1
 1)
 (2
 2)
 (3
3)g | OTNOENIE PORQDKA
   2. %2 = EA f(1
 2)
 (1
 3)g | OTNOENIE PORQDKA (OTNOENIE DELIMOSTI ... )
   3. %3 = f(1
 1)
 (1
 2)
 (1
3)g NE QWLQETSQ OTNOENIEM PORQDKA
   4. %4 = EA f(1
 2)
 (2
 1)
 (3
 3)g NE QWLQETSQ OTNOENIEM PORQDKA
   5. %5 = EA f(1
 2)
 (2
 3)g NE QWLQETSQ OTNOENIEM PORQDKA
   6. %6 = EA f(1
 2)
 (2
 3)
 (1
 3)g | OTNOENIE PORQDKA (OTNOENIE SRAWNENIQ PO WELI^INE |
      ).
    oTNOENIQ PORQDKA BUDEM OBOZNA^ATX SIMWOLAMI ,  I T. D. wMESTO (a
 b) 2 BUDEM PISATX
a  b.
  5.2. uPORQDO^ENNYE MNOVESTWA.
oPREDELENIE 1. pUSTX hA
 i UPORQDO^ENNOE MNOVESTWO
                                  |                                  .


  1.eSLI (a
 b) 2, TO \TOT FAKT BUDEM ZAPISYWATX W WIDE:
                                                a  b
 b  a

    I GOWORITX \a MENXE LIBO RAWNO b", \b BOLXE LIBO RAWNO a" (W SMYSLE OTNOENIQ PO-
    RQDKA ). eSLI a  b ILI a  b I a 6= b, TO BUDEM PISATX a < b ILI b > a I GOWORITX \a
    MENXE b", \b BOLXE a".
 2. |LEMENT a 2 A NAZYWAETSQ MINIMALXNYM (MAKSIMALXNYM), ESLI W A NET \LEMENTOW,
    MENXIH (BOLXIH) \LEMENTA a.
 3. |LEMENT a 2 A NAZYWAETSQ NAIMENXIM (NAIBOLXIM) \LEMENTOM MNOVESTWA A, ESLI
    \TOT \LEMENT MENXE (BOLXE) L@BOGO DRUGOGO \LEMENTA IZ A.
pRIMER 1. pUSTX A = f1
 2
 3g.
 1. 2A = f?
 f1g
 f2g
 f3g
 f1
2g
 f1
 3g
 f2
 3g
 Ag, h2A 
 i | UPORQDO^ENNOE MNOVESTWO, NAIMENX-
    IJ \LEMENT (ON VE MINIMALXNYJ) | ?, NAIBOLXIJ (ON VE MAKSIMALXNYJ) | SAMO MNO-
    VESTWO A = f1
 2
 3g.
 2. 2A0 = 2A nf?g, h2A0 
 i | UPORQDO^ENNOE MNOVESTWO, NAIMENXEGO \LEMENTA NET, MINIMALX-
    NYE | f1g, f2g, f3g, NAIBOLXIJ (ON VE MAKSIMALXNYJ) | A = f1
 2
 3g.
                                                32