[Bài Giảng] Chương 2 - Các cơ sở của đặc tả

Nội dung

1. Mục tiêu của chương
2. Giới thiệu
3. Logic mệnh đề
4. Logic vị từ
5. Lý thuyết tập hợp
6. Tóm tắt chương
7. Bài tập

Mục tiêu của chương
Sau chương này, người học có thể:

• Thực hiện các phép toán trên mệnh đề.
• Lập bảng chân trị của 1 dạng mệnh đề.
• Chứng minh dạng mệnh đề là hằng đúng/sai.
• Chứng minh 2 dạng mệnh đề tương đương logic.
• Chứng minh các phép suy diễn trên mệnh đề.
• Biểu diễn các phát biểu dưới dạng vị từ.
• Sử dụng được 2 lượng từ “tồn tại” và “với mọi”.
• Chứng minh các suy diễn trên logic vị từ.
• Thực hiện được các phép toán trên tập hợp.
• Chứng minh các bài toán liên quan đến lý thuyết tập hợp.

Giới thiệu

• Đặc tả hình thức (ĐTHT) phải đảm bảo:
• Chính xác + nhất quán
• Ngắn gọn + đầy đủ
• Xử lý được bởi máy tính
• Do đó, ĐTHT được phát triển chủ yếu dựa trên các cơ sở toán học.

Một số cơ sở toán học liên quan mật thiết đến đặc tả hình thức:

1. Logic mệnh đề
2. Logic vị từ
3. Lý thuyết tập hợp

Logic mệnh đề

• Mệnh đề
• Các phép toán trên mệnh đề
• Dạng mệnh đề
• Tương đương logic
• Hệ quả logic
• Các nguyên tắc thay thế
• Các quy luật logic
• Các quy tắc suy diễn

Mệnh đề

• Mệnh đề là một phát biểu có giá trị chân lý xác định (hoặc đúng, hoặc sai)
• Mệnh đề đúng: có chân trị đúng
• Mệnh đề sai: có chân trị sai
• Mệnh đề thường được ký hiệu bởi P, Q, R, …
• Giá trị đúng biểu diễn bởi trị 1 hay T
• Giá trị sai biểu diễn bởi trị 0 hay F

Ví dụ:

• ‘Môn đặc tả hình thức là môn học bắt buộc đối với sinh viên chuyên ngành CNPM’
• ‘1+1= 2’
• ‘7 là một số chẵn’
• ‘4 là một số nguyên tố’
• ‘n là một số lẻ’
• ‘Hôm nay trời sẽ mưa’
• ‘Hôm qua trời mưa’

1. Phép phủ định

Phủ định của mệnh đề P, được ký hiệu là -P (đọc là KHÔNG P). Chân trị của P  là 0 nếu chân trị của P là 1 và ngược lại.

2. Phép nối liền

Phép nối liền của 2 mệnh đề P và Q, được ký hiệu là P ^ Q (đọc là P VÀ Q)

3. Phép nối rời

Phép nối rời của 2 mệnh đề P và Q, được ký hiệu là P v Q (đọc là P HOẶC Q)

4. Phép kéo theo

Mệnh đề nếu P thì Q được ký hiệu là P -> Q (đọc là P KÉO THEO Q)

4. Phép kéo theo 2 chiều

Mệnh đề nếu P thì Q và ngược lại được ký hiệu là P <-> Q (đọc là P KHI VÀ CHỈ KHI Q)

Dạng mệnh đề

• Là các biểu thức logic.
• Được xây dựng bằng cách kết hợp các biến mệnh đề với nhau bởi các phép nối theo một thứ tự nhất định.
• Có một chân trị xác định đối với từng bộ chân trị của các biến mệnh đề.
• Tập tất cả các chân trị của dạng mệnh đề ứng với từng chân trị của các biến mệnh đề lập thành bảng chân trị của dạng mệnh đề đó.

• Ví dụ : Dạng mệnh đề E(p, q, r) = p ^ (q ^ r) có bảng chân trị như sau:

Tương đương logic

• Hai dạng mệnh đề E và F được gọi là tương đương logic nếu chúng có cùng một bảng chân trị.
• Khi ấy ta viết E <=> F
• Mệnh đề dạng E <->F luôn mang chân trị bằng 1 cho dù các biến có lấy giá trị nào đi nữa.

• Ví dụ: Xét 2 mệnh đề: p -> q và -p v q

Như vậy ta nói 2 mệnh đề trên là tương đương logic, và được viết là:
(p -> q) <=> (-p v q)
Ghi chú: để chứng minh 2 dạng mệnh đề là tương đương logic, cách đơn giản nhất là chứng minh chúng có cùng bảng chân trị.

Hệ quả logic

• Dạng mệnh đề F được gọi là hệ quả logic của dạng mệnh đề E nếu E -> F luôn có chân trị đúng.
• Khi đó ta viết là E => F
• Ta có thể nói cách khác : E có hệ quả logic là F.

Các nguyên tắc thay thế

Quy tắc 1: trong dạng mệnh đề E, nếu ta thay thế biểu thức con F bởi một dạng mệnh đề tương đương logic thì dạng mệnh đề thu được vẫn còn tương đương logic với E.

Ví dụ: E(p,q,r)= (p->q) ->r
Đặt F = p ->q
Ta đã chứng minh được:
(p ->q) <=>(-p v q)
Thay F bởi -p v q, ta có:
E’=(-p v q) ->r
E’<=> E

Quy tắc 2: giả sử dạng mệnh đề E(p, q, r,…) là một hằng đúng. Nếu ta thay thế những nơi p xuất hiện trong E bởi một dạng mệnh đề tuỳ ý F(p’, q’, r’,…) thì dạng mệnh đề nhận được theo các biến p, q, r,…, p’, q’, r’,… vẫn còn là một hằng đúng.


Ví dụ: E(p,q)= (p->q) v (q->p)
E là 1 hằng đúng (tự chứng minh)
Thay p bởi r, ta có:
E’(r,q)= (r->q) v (q -> r)
E’ vẫn là hằng đúng
Thay p bởi a^b, ta có:
E”(a,b,q)= (a^b ->q) v (q-> a^b)
E” vẫn là hằng đúng
Các quy luật logic
Với:
p, q, r là các biến mệnh đề
1 là hằng đúng và 0 là hằng sai
ta có các tương đương logic sau:

Phủ định của phủ định:

• - -p <=> p

Quy tắc De Morgan

• -(p ^ q) <=> -p v -q
• và -(p v q) <=> -p ^ -q

Luật giao hoán

• p v q <=> q v p  
• và p ^ q <=> q ^ p

Luật kết hợp

p ^ (q ^ r) <=> (p ^ q) ^ r
và p v (q v r) <=> (p v q) v r

Luật phân bổ

• p^(q v r) <=> (p ^ q) v (p ^ r)
• và p v (q^r) <=> (p v q) ^ (p v r)

Luật lũy đẳng

• p v  p <=> p
• và p ^ p <=> p

Luật trung hòa

• p ^ 1 <=> p
• và p v 0 <=> p

Luật về phần tử bù

• p ^ -p <=> 0
• và p v -p <=> 1

Luật thống trị

• p ^ 0 <=> 0
• và p v 1 <=> 1

Luật hấp thụ

• p ^ (p v q) <=>  p
• và p v (p ^ q) <=> p

Ví dụ: Hãy chứng minh dạng mệnh đề sau là một hằng đúng:
[(r-> s) ^ [(r ->s) ->(-t v u)]] -> (-t v u)

Hướng dẫn: đặt p = r-> s
q = -t v u

Ví dụ 2: Chứng minh:
(p ^ q) -> r <=> p -> (q -> r)

Từ đó áp dụng vào trong lập trình, xét 3 đoạn chương trình sau:
int x, y, z = 3;
for (i=1 ; i<=10 ; i++)  {
x = z – i ;
y = z + 2*i ;
if ((x > 0) && (y > 0))
printf (“x + y =   %d\n”, x + y) ;
}
Các quy luật logic (10)
int x, y, z = 3;
for (i=1 ; i<=10 ; i++)  {
x = z – i ;
y = z + 2*i ;
if (x > 0)
if  (y > 0)
printf (“x + y = %d\n”, x + y) ;
}

int x, y, z = 3;
for (i=1 ; i<=10 ; i++)  {
x = z – i ;
y = z + 2*i ;
if (y > 0)
if (x > 0)
printf(“x + y = %d\n”, x + y) ;
}

****Các quy tắc suy diễn: 

Modus Ponens (khẳng định)

• [(p -> q) ^ p]         => q

Syllogism (Tam đoạn luận)

• [(p -> q) ^ (q -> r)] => (p -> r)

Modus Tollens (phủ định)

• [(p -> q) ^ (-q] <=> -p

Tam đoạn luận rời

• [(p v q) ^ -p] <=>q

Quy tắc mâu thuẫn

• [(p1 ^ p2 ^ … ^ pn) -> q]    <=>  [(p1^   p2 ^ …^ pn ^ -q) -> 0]

Quy tắc chứng minh theo trường hợp

• [(p -> r) ^ (q -> r)] => (p v q) -> r)

Ví dụ: Chứng minh
f(n) = n3 + 2n
luôn chia hết cho 3.


Logic vị từ

• Vị từ
• Lượng từ

Vị từ
Là một khẳng định p(x, y,…) trong đó có chứa một số biến x, y, ... lấy giá trị trong những tập hợp cho trước A,B,... sao cho:
Bản thân p(x, y,...) không phải là một mệnh đề.
Nếu thay x, y,… bằng những phần tử cố định nhưng tuỳ ý a A, b B,…thì ta được một mệnh đề p(a, b,…), tức là chân trị của nó hoàn toàn xác định. Khi đó x, y,… gọi là các biến tự do của vị từ.

Nói một cách khác, một vị từ là một hàm số dạng:
f: X ->  B
trong đó: X = A x B x … và B = {0, 1}

Ví dụ: p(n) = ‘‘n là một số nguyên tố’’ là một vị từ theo một biến tự do n thuộc N.
f: N  B
Với n = 2, 5, 7, 11 ta có các mệnh đề đúng p(2), p(5), p(7), p(11)
Còn với n = 4, 8 thì ta có các mệnh đề sai p(4), p(8).

Lượng từ

• Giả sử p(x) là vị từ theo một biến tự do x thuộc A, khi đó có 3 trường hợp có thể xảy ra :
• TH1 : khi thay x bởi một phần tử bất kỳ a A, ta đều được mệnh đề đúng p(a).
• TH2 : với một (hoặc một số) giá trị a A thì p(a) là mệnh đề đúng, và với một số giá trị b A thì p(b) là mệnh đề sai.
• TH3 : khi thay x bởi một phần tử bất kỳ a A, ta đều được mệnh đề sai p(a).

Đối với TH1 thì mệnh đề ‘‘với mọi x thuộc  A, p(x)’’ là một mệnh đề đúng, ký hiệu bởi ‘‘Với mọi x thuộc A, p(x)’’. Bản chất của mệnh đề này là phép VÀ (^)
Nếu TH1 hoặc TH2 xảy ra thì mệnh đề ‘‘tồn tại x thuộc A, p(x)’’ là một mệnh đề đúng, ký hiệu bởi " Tồn tại  x thuộc A, p(x)’’. Bản chất của mệnh đề này là phép HOẶC (v)
Các mệnh đề "Với mọi  x thuộc A", p(x) và Với mọi  x thuộc A, p(x) được gọi là lượng từ hoá của vị từ p(x) bởi lượng từ phổ dụng (Với mọi) và lượng từ tồn tại (Tồn tại ).

Chú ý:

• Trong mệnh đề lượng từ hoá, x không còn là biến tự do nữa mà nó bị ràng buộc bởi các lượng từ.
• TH3 ở trên có thể được viết lại : Với mọi x thuộc A,-p(x). Như vậy, phủ định của mệnh đề Với mọi x thuộc A, p(x) xảy ra khi TH2 hoặc TH3 xảy ra,tức là mệnh đề Tồn tại x thuộc A, - p(x) là mệnh đề đúng.

Rút ra :

• Phủ định của Với mọi x thuộc  A, p(x) là mệnh đề Tồn tại x Thuộc A,-p(x)
• Phủ định của Tồn tại x Thuộc A, p(x) là mệnh đề Vói mọi x thuộc A, -p(x)

Xét vị từ theo 2 biến x thuộc A, y  thuộc B: p(x, y)
Thay x bằng a  thuộc A, ta được p(a,y) là vị từ theo 1 biến y.
Lượng từ hóa vị từ này, ta có 2 mệnh đề:
 Với mọi y thuộc B, p(a,y)
 Tồn tại y thuộc B, p(a,y)

Như vậy, ta có:

•  Với mọi y thuộc B, p(x,y)
•  Tồn tại y thuộc B, p(x,y)

là 2 vị từ theo 1 biến x thuộc A.
Tiếp tục lượng từ hóa theo x, ta có:
Với mọi x thuộc  A ,Với mọi y thuộc B, p(x,y)
Tồn tại  x thuộc A, Với mọi y thuộc  B, p(x,y)
Tồn tại x thuộc A, Tồn tại y thuộc B, p(x,y)
Với mọi  x thuộc A, Tồn tại y thuộc B, p(x,y)

Định lý:
Với p(x,y) là vị từ theo 2 biến x,y, ta có:

• Với mọi x thuộc A ,Với mọi y thuộc B, p(x,y) <=> Với mọi y thuộc B ,Với mọi x thuộc A, p(x,y)
• Tồn tại x thuộc A , Tồn tại y thuộc B, p(x,y) <=> Tồn tại y thuộc B , Tồn tại x Thuộc A, p(x,y)
• Tồn tại x thuộc A ,Với mọi y thuộc B, p(x,y) <=> Với mọi y thuộc B , Tồn tại x thuộc  A, p(x,y)

Lý thuyết tập hợp

• Không trình bày lại toàn bộ các khái niệm liên quan đến lý thuyết tập hợp.
• Chỉ nhắc lại một số khái niệm cơ bản nhất và các ký hiệu dùng trong lý thuyết tập hợp:

1. Nếu a là một phần tử thuộc tập hợp A, ta viết a Î A, ngược lại ta viết a Ï A.
2. Tập hợp A thoả một tính chất nào đó, tính chất ở đây được biểu diễn dưới dạng một vị từ p(x)

Ta viết : A = {x U /p(x)}, trong đó U được gọi là tập vũ trụ.
Ví dụ :
A = {x Î N / x là số nguyên tố}
A = {x Î Z / x2 <5}

   3. Ngoài ra có thể biểu diễn tập hợp bằng cách liệt kê tất cả các phần tử của nó, ví dụ 2 ở trên có thể được viết lại A = {-2, -1, 0, 1, 2}
  4.Tập hợp không có phần tử nào cả gọi là tập hợp rỗng, được ký hiệu là Æ

  5. Giả sử A và B là 2  tập hợp con của tập vũ trụ U, ta nói A là tập con của B ( hay A được bao hàm trong B, hay B bao hàm A), ký hiệu A Ì B nếu:
"x Î U,(x Î A) Þ (x Î B)
  6. Nếu A Ì B và B Ì A, ta nói A bằng B, được ký hiệu A = B. Như vậy rõ ràng A = B khi và chỉ khi:
"x Î U, (x Î A) Û (x Î B)

Hợp (È) , giao (Ç) và phần bù của tập hợp:
A È B = {x Π U/ (x Î A) Ú (x Î B)}
A Ç B = {x Î U / (x Î A) Ù (x Î B)}
Ā = {x Î U / (x ÏA)},

Ā được gọi là phần bù của A trong U.

Tính chất trên tập hợp
1. Tính giao hoán:

•   A È B = B È A
•   A Ç B = B Ç A

2. Tính kết hợp:

A È (B È C) = (A È B) È C

A Ç (B Ç C) = (A Ç B) Ç C

3. Luật De Morgan:

A È B = Ā Ç`B

A Ç B = Ā È`B

4. Tính phân bố:
A È (B Ç C) = (A È B) Ç (A È C)
A Ç (B È C) = (A Ç B) È (A Ç C)

5. Phần tử trung hòa:

A È Æ = A

A Ç U = A

6. Phần bù:

A È Ā = U

A Ç Ā = Æ

7. Tính thống trị:

A È U = U

A Ç Æ = Æ

Tóm tắt chương

• Mệnh đề là phát biểu có tính chất đúng/sai.
• Trên kiểu mệnh đề cũng có các phép toán.
• Dạng mệnh đề là biểu thức chứa các biến mệnh đề, có bảng chân trị ứng với bộ giá trị các biến mệnh đề.
• Trên dạng mệnh đề có các khái niệm tương đương logic, hệ quả logic.
• 2 nguyên tắc thay thế.
• 10 quy luật logic.
• 6 quy tắc suy diễn.
• Vị từ là 1 hàm số dạng f: X B.
• Có 2 lượng từ chính là “với mọi” và “tồn tại”.
• Một số khái niệm chính trong lý thuyết tập hợp.

Bài tập
1. Hãy lấy phủ định của các mệnh đề sau:

• Ngày mai nếu trời mưa hay trời lạnh thì tôi sẽ không ra ngoài.
• 15 chia hết cho 3 nhưng không chia hết cho 4.
• Hình tứ giác này không phải là hình chữ nhật mà cũng không phải là hình thoi.
• Mọi tam giác đều có các góc bằng 600.

2. Lập bảng chân trị cho các mệnh đề sau:

a)Øp ® (p Ú q)

b)Øp ® (Øp Ú r)

c)(p Ú q) ® Øq

d)(p Ú r) ® (r Ú Øp)

e)(p ®q) Ú (q® p)

f)(p Ú Øq) Ù (Øp Ú q)

g)(p ® Øq) Ú (q ® Øp)

h)Ø(Øp Ù Øq)

3. Trong các khẳng định sau, hãy chỉ ra các khẳng định đúng:

a)p Þ p ® q

b)Ø(p ® q) Þ p

c)(p Ù q) Ú r Þ p Ù (q Ú r)

(p ® q) Ù (q ® r) Þ p ® (q ® r)

4. Cho biết suy luận nào trong các suy luận sau đây là đúng và quy tắc suy diễn nào đã được sử dụng?
CSG sẽ thắng trận nếu đối thủ đừng gỡ lại vào phút cuối.
Mà CSG đã thắng trận.
Vậy đối thủ của CSG không gỡ lại vào phút cuối.

5. Nếu Minh giải được bài toán thứ tư thì em đã nộp bài trước giờ quy định.
Mà Minh đã không nộp bài trước giờ quy định.
Vậy Minh không giải được bài toán thứ tư.

6. Nếu lãi suất giảm thì số người gửi tiết kiệm sẽ giảm.
Mà lãi suất đã không giảm.
Vậy số người gửi tiết kiệm không giảm.

7. Nếu được thưởng cuối năm Hà sẽ đi Đà Lạt.
Nếu đi Đà Lạt Hà sẽ ghé thăm Suối Vàng.
Do đó nếu được thưởng cuối năm Hà sẽ đi thăm Suối Vàng.

8. Lấy phủ định của các mệnh đề sau:
Nếu bình phương của một số nguyên là lẻ thì số nguyên ấy là lẻ.
Nếu x là một số thực sao cho x2 >16 thì x <-4 hay x >4
Với mọi số nguyên n, nếu n không chia hết cho 2 thì n là số lẻ
Với mọi số thực x, nếu | x-3| < 7 thì – 4 < x <10

HẾT CHƯƠNG 2
(còn tiếp…)