Loogikaalgebra (0)

Loogikaalgebra        ( Boole 'i   algebra )
Kasutusel on ka alternatiivseid tehtemärke :   &
~ 

    
    
+   

George  Boole
(1815  —  1864)
Inversiooni  esitatakse  mõnes allikas ka  ülakomaga:     x
¯        x'
Sündinud Inglismaal Lincolnis.  16-aastasena tegutses kooliõpetaja 
Loogikaavaldiste  võrdsus
assistendina. Õppis 5 aastat iseseisvalt omal käel matemaatikat, 
keskendudes hiljem algebrale.  1835 avas oma kooli.
Kaks erinevat loogikaavaldist on võrdväärsed  ehk  loogiliselt  võrdsed ,  kui
Uudse lähenemisega loogikale korrastas selle  kaasaegseks 
nad mõlemad omandavad  muutujate (kõikvõimalike) samade
loogikaalgebraks.
väärtuskombinatsioonide korral  sama loogikaväärtuse   0   või   1 .
Loogikaalgebra   (

 { 0 , 1 } ;      
¯¯  ,   ,   ) koosneb loogikaväärtuste hulgast    
teiste sõnadega:   loogikaavaldised / loogikafunktsioonid on teineteisega
< , millel on defineeritud  3 elementaarset loogikatehet:   unaarne tehe  
loogiliselt võrdsed, kui nende tõeväärtustabelid on täpselt samasugused
inversioon    ja   binaarsed tehted    konjunktsioon    ja    disjunktsioon .
näide: 
   
Kõik 3 elementaarset loogikatehet on juba eelpool lausearvutuse juures
 x1 x
¯2     w    x2       =       x1    w    x
¯1 x2
     TTÜ 
defineeritud ja loogikaalgebras kehtivad nad täpselt samal kujul. 
Asendades siin  muutujate    x1   ja     x2   asemele  mingid loogikaväärtused,
väärtustuvad võrduse mõlema poole avaldised  alati ühtemoodi  0-ks  või
Muutuja   x   või   xi   on  loogikamuutuja , kui ta saab omandada väärtusi
ühtemoodi  1-ks.     (kontrollida!)
ainult hulgast  <.
     
xi { x1    x2 . . . . xn }
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
Numbrimärkidena   0   ja   1   esitatud loogikaväärtusi nimetatakse ka  
"konstant 0"  ja  "konstant 1" , et rõhutada nende erinevust  muutujatest  xi  .
Loogikaavaldis  on   loogikamuutujaid   xi  ,    konstante   0   1   ja  
Kontrollida  eelpoolsete  avaldiste     x1 x
¯2    w   x2      ja      x1   w   x
¯1 x2 
tehtemärke  sisaldav kooslus , mis tema muutujate   x
loogilist võrdsust  nende tõeväärtustabelite võrdlemise teel
i   väärtustamisel
omandab samuti loogikaväärtuse   0   või   1 .
x1 x2
x1 x
¯2    w    x2
x1   w    x
¯1 x2
Loogikaavaldis sarnaneb lausearvutuses kasutatavale  lausearvutusvalemile  
Arvutitehnika 
 0  0  
ning ta  defineeritakse analoogiliselt:
  0  1  
/¯¯  definitsioon:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
 1  0  

loogikamuutuja    xi    ja  konstandid    0    1   on  loogikaavaldised;
 1  1  
   __

kui   A   on loogikaavaldis,  siis on avaldised ka   A    ja   ( A )

kui   A   ja   B   on  loogikaavaldised,  siis on  avaldised  ka
A  B
 
A  B
 
 
A  B
   A  B              A  B
x1 x2
x1 x
¯2    w    x2
x1   w    x
¯1 x2

tehtemärgi puudumine operandide vahel on samaväärne tehtega     
 0  0  
0
0
ehk  konjunktsiooniga :    A

   Instituut
 B      A  B      A   B  
  0  1  
1
1
|____________________________________________________________________________________ |
 1  0  
1
1
Eelnev definitsioon välistab loogikaavaldiste hulgast ebakorrektsed
 1  1  
1
1
operandide ja tehtemärkide kooslused:   A  

 
|____________________________________________________________________________________ |
 
 
 B
       A B 
        A ( 
   B
Loogikaavaldised
  2-muutuja  loogikafunktsioonid      f (
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
 x1 x2 )
/¯¯  ülesanne:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
Arvutada   tõeväärtustabel    3-muutuja loogikafunktsioonile:

Esitada igale järgnevale tõeväärtustabelile    f
f ( x1 x2  x3 )    =     ( x 3  
 x 1 ) x
¯ 2     w     ( x
¯ 1   x 2 )
1 . . . . f5
1 . . . . 3  erinevat sobivat  loogikaavaldist:
x1 x2 x3
 f ( x1 x2  x3 )
f
0  0  0
  1
f 2
f3
f4
f5
x1 x2
0  0  1
 0  0
0
1
1
1
1
0  1  0
 0  1
0
0
0
0
1
0  1  1
     TTÜ 
 1  0
1
0
1
1
1
1  0  0
 1  1
0
1
1
0
1
1  0  1
1  1  0
1  1  1
x1 x2 x3
 f ( x1 x2  x3 )
0  0  0
1
f
0  0  1
0
Arvutitehnika 
  1
f 2
f3
f4
f5
x1 x2
0  1  0
1
 0  0
0
1
1
1
1
0  1  1
1
 0  1
0
0
0
0
1
1  0  0
1
 1  0
1
0
1
1
1
1  0  1
1
 1  1
0
1
1
0
1
1  1  0
0
1  1  1
0
vastus:
vastus:
vastus:
vastus:
vastus:
|______________________________________________________________________________|
_________
x1 
  
  x2
x1 
  
  x2
x2 
  
  x1
x
¯2
1
x1  x
¯2
x
¯1 x
¯2   
 
  x1 x2
x1 
       x
¯2
   Instituut
________ 
________________ 
______
x
¯1  
    x2
x
¯1 x2   
     x1 x
¯2
x
¯1  x2
|____________________________________________________________________________________ |
Loogikaavaldiste  duaalsus
L O O G I K A A L G E B R A      P Õ H I S E O S E D 
Loogikaavaldis omandab  oma  duaalse  kuju, kui
   _
    avaldise kõik   konjunktsioonid   asendada   disjunktsiooniga
eituse eitamise seadus :
 x
¯  =  x
    avaldise kõik  disjunktsioonid  asendada  konjunktsiooniga
seosed konstantidega  0  ja  1 :  
   avaldise kõik  konstandid   0   asendada  konstandiga   1
__

 __
   avaldise kõik  konstandid   1   asendada  konstandiga   0
(inversioone  ei asendata  duaalsele kujule üleminnes)
 0  =  1
 1  =  0
0  1 = 0
0  w  1 = 1
Loogikaavaldiste kohta kehtib  duaalsusprintsiip :
 x  0  =  0
 x  1  =  x
x  x
¯  =  0
Kui  2  loogikaavaldist on võrdsed,  siis on ka nende   duaalsed avaldised
 x 
omavahel võrdsed.
 w  0  =  x
 x  w  1  =  1
x  w  x
¯  =  1
     TTÜ 
idempotentsus :
x  x  =  x
x  w  x  =  x
Loogikaalgebra   põhiseosed
DeMorgani seadused :
Duaalsusprintsiibist tulenevalt  kehtivad  kõik  loogikaalgebra põhiseosed
 kahe  muutuja   jaoks )
duaalsete  paaridena .
 ______
 ____
Loogikaalgebra põhiseosed  esituvad  kuni  3 loogikamuutuja abil, mida
 x  w  y   =   x
¯  y
¯
  x  y   =   x
¯  w   y
¯
tähistame siin    x    y    z  .    Neid muutujatähiseid on põhiseoste esitamisel
kasutatud indeksite vältimiseks  ehk  nad on    x
DeMorgani seaduste modifikatsioon 3 muutuja jaoks:
1 x2 x3    asemel
Igaüks nendest  on tegelikult  loogikaväärtus   0  või  1 :      x,
___________
 ______
 y, z { 0 1 }
 x  w  y   w 
Arvutitehnika 
 z    =   x
¯  y
¯  z¯
 x  y  z   =   x
¯  w   y
¯   w   z¯
Järgnevad võrdused  (põhiseosed)  kehtivad olenemata sellest, kumba
loogikaväärtuse  ( 0  või  1 )  me nendes iga loogikamuutuja       x     y     z   
asemele asendame.  
neeldumine  :
   x   w  x y   =  x 
  x   w   x
¯ y    =   x    w  y
Põhiseoste kehtivus  tuleneb  elementaarsete loogikatehete definitsioonidest:
konjunktsioon
disjunktsioon
distributiivsus :  
( sulgude nn. "lahtikorrutamine"  ja  "lahtiliitmine)



 x (  y  w  z )  =  x y  w  x z
            x  w  (  y z )  =  ( x  w  y ) ( x  w  z )
___________________________________________________________
0   0
0
0
0   1
0
1
   Instituut
kleepimine :
 (ebaolulise  muutuja / avaldiseliikme  lisamine)
1   0
0
1
1   1
1
1
 x   =   x y   w   x y
¯  
     x   =   ( x   w   y ) ( x  w  y
¯  )
Neeldumisseaduste olemus
Rõhutame, et  eelnevad  tähised     x     y     z      esitavad mitte ainult
Lisame veel ühe märkuse  neeldumisseadusele     x   w   x
¯ y   =   x   w   y
üksikuid loogikamuutujaid, vaid    x     y     z     asemel võivad olla ka  
Selle reegli verbaalseks esituseks sobiks:
keeruka(ma)d  loogikaavaldised,  kuna ka avaldised  arvutuvad / asenduvad
loogikaväärtusteks  0  või  1 . 
"disjunktsiooni ühele poolele võib  juurde korrutada teise poole inversiooni  
(avaldise väärtust sellega muutmata)".
/¯¯  näide:   ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ \
neeldumisseadusest     x   w  x y   =  x     tuleneb, et  neeldumine toimub ka
Seega kehtivad võrdused:
näiteks avaldises      x1 x
¯2 x3    w    x1 x
¯2 x3 x4 x
¯5    :
 x   w   y    =    x    w   y x
¯          ning samuti        x   w   y    =    x y
¯   w   y 
ehk
 x1 x
¯2 x3   w   x1 x
¯2 x3 x4 x
¯5     =    (
)   w   (
) [
]   =   
 x1 x
¯2 x3 
 x1 x
¯2 x3     x4 x
¯5 
 
 x1 x
¯2 x3
 x   
|____________________________________________________________________________________ |
w   x
¯ y     =     x   w   y     =     x y
¯    w    y
     TTÜ 
Loogikatehete  asendusseosed
Neeldumise      x   w  x y   =   x    kehtivust kinnitab ka teisendus, kus ühine
tegur   x  tuuakse  võrduse vasakus pooles  sulgude ette, misjuhul sulgudesse
Asendusseosed  asendavad   mitteelementaarseid  loogikatehteid
jääb konstant 1 :
implikatsioon:       
 x   w  x y    =    x ( 1  w  y )   =    x ( 1)    =    x 
ekvivalents:        
summa mooduliga 2:    
( ka  "välistav VÕI"       XOR  )   
pane tähele:     x   w  x y    =    x ( 1  w  y )    on korrektne teisendussamm, kuna  
( see tehe on käsitletud edaspidi )
sulgude lahtikorrutamisel             x ( 1  w  y )    tekkib taas avaldis     x   w  x y   
...elementaarsete loogikatehete  (inversioon, disjunktsioon, konjunktsioon)  kaudu:
Neeldumisvõrduste     x   w   x
¯ y     =     x   w   y    
Arvutitehnika 
ja
   x y
¯ 
  x
   w    y      =     x   w   y  
    y    =     x
¯   w  y
kehtivus on tõestatav  ka  nende võrduste  parema poole avaldise
teisendamise teel  vasaku poole avaldiseks.
  x    y    =    ( x  y ) (  y  x )   =  . . . . . .  =    x
¯ y
¯   w   x y
Arvestades, et    x  w  x
¯  =  1   saame  distributiivsusseaduse  (sulgude
  x    y    =    x
¯ y   w   x  y
¯
lahtikorrutamise) abil   ja   neeldumise     x   w  x y   =  x     abil  teisendada:
 x   w  
Loogikaavaldiste  teisendamine
 y    =    ( x   w   y )  1    =     ( x   w   y )  ( x   w  x
¯ )    =   
  =     x x   w   y x   w   x x
¯    w    y x
¯     =    
Loogikaavaldiste  teisendamine  on nende viimine  muule  samaväärsele
  =       x   w   x y    w    0     w    y x
¯    =    x   w   x
¯ y 
(lihtsamale)  kujule.
   Instituut
Loogikaavaldisi  teisendatakse   loogikaalgebra põhiseoseid   ja  
Seega saime : 
 x   w  
loogikatehete asendusseoseid   rakendades.
 y    =    x   w   x
¯ y