Jääkfunktsioon (0)

Jääkfunktsioon
Kui asendada  n- muutuja funktsiooni   f ( x1 x2 ..... xn )   avaldises  osad tema
 f = x¯2 ( x1· 0 · x¯3  w x¯1·1· x4 w x1·1 )   w   x2 ( x1· 1 · x¯3  w  x¯1·0· x4 w x1·0 ) =
muutujad  konstantidega   0   või   1 ,  siis selliselt saadavat lihtsamat
loogikafunktsiooni nimetatakse  algse  n- muutuja funktsiooni   
 =    x
¯2 ( x
¯1 x4   w  x1 )   w  x2 ( x1 x
¯3 )    =  
jääkfunktsiooniks.
 
  =     x
¯2 ( x4    w   x1 )    w   x2 ( x1 x
¯3 )
Kui asendada  n-muutuja funktsiooni   f ( x1 x2 ... xi ... xn )   avaldises üks
tema muutuja   xi   konstandiga   0  või  1 ,  siis  on  jääkfunktsiooniks  
. . . . arenduse avaldis  leitud
(n1)-muutuja funktsioon:
sellele  avaldisele  leidub  ka  lihtsam / kiirem  arenduse  leidmisvõimalus :
 f   =    x
  f
1 x2 x
¯3   w   x
¯1 x
¯2 x4   w   x1 x
¯2       =    .  .  .  . 
 ( x1 ... xi1 0  xi1 ... xn )      või       f ( x1 ... xi1 1  xi1 ... xn )
arenduse aluseks  olev muutuja    x 2    juhtub siin olema  ühine tegur  ja  teda
     TTÜ 
Jääkfunktsioon  ei sisalda enam seda muutujat, mis asendati konstandiga.
saab seega tuua   sulgude ette  —  misjuhul avaldis omandab kah   ( x2   järgi )
Jääkfunktsioon  leiab kasutamist  loogikaavaldiste mitmes erikujus.
disjunktiivse arenduse   üldkuju :
 .  .  .  .    =      x
¯2 ( x
¯1 x4  w  x1 )   w    x2 ( x1 x
¯3 )
 jääkfunktsiooni  kaudu esitatavad  loogikafunktsioonide / avaldiste   erikujud :
|______________________________________________________________________________|
Shannoni  arendused
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
loogikafunktsiooni   tuletis
SHANNONI   ARENDUSED
Teha  Shannoni  konjunktiivne arendus   sama muutuja    x 2    
Shannoni  arendus  on  ( jääkfunktsioone sisaldav)  loogikaavaldise üks erikuju .
järgi  samale avaldisele :
Lihtsaim arendusjuhtum on   disjunktiivne   arendus  1-he muutuja  järgi.
Arvutitehnika 
 f 
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
    =      x 1 x 2  x
¯ 3       w      x
¯ 1 x
¯ 2  x 4       w      x 1 x
¯ 2
f   =    [ x
Teha  Shannoni  disjunktiivne arendus   muutuja    x
2    wf (  x1 0 x3 x4  ) ] [ x
¯2    wf (  x1 1 x3 x4  ) ]
 2    järgi  
avaldisele :
         f   =    [ x2    wf ( x1 0 x3 x4 ) ] [ x
¯2    wf ( x1 1 x3 x4 ) ]  =
 f     =      x 1 x 2  x
¯ 3       w      x
¯ 1 x
¯ 2  x 4       w      x 1 x
¯ 2
 f = ( x2  w  x1· 0 · x¯3  w x¯1·1· x4 w x1·1 )( x¯2  w  x1· 1 · x¯3  w  x¯1·0· x4 w x1·0 ) =
   Instituut
f   =      x
¯2 ·f (  x1 0 x3 x4  )    w      x2 ·f (  x1 1 x3 x4  )
=  ( x2    w    x
¯1 x4   w  x1 ) ( x
¯2   w   x1 x
¯3 )  =   ( x2    w    x4   w  x1 )( x
¯2   w   x1 x
¯3 )
|______________________________________________________________________________|
  f   =      x
¯2 ·f ( x1 0 x3 x4 )    w      x2 ·f ( x1 1 x3 x4 )    =   
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
 f   =   [ x2    w    x3    w    f (   x  1  x4  ) ]·[ x2    w    x
¯3    w    f (  x   1  x4  ) ] · 
     ·[ x
¯2    w    x3    w    f (   x  1  x 4 ) ]·[ x
¯2    w    x
¯3    w    f (   x  1  x4  ) ]  =
2 muutuja  järgi  disjunktiivne arendus:
Teha  Shannoni  disjunktiivne arendus  muutujate    x
   =       [ x
 1    ja    x 4    järgi   
2    w    x3    w    f ( x1 0 0 x4 ) ]·[ x2    w    x
¯3    w    f ( x1 0 1 x4 ) ] · 
avaldisele     [


   x 1  
   ( x 2   
  x 3 )] x
¯ 4 
   ·[ x
¯2    w    x3    w    f ( x1 1 0 x4 ) ]·[ x
¯2    w    x
¯3    w    f ( x1 1 1 x4 ) ]  =
= 
 f    = 
    [ x2    w    x3     w                                      ]·[ x2    w    x
¯3     w                                     ] · 
     x
¯1 x
¯4 · f (  x  1  x4  )     w        x
¯1 x4 · f (  x 1   x4  )  x  w  1 1 x3 
     ·[ x
¯
     TTÜ 
       
2    w    x3     w                                      ]·[ x
¯2    w    x
¯3     w                                     ] =
w        x1 x
¯4 · f (  x  1  x4  )     w        x1 x4 · f (  x 1   x4  )     =
  
      = 
(x
     x
¯
2   w  x3   w    x
¯4 )(x2   w   x
¯3   w   x
¯4)(x
¯2    w    x3    w    x
¯1 x
¯4)(x
¯2   w   x
¯3   w    x
¯4)
1 x
¯4 · f ( 0 x2 x3 0 )     w        x
¯1 x4 · f ( 0 x2 x3 1 )  x  w  1 1 x3 
 |______________________________________________________________________________|
       w        x1 x
¯4 · f ( 1 x2 x3 0 )     w        x1 x4 · f ( 1 x2 x3 1 )     =
/¯¯  iseseisvaks  lahendamiseks:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
      =      x
¯1 x
¯4 · (  x         1      x4  )     w        x
¯1 x4 · (  x         1      x4  )  x  w  1
3 muutuja  järgi  disjunktiivne arendus:
       w        x1 x
¯4 · (  x      1         x4  )    w        x1 x4 · (  x      1         x4  )      =
Teha  Shannoni  disjunktiivne arendus  muutujate    x 1      x 3      x 4    järgi
Arvutitehnika 


= 
avaldisele     [
   x 1  
   ( x 2   
  x 3 )] x
¯ 4 
    x
¯

1 x
¯4 · ( 1 )   w      x
¯1 x4 · ( 0 )   w     x1 x
¯4 · ( x2      x3 )   w      x1 x4 · ( 0 )
|______________________________________________________________________________|
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
 f    =       x
¯1 x
¯3 x
¯4 · f ( 0 x2 0 0)     w         x
¯1 x
¯3 x4 · f ( 0 x2 0 1)  x  w  1 1 x3 
2 muutuja  järgi  konjunktiivne arendus:
w      .   .   .   .  .   .      w      x1 x3 x
¯4 · f ( 1 x2 1 0)     w        x1 x3 x4 · f ( 1 x2 1 1)    =
Teha  Shannoni  konjunktiivne arendus  muutujate    x 2    ja    x 3    järgi   
samale avaldisele     [


=   .   .   .   .    jääkfunktsioonid saavad tulla:     x2     või      x
¯2     või     0    või    1
   x 1  
   ( x 2   
  x 3 )] x
¯ 4 
   Instituut
|______________________________________________________________________________|
Shannoni arendus  samaaegselt  kõikide  muutujate järgi  on  täielik arendus.
Täieliku  arenduse  jääkfunktsioonideks  saavad jääda  ainult  konstandid  ( 0   1 )
Loogikafunktsiooni   TULETIS
meenutame tehte   
n-muutuja  funktsiooni
   asendusseost :            x1      x2   =    x
¯1 x2    x1 x
¯2
    f ( x1 . . . . xn )    tuletis  selle funktsiooni mingi
muutuja    xi   järgi 
                  ______________
 
           ____
 
 f (
.  .  .   =  ( x
¯2 x
¯4    w   x
¯1 x 2) x
¯2 x
¯4     w     ( x
¯2  x
¯4    w   x
¯1 x2 ) x
¯2 x
¯4    =
 x1 . . . . xn )
————————

        ____    ____
 xi
=   x
¯2 x
¯4    x
¯1 x 2  x
¯2  x
¯4     w     ( x
¯2  x
¯4    w   x
¯1 x2 ) ( x 2    w  x 4 )   =
on   jääkfunktsioonide  summa mooduliga 2  avaldis  kujul:
=    (x 2    w  x 4)(x 1   w  x
¯ 2) x
¯2 x
¯4     w     x
¯1 x2       w      x
¯1 x2 x4     =
 f ( x1 . . . . xn )
 ———————    =   f ( x1 .. xi1 0  xi1 .. xn )        f ( x1 .. xi1 1  xi1 .. xn )
=    ( x1 x2     w   x1 x4     w    x
¯2 x4 ) x
¯2 x
¯4      w      x
¯1 x2        =
     TTÜ 
   xi
=     
Seega  on  n-muutuja  funktsiooni  tuletis   (n1)-muutuja funktsioon, kus
 x
¯1 x2 
puudub see muutuja   xi  ,  mille järgi tuletis võeti:
saime vaadeldava funktsiooni    f  =   x
¯ 2  x
¯ 4    w   x
¯ 1 x 2  x
¯ 3     jaoks  tema
 
tuletise  muutuja    x
f (
 3    järgi :  
 x1 . . xi . . xn )
 —————————     =   f ( x1 .. xi1  xi+1 .. xn )
 f 
    xi
 ———     =       x
¯1 x2
 x 3
Arvutitehnika 
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
|______________________________________________________________________________|
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
Leida  järgneva loogikafunktsiooni  tuletis   muutuja    x 3    järgi :
Leida  sama loogikafunktsiooni  tuletis   muutuja    x 2    järgi :
 f     =      x
¯ 2  x
¯ 4       w     x
¯ 1 x 2  x
¯ 3 
 f     =      x
¯ 2  x
¯ 4       w     x
¯ 1 x 2  x
¯ 3 
 f ( x1 x2 x3 x4 )
   Instituut
 ————————      =      f ( x1 x2 0 x4 )             f ( x1 x2 1 x4 )    = 
  x3
 f ( x1 x2 x3 x4 )
 ————————      =      f ( x1 0 x3 x4 )             f (x1 1 x3 x4 )    =
  =    ( x
¯
  x2
 2  x
¯ 4       w     x
¯ 1 x 2 )               x
¯ 2  x
¯ 4      =     .  .  .  .
  =      x
¯ 4               x
¯ 1  x
¯ 3      =     .  .  .  .
 jälle kasutame  tehte      asendusseost :        x1      x2   =    x
¯1 x2    x1 x
¯2
                        __
  ____
.  .  .  .    =     x
¯4  x
¯1 x
¯3      w      x
¯4  x
¯1 x
¯3    =
              =     x4 x
¯1 x
¯3       w      x
¯4 ( x 1    w   x 3 )     =
              =     x
¯1 x
¯3 x4       w      x1 x
¯4      w      x3 x
¯4 
     TTÜ 
tekkis  DNK  mida ei saa enam teisendada  lihtsamaks DNK-ks, seega ongi valmis
saime vaadeldava funktsiooni   f  =    x
¯ 2  x
¯ 4    w   x
¯ 1 x 2  x
¯ 3     jaoks  tema
tuletise  muutuja    x 2    järgi :  
 f 
 ———     =       x
¯1 x
¯3 x4       w      x1 x
¯4      w      x3 x
¯4
 x 2
|______________________________________________________________________________|
Arvutitehnika 
   Instituut