Tiếp cận tính toán Meet và Join các trị chân lý ngôn ngữ

2. CÁC PHÉP TOÁN VỚI CÁC GIÁ TRỊ CHÂN LÝ NGÔN NGỮ

2.4. Tiếp cận tính toán Meet và Join các trị chân lý ngôn ngữ

Trong Ví dụ 2.3, chúng ta đã sử dụng trực tiếp các phép toán ở Định nghĩa 2.6 và Định nghĩa 2.7 để tính meet và join hai giá trị chân lý ngôn ngữ. Tuy nhiên, như đã thấy, các kết quả thu được của các phép toán này không phải lúc nào cũng là một phần tử trong ĐSGT. Cụ thể hơn, khi xˆ và yˆ mà không có quan hệ kế thừa ngữ nghĩa, tương ứng với các trường hợp (i) trong hai định nghĩa trên thì kết quả thu được của phép toán này luôn là một giá trị ngôn ngữ, còn khi yˆ kế thừa ngữ nghĩa từ xˆ, tức là trong trường hợp (ii) thì không phải như vậy. Để kết quả của meet và join các giá trị ngôn ngữ luôn là một phần tử trong ĐSGT, tiếp theo đây sẽ đưa ra cách tính xấp xỉ cho chúng.

Vấn đề đặt ra là xấp xỉ như thế nào cho hợp lý! Từ trực quan ta có, nếu ˆ

zAX là một xấp xỉ của phép meet giữa và , tức là của (x yˆˆ)thì nó phải thỏa các yêu cầu sau. Trước tiên, zˆ phải kế thừa ngữ nghĩa từ . Sau đó, giá trị ngôn ngữ mức-k nhỏ nhất kế thừa ngữ nghĩa từ là phải kế thừa ngữ nghĩa từ

̂. Và ngữ nghĩa định lượng của zˆ không được vượt quá ngữ nghĩa định lượng của các giá trị chân lý ngôn ngữ tham gia thực hiện phép meet, tức là

ˆ ˆ ˆmin( , ) z x y .

Từ sự phân tích trên, ta có thể đưa ra tiêu chuẩn xấp xỉ cho phép meet các giá trị chân lý ngôn ngữ trong ĐSGT khi chúng có quan hệ kế thừa ngữ nghĩa.

Tiêu chuẩn xấp xỉ phép meet (Meet Approximation Criterion - MAC)

Giả sử ∈ là giá trị chân lý ngôn ngữ mức-g, ∈ là giá trị chân lý ngôn ngữ mức-k với k ≥ g và ⊲ . Đặt là giá trị ngôn ngữ mức-k nhỏ nhất kế thừa ngữ nghĩa từ . Giá trị ngôn ngữ ̂ là một “xấp xỉ tốt” của (x yˆˆ) nếu ̂ đồng thời thỏa các điều kiện sau :

(i) ̂ ⊲ ; (ii) ⊲ ̂; và (iii) zˆmin( , )x yˆ ˆ .

Bằng cách lập luận tương tự phép meet, ta có thể đưa ra một tiêu chuẩn xấp xỉ cho phép join các giá trị chân lý ngôn ngữ trong ĐSGT.

Tiêu chuẩn xấp xỉ phép join (Join Approximation Criterion - JAC)

Giả sử ∈ là giá trị chân lý ngôn ngữ mức-g, ∈ à giá trị chân lý ngôn ngữ mức-k với k ≥ g và ⊲ . Đặt là giá trị ngôn ngữ mức-k lớn nhất kế thừa ngữ nghĩa từ . Giá trị ngôn ngữ ̂ là một “xấp xỉ tốt” của (x yˆˆ) nếu ̂ đồng thời thỏa các điều kiện sau :

(i) ̂ ⊲ ; (ii) ⊲ ̂; và (iii) zˆmax( , )x yˆ ˆ .

Ta thấy rằng, với  ,  và k ≥ g cho trước sẽ có nhiều giá trị ngôn ngữ ̂ thỏa tiêu chuẩn xấp xỉ MAC hay JAC mà độ dài của nó thuộc vào đoạn [g, k]. Các mệnh đề sau sẽ chỉ ra cách thức để xác định tất cả giá trị ngôn ngữ có thể làm kết quả xấp xỉ cho meet và join của hai giá trị ngôn ngữ khi chúng có quan hệ kế thừa ngữ nghĩa.

Mệnh đề 2.2. Cho ĐSGT tuyến tính đầy đủ (AX, H, G, ≤), giả sử =

… ∈ ,  ớ  = 1, ( − 1); = … ∈ ,

 ớ  = 1, ( − 1); k ≥ g và ⊲ . Giả sử ∆ = (  … ) và

 = … là giá trị ngôn ngữ mức-k nhỏ nhất kế thừa ngữ nghĩa từ . Đặt = { ̂ , ̂ , … , ̂ } là tập các giá trị ngôn ngữ được xây dựng như sau:

̂ = = … ;

̂ = … ; …

̂ = ;

và MeetValues = { ̂ : ( ̂) ≤ ( )}. Khi đó MeetValues là tập tất cả các giá trị ngôn ngữ “xấp xỉ tốt” của ∆ .

Chứng minh: Để chứng minh MeetValues chứa tất cả giá trị ngôn ngữ là “xấp xỉ tốt” của ∆ , ta cần chứng minh với mọi ̂ , ̂ thỏa các điều kiện (i), (ii) và (iii) trong tiêu chuẩn xấp xỉ phép meet - MAC. Thật vậy:

- ̂ nên ̂ , theo cách xây dựng tập Z ta có ̂ ⊲ , hay điều kiện (i) được thỏa.

- Mặt khác, ta thấy quan hệ kế thừa ngữ nghĩa có tính chất bắc cầu nên = sẽ kế thừa ngữ nghĩa ̂ với j = g, …, (k-1), tức điều kiện (ii) được thỏa.

- Theo cách thiết lập tập hợp Z ta luôn có: ̂ < ̂ < ⋯ < ̂ < ̂ , do vậy

̂  (với j = g, …, k ) sẽ không lớn hơn ̂ . Mà ̂ = , có nghĩa là với mọi

̂  (với = , … , ), ( ̂ ) ≤ ( ). Hơn nữa, với ràng buộc MeetValues =

̂ có ( ̂) ≤ ( ) nên ̂ ≤ ( , ), hay điều kiện (iii) thỏa.■

Mệnh đề 2.3. Cho ĐSGT tuyến tính đầy đủ (AX, H, G, ≤), giả sử =

… ∈ ,  ớ  = 1, ( − 1); = … ∈ ,

 ớ  = 1, ( − 1); k ≥ g và ⊲ . Giả sử  = (  … ) và  = … là giá trị ngôn ngữ mức-k lớn nhất kế thừa ngữ nghĩa từ . Đặt = { ̂ , ̂ , … , ̂ } là tập các giá trị ngôn ngữ được xây dựng như sau:

̂ = = … ;

̂ = … ; …

̂ = ;

và JoinValues = { ̂ : ( ̂) ≥ ( )}. Khi đó JoinValues là tập tất cả các giá trị ngôn ngữ “xấp xỉ tốt” của ∇ .

Chứng minh: Tương tự chứng minh Mệnh đề 2.2.■

Mệnh đề 2.2 và 2.3 đưa ra cách thức xác định các giá trị chân lý ngôn ngữ tiềm năng, có thể làm kết quả của phép meet và join tương ứng. Tuy nhiên, lúc này sẽ có nhiều giá trị ngôn ngữ trong tập MeetValues thỏa MAC và cũng sẽ có nhiều giá trị trong tập JoinValues thỏa JAC, nên có thể đưa ra các cách khác nhau để lựa chọn một giá trị ngôn ngữ làm “xấp xỉ tốt nhất” cho các phép toán này. Trong luận án này, giá trị ngôn ngữ được xem là “xấp xỉ tốt nhất” của ∆ là phần tử thuộc MeetValues và có độ đo tính mờ lớn nhất. Một cách tương tự,

“xấp xỉ tốt nhất” của ∇ là phần tử thuộc JoinValues và có độ đo tính mờ lớn nhất. Từ đây, hai phép toán mới trên các giá trị chân lý ngôn ngữ được đề nghị sao cho kết quả của chúng luôn là một giá trị ngôn ngữ, đó chính là phép HA- Meet và phép HA-Join.

Định nghĩa 2.8. Phép HA-Meet - ∆

Cho hai giá trị chân lý ngôn ngữ trong ĐSGT và . Khi đó,

(i) Nếu và không có quan hệ kế thừa ngữ nghĩa thì ∆ = ∆ . (ii) Ngược lại, ∆ = ̂ với ̂ và có độ đo tính mờ lớn nhất.

Định nghĩa 2.9. Phép HA-Join - ∇

Cho hai giá trị chân lý ngôn ngữ trong ĐSGT và . Khi đó,

(i) Nếu và không có quan hệ kế thừa ngữ nghĩa thì ∇ = ∇ . (ii) Ngược lại, ∇ = ̂ với ̂ và có độ đo tính mờ lớn nhất.

Thuật toán 2.1 và Thuật toán 2.2 được đề xuất sau đây cho phép tính toán HA-Meet và HA-Join của hai giá trị chân lý ngôn ngữ tương ứng.

Thuật toán 2.1. Tính HA-Meet của hai giá trị chân lý ngôn ngữ Input:

- H– = {h–q, …, h–1}, H+ ={h1, h2, …, hp}; Bảng SIG của ĐSGT;

- = … ∈ ,  ớ  = 1, ( − 1);

- = … ∈ ,  ớ  = 1, ( − 1); và g  k.

Output: ̂ = ∆ Method:

Bước 1: //Trường hợp và không có quan hệ kế thừa ngữ nghĩa (1) if không kế thừa ngữ nghĩa từ then

if < then return ̂

else return ̂

end if end if

Bước 2: //Trường hợp kế thừa ngữ nghĩa từ (2) ̂  ;

(3) if =c– then sig1  –1 else sig1  1 end if (4) if > 1 then sig1 sig1  SIG(l1,c) end if

(5) for i = 2 to (g -1) do sig1  sig1  SIG(li, li–1) end for (6) for i = g to (k -1) do

(7) if ≤ then

̂ ̂ , break, end if

(8) if SIG(hp, li–1)  sig1 = –1 then ̂ ℎ ̂ , sig1  –sig1, li hp,

else

̂ ℎ ̂ , li h–q, end if

(9) end for return ̂.

Độ phức tạp tính toán của Thuật toán 2.1:

Dòng lệnh (1) có độ phức tạp tính toán là O(g). Các dòng lệnh từ (2) đến (4) có độ phức tạp tính toán là O(1). Dòng lệnh (5) có độ phức tạp tính toán là O(g). Dòng lệnh (7) có độ phức tạp tính toán là O(k(p+q)), vì nó phải tính giá trị định lượng ngữ nghĩa của ̂ và (xem thêm Thuật toán 1.1), dòng lệnh (8) có độ phức tạp tính toán là O(1). Do đó, dòng lệnh từ (6) đến (9) sẽ có độ phức tạp tính toán là O(k(p+q)(k-g)).

Tóm lại, thuật toán tính HA-meet của hai giá trị chân lý ngôn ngữ có độ phức tạp tính toán là O(k(p+q)(k-g)).

Thuật toán 2.2. Tính HA-Join của hai giá trị chân lý ngôn ngữ Input:

- H– = {h–q, …, h–1}, H+ ={h1, h2, …, hp}; Bảng SIG của ĐSGT;

- = … ∈ ,  ớ  = 1, ( − 1);

- = … ∈ ,  ớ  = 1, ( − 1); và g  k.

Output: ̂ = ∇ Method:

Bước 1: // Trường hợp và không có quan hệ kế thừa ngữ nghĩa if không kế thừa ngữ nghĩa từ then

if > then return ̂

else return ̂

end if end if

Bước 2: //Trường hợp kế thừa ngữ nghĩa từ

̂ 

if =c– then sig1  –1 else sig1  1 end if if > 1 then sig1 sig1  SIG(l1,c) end if

for i = 2 to (g -1) do sig1  sig1  SIG(li, li–1) end for for i = g to (k -1) do

if ̂ ≥ then

̂ ̂ , break end if

if SIG(hp, li–1)  sig1 = 1 then ̂  ℎ ̂ , li hp

else

̂ ℎ ̂ , sig1  –sig1, li h–q, end if

end for return ̂.

Độ phức tạp tính toán của Thuật toán 2.2:

Lập luận tương tự cách tính độ phức tạp tính toán trong Thuật toán 2.1, Thuật toán 2.2 có độ phức tạp tính toán là O(k(p+q)(k-g)).

Ví dụ 2.4. Cho ĐSGT (AX, G, H, ) với H– = {less, possibly}; H+ = {more, very}; G = {true, false}. Khi đó,

(i) less_very_true ∆ more_true = more_true

(ii) possible_more_true ∆ more_true = less_more_true (iii) less_more_true ∇ more_true = more_true

(iv) possible_more_true ∇ more_true = more_true

Định nghĩa 2.10. Giả sử ∈ có dạng = với  là chuỗi gia tử bất kỳ, phủ định của là ̅ = ̅ với = và = .

Ví dụ 2.5. Cho ĐSGT (AX, G, H, ) với H– = {less, possibly}; H+ = {more, very}; G = {true, false}. Khi đó,

(i) _ = _

(ii) _ _ = _ _ .