Ngôn ngữ tân từ

Phần cú pháp:

    Trước hết chúng ta cần phải thống nhất về các ký hiệu:

( ) - Biểu thức trong ngoặc.

Biến: Tên gọi của một đại lượng biến thiên trong một miền giá trị xác định. Thường dùng các chữ cái nhỏ ở cuối bảng mẫu tự để đặt tên cho biến: x, y, z, ...

Hằng: Là các đại lượng không đổi. Thường sử dụng các chữ cái ở đầu bảng mẫu tự như a, b, c, ... làm tên hằng.

Hàm: Là một ánh xạ từ một miền giá trị vào tập hợp gồm 2 giá trị hoặc đúng hoặc sai. Thường dùng các chữ nhỏ ở giữa bảng mẫu tự như f, g, h. ...

Tân từ: Là một biểu thức được xây dựng dựa trên biểu thức lôgic. Thường dùnhg các chữ in hoa ở giữa như P, Q, R, ...

Các phép toán lôgic: phủ định ( ), kéo theo (Þ ), nối liền ( - conjuction) và nối rời ( - disjunction).

Các lượng từ: với mọi ( " ) và tồn tại ($ )

   Định nghĩa 7.1.2:

Tân từ một ngôi được định nghĩa trên 1 tập X và một biến x có giá trị chạy trên các phần tử của X.

Với mỗi giá trị của x, tân từ P(x) là một mệnh đề lôgic, tức là nó có giá trị hoặc là đúng (Đ), hoặc là sai (S).

   Ví dụ 7.2:

P(x), x là biến chạy trên X, là một tân từ.

P(gt), gt Ỵ X là một mệnh đề.

   Ví dụ 7.3: X là tập hợp những người có tên như sau:

X = { Nguyễn Văn Nam, Đặng Thị Thúy, Hồ thiệu Hùng ...}

Với tân từ NỮ (x) được xác định như: "x là người nữ". Khi đó mệnh đề:

NỮ (Nguyễn Văn Nam) - cho kết quả là sai.

NỮ (Đặng Thị Thúy) - Cho kết quả là đúng.

   Định nghĩa 7.1.3:

Tân từ n ngôi được định nghĩa trên các tập X 1 , X 2 , ¼ X n và n biến x 1 , x 2 , ¼ x n lấy giá trị trên các tập X i tương ứng. Với mỗi a i Ỵ X i x i = a i . Tân từ n ngôi là một mệnh đề.

Ký hiệu: P(x 1 , x 2 , ¼ x n )

   Ví dụ 7.4. CHA (x₁, x₂): "x₁ là CHA của x₂".

    Chú ý:

Các X_i không nhất thiết phải là rời nhau.

Với xi = ai, P(x₁, x₂,, ¼ , ai, ¼ x_n) là tân từ n-1 ngôi.

   Định nghĩa 7.1.4:

Từ (Word) được định nghĩa một cách truy hồi như sau:

(í) Từ là một hằng hay một biến.

(ii) f (t 1 , t 2 , ¼ , t n ) là một hàm n ngôi thì f là một từ.

   Định nghĩa 7.1.5:

Công thức (Formula):

(i) Công thức nguyên tố là một tân từ n ngôi P(t₁, t₂, ¼ , t_n);

    Ở đây t₁, t₂, ¼ , t_n là các từ.

    Công thức nguyên tố là một công thức.

(ii) Nếu F₁, F₂, ¼ , F_n là các công thức thì các biểu thức sau cũng là các công thức:

(· ) F₁ F₂

(· ) F₁ F₂

(· ) F₁ Þ F₂

(· ) F₁

(iii) Nếu F₁ là một công thức thì " x: F₁, $ x: F₁ cũng là các công thức.

(iv) Nếu F₁ là một công thức thì ( F₁ ) cũng là một công thức.

** Lưu ý: Chúng ta đã biết các phép biến đổi tương đương sau:

(· ) F₁ Þ F₂ º F₁ F₂

(· ) ( F₁ Þ F₂) º F₁ F₂

(· ) (" x F₁) º $ x F₁

   Định nghĩa 7.1.6:

() Một công thức được gọi là "đóng" nếu mọi biến của nó đều có kèm với lượng từ.

() Một công thức được gọi là "mở" nếu tồn tại một biến không có kèm với lượng từ.Biến này còn được gọi là biến tự do.

   Định nghĩa 7.1.7: Dạng chuẩn Prenexe:

F là một công thức có dạng: Q₁ x₁, Q₂ x₂, ¼ , Q_n x_n M

Với: Q_i là các lượng từ (i = 1, 2, ¼ , n).

x_i là các biến.

M là một ma trận công thức.

Nếu M không chứa lượng từ thì ta nói rằng F có dạng chuẩn Prenexe.

    Ví dụ 7.5:

" x $ t " y $ z ( P(x, y,a) Þ Q(y, z, t) R (x, t))

Diễn giải và mô hình

Diễn giải của 1 công thức:

    Một diễn giải của một công thức gồm 4 phần:

Miền giá trị của các biến của công thức (ký hiệu là tập M)

Việc sử dụng công thức:

Hằng là một giá trị cụ thể thuộc M.

Hàm n ngôi của Mn lên M là một ánh xạ f : Mn ® M

Tân từ trên Mn là một quan hệ n ngôi trên tập Mn.

Ý nghĩa của công thức và

Xác định 1 quan hệ n ngôi trên tập Mn

    Ví dụ 7.6 :

    Cho M = { Trí, Minh, Hưng, Long, Đoàn, Tuấn }và một công thức C có dạng như sau:

C: " x " y ( $ z (P(x,y) P(y,z) Þ Q(x, z))

    Tập diễn giải của công thức có thể là:

  M: là miền giá trị của các biến x, y, z.

  Các tân từ:

P: CHA

Q: ÔNG

  Ý nghĩa:

CHA (x, y): x có cha là y (hoặc: cha của x là y).

ÔNG (x, y): x có ông là y (hoặc ông của x là y)

  Các quan hệ 2 ngôi trên M²:

CHA = {(Trí, Minh), (Long, Đoàn), (Minh, Huy), (Đoàn, Tuấn)}

ÔNG = { (Trí, Huy), (Long, Tuấn) }

    Mỗi khi xác định được diễn giải phải đánh giá

(i) Công thức là đúng hay là sai. Ở đây C là đúng.

(ii) Với công thức mở có m biến tự do thì nó xác định 1 quan hệ m ngôi trên M^m.

    Với một bộ của quan hệ này, nếu ta thay thến m giá trị vào cho m biến thì công thức trở thành "đóng" và nó có giá trị hoặc đúng hoặc sai.

    Nếu tập các bộ m được cho bởi công thức "mở" mà rỗng (không có bộ nào để công thức là đúng, thì ta nói rằng "công thức này là sai", ngược lại thì công thức là đúng.

Ứng dụng lôgic toán trong CSDL.

Một câu hỏi trong ngôn ngữ tân từ có biến là bộ-n thỏa các quy tắc sau:

   Biến là một bộ của quan hệ.

   Từ: là hằng, biến hay biểu thức có dạng s[c], c là biến; c là tập các thuộc tính của quan hệ, còn được gọi là từ chiếu.

   Các biểu thức:

Rs : R: là một quan hệ;

s : là biến bộ – n.

được gọi là từ. Miền giá trị sẽ định nghĩa miền biến thiên của s.

t_1q a, t_1q t₂.

    Ở đây t₁ và t₂ là các từ chiếu, còn a là một hằng. q là toán tử so sánh =, ¹ , <, <=, >, >= được gọi là công thức nguyên tố.

Một công thức nguyên tố là một công thức.

Nếu F1 và F2 là các công thức thì F₁ F₂, F₁ F₂, F₂ và F₁ Þ F₂, cũng là các công thức.

Nếu F là một công thức và s là một biến tự do thì " s F và $ sF cũng là các công thức.

Nếu F là công thức thì (F) cũng là công thức (công thức đặt trong ngoặc tròn cũng là công thức).

   Định nghĩa 7.2.1:

    Một câu hỏi trong ngôn ngữ tân từ có biến là bộ-n được biểu diễn như sau:

{ s ½ F }

    Ở đây s là biến bộ – n, F là một công thức chỉ có một biến tự do là s.

   Ví dụ 7.11:

Quan hệ BIÊNGIỚI (Nước, Tỉnh_TP): Danh sách các nước có biên giới giáp với Việt nam.

Phép toán quan hệ BIÊNGIỚI [Nước] được chuyển thành câu hỏi trong ngôn ngữ tân từ có biến là bộ:

{ s [Nước] BIÊNGIỚI s }

Công thức an toàn:

 

Miền giá trị của công thức:

   Định nghĩa 7.2.2:

        Cho công thức F có sự hiện diện của các quan hệ Q 1 , Q 2 , … Q n và các hằng a 1 , a 2 , … a p . Miền giá trị của công thức F, ký hiệu là DOM(F) hay MGT(F), được định nghĩa là:

DOM (F) = { (a 1 , a 2 , … a p } : là tập giá trị của các thành phần của các bộ thuộc Q 1 , Q 2 , … Q n .

   Ví dụ 7.12: Cho 2 quan hệ R và S như sau:

R	A	B	S	A	B
	1	2		3	4
	3	4		2	2
	2	5

    Công thức F(s): Rs Ss.

    Miền giá trị của công thức F là DOM(F) = { 1, 2, 3, 4, 5 }

 Nhận xét: DOM(F) = DOM ( F). Thật vậy:

F = Rs Rs. S vẫn biến thiên trên R và S.

Công thức an toàn:

    Định nghĩa 7.2.3 :

Một công thức F được gọi là an toàn nếu nó thỏa mãn 3 điều kiện sau đây:

Nếu s là bộ-n thỏa: F(s) là đúng thì mọi thành phần của s là phần tử của DOM(F).

(F(s) : Đúng Þ s i Ỵ DOM (F); " i, s = (s 1 , s 2 , …, s n )

Với mỗi công thức con F ’ của F có dạng $ s F ’ (s), nếu s thỏa F’(s): Đúng, thì s Ỵ DOM(F’).

Với mỗi công thức con F’ của F có dạng " s F’(s), nếu có một thành phần nào đó của s không nằm trong DOM(F’) thì F’(s) là đúng. Nghĩa là $ s DOM(F) Þ F’(s): Đúng, hay F’(s): Sai Þ s Ỵ DOM (F’).

 

   Ví dụ 7.13: Như ví dụ trong điểm (a): 2 quan hệ R và S như sau:

R	A	B	S	A	B
	1	2		3	4
	3	4		2	2
	2	5

    Các câu hỏi:

c₁: { s ½ Rs Ss }

c₂: { s ½ Rs Ss }

F₁: Rs Ss không an toàn vì cho s = { 3,7 }, si DOM(F) mà không thỏa S Þ s thỏa F₁.

(s : F₁ (s): là Đúng và s DOM(F1))

F₂ = Rs Ss : là an toàn, nếu s thỏa F₂ Þ Rs : là Đúng Þ s Ỵ R do đó mọi thành phần của s Ỵ DOM(F2).

   Chúng ta có:

() F = Rs F’(s) là an toàn, với F’ là 1 công thức (không có công thức con có dạng " u F(u) và $ u F(u)).

() $ s ( F(s) G(s)) với F là an toàn.

() " s ( F(s) G(s)) với G là một công thức.

Þ (2).

: $ u F ’ (u), nếu u thỏa F ’(u) : Đúng Þ u Ỵ DOM(F ’, nếu u thỏa F ’(u) : Đúng Þ u Ỵ DOM(F ’ ).

$ u F ’ (u) Þ $ u F ’ Þ $ u F ’ (u)),

" u F ’),

" u F ’ (u)).

Theo (1):

" u ( F ’ (u) : Đúng Þ u Ỵ Dom(F ’).

    Theo (1):

" u ( F ’ (u) : Đúng Þ u Ỵ Dom(F ’ ).

" u( u Dom( F ’ ) Þ F ’(u) : Đúng ),

    mà

DOM (F ‘ ) = DOM ( F ’),

    nên ta có:

" u( u DOM( F ’ ) Þ F ’(u) : Đúng )