Giáo trình Công nghệ phần mềm - Phan Huy Khánh (Phần 2)

= ∅ keïo theo (f \ s) og = fog (5.3) 
dom (f) ∩ ran (g) = ∅ keïo theo fog = { } (5.4) 
Biãøu thæïc { } chè âënh haìm räùng 
f o (g \ S) = (fog) \ S (5.5) 
{ x → y } o { x → u } = { x → y } (5.6) 
Tæì caïc luáût trãn, ta coï thãø âån giaín hoïa pheïp thay âäøi biãún âaî âënh nghéa åí 
(4.2) nhæ sau : 
p = m o a 
q = m o n (5.7) 
Vaì ta coï thãø chæïng minh dãù daìng âënh lyï phuì håüp (4.5) bàòng caïch sæí duûng caïc 
tênh cháút trãn. Tháût váûy, ta cáön chæïng minh hai âàóng thæïc sau âáy : 
m’ o n’ = (m o n) + { x → y } 
m’ o o’ = m o a 
Nghéa laì : 
(m + { u → y }) o (n + { x → u }) = (m o n) + { x → y } 
Âàûc taí 141 
(m + { u → y }) o a = m o a 
våïi caïc giaí thiãút : 
u ∉ ran (n) nghéa laì { u } ∩ ran (n) = ∅ (5.8) 
u ∉ ran (a) nghéa laì { u } ∩ ran (a) = ∅ (5.9) 
Ta coï kãút quaí phuû nhæ sau : 
(m \ { u }) o (n \ { x }) = (( m \ { u }) o n) \ { x } theo (5.5) = (m o n) \ { x } 
theo (5.3) vaì (5.8). Nhæng : 
{ x → y } o (n \ { x }} = { } 
theo (5.4), (2.2) vaì (5.8). Vaì ta cuîng coï : 
(m \ { u }) o { x → u } = { } 
theo (5.4) vaì (2.2) 
{ u → y } o { x → u } = { x → y } 
theo (5.6) 
Nhæ váûy theo (5.2) vaì (2.5) : 
(m + { u → y }) o (m + { x → u}) = (m o n) \ { x } ∪ { x → y } = (m o n) + { x → y } 
Màût khaïc ta coï : 
m \ { u } o a = m o a theo (5.3) 
{ u → y } o a = { } theo (5.4) 
Nhæ váûy : 
(m + { u → y }) o a = m o a theo (2.4) vaì (5.3) 
IV.6. Triãøn khai thæï hai 
Muûc naìy seî täúi æu caïch triãøn khai âáöu tiãn âaî trçnh baìy trong muûc 4 bàòng caïch 
xáy dæûng táûp håüp L caïc âëa chè tæû do cuía D, táûp håüp maì ta âaî choün tuìy yï mäüt pháön 
tæí u trong âàûc taí pheïp toaïn mod1 åí (4.3). 
YÏ tæåíng thiãút kãú caïch triãøn khai thæï hai naìy nàòm åí chäø giæî laûi traûng thaïi cuía 
mäùi âëa chè cuía D maì âëa chè naìy coï thãø thuäüc vãö mäüt (vaì chè mäüt maì thäi) trong 4 
táûp håüp råìi nhau nhæ sau : 
RN _ RN 
RA ∩ RN 
RN _ RA 
RA ∪ RN = L 
trong âoï RA = ran (a), RN = ran (n) 
TS. PHAN HUY KHAÏNH biãn soaûn 141 
142 Cäng nghãû Pháön mãöm 
Tuìy theo mäüt âëa chè d cuía D thuäüc vãö mäüt trong bäún táûp håüp trãn, ta noïi traûng 
thaïi tæång æïng seî laì : 
old (cuî) d ∈ ran (a) 
common (chung) d ∈ ran (a) vaì d ∈ ran (n) 
new (måïi) d ∈ ran (a) 
free (tæû do) d ∉ ran (a) vaì d ∉ ran (n) 
Khi mäüt âëa chè tæû do âæåüc choün, khi mäüt thay âäøi xaíy ra, âëa chè âoï chuyãøn qua 
traûng thaïi måïi ; vãö âëa chè quaï taíi trong baíng n, nãúu âëa chè âoï khäng phán chia 
bãn trong baíng n (nghéa laì nãúu haìm nlaì âån aïnh vaì âiãöu naìy âæåüc giaí thiãút laì luän 
âuïng), khi âoï, âëa chè seî tråí nãn tæû do nãúu âaûng åí traûng thaïi måïi hoàûc chuyãøn sang 
traûng thaïi cuî nãúu âang åí traûng thaïi chung. 
Khi mäüt pheïp håüp thæïc hoïa hay khåíi âäüng laûi caïc âëa chè tæû do hay chung váùn 
nhæ cuî. Caïc âëa chè måïi chuyãøn thaình tæû do khi mäüt sæû khåíi âäüng laûi vaì laì træåìng 
håüp chung khi håüp thæïc hoïa. 
Cuäúi cuìng, caïc âëa chè cuî chuyãøn thaình tæû do khi håüp thæïc hoïa vaì tråí thaình 
chung khi khåíi âäüng laûi.Chuï yï ràòng caïc âëa chè cuî khäng liãn quan âãún sæû thay âäøi. 
Så âäö dæåïi âáy toïm tàõt mäüt caïch phi hçnh thæïc nhæîng chuyãøn âäøi khaïc nhau naìy. 
Muûc âêch âãø hçnh thæïc hoïa phæång phaïp naìy, ta âæa vaìo mäüt biãún måïi s âënh 
nghéa traûng thaïi cuía mäùi âëa chè cuía D. 
s ∈ D → {fr, nw, cm, ol} (6.1) 
Ta coï báút biãún sau âáy : 
RA - RN = adr (ol) 
RA ∩ RN = adr (cm) (6.2) 
RN - RA = adr (nw) 
RA ∪ RN = adr (fr) 
HÇNH VEÎ 
Trong âoï : 
RA = ran (a) 
RN = ran (n) 
adr (z) = {x ∈ D / s (x) = Z} 
våïi Z ∈ {fr, nw, cm, ol} 
Cuäúi cuìng báút biãún thæï ba chè roî ràòng caí hai haìm n vaì a âãöu âån aïnh, nghéa laì 
hai âëa chè cuía A phán biãût seî luän luän tæång æïng våïi caïc âëa chè cuía D phán biãût 
qua caïc haìm naìy. 
Táûp håüp caïc haìm tæì A vaìo D nhæ váûy âæåüc kyï hiãûu 
båíi A ⌡ D nhæ váûy 
Âàûc taí 143 
n ∈ A ⌡ D 
a ∈ A ⌡ D 
Báy giåì seî laì âënh nghéa ba haìm chuyãøn tiãúp láön læåüt laì f, g vaì h sæí duûng khi 
thay âäøi (cho caïc âëa chè cuía D liãn quan), khåíi âäüng laûi thay cho håüp thæïc hoïa (cho 
moüi âëa chè cuía D) : 
f = {fr → nw, 
nw → fr, thay âäøi 
cm → ol} 
g = {fr → fr, 
nw → fr, 
cm → cm, khåíi âäüng laûi 
ol → cm} 
h = {fr → fr, 
nw → cm, 
cm → cm, håüp thæïc hoïa 
ol → fr} 
Ta coï âàûc taí cuía 3 pheïp toaïn måïi mod2, rst2, vaì vld2 xuáút hiãûn nhæ laì caïc måí 
räüng tæång æïng tæì muûc 4 : 
(a, n, m, s) mod2 (x, y) (a’, n’, m’, s’) 
(a, n, m) mod1 (x, y) (a’, n’, m’) (6.5) 
s’ = s + {u → f (s (u)), v → f (s) (v))} 
xem (4.3) 
trong âoï : 
L = { Z ∈ D |s (z) = fr } 
u ∈ L 
v = n (x) 
(a, n, m, s) rst2 (a’, n’, m’, s’) (6.6) 
s’ = gos xem (4.6) 
(a, n, m, s) vld2 (a’, n’, m’, s’) (6.7) 
(a, n, m) vld1 (a’, n’, m’) xem (4.7) 
s’ = hos 
Sau âáy laì mäüt quaï trçnh chuyãøn âäøi cuía hãû thäúng 
CHÆÌA 
Chæïng minh 
TS. PHAN HUY KHAÏNH biãn soaûn 143 
144 Cäng nghãû Pháön mãöm 
Màûc duì trong muûc træåïc ta âaî kiãøm chæïng kyî læåîng âàûc taí hãû thäúng vaì nháûn 
âæåüc kãút quaí thoîa maîn, nhæng chæa âaím baío âæåüc tênh âuïng âàõn cuía âàûc taí trong 
moüi træåìng håüp. 
Âãø âi âãún mäüt kãút quaí täøng quaït, ta cáön phaíi chæïng minh khäng phaíi cho mäüt 
træåìng håüp âàûc biãût naìo âoï maì phaíi cho caïc dæî liãûu tæåüng træng thoía maîn nhæîng 
giaí thiãút naìo âoï, caïc pheïp toaïn âaî âàûc taí laì phuì håüp vaì cháúp nháûn âæåüc. 
Viãûc chæïng minh tênh phuì håüp cuía caïc pheïp toaïn âàûc taí åí (6.5), (6.6) vaì (6.7) so 
våïi caïc pheïp toaïn âàûc taí åí (4.3), (4.6) vaì (4.7) laì hiãøn nhiãn vç ràòng trong caïch láûp 
caïc cäng thæïc thç caïc pheïp toaïn (4.3), (4.6) vaì (4.7) mäüt caïch tæång æïng. 
Traïi laûi, viãûc chæïng minh tênh cháúp nháûn âæåüc phæïc taûp hån. Træåïc hãút ta cáön 
chæïng minh ba nhoïm âënh lyï báút biãún sau âáy : 
((6.1) vaì (6.5)) keïo theo (6.1)’ (7.1) 
((6.2) vaì (6.5)) keïo theo (6.2)’ (7.2) 
((6.3) vaì (6.5)) keïo theo (6.3)’ (7.3) 
((6.1) vaì (6.6)) keïo theo (6.1)’ (7.4) 
((6.2) vaì (6.6)) keïo theo (6.2)’ (7.5) 
((6.3) vaì (6.6)) keïo theo (6.3)’ (7.6) 
((6.1) vaì (6.7)) keïo theo (6.1)’ (7.7) 
((6.2) vaì (6.7)) keïo theo (6.2)’ (7.8) 
((6.3) vaì (6.7)) keïo theo (6.3)’ (7.9) 
Âäúi våïi 3 âënh lyï åí nhoïm 1, ta coï thãø dáùn âãún caïc giaí thiãút cho caïc âiãöu kiãûn sau 
âáy : 
a ∈ A ⌡ D 
n ∈ A ⌡ D 
u ∉ RN (7.10) 
u ∉ RA 
v ∈ RN 
Trong âoï u vaì âæåüc âënh nghéa åí (6.5) vaì RA, RN âæåüc âënh nghéa åí (6.2) 
chæïng minh (7.1) 
Âàûc taí 145 
Mäüt khoï khàn nhoí laì haìm chuyãøn tiãúp f âæåüc âënh nghéa åí (6.4) laì haìm bäü 
pháûn. Cáön chæïng minh ràòng s’ âæåüc âënh nghéa âuïng, nghéa laì caïc biãøu thæïc f (s 
(u)) vaì f (s (v)) trong (6.5) coï nghéa, noïi caïch khaïc ta coï : 
s (u) ∈ dom (f) 
s (v) ∈ dom (f) 
âiãöu naìy hiãøn nhiãn vç ràòng theo (7.10), ta coï : 
s (u) = fr 
s (v) = { nw, cm} 
vaì theo (6.4) ta coï 
dom (f) = {fr, nw, cm} 
Âãø chæïng minh (7.2) vaì (7.3) ta cáön kãút quaí sau âáy liãn quan âãún sæû quaï taíi 
cuía mäüt haìm âån aïnh thæìa nháûn maì khäng chæïng minh : 
f ∈ X ⌡ Y keïo theo f’ ∈ X ⌡ Y 
x ∈ dom (f) ran (f’) = r’ 
y ∉ Y - ran (f) y ≠ f (x) 
Trong âoï : 
f’ = f + {x → y} 
r’ = (ran (f) - {f (x)}) ∪ {y} 
chæïng minh (7.2) : Theo (7.10), (7.11) vaì (6.5) ta coï 
RA’ = RA (vç ràòng a’ = a theo (4.3)) 
RN’ = (RN {V}) ∪ {u} theo 7.11 
u ≠ v theo 7.10 
HÇNH VEÎ 
Xaíy ra hai træåìng håüp : 
1/ v ∈ RA, nghéa laì s (v) = cm 
Khi âoï : 
RA’ - RN’ = (RA - RN) ∪ {v} 
RA’ ∩ RN’ = (RA ∩ RN) - {v} 
RN’ - RA’ = (RN - RA) ∪ {u} 
RA’ ∪ RN’ = (RA ∪ RN) - {u} 
HÇNH VEÎ 
2/ v ∉ RA, nghéa laì s (v) = nw 
Khi âoï : 
RA’ - RN’ = RA - RN 
TS. PHAN HUY KHAÏNH biãn soaûn 145 
146 Cäng nghãû Pháön mãöm 
RA’ ∩ RN’ = RA ∩ RN 
RN’ - RA’ = ((RN - RA) - {v}) ∪ {v} 
RN’ ∪ RA’ = ((RN ∪ RA) - {u} ∪ {v} 
HÇNH VEÎ 
Nhæ váûy caïc chuyãøn tiãúp tæì s (u) vaì s (v) nhæ sau 
fr → nw våïi u 
cm → ol våïi v trong træåìng håüp 1/ 
nw → fr våïi v trong træåìng håüp 2/ 
Caïc chuyãøn tiãúp naìy tæång æïng våïi caïc chuyãøn tiãúp âaî chè ra båíi haìm g âënh 
nghéa åí (6.4) 
IV.7. Triãøn khai thæûc hiãûn láön thæï ba 
Láön naìy, ta giaí thiãút ràòng xaíy ra caïc sai soït cáön phaíi dæû phoìng nhåì hãû thäúng 
håüp thæïc hoïa vaì khåíi âäüng laûi. 
Giaí sæí caïc baíng a, n, m vaì s âæåüc caìi âàût trãn caïc thiãút bë nhåï khaïc nhæ sau : 
HÇNH VEÎ 
Tæì caïch täø chæïc naìy, ta muäún dæû phoìng caïc sai soït taïc âäüng lãn bäü nhåï trong 
bàòng caïch khåíi âäüng laûi tæì âéa. ÅÍ âáy, ta âaî caìi âàût caïc baíng s vaì s trong bäü nhåï 
trong våïi muûc âêch tàng tênh hiãûu quaí cuía pheïp thay âäøi bäü nhåï laì nhanh nháút coï 
thãø. 
Våïi muûc âêch trãn, viãûc khåíi âäüng laûi laìm thay âäøi baíng s tæì chênh noï (thæûc tãú laì 
s’ = gos theo (6.6)) khäng coìn coï taïc duûng næîa vç ràòng ta giaí thiãút ràòng bäü nhoï 
trung tám laì s seî khäng coìn næîa. 
Mäüt giaíi phaïp laì gáúp âäi baíng s lãn âéa cho mäùi láön håüp thæïc hoïa. Xáy dæûng 
baíng måïi t âæåüc tæång æïng våïi báút biãún nhæ sau : 
t ∈ D → {fr, cm} (8.1) 
Chuï yï ràòng ta khäng cáön moüi giaï trë caïc traûng thaïi âëa chè âéa vç ràòng t chè 
duìng âãø taïi sinh laûi baíng s khi khåíi âäüng laûi, tæì âoï ta coï báút biãún bäø sung nhæ sau : 
{x ∈ D | t (x) = cm} = ran (a) (8.2) 
Ta coï caïc âàûc taí måïi nhæ sau : 
(a, n, m, s, t) mod3 (x, y) (a’, n’, m’, s’, t’) 
(a, n, m, s) mod2 (x, y) (a’, n’, m’, s’) (8.3) 
t’ = t xem (6.5) 
(a, n, m, s, t) rst3 (a’, n’, m’, s’, t’) 
(a, n, m) rst1 (a’, n’, m’) (8.4) 
s’ = t xem (4.6) 
Âàûc taí 147 
t’ = t 
(a, n, m, s, t) vld3 (a’, n’, m’, s’, t’) (8.5) 
(a, n, m, s) vld2 (a’, n’, m’, s’) xem (6.7) 
t’ = s’ 
Dãù daìng chæïng minh ràòng caí ba âàûc taí trãn laì phuì håüp vaì cháúp nháûn âæåüc. Màût 
khaïc ta tháúy ràòng pheïp khåíi âäüng laûi taïi sinh bäü nhåï trong tæì âéa vaì chè tæì âéa maì 
thäi. 
Triãøn khai láön thæï tæ vaì láön thæï nàm 
Ta seî maî hoïa caïc giaï trë fr, nw, cm vaì ol nhæ haìm âån aïnh k nhæ sau : 
k = {(0, 0) → fr, 
(0, 1) → ol, 
(1, 0) → cm, (9.1) 
(1, 1) → nw} 
Sau âoï ta biãøu diãùn caïc haìm s vaì t nhåì ba chuäùi bit nhæ sau : 
b ∈ D → {0, 1} âãø biãøu diãùn s 
c ∈ D → {0, 1} 
d → {0, 1}âãø biãøu diãùn t (9.2) 
Cuäúi cuìng, thay âäøi caïc biãún tæång æïng våïi caïc âiãöu kiãûn sau : 
s (x) = k (b (x), c (x)) 
t (x) = k (d (x), 0) våïi x ∈ D (9.3) 
Giaí sæí laì pheïp buì (âaío ngæåüc bêt) nhæ sau 
0 = 1,1 = 0 (9.4) 
Ta tháúy coï thãø maî hoïa haìm f âaî âënh nghéa åí (6.4) nhåì hai pheïp buì vaì haìm h 
cuîng âaî dënh nghéa åí (6.4) nhåì pheïp sao cheïp vaì âàût lãö 0 tæång æïng våïi haìm : 
Z ∈ D → {0} (9.5) 
Ta coï 3 âàûc taí måïi nhæ sau : 
(a, n, m, b, c, d) mod4 (x, y) (a’, n’, m’, b’, c’, d’) 
(a, n, m) vld1 (a’, n’,m’) 
b’ = b (9.8) 
c’ = z xem (4.7) 
d’ = b 
Báy giåì ta chè cáön toïm tàõt laûi nhæîng gç âaî laìm cho âãún luïc naìy, nghéa laì mäüt 
màût, sao cheïp laûi caïc âàûc taí (4.3), (4.6) vaì (4.7) vaìo bãn trong cuía (9.6), (9.7) vaì 
(9.8), màût khaïc, nhoïm caïc báút biãún (4.1), (6.1), (6.2), (6.3), (8.1), (8.2) vaì (9.2) 
Âiãöu naìy laìm âæåüc bàòng caïch khæí caïc biãún tråí thaình dæ thæìa (chæïa s vaì t) båíi 
caïc pheïp thay âäøi biãún (9.3). 
TS. PHAN HUY KHAÏNH biãn soaûn 147 
148 Cäng nghãû Pháön mãöm 
Khi sao cheïp, ta tháúy ràòng âàûc taí (4.3) chæïa âiãöu kiãûn træåïc L ≠ ∅ khäng dãù gç 
tênh âæåüc. Âãø khàõc phuûc nhæåüc âiãøm naìy ta âæa vaìo mäüt biãún måïi w laì mäüt säú 
nguyãn 
w ∈ N (9.9) 
w chæïa caïc pháön tæí cuía táûp håüp L (cardinality) 
w = | RA ∪ RN | 
Ta thæìa nháûn ngáöm ràòng caïc táûp håüp D vaì A âãöu laì hæîu haûn. Khi håüp thæïc hoïa 
vaì khåíi âäüng laûi, bäü âãúm w âæåüc khåíi taûo giaï trë |D| - |A| (vç ràòng a vaì n âãöu âån 
aïnh) laì mäüt hàòng säú dæång cuía hãû thäúng. Khi coï sæû thay âäøi, bäü âãúm w tàng lãn khi 
vaì chè khi âëa chè v, quaï taíi trong n, âang åí traûng thaïi cm, nghéa laì nãúu b (v) = 1 vaì 
nãúu c (v) = 0 
Våïi sæû måí räüng måïi naìy, báút biãún cuía hãû thäúng luïc naìy seî laì : 
a ∈ A → D (6.3) 
n ∈ A → D (6.3) 
m ∈ D → V (4.1) 
b ∈ D → {0, 1} (9.2) 
c ∈ D → {0, 1} (9.2) 
d ∈ D → {0, 1} (9.2) 
d ∈ D → {0, 1} (9.2) 
w ∈ N (9.9) 
RA - RN = {x ∈ D / b (x) = 0 vaì c (x) = 1} (6.2) 
RA ∩ RN = {x ∈ D / b (x) = 1 vaì c (x) = 0} (6.2) 
RN - RA = {x ∈ D / b (x) = 1 vaì c (x) = 1} (6.2) 
RA ∪ RA {x ∈ D / b (x) = 0 vaì c (x) = 0} (6.2) 
RA = {x ∈ D / d (x) = 1} (9.2) 
W = | RA ∪ RN | (9.10) 
Trong âoï 
RA = ran (a) 
RN = ran (n) 
Sau âáy laì caïc âàûc taí âæåüc toïm tàõt bàòng caïch thay thãú caïc danh saïch daìi caïc 
biãún båíi hai biãún traûng thaïi state vaì traûng thaïi coï dáúu nhaïy (‘) state’ 
state mod5 (x, y) state’ 
x ∈ A 
y ∈ V 
w ≠ 0 
a’ = a 
n’ = n + {x → u} 
Âàûc taí 149 
m’ = m + {u → y} 
b’ = b + {u → b (u) v → b (v)} (9.12) 
c’ = c + {u → c (u), v → c (v)} 
d’ = d 
(b (v) = 1 & c (v) = 0) ⇒ w’ = w - 1 
Trong âoï 
u ∈ {Z ∈ D | b (z) = 0 & c (z) = 0} 
v = n (x) 
state rst5 state’ 
a’ = a 
n’ = a 
m’ = m 
b’ = d (9.13) 
c’ = z 
d’ = d 
w’ = | D | - | A | 
state vdl5 state’ 
a’ = n 
n’ = n 
m’ = m 
b’ = b (9.14) 
c’ = z 
d’ = b 
w’ = | D | - | A | 
Trong âoï Z ∈ D → {0} 
Sau âáy laì quaï trçnh biãún âäøi cuû thãø 
IV.8. Âàûc taí laìm gç ? 
Sau âáy ta seî traí låìi cáu hoíi vãö muûc âêch (cho ai, cho caïi gç) cuía caïc cäng viãûc 
maì ta âaî laìm. Vai troì âáöu tiãn cuía mäüt âàûc taí laì cho pheïp måí ra caïc tranh luáûn vãö 
âãö taìi âàûc taí âãö taìi âàûc taí âãø cáûp âãún. Thæûc tãú, khaïc våïi mäüt chæång trçnh, mäüt âàûc 
khäng phaíi viãút ra âãø maïy tênh coï thãø hiãøu âæåüc maì âãø cho nhæîng NSD coï thãø hiãøu 
vaì tin tæåíng vaìo tênh âuïng âàõn cuía näüi dung âaî âàûc taí. 
Tæì âàûc taí luïc âáöu åí muûc 3 cho âãún caïc âàûc taí tiãúp theo åí caïc muûc 4, 6, 8 vaì 8, ta 
âaî sæí duûng caïc raìng buäüc mäùi luïc mäüt mang tênh thæc tiãùn. Ta âaî khàóng âënh âæåüc 
tênh âuïng âàõn cuía âàûc taí båíi caïc chæïng minh âënh lyï phuì håüp vaì cháúp nháûn âæåüc : 
baío toaìn tênh báút biãún. 
Báy giåì váún âãö laì sæí duûng caïc âàûc taí âãø láûp trçnh. Trong muûc naìy, ta seî láûp 
trçnh cho caïc træåìng håüp âàûc taí (9.12), (9.13) vaì (9.14), bàòng caïch sæí duûng ngän 
TS. PHAN HUY KHAÏNH biãn soaûn 149 
150 Cäng nghãû Pháön mãöm 
ngæî giaí Pascal. Ta âæa vaìo caïc quy tàõc âãø tiãút láûp mäúi liãn hãû giæîa âàûc taí vaì láûp 
trçnh. 
Quy tàõc 1 : 
Khi mäüt âàûc taí chæïa caïc âiãöu kiãûn træåïc, chæång trçnh tæång æïng seî laì mäüt 
haìm. Theo nghéa cuía Pascal, mäùi giaï trë sai cuía âiãöu kiãûn træåïc seî traí vãö biãún 
traûng thaïi state mäüt giaï trë phán biãût. 
Chæång trçnh tæång æïng våïi âàûc taí (9.12) laì nhæ sau : 
if not (x in A) then 
state := bad - x 
else if not (y in v) then 
state := bad - y 
else if w = 0 then 
state := no more place 
else begin 
State := OK ; 
Modification {goüi thuí tuûc} 
end ; 
Quy tàõc 2 : 
Khi mäüt âàûc taí chæïa caïc biãún phuû, ta coï thãø måí moüi thuí tuûc chæïa caïc biãún naìy 
nhæ laì caïc biãún cuûc bäü. Thuí tuûc naìy bàõt âáöu båíi caïc lãûnh khåíi âäüng 
Thuí tuûc Modification nhæ sau : 
procedure Modification ; 
var u, v : D 
begin 
u := 1 ; {choün u laì âëa chè beï nháút cuía L} 
while (b (u) ≠ 0) or (c (u) ≠ 0) do 
u := u + 1 ; (10.2) 
v := n (x) 
{tiãúp tuûc thán thuí tuûc 
end ; 
Quy tàõc 3 : 
Caïc âiãöu kiãûn sau khaïc nhau nãúu coï daûng a’ = ... (trong âoï dáúu ba cháúm ... chè 
âënh mäüt biãøu thæïc khåíi âäüng chæïa caïc biãún coï âaïnh dáúu nhaïy), thç coï thãø âæåüc 
chuyãøn thaình pheïp gaïn qua caïc quy tàõc bäø tråü nhæ sau : 
- Loaûi boí caïc âiãöu kiãûn sau daûng âàóng thæïc. 
Vê duû : d’ = d 
- Thay thãú dáúu = båíi dáúu gaïn bàòng := 
- Thæûc hiãûn pheïp täúi æu khi mäüt haìm laì quaï taíi 
Âàûc taí 151 
- Loaûi boí caïc dáúu nhaïy ‘ 
- Thay thãú mäüt âiãöu kiãûn sau båíi cáúu truïc âiãöu kiãûn if... else : 
Caïc âiãöu kiãûn sau khäng bë loaûi boí cuía âàûc taí (9.12) nhæ sau : 
 if not (x in A) then 
state := bad - x 
else if not (y in V) then 
state := bad - y (10.1) 
else if w = 0 then 
state := no-more-place 
else begin 
state := O.K ; 
Modication {goüi giaï trë thuí tuûc} 
end ; 
Quy tàõc 2 : 
Khi mäüt âàûc taí chæïa caïc biãún phuû, ta coï thãø måí mäüt thuí tuûc chæïa caïc biãún naìy 
nhæ laì caïc biãún cuûc bäü. Thuí tuûc naìy bàõt âáöu båíi caïc lãûnh khåíi âäüng. 
Thuí tuûc Modication nhæ sau : 
Procedure Modication ; 
var u, v : D 
begin 
u := 1 ; {choün u laì âëa chè beï nháútcuía L} 
æhile (b (u) ≠ 0) or (c (u) ≠ 0) do 
u := u + 1 ; (10.2) 
v := n (x) 
{tiãúp tuûc thán thuí tuûc 
end ; 
Quy tàõc 3 : 
Caïc âiãöu kiãûn sau khaïc nhau nãúu âãöu coï daûng a’ = ... (trong âoï dáúu cháúm ... chè 
dënh mäüt biãøu thæïc khäng chæïa caïc biãún coï âaïnh dáúu nhaïy), thç coï thãø âæåüc chuyãøn 
thaình pheïp gaïn qua caïc quy tàõc bäø tråü nhæ sau : 
- Loaûi boí caïc âiãöu kiãûn sau daûng âàóng thæïc. 
Vê duû : d’ = d 
- Thay thãú dáúu = båíi dáúu gaïn bàòng := 
- thæûc hiãûn pheïp täúi æu khi mäüt haìm laì quaï taíi. 
- Loaûi boí caïc dáúu nhaïy ‘ 
- Thay thãú mäüt âiãöukiãûn sau båíi cáúu truïc âiãöu kiãûn if ... else : 
Caïc âiãöu kiãûn sau khäng loaûi boí cuía âàûc taí (9.12) nhæ sau : 
n (x) := u ; 
m (u) := y ; (10.3) 
TS. PHAN HUY KHAÏNH biãn soaûn 151 
152 Cäng nghãû Pháön mãöm 
b (u) := b (u) ; b (v) := b (v) ; 
c (u) := c (u) ; c (v) = c (v) ; 
if (b (v) = 1) and (c (v) = 0) then w := w - 1 
Quy tàõc 4 : 
Mäüt caïch hãû thäúng caïc hãû chæång trçnh âaî viãút âæåüc båíi caïc quy tàõc âaím baío 
tênh “song song” âæa vaìo tæì âàûc taí. Tæì caïc âoaûn chæång trçnh (10.1), (10.2) vaì 
(10.3) ta nháûn âæåüc cäng thæïc âáúy âuí hån nhæ sau : 
Âàûc taí 153 
Mäüt säú âãö thi 
I. Âàûc taí (Specification) 
1. Cho ma tráûn vuäng A cáúp n×n. Viãút âàûc taí thãø hiãûn : a) Mäùi pháön tæí trãn 
âæåìng cheïo chênh laì pháön tæí låïn nháút trãn cuìng haìng âi qua pháön tæí âoï. b) 
Mäùi pháön tæí trãn âæåìng cheïo phuû laì pháön tæí nhoí nháút trãn cuìng cäüt âi qua 
pháön tæí âoï. 
2. Mäüt xáu (string) w âæåüc goüi laì âäúi xæïng (palindrome) nãúu w = wR hay âoüc 
xuäi ngæåüc âoüc ngæåüc âãöu nhæ nhau (wR laì xáu âaío ngæåüc cuía w). Vê duû caïc 
xáu omo, mannam, ... âãöu laì âäúi xæïng. Viãút âàûc taí thãø hiãûn caïc xáu âäúi 
xæïng. 
3. Âa thæïc cáúp n âæåüc viãút dæåïi daûng Toaïn hoüc laì : 
Pn(x) = a0 + a1x1 + a2x2 + ... + anxn 
Viãút âàûc taí thãø hiãûn pheïp cäüng, so saïnh hai âa thæïc Pn(x) vaì Qm(x), nhán âa 
thæïc våïi mäüt hàòng säú a × Pn(x) vaì nhán hai âa thæïc Pn(x) × Qm(x). 
4. Caïc phán säú (hay säú hæîu tyí) âæåüc biãøu diãùn båíi danh saïch (n, d), våïi n laì tæí säú vaì d 
laì máùu säú, laì nhæîng säú nguyãn (d ≠ 0). Viãút âàûc taí xáy dæûng caïc haìm xæí lyï phán säú: 
ruït goün, træì, chia vaì so saïnh hai phán säú, cäüng, nhán hai phán säú vaì chuyãøn âäøi 
phán säú thaình säú thæûc. 
II. Láûp trçnh cáúu truïc (Structured programming) 
1. Viãút lãûnh bàòng giaí ngæî (phoíng Pascal), chè sæí duûng täúi âa ba cáúu truïc tuáön tæû, âiãöu 
kiãûn if vaì làûp (while-repeat), theo caïc så âäö khäúi dæåïi âáy : 
S1 
Âuïng 
Sai 
S2 
Sai
Âuïng
C2
C1S1 
Âuïng
Sai 
S2 
Sai
Âuïng 
C2
C1
TS. PHAN HUY KHAÏNH biãn soaûn 153 
154 Cäng nghãû Pháön mãöm 
S1
Sai 
Sai 
S2
Âuïng
Âuïng
C2
C1
S3 
Âuïng
Âuïng 
S1 
Sai 
Sai 
S2 
C2
C1
S3
Âuïng
Sai 
S3 
Sai 
Âuïng 
S1 
C1
C2
S2 S1 
Âuïng
Sai
S2 
Sai 
Âuïng 
C2
C1
2. Viãút lãûnh bàòng giaí ngæî (phoíng Pascal), chè sæí duûng täúi âa ba cáúu truïc tuáön tæû, âiãöu 
kiãûn if vaì làûp (whilerepeat), theo så âäö khäúi dæåïi âáy : 
III. Thæí nghiãûm chæång trçnh (Testing) 
Giaí sæí caïc chæång trçnh âaî cho åí pháön trãn âáy laì caïc âån thãø goüi âãún caïc âån 
thãø con S1, S2 vaì S3). Trçnh baìy mäüt phæång phaïp âãø thæí nghiãûm âån thãø goüi.