Giáo trình Kỹ thuật lập trình nâng cao - Trần Hoàng Thọ

ñuùng. 
 Baûng chaân trò sau khaúng ñònh ñieàu ñoù: 
 A B C [ (A ==> B) and (B ==> C) and A ] ==> C 
 F F F [ T and T and F ] ==> F ( T ) 
 F F T [ T and T and F ] ==> T ( T ) 
 F T F [ T and F and F ] ==> F ( T ) 
 F T T [ T and T and F ] ==> T ( T ) 
 T F F [ F and T and T ] ==> F ( T ) 
 T F T [ F and T and T ] ==> T ( T ) 
 T T F [ T and F and T ] ==> F ( T ) 
 T T T [ T and T and T ] ==> T ( T ) 
Ví duï 2: Lyù luaän (3) laø sai . 
 Ñaët : A : hoâm nay trôøi ñeïp 
 B : Toâi ñi chôi 
 C : Toâi veà treã 
 Daïng lyù luaän (3) laø : [(A ==> B) and (B ==> C) and C ] ==> A 
laø sai vì vôùi A, B False , C true thì meänh ñeà : 
 [(A ==> B) and (B ==> C) and C ] ==> A nhaän gía trò False 
Traàn Hoaøng Thoï Khoa Toaùn - Tin 
 Kyõ thuaät laäp trình naâng cao - 99 - 
 A B C [(A ==> B) and (B ==> C) and C ] ==> A 
 F F T [ T and T and T ] ==> F 
5. Töông ñöông (Equivalence). 
 a) Ñònh nghóa: 
Hai meänh ñeà P vaø Q ñöôïc goïi laø töông ñöông nhau (kyù hieäu P ≡ Q), neáu meänh ñeà 
P Q luoân nhaän giaù trò ñuùng (True) vôùi moïi khaû naêng ñuùng sai cuûa caùc meänh ñeà 
thaønh phaàn . 
 Ta coù theå chöùng minh moät söï töông ñöông baèng caùch laäp baûng chaân trò . 
 Ví duï: chöùng minh : p and q ≡ not( not p or not q ). 
 Baûng chaân trò : 
 p q p and q not ( not p or not q ) 
 F F F not ( T or T ) 
 F T F not ( T or F ) 
 T F F not ( F or T ) 
 T T T not ( F or F ) 
 b) Moät soá töông ñöông höõu ích. 
 ( haõy chöùng minh chuùng baèng caùch laäp baûng chaân trò) 
 Caùc haèng : P or true ≡ true 
 P or false ≡ p 
 p and true ≡ p 
 p and false ≡ false 
 true ==> p ≡ p 
 false ==> p ≡ true 
 p ==> true ≡ true 
 p ==> false ≡ not p 
 Luaät loaïi tröø trung gian : p or not p ≡ true 
 Luaät veà maâu thuaãn : p and not p ≡ false 
 Luaät phuû ñònh : not not p ≡ p 
 Luaät Keát hôïp : p or (q or r) ≡ (p or q) or r 
 p and (q and r) ≡ (p and q) and r 
 p (q r) ≡ (p q) r 
 Luaät giao hoaùn : p and q ≡ q and p 
 p or q ≡ q or p 
Traàn Hoaøng Thoï Khoa Toaùn - Tin 
 Kyõ thuaät laäp trình naâng cao - 100 - 
 p q ≡ q p 
 luaät phaân phoái : p and (q or r) ≡ (p and q) or (p and r) 
 p or (q and r) ≡ (p or q) and (p or r) 
 Luaät ñoàng nhaát : p or p ≡ p 
 p and p ≡ p 
 Luaät De Morgan : not (p or q) ≡ not p and not q 
 not (p and q) ≡ not p or not q 
 Luaät haøm yù : p ==> q ≡ not p or q 
 p ==> q ≡ not q ==> p 
 (p and q) ==> r ) ≡ (p ==> (q ==> r) ) 
 luaät neáu vaø chæ neáu : p q ≡ ( (p ==> q) and (q ==> p) ) 
 p q ≡ ((p ==> q) and (not p ==> not q)) 
 p q ≡ ((p and q) or (not p and not q)) 
6. Tính thay theá, tính truyeàn vaø tính ñoái xöùng. 
 Khi 2 meänh ñeà P vaø Q laø töông ñöông thì ta coù theå thay theá caùi naøy bôûi caùi kia 
trong moät meänh ñeà baát kyø maø khoâng laøm sai trò cuûa noù. 
 Ta coù theå chöùng minh tính chaát cuûa moät meänh ñeà baèng caùch bieán ñoåi noù thaønh caùc 
meänh ñeà töông ñöông. 
 Ví duï: ta chöùng minh raèng (p and (p ==> q)) ==> q laø moät lyù luaän hôïp logic baèng 
caùch bieán ñoåi töông ñöông. 
 (p and (p ==> q)) ==> q (p and (not p or q)) ==> q (haøm yù) ≡
 ((p and not p) or (p and q)) ==> q (phaân phoái) ≡
 (false or (p and q)) ==> q (maâu thuaãn) ≡
 (p and q) ==> q (haèng) ≡
 not (p and q) or q (haøm yù) ≡
 (not p or not q) or q (De Morgan) ≡
 not p or (not q or q) (keát hôïp) ≡
 not p or (q or not q) (giao hoaùn) ≡
 not p or true ≡ ≡ true 
 Quan heä "töông ñöông" giöõa caùc meänh ñeà coù tính : 
 + Phaûn xaï : p p ≡
 + Ñoái xöùng : neáu p q thì ta cuõng coù q ≡ ≡ p 
 + Baéc caàu : neáu p q vaø q ≡ ≡ r thì ta cuõng coù p ≡ r. 
7. Baøi toaùn suy dieãn logic. 
 Xeùt baøi toaùn : Treân hoøn ñaûo coù hai loaïi ngöôøi sinh soáng : quaân töû vaø tieåu nhaân. 
Traàn Hoaøng Thoï Khoa Toaùn - Tin 
 Kyõ thuaät laäp trình naâng cao - 101 - 
 Quaân töû luoân noùi thaät vaø tieåu nhaân luoân noùi doái. Moät ngöôøi hoûi moät daân cö A treân 
ñaûo : "coù phaûi anh laø moät quaân töû ?". A ñaùp :"neáu toâi laø quaân töû thì toâi thua tieàn anh 
". Haõy chöùng minh raèng : A nhaát ñònh phaûi thua tieàn. 
 Ta moâ hình hoùa baøi toaùn nhö sau : 
 Ñaët caùc meänh ñeà P : A laø quaân töû. Q : A phaûi traû tieàn. 
 Keát luaän phaûi chöùng minh laø Q. 
 Khaûo saùt giaû thieát cuûa baøi toaùn: 
 + Meänh ñeà khaúng ñònh : " A laø tieåu nhaân " laø not P 
 + A phaùt bieåu moät meänh ñeà S. giaû thieát cho bieát : Neáu A laø quaân töû thì S phaûi 
ñuùng töùc laø : P ==> S 
 + Neáu A laø tieåu nhaân thì S phaûi sai : not p ==> not s 
 + S laø moät haøm yù : " Neáu A laø quaân töû thì A phaûi traû tieàn". 
Ta bieåu thò S bôûi : p ==> q 
 Nhö vaäy tieàn ñeà laø : (P ==> S) and (not P ==> not S) 
theo luaät töông ñöông (k) ta coù theå vieát laø : P S. 
 Baøi toaùn ñöôïc phaùt bieåu döôùi daïng thuaàn tuyù logic nhö sau : 
 Cho tieàn ñeà P (P ==> Q) 
 Coù theå suy dieãn ñöôïc keát luaän Q khoâng ? 
 Ta seõ xaùc laäp raèng (lyù luaän treân laø ñuùng) meänh ñeà (P (p ==> Q)) ==> Q 
laø ñuùng vôùi moïi boä giaù trò ñuùng sai cuûa caùc meänh ñeà thaønh phaàn . 
 Coù hai caùch : (a) Duøng baûng giaù trò ñuùng sai . 
 P Q ( P ( P ==> Q ) ) ==> Q 
 ––––––––––––––––––––––––––––––––––––– 
 T T ( T T ) ==> T 
 F T ( F T ) ==> T 
 T F ( T F ) ==> F 
 F F ( F T ) ==> F 
 (b) Duøng caùch thay theá baèng caùc meänh ñeà töông ñöông . 
 P (P ==> Q) P (not P or Q) (haøm yù) ≡
 ≡ [(P and (not P or Q)] or [not P and not (not P or Q )] 
 (töông ñöông) 
 maø not P and not (not P or Q) ≡ not P and (not not P and not Q) 
 ≡ not P and ( P and not Q) 
 ≡ (not P and P) and not Q 
 ≡ false and not Q ≡ false 
 vaø P and (not P or Q) ≡ (P and not P) or (P and Q) 
 ≡ false or (p and Q) 
 ≡ P and Q 
 Nhö vaäy P (P ==> Q) ≡ P and Q 
 Töø ñoù [P(P ==>Q)] ==> Q ≡ (P and Q) ==> Q 
Traàn Hoaøng Thoï Khoa Toaùn - Tin 
 Kyõ thuaät laäp trình naâng cao - 102 - 
 ≡ not (P and Q) or Q 
 ≡ (not P or not Q) or Q 
 ≡ not P or (not Q or Q) 
 ≡ not P or true ≡ true 
 Vôùi caùc baøi toaùn chæ lieân quan ñeán ít meänh ñeà nhö trong ví duï treân, caùch duøng baûng 
chaân trò ñôn giaûn hôn . Nhöng neân coá gaéng söû duïng caùch bieán ñoåi töông ñöông, bôûi vì 
aùp duïng thöïc tieãn cuûa noù laø lôùn hôn nhieàu. 
8. Caùc luaät suy dieãn (rules of inference). 
 Töông töï nhö baøi toaùn ôû muïc treân, trong nhieàu lónh vöïc, ngöôøi ta caàn phaûi xuaát phaùt 
töø moät taäp hôïp caùc tieàn ñeà, vaø tìm caùch khaúng ñònh moät keát luaän coù phaûi laø heä quaû cuûa 
caùc tieàn ñeà ñoù khoâng ? 
 Caùch giaûi quyeát laø ngöôøi ta xaây döïng cho lónh vöïc ñoù moät heä thoáng caùc tieân ñeà 
(axioms), töùc laø caùc khaúng ñònh ñöôïc xem nhö ñöông nhieân ñuùng (valid) vaø moät taäp 
hôïp caùc luaät suy dieãn (rules of inference – taäp caùc qui taéc cho pheùp xaây döïng caùc 
khaúng ñònh ñuùng môùi xuaát phaùt töø caùc tieân ñeà vaø caùc khaúng ñònh ñaõ coù ) . 
 Trong khung caûnh naøy, moät khaúng ñònh ñöôïc thieát laäp nhö vaäy ñöôïc goïi laø moät ñònh 
lyù . Moät chöùng minh hình thöùc (formal proof) laø moät daõy coù thöù töï cuûa caùc khaúng ñònh, 
maø moãi khaúng ñònh hoaëc laø tieân ñeà, hoaëc ñöôïc suy dieãn töø caùc khaúng ñònh ñi tröôùc, 
baèng moät luaät suy dieãn naøo ñoù. 
 a) Heä luaät suy dieãn cuûa Gentden cho logic meänh ñeà. Trong ñoù moãi luaät suy dieãn seõ 
ñöôïc vieát döôùi daïng : S1 , S2 , . . . ,Sn 
 S 
dieãn taû neáu ñaõ coù caùc meänh ñeà daïng S1, S2,..., Sn thì ta coù theå suy ra S 
Caùc luaät theâm vaøo 
Caùc ñònh luaät loaïi boû 
 and_I 
p, q 
_______ 
p and q 
or_I 
p q 
 ______ ______ 
p or q p or q 
==>_I 
[p] q 
______ 
p ==> q 
 not_I 
and_E 
p and q p and q 
 _______ _______ 
p q 
 or_E 
p or q , [p] r , [q] r 
________________ 
r 
==>_E 
p , p ==> q 
__________ 
q 
not_E 
Traàn Hoaøng Thoï Khoa Toaùn - Tin 
 Kyõ thuaät laäp trình naâng cao - 103 - 
[p] false 
_______ 
not p 
 _I 
p ==> q , q ==> p 
_______________ 
p q 
 p ,not p false not not p 
 _______ ____ _______ 
 false p p 
_E 
p q p q 
 _______ _______ 
p q p q 
 Caùc luaät ñöôïc chia laøm caùc luaät theâm vaø caùc luaät loaïi boû : Caùc luaät theâm vaøo cho 
pheùp suy ra moät khaúng ñònh môùi trong ñoù coù xuaát hieän theâm moät lieân töø logic. Coøn caùc 
luaät loaïi boû thì loaïi boû moät lieân töø logic. 
 Luaät and_I noùi raèng neáu coù theå chöùng minh ñöôïc p vaø q thì ta suy ñöôïc ra p and q . 
 Luaät and_E noùi raèng neáu chöùng minh ñöôïc p and q thì ta suy ñöôïc töøng thaønh 
phaàn p vaø q . 
 Luaät or_E söû duïng 3 tieàn ñeà : ñaõ coù p or q , neáu giaû ñònh p ñuùng thì chöùng minh 
ñöôïc r , neáu giaû ñònh q ñuùng thì chöùng minh ñöôïc r. khi ñoù luaät naøy cho pheùp keát 
luaän r ñuùng. Ñaây chính laø phaân tích theo tröôøng hôïp (case analysis) vaãn thöôøng ñöôïc 
duøng trong lyù luaän haøng ngaøy . 
 Luaät ==>E thöôøng ñöôïc goïi laø modusponens (tam ñoaïn luaän). Noù noùi raèng coù q 
neáu chöùng minh ñöôïc p vaø p ==> q . 
 Luaät not_I noùi raèng neáu xuaát phaùt töø giaû ñònh p maø coù maâu thuaãn thì cho ta keát 
luaän not p . Cuøng vôùi luaät naøy , caàn boå sung theâm luaät veà loaïi tröø trung gian true 
 p or not p 
 ñöôïc phaùt bieåu nhö tieân ñeà (töùc laø luaät suy dieãn khoâng caàn tieàn ñeà). 
III. LOGIC TAÂN TÖØ. 
1. Khaùi nieäm 
 Trong logic meänh ñeà , moãi meänh ñeà coù giaù trò xaùc ñònh hoaëc laø T (ñuùng) hoaëc laø 
F (sai) . Trong thöïc teá ngöôøi ta hay gaëp vaø caàn laøm vieäc vôùi nhöõng khaúng ñònh maø tính 
ñuùng sai cuûa noù phuï thuoäc vaøo caùc ñoái töôïng thöïc söï ñöôïc thay theá . 
 Ví duï xeùt phaùt bieåu sau : “ x laø soá nguyeân toá “. 
 Goïi meänh ñeà naøy laø P(x), ñaây laø moät meänh ñeà maø tính ñuùng sai cuûa noù chæ 
ñöôïc xaùc ñònh hoaøn toaøn khi ta "theá" moät giaù trò haèng cho "bieán" x. 
 Ví duï P(5) laø T (duùng) , P(6) laø F (sai) . 
 Trong logic taân töø , ngöôøi ta phaùt bieåu caùc meänh ñeà baèng caùch söû duïng nhöõng 
khaùi nieäm sau: 
Traàn Hoaøng Thoï Khoa Toaùn - Tin 
 Kyõ thuaät laäp trình naâng cao - 104 - 
 a) Caùc haèng: laø caùc ñoái töôïng cuï theå toàn taïi trong lónh vöïc maø ngöôøi ta ñang 
khaûo saùt . 
 Ví duï : + Caùc haèng soá 5,6,10.2,... 
 + Caùc haèng logic T(ñuùng) , F(sai) 
 Trong tröôøng hôïp toång quaùt ,ngöôøi ta thöôøng ñaïi dieän cho caùc haèng baèng caùc 
chöõ caùi vieát thöôøng oû ñaàu baûng töø vöïng: a,b,c...,a1 ,b1 , c1 ,... 
 b) Caùc bieán (Variable): laø caùc teân töôïng tröng . Moãi bieán ñöôïc aán ñònh moät 
mieàn giaù trò laø taäp caùc ñoái töôïng maø noù coù theå nhaän. 
 Ví duï: + Caùc bieán soá nguyeân n, j , k ,. . . vôùi caùc taäp trò laø caùc taäp con cuûa 
taäp soá nguyeân Z . 
 + Caùc bieán soá thöïc x, y, z, . vôùi caùc taäp trò laø caùc taäp con cuûa taäp soá 
thöïc R . 
 + Caùc bieán veùc tô V, W, . . . vôùi caùc taäp trò laø caùc taäp con cuûa taäp tích 
ÑeàCaùc R X R X R X ... X R ( Rn ) 
 Thöôøng duøng caùc chöõ caùi vieát thöôøng ôû cuoái baûng töø vöïng ñeå bieåu thò caùc bieán : 
x,y,z,...,x1 ,y1 ,z1 ,... Töø daây veà sau ,moãi bieán neáu khoâng ñöôïc noùi roõ ñeàu ñöôïc xem laø 
bieán nguyeân . 
 c) Caùc toaùn töû (Operotors , hay haøm (functions)) laø caùc aùnh xaï töø caùc taäp hôïp ñoái 
töôïng vaøo caùc taäp hôïp ñoái töôïng trong lónh vöïc ñang khaûo saùt. Ta seõ thöôøng duøng 
caùc toaùn töû toaùn hoïc sau : + , - , * , / , div , mod 
 Moät toaùn töû coù theå coù moät hay nhieàu toaùn haïng (ngoâi) . 
 Ví duï : + Toaùn töû "ñoái" (bieåu thò bôûi -) laø moät ngoâi : -x 
 + Toaùn töû - ,+, - , * , / , div, mod laø hai ngoâi : 2 + 3 , x * y 
 d) Caùc haøm logic hay caùc taân töø (predicates) . Ñoù laø caùc aùnh xaï töø taäp hôïp caùc 
ñoái töôïng vaøo taäp boolean {true,false}, ta seõ thöôøng duøng caùc taân töø laø caùc quan heä 
toaùn hoïc nhö sau : 
 + Caùc quan heä so saùnh : = , , > , >= , < , <= 
 + Caùc quan heä taäp hôïp : ⊆ , ⊇ , . . . 
 + Caùc quan heä khaùc : odd(x) kieåm tra xem x coù leû khoâng ? 
 even(x) kieåm tra xem x coù chaün khoâng ? 
 e) Caùc lieân töø logic : ñaây laø caùc toaùn töû treân taäp boolean maø ta gaëp trong logic 
meänh ñeà: and , or , not , ==> , . 
 f) Caùc löôïng töø phoå duïng ∀ vaø toàn taïi ∃ (seõ noùi roõ ôû muïc sau) 
 Caùc bieán logic , caùc taân töø trong ñoù coù chöùa caùc haèng hay bieán hay haøm ñöôïc goïi 
laø caùc coâng thöùc cô sôû (formule elementaire) 
 Ví duï : Caùc coâng thöùc cô sôû 
 - Bieán logic : hoâm-nay-trôøi-ñeïp , toâi-veà-luùc-8-giôø ,... 
 - taân töø : 5 > 2 
 x > 5 
 x + 5 > y - 3 
Traàn Hoaøng Thoï Khoa Toaùn - Tin 
 Kyõ thuaät laäp trình naâng cao - 105 - 
 Töø caùc coâng thöùc cô sôû naøy,ngöôøi ta coù theå thaønh laäp caùc coâng thöùc phöùc hôïp 
(formule complexe) baèng caùch noái keát chuùng duøng caùc lieân töø logic vaø caùc löôïng töø 
. Moãi coâng thöùc phöùc hôïp coù theå xem laø moät taân töø môùi. 
 Ví duï : Coâng thöùc phöùc hôïp 
 a) Hoâm_nay_trôøi_ñeïp and x > y 
 b) x > y ==> x > z 
2. Caùc löôïng töø logic 
 Ngoaøi caùc lieân töø logic , ngöôøi ta coù theå taïo ra caùc coâng thöùc phöùc hôïp baèng caùch 
gaén vôùi caùc coâng thöùc caùc löôïng töø logic . 
 a) Löôïng töø phoå duïng. 
 Ñeå noùi raèng moãi phaàn töû cuûa moät taäp ñeàu coù tính chaát P ta duøng löôïng töû phoå 
duïng ( ñoïc laø vôùi moïi ) . ∀
 Ví duï ñeå noùi raèng taát caû caùc phaàn töû cuûa array a laø khoâng aâm ta vieát : 
 ( i : 0 = 0) ∀
 Bieåu thöùc naøy ñöôïc ñoïc nhö sau : 
 ∀ ( i Vôùi moïi (soá nguyeân) i 
 : 0 <= i < n sao cho i naèm giöõa 0 vaø n-1 
 : a[i] >= 0 thì a [i] laø khoâng aâm 
 Daïng chung : (danh saùch bieán : R : P) ∀
 Vôùi : R laø taân töø haïn cheá taäp hôïp ñöôïc xeùt trong khoâng gian ñònh bôûi danh saùch 
bieán , P laø taân töø maø moãi phaàn töû trong taäp ñöôïc xeùt phaûi thoaû. 
Meänh ñeà phoå duïng chæ ñuùng khi moïi phaàn töû trong taäp xaùc ñònh bôûi R ñeàu thoaû P. 
 Ví duï : Cho a laø array [0...n-1] of Integer 
 - Khaúng ñònh : "a [k] laø phaàn töû lôùn nhaát trong array" 
 ( i : 0 = a [i] ) ∀
 - Khaúng ñònh : "caùc phaàn töû cuûa a taïo thaønh caáp soá coäng b,b+d, b+2d, . . 
 ( i : 0 <= i < n : a [i] = b + i*d) ∀
 - Khaúng ñònh : "a döôïc saép theo thöù töï khoâng ñôn giaûn" : 
 (i,j : 0 a[i] <= a [j]) ∀
 neáu R = true , ta coù theå boû qua : ∀ (d :: 0 = d*0) 
 b) Löôïng töø toàn taïi. 
 Ñeå khaúng ñònh coù moät phaàn töû cuûa taäp hôïp coù tính chaát P ta duøng löôïng töø toàn taïi 
 ( ñoïc laø: “ coù moät “ hoaëc “ toàn taïi “). ∃
 Ví duï : ñeå khaúng ñònh coù gía tri x trong array a ta vieát : 
 (i : 0 <= i < n : a [i] = x) ∃
 Bieåu thöùc naøy ñöôïc ñoïc nhö sau : 
 (i toàn taïi moät (soá nguyeân) i ∃
 : 0<= i < n sao cho i naèm giöõa 0 vaø n-1 
Traàn Hoaøng Thoï Khoa Toaùn - Tin 
 Kyõ thuaät laäp trình naâng cao - 106 - 
 : a[i] = x thoaû ñieàu sau a[i] baèng x 
 Daïng chung laø : ( danh saùch bieán : R : P ) ∃
 Meänh ñeà toàn taïi chæ ñuùng khi coù moät phaàn töû trong mieàn xaùc ñònh bôûi R thoaû P. 
 khi R = true thì ta coù theå vieát : ∃(danh saùch bieán :: P) 
 Ví duï : cho hai array a vaø b 
 - Khaúng ñònh :"trong array a khoâng coù thöù töï taêng" 
 ( i : 0 a [i+1]) ∃
 - Khaúng ñònh : "coù ít nhaát moät phaàn töû cuûa a lôùn hôn moïi phaàn töû cuûa b" 
 ∃( i : 0 b[j] )) 
 - Khaúng ñònh "n laø chaün" : ∃(m :: n = 2*m) 
 c) Moät soá tính chaát: 
 - (i : R : P) ≡ (i :: R and P) 
 - (i : R : P) ≡ not (i :: R and not P) 
 - (i : R : P) ≡ not (i : R : not P) 
 d) Caùc bieán töï do vaø bò buoäc (free and band variables), pheùp theá(substitution) 
 Trong bieåu thöùc Q(i: r(i) : p(i)) (ôû ñaây ta xeùt Q laø ∀ hay ∃ ) bieán i ñöôïc goïi 
laø bò buoäc (band) vaøo löôïng töø Q . 
 Nhöõng xuaát hieän cuûa moät bieán i khoâng bò buoäc vaøo moät löôïng töø naøo ñoù trong 
bieåu thöùc R,ñöôïc goïi laø töï do (free) trong R. 
 Ví duï trong bieåu thöùc : (d : p = q*d) ∃
 caùc bieán p vaø q laø töï do , coøn bieán d laø bò buoäc . Caùc bieán bò buoäc chæ ñoùng vai troø 
"giöõ choã" vaø coù theå ñöôïc ñoåi teân , neáu teân naøy khoâng truøng vôùi moät bieán töï do ñaõ coù. 
Vì vaäy , bieåu thöùc treân töông ñöông vôùi : 
 ∃(m :: p = q*m) nhöng hoaøn toaøn khaùc vôùi : (p :: p = q*p) 
 Veà nguyeân taéc , moät teân bieán coù theå vöøa töï do vaø bò buoäc trong cuøng moät bieåu thöùc 
. 
 Ví duï : Trong bieåu thöùc ∀ ( 0<i ) and ( i : 0 <= i < n : a [i] = 0 ) 
 xuaát hieän thöù nhaát cuûa i laø töï do , coøn xuaát hieän coøn laïi laø bò buoäc. 
 Maëc duø yù nghóa cuûa bieåu thöùc laø roõ raøng nhöng neân traùnh vì deã gaây neân laàm laãn . 
 Xeùt moät taân töø chöùa bieán töï do . 
 Ví duï : is-divisor(q) ∃ (d :: p = q*d) 
 Ta coù theå thay caùc xuaát hieän töï do cuûa moät bieán baèng moät bieåu thöùc ñeå ñöôïc moät 
taân töø môùi. 
 Ví duï: theá 2*q cho q ta seõ ñöôïc taân töø is-divisor(2*q) maø daïng bieåu thöùc cuûa noù 
laø : is-divisor(2*q) (d :: p = (2*q)*d) ∃
 Chuù yù raèng trong ∃ (d :: p = q*d) bieán p cuõng töï do , nhöng vì ta khoâng quan taâm 
ñeán pheùp theá cho p neân trong taân töø is-divisor(q) ta chæ neâu q ñeå giaûm bôùt ñi caùc chi 
tieát khoâng caàn thieát trong dieãn giaûi. 
Traàn Hoaøng Thoï Khoa Toaùn - Tin 
 Kyõ thuaät laäp trình naâng cao - 107 - 
3. Taäp hôïp vaø taân töØ. 
 Moãi bieán coù theå laáy giaù trò trong moät taäp hôïp xaùc ñònh . Taäp trò maø moät daõy caùc 
bieán coù theå nhaän ñöôïc laø tích Descarters caùc taäp trò cuûa töøng bieán . 
 Öng vôùi moät taân töø P(i), vôùi i laø (danh saùch) bieán töï do maø moãi pheùp theá i baèng 
moät haèng seõ cho giaù trò ñuùng hay sai , ta coù moät taäp hôïp taát caû caùc haøm maø pheùp theá 
i trong P cho giaù trò ñuùng . 
 kyù hieäu taäp ñoù laø : { i : P(i) } 
 Ví duï : { i : i >= 0 } "taäp caùc (soá nguyeân) i sao cho i khoâng aâm " 
 { i,j : i < j } "taäp caùc (soá nguyeân) i,j sao cho i nhoû hôn j" 
 Ngöôïc laïi öùng vôùi moãi taäp S , ta xaây döïng taân töø ñaëc tröng cho S ñoù laø: 
 P(i) = ( i ∈ S ) 
 Giöõa caùc pheùp toaùn taäp hôïp vaø caùc pheùp toaùn logic coù quan heä chaët cheõ. 
 { i : P(i) or Q(i) } { i : P(i) } U { i : Q(i) } ≡
 { i : P(i) and Q(i) } ≡ { i : P(i) } ∩ { i : Q(i) } 
 Phaàn töû trung hoaø cuûa pheùp toaùn giao : taäp vuõ truï (tích Descarters cuûa caùc taäp trò 
öùng vôùi caùc bieán trong danh saùch bieán) öùng vôùi i chính laø: { i : true } 
 Phaàn töû trung hoaø cuûa pheáp toaùn hoäi laø : { i : false } 
4. Caùc löôïng töø soá hoïc. 
 söû duïng yù töôûng cuûa ∀ vaø ∃ ta ñaët theâm caùc löôïng töø soá hoïc ñeå dôn giaûn hoaù 
caùch vieát vaø deã daøng aùp duïng caùc pheùp bieán ñoåi . 
 Moãi löôïng töø sau seõ bieåu thò moät haøm soá hoïc : 
 - Löôïng töø toång S (sumation) 
 S( i: r(i): f(i) ) chính laø f i
i
( )∑ vôùi i chaïy treân taäp hôïp thoaû r(i) 
 - Löôïng töø tích P (product) 
 P( i: r(i): f(i) ) chính laø f i
i
( )∏ vôùi i chaïy treân taäp hôïp thoaû r(i) 
 Qui öôùc : 
 S( i: false: f(i) ) = 0 
 P( i: false: f(i) ) = 1 
 - Löôïng töø MAX vaø MIN 
 MAX ( I: r(i): f(i)) laø giaù trò lôùn nhaát cuûa f(i) trong caùc i thoaû r(i). 
 MIN ( I: r(i):f(i) ) laø giaù trò nhoû nhaát cuûa f(i) trong caùc i thoaû r(i). 
 Qui öôùc : 
 MAX ( i: false: f(i) ) = - ∞ 
 MIN ( i: false: f(i) ) = ∞ 
 - Löôïng töø N 
 N ( i:r(i): P(i)) soá giaù trò i trong mieàn r(i) thoaû P(i) 
 Töùc laø : N ( i: r(i): P(i)) = S(i: r(i) and p(i): 1) 
Traàn Hoaøng Thoï Khoa Toaùn - Tin 
 Kyõ thuaät laäp trình naâng cao - 108 - 
 Moãi löôïng töø maø ta xeùt ngoaïi tröø N la ø söï khaùi quaùt cuûa caùc pheùp toaùn hai ngoâi 
coù tính giao hoaùn vaø keát hôïp thaønh pheùp toaùn treân moät taäp baát kyø. 
 Ví duï : 
 S laø khaùi quaùt cuûa pheùp coâng ( + ), P laø khaùi quaùt cuûa pheùp nhaân ( * ). 
Traàn Hoaøng Thoï Khoa Toaùn - Tin