MATHMVTISKE DEFINISJONER - ET EDB-SYSTEM FOR

La c og d é R1" . Vi definerer to p a r tie lle ordninger i

c i d ( V i ) : d i c > d c i d A c * d .

3 . 1 v e r d i, vekt, teoretisk resu lta t, forklaring av beslutning og fe ile n for beslutning

3.1 . 1 VercUen t il argumentene

La n x m na trisa V representere verdiene på de ra argu

mentene i de n fo rskjellig e o e slutm n g e n e.

La V^ være den i-te raden i verdim atrisa. Den

representerer da verdiene til argumentene i den i-te beslut- ninga i m aterialet.

V kan skrives son n rader s l i k : og i .

- 1 hvis argument j i beslutning i er negativt 1 hvis argument j i beslutning i er positivt 0 hvis argument j i beslutning i er nøytralt

V V.

Vn-1

- 28

3 .1 .2 Vektene på_a£gumentparenc

La w vaire en vektor med m elementer som skal represent kaller vi definisjonsområaet tor vektene.

3 .1 .3 Teoretisk c_eslU tat_tor_Des_lutni^ngene Produktet D^ = v^-w kaller vi det teoretiske

resultat. Hvis v J w > 0 , sier vi at det teoretiske resultatet er positivt. Hvis V . . w < 0 , sier vi at det teoretiske resultatet er negativt.

- 29

-3 .1 .4 Forklaring_jv eijaes^utning

Vi sier a t et sett av vekter, w = (w1(w2, . . . ,wm) ,

3 .2 .1 KonsiJtent^ mertgde_av besliJtninger

Ei mengde ,M av beslutninger er konsistent hvis det fins

3 .2 .2 Maisijnalt kons^stentjnengde av_be^lutninge£

Mengden av a lle beslutninger i materialet kaller v i M. Ei konsistent delmengde MB£M er rraksinal hvis MBl>{i}er

inkonsistent for alle i t M - MB. Eller uttrykt på en annen måte. MB er maksimal konsistent hvis alle mengder av beslutninger M som tilfredsstiller relasjonen

M B C H j£ M er inkonsistent.

- 31

-3 . 2 . -3 QotuiHl inengde_av konsistent£ beslutriing er Di maksimal konsistent mengde av beslutninger MB er optimal hvis for a l l e aeimengu^r M^C m,

|m I > {m b I er inkonsistent.

3 .3 Inkonsistente mengder av beslutninger

3 .3 .1 M_Lnijoal£ j^ton s is tente mengde£ a v_bes i. u tninge r Ei minimal inkonsistent mengde av beslutninger er ei mengde scm er inkonsistent og som også er s lik at ingen d el

mengde av mengda er inkonsistent.

3 . 3 . 2 Minimale kutt-mengder

L a ff[ være mengden av minimalt inkonsistente deunengær av M. la C & M være en mengde s lik at

m t f f l MBflC f ø.

C kaller v i en kutt-mengde. Bi kutt-mengde C er minimal hvis

|CjJ>|c| for a l le kuttmengder Cj for .

Det er klart at det for et g it t materiale gjerne kan være flere minimale kutt-mengder.

3 .4 Antall uforklarte beslutninger

La Fjlw) være en funksjon som er 0 hvis beslutning i er forklart og 1 hvis beslutning i er u fork lart. A itallet uforklarte b eslu tn in g er,F, for materialet for en vektor w kan vi nå uttrykke s l ik :

i * ~ n F(w) = 2 L F, (w)

i' = 1

Vi har følgende sanmenheng i neilom FB^ og F^:

F B ^ w ) F i (w) = 0 og I F B ^ w ) ^ Fi <w) = 1

- 32

-3 . 4 . 1 Problemet med å finne et_optimalt konsis tent_mat-eriale

Oppgaven t il aARA kan nå uttrykkes svært enkelt, nemlig minimaliser F . Det v il s i : Finn en vektor w slik at F antar sin minimale verdi.

EXsempel 3 .2 . Minimal F.

La V være som i eksemplet foran.

; i o

0 -1 i

0 -1 ⁱ

-i i 0

-i -i

w

Fra beslutning 1 har vi at wj>w3 , tra beslutning 2 at w > w ,, fra beslutning 3 at w3>w2' ^ca beslutning 4 at

og fra beslutning 5 at v ^ + v ^ w ^ . Fra

beslutning 1 og beslutning 2 følger at w Dette

strider mot beslutning 4. Beslutning 1 strider mot beslutning 5.

Foreløpig konklusjon: A lle beslutninger kan ikke forklares av modellen. 1 eller 2 beslutninger v i l ikke b li forklart. Eir F=1 eller er F=2? Vi ser at hvis W ^w j+ W j og så er F=l. Da er det bare beslutning 1 som ikke forklares. Vi har da manuelt funne*- ei optimal løsning. Alle vekter der w^> og w ^ v ^ , Wj?0, w2>0 og

w.>o er optimale løsninger på problemet vårt. I a lle t ilfe lle r er F=l.

3 .4 .2 L<asn_in£S£OiTi for vekLc/ie

Et løsningsrom for ei mengde av beslutninger er ei mengde WM-M1^ WM1 * 0

hvor M-Ml er e i optimal konsistent mengde av oeslutninger.

- 33

-3 .5 Dominerinqsbegrepet og noen størrelser knytta t i l det

De argumentene som trekker i samne retninga som resultat

et kaller vi dominerende argumenter i beslutninga. De argument

ene som trekker i motsatt retning kaller v i dominerte argument

Forholdet mellom antallet dominerte argumenter i ei beslutning og a n ta llet dominante kaller vi dominans forholdet for beslutninga. Dominansforholdet, CF, er altså defin ert som

, _ ACE(i) representerer gjennomsnittet av vektene på de dominante argumentene ved \T , og gjennomsnittet av vektene på ae dominerte argumentene med w’^ , så har vi

- 34

-WDA ^ D P I1* ' w d e"

Vi bruker altså dominansforholdet for beslutninga og

gjennomsnittsvekta tor de ocminerte argumentene t i l å uttrykke en nedre grense for gjennomsnittsvekta på de dominante

argumentene for at beslutninga skal b l i forklart.

Om vi nå ikke vet mer om vektene på argumsntene enn disse dominansforholdene for beslutnigene, så kan det være en mulig

het å ta utgangspunkt i disse i forsøket på å finne rram til vekter som gir en mest mulig konsistent modell av beslutningene.

Antallet g a n g e r ,B E A (j), argument j har vært et dominant argument i materialet er g it t ved:

BDA(]) = 2 1 D M 1 ' ! )

i = 1

og antallet ganger argument j har vært dominert, B U E (j), ved n

BEE(j) = 5 ; D E (i ,j ) i = 1

Vi kan nå definere et par interessante størrelser. Uet gjennomsnittlige dominansforholdet i de beslutninger hvor argu

ment j er et dominant argument er:

^ ■ r a r i .

Det gjennomsnittlige dominansforholdet i de beslutninger hvor argument j er e t dominert-argument er:

1 n

GDE(3) = BDE(J~) DE<i 'J> *DF(i) Eksempel:

La oss s i at vi har følgende fem beslutninger:

( l - 1 0 1 - 1

10 1 1 - 1 1

V = 1 0 1 - 1 1

-1 1 -1 - 1 1

- 35

Nedator er de størrelsene som er aetinert i aette av -snittet lista opp.

DA ALA UE AUE UF

0 0 1 0

' <2 fQ j.

0

0 1 f 2 (

1 0 1 1 0 1

i U U

0

1 0

1

1 /3

0 1 0 1

0 0 0 1 0 1

1 /3

0 1 0 0 1 2 1 0 1 1 0

3 3 /2

1 0 0 0

2 0 0 0 1

_{u /}

W /

ⁱ

W

BUA (3

2 2 1

4) BUE (i

1

± 4 u

GDAi

11

l l

1 2

GUE ,3 3 i

18 12

1

Ï .

l2

ⁱ

2

3 .6 Nettverk av peslutm nqer

Vi Kan representere beslutningene som to noaer meu en retta kant mellom. I noaen ved starten av aen retta Kanten representerer v i ae dominante argumentene i oeslutninga. ug i nouen vea slutten av den retta kanten representerer vi ae dominerte argumentene.

Hvis v i nar ei oeslutning > Wj +v7 , s<5 kan vi representere denne oeslutninga s l i c

K Ø

Vi representerer da domirante og aominerte argumenter vea aeres ircieKsmenguer. Hvis vi også nar ei beslutning

W3 +w7^w4 + w i ' ^ ser vl at olsse to oesiutm ngene t il saninen kan representeres vea

3 .7 Utleaa reslutninger

Hvis v i tra ei beslutning vet at wl +v2> w3+w4

og tra e i anna oeslutning vet at

- 36

-w3> w2

så kan vi trekke ei interessant slutning. Por at begge beslutningene skal forklares så må

V v

- 37

- 38

-3 .7 .1 Grunn lage t_f or _noen utledrunger

I SARA-rapporten på side 100 er grunnlaget for 8 typer utledninger skissert. Jeg bruker samne nuimerering på utled

ningene som i rapporten. kaller vi ei reduksjonautledninq (kortere:reduksjon) hvis antallet argumenter i den reduserte beslutninga er minor“ enn utledninger verken er en reduksjon eller konstruksjon generelt.

Vi ser og at for eksenfiel c3 er en reduksjon hvis AUE(i) > ADE( j) og AOA( j) > ADA(i) .

- 39

-3 .7 .4 Utled nuK^s tre

Ei utledet beslutning kan selv inngå i a n ttæ d enten i ei ny utledning. Det kan derfor være hensiktsmessig å tenke seg utledningene representert som et tre. Anta a t vi har

F B ^ F B j ,

for ei ei mengde I av beslutninger og for e i beslutning j . La 11/ = r - " • ' xrl ‘ Vl * an representere

utledninga s l i k :

Rota i treet v il da være det endelige resultatet av utledningene. Hvis |l| = 2 er treet Dinært.

Det er ganske innlysende at to utleaningstrær for å u t

lede samme beslutning ikke trenger vatre identiske.

Utledningstre der hver utledning er en reduksjon kaller vi reduksjonstrær ■ Er a lle utledningene konstruksjoner kaller vi treet konstruksjonstre.

Ut p være det største antallet argumenter i de beslutningene som det skal reduseres fr a . Representerer v i utledningene i et tre så vet vi at dyDden i treet er mindre eller lik fH-1. Det er slik siden antallet argumenter rf>auseres med minst 1 for hver reduksjon, og antallet argumenter i den endelige beslutninga er "> 0.

Ia så p være det mir^ste antall argumenter i de beslutninger som det skal utledes fra vea konstruksjoner.

Antallet nivåer i Lreet for å representere konstruksjonene er mindre elle r lik m-p.

3 . 7 . 5 EXseupei_på reduksjons tre

La oss s i at v i har følgende tre beslutniger:

- 40

-2 5 . 8 , 9

( T T Z t ) --- ^ , 5 , 6 ,8.9)

0 O— O

1 /2 ,3 ,7 5 ,8 ,9

4 ,5 ,6 ,8 ,9 X 3,7

Ni

1,2

*,f> "v ^ 1 , 2

Altså er de tre ovenstående beslutningene inkonsistente.

3 .7 .6 Hv i l^e_u tlednir>ger_bør_u tf øres £

& i kunne tenke seg at en utleda alle beslutninger som er mulig å utled«; ved reduksjoner fra et materiale M. Ville en da klare å utlede alle motsigelser? Vi skal nå vise at dette ikke a lltid er tilfe lle

(Sats 3.5) EA kan ikke utlede alle motsigelser uten kons truxsjoner

Jeg skal vise det ved et ensempel:

Vi har følgende materiale:

- 41

-f e ) ---* © © --- > ©

(5)—^5) ©^— Q)

Vi kan ikke utlede motsigelsene uten å gjø re en konstruksjon.

Bruker vi konstruksjon, for eksempel på de to første beslut

ningene får vi

Av denne beslutninga og beslutninga

@ e - 0

kan vi så utlede

som strider mot beslutninga

@ e - @

Altså har vi utleda en motsigelse.

(Sats 3 .6 ) & i kan ikke utlede a l l e motsigelser uten reduksjoner

I for eksenpel følgende situasjon trengs reduksjon:

© — i►©

- 42

-Ved to reduksjoner kan vi utlede

( S ) '5© ^ 0 Ø ^ / © -* © 0 <9 J 0 O l© - ^ © ■

3.7 . 7 Beskrivelse av_u^edninger_ved_hjelp_av verdiene forjaeslutm ngene

(Sats 3.7) Hvis vi for ei mengde I av beslutninger og ei b e s l u t n i n g j som ik k e e r s e l v m o t s i g e n d e h a r a t

vj ^ c i ' vi ' V - 0 Ifc I

så følger det at F B j F B j

.

Bevis: Hvis I er inkonsistent er dette t r iv ie l t . La w é W r w é - W j ^ < t / i f c D : V - w > 0 .

( V i 6 I) : V.. w > 0 A ‘‘,2 0 A Vj =Z c i ’V i l t I V. -w>0

< ^ > w é W . .

Vi har altså vist at w f " , = $ «6^ Det v il s i at w. , som er ekvivalent med at F B j = ^ KB . ®

Vi har altså vist at

V^ v i ' C!- 0 Deskriver ei utledning av i6 I

beslutning j .

(Sats 3 . 8 ) Anta at vi har Vj = 2 c i v i - c i ^ °

i fe I

og er et rasjonalt ta ll. Det medfører at det fins n t og Oj slik at

Vj = (l /n j) •

2

^{n i-Vx}

i 6 l

der n.. og alle n i er naturlige ta ll.

- 43

-B evis: U mfn være minste felles nevner for a l l e c , c i = Pi

Ali-mfn-V^ = 2L m fn(pi/ q i )V i 1 ^ 1

mfr'(P i/ q i ) = n t er et naturlig tall og n^ = mfn er også det. Ergo har v i at

Vj = (l/h .,) ^ n r V i • i 6 I

Vi kan nå s i at n^ uttrykker a n tallet ganger beslutning i har vært involvert i utledninga av n ■ V ^ .

Det v il vasre av interesse å finne ei ervre grense for n t for eventuell utledning av V ^ . Ei øvre grense på n± v il angi hvilke mulige komoinasjoner av som eventuelt kan danne grunnlag for utledning av V ^ .

Jeg antar at det fin s ei slik grense og at den er avhengig av kardinaliteten t il I U E . Jeg har ikke sett nærmere på dette problemet.

Ser vi nå tilbake på utledningsreglene cl-10 fra 3 . 7 . 1 så får disse e i svært enkel fortolking, c l-2 utledningene er utledninger en oppnår ved addisjon av tr iv ie lle beslutninger.

c6 -7 utledningene er overflødige på grunn av at verdiene viser netto antall ganger et argument har forekommet som dominant eller dominert. De øvrige utledninger er utluaninger ved addisjon av to beslutninger, som enten er fra materialet eller som er utleda fra m aterialet.

EXsenpel på beskrivelse av utledninger ved *i]elp av verdier:

- 44

-V6 = V1 + 2V2 + V4 - V3 + V5

La I være e i mengde av beslutninger og c en

koeffisientvektor av ikke-negative koeffisien ter der c i er g it t for alle i t I . (c ,I ) kan representere verdien t il ei utleda beslutning j ved at

v 2

c i ' V c ii 0 i e i

Det er klart at er entydig bestemt.

Hvis ni I er konsistent og ingen beslutning i I kan utledes fra andre beslutninger i I , v il det da t il eihver beslutning j fins entydige koeffisienter s lik at

Vj = i T Ci V i ' Ci ~ ° J ifc I

Svaret er n e i, og her er et eKsempel:

1: Wj 4v2 > Uj 2: w1 +w3> w2 +w4 3: +w6> w ? 4: -j 4«7 >w6

5 : wx> w4 Vi har at

V5 = 2 V1 + 2 V2 = 2 V3 + 2 V4

-(Sats 3.9) Beslutning i begrenser Kj hvis og bare hvis

™ r

_W

^{F B ,.}

Bevis: ' WT c Wj , fiJ Wr . ^ 0Wi C Mj _ / l

r e i -fl

J &

^ i - *

Denne satsen gjelder sjølsagt også hvis Vij er et løsningsrom.

(Sats 3.10) For enhver niaksuiialt konsistent uengae av beslutninger Ml gjelder:

WM1 - WM - Ml-

Bevis: for alle j & M - Ml har v i:

‘S u 0 °

E t g o v ^u c ^ _ M l . ■

- 45

-Denne satsen gjelder sjølsagt også om Ml er optimalt konsistent. Ergo gjelder følgende korrolar t il sats 3 .1 0 :

Uforklarte beslutninger oegrenser iKke et løsmngsrom . FOr et materiale kan v i beskrive et løsmngsrom ved de er ganske kompakt sanmenligna med utledningstrær.

Vi skal senere vise at for konsistent I :

- 46

Jeg skal illustrere disse fire parallellitetstypene vea Venn-diagram og ved utsagnstabeller.

^ T F B i ) I F B j )

==? F B ^

3 .8 .1 Implikasjoner mellam_torklaringer

Det kan altså være slik ) et inateciale at hvis ei oeslut-

- 47

-For å overblikke saimenhengene mellom implikasjonene tror jeg det er gunstig å representere dem i en g r a f, i stedet for som ei lis te av par ( i , j ) , ( i , k ) , ( j , l ) , (j ,m) , (k,m) , ( i , l ) og

(i ,m ) . La oss representere beslutningene som noder l grafen.

representerer beslutning i .

La en retta kant fra beslutning i t i l beslutning j representere at FBj FB^.

□ o

Alle nooene i grafen som ikke har noen grein inn t il seg kaller jeg en toppnode.

Det kunne også være inter

essant å l is t e opp ijrplika- sjoner mellom mengder av be

slutninger. Men her får en

store antall s lik e mengder s lik at undersøkelsen ikke lar seg gjennomføre i praksis for store r a te r ia le r . El anna mulighet er å begrense mengdene t i l 2, 3 eller maks 4 elementer hvis antall ikke-trivielle beslutninger er større enn 1 0 0. Dette har jeg ikke forsøkt.

tmplikasjonsgrafen er bygd opp på grunnlag av iølgende erkjennelse:

(FB FBn A FB =t> FR )

1 J J K

(FBt •=*> FB^J .

Det v il s i at inqolikasjonsrelasjonen er tra n sitiv .

Jeg skal nå definere to relasjoner som er vanlige å bruke i grafer, j er en etterfølger t il i , og i er en forgjenger til j i implikasjonsgrafen hvis det fins oeslucninger k ^ , k j , . . . . kp der

FB. •=*> FB, -*> FB...=^FB„^- < FB

S * 2 * t > 3

- 48

-Hvis beslutning i i grafen er forklart, ]a aa er a lle etterfølgere til i forklart. Og er beslutning j i grafen uforklart cia mi alle forgjengere til j være uforklart.

3.8 .2 Motsigelse£ me 11 am_oes 1 utnlngej:

Det er ekvivalens mellom utsagnene: beslutning i strider mot beslutning j - og - FB^ T F B ^ .

Vi har at

(FB, T F B 1

3

< = ? (FBj T F B i ) . Derfor gjelder ekvivalensen foran.

Siaen motsigelsesrelasjonen mellom par av reslutm nger er synmetrisk v il ei utskrift av par av æ slutn in ger som strider mot hverandre være nokså informativ. Beslutning i strider mot beslutning j v il ]eg illustrere s lik :

□HU

For dette tilfe lle t har vi altså at:

Wj » a .

Det er ei mulighet som ikke kan inntreffe ner også. Det er at begge beslutninger er forklart.

3 .8 .3 Beslutning_i_uforkl:a£t_impl^isere£ o e s lu t n in g j forklar^.

Dette er den siste typen p a r alle llitet mellom to beslut

ninger. Den er også synmetrisk.

-7 F B .

F T

FBX F F T

T T T

Den muligheta som ikke kan inntreffe her er a t regge beslutningene er u forklart.

Por den s is te muligheta hat vi

1 T F B j

<=£> FB3 =^> FB1

Ergo danner denne muligheten ikke en ny type avhengig net. For ordens skyld kan vi vise Venn-diagram og utsagnstaoell for denne muligheta også.

-lFBi =$> TFb^

F ™ 3 T

FB j P

I

^T ^F

T I T T

Her kan ikke Deslutning i vaere ufork i3rt og j fork lart.

3 . 8 . 4 Spesi.e_Lle £a£aLlelJ.i^etsreLasjoner

Por hver av de fire mulighetene tor p a r ax le llitet d e fin erer vi en relasjon mellom to beslutninger i og j .

(1) Helasjonene.

Fbrklart-forklart-relasjonen.

FB^ i FF j . Jeg kaller forklart-forklart relasjonen FF.

- 50

-Forklart-uforklart relasjonen.

FB^ i FU j . Jeg kaller Eorklart-uforklart relasjonen for FU.

Uforklart-forklart relasjonen.

TFB^ = ♦ fBj <é=i> i UF j . Jeg kaller uforklart-forklart relasjonen for UF.

Uforklart-uforklart relasjonen.

"fFB^ -=p iF b j i UU j . Jeg kaller uforklart-uforklart relasjonen UU.

Den tekstlige representasjonen av relasjonene er satt sairmen av to forklaringstilstanas-konstanter. Hver av dem er enten F for forklart eller U for uforklart.

(2) Egenskaper ved de spesielle parallellitetsrelasjonene.

Jeg skal bare se på egenskapene refleksiv, synmetrisk og transitiv.

FF FU UF UU

refleksiv ja nei nei 3a

synmetrisk nei ja ja nei

transitiv nei nei ja

Tfcoell 3 .1

(Sats 3.1 1 ) Parallellitetsrelasjonene er innbyrdes eksklusive. (Det v il si at for to beslutninger i og j fins det bare en parallellitetsrelasjon R s lik at i R j er o p p fy lt ).

Bevis: Jeg skal vise dette for FF-relasjonen: Anta altså at i FF j . FBi = $ F B j . Da holder ikke FU- relasjonen. Hvis i UF j også skulle holde så måtte TFB^ f b^ . Da måtte FB.. være en tautologi, i strid med forutsetninga om ikke-trivielle beslutninger.

Hvis i UU j også skulle holde så måtte j FF i også holde.

Da måtte beslutningene være identiske, i strid med forutset

ninga om ulike beslutninger. (Ftir Jtsetningene er presisert i innledninga til 3 .8 .) ■

Samrensettinq av parallellitetsrelasjo n er er m ulig. Hvis vi har at en relasjon S gjelder inellom beslutning i 09 ] ,

Tfeoell 3 .2 over sammensetting av parallellitetsrelasjo ner

La oss representere en forklaringstilstanas- variabel med X. Hvis i x j x^, j g je ld e r så s k a l det oety at hvis

52 av de inverse til parallellitetsrelasjonene. •

3 .8 .5 Parcdlellite^sanal^se av_et nyater^ale

Ponnålet ined dette er for hvert par av beslutninger 11 »3)

3 .8 .6 Qi_måte å re£resen^e£e_jMrallellitetsrelasjoriene på i_ en_g£af grafen og motsigelsesgrafen var egenskapene mellom beslutning

ene lett å lese ut fra gratenes struxtur. Men Hvordan sKulle vi representere alle fire relasjonene 1 én graf sliK a t egenskap

ene lett skulle kunne leses ut? Det er 30 innlysende at den manuelle bruksverdien til grafen et proporsjonal med hvor enkelt egenskapene i grafen kan leses ut av den.

-Det er særlig ett problem som er vanskelig å lø se. -Det er raskt å gi brukeren oversikt over for eksenpel, alle beslutninger som kan utledes fra ei beslutning, - a lle motsigelser melloni to og to b eslutninger, osv.

Det var sats 3 .1 3 som leda fram t i l den nåværende representasjonen av relasjonene.

Grafisk v il vi representere parallellitetsrelasjo n en e s lik :

i FF j representeres

i FU j representeres

i UF j representeres

i UU j representeres

&

<> 3

i (►

■£]

-*n

- ø Et diagram av parallellitetsrelasjo n er leses s l ik : Fra svart halvsirkel - langs en kant - t i l hvit h alvsirkel.

Halvsirkel inne i nodeboks oetyr fork lart, halvsirkel utafor nodeboks betyr u forklart.

Vi kan enxelt kontrollere at representasjonen er entyoig.

Det inkluderer at den er uavhengig av leseretning.

Relasjonene 1 FU 2 , 2 FF 3, 4 UU 3 , 3 FU 5 , og 3 UF 6 kan vi repcesentere s l ik :

Bi s ir k el som er knytta t il en node kaller jeg et knutept ct. Sirkler som representerer knutepunxt består a lltid av en svart og en hvit h alv sirkel. Ftolgelig kan v i ved nver node ha maksimalt to uliKe knutepunkter.

Hvis to beslutninger er knytta til ei treaje beslutning ved motsatte knutepunkter sier vi at beslutninga er transient med hensyn p5 parallellitet mellom beslutningene. Populært kan vi si at beslutninga "videresender" parallelliteten mellom beslutningene. For eksempel er 3 transient for 2 og 5 i grafen Siden veien er transient gjelder

- J W -i .

Ftolgelig gjelder i X1 Yr J . '

-Vender vi nå tilbake t i l eksempelgrafen så plukker vi lett ut følgende informasjon:

FB1

fb 2 = £

(i

f b 5 A fb 4 A f b 3 ) , l F B ft (FB3 /»FB4 A T F B 5) . Vil vi gå fra 5 så har vi

FB5

■=?

⁽

7

FBj A FBg A T F B j ) .

3 .9 Partisjon av materialet

tn partisjon , P, av materialet er ei mengde av delmengder av materialet s lik at alle beslutninger tilhører e i og bare ei delmengde. La 71 ^ være den i-te delmengda som partisjonen deler materialet inn i av i alt r for m aterialet.

P = { X , TT2...JTr ] -TTi 0 JT-j = 0, for i * j . TTi u ^ 2 w ^ 3 • • • ^ T 7 ~ w m.

3 . 9 . 1 Konsistente^ E a r t is ^ o n e £ a y _m a t e r ia l e t

La P ^ T I j , ... ' ^ r ^ Vdere en Pa r t l s 30n av m aterial

et M. Vi kaller partisjonen en konsistent partisjon hvis TT , for a lle i er en konsistent mengde beslutninger.

3 .9 .2 Minimal kpnsi_stentjM rtisjon_av naterialet La P ..., T f J være en konsistent p a r ti

sjon av n eterialet M. Partisjonen er en minimalt konsistent partisjon hvis det ikke fins noen konsistent partisjon av M med feer re deler enn r.

Det v i lle nå være svært nyttig om det var s lik at ctet minimale antallet konsistente partisjoner for et materiale av

ikke-trivielle beslutninger var £ 2.

La MB være en op tiral konsistent mengde. Er da

komplementet MB' t i l MB konsistent? Kunne vi svare ja på dette spørsmålet så var det s lik a t det minimale antallet konsistente partisjoner var i 2 . Men det er dessverre ikse s l i k . Jeg Skal vise et eksesnpel med tre beslutninger der alle tre

beslutningene strider mot hverandre.

0 ---s @

0 --0

© -->©

Jeg har ikke gjort mer arbeid med partisjoner enn det l i l l e som er beskrevet her. Men det er absolutt et område som det kan svare seg å granske nærmere ved anledning. For eksempel kan det være av interesse å bestenme minimale Konsistente partisjoner for et materielle.

-4 MATfcMATISKE EGENSKAPER VED MATERIALET

4 .1 Representasjon av beslutningene i et m-dimensionalt vektorrom

Vi antar at hver beslutning har m mulige argumenter, ta R"1 være et m-dimens]onalt vektorrom.

4.1 . 1 Regresentas jon_av velt te ij_ verdiex ^ _ o e s Ki tn_i rig er_

Et punkt i rcxnmet tolkes som vektene på de m argumentene Et punkt w i rommet angir v i vea .sine koordinater,

W = <V w2 , . . . wm) .

Mengda av a lle punkter som tilfr e d s s tille r ulikheta V t . w > 0 eller V ^ w < 0 kalles åpne halvrom. Ei

beslutning kan vi representere ved V . w > 0 . Hermed danner ei beslutning et åpent halv-rom i Rm. Ei likning V • w = 0 i et m-dimensjonalt vektorrom aanner et hyperplan.

Verdiene til argumentene i ei beslutning representerer normalen t i l hyperplanet bestemt av beslutninga. Et hyperplan er karakterisert vea en normal t i l planet og et punkt i planet La V. være en vektor i romnet. Da tilnører a lle punktene w, hvor V^ . w = 0 dette hyperplanet. V x er altså normalen til hyperplanet.

4 . 1 . 2 Konvekse_ffk=i^aer

Ei mengde w er konveks hvis for to punkter Xjfc y og x~ 6 W, Å x^ + (1 - Å ) x2 t w, når 0 £ A i 1.

Noen velkjente resultater om konvekse nengaei -Et åpent halv-rom er ei konveks mengde, og -snittet av to konvekse mengder er konvekst.

-4 .1 .3 Konvekse_koner

Eli mengae KK^R™ som er lukxet unaer aaaisjon og lkke-negativ multiplikasjon kalles en Konveks kon.

La x og y være elementer i KK og j.a A i U være et reelt t a l l . Da er altså

x + y é KK og KK

Tre velkjente egenskaper ror xonveKse koner:

-Konvekse koner er konvekse mengaer.

In document ET EDB-SYSTEM FOR (sider 31-64)