Mis on Diskreetne Matemaatika (0)

Diskreetse Matemaatika õpik



Mis  on  Diskreetne Matemaatika  ? " diskreetne "    ≡   " mitte pidev "  ehk  " astmeline " vs. " Diskreetne Matemaatika "    ↔   " Pidev Matemaatika "       Diskreetne Matemaatika  ei tegele  reaalarvudega  ega  pidevate funktsioonidega. Diskreetse  Matemaatika  alla kuuluvad: —  Hulgad: Hulgaalgebra  (Cantori algebra),  Hulgaaritmeetika —  Loogika: Lausearvutus,  Predikaatarvutus,  Tõestusmeetodid —  Loogikaalgebra  (Boole'i algebra) —  Loogikafunktsioonid: minimeerimine,  normaalkujud . . . —  Algebralised  struktuurid:   Fundamentaalalgebrad:   Võred,  Rühmad,  Ringid,  Korpused —  Vastavused  ja  Relatsioonid —  Graafid —  Kombinatoorika: Kombinatsioonid,  Variatsioonid,  Permutatsioonid Termineid: —  verbaalne  esitus   on  mistahes info esitamine  lingvistilise  keele  abil. —  formaalne  esitus   on  mistahes info esitamine  ilma lingvistilise  keele  
abita  ehk  kokkulepitud  sümbolite  abil. NB!
MÕTLEMINE on  alati  verbaalne ehk toimub mingi lingvistilise  keele  
abil. Mistahes formaalne esitus  on   algupäraselt verbaalse  info  
"salvestamiseks". Formaalsete  esituste  ainus  otstarve  on  nendes  sisalduv  info  hiljem  jälle
verbaalseks  (ehk mõnda  lingvistilisse  keelde)  tagasi  "üles lugeda"  
(taastada). Mistahes  formaalne  esitus  peab  olema  üheselt  tõlgendatav !    "mitteformaalne"    ≡   "verbaalne"    (sünonüümid) M A T E M A A T I L I N E     L O O G I K A LAUSEARVUTUS Lausearvutus  on  loogilise  mõtlemise  matemaatiline  mudel. Lausearvutuse  lause  võib olla  iga  verbaalne  (ehk lingvistilises keeles
väljendatud)  väide,  millele  saame  omistada  tõeväärtuse  —  tõene  või  
vale. Tõeväärtusi  tähistame  numbritega  0  ja  1. 0  —  vale (väär) 1  —  tõene Lause peab omandama ühe tõeväärtuse nendest kahest alternatiivist. Lausearvutuslauseteks  võivad  olla: " 19 on algarv "


" popcorn  on  hea " " jänesed  jooksevad  vihmaveetorudes " Lausearvutuslauseteks  ei  ole  (ei kõlba): " kõigi  maade  proletaarlased, ühinege  " " olla  või  mitte  olla " Lihtsaimaid  võimalikke  lausearvutuslauseid  nimetatakse  lihtlauseteks. Lihtlauseid  ei saa  enam  jagada  veelgi  lihtsamateks  
lausearvutuslauseteks. Lausearvutuslauseid  tähistame  formaalselt  suurtähtedega:  A, B,  P,  Q . . . Lihtlausetest  koostatakse  kindlate sidesõnade  ja  loogiliste
konstruktsioonide abil  liitlauseid: " kui palka ei tõsteta  või  tööaega ei vähendata, siis algab streik " " ülemus  on  kohal  ainult  siis,  kui  tema auto  on  maja  ees" Lausearvutuse  lihtlauseid  seotakse  liitlauseteks  5  loogilise
konstruktsiooni ehk  loogikatehte  abil. 4 sidumiskonstruktsiooni seovad igaüks  kahte lauset  (binaarsed
loogikatehted)  ja  1  tehe  on  rakendatav  üksikule  lausele  (unaarne  
loogikatehe) verbaalne  esitus formaalne  tähistus P eitus: " mitte P ";  " pole õige, et P " __ P Ühe  alternatiivi  kehtimise  nõue: " P või Q " P  ∨ Q Tingimuste samaaegse kehtimise nõue: " P ja Q " P  ∧ Q Järeldumine : " Kui P ,  siis Q " "P kehtimisest järeldub Q kehtimine " P  → Q Samaväärsus  (ekvivalents): " P (siis ja) ainult siis, kui Q " P   ↔  Q JA-tehte märgina kasutatakse ka sümbolit  'ampersand ' :   &     ( &   ≡  ∧ ) Ekvivalentsitehte märgina  kasutatakse  ka  sümbolit     ~    ( ~    ≡   ↔ ) VÕI-tehte märgina  kasutatakse  ka  sümbolit     +    ( +     ≡   ∨∨  )


LOOGIKATEHTED  lausearvutuses tehtemärk tehte nimi  ja  selgitus      ¯ ¯  loogiline eitus  e.  inversioon ∧  loogiline  korrutamine  e.  konjunktsioon  e.  JA-tehe
( aritmeetilise  korrutamise  analoog  loogikas ) ∨  loogiline  liitmine  e.  disjunktsioon  e.  VÕI-tehe
( aritmeetilise  liitmise  analoog  loogikas ) →  loogiline  järeldamine  e.  implikatsioon
( ei oma aritmeetikas analoogi) ↔  loogiline  samaväärsus  e.  ekvivalents
( võrdusmärgi  '  = '  analoog  loogikas) Implikatsioonitehte  operandide  staatus: eeldus   →  järeldus Ekvivalentsitehte mõlemad operandid  on  teineteise eelduseks  ja  järelduseks : kui       P   ↔  Q     siis     P   →  Q  ja samal ajal ka      Q  →  P LAUSEARVUTUSVALEMID
Nii  liht-  kui ka  liitlausete  formaalseid  esitusi  nimetatakse  
lausearvutusvalemiteks.     Lausearvutusvalem on defineeritud järgnevalt: — Lihtlause formaalne tähis ja tõeväärtuskonstant on valem:  A    0   1    __ — Kui A on valem, siis on valemid ka   A   ja  (  A ) — Kui  A  ja  B  on valemid, siis on valemid ka A  ∧ B A  ∨ B A  → B A  ↔ B Eelnev määratlus välistab valemite hulgast näiteks sellised sümbolitekooslused:   A  ∧ ∨ B A    B   ↔    A (  → ) B ülesanded: Olgu  antud  järgnevad  lihtlaused  (väited): S  —    on suvi O  —   väljas on soe V  —   vihma sajab P  —   väljas on pime R  —   päikesevarjutus kestab L  —   päike on loojunud M  —   Ferrari on kiirem kui McLaren H  —   Häkkinen võidab sõidu Esitada  järgnevad  liitlaused  lausearvutusvalemitena: Kui vihma sajab, siis on suvi või väljas on soe V   →  ( S  ∨  O ) Väljas on pime (siis ja) ainult siis, kui päike on
loojunud ja pole suvi  või  päikesevarjutus kestab      __    P   ↔  ( L  ∧∧    S  ∨∨    R ) Kui on suvi või päike pole loojunud, siis väljas
pole pime   __    __  ( S   ∨  L )   →   P Kui vihma sajab, siis Häkkinen ei võida sõitu    __ V    →    H


Kui McLaren on kiirem kui Ferrari ja vihma ei saja,
siis Häkkinen võidab sõidu       __    __   ( M    ∧   V )   →   H Häkkinen ei võida sõitu (siis ja) ainult siis, kui
Ferrari on kiirem kui McLaren või vihma sajab  __ H    ↔    ( M   ∨∨     V )   Lugeda  järgnevaid  lausearvutusvalemeid  (taastada lause verbaalne  esitus):      __ R    →    ( L  ∧∧    P )  Kui päikesevarjutus kestab, siis päike pole
loojunud ja on pime        __ O    ↔    ( S  ∨∨    L ) Soe on (siis ja) ainult siis, kui on suvi või päike
pole loojunud           __ ( V    ↔   S  )   ∨   ( P   ∧   O  ) Vihma sajab (siis ja) ainult siis, kui on suvi või väljas on pime ja külm           __ ( S    ∧   O   ∧   P )   →    S Kui vihma sajab ja on soe ja pole pime, siis on
suvi      __    __ ( M    ∧   H  )   ∨   ( V   ∧   H  ) McLaren on kiirem kui Ferrari ja Häkkinen võidab
või  vihma sajab ja Häkkinen ei võida


LOOGIKATEHETE  DEFINITSIOONID Loogikatehete  definitsioonid  määravad  nende  resultaadi  kõikide  
operandiväärtuste  kombinatsioonide  korral.   (määravad  nende "käitumise"
kõikvõimalikes  olukordades). Loogikatehete  operandideks on tõeväärtused  (0 ja 1)  ja tulemuseks on samuti
tõeväärtus.     Lausearvutuses  kasutatakse ühte unaarset ja nelja binaarset tehet. Kui  A  ja  B  on  suvalised lausearvutuslaused  alternatiivsete tõeväärtustega
0 või 1, siis nendevaheliste  loogikatehete  tulemuseks  olevate  liitlausete   
tõeväärtused  on  järgnevad:   inversioon konjunktsioon disjunktsioon implikatsioon ekvivalents Α  Β ___ A Α  Α ∧∧∧ Β  Β   Β Α  Α  Α ∨∨∨ Β  Β   Β Α  Α  Α → → → Β  Β   Β Α  Α  Α ↔ ↔ ↔ Β  Β 0   0 1 0 0 1 1 0   1 1 0 1 1 0 1   0 0 0 1 0 0 1   1 0 1 1 1 1 Seega  oleneb  iga  liitlause  tõeväärtus  teda  moodustavate  lihtlausete
tõeväärtustest  ja  nende  sidumiseks  kasutatud  loogikatehetest. Loogikatehete  prioriteet:            ¯ ¯ ∧ ∨ →               ↔ ülesanded: Olgu  lihtlaused  järgnevate  tõeväärtustega: S   =   0 O  =   1 V   =   0 P   =   1 L   =   1 M  =   1 H   =   0 Leida  selliste  koostislausete tõeväärtuste  korral järgnevate  liitlausete  tõeväärtused:        __ O    ↔    ( S  ∨∨    L )    __      __ O    ↔    ( S  ∨∨    L )   =   1   ↔    ( 0  ∨∨    1 )   =   0    [vale] ————————————————————————————————————————————           __ ( V    ↔   S  )   ∨   ( P   ∧   O  )      __     __ ( V  ↔ S )  ∨  ( P  ∧  O )   =   ( 0  ↔  0 )   ∨   ( 1  ∧  1 )  =  1 [tõene] ————————————————————————————————————————————           __ ( S    ∧   O   ∧   P )   →    S          __   __ ( S   ∧  O   ∧   P )  →   S   =   ( 0  ∧  1  ∧  1 )  →  0   =   1     [tõene] ————————————————————————————————————————————      __   __ ( M    ∧   H  )   ∨   ( V   ∧   H  )   __   __   __       __ ( M  ∧ H ) ∨ ( V ∧ H )   =   ( 1  ∧  0  )  ∨  ( 0  ∧  0  )    =   0    [vale] ———————————————————————————————————————————— Lause  on  samaselt tõene,  kui  ta omandab  tõeväärtuse  1  koostislausete
mistahes  väärtuskombinatsioonide  korral.  Samaselt  tõest  lauset  nimetatakse ka  tautoloogiaks. Lause  on  samaselt väär,  kui ta omandab  tõeväärtuse  0    koostislausete
mistahes  väärtuskombinatsioonide  korral.  Samaselt  väära  lauset  nimetatakse ka  vastuoluks. Samaselt  tõesed  laused  võib  asendada  (tähistada)  konstandiga  1  ja   samaselt väärad  laused  konstandiga  0 . 


PREDIKAADID
Predikaat  on  lause (valem),  mis  sisaldab  ühte  või  enamat  muutujat.
(Predikaatlause) Predikaatlause  tõeväärtus  oleneb  väärtustatud  muutuja(te)  
tõeväärtus(t)est. Kui  predikaadi  muutujad  asendada  mingite  konkreetsete  väärtustega  
lubatud  väärtustehulgast,  siis  predikaat  muutub  lauseks  (ehk  omandab  
tõeväärtuse). Predikaate  tähistatakse  suurtähtedega;  temas  sisalduvaid  muutujaid  
(predikaatmuutujaid)  väiketähtedega. Ühekohaline  predikaat  —  ühe muutujaga: P ( x )   ≡  . . . muutujat  x  sisaldav  lause  või  valem . . . Kahekohaline  predikaat  —  kahe muutujaga: P ( x, y )   ≡  . . . muutujaid  x  ja  y  sisaldav  lause  või  valem . . . Predikaat  võib  olla  esitatud  ka verbaalselt:   (harvaesinev) A ( x )   ≡   "  x  on  algarv  " Reeglina  eelistame  predikaate  võimalusekorral  esitada  formaalselt  ehk  
valemitekujul   (predikaatvalem). Predikaatmuutujate  kohta  tuleb  alati  eelnevalt  täpsustada, milliseid  
väärtusi  ta  võib  omandada  ehk  milline  on  predikaadi  
määramispiirkond. Olgu   x   täisarv  ja  vaatleme  ühekohalist  predikaati: P ( x )    ≡   ( x  >  2 )   ∧  ( x  <  4 ) Väärtustades    x  =  3  saame  tõese  predikaatlause  (predikaatvalemi): P ( 3 )    =   ( 3  >  2 )   ∧  ( 3  <  4 )   =  1  ehk P ( 3 )    =   1   ehk    tõene Omistades  predikaatmuutujale  mõne muu  täisarvulise  väärtuse: P ( 5 )    ≡   ( 5  >  2 )   ∧  ( 5  <  4 )   =   0   ehk P ( 5 )    =   0   ehk    vale Ühekohalist  predikaati  nimetatakse  omaduseks. Kui predikaatmuutuja  mingi  konkreetse väärtuse   n  korral  predikaatlause   P (  n )   osutub  tõeseks,  siis  ütleme,  et  " n-il  on  omadus  P ". Eelmises  näites: täisarvul  3  on omadus  P ;  täisarvul  5  pole. Predikaatlause   P ( x )  võib  olla: —  täidetav ehk kehtestatav:  kui ta on  tõene ainult  osade   muutujaväärtuste   x  korral  (ehk osas määramispiirkonnas) —  samaselt tõene: kui ta on  tõene (kehtiv)  kogu  määramispiirkonnas —  samaselt väär: kui ta ei  kehti  mitte  mingite  muutujaväärtuste 
korral  oma  määramispiirkonnas KVANTORID ∀ ∃ Kui  soovime  väita,  et  predikaat   P (x)  kehtib  oma  määramispiirkonna   kõikide    x-ide  (  x 1  x2  x3  . . .  )  korral  ehk: P ( x 1 )   ∧  P ( x2 )   ∧  P ( x3 )   ∧  P ( x4 )   ∧  . . . .   =   1 siis  kasutame  sellise  väite  kompaktsemaks esitamiseks üldsuse  kvantorit:   ∀ ∀x P (x) ehk  üldkujul: ∀x ( . . . mistahes  lause  muutuja  x  osalusel . . . ) Kui  kvantorit  rakendatakse  üksikule  predikaaditähisele, võib  sulud  ära  jätta.


Üldsuse kvantorit   ∀  interpreteeritakse  valemi  lugemisel:   "iga". Kui  soovime  väita,  et  predikaat   P (x)  kehtib  vähemalt  ühe  oma   määramispiirkonna   x-i   korral  ehk: P ( x 1 )   ∨ ∨   P ( x 2 )   ∨ ∨   P ( x 3 )   ∨ ∨   P ( x 4 )   ∨  . . . .   =   1 siis  kasutame  sellise  väite  kopaktsemaks esitamiseks olemasolu  kvantorit   ehk  eksistentsikvantorit    ∃   : ∃x P (x) ehk  üldkujul: ∃x ( . . . mistahes  lause  muutuja  x  osalusel . . . ) Üldsuse kvantorit   ∃  interpreteeritakse  valemi  lugemisel:   "leidub"  ehk   "eksisteerib". Kvantorid   ∀   ja   ∃  sobivad  seega  predikaadi  P (x)  kehtestatavuse   täpsustamiseks  nii  lõpliku  määramispiirkonna  kui  ka  lõpmatult  suure  
määramispiirkonna korral. Kui  predikaadile   P (x)  on  rakendatud  kvantorit,  siis  ta  omandab  kohe   tõeväärtuse  (tõene  või   vale)  ja  ta  tõeväärtus  ei  olene  enam  
predikaatmuutujale   x  omistatud  konkreetsest  väärtusest.  Kvantori  rakendamise  tulemuseks  on  seega  uus,  tõeväärtusega  lause. näide: Rakendame  eelnevalt  vaadeldud  predikaadile   P ( x )    ≡   ( x  >  2 )   ∧  ( x  <  4 ) esmalt  üldsuse  kvantorit  ning  seejärel  olemasolu  kvantorit   ning  leiame
 tulemuseks  olevate  lausete  tõeväärtused:
∀x P (x)      [vale]    ∃x P (x)   [tõene] Kvantorit  võib  predikaaditähise  asemel  rakendada  ka  predikaatlausele  
endale:
∃x [ ( x  >  2 )   ∧  ( x  <  4 ) ] Kvantorite  määratlusest  järeldub: Kui lause     ∀x P (x)     osutub  tõeseks,  siis   ∃x P (x)   on  samuti  tõene. Kvantorimärgiga  seotud  muutujat (muutujaid)  nimetatakse  seotud  
muutujateks. Kvantorimärgiga  mitteseotud  predikaatmuutujad  on  vabad muutujad. näide: ∀x  P (x, y) korral:   x  on seotud  ja  y  on vaba muutuja. __ Eksistentsikvantorit  saab  ka "eitada":    ∃ x "ei leidu . . ." Hüüumärgiga eksistentsikvantor     ∃! x    väidab  seotud  muutuja  kohta: "leidub  täpselt  üks . . ." Kvantorid    ∀   ja   ∃   on omavahel  seotud  järgneva  samaväärsusega:   __   __ ∀x  P (x)   ≡   ∃x  P (x) Kvantorit saab rakendada ka sellisele lausele, millele on juba eelnevalt
kvantorit rakendatud: ∀x ∃y ( x + y  = 9 ) (eelneva predikaatlause tõeväärtus oleneb ta määramispiirkonnast) Kvantoriga  võivad olla seotud  ka  mitu  muutujat: ∀x ,y P (x, y)   ≡   ∀x∀y P (x, y)


Sarnaselt  muutujateta lausearvutuslausetega  saab  ka  predikaate  siduda  
liitpredikaatideks  nendesamade  loogikatehetega:        ¯ ¯      ∧     ∨     →      ↔ Predikaadid  on  võrdväärsed (ekvivalentsed) , kui  nende  
tõeväärtuspiirkonnad  langevad  kokku. näide: Olgu  naturaalarvulise  muutumispiirkonnaga  ühekohalised  predikaadid: P (x)   ≡  " x  jagub  3-ga " Q (x)   ≡  " x  jagub  4-ga " S (x)   ≡  " x  jagub  12-ga " T (x)  =  P (x)    ∧   Q (x) . . . .  siis: S (x)   ≡  T (x) ülesanded: On  antud  reaalarvulise  määramispiirkonnaga  predikaadid:   N (x)   ≡   " x  on  naturaalarv " Z (x)   ≡   " x  on  täisarv " P (x)   ≡   " x  on  algarv " H (x)   ≡   " x  on  paarisarv " D (x , y)   ≡   " x  jagub  y-ga " Leida  predikaatlausete  tõeväärtus:      ∀x [ N (x)   →   Z (x) ] __  ∀x [ Z (x)   →   H (x)   ∨  H (x) ] ∀x ∃y [ Z (x)  ∧  Z (y)   →   D (x , y) ] ∃x [ P (x)  ∧  H (x) ]    märkus:   kui määramispiirkonnaks oleks reaalarvude asemel täisarvud ,  siis
2ne  ja  3mas  predikaatvalem  lihtsustuksid:     __ ∀x [ H (x)  ∨  H (x) ] ∀x ∃y [ D (x , y) ] ülesanded: Näidata  kahekohalise  predikaadi     P (x , y)   tõesuspiirkond: P (x , y)   ≡  x 2 —  y 2  =  0 vastus:   (x   =  y)    ∨  (x  =  - y) P (x , y)    ≡   (x   >  0)  →  (y  <  0) vastus:   (x   <  0)   ∨  (x   >  0) ∧ ( y  <  0) P (x , y)    ≡   (x   >  0)  ∧  (y  <  0) vastus:   (x    >  0)   ∧  ( y  <  0)


L O O G I K A S E A D U S E D Loogikaseadused  on  kuni  3me  operandiga   lihtsaimad   samaselt tõesed  
lausearvutusvalemid. Loogikaseadused  ei  ole  aksioomid.  Nende  kehtivus  tuleneb   loogikatehete      ¯ ¯    ∧      ∨     →     definitsioonidest. Olgu  3  lauset    A   B   C    mis  omavad  tõeväärtusi   0  või  1. assotsiatiivsus: A   ∧  B  ∧  C   =   (A  ∧  B)  ∧  C   =   A  ∧  (B  ∧  C) A   ∨  B  ∨  C   =   (A  ∨  B)  ∨  C   =   A  ∨  (B  ∨  C) kommutatiivsus: A   ∧  B    =   B  ∧  A A   ∨  B    =   B  ∨  A idempotentsus: A   ∧  A    =   A A   ∨  A    =   A neeldumine: A   ∧  (A  ∨  B)   =   A A   ∨  (A  ∧  B)   =   A distributiivsus: A   ∧  (B  ∨  C)   =   (A  ∧  B)  ∨  (A  ∧  C) A   ∨  (B  ∧  C)   =   (A  ∨  B)  ∧  (A  ∨  C) topelteituse seadus:         __         __
A      =   A De Morgani  seadused:       _______    __       __ A   ∧  B    =   B  ∨  A       _______    __       __ A   ∨  B    =   B   ∧  A Seadused konstantidega  0 ja 1 : A   ∨  0    =   A A   ∧  1    =   A A   ∨  1    =   1 A   ∧  0    =   0 Välistatud kolmanda seadus :      __ A   ∨  A   =   1  Vastuolu seadus :      __ A   ∧  A   =    0 Kontrapositsiooni seadus :      __ __ A   →  B   =   B  →  A Süllogismi seadus : [  (A   →  B)   ∧   (B  →  C) ]   →   (A  →  C)       __ A  → B   =  A  ∨  B                                 __ 1  → A   =  A A  → 0   =  A 0   →   A A   →   A A   →  1 A   ∧  (A  → B)   =  B


A   ↔  B   =   (A → B)   ∧  (B → A)  Loogikaseadused  võimaldavad  formaalsete  teisenduste  abil  saada  
lausetest (valemitest)  uusi,  esialgsega  loogiliselt  samaväärseid  lauseid. ülesanne:   On  eespool  olnud  lause: Kui McLaren on kiirem kui Ferrari ja vihma ei saja,
siis Häkkinen võidab sõidu: __     __     ( M    ∧   V )   →   H . . . ja  eespool olnud ühe teise lause vähemuudetud kuju:
Kui Häkkinen ei võida sõitu, siis Ferrari on kiirem
kui McLaren või vihma sajab:  __ H    →    ( M   ∨∨     V )   Kontrollida  nende  lausete  loogilist samaväärsust  ühe lause valemesituse  formaalse teisendusega  teise lause  valemiks. lahendus:  Teisendame  esimese  valemi  teiseks   Kontrapositsiooni   ja   De Morgani
seaduste  abil:   __       __ A   →  B   =   B  →  A ______ __    __ A   ∧  B      =   B  ∨  A ——————————————————————————————     __  __     ( M    ∧  V )   →   H   ________ __   __     __ H    →    ( M     ∧∧∧     V  )   __
H    →    ( M   ∨∨     V )  


H U L G A D Mõistel  "hulk"  pole  definitsiooni.  Hulk on fundamentaalne baasmõiste. ". . . . hulk  on  koosvaadeldavate  objektide (hulgaelementide) kogum . . . ." Hulk  koosneb  hulgaelementidest. ( Hulk  sisaldab  elemente ) Hulga  esitamine  Hulka  tähistatakse  suurtähtedega:        A B C             D Hulka  esitatakse: — tema  elementide  täieliku  loeteluna  loogsulgude  vahel: < või < ( komast  võib  loobuda,  kui  iga  hulgaelement  esitub  üksiku  tähemärgi  abil ) — tema  elementide  osalise  loeteluna, mis  esitab  mingit  regulaarset  
äratuntavat  seaduspärasust: < < < << < — üldise  avaldise  kaudu ,  mis  kehtib  kõigi  hulgaelementide  jaoks: < << < Kui  hulk  on  tähistatud  mingi  suurtähega , siis : V = < Z = < N = < HULKADE  VÕRDSUS : Hulgad  on  võrdsed ,  kui  nad  koosnevad  samadest  elementidest: <  =  { 5   1   3 } Hulgaelemendid  ei ole  hulgas  üksteise  suhtes  kuidagi  järjestatud. Hulgas  ei ole  korduvaid  elemente.   Igat  hulgaelementi  on  hulgas  "üks  eksemplar" :  {  1 3 3 5 5 5 } = { 1 3 5 } Hulgaelemendi   e  kuulumist  hulka  V  tähistatakse:   e  ∈ V Elemendi   d  mittekuulumist   hulka  V  tähistatakse:   d  ∉ V hulga sisaldumine  teises  hulgas: Hulk  A  on  hulga  B  osahulk  (alamhulk) :     A   ⊂  B      kui  hulga  A  iga element  on  samal  ajal  ka  hulga   B   elemendiks: A   ⊂  B     ↔     ∀x ( x  ∈ A   →   x  ∈ B )  Iga  hulk  on  iseenda  osahulgaks:     A   ⊂  A Kui  2  hulka  osutuvad  teineteise  osahulkadeks , siis  nad  on  võrdsed: ( A   ⊂  B     ∧    B  ⊂  A )    ↔    A  =  B     Venni  Diagrammid  Venni  diagramme  kasutatakse  hulkade  illustratiivseks  graafiliseks  
esitamiseks. Diagrammil  esitatakse  hulki  ringjoontega ,  mille  sees  võivad  olla  
näidatud  ka  hulgaelemendid. Hulka  mittekuuluvate  elementide  esitamiseks  on  kasutusele  võetud  
UNIVERSIAALHULGA   mõiste. 


Universiaalhulga     I    moodustavad  elemendid ,  mis kuuluvad   vaadeldavasse  hulka  ja  (ülejäänud) elemendid ,  mis ei kuulu  
vaadeldavasse hulka. Venni  diagrammil  esitatakse  universiaalhulka  ristkülikuna: Mistahes  vaadeldav  hulk  on  osa  universiaalhulgast:      A   ⊂  I  : Universiaalhulk  sisaldab  kõiki  antud  kontekstis  vaadeldavaid  elemente. Vokaalide hulga   V  =  { a  e  i  o  u  õ  ä  ö  ü }    vaatlemisel  sobib universiaalhulgaks  kõigi  tähtede  hulk : I  =  {  a b c d e f g h i j k l m n o p q r s t u v w x y z õ ä ö ü } Venni  diagramm  vokaalide  hulgale  V : I I A ÜHE  hulga  Venni  diagramm a e i o u õ ä ö ü b c d f g h j g h k l m n p q r s t v w x y z I V                      __ Hulka   A  mittekuuluvad  elemendid  moodustavad  hulga  A  täiendi    A .¯ näide :     __ Kui      I  = { e t k n r l p }    ja     A  = { l p }    siis     A  = { e t k n r }  " hulga  täiend "    ≡   " hulga  täiend  universaalhulgani " __ Hulga  A  täiendi    A  definitsioon:  __ A    =  {  x  |  x ∉ A  } A A Hulga  A   täiend   A I I I A B Venni  diagramm hulkadele  A  ja  B  KAHE  HULGA  Venni  diagramm KOLME  HULGA  Venni  diagramm erijuhul ,  kui    A  ⊂ B


TÜHI  HULK: Hulgas  võivad elemendid  ka  täielikult  puududa:   < Elementideta  hulka  nimetatakse  tühjaks.  Tühja  hulka  tähistatakse  ka   ∅ ehk:     ∅   Tühi hulk    ∅    on  iga  hulga  osahulgaks:      ∀A  ( ∅  ⊂ A ) Kuna  eelnevalt  oli  märgitud ,  et     A ⊂ A      siis  kehtib  iga  hulga  jaoks:      ∀A  ( ∅  ⊂ A   ∧    A ⊂ A ) ASTMEHULK   Mingi  hulga  A  astmehulgaks   2 A     ehk   P (A)   nimetatakse  selle  hulga   kõikide  osahulkade  hulka. näide: Olgu  antud    <   Sellise  hulga   A  astmehulk  on:  2 A    =  P (A)   =   <       { b }    { a b }   }   Hulga  <   astmehulk  on:  2 <    =  P (  { 0 , 1 , 2 } )  =  { {  }  {0}   {1}   {2}     {0 2}   {1 2}  { 0 1 2 } } LÕPLIKUD, LÕPMATUD, LOENDUVAD, MITTELOENDUVAD  HULGAD Hulk  on  lõplik ,  kui  ta  sisaldab  kindla  arvu  elemente.  <   on  lõplik  hulk. Lõpmatu  hulk  sisaldab  piiramatult (lõpmatult)  palju  elemente. <   ja    on  lõpmatud  hulgad. Hulk  on  loenduv ,  kui  tema  elementidele  saab  hakata  vastavaks  seadma
naturaalarve    < Iga  lõplik  hulk  on  alati ka  loenduv. Naturaalarvude  hulk   N  ise  ja  täisarvude  hulk   Z   on   lõpmatud  ja  loenduvad  hulgad.  Reaalarvude  hulk   R  on  lõpmatu  ja  mitteloenduv. ( Diskreetne  Matemaatika  ei tegele reaalarvudega ) HULGAARITMEETILISED  TEHTED On  1  unaarne  ja  4  binaarset   hulgaaritmeetilist  operatsiooni.
(binaarsetel  on  operandideks  on  2  hulka) —  hulkade  ÜHEND ∪ ( hulgaaritmeetiline  liitmine ) Kahe  hulga   A  ja  B   ühendisse     A   ∪  B     kuuluvad  elemendid ,  mis   kuuluvad  hulka   A  või  hulka  B : A   ∪  B  =  {  x  |  x ∈ A   ∨   x ∈ B  } —  hulkade  ÜHISOSA ∩ ( hulgaaritmeetiline  korrutamine ) Kahe  hulga   A  ja  B   ühisosasse     A   ∩  B     kuuluvad  elemendid ,  mis  kuuluvad  hulka   A  ja  samal ajal ka  hulka  B : A   ∩  B  =  {  x  |  x ∈ A    ∧   x ∈ B  } I  A  A ∪ B B ühend I  A  A ∩ B B ühisosa


—  hulkade  VAHE \ ( hulgaaritmeetiline  lahutamine ) Kahe  hulga   A  ja  B   vahesse     A   \  B     kuuluvad  elemendid ,  mis   kuuluvad  hulka   A  ja  ei kuulu  hulka  B : A   \  B   =  {  x  |  x ∈ A    ∧   x ∉ B  }  " A  ilma  B-ta " —  hulkade   SÜMMEETRILINE  VAHE ∆ Kahe  hulga   A  ja  B   sümmeetrilisse vahesse     A   ∆  B     kuuluvad   elemendid : A   ∆  B   =  { x  | ( x ∈ A    ∧   x ∉ B )  ∨  ( x ∈ B   ∧   x ∉ A ) }  ——————————————————————————————————————— Kui    A   ∩  B  =  ∅  ,  siis   A   ja    B   on  mittelõikuvad.  näide:      ja   <  on  mittelõikuvad  hulgad.  I  A  A B vahe B \ I  A  A B B sümm. vahe ∆ Lõpliku  hulga     A    võimsuseks     | A |   nimetatakse  tema  elementide   arvu .  Hulga     V  =  { a  e  i  o  u  õ  ä  ö  ü }    võimsus   | V |  =  9 GRASSMANI  VALEMID: Kahe hulga ühendi    A   ∪  B    elementide arv    | A  ∪  B |  avaldub : | A   ∪  B |   =   | A |  +  | B |  -  | A  ∩  B |  Kahe hulga ühisosa    A   ∩  B    elementide arv    | A  ∩  B |  avaldub : | A   ∩  B |   =   | A |  +  | B |  -  | A  ∪  B |    Kolme hulga ühendi    A   ∪  B   ∪  C   elementide arv    | A  ∪  B   ∪  C | avaldub : | A   ∪  B   ∪  C |   =   | A |  +  | B | +  | C |  -  | A  ∩  B | -     -   | A   ∩  C |  -  | B  ∩  C |  +  |  A  ∩ B  ∩  C | HULGAALGEBRA  PÕHISEOSED A     ∪  ∅      =   A A     ∩ ∩    Ι      =   A A     ∪   Ι       =   I A     ∩ ∩    ∅      =    ∅ __     __ __ A     ∪  A       =   I A   =   A     __      __ A     ∩ ∩    A       =    ∅ I      =    ∅ A    ∪ A     =  A A    ∩ ∩  A      =  A


kommutatiivsus: A    ∪ B      =  B     ∪ A A    ∩ ∩  B      =  B    ∩ ∩  A assotsiatiivsus: ( A    ∪ B )     ∪ C     =  A    ∪ ( B     ∪ C ) ( A    ∩ ∩  B )     ∩ ∩  C     =  A    ∩ ∩  ( B     ∩ ∩  C ) distributiivsus:  A    ∩ ∩  ( B     ∪ ∪  C )     =  ( A    ∩ ∩  B )     ∪ ∪   ( A     ∩ ∩  C )  A    ∪ ∪  ( B     ∩ ∩  C )     =  ( A    ∪ ∪  B )     ∩ ∩   ( A     ∪ ∪  C ) neeldumine:  A    ∩ ∩  ( A     ∪ ∪  B )     =   A   A    ∪ ∪  ( A     ∩ ∩  B )     =   A        _    _ A  ∩ ∩  ( A ∪ ∪  B )   =  A ∩ ∩  B    A  ∪ ∪  ( A ∩ ∩  B )   =  A ∪ ∪  B kleepimine:                   __                 __ A =  ( A ∪ ∪  B )  ∩  ( A ∪ ∪  B ) A =  ( A ∩ ∩  B )  ∪  ( A ∩ ∩  B ) de Morgani seadused  ( 2he hulga jaoks):   ______     __     __ ______     __     __ A    ∪ B  =  A     ∩ ∩  B A    ∩ ∩  B  =  A     ∪ ∪  B muud  hulgaaritmeetilised  asendusseosed:           __   A   \  B   =   A     ∩ ∩  B   A    ∆  B   =   ( A    \  B )  ∪  ( B    \  A )       A    ∆  B   =   ( A    ∪ ∪  B )  \  ( B    ∩ ∩  A )   __ Hulgatehete  prioriteet:     ∩ ∪ \  ∆ Cantori normaalkujud  (CNK): Hulgaavaldise  Cantori  normaalkuju  on  ühendite ühisosa  või  ühisosade
ühend,  kus  osalevad  üksikud  hulgad  või  nende  täiendid. Lihtsaim  (vähima arvu hulgatähistega)  CNK on minimaalne normaalkuju. näide: ____________   __ Teisendada  hulgaavaldis        (A    ∆  B  )  \  C      Cantori  normaalkujule . ____________    ________________________    __     __      __    __ (A    ∆  B )  \  C  =  (A     \  B )    ∪ ( B \ A )     ∩    C    =      ___________________________       __      __    __ =  (A    ∩ ∩  B )     ∪     ( B    ∩ ∩  A )     ∩    C     =     ________         ________       __      __ =  (A    ∩ ∩  B )      ∩ ∩     ( B    ∩ ∩  A )       ∪    C      =   __    __ =   (  A     ∪ ∪  B )      ∩ ∩     ( B    ∪ ∪  A )      ∪    C      =   __         __     __  __ =   ( A    ∩  B )    ∪  ( B   ∩  B )     ∪  ( A   ∩  A )     ∪    ( B    ∩  A ) ∪    C    =   __      __ =   (  A     ∩ ∩  B )     ∪     ( B    ∩ ∩  A )  ∪     C


teine  teisendusvõimalus:  ____________     _________________________      __ __ __  __ (A    ∆   B )  \  C  =  (A     ∪ ∪  B )    \ ( A  ∩ ∩  B )       ∩      C   =      ____________________________     _______    __ __ __ =  (A    ∪ ∪  B )     ∩  ( A  ∩ ∩  B )      ∩     C    =       ________    __ __ =  (A    ∪ ∪  B )      ∪  ( A ∩ ∩  B )      ∪    C    =  __ __ =  (  A     ∩ ∩  B )     ∪  ( A ∩ ∩  B )      ∪    C ( minimaalne CNK ) Cantori  täielik  normaalkuju  sisaldab  igas  ühendis või  ühisosas  kõiki  
avaldises osalevaid  hulki. Avaldiseliikmes  puuduvaid  hulki  saab  lisada  kleepimisseadust  
rakendades:                   __                 __ A =  ( A ∪ ∪  B )  ∩  ( A ∪ ∪  B ) A =  ( A ∩ ∩  B )  ∪  ( A ∩ ∩  B ) A B C A B  ∆ C ( ) \ näide: Teisendame  eespool  saadud  minimaalse Cantori  normaalkuju  täielikuks  
CNK-ks:       __  __ __ (  A     ∩ ∩  B )    ∪  ( A ∩ ∩  B  )      ∪    C   =    (  A     ∩ ∩  B  ∩  C )     ∪     __ __   __  __      __ ∪ ( A     ∩ ∩  B  ∩  C )    ∪ ( A ∩ ∩  B ∩ C )      ∪  ( A ∩ ∩  B  ∩  C )    ∪      __    ∪ ∪  ( C  ∩  A )    ∪ ∪  ( C  ∩  A )   =       __  =   .  .  .  .  .  .   ∪ ∪  ( C  ∩  A    ∩  ∩  B )    ∪ ∪  ( C  ∩  A    ∩  ∩  B )    ∪ ∪   __   __ __    ∪  ∪   ( C  ∩  A     ∩  ∩  B )   ∪  ∪  ∪   ( C  ∩  A     ∩  ∩  B )   =            __ __     __  __ = (  A     ∩ ∩  B  ∩  C )  ∪ ( A     ∩ ∩  B ∩  C  )    ∪ ( A ∩ ∩  B ∩ C )  ∪        __  __       __     __ ∪  ( A ∩  ∩   B  ∩  C )    ∪    ( A ∩ B   ∩ ∩  C )    ∪ ∪  ( A  ∩ B  ∩ ∩  C ) 


Hulkade  RISTKORRUTIS  ehk  OTSEKORRUTIS × Kahe hulga ristkorrutis    A  × B  on  järjestatud  paaride   < a, b >  hulk,  kus  paari esimene element  on  esimeseks teguriks olevast hulgast  ja  paari
teine element  on  teiseks teguriks olevast hulgast: A  × B  =  { < a, b >  |  a ∈ A   ∧   b ∈ B } näide: A  =  { 1, 2, 3 } B  =  { a, b } A  × < Elementide  (paaride) arv  ristkorrutises: |A  × B|  =  |A| • |B| Hulga    A   otseruut    A  × A   on  hulga  otsekorrutis  iseendaga: A  × A  =  A2  =  { < a, b >  |  a ∈ A   ∧   b ∈ A }  näide: Kui    A  =  { 1, 2 } ,  siis    A  × A  =  {  < 1, 1 >  < 1, 2 >  < 2, 1 >  < 2, 2 >  } Ristkorrutis  pole  kommutatiivne:    A   × B  ≠  B  × A Ristkorrutistehte  võib  defineerida  ka  suuremale  teguritearvule. 3-me  hulga    A   B   C   ristkorrutis: A  × B  × C  =  { < a, b, c >  |  a ∈ A   ∧   b ∈ B   ∧   c ∈ C } n  hulga    A   B   C  . . .  N   ristkorrutis: A ×B×C× ... ×N  =  { < a, b, c, ... n > | a∈A  ∧  b∈B  ∧  c∈C ∧ . . . ∧ n∈N }


VASTAVUSED Vastavus  seab  ühe  hulga  elementidele  vastavaks   teise  hulga  mingeid  
elemente. Olgu  õpilaste  hulk:     A  =    < ja võimalike hinnete  hulk:    B  =   Nende  6  õpilase  hindamisel  luuakse  vastavus   hulgast   A  hulka  B. Väikeste  hulkade  korral  on  vastavuse  kõige  illustratiivsem  esitus
vastavuse diagramm : Kui  vastavus     ϕϕ  seab  hulga  A  elementidele  vastavaks  hulga   B    elemente  (ehk   ϕ  on   "hulgast  A  hulka   B  " ) ,  siis  märgime : ϕ :    A  →  B A  on  sellisel juhul  vastavuse  lähtehulk  ja  B  on  sihthulk .
Vastavuse matemaatiliseks mudeliks (esituseks)  on  järjestatud paaride hulk
. Jüri 5 Mari Juhan Jaan Kati Mati 4 3 2 1 0 ϕ : Α Β Kuna  kahe  hulga  otsekorrutis    A  × B   koosneb  nende elementide kõikvõimalikest järjestatud  paaridest   < a, b > ,  siis defineeritaksegi vastavust  lähtehulga ja sihthulga  otsekorrutise  osahulgana: Vastavus      ϕ :  A → B   on hulk      ϕ  ϕ   ⊂⊂   A × B Eelnev  näitevastavus    ϕ  esitub  seega  järjestatud  paaride  hulgana : ϕ  =  < Kui    ϕ  seab  a-le  vastavaks  b   ehk     < a, b >  ∈ ϕ   siis  võib  ka   tähistada:   a    ϕ  b   Vastavuse    ϕ : A → B   määramispiirkonna    D (ϕ)   moodustavad   vastavuses osalevad  lähtehulga  elemendid: D ( ϕ)  =   <  ⊂  A Vastavuse    ϕ : A → B   muutumispiirkonna    R (ϕ)   moodustavad   vastavuses osalevad  sihthulga  elemendid: R ( ϕ)  =   <   ⊂  B      __ Vastavuse    ϕ : A → B   täiendi    ϕ   moodustavad  järjestatud  paarid  < a, b >   ∈  A  × B    mis  ei  kuulu  vastavusse  ϕ : __
  ϕ  =   {  , b> ∈ A×B |   < a, b >  ∉ ϕ  ϕ )) }  ⊂  A × B __
  ϕ  =  ( A×B ) \  ϕ   __ |  ϕ  |  =   | A × B |  —  | ϕ | Vastavuse    ϕ : A → B   pöördvastavus    ϕ-1   seab  sihthulga   B elementidele  vastavaks  lähtehulga   A  elemente: ϕ-1  =   {  , a> ∈ B×A |   < a, b >  ∈ ϕ  ϕ )) }  ⊂  B × A


| ϕ-1 |  =   | ϕ | Vastavuste    ϕ 1 : A → B   ja   ϕ2 : B → C    kompositsioon  ehk   liitvastavus     ϕ 1 •  ϕ2    on  vastavus,  mis  seab  hulga   A   elementidele   vastavaks  hulga    C    elemente  "üle hulga  B  elementide": ϕ 1• ϕ2 = { , c>∈A×C |  | ∃  ∃b∈∈ΒΒ(< a, b >∈ϕ 1  ∧ < b, c >∈ϕ2 )} ⊂ A × C ϕ 1 • ϕ2  =  { < a, y >   < a, z >   < d, p > } Kompositsioonitehet nimetatakse  ka  vastavuste  korrutamiseks. Vastavuste kompositsioon on assotsiatiivne:    (ϕ 1 •  ϕ2 ) • ϕ3 = ϕ1 • (ϕ2 • ϕ3 ) Kompositsiooni pöördvastavus  on  pöördvastavuste  kompositsioon: (ϕ 1 •  ϕ2 ) -1   =    ϕ 2  -1 •   ϕ 1  -1  a 5 x b c d e f 4 y 3 z 2 p 1 q 0 ϕ : ϕ : A B C 1 2 VASTAVUSTE  LIIGID Vastavus    ϕ ⊂ ⊂  A  × B   on  kõikjal  määratud ,  kui  D (ϕ)  =  A Vastavus    ϕ ⊂ ⊂  A  × B   on  kõikjale  määratud ,  kui  R (ϕ)  =  B Vastavus    ϕ ⊂ ⊂  A  × B   on  ühene ,  kui  igale  määramispiirkonna   elemendile  vastab  täpselt  üks  muutumispiirkonna  element: ∀a∈D(ϕ) ∃!b∈R(ϕ) [ < a,b > ∈ ϕ ] a 5 b c d e 4 3 2 1 0 ϕ : Α Β KÕIKJAL  määratud vastavus a g f 5 b c d e 4 3 2 1 0 ϕ : Α Β KÕIKJALE  määratud vastavus


Ühese  vastavuse  korral  kehtib:
ϕ-1   •  ϕ  =  { < b, b > | b ∈ B } Kõikjal määratud ühest  vastavust  nimetatakse  funktsiooniks. Kui   ϕ  on  funktsioon, siis   < x, y > ∈  ϕϕ   esitamiseks  võib  kasutada   tähistust:      ϕϕ (x)  =  y Kui  funktsiooni   ϕ  korral   ∃a∈A[a ∉ D(ϕ)]  siis  ϕ  on  osaliselt   määratud  funktsioon. Kui  funktsiooni    ϕ : A → B   (ehk  ϕ  ϕ  ⊂⊂  A×B )  määramispiirkond  D( ϕ) = A ,  siis selle rõhutamiseks võib funktsiooni   ϕ  nimetada ka   täielikult määratud  funktsiooniks. (vaikimisi:  "funktsioon"   ≡  "täielikult määratud funktsioon" ) Vastavus    ϕ : A → B   on   üks-ühene ,   kui ta on ühene  ja muutumispiirkonna  iga element  vastab  täpselt  ühele  määramispiirkonna
elemendile:
∀a,b∈D(ϕ) [ϕ(a) = ϕ(b)   →    a = b] ehk ∀a,b∈D(ϕ) [a ≠ b   →    ϕ(a) ≠ ϕ(b)] a g f 5 b c d e 4 3 2 1 0 ϕ : Α Β ÜHENE   vastavus FUNKTSIOONIDE  LIIGID Kõikjale  määratud  funktsioon  on  sürjektsioon: ∀b∈B ∃a∈A [ϕ(a) = b ] a 5 b c d e 4 3 6 2 1 ϕ : Α Β ÜKS-ÜHENE  vastavus a 5 b c d e 4 2 ϕ : Α Β sürjektsioon


Üks-ühene  funktsioon  on  injektsioon: Kui     ϕ : A → B  on injektsioon , siis  | A | ≤ | B | Kõikjale  määratud  üks-ühene  funktsioon  on  bijektsioon: Kui     ϕ : A → B  on bijektsioon , siis   | A | = | B | a 5 b c d 4 3 6 2 1 ϕ : Α Β injektsioon a 5 b c d e 4 3 6 1 ϕ : Α Β bijektsioon Funktsioonid S ü r j e k t s i o o n i d I n j e k t s i o o n i d Bijektsioonid Funktsioonide  liigitumine küsimus: On vastavus    ϕ : A → B  , kus  lähtehulk   A  on  õpilaste   hulk  ja  sihthulk  on  hinded:   B =  {0, 1, 2, 3, 4, 5}.    ϕ näitab  eksamil saadud  hinnet.  Millistel  tingimustel  on    ϕ : —  osaliselt  määratud  funktsioon? —  täielikult  määratud  funktsioon? —  sürjektsioon? —  injektsioon? —  bijektsioon? BINAARSUHTED  (KAHENDSUHTED)  e.  RELATSIOONID Binaarne relatsioon  on  vastavuse  erijuht,  kus  nii lähtehulk  kui ka  
sihthulk  on üks ja sama hulk: ( "Relatsioon  hulgal  M" ) D ( ϕ)  ⊂  M R ( ϕ)  ⊂  M    ϕ  ⊂ ⊂   M  × M  Relatsiooni  tähistatakse  eelistatult  tähega    R :        R    ⊂⊂   M × M  Kui   R  on  binaarne relatsioon  ja   , b>  ∈ R ,  siis  üteldakse, et  "a ja b on relatsioonis "  ja  tähistatakse:  a  R b    ≡   ,b>∈R Hulka, millel  relatsioon  on  määratud  (siin: M), nimetatakse  binaarsuhte   alushulgaks. Kuna  relatsioonid  on  vastavused, siis  kehtivad  ka nende jaoks  kõik  
vastavuste  juures tuntud mõisted:  täiend,  pöördvastavus, kompositsioon: __ R  täiend  R  =   <  ⊂ M × M __   R  =  ( M ×M ) \  R R  pöördvastavus   R -1  =  < R  kompositsioon iseendaga: R  •  R  =  R 2   R  •  R   •  R  =  R 3 R 1   =  R


Relatsioonide  ESITUSVIISID Olgu  relatsiooni  alushulk    M  =   <   millel  on määratud  mingi  binaarsuhe   R Relatsioon  võib  olla  esitatud: 1.   järjestatud  paaride  hulgana:      R  =   <   R  =   < Kui  alushulga  elemendid  on  seotud  vastavuspaarideks  mingi  reegli  
(tunnuse või  tingimuse)  abil,  siis seda  reeglit  nimetatakse   relatsioonikriteeriumiks.    ( binaarsuhet moodustav  reegel ) Eelmises  näiterelatsioonis  on  alushulga elemente  paarikaupa
kokkusiduvaks  tunnuseks  jagumine — iga  alushulga  element  on  pandud
vastavaks  (ehk ta "on relatsioonis")  selliste alushulga elementidega, millega ta
jagub :  a mod b = 0 2.   ( orienteeritud ) graafina: Graafi  tippudeks  on  alushulga  elemendid   ja  graafi  iga  
kaar  esitab  ühte  järjestatud  paari   < a, b > 2 3 4 5 6 R: 3.   naabrusmaatriksiga: 2 3 4 5 6 2 1 0 0 0 0 3 0 1 0 0 0 R  = 4 1 0 1 0 0 5 0 0 0 1 0 6 1 1 0 0 1 Relatsiooni  esitab  kahendtäitega  ruutmaatriks. Ühikrelatsioon   E  ehk  binaarsuhte  diagonaal  on  binaarsuhe,  mis seab igale alushulga  elemendile  vastavaks  ainult  selle elemendi enda:   E  =   < | E |  =   | M | Eelneva näidisalushulga    M  =   <   jaoks  E =  < E -1      =   E  Kui   E  ja  R  on  sama  alushulga   M   relatsioonid,  siis nendevaheline   kompositsioon (korrutis): E    •  R    =    R  •  E    =   R


Relatsioonide  OMADUSED Relatsioonidel  on  6  omadust, mida  tähistatakse    α 1  α2  α3  α4  α5  α6  1. refleksiivsus  (  α 1 ) :   ∀a∈M (< a, a >∈R ) Kui   R  on  refleksiivne, siis   E    ⊂⊂   R 2. antirefleksiivsus  (  α 2 ) :   ∀a∈M (< a, a >∉R ) Kui  relatsioon  pole  ei refleksiivne  ega  antirefleksiivne, siis nimetatakse  
teda  mitterefleksiivseks. 2 3 4 5 6 refleksiivne binaarsuhe R: 2 3 4 5 6 antirefleksiivne binaarsuhe R: 3. sümmeetria  (  α 3 ) :  ∀a,b∈M [(a ≠ b) ∧ < a, b >∈R →  < b, a >∈R] Kui   R  on  sümmeetriline, siis    R-1   =   R  4. antisümmeetria (  α 4 ) : ∀a,b∈M [(a ≠ b) ∧ < a, b >∈R →  < b, a >∉R] Kui   R  on  antisümmeetriline, siis   R   ∩  R-1   ⊂ ⊂   E Kui  relatsioon  pole  ei sümmeetriline  ega  antisümmeetriline, siis
nimetatakse  teda  mittesümmeetriliseks. 2 3 4 5 6 sümmeetriline binaarsuhe R: 2 3 4 5 6 antisümmeetriline binaarsuhe R:


5. transitiivsus (  α 5 ) :   ∀a,b,c∈M   [(a ≠ b) ∧  (b ≠ c) ∧ (a ≠ c) ∧  (a R b) ∧ (b R c) →  (a R c)] Kui   R  on  transitiivne, siis  R  • R   ⊂ ⊂   R 6. antitransitiivsus (  α 6 ) :   ∀a,b,c∈M   [(a ≠ b) ∧  (b ≠ c) ∧ (a ≠ c) ∧  (a R b) ∧ (b R c) →  (a R  ¯ ¯  c) ] Kui  relatsioon  pole  ei transitiivne  ega  antitransitiivne,  siis nimetatakse  
teda  mittetransitiivseks. Kõik 3 omadust ja nende 3 vastandomadust on vastastikku  teineteist
välistavad:  ühe omaduse kehtimine välistab ta antiomaduse kehtimise. Omaduse mittekehtimine  ei tähenda ta vastandomaduse kehtimist. 2 3 4 5 6 transitiivne binaarsuhe R: 2 3 4 5 6 antitransitiivne binaarsuhe R: Relatsiooni   R  kaugus  d   omaduseni   α i  :     d (R , αi  )   on  järjestatud   paaride  arv, mis tuleb  relatsiooni lisada  või  sellest eemaldada ,  et omadus   α i   kehtima  hakkaks. ülesanne:   Alushulgal    M  =   <  on  määratud  relatsioon  R =  < Leida    R  kaugus  kõigi  omadusteni     α 1  α2  α3  α4  α5  α6  ——————————————————————————————————————————————   d(R ,  α 1  )  =  1   d(R ,  α 2  )  =  3   d(R ,  α 3  )  =  2   d(R ,  α 4  )  =  2   d(R ,  α 5  )  =  3   d(R ,  α 6  )  =  0 —————————————————————————————————————————————— ^ Relatsiooni   R  transitiivseks  sulundiks     R    nimetatakse vähima   paaridearvuga  transitiivset relatsiooni,  mis sisaldab  endas  alamhulgana  
relatsiooni    R . Transitiivne  sulund  avaldub    R   astmete  ühendina: Kui alushulgas   |M|  =  n siis ^ i = n-1 R =  R   ∪  R2  ∪  R3  ∪ . . . ∪  Rn-1   =   U Ri    ^ i = 1 Kui    R  on  juba  transitiivne,  siis   R  =  R ——————————————————————————————————————————————    ülesanne:   Alushulgal    M  =   <  on  määratud  relatsioon R =  < Leida    R  transitiivne  sulund. —————————————————————————————————————————————— ^
R =  <   ^ |R| =  11


JÄRJESTUSSUHTED OSALINE  järjestussuhe Osaline  järjestussuhe  on  relatsioon, mis on  antisümmeetriline  ja  
transitiivne. Kui  osaline  järjestussuhe  on samas ka antirefleksiivne ,  siis ta on range osaline järjestussuhe  (   <  ) või Kui  osaline  järjestussuhe  on samas ka refleksiivne ,  siis ta on mitterange osaline järjestussuhe  (   ≤  ) Kui  R on  järjestussuhe  hulgal  M ,  siis "relatsioon R järjestab hulga M". Eespool  kasutatud  näiterelatsioon   R  =   < on  samuti  (mitterange) osaline järjestussuhe, kuna ta on refleksiivne :  (arv jagub iseendaga:  < a, a >  ∈ R ) antisümmeetriline :  (kui  a jagub b-ga ,   siis   b ei jagu a-ga:    < a, b >  ∈ R        < b, a > ∉ ∉  R ) transitiivne :  (kui   a jagub b-ga    ja    b jagub c-ga ,  siis  a jagub c-ga ) Järjestussuhte relatsioonikriteeriumit  võib nimetada ka    järjestuskriteeriumiks . Kui  alushulga  moodustuvad  elemendid, mille  jaoks on defineeritud võrdlemistehted   "suurem kui"   ( "väiksem kui" )     >     ≥   ( <    ≤  )  siis   relatsioonid     R  =   <    R  =   <    R  =   <    R  =   <  osutuvad  järjestussuheteks. Kui  alushulga  elementideks on hulgad  ja relatsioonikriteeriumiks valida   ⊂ siis  moodustuv  binaarsuhe  on  samuti  järjestussuhe.  (Teatavasti pole hulkade jaoks defineeritud võrdlustehteid     >     ≥    <    ≤  ) näide: Olgu alushulgaks hulga   <  astmehulk  2 <   =  < {3} {4} {3,4} }  =  M Koostame hulgal    M  relatsiooni  R  =  < R  =   <, {3} >    <   < , {4} >      <   < , {3,4} >      <   < , {3,4} >    <   < , {3,4} >  } Moodustunud relatsioon on (range) järjestussuhe, kuna ta on antisümmeetriline ja transitiivne  ning samas on ta  osaline järjestussuhe , kuna  alushulk    M sisaldab ka elementidepaari, mis pole selle relatsiooni järjestuskriteeriumiga     ⊂   võrreldavad: <   ⊄ {4}   ega   {4} ⊄ {3}    ehk < {3}, {4} >  ∉ ∉ ∉ M    ja    <   < , {3} >  ∉ ∉ ∉ M Relatsiooni ennast võib samuti tähistada järjestatud paariga, mille
komponentideks on relatsiooni  alushulk  ja  järjestuskriteerium. Eelnev näiterelatsioon oleks järjestatud paarina esitatult    < 2 <,  ⊂     > . TÄIELIK  järjestussuhe Kui alushulga mistahes 2 elementi  on järjestatavad  (ehk  selle relatsiooni
järjestuskriteeriumi abil võrreldavad):
∀a,b∈M   [  (a  ≤ b)   ∨     (a  ≥ b)  ] siis sellist relatsiooni nimetatakse  lineaarseks  järjestuseks. näide:  Täisarvude hulk  Z   järjestuskriteeriumiga   ≥  (või  ≤ ) osutub   lineaarseks  järjestuseks    < Z,   ≤  >  Kui lineaarselt järjestatud hulgas leidub täpselt 1 vähim element:
∃!m∈M ∀a∈M   [  m  ≤ a ] siis on hulk täielikult järjestatud  (täielik järjestussuhe). näide:  Naturaalarvude hulk  N   järjestuskriteeriumiga   ≥  (või  ≤ ) osutub täielikuks  järjestuseks    < N,   ≤  >  , sest seal on olemas lineaarjärjestus ja selles hulgas leidub element (naturaalarv  0) , mis on väiksem mistahes
teisest naturaalarvust. ( Järjestuskriteeriumite   ≥  ja  ≤  asendamisel teineteisega relatsiooni omadused ei muutu. Muutub ainult komponentide järjestus järjestatud
paarides: < a, b > asendub  < b, a >-ga )  Huvipakkuvamad järjestussuhted on  osalised  järjestused.


Hasse  diagrammid Hasse diagramm on osalise järjestussuhte illustratiivne graafiline esitus. Diagramm koosneb sihipäraselt paigutatud ja joontega ühendatud alushulga
elementidest.  Relatsiooni  R  Hasse diagramm joonistatakse järgnevaid
nõudeid arvestades: — Kui  ( a   ≤  b     )  ja   ( a  ≠   b     ) ,  siis  b     paigutatakse diagrammil  kõrgemale kui  a  ja  nad ühendatakse omavahel joonega. — Transitiivseks osutuvad jooned jäetakse diagrammile märkimata. Täpsustame, et teine tingimus välistab osa jooni, mis esimese tingimuse kohaselt
kuuluksid samuti diagrammilekandmisele. Transitiivsust esitavad jooned ei lisaks
enam osalise järjestuse kohta uut infot. näide:  Eelnev osalise järjestuse näide   < 2 <,  ⊂     >  omab järgnevat Hasse diagrammi: Ära on jäetud joon <  ja  < vahel, kuna ka
olemasolevad jooned näitavad , et   <  ⊂ < ehk  < { }, {3, 4} >  ∈ R näide:  Koostame  Hasse diagrammid  kahele   8-elemendilisel alushulgal määratud osalisele järjestusele:    < 2 <,   ⊂     >   ja    < < 3,   <      >Hasse diagramm relatsioonile 2   , < ⊂ < < < < < 111 011 001 010 100 000 101 110 < < < Hasse diagramm Hasse diagramm relatsioonile relatsioonile 2   , < 3 ⊂ <


POSITSIOONILISED    ARVUSÜSTEEMID Igal positsioonilisel arvusüsteemil on  täisarvuline  alus  p   Arvujärgud: . . . .  a 5    a4   a3   a2    a1    a0   a-1   a-2   a-3   a-4  . . . .  a i  . . . .  Igal järgul  a   i  on kaal   p i   :        p   i  =  p i   Järgukaalud: . . . .  p 5   p4   p3   p2   p1   p0   p-1  p-2  p-3  p-4  . . . .  pi   . . . . Kui alus  p = 10 ,  siis on  kümnendsüsteem ,  kus järkude kaaludeks on:     . . . .  10 3  102  101 100  10-1 10-2 10- 3  . . . .       . . . .  100    10    1     0.1   0.01   . . . . Igas järgus   a   i   saab olla   p  erinevat järguväärtust. Kui    p = 10 ,   siis   a   i   ∈ ∈   Mistahes positsioonilises arvusüsteemis avaldub arvu  väärtus N: N  =   . . .  +  a 3⋅ p 3  +  a 2⋅ p 2  +  a 1⋅ p 1  +  a 0⋅ p 0  +  a -1⋅ p -1  +  a -2⋅ p -2  +  . . . 123  10   =     1 ⋅ 100   +   2 ⋅ 10   +   3 ⋅ 1   =   123 10 Seega  täisosa ees  ja murdosa järel  asuvad  '0'-d ei mõjuta arvu väärtust: 123.45  10   =    . . . . 00000123.450000000 . . . . 10  Mõiste  arvu väärtus  on eranditult seotud ainult 10ndsüsteemiga. "Väärtuse leidmine"  ja  "10ndsüsteemi teisendamine" on sünonüümid. Üleskirjutatud arvu süsteemikuuluvuse täpsustamiseks lisame talle süsteemi
näitava indeksi:    372 8   on 8ndsüsteemne arv väärtusega  250:  372 8   =  3 × 8 2   +   7 × 81   +   2 × 80   =   250 10 kõrgemad  järgud                            madalamad  järgud täisosa     murdosa KAHENDSÜSTEEM Kahendsüsteem on lihtsaim positsiooniline arvusüsteem: p  =  2   a   i   ∈ ∈   2ndsüsteemi järgukaalud:    . . .  2 5    24    23    22    21    20    2-1    2-2    2-3  . . .      32     16      8       4       2       1      0.5   0.25  0.125 Järgnevalt on loetletud kahendarvud kuni 63-ni: 0 2 =  010 10000 2 =1610 100000 2 =3210 110000 2 =4810 1 2 =  110 10001 2 =1710 100001 2 =3310 110001 2 =4910 10 2 =  210 10010 2 =1810 100010 2 =3410 110010 2 =5010 11 2 =  310 10011 2 =1910 100011 2 =3510 110011 2 =5110 100 2 =  410 10100 2 =2010 100100 2 =3610 110100 2 =5210 101 2 =  510 10101 2 =2110 100101 2 =3710 110101 2 =5310 110 2 =  610 10110 2 =2210 100110 2 =3810 110110 2 =5410 111 2 =  710 10111 2 =2310 100111 2 =3910 110111 2 =5510 1000 2 =  810 11000 2 =2410 101000 2 =4010 111000 2 =5610 1001 2 =  910 11001 2 =2510 101001 2 =4110 111001 2 =5710 1010 2 =1010 11010 2 =2610 101010 2 =4210 111010 2 =5810 1011 2 =1110 11011 2 =2710 101011 2 =4310 111011 2 =5910 1100 2 =1210 11100 2 =2810 101100 2 =4410 111100 2 =6010 1101 2 =1310 11101 2 =2910 101101 2 =4510 111101 2 =6110 1110 2 =1410 11110 2 =3010 101110 2 =4610 111110 2 =6210 1111 2 =1510 11111 2 =3110 101111 2 =4710 111111 2 =6310 Kuna kahendarvudes ei leidu suuremaid järguväärtusi kui 1, siis
kahendarvude korral arvu väärtust arvutav avaldis lihtsustub  nende järgukaalude summeerimiseks, kus asub järguväärtus 1: 101011 2  =   1  × 2 5   +   0  × 2 4   +   1  × 2 3   +   0  × 2 2  +  1  × 2 1  +   1  × 2 0    =  =   32   +   8   +   2   +  1     =   43 10


                                     Kahendkoodidega seotud MÕISTED G 3               Q
        Q     Q
QlLGH           
.DKHQGYHNWRULO     !   
"  NDKHQGDUYXVW      MlUJXNDDOX #                NDKHQGDUYXQD                      G  !        $       
% Q     Q  
QlLGH           G            3   ∈  &  $                  
       $      ' (              <
)        $                       *   G        "!      $               
+     3   $                 
 %    ^   <  4-järgulist vektorit ja intervallil on  #  $ %  järku ja   järk. Intervalli kompaktseks esituseks sobib kasutada            & $                      &  ,          & &  
^     ` $  & &
"         &   
^   ` $   &  G 3'(('   ) *  '    3     + ,  -3 võimsusega 3 : _ +, -3 _ $ 3  -    + ,  -   -     + ,  - $ _+, - _ $  $    ./01
,        ( '
  ! ≥  ≤  +                    
/         
3   [[    [3 ∈+ ,  - 3 ja \ \    \3 ∈+ ,  - 3    !   
2 [[    [3 ≤ \\    \3    ↔ ∀L ∈+      -  [L ≤ \L 


 
! 
 
! 
! 
          +            !    &    )        0    /$           + ,  -3   "!"        + ,  -3 . ) Osalist järjestussuhet esitavad  
hulkadel + ,  -  + ,  -  
Hasse diagramm Hasse diagramm relatsioonile relatsioonile    


LOOGIKAALGEBRA  (Boole'i algebra) Loogikaalgebra  koosneb loogikaväärtuste hulgast  < , millel on defineeritud  3 elementaarset loogikatehet:  unaarne tehe  inversioon  ja
binaarsed tehted  konjunktsioon  ja  disjunktsioon.  Loogikaalgebra koosseis
on seega: <  < ;      ¯ ∧ ∨  > Kõik 3 loogikatehet on juba eelpool lausearvutuse juures defineeritud ja kõik
lausearvutuses kehtiv kehtib ka loogikaalgebras. Muutuja  x i  on  loogikamuutuja , kui ta saab omandada väärtusi ainult hulgast  <.       x i ∈  < Numbrimärkidena  0  ja  1   esitatud loogikaväärtusi nimetatakse ka   "konstant 0"  ja  "konstant 1" , et rõhutada nende erinevust  muutujatest  x i . Loogikaavaldis  on  loogikamuutujaid  x i  ,  konstante  0   1  ja  tehtemärke sisaldav kooslus, mis tema muutujate   x i  väärtustamisel omandab samuti loogikaväärtuse   0  või  1  . Loogikaavaldis sarnaneb lausearvutuses tuntud  lausearvutusvalemile  ning
ta defineeritakse analoogiliselt: — loogikamuutuja   x i   ja  konstandid   0   1  on  loogikaavaldised      __ — kui  A  on loogikaavaldis, siis on avaldised ka   A   ja  (  A ) — kui  A  ja  B  on avaldised, siis on avaldised ka A  ∧ B   A  ∨ B     A  → B    A  ↔ B              A ⊕ B — tehtemärgi puudumine operandide vahel on samaväärne tehtega    ∧   ehk konjunktsiooniga :     A  B   ≡   A ∧ B   ≡   A ⋅ B   Eelnev definitsioon välistab loogikaavaldiste hulgast ebakorrektsed operandide ja tehtemärkide kooslused:   A  ∧ ∨ B        A  B ↔        A ( → ) B Kasutusel on ka alternatiivseid tehtemärke:    &  ≡ ∧      ~ ≡ ↔ ↔       + ≡ ∨∨  Siintoodud loogikatehteid ja lausearvutuses leiduvaid loogikatehteid
võrreldes  leiame siin täiendava olulise loogikatehte "summa mooduliga 2" (tehtemärk    ⊕)  , mis lausearvutuses puudub.  See loogikatehe leiab edaspidi põhjalikku käsitlust. LOOGIKALGEBRA  PÕHISEOSED   _ eituse eitamise seadus :   x ¯   =  x seosed     konstantidega    0  ja  1 :   __ __  0  =  1  1  =  0  0  ⋅ 1 = 0  0  w 1 = 1   x  ⋅ 0  =  0   x  ⋅ 1  =  x x  ⋅ x¯  =  0   x  w 0  =  x   x  w 1  =  1 x  w x¯  =  1 idempotentsus : x  ⋅ x  =  x x  w x  =  x de   Morgani    seadused    ( 2he    muutuja    jaoks ) :  ______  ____  x   w  y   =  x¯   y ¯    x  y   =  x ¯    w    y ¯ neeldumine:  x   w x y   =  x    x   w   x ¯   y   =   x   w y distributiivsus: x ( y  w z )  =  x y  w  x  z x   w (   y z )  =  ( x  w  y ) ( x  w  z ) muud seosed: x y   w   x y ¯    =   x (  x    w    y ) ( x  w  y ¯    )   =   x


mitteelementaarsete  loogikatehete  asendamine  elementaarsete  kaudu :   x   →  y   =   x ¯     w  y (  x ↔ y )  =   ( x → y ) ( y → x )   =  . . . .  =    x ¯   y¯    w  x  y    x  ⊕  y   =   x ¯   y    w  x  y ¯   LOOGIKAFUNKTSIOONID  (Boole'i funktsioonid) Vastavuste juures märkisime, et funktsioon on kõikjal lähtehulgas määratud
ühene vastavus. n-muutuja loogikafunktsioon    f (  x 1 x2  . . . xn )  on vastavus  n-muutuja Boole'i ruumist  < n   loogikaväärtuste hulka  < :    f (  x 1 x2  . . . xn ) :   < n    →  {  0, 1 } Seega seab n-muutuja loogikafunktsioon igale n-järgulisele kahendvektorile
(ehk argumentvektorile)    x 1 x2  . . . xn  vastavaks loogikaväärtuse  0  või  1. 2-muutuja funktsioon    f (  x 1 x2 )  on seega vastavus    f (  x 1 x2 ) :   < 2    →  {  0, 1 } Edaspidi tähistab mõiste  funktsioon  kõikjal  loogikafunktsiooni. Vastavuste vaatlemisel kasutasime vastavuste
illustratiivseks esituseks  diagramme. Toodud näide on ühe suvalise 2-muutuja 
funktsiooni diagramm, mis esitab 
funktsiooni kui ühest vastavust lähtehulgast <  sihthulka  <. Vastavusdiagrammist eelistatumaks 
loogikafunktsiooni esituseks on 
tõeväärtustabel , mis on vastavusdiagrammi
reorganiseeritud erikuju ja sisaldab seega 00 0 1 01 10 00 < < 2 f (x  x ): 1    2 Vastavuse Diagramm 2-muutuja funktsioonile funktsiooni kohta sedasama infot mis diagrammgi:   x 1 x2 f (  x 1 x2 )  0 0 0   0 1 1  1 0 0  1 1 0 2-muutuja funktsiooni tõeväärtustabel 3-muutuja funktsioon    f  ( x 1 x2 x3 )  on 8-elemendilise lähtehulgaga vastavus:    f (  x 1 x2 x3 ) :   < 3    →  {  0, 1 } 3-mõõtmeline Boole'i ruum sisaldab  2 3   = 8   erinevat 3-järgulist kahendvektorit:    < 3    Seega on 3-muutuja loogikafunktsiooni tõeväärtustabel samuti  8-realine. Järgnevalt esitame ühe suvalise 3-muutuja loogikafunktsiooni nii
vastavusdiagrammina  kui ka  tõeväärtustabelina : x 1 x2 x3 f (  x 1 x2 x3 ) 0  0  0 0 0  0  1 1 0  1  0 0 0  1  1 0 1  0  0 1 1  0  1 0 1  1  0 1 1  1  1 1            3-muutuja funktsiooni tõeväärtustabel   4-mõõtmeline Boole'i ruum sisaldab juba 16 erinevat kahendvektorit ja
4-muutuja loogikafunktsiooni tõeväärtustabel on seega 16-realine. Funktsiooni muutujate (ehk argumentide) arvu suurenemisel ühevõrra  
funktsiooni argumentvektorite arv kahekordistub. 000 0 1 001 010 011 100 101 110
111 < < 3 f (x  x  x ): 1    2    3 Vastavuse Diagramm 3-muutuja funktsioonile


Argumentvektor     x 1 x2  . . . xn  ∈   < n    on loogikamuutujate "väärtustekomplekt", mis esitab funktsiooni igale üksikule muutujale    x 1  ,   x 2  ,   . . .   xn   omistatavat väärtust  0  või  1.   Muutujate väärtustamisel omandab ka loogikafunktsioon ise väärtuse   0  või  1   ("seab argumentvektorile vastavaks loogikaväärtuse 0 või 1"). Kui vaadeldav 3-muutuja funktsioon    f (  x 1 x2 x3 )  väärtustub muutujaväärtuste   x 1 = 1  x 2 = 0 x 3 = 1  korral   0-ks, siis kirjutame:      f (  1 0 1 ) = 0 Funktsiooni  1-de piirkonna    V 1  ⊂ < n   moodustavad  need argumentvektorid    x 1 x2  . . . xn  ∈   V 1  , mille korral    f (  x 1 x2  . . . xn )  = 1 Funktsiooni  0-de piirkonna    V 0  ⊂ < n   moodustavad  need argumentvektorid    x 1 x2  . . . xn  ∈   V 0  , mille korral    f (  x 1 x2  . . . xn )  = 0 OSALISELT MÄÄRATUD  loogikafunktsioonid Vastavuste juures funktsiooni mõistet sisse tuues märkisime, et funktsiooni
määramispiirkonnaks võib olla ka ainult  osa  lähtehulga elementidest.
Sellisel juhul on tegemist osaliselt määratud funktsiooniga.
Loogikafunktsioonide korral tähendab osaline määratus seda, et tema
lähtehulgaks olevas Booli'i ruumis leidub selliseid argumentvektoreid   x 1 x2  . . . xn  ∈   < n    mille jaoks pole rangelt määratud, kumba loogikaväärtuse   0  või  1  funktsioon nende korral omandama peab. Sellised argumentvektorid moodustavad funktsiooni määramatuspiirkonna
V  —  ⊂ < n        V 0   ∪  V1   ∪  V —     =  {  0, 1 } n V V V 0 n — 1 < Boole'i ruumi jaotus osaliselt määratud f ( x . . x ) 1        n jaoks funktsiooni Funktsioon võib omandada  määramatuspiirkonda  kuuluvate
argumentvektorite     x 1 x2  . . . xn  ∈   V  —    korral ükskõik kumba loogikaväärtuse    0  või  1 .  Selle tähistamiseks kirjutatakse osaliselt
määratud funktsiooni tõeväärtustabelisse määramatuspiirkonna
argumentvektoritele vastavaks  '—'. Järgnevalt on esitatud osaliselt määratud 3-muutuja loogikafunktsiooni
tõeväärtustabel. Funktsiooni määramatuspiirkonna moodustavad  2
argumentvektorit:    V  —  =  <  x 1 x2 x3 f (  x 1 x2 x3 ) x 1 x2 x3 f f 1 f 2 f 3 f 4 0  0  0 0 0  0  0 0 0 0 0 0 0  0  1 1 0  0  1 1 1 1 1 1 0  1  0 — 0  1  0 — 0 0 1 1 0  1  1 0 0  1  1 0 0 0 0 0 1  0  0 — 1  0  0 — 0 1 0 1 1  0  1 0 1  0  1 0 0 0 0 0 1  1  0 1 1  1  0 1 1 1 1 1 1  1  1 1 1  1  1 1 1 1 1 1 Osaliselt määratud funktsioon   f     Täielikult määratud funktsioonid  f1  f2  f3   f 4     | V  — | =  2 mis sobivad funktsiooni     f  esitamiseks Osaliselt määratud funktsioon kuulub "lõpunimääramisele" ehk temalt
minnakse alati üle  täielikult määratud  funktsioonile, jaotades  ta
määramatuspiirkonna vabalt ära  1-de  ja  0-de  piirkonna vahel. Selle
tulemusel saadakse täielikult määratud funktsioon, mis sobib vaadeldava
osaliselt määratud funktsiooni esitamiseks. Kui funktsiooni
määramatuspiirkonnas on  n  kahendvektorit, siis saab määramatuspiirkonda
1-de  ja  0-de  piirkonna vahel ära jaotada  2 n  erineval viisil. Eelnevate tõeväärtustabelitega on toodud kõik  2 2 = 4  täielikult määratud funktsiooni   f 1     f2     f3     f4    ,  mis sobivad vaadeldava osaliselt määratud funktsiooni    f esitamiseks.  Osaliselt määratud funktsiooni    f   1-de  ja  0-de  piirkonnad sisalduvad tervikuna kõikide funktsioonide    f 1    f2    f3    f4    vastavates piirkondades. Erinevused täielikult määratud funktsioonide      f 1    f2    f3    f4    


1-de  ja  0-de  piirkondades piirduvad ainult nende argumentvektoritega, mis
moodustavad funktsiooni    f  määramatuspiirkonna. Seega "käituvad" kõik 4 funktsiooni    f 1    f2    f3    f4    nii, nagu nõuab funktsiooni    f   tõeväärtustabel. Kuigi osaliselt määratud funktsiooni võib "lõpuni" määrata vabalt, ei tehta
seda siiski juhuslikult vaid teatud tunnuste järgi valitakse sobivate täielikult
määratud funktsioonide hulgast eelistatuim. Loogikafunktsioonide  ESITUSKUJUD Funktsiooni mistahes esituskujust peab selguma, kuidas funktsioon
väärtustub oma muutujate kõikvõimalike väärtuskombinatsioonide korral. — tõeväärtustabel Tõeväärtustabel on loogikafunktsiooni kõige "vahetum" esitus. Ta loetleb
esitatava funktsiooni väärtused  tabelisse korrastatuna  kõikide
argumendiväärtuste kombinatsioonide (ehk argumentvektorite) korral,
alustades argumentvektorist   000. . .0   ja  lõpetades argumentvektoriga   
111. . .1 . Eelpool leiduvad juba näited 2-muutuja funktsiooni ja 3-muutuja
funktsiooni tõeväärtustabelitest. n-muutuja loogikafunktsiooni muutujatele    x 1 x2  . . . xn   saab väärtusi  0  ja 1   omistada   2 n   erineval viisil.  Samapalju peab olema ridu ka tema tõeväärtustabelis.  Seega tõeväärtustabeli suurus kasvab muutujate arvu
suurenemisel kiiresti (eksponentsiaalses progressioonis)  ja on ilmne, et
tõeväärtustabel sobib ainult väikse muutujatearvuga  loogikafunktsiooni
esitamiseks   (kuni  6  muutujat). — numbriline kümnendesitus Numbrilisel kujul 10ndesitus on tõeväärtustabeli kompaktne üherealine
esitus, kus 2ndvektorid on asendatud vastavate 10ndarvudega.  Funktsiooni
10ndesitus võib olla antud kas  1-de  või  0-de piirkonna järgi. Eelnev
osaliselt määratud näitefunktsioon     f  ( x 1 x2 x3 )  omaks  1-de piirkonna järgi järgnevat 10ndesitust:   f (  x 1 x2 x3 )  =  ∑ ( 1,  6,  7 ) 1   ( 2, 4 )  —          ehk   f (  x 1 x2 x3 )  =  ∑  1,  6,  7   ( 2, 4 )  —  ja  0-de piirkonna järgi järgnevat 10ndesitust:   f (  x 1 x2 x3 )  =  Π ( 0,  3,  5 ) 0   ( 2, 4 )  —          ehk   f (  x 1 x2 x3 )  =  Π  0,  3,  5   ( 2, 4 )  —   — loogikaavaldis Suvaline muutujaid sisaldav loogikaavaldis (oma eelpool defineeritud kujul)
on vaadeldav loogikafunktsioonina, kuna tema muutujate väärtustamisel
omandab ka kogu loogikaavaldis väärtuse  0  või  1 . Funktsiooni esitamisel avaldisena eelistatakse loogikafunktsiooni
normaalkujusid. Loogikafunktsioonide  NORMAALKUJUD Algterm  on  avaldise koosseisu kuuluv loogikamuutuja    xi   või selle inversioon    x ¯ i  või   konstant   0    1 . Elementaarkonjunktsioon on üksik algterm või algtermide konjunktsioon. Järgneval real on näitena toodud  5  elementaarkonjunktsiooni:  x1 x ¯ 2  x2 x ¯ 4 x ¯ 5 x ¯ 1 x ¯ 1   x 3 x ¯ 4 x6    x 1 x ¯ 3 x6 x ¯ 5 x2 Elementaardisjunktsioon  on üksik  algterm  või  algtermide disjunktsioon. Järgneval real on näitena toodud  4  elementaardisjunktsiooni:  x1 w  x ¯ 2  x2  w  x ¯ 4  w  x ¯ 5  w  x ¯ 1 x ¯ 1   x 3  w  x ¯ 4  w  x6 Disjunktiivne normaalkuju   (  DNK )   on üksik elementaarkonjunktsioon või  elementaarkonjunktsioonide disjunktsioon. Järgneval kahel real on mõlemal üks DNK :  x1 x2 x ¯ 3   w   x ¯ 2   w   x ¯ 2 x ¯ 4 x1  x 2 x ¯ 3   w   x ¯ 2 x ¯ 4   w   x1 x ¯ 4   w   x ¯ 2 x ¯ 4 x1 x3 Konjunktiivne normaalkuju   (  KNK )   on üksik elementaardisjunktsioon või  elementaardisjunktsioonide konjunktsioon. Järgneval kahel real on mõlemal üks KNK :


 (  x1 w  x2 w  x ¯ 3 ) ( x ¯ 1 w  x ¯ 2 )  x2    (  x ¯ 1 w  x2 w  x3  w  x4 ) ( x ¯ 1 w  x ¯ 2 w  x4 ) Järgneval kolmel real on igal real avaldis, mis on samaaegselt  nii DNK kui
ka  KNK :  x1 w  x2 w  x ¯ 3  x ¯ 1 x2 x ¯ 3  x ¯ 2   Täielik DNK   (  TDNK )   on  DNK,  kus iga elementaarkonjunktsioon sisaldab funktsiooni  kõiki  muutujaid   x i Järgneval viiel real on igal real üks  täielik DNK :  x ¯ 1 x2 x ¯ 3 x ¯ 4   w    x1 x ¯ 2 x ¯ 3 x4  x ¯ 1 x2 x ¯ 3   w    x1 x ¯ 2 x ¯ 3   w    x1 x2 x ¯ 3  x ¯ 1 x2   w    x1 x ¯ 2  x ¯ 1 x2 x ¯ 3 x ¯ 4  x 2 Täielik KNK   (  TKNK )   on  KNK,  kus iga elementaardisjunktsioon sisaldab funktsiooni  kõiki  muutujaid   x i Järgneval viiel real on igal real üks  täielik KNK :  ( x1 w  x2 w  x ¯ 3 ) ( x ¯ 1 w  x2 w  x3 )  ( x ¯ 1 w x2 w  x3 w  x4 ) ( x1 w  x ¯ 2 w x3 w x ¯ 4 ) ( x1 w  x ¯ 2 w x ¯ 3 w x ¯ 4 )  (  x1 w  x2 ) ( x ¯ 1 w  x ¯ 2 )  x ¯ 1 w  x2 w  x ¯ 3  x 2 Loogikaavaldise     f   keerukus   L  ( f  )  on tema koosseisus olevate algtermide arv. Igale funktsioonile leidub palju erinevaid loogiliselt võrdväärseid, kuid
erineva keerukusega normaalkujusid. Minimaalne  normaalkuju  (  MDNK   MKNK )  on konkreetse funktsiooni väikseima keerukusega  DNK või KNK. Funktsioon võib omada mitut erinevat  MDNK-d  või mitut erinevat  
MKNK-d. V 1  =  {  001, 010, 100, 110, 111 } DNK on seotud funktsiooni 1-de piirkonnaga  ja KNK on seotud 0-de piirkonnaga. Funktsiooni  1-de piirkonnast saab välja kirjutada selle funktsiooni TDNK.  Vaatleme järgnevat 3-muutuja funktsiooni: x 1 x2 x3 f (  x 1 x2 x3 ) 0  0  0 0 Funktsiooni 1-de piirkonda kuulub  0  0  1 1 5  argumentvektorit:   0  1  0 1 V 1 < 0  1  1 0 Koostame  DNK, kus iga  1  0  0 1 elementaarkonjunktsioon  omandab 1  0  1 0 väärtuse  1  täpselt ühe  1-de piirkonna 1  1  0 1 argumentvektori korral: 1  1  1 1  f (  x 1 x2 x3 )  =   x ¯ 1 x ¯ 2 x3   w    x ¯ 1 x2 x ¯ 3   w    x1 x ¯ 2 x ¯ 3   w    x1 x2 x ¯ 3   w    x1 x2 x3 Saadav DNK osutub TDNK-ks. Vaatleme selle avaldise "käitumist"  1-de piirkonna iga konkreetse
argumentvektori korral:  f (001)  =  1  w  0  w  0    w  0   w  0   =   1  f (010)  =  0  w  1  w  0    w  0   w  0   =   1  f (100)  =  0  w  0  w  1    w  0   w  0   =   1  f (110)  =  0  w  0  w  0    w  1   w  0   =   1  f (111)  =  0  w  0  w  0    w  0   w  1   =   1 . . . ja samuti ülejäänud kolme (ehk 0-de piirkonna) argumentvektori korral:  f (000)  =  0  w  0  w  0    w  0   w  0   =   0  f (011)  =  0  w  0  w  0    w  0   w  0   =   0  f (101)  =  0  w  0  w  0    w  0   w  0   =   0 Ilmneb, et saadud TDNK väärtustub tõeväärtustabeliga kokkulangevalt.


    1  [  [ )            3      3   
 :3,,730    inversioon      
f (  =                x f  x  1  x  1  x  1  x 
f  x ) = 0  (  ) =   (  ) =   (  ) = 1 !             " muutuja  #              [       "    $          %                       1   [ ) = [          Inversioon 1 ( x   x¯           &"
$        "      x1x f [1[2 I [1[2 I [1[2 I [1[2 I  [ 1 [2  I  [ 1 [2   
    
0 1
    
1 0
    
1 1
    
$        '"  
[1 [ 1 1 1 1 1 1 1 1 0 0
 
 
 
0 [  x ******** x  → x x
******** x  → x x
x  ⊕ x x  ∨ x x1 [2 1  1 1 1 1 1 1 1  
 
 
 
********
1 ∨ 2
1 ↔ 2
2
2 → 1
1
1 → 2 ______
1 2
f0 ([x   =   0 konstant 0 1 xx)   =   [[   ___________ f2 [[   =    [ → [ implikatsiooni inversioon 1 (xx   =   [    *********** f ([[   =    x → x pöördimplikatsiooni inversioon f [1[2   =   x    1 [[   =    [ ⊕ [         ()*    1 x1[2)   =    x ∨ x disjunktsioon ********* f  (x1x2)   =    x ∨ x disjunktsiooni inversioon     1 [[   =    [ ↔ x ekvivalents


110 [x   =    teise muutuja inversioon 111 [[   =    x2 → x1 pöördimplikatsioon f x1[   =   1     f [1[2   =    [1 → [
****** f ([x   =    [[ konjunktsiooni inversioon     1 x1x2   =     konstant 1 *                   '"           %                     
 ⊕    +     '"             
 ⊕       ↔  
 ↔    
1 ⊕  2 #     '"        
1 [1[ f f 0 0
0 1
1 0
1 1
x  ⊕ x x  ↔ x ,                   -"                           '  .  '  
      '  &  '  
      '  &  '  
      '  '  '   +                     ! "# 
(      ()*    ()*           "      #      
[  [    /      1"            %         1
0%   1           
  ()*        [  [            ()* x[ f f  
 
 
 
[  ⊕ x x  ∨ x   x 1 ⊕ [ 1,$     1 -de piirkonnast, mis on ! 01, 10 " [  ⊕  =    ∨  
1 2 ∨ 1 
2              
1 ⊕ 2 


[[ x  ⊕ x
   ∨  
   ⊕   
  ∨        ⊕   
  ∨        ⊕   
  ∨        ⊕   
  ∨     #    
 ⊕      ∨  
     ⊕          !" ⊕ 
/   ⊕        x ⊕ 1   x sest  ⊕     ja  ⊕     !           ⊕      % $  ⊕            ⊕      ⊕  ⊕      ⊕  ⊕  ⊕      ⊕  ⊕  ⊕  ⊕      ⊕  ⊕  ⊕  ⊕  ⊕     Seega võib paarisarv tk. liidetavaid konstante  lihtsalt avaldisest ära jätta sest nende summa tehtega ⊕ on  ja konstandi  liitmine ei muuda avaldise väärtust: [ ⊕    [ $ 0 ⊕ 0   0   1 ⊕ 1   0       [     [ ⊕ [   0 +     ⊕     x          x ⊕ x ⊕ x   x x ⊕ x ⊕ x ⊕ x    x ⊕ x ⊕ x ⊕ x ⊕ x   x [ ⊕ [ ⊕ [ ⊕ [ ⊕ [ ⊕ [ =  !    %     [               ⊕     +  %         konjunktsioon    disjunktsiooni   [   ∨       ∨   $       ⊕     [   ⊕   =   ⊕   !                 %       2           %                ⊕     ⊕     
  
  
  
  
  
  
  


(     ⊕       ⊕             %      
 ⊕ [  x¯  x ∨ x x ¯
 
 (  ⊕  )    (   ∨   )      ∨    ## ##   ⊕         ∨       ( ∨  )   ∨   ( ∨  )        ∨    ∨    ∨         ∨    Seega jõudsime võrduse    ⊕       ⊕   mõlemat poolt teisendades sama avaldiseni    ∨          
3         ∨     /1,$        ⊕          ⊕  


Loogikaavaldiste  TEISENDAMINE  (lihtsustamine) Loogikaavaldiste (loogikafunktsioonide) teisendamine on nende viimine  
muule  samaväärsele (lihtsamale) kujule. Loogikaavaldisi teisendatakse loogikaalgebra põhiseoseid ja
loogikafunktsioonide asendusseoseid rakendades. näide: Lihtsustada järgnev 3-muutuja loogikaavaldis. Kontrollida lihtsustatud avaldise ning esialgse avaldise samaväärsust. [ ( x  1  → →  x  2 )   Z    x ¯  1  x 3  ]   ⊕   x 2   = =    [  x ¯  1    Z  x 2     Z    x ¯  1  x 3  ]   ⊕   x 2    =    ________ =   ( x ¯  1   Z x 2  )   ⊕   x 2   =  ( x ¯  1    Z  x 2  )  x 2    Z  ( x ¯  1   Z x 2 )  x ¯  2  =  =    x  1  x ¯  2  x 2     Z    x ¯  1 x ¯  2      Z    x 2 x ¯  2     =      x ¯  1 x ¯  2   Seega osutub, et      [ ( x  1  → →  x  2 )   Z    x ¯  1  x 3  ]   ⊕   x 2    =    x ¯  1 x ¯  2  kontroll: Esialgne avaldis ja lihtsustatud avaldis peavad omandama sama loogilise väärtuse (0 või 1)  muutujate    x i   kõikide väärtuskombinatsioonide korral: x   1 x 2 x 3   [ ( x   1  → x 2 )   Z    x ¯   1  x 3  ]   ⊕   x 2 x ¯   1  x ¯   2 0    0    0    __  [ ( 0    →  0 )     Z  0   0  ]    ⊕   0   =   1 __   __          0     0   =  1 0    0    0   __  [ ( 0    →  0 )     Z  0   1  ]    ⊕   0   =   1 __   __          0     0   =  1 0    1    0   __ [ ( 0    →  1 )     Z  0   0  ]    ⊕   1   =   0 __   __          0     1   =  0 0    1    1   __ [ ( 0    →  1 )     Z  0   1  ]    ⊕   1   =   0 __   __          0     1   =  0 1    0    0   __ [ ( 1    →  0 )     Z  1   0  ]    ⊕   0   =   0 __   __          1     0   =  0 1    0    1   __ [ ( 1    →  0 )     Z  1   1  ]    ⊕   0   =   0 __   __          1     0   =  0 1    1    0   __ [ ( 1    →  1 )     Z  1   0  ]    ⊕   1   =   0 __   __          1     1   =  0 1    1    1   __ [ ( 1    →  1 )     Z  1   1  ]    ⊕   1   =   0 __   __          1     1   =  0 Seega omavad  nii esialgne lihtsustatav avaldis  kui ka  lihtsustatud avaldis  
samasugust tõeväärtustabelit   ehk  nad on loogiliselt võrdsed: x   1 x 2 x 3   [ ( x   1  → x 2 )   Z    x ¯   1  x 3  ]   ⊕   x 2 x ¯   1  x ¯   2 0    0    0    1 1 0    0    1    1 1 0    1    0   0 0 0    1    1   0 0 1    0    0   0 0 1    0    1   0 0 1    1    0   0 0 1    1    1   0 0 Loogikaavaldise  algtermiks  (lihtliikmeks)  nimetatakse üksikut loogikamuutujat    x  i  või tema inversiooni   x ¯  i   või avaldise koosseisu kuuluvat  konstanti    0  või  1.


KARNAUGH'  KAARDID Karnaugh' Kaart on tõeväärtustabeli sihipärane topoloogiline
ümberpaigutus tasandil või ruumis. Karnaugh' Kaardi põhiomadused: —  n-muutuja kaardi igal ruudul on n naaberruutu —  suvalised 2 naaberruutu on teineteise lähiskoodidega (lähiskoodid on kahendvektorid, mis erinevad ainult ühesainsas oma kahendjärgus) 2- ja 3- ja 4-muutuja funktsiooni Karnaugh' Kaart on tasandiline   
(2-mõõtmeline) 5- ja 6-muutuja funktsiooni Karnaugh' Kaart on ruumiline   (3-mõõtmeline) näide:   3-muutuja loogikafunktsiooni       f ( x 1 x2 x3 )  =   x 1  x ¯  2      Z   x 3   tõeväärtustabel:      
    paikneb 3-muutuja Karnaugh'  Kaardil: 0 1 3 4 5 2 7 8 9 11 10 12 13 15 14 6 0000 0001 0011 0010 0100 0101 0111 0110 1100 1101 1111 1110 1000 1001 1011 1010 3-muutuja  Karnaugh'  Kaart 4-muutuja  Karnaugh' Kaart   x   x   x   x   x   x   x 1  2     3  3      4  1     2   0   1 00 00 00 01 01 01 11 11 11 10 10 10 0 1 3 4 5 2 7 6 000 001 010 110 111 011 101 100     x 1  x2 x3             x  1 x ¯  2  Z  x 3     ———————————————————      0   0   0                        0        0   0   1                        1      0   1   0                        0      0   1   1                        1      1   0   0                        1      1   0   1                        1      1   1   0                        0      1   1   1                        1   x   x  x 1  2     3   0   1 00 01 11 10 0 1 1 0 0 1 1 1   Karnaugh' kaardil võib välja valida kindlate mõõtmetega ruutude gruppe,
mida nimetatakse kontuurideks. 2-mõõtmelise  Karnaugh' Kaardi  kontuuride võimalikud suurused :   1  × 1   ruutu 1  × 2   ruutu 1  × 4 2  × 2 2  × 4 4  × 4 ——————
      2 m   ×  2n x  x x  x x  x x  x 2   3 2   3 4   5 4   5 00 01 11 10 1 1 0 0 00 01 11 10 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 16 17 19 18 20 21 23 22 28 29 31 30 24 25 27 26 00 01 11 10 00 01 11 10 1 1 1 1 x    = x    = x    = x    = 10000 10001 10011 10010 10100 10101 10111 10110 11100 11101 11111 11110 11000 11001 11011 11010 00000 00001 00011 00010 00100 00101 00111 00110 01100 01101 01111 01110 01000 01001 01011 01010 5-muutuja  Karnaugh'  Kaart ( kolmemõõtmeline! ) x  x x  x 3   4 5   6 x   x    = x   x    = x   x    = x   x    = 1     2 1     2 1     2 1     2 00 00 00 00 00 01 01 01 01 01 11 11 11 11 11 10 10 10 10 10 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 16 17 19 18 20 21 23 22 28 29 31 30 24 25 27 26 48 49 51 50 52 53 55 54 60 61 63 62 56 57 59 58 32 33 35 36 34 37 39 38 44 45 47 46 40 41 42 43 000000 001000 000001 000011 000010 000100 000101 001111 001110 010000 011000 011111 010001 111000 110000 111111 111110 011110 100000 100001 101000 101110 101111 x  x 1   2  0 0  0 1  1 1  1 0 6-muutuja  Karnaugh' Kaart 00 01 11 10 ( kolmemõõtmeline )


 3-mõõtmelise  Karnaugh' Kaardi  kontuuride võimalikud suurused :
 1  × 1 × 1     ruutu 1  × 1 × 2     ruutu 1  × 1 × 4 1  × 2 × 1 1  × 2 × 2 1  × 2 × 4 .  .  .  .  .  .
4  × 4 × 4 Seega pole Karnaugh' kaardi kontuurideks ruutudegrupid küljepikkusega 3
ruutu. Ülejäänud võimalikud küljepikkused on kontuuridel lubatud. Karnaugh' kaardi iga kontuur vastab ühele kahendvektorite intervallile:
  Eelnevas näites on väljaeraldatud 3 kontuuri 3-muutuja  K. Kaardil ja 3
kontuuri 4-muutuja K. kaardil.  Iga kontuuri jaoks on näidatud ka temale
vastav intervall. n-muutuja kaardil on  2n  kattuvat  piirkonda:  x  1 = 0     x  1 = 1     x  2 = 0       x 2 = 1     .  .  .  .    x n = 0      x n = 1 mida võib tähistada vastavalt:   x ¯  1  x  1    x ¯  2  x  2    .  .  .  .  .  .     x ¯  n  x  n  1000 1001 1011 1010   x   x   x   x   x   x   x 1  2     3  3      4  1     2   0   1 00 00 00 01 01 01 11 11 11 10 10 10 < < < < < < Loogikafunktsioonide  MINIMEERIMINE Loogikafunktsiooni minimeerimine  on tema esitamine minimaalse
keerukusega normaalkujul — minimaalsel disjunktiivsel normaalkujul
(MDNK)  või  minimaalsel konjunktiivsel normaalkujul  (MKNK). Loogikafunktsioone võib minimeerida nende esituskuju teisendamisega —
loogikaalgebra põhiseosed ja loogikatehete asendusvalemeid kasutades. Loogikafunktsioonide minimeerimiseks on olemas ka spetsiaalsed meetodid,
mis leiavad suvalisele loogikafunktsioonile tema minimaalse
normaalkujulise esituskuju:  MDNK või MKNK. Loogikafunktsiooni  minimeerimine KARNAUGH' KAARDI  abil. Loogikafunktsiooni minimeerimine on Karnaugh' kaardi põhiline
rakendusvaldkond. Karnaugh' kaart on kõige eelistatum minimeerimisvahend. Loogikafunktsiooni minimeerimiseks Karnaugh' Kaardi abil: Ž  paigutada funktsiooni tõeväärtustabel Karnaugh' kaardile. Ž  katta kõik  '1'-d  ( või kõik '0'-d )  võimalikult väikse arvu  võimalikult suurte kontuuridega. Ž  määrata iga valitud kontuuri jaoks tema ulatuses konstantsed muutujad   x i   x   x   x   x   x   x   x 1  2     3  3      4  1     2   0   1 00 00 00 01 01 01 11 11 11 10 10 10 x x x x x x x x x x x x 1 1 1 1 2 2 2 3 3 3 3 3


Ž  kirjutada kontuuride konstantsete muutujate järgi välja MDNK või
MKNK liikmed.  Iga kontuur annab ühe elementaarkonjunktsiooni või
elementaardisjunktsiooni. näide: Vaatleme eelpoolset 3-muutuja funktsiooni     f ( x 1 x2 x3 )  tõeväärtustabeliga   Olgu eesmärk esitada sellele funktsioonile       MDNK  ja  MKNK.        Kanname  tõeväärtustabeli Karnaugh'   Kaardile: MDNK saamiseks  katame 1de ruudud võimalikult väikse arvu võimalikult suurte kontuuridega: MKNK saamiseks — 0de ruudud: Kontuurid tohivad osaliselt kattuda — suurendada igat kontuuri maksimaalsuuruseni. 1de kontuuri ei tohi sattuda 0lle  ja vastupidi. 1de ruudud (1de piirkond) on kaetav kahe max kontuuriga:  4se  ja  2sega. 4se kontuuri ulatuses on ainus konstantne muutuja    x  3     ( x 3  =  1 ) 2se kontuuri ulatuses on konstantseteks muutujateks      x  1 = 1   ja    x 2 = 0 Iga 1de kontuur määrab DNK-s ühe elementaarkonjunktsiooni: MDNK:      f ( x 1 x2 x3 )   =   x 1  x ¯  2   Z  x 3       x 1   x2  x3              f     —————————————
    0    0    0                0       0    0    1                1     0    1    0                0     0    1    1                1     1    0    0                1     1    0    1                1     1    1    0                0     1    1    1                1   x   x  x 1  2     3   0   1 00 01 11 10 0 1 1 0 0 1 1 1 f:   x   x  x 1  2     3   0   1 00 01 11 10 0 1 1 0 0 1 1 1   x   x  x 1  2     3   0   1 00 01 11 10 0 1 1 0 0 1 1 1 1de kontuuri ulatuses konstantne muutuja    x  i = 1  annab elementaarkonjunktsiooni koosseisu vastava  otseväärtuses  muutuja    x  i  1de kontuuri ulatuses konstantne muutuja    x  i = 0  annab elementaarkonjunktsiooni koosseisu vastava  inversioonis  muutuja    x ¯  i  0de ruudud (0de piirkond) on kaetav samuti kahe kontuuriga: mõlemad 2sed. Ühe kontuuri ulatuses on konstantseteks muutujateks      x  1 = 0   ja    x 3 = 0 Teise kontuuri ulatuses on konstantseteks muutujateks    x  2 = 1   ja    x 3 = 0 Iga 0de kontuur määrab DNK-s ühe elementaardisjunktsiooni: MKNK:      f ( x 1 x2 x3 )   =  ( x 1   Z  x 3  ) ( x ¯  2   Z  x 3 ) 0de kontuuri ulatuses konstantne muutuja    x  i = 0  annab elementaardisjunktsiooni koosseisu vastava  otseväärtuses  muutuja    x  i  0de kontuuri ulatuses konstantne muutuja    x  i = 1  annab elementaardisjunktsiooni koosseisu vastava  inversioonis  muutuja    x ¯  i 


Loogikafunktsiooni  minimeerimine McCLUSKEY'  MEETODIGA Quine - McCluskey meetod on loogikafunktsioonide minimeerimismeetod,
mis on rakendatav suvalise loogikamuutujate arvu korral. Vaatleme  numbrilist McCluskey meetodit ,  mida rakendatakse
minimiseeritava loogikafunktsiooni 10ndesitusele. McCluskey meetod kasutab mõistet  "10ndarvu indeks",  mis on 1de arv
selle 10ndarvu kahendkujus. Funktsiooni MDNK saamiseks lähtutakse 1de piirkonnast ja MKNK
saamiseks 0de piirkonnast. Olgu antud 3me muutuja loogikafunktsioon, millele vaja leida MDNK:   f ( x 1 x2 x3 ) = ∑ ( 0, 1, 3, 5, 6, 7 )  1 =  Π ( 2, 4 ) 0   MDNK leidmiseks:  1.  Grupeerida 1de  piirkonna arvud tabelisektsioonidesse kokku vastavalt
nende indeksitele: index 1de pk 0 0 1 1 2 3 5 6 3 7 2.  "Kleepida" naabersektsioonide arve kokku  "kahesteks" intervallideks.  — omavahel kokkukleepida saab ainult naabersektsioonide arve — kokku kleepida saab ainult selliseid naabersektsioonide arve, mille vahe
on   2 n  ehk  1  või  2  või  4  või  8  või  16  jne. — väiksema indeksiga sektsioonist pärit kleebitav arv peab ka oma
väärtuselt väiksem olema index 1de pk 2-sed vahe 0 0 0 - 1 1 1 1 1 - 3 2 2 3 1 - 5 4 5 3 - 7 4 6 5 - 7 2 3 7 6 - 7 1 3.  Kleepida naabersektsioonide intervalle kokku suuremateks intervallideks. — kokku kleepida saab ainult naabersektsioonide intervalle — kokku kleepida saab naabersektsioonide selliseid intervalle, millel on
sama vahe — intervalle tohib kokku kleepida ainult siis, kui kleebitavate intervallide
omavaheline vahe ("uus vahe") on samuti  2 n index 1de pk 2-sed vahe 4-sed vahe 0 0 0 - 1 1 1 - 3 - 5 - 7 2,4 1 1 1 - 3 2 1 - 5 - 3 - 7 4,2 2 3 1  -  5 4 5 3 - 7 4 6 5 - 7 2 3 7 6  -  7 1 4.  Korrata rekursiivselt eelmist sammu seni kuni võimalik — viimasel
kleepimisel saadud intervallide edasikleepimiseks veelgi suuremateks.
(käesolevas näites ei saa enam 4-seid intervalle kokku kleepida 8-steks) Kleepimisel moodustunud korduvaid intervalle võib ignoreerida ehk jätta
kleepimistabelisse üldse märkimata.  (1-5-3-7 on juba olemas: 1-3-5-7) 5.  Moodustunud lõplikus kleepimistabelis märgistada kõik lihtimplikandid: index 1de pk 2-sed vahe 4-sed vahe 0 0  0 - 1  A2 1  1 - 3 - 5 - 7    A1 2,4 1 1  1 - 3 2 2 3  1 - 5 4 5  3 - 7 4 6  5 - 7 2 3 7  6 - 7  A3 1 Käesolevas näites on lõplikus kleepimistabelis  3 lihtimplikanti   ( A1   A2   A3 ) 6.  Koostada lihtimplikantide tabel, mis näitab 1de piirkonna katmist
lihtimplikantide poolt: lihtimpl. \ 1de pk 0 1 3 5 6 7 A1 1 1 1 1  ← valitud A2 1 1  ← valitud A3 1 1  ← valitud


7.  Valida lihtimplikantide tabelist välja minimaalne arv ridu, nii et kõik
veerud oleks "kaetud". 8.  Valitud ridadele vastavatest lihtimplikantidest kirjutada igaühest välja
üks tema suvaline kahendvektor:   x  1  x 2  x 3           4    2    1 A1          0    0    1 A2          0    0    1 A3          1    1    1 9.  Igast kahendvektorist elimineeritakse välja need järgud, mille kaaluga
võrdne vahe kaasnes selle lihtimplikandiga  A:   x  1  x 2  x 3           4    2    1 A1          0    0    1  x  3  ( A1-ga kaasnes vahe  2,4 ) A2          0    0    1 x ¯  1  x ¯  2  ( A2-ga kaasnes vahe  1 ) A3          1    1    1 x  1  x 2  ( A3-ga kaasnes vahe  1 ) 10.  Kirjutatakse välja  MDNK.   Kahendvektori säilinud järguväärtus '1'
annab vastava muutuja otseväärtuse  ja  '0' annab inversiooni: MDNK :      f   =    x   3    Z    x ¯   1  x ¯   2     Z   x 1  x 2 McCluskey meetodi sarnasus Karnaugh' kaardi abil minimeerimisega 1.  Lähiskoodid sattuvad indeksite järgi grupeerides naabersektsioonidesse.
Seega on Karnaugh' kaardil naaberruutudes paiknevad koodid ka McCluskey
kleepimistabelis naabersektsioonides ehk McCluskey meetod kleebib kokku
neidsamu koode, mis ka Karnaugh' kaardil oleksid kokkuseotavad. 2.  Intervallide kasvatamine kleepides on samaväärne kontuuride
suurendamisega kaardil. Igale kleepimistabelis moodustunud intervallile
vastab üks kindel kaardikontuur. Taandatud DNK Loogikafunktsiooni implikandiks nimetatakse igat tema 1de intervalli. näide: Olgu 3me muutuja funktsioon: Sellel funktsioonil on 4 ühevektorilist 
1de intervalli:  <  {011}  {100}  {101} ja 3 kahevektorilist  1de intervalli: <      {001  011}      {001  101} Suuremaid (ehk "neljaseid") 1de intervalle  sellel funktsioonil pole. Seega omab vaadeldav 3me muutuja funktsioon  7  implikanti. Lihtimplikandiks  nimetatakse maksimaalset (ehk suurimat) implikanti. Lihtimplikant ei sisaldu tervikuna mitte üheski veelgi suuremas selle
funktsiooni implikandis. Eelneval näitefunktsioonil on  3  lihtimplikanti ehk kõik kahesed
implikandid on lihtimplikantideks. Ükski "ühene" implikant pole siin
lihtimplikandiks. Taandatud disjunktiivne normaalkuju  on funktsiooni kõigi
lihtimplikantide disjunktsioon. Vaadeldava funktsiooni 1de piirkond õnnestub katta kahe kontuuriga, mis
annavad tema MDNK-ks:        f ( x 1 x2 x3 )   =  x 1  x ¯  2      Z  x ¯  1  x 3 Funktsioonil on 3 lihtimplikanti, mis annavad tema Taandatud DNK-ks:     f ( x 1 x2 x3 )   =  x 1  x ¯  2      Z  x ¯  1  x 3     Z  x ¯  2  x 3   x   x  x 1  2     3   0   1 00 01 11 10 0 1 1 0 0 0 1 1 f :   x   x  x 1  2     3   0   1 00 01 11 10 0 1 1 0 0 0 1 1 f :   x   x  x 1  2     3   0   1 00 01 11 10 0 1 1 0 0 0 1 1 f : MDNK Taandatud DNK


MDNK koosneb alati  osadest või kõikidest  Taandatud DNK
elementaarkonjunktsioonidest.   Funktsiooni MDNK  ja Taandatud DNK  
võivad olla võrdsed. Loogikaskeemide elemendid  (loogikaelemendid) Kahendkoode (ehk nende koosseisu kuuluvaid loogikaväärtusi  0   1 )  
töötlevat elektriskeemi nimetatakse digitaalskeemiks. Iga digitaalseadme elementaarseteks koostisosadeks on loogikaelemendid,
mis teevad loogikaväärtustega   0  ja  1  lihtsaimaid loogikatehteid.
Loogikaelementide omavahelisel kokkuühendamisel saadakse
loogikaskeem. Iga digitaalseade koosneb seega loogikaskeemi(de)st ja ta töötleb 1-de ja
0-de kogumeid. Seega osutuvad loogikafunktsioonid digitaalseadmete
matemaatiliseks mudeliks  ja ka vastupidi — loogikaskeemid on
loogikafunktsioonide füüsiliseks mudeliks. Joonisena esitatud loogikaskeemides kasutatakse loogikaelementide
tähistamiseks spetsiaalseid tähiseid. 1.  Lihtsaim loogikaelement on invertor  ehk  EI-element   (NOT).  Invertor teostab loogikamuutuja inversioonitehet ehk eitust: Kuna inversioon on ainus unaarne loogikatehe, siis invertor on ainus ühe
sisendiga loogikaelement. Ülejäänud loogikaelemendid omavad 2 või enam sisendit. 2.  JA-element teeb sisendite loogilist korrutamist ehk konjunktsiooni. (AND)


3.  VÕI-element teeb oma sisendite loogilist liitmist ehk disjunktsiooni. (OR) 4.  JA-EI element teeb oma sisendite konjunktsiooni inversiooni.  (NAND) 5.  VÕI-EI element teeb oma sisendite disjunktsiooni inversiooni.  (NOR) 5.  XOR-element (Exclusive OR)  teeb tehet  "summa mooduliga 2". Ülalloetletud loogikatehetel    NOT    AND    OR    NAND    NOR    XOR on "oma" spetsiaalsed loogikaelemendid. 6.  Implikatsioon  realiseeritakse asendusseose    x  1 →  x 2 =   x ¯  1  Z x 2     kaudu:       _______ 7.  Ekvivalents  realiseeritakse asendusseose    x  1 ↔  x 2  =   x 1  ⊕ x 2     kaudu: —————————————————————————————————— näide:   ____________ Loogikaavaldisele     f  =   x  1 ( x ¯  2   Z  x 3 )     vastab loogikaskeem: —————————————————————————————————————————————————————— Igast loogikaskeemist võib välja kirjutada talle vastava loogikaavaldise
(loogikafunktsiooni). Iga loogikaavaldise jaoks võib koostada teda realiseeriva loogikaskeemi.
Kuna loogikaavaldisel võib olla mitu erinevat samaväärset esituskuju, siis
sobivad avaldise esitamiseks ka mitmed erinevad loogikaskeemid. x x x 3 1 2 f & 1


              K0  nulli säilitavad funktsioonid .  ühte säilitavad funktsioonid .5  pööratavad funktsioonid .2  monotoonsed funktsioonid .l — lineaarsed funktsioonid 0-lli säilitavate    
K0   f  [    [  _ 1 ( 0 0 . . . 0  = 0 }              0       0 1-te säilitavate    
K1 = { 1 ( x . . . x ) _ 1  1 1 . . . 1  = 1 }              1       1
     K0  K           pööratavate     ___ K5 = { f ( x . . . x ) _ f  x¯1 x¯2 . . . x¯n  = 1  x1 x2 . . . xn  }      pööratav,            monotoonsete     Km = { fx   [3  |x  x ... x3 < z z ...z3  ↔   f  x x ... x3  ≤ f  z z ...z3 (}      monotoonne,            lineaarsete    
KO   f ( x x... x3) | f  x1 x2 ... xn   0  ⊕ 1x1 ⊕ 2 x2 ⊕ . . . ⊕ c3 [3 
c 0  c1  c2  3 ∈     n -muutuja loogikafunktsioon on lineaarne, kui ta on esitatav kujul
0    ⊕  1 x1   ⊕   2 x2   ⊕  . . .  ⊕     [      c i ∈ { 0 1 }   n -muutuja funktsioonile leidub kahendkonstantide  i komplekt (n!"   #    
0    ⊕  1 x1   ⊕   2 x2   ⊕      ⊕   c n [n kehtib kõigi argumentvektorite x 1 x2    xn ∈ { 0 1 } n korral.     0 1 2  3  $      ⊕  [ ⊕  [ ⊕    ⊕ n [n peab lineaarse funktsiooni korral kehtima kõikide argumentvektorite korral, siis peab ta kehtima ka järgnevate korral:       
      
      
      
       Nende argumentvektorite asendamisel avaldisse lihtsustub aga tegurite    #       
&     i  1         =  0    ⊕
1 ⋅     ⊕
2 ⋅    ⊕ . . .  ⊕    ⋅  =  0 f           0    ⊕
1 ⋅     ⊕
2 ⋅    ⊕    ⊕  c  ⋅ 0   0  ⊕ 1 f           0    ⊕
1 ⋅     ⊕
2 ⋅    ⊕     ⊕   n ⋅     ⊕        1               ⊕
 ⋅     ⊕
 ⋅    ⊕    ⊕   n ⋅  = c   ⊕ c
Seega avalduvad konkreetse funktsiooni jaoks konstandid  L järgnevalt:


0  1         
 
    ⊕ 1           1             ⊕ 1         
 
    ⊕ 1           1             ⊕ 1         
 
    ⊕ 1           1             ⊕ 1          . . . . . .       ⊕ 1 (000. . .1) = 1 (000. . .0)    ⊕ 1 (000. . .1) '         
 ,  ,   n ∈ { 0 1 } mistahes funktsioonile, kuid see ei tähenda, et iga loogikafunktsioon on lineaarne. Kuigi meil on pärast konstantide  i leidmist mingi avaldis  0   ⊕  1 [  ⊕   [  ⊕ . . . ⊕  3 [3  #           1 ( [ 1 [2  [n  mitteesitavaks. Selliselt saadud avaldis  0   ⊕  1 x1  ⊕  2 x2  ⊕ . . . ⊕  n xn           . . . 
   . . . 
   . . . 
   . . . 
   . . .  #    n1) konstanti  i ongi selliselt valitud, et avaldis kehtiks just nende (n+1) argumentvektori korral. Et funktsioon osutuks lineaarseks, peab saadud avaldis c 0   ⊕  1 x1  ⊕  2 x2  ⊕    ⊕  n xn       
          &        #            
$    &   [ 1 [2  [n #   1  x  x ... x3  ≠ c 0   ⊕  c1 x1  ⊕  c2 x2  ⊕    ⊕  3 [3      1 ( [  [  [3 )      f ( [ 1 x2 ... xn ) ∉  .l Märgime, et avaldisest c 0   ⊕  c1 [1  ⊕  c2 [2  ⊕    ⊕  cn [n     [ i #   
i   * +    I  [  [  lineaarsust. f  [  [ )     #       1  [  x    0   ⊕  1 [1  ⊕  2 [2 Konstandid  i on leitavad vaadeldava funktsiooni 1  [  [  tõeväärtustabelist: c 0  f ( 0 0 ) c 1  f ( 0 0 )    ⊕ f ( 1 0 ) c 2  f ( 0 0 )    ⊕ f ( 0 1 ) Saadud avaldis c 0   ⊕  c1 x1  ⊕  c2 x2 kehtib kindlasti argumentvektorite 0 0 0 1 1 0 korral: c 0    ⊕ c1 ⋅ 0   ⊕ c2 ⋅ 0 = 1 ( 0 0 ) c 0    ⊕ c1 ⋅ 0   ⊕ c2 ⋅ 1 = f ( 0 1 ) c 0    ⊕ c1 ⋅ 1   ⊕ c2 ⋅ 0 = f ( 1 0  2-muutuja funktsiooni f[  [ )         &    
    ⊕  ⋅    ⊕  ⋅   f    
    ⊕   ⊕   f     Asendades eelnevas avaldises konstandid c L neid määravate avaldistega, teisendub 2-muutuja funktsiooni lineaarsust kontrolliv avaldise kujule: f ( 0 0     ⊕ 1        ⊕ 1        ⊕ 1        ⊕ 1      1     $      ⊕  1        ⊕ 1        ⊕ 1      1             
'  +    f  [ 1 [2    #    f        ⊕ f        ⊕ f      f     Selle võrduse kehtivus või mittekehtivus (ehk samas ka funktsiooni lineaarsus ) on vaadeldava 2-muutuja funktsiooni tõeväärtustabelist kergesti kontrollitav. näide : Kontrollime 2-muutuja funktsioonide


1 ( x  x )  x 1 x2
f  [  [ ) = x  ∨ x () f  [  [   [ 1 ↔ [2   I ( [  [ ) = x  ⊕ x
summa mooduliga 2   xx 0 0
0 1
1 0
1 1
x  x x  ∨ [2 [ 1 ↔ [2 [ 1 ⊕ [2 - #  konjunktsioon  disjunktsioon   #   
1        ⊕ 1        ⊕ 1     ≠ 1    
 ⊕ 0  ⊕ 0 = 0 ≠ 1
0 ⊕ 1  ⊕ 1 = 0 ≠ 1         on  #      f        ⊕ 1        ⊕ 1      1     ekvivalents:  ⊕   ⊕     1     summa mooduliga 2:  ⊕   ⊕     1              1  x  x ) = [  ⊕ [      +    & I ( [  [ ) =     ⊕   [  ⊕   [
 =
1 =
2 =
$       #      
x  ↔ x = c   ⊕  1 x1  ⊕  2 x2      0    1   2
0 
1 
2 
x 1 ↔ x2    ⊕  x1 ⊕  x2 '         #                      1     ⊕   x  ⊕  x inverteerib selle: _______ [  ↔ [ = [ ⊕ [ ______ [  ⊕ [ ⊕ 1 = [  ⊕ [ (    +    f  [  x  on samapalju, kui palju on avaldise  0   ⊕  1 x1  ⊕  2 x2      c L     c 0 c1 c2 c 0   ⊕  c1 [  ⊕   [   
   [ 2    [ 1    [ 1 ⊕ [2   
    ⊕ [ 2     ⊕ [ 1     ⊕ [ 1 ⊕ [2 Ilmneb, et 8-st lineaarsest 2-muutuja funktsioonist on    muutujaga ainult 2 funktsiooni. 4 funktsiooni on tegelikult 1-muutuja funktsioonid ja 2 funktsiooni on 0-muutuja funktsioonid ehk konstandid.


Loogikafunktsioonide  TÄIELIKUD SÜSTEEMID.   BAASID Loogikafunktsioonide (loogikatehete) süsteem  on  loogikafunktsioonide
hulk. Süsteemi võivad kuuluda lisaks loogikatehetele ka konstandid  0 ja 1 ,
mis on vaadeldavad muutujatest mittesõltuvate funktsioonidena. näide: <    on kolme loogikatehtega süsteem; <    on kahe loogikatehtega süsteem; <    on ühe loogikatehtega süsteem; Kui loogikaavaldis kuulub kuhugi kindlasse süsteemi, siis on ta esitatud
ainult selles süsteemis leiduvaid loogikatehteid (funktsioone) kasutades. näide:   Avaldis    (  x  1 →  x 2 ) ( x 1 x ¯  2 →  x ¯  3 )    kuulub esimese näitena toodud süsteemi, kuna ta ei sisalda muid tehteid peale  konjunktsiooni,
implikatsiooni  ja  inversiooni. Loogikafunktsioonide süsteem on täielik, kui temas sisalduvaid funktsioone
(tehteid) kasutades on võimalik esitada suvalist loogikaavaldist  (ehk suvalist
loogikafunktsiooni). Süsteemi täielikkuse kriteerium   (Post-Jablonski kriteerium): Loogikafunktsioonide süsteem on täielik, kui ta sisaldab  vähemalt ühte 0-lli mittesäilitavat  funktsiooni; vähemalt ühte 1-te mittesäilitavat  funktsiooni; vähemalt ühte mittepööratavat  funktsiooni; vähemalt ühte mittemonotoonset  funktsiooni; vähemalt ühte mittelineaarset  funktsiooni. Nende viie tingimuse samaaegse täidetuse nõue ei tähenda, et täielik süsteem
peaks koosnema vähemalt viiest loogikafunktsioonist.  Täielikuks võib
osutuda ka ainult ühe funktsiooniga süsteem  <,  kui selle süsteemi ainus
funktsioon   f   ei kuulu mitte ühtegi klassi viiest:  (  f    ∉  K 0 )  ∧  (  f   ∉  K1 )  ∧  (  f   ∉  Kp )  ∧  (  f   ∉  Km )  ∧  (  f   ∉  Kl ) Süsteemi täielikkuse kontrollimiseks ja täielike süsteemide koostamiseks
tuleb teada süsteemi moodustavate funktsioonide omadusi ehk nende
kuulumist või mittekuulumist klassidesse    K 0     K1     Kp     Km    Kl Loogikatehete omaduste määramiseks tuleb võtta vaatluse alla need
2-muutuja funktsioonid, mis neid tehteid esitavad.  Eelpool vaadeldud 16-st
2-muutuja funktsioonist   f  0  . . .   f 15   keskendume järgnevatele: f  0  =  0 (konstant 0) f  9 =  x 1 ↔  x 2    (ekvivalents) f  1 =   x 1 x 2 (konjunktsioon) f  12 =    x ¯  1     (inversioon)  ______ f  2 =  x 1 → x 2   (implikatsiooni inversioon) f  13 =  x 1 →  x 2  (implikatsioon)     ____ f  6  =   x 1  ⊕ x 2  (summa mod 2) f  14  =   x 1  x 2 (konj. inversioon)   ______ f  7 =   x 1  Z   x 2    (disjunktsiooni inversioon) f  0  =  1 (konstant 1) f  8  =   x 1  Z   x 2    (disjunktsioon) Vaatlusest jätame välja ülejäänud  2-muutuja funktsioonid    f  3   f 4   f 5   f 10   f 11   _______  f  3 =   x 1 f  4   =  x 2 → x 1             f  5 =   x 2         f  10 =   x ¯  2           f  11 =   x 2 → x 1   ( pöördimplikatsioon) mis on oma operandi triviaalsed taasesitused  (  f  3   f 5  ) või mis dubleerivad (vahetatud operandidega) mõnda eespool loetelus juba leiduvat tehet. Kuna süsteemi täielikkuse kriteerium põhineb funktsioonide mittekuulumisel
klassidesse   K 0     K1     Kp     Km    Kl  ,  siis järgnev tabel esitab 2-muutuja funktsioonide omadusi, rõhutades nende mittekuulumist konkreetsesse
klassi:


f  i K 0 K 1 K p K m K l f  0 ∉ f  1 ∉ ∉ f  2 ∉ ∉ ∉ ∉ f  6 ∉ ∉ ∉ f  7 ∉ ∉ f  8 ∉ ∉ ∉ ∉ ∉ f  9 ∉ ∉ ∉ f  12 ∉ ∉ ∉ f  13 ∉ ∉ ∉ ∉ f  14 ∉ ∉ ∉ ∉ ∉ f  15 ∉ ∉ 2-muutuja funktsioonide   f  0  . . .  f 15  omadused Kui koostada alamhulk    <  ⊂    {  f  0  . . .  f 15 }  selliselt, et funktsioonide   <  read katavad ühiselt märgiga  ∉  eelnevas tabelis kõik veerud   K 0     K1     Kp     Km    Kl  ,  siis   <   osutub täielikuks süsteemiks. Baas  on minimaalne täielik loogikafunktsioonide süsteem. Suvalise funktsiooni väljajätmisel baasist tema täielikkus kaob.  Täielike süsteemidega tegelemisel on huvipakkuvad just baasid. Eelnevast tabelist ilmneb, et funktsioonidest    f  0  . . .  f 15   ehk loogikatehetest ja konstantidest  0  ja  1 saab moodustada  17  baasi :        __ < = < VÕI-EI  baas ("Peirce'i nool")        __ < = < JA-EI  baas (Schefferi baas)        __ < = < < = < (implikatiivne baas)        __ < = < < = <        __    __ < = <        __ < = < (implikatiivne baas)          __ < = < (Boole'i konjunktiivne baas)          __ < = < (Boole'i disjunktiivne baas)        __ < = < < = < < = < < = < < = < < = < < = <      (Zegalkini baas e. Read-Mülleri baas) Ilmneb, et —  konjunktsiooni inversioon moodustab üksikult baasi   (JA-EI  baas) —  disjunktsiooni inversioon moodustab üksikult baasi   (VÕI-EI  baas) Seega saab mistahes loogikaavaldist esitada kujul, kus esineb ainult JA-EI
(VÕI-EI) tehe.  Nendes baasides avaldistele saab koostada vastava loogikaskeemi, kasutades
skeemis ainult JA-EI  (VÕI-EI)  elemente.


Loogikafunktsioonide  teisendused  baasidesse Loogikaavaldise esitamiseks mingis kindlas baasis tuleb ta esitada selle baasi
loogikatehete abil.  Baasis puuduvad tehted tuleb selle baasi
üleminekuseoste abil asendada baasis olemasolevate kaudu. Kuna mistahes loogikatehe on esitatav elementaartehete  inversiooni,
konjunktsiooni ja disjunktsiooni abil, siis avaldise teisendamiseks
konkreetsesse baasi piisab kolmest üleminekuseosest, mis asendavad just
baasis puuduvad elementaartehted baasis olemasolevate tehete kaudu.  __ __ Baasid    <    <  ei oma erandina üleminekuseoseid, kuna nendesse teisendamiseks piisab sobiva normaalkuju topeltinversioonist koos järgneva
de Morgani seaduse rakendamisega: _____    __ _____ <   ⇐ ⇐⇒ ⇒   KNK  _____    __ _____ <     ⇐ ⇐⇒ ⇒   DNK Teistele olulistele baasidele koostame üleminekuseosed: < :   x ¯    =   x   →  0   x  1  Z   x 2  =   x ¯  1  →   x 2    =    ( x 1  →  0 )  →   x 2      ______  x  1  x 2   =   x ¯  1  Z   x ¯  2    =    ( x 1  →  ( x 2  →  0 ) )  →   0 ——————————————————————————————     __< : ( inversioon lubatud, vaja asendada    Z   ja  & )   x  1  Z   x 2   =   x ¯  1  →   x 2     ______    _______  x  1  x 2   =   x ¯  1  Z   x ¯  2    =    x 1  →   x ¯  2 < :   x ¯    =   x  →  ( x   ⊕ x  )   x  1  Z   x 2   =    x ¯  1  →   x 2   =    x 1  →  ( x 1   ⊕ x 1  )  →   x 2  x  1  x 2  =  ( x 1  →  ( x 2  →  0 ))  →   0   =    =    ( x  1  →  ( x 2  →  ( x 1   ⊕ x 1 )))  →   ( x 1   ⊕ x 1 )   —————————————————————————————— < : ( &  lubatud, vaja asendada  inversioon   ja   Z )   x ¯    =   x   ⊕ 1        _____   x  1  Z   x 2   =    x ¯  1   x ¯  2    =  (x 1   ⊕ 1) (x 2   ⊕ 1)  ⊕ 1  =    =    x  1 x 2   ⊕  x 1  ⊕ x 2   ⊕ 1   ⊕ 1   =    x 1 x 2   ⊕  x 1  ⊕ x 2