HULGAD, hulgaaritmeetilised tehted ja hulgaalgebra (0)

HULGAD
Hulgaaritmeetilised tehted
I
Hulgaalgebra
 A
B
. . . .  Hulk  on  koosvaadeldavate  hulgaelementide  kogum  . . . .
( hulk koosneb  elementidest )
Hulkade jaoks on defineeritud  5  hulgaaritmeetilist tehet :
tehte  NIMI
formaalne  tähistus
 A  B
hulkade
ühend
__
 hulga   täiend
A
I
hulkade  ühend
     TTÜ 
( hulkade    liitmine  )
A     B
 A
B
hulkade   ühisosa
( hulkade   korrutamine )
A     B
hulkade  vahe
 A  B
A  \  B
( hulkade   lahutamine )        "A ilma B-ta"
hulkade
ühisosa
hulkade   sümmeetriline vahe
A    B
I
Arvutitehnika 
Hulgatehete tulemuseks olev hulk  viirutatuna   Venni diagrammidel :
 A
B
A
 A \ B
A
hulkade
vahe
" A  ilma  B-ta "
A
 B
hulga  A
täiend A
 \ B  
 \ A    ehk  hulkade lahutamine pole  kommutatiivne   
   Instituut
(oleneb operandide järjekorrast)
( täiend  on alati  universaalhulgani )
ainus  mittekommutatiivne  ( binaarne ) hulgatehe.
I
I
 A
B
A
 A  B
ühe hulga Venni  diagramm
hulkade
sümmeetriline vahe
__
    __
__
__
      __
Hulgaalgebra  sisaldab  3  tehet :    
            
   A   =   A
 I    =   
          =   I
     TTÜ 
teineteisele VASTAVAD   tehted,  loogikaväärtused   ja  hulgad :
A        =   A
A         =   A
loogikas
hulkades
A         =   I
A        =   
                                       __
                       __
  inversioon                 A
täiend          A
   __
   __
A
konjunktsioon
    A     =    
A    A     =    I
            
ühisosa            
idempotentsus:
disjunktsioon              
ühend              
A     A      =   A
A     A     =   A
Arvutitehnika 
. . . ei oma loogikas vastavat tehet . . .
lahutamine  e.  vahe       \  
summa mooduliga 2           
kommutatiivsus:
sümmeetriline vahe          
välistav VÕI    ( XOR )             
A     B      =    B     A
      A     B      =   B   
 
 A
konstant    0
tühi  hulk                   {  }
assotsiatiivsus:
konstant    1
universaalhulk                  
( A   B )     C      =     A     ( B   C )
( A   B )     C      =     A     ( B   C )
HULGAALGEBRA   PÕHISEOSED
   Instituut
distributiivsus:      (  sulgude  "lahtikorrutamine"  ja  "lahtiliitmine" )
loogikaalgebra põhiseosed  muutuvad  hulgaalgebra põhiseosteks, kui
nendes teha eelnevalt näidatud asendused.
A    ( B     C )      =     ( A    B )       ( A    C )
Ka hulgaavaldiste korral kehtib  duaalsusprintsiip.
I
I
A
B
A
B
DeMorgani seadused
(kahe hulga jaoks):  
______
 __     __
______        __      __
A   B    =    A     B
A   B    =    A     B
I
I
C
C
A    B   C 
A  B    A  C 
A
A
B
B
I
I
A
B
A
B
A B 

     TTÜ 
kleepimine:
                   __
                 __
C
C
A  = ( A B )    ( A B )
A  =( A B )    ( A B )
A    B   C 
A  B    A  C 
mõlemad hulgaavaldised määravad diagrammil  sama piirkonna
Hulgaaritmeetilised  asendusseosed
A    ( B     C )      =     ( A    B )       ( A    C )
Asendusseosed  võimaldavad asendada hulgatehteid     \  ja       
hulgaalgebrasse kuuluvate tehete          
¯             kaudu:
neeldumine :
Arvutitehnika 
     
    __
A    ( A
            A
    B )      =    A 
 A    ( A    B )     =    A
  \B   =   A    B
I
I
I
I
A
A
B
B
A
A
B
B
   Instituut
      __
A    ( A   B )      =    A     B
järeldub tehte      definitsioonist :      A    B    =    ( A  \B )  ( B  \A )
      __
A    ( A   B )      =    A     B
B
I
I
  \A   =   { f  g  h }
A
A
B
B
B   A    =    B  \A
B
I
f
g
a
e
b
h
c
d
                                       A    B    =    ( A  B )  \( A  B )
A
I
I
vaadeldud  hulkade
Venni  diagramm
     TTÜ 
|______________________________________________________________________________|
A
A
B
B
/¯¯  ülesanne :   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
Leida  hulgad   A  ja  B   kui :
   __
A \B   =  
B  \A   =  
Hulgatehete   prioriteet :
       

  
  \ 

/¯¯  ülesanne :   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
A  
B   =  
Arvutitehnika 
On antud hulgad :
A   =  { a  b  c  d  e }  
B   =  { a  b  c  d  e  f  g  h }
I
Leida
A 

  
B A  
B         A  \B
      B  \A         B   A
A
B
A 
  
B   =   { a  b  c  d  e  f  g  h }   =   B
   Instituut
A 
  
B   =   { a  b  c  d  e  }   =   A
A  \B   =   {   }
B    A
I
1
3

2
A   
B   =   A
A
5
6
B
B
I
7
9
10
8
A   =  { 1  3  5  6  7  8  9 }  
B   =  { 2  3  6  9  10 }
A
|______________________________________________________________________________|
/¯¯  ülesanne :   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
A    B
     TTÜ 
A \  B   =   A
Mida saab ütelda  hulkade  A  ja  B  kohta  järgneval viiel juhul  
ehk millisel erijuhtumil / tingimusel  iga konkreetne võrdus kehtib :
I
( kuidas peavad  A  ja B  paiknema teineteise suhtes )
A 

   
 B   =   A
A   
 B   =   A
A


A
B
 \  B   =   A
A   
 B    =    B   
A
A \  B    =    B  \  A
A  
 
  B  =  
Arvutitehnika 
A 

   
 B    =    B   
A
"A  või  B  on  tühi hulk"   oleks triviaalne lahend ;   seda me ei pea vastuseks .
selline võrdus kehtib alati:    kommutatiivsus
Otsime selliseid erijuhtumeid, kus hulgad  A  ja  B  on mõlemad mittetühjad
võrduse kehtimine  ei anna mingit infot  hulkade  A  ja  B  kohta
ja  vaadeldav võrdus kehtib ikkagi
A \  B    =    B  \  A
A 
   
 B   =   A
A
I
I
A
   Instituut
B
B
A   =   B
|______________________________________________________________________________|
  __
Hulgaaritmeetiliste   avaldiste   TEISENDUSED
Hulgaavaldis teisendatakse  hulgaalgebra põhiseoste  ja  hulgatehete
=  A  ( C  A )    ( A  B  C )   =
asendusseoste  abil  lihtsamale / lühemale, kuid  esialgsega samaväärsele
kujule .  
=   A       C      ( A   B  C ) =
Teisenduse eesmärgiks  võib olla  hulgaavaldise viimine  
Cantori  normaalkujule.   ( DNK  ja  KNK  analoogid hulgaavaldiste jaoks )
=   A      C
|______________________________________________________________________________|
/¯¯  ülesanne :   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
/¯¯  ülesanne :   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
     TTÜ 
Lihtsusta  hulgaavaldis :
 __
Lihtsusta  hulgaavaldis :
[ ( A

__
  
  \B )   ( A   B )    ( A  \C ) ]  
A    = 
 __
( A  C )   ( B  C )   ( A   C )     ( A  B  C )  = 
 
             __
    __
= [ ( A
 
  \B )   ( A  \B )    ( B  \A )    ( A  \C ) ]   
  A  = 
= 
    __
 __
      __
      __
 A    ( B  C )     ( A  B  C )    =
= [ ( Arvutitehnika 
 A 



   
B )    ( B   
A )    ( A   
C ) ]  
A  = 
=    

 A      ( B     C )
__       __
       __        __
        __       __
|______________________________________________________________________________|
= (A 



   
B  A )    (B   
A  A )    ( A   
C    A ) =
/¯¯  ülesanne :   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
 __       __
=    B 
  
A   A  =
  __
Lihtsusta  hulgaavaldis :
=    B 
  ________________
   
A 
  ______ ______
 
______
|______________________________________________________________________________|
/¯¯  ülesanne :   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
( A \  B )   ( B  \  C )  ( C  \  A )  =  
   Instituut
Lihtsusta  hulgaavaldis :
 A 
 
    
 ( C  \A )    ( A   
B  
C )   = 
      ______          ______
/¯¯  iseseisvaks  lahendamiseks :   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
      ______         ______       ______
=  ( A \  B )   ( B  \  C )  ( C  \  A )  =  
Teisenda eelneva võrduse vasaku poole avaldist    A

    ( A  
 B )  
     _______
 kasutades  teist võimalikku  asendusseost :
        __
=  ( A
    A    B    =    ( A  B )  \( A  B )
 \  B )   ( B  \  C )  ( C      A )  =  
 
 . . . . edukal teisendamisel peab tulema sama tulemus :
 __
     __
      __
 
=  ( A 
      __
   B )   ( B      C )   ( C    A )   =

  __
    __
    __
 . . . . .    =    A  
B    =    A  \B 
=  (
|______________________________________________________________________________|
 A    B )   ( B      C )    C        A    =
     TTÜ 
 __
/¯¯  ülesanne :   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
=     C      A
|______________________________________________________________________________|
/¯¯  ülesanne :   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
Tõesta  hulgaavaldiste võrduse  kehtivus :
(A



 \B )  
 ( C \D )   =   ( A  
C ) \( B  
D )
Tõesta  hulgaavaldiste võrduse  kehtivus :
 
A

    ( A  
 B )   =   A  \B
       __                       __
(A




Arvutitehnika 
 \B )  
(C \D )  =   (A   
B )   
 ( C  
 D )   = 
          __                    __
 =   A  


  
B    
   C  
 D    = 
 A



     ( A  
B )  =  [A  \( A    B )]    [( A    B )  \ A  ] = 
__     __
     ______
__
=   A  


  
 C    
  B   
 D   = 
 =  [A 

 
  
( A  
B )]    [ A  
B   
 A  ] = 
       _______
    __       __
=   A  
 
  
 C    
 B   
 D   =
 =  A  
 
   
  ( A    
  B )   =
 
  __
=    


 A  
 C   \ B  
 D      =
   Instituut
 =  

 A   
B    =
=   (


 A  
 C )   \ ( B  
 D ) 
 =    A  \B 
|______________________________________________________________________________|
|______________________________________________________________________________|