Giáo trình Kỹ thuật lập trình nâng cao

) là T (dúng) , P(6) là F (sai) . 
 Trong logic tân từ , người ta phát biểu các mệnh đề bằng cách sử dụng những 
khái niệm sau: 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 104 - 
 a) Các hằng: là các đối tượng cụ thể tồn tại trong lĩnh vực mà người ta đang 
khảo sát . 
 Ví dụ : + Các hằng số 5,6,10.2,... 
 + Các hằng logic T(đúng) , F(sai) 
 Trong trường hợp tổng quát ,người ta thường đại diện cho các hằng bằng các 
chữ cái viết thường ỏ đầu bảng từ vựng: a,b,c...,a1 ,b1 , c1 ,... 
 b) Các biến (Variable): là các tên tượng trưng . Mỗi biến được ấn định một 
miền giá trị là tập các đối tượng mà nó có thể nhận. 
 Ví dụ: + Các biến số nguyên n, j , k ,. . . với các tập trị là các tập con của 
tập số nguyên Z . 
 + Các biến số thực x, y, z, . với các tập trị là các tập con của tập số 
thực R . 
 + Các biến véc tơ V, W, . . . với các tập trị là các tập con của tập tích 
ĐềCác R X R X R X ... X R ( Rn ) 
 Thường dùng các chữ cái viết thường ở cuối bảng từ vựng để biểu thị các biến : 
x,y,z,...,x1 ,y1 ,z1 ,... Từ dây về sau ,mỗi biến nếu không được nói rõ đều được xem là 
biến nguyên . 
 c) Các toán tử (Operotors , hay hàm (functions)) là các ánh xạ từ các tập hợp đối 
tượng vào các tập hợp đối tượng trong lĩnh vực đang khảo sát. Ta sẽ thường dùng 
các toán tử toán học sau : + , - , * , / , div , mod 
 Một toán tử có thể có một hay nhiều toán hạng (ngôi) . 
 Ví dụ : + Toán tử "đối" (biểu thị bởi -) là một ngôi : -x 
 + Toán tử - ,+, - , * , / , div, mod là hai ngôi : 2 + 3 , x * y 
 d) Các hàm logic hay các tân từ (predicates) . Đó là các ánh xạ từ tập hợp các 
đối tượng vào tập boolean {true,false}, ta sẽ thường dùng các tân từ là các quan hệ 
toán học như sau : 
 + Các quan hệ so sánh : = , , > , >= , < , <= 
 + Các quan hệ tập hợp : ⊆ , ⊇ , . . . 
 + Các quan hệ khác : odd(x) kiểm tra xem x có lẻ không ? 
 even(x) kiểm tra xem x có chẵn không ? 
 e) Các liên từ logic : đây là các toán tử trên tập boolean mà ta gặp trong logic 
mệnh đề: and , or , not , ==> , . 
 f) Các lượng từ phổ dụng ∀ và tồn tại ∃ (sẽ nói rõ ở mục sau) 
 Các biến logic , các tân từ trong đó có chứa các hằng hay biến hay hàm được gọi 
là các công thức cơ sở (formule elementaire) 
 Ví dụ : Các công thức cơ sở 
 - Biến logic : hôm-nay-trời-đẹp , tôi-về-lúc-8-giờ ,... 
 - tân từ : 5 > 2 
 x > 5 
 x + 5 > y - 3 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 105 - 
 Từ các công thức cơ sở này,người ta có thể thành lập các công thức phức hợp 
(formule complexe) bằng cách nối kết chúng dùng các liên từ logic và các lượng từ 
. Mỗi công thức phức hợp có thể xem là một tân từ mới. 
 Ví dụ : Công thức phức hợp 
 a) Hôm_nay_trời_đẹp and x > y 
 b) x > y ==> x > z 
2. Các lượng từ logic 
 Ngoài các liên từ logic , người ta có thể tạo ra các công thức phức hợp bằng cách 
gắn với các công thức các lượng từ logic . 
 a) Lượng từ phổ dụng. 
 Để nói rằng mỗi phần tử của một tập đều có tính chất P ta dùng lượng tử phổ 
dụng ( đọc là với mọi ) . ∀
 Ví dụ để nói rằng tất cả các phần tử của array a là không âm ta viết : 
 ( i : 0 = 0) ∀
 Biểu thức này được đọc như sau : 
 ∀ ( i Với mọi (số nguyên) i 
 : 0 <= i < n sao cho i nằm giữa 0 và n-1 
 : a[i] >= 0 thì a [i] là không âm 
 Dạng chung : (danh sách biến : R : P) ∀
 Với : R là tân từ hạn chế tập hợp được xét trong không gian định bởi danh sách 
biến , P là tân từ mà mỗi phần tử trong tập được xét phải thoả. 
Mệnh đề phổ dụng chỉ đúng khi mọi phần tử trong tập xác định bởi R đều thoả P. 
 Ví dụ : Cho a là array [0...n-1] of Integer 
 - Khẳng định : "a [k] là phần tử lớn nhất trong array" 
 ( i : 0 = a [i] ) ∀
 - Khẳng định : "các phần tử của a tạo thành cấp số cộng b,b+d, b+2d, . . 
 ( i : 0 <= i < n : a [i] = b + i*d) ∀
 - Khẳng định : "a dược sắp theo thứ tự không đơn giản" : 
 (i,j : 0 a[i] <= a [j]) ∀
 nếu R = true , ta có thể bỏ qua : ∀ (d :: 0 = d*0) 
 b) Lượng từ tồn tại. 
 Để khẳng định có một phần tử của tập hợp có tính chất P ta dùng lượng từ tồn tại 
 ( đọc là: “ có một “ hoặc “ tồn tại “). ∃
 Ví dụ : để khẳng định có gía tri x trong array a ta viết : 
 (i : 0 <= i < n : a [i] = x) ∃
 Biểu thức này được đọc như sau : 
 (i tồn tại một (số nguyên) i ∃
 : 0<= i < n sao cho i nằm giữa 0 và n-1 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 106 - 
 : a[i] = x thoả điều sau a[i] bằng x 
 Dạng chung là : ( danh sách biến : R : P ) ∃
 Mệnh đề tồn tại chỉ đúng khi có một phần tử trong miền xác định bởi R thoả P. 
 khi R = true thì ta có thể viết : ∃(danh sách biến :: P) 
 Ví dụ : cho hai array a và b 
 - Khẳng định :"trong array a không có thứ tự tăng" 
 ( i : 0 a [i+1]) ∃
 - Khẳng định : "có ít nhất một phần tử của a lớn hơn mọi phần tử của b" 
 ∃( i : 0 b[j] )) 
 - Khẳng định "n là chẵn" : ∃(m :: n = 2*m) 
 c) Một số tính chấ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) Các biến tự do và bị buộc (free and band variables), phép thế(substitution) 
 Trong biểu thức Q(i: r(i) : p(i)) (ở đây ta xét Q là ∀ hay ∃ ) biến i được gọi 
là bị buộc (band) vào lượng từ Q . 
 Những xuất hiện của một biến i không bị buộc vào một lượng từ nào đó trong 
biểu thức R,được gọi là tự do (free) trong R. 
 Ví dụ trong biểu thức : (d : p = q*d) ∃
 các biến p và q là tự do , còn biến d là bị buộc . Các biến bị buộc chỉ đóng vai trò 
"giữ chỗ" và có thể được đổi tên , nếu tên này không trùng với một biến tự do đã có. 
Vì vậy , biểu thức trên tương đương với : 
 ∃(m :: p = q*m) nhưng hoàn toàn khác với : (p :: p = q*p) 
 Về nguyên tắc , một tên biến có thể vừa tự do và bị buộc trong cùng một biểu thức 
. 
 Ví dụ : Trong biểu thức ∀ ( 0<i ) and ( i : 0 <= i < n : a [i] = 0 ) 
 xuất hiện thứ nhất của i là tự do , còn xuất hiện còn lại là bị buộc. 
 Mặc dù ý nghĩa của biểu thức là rõ ràng nhưng nên tránh vì dễ gây nên lầm lẫn . 
 Xét một tân từ chứa biến tự do . 
 Ví dụ : is-divisor(q) ∃ (d :: p = q*d) 
 Ta có thể thay các xuất hiện tự do của một biến bằng một biểu thức để được một 
tân từ mới. 
 Ví dụ: thế 2*q cho q ta sẽ được tân từ is-divisor(2*q) mà dạng biểu thức của nó 
là : is-divisor(2*q) (d :: p = (2*q)*d) ∃
 Chú ý rằng trong ∃ (d :: p = q*d) biến p cũng tự do , nhưng vì ta không quan tâm 
đến phép thế cho p nên trong tân từ is-divisor(q) ta chỉ nêu q để giảm bớt đi các chi 
tiết không cần thiết trong diễn giải. 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 107 - 
3. Tập hợp và tân tưØ. 
 Mỗi biến có thể lấy giá trị trong một tập hợp xác định . Tập trị mà một dãy các 
biến có thể nhận được là tích Descarters các tập trị của từng biến . 
 Ưng với một tân từ P(i), với i là (danh sách) biến tự do mà mỗi phép thế i bằng 
một hằng sẽ cho giá trị đúng hay sai , ta có một tập hợp tất cả các hàm mà phép thế 
i trong P cho giá trị đúng . 
 ký hiệu tập đó là : { i : P(i) } 
 Ví dụ : { i : i >= 0 } "tập các (số nguyên) i sao cho i không âm " 
 { i,j : i < j } "tập các (số nguyên) i,j sao cho i nhỏ hơn j" 
 Ngược lại ứng với mỗi tập S , ta xây dựng tân từ đặc trưng cho S đó là: 
 P(i) = ( i ∈ S ) 
 Giữa các phép toán tập hợp và các phép toán logic có quan hệ chặt chẽ. 
 { 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) } 
 Phần tử trung hoà của phép toán giao : tập vũ trụ (tích Descarters của các tập trị 
ứng với các biến trong danh sách biến) ứng với i chính là: { i : true } 
 Phần tử trung hoà của phếp toán hội là : { i : false } 
4. Các lượng từ số học. 
 sử dụng ý tưởng của ∀ và ∃ ta đặt thêm các lượng từ số học để dơn giản hoá 
cách viết và dễ dàng áp dụng các phép biến đổi . 
 Mỗi lượng từ sau sẽ biểu thị một hàm số học : 
 - Lượng từ tổng S (sumation) 
 S( i: r(i): f(i) ) chính là f i
i
( )∑ với i chạy trên tập hợp thoả r(i) 
 - Lượng từ tích P (product) 
 P( i: r(i): f(i) ) chính là f i
i
( )∏ với i chạy trên tập hợp thoả r(i) 
 Qui ước : 
 S( i: false: f(i) ) = 0 
 P( i: false: f(i) ) = 1 
 - Lượng từ MAX và MIN 
 MAX ( I: r(i): f(i)) là giá trị lớn nhất của f(i) trong các i thoả r(i). 
 MIN ( I: r(i):f(i) ) là giá trị nhỏ nhất của f(i) trong các i thoả r(i). 
 Qui ước : 
 MAX ( i: false: f(i) ) = - ∞ 
 MIN ( i: false: f(i) ) = ∞ 
 - Lượng từ N 
 N ( i:r(i): P(i)) số giá trị i trong miền r(i) thoả P(i) 
 Tức là : N ( i: r(i): P(i)) = S(i: r(i) and p(i): 1) 
Trần Hoàng Thọ Khoa Toán - Tin 
 Kỹ thuật lập trình nâng cao - 108 - 
 Mỗi lượng từ mà ta xét ngoại trừ N la ø sự khái quát của các phép toán hai ngôi 
có tính giao hoán và kết hợp thành phép toán trên một tập bất kỳ. 
 Ví dụ : 
 S là khái quát của phép công ( + ), P là khái quát của phép nhân ( * ). 
Trần Hoàng Thọ Khoa Toán - Tin