02.CoSoToan Dac Ta Hinh Thuc

1
Chương 2: Cơ sở Toán học
trong Đặc tả Hình thức
Giảng viên: PGS.TS. Vũ Thanh Nguyên
Trường Đại học Công Nghệ Thông Tin, ĐHQG-HCM
Khoa Công Nghệ Phần Mềm
2
Nội dung
Lý thuyết tập hợp
Phép toán vị từ
Lượng từ
Luật suy diễn
3
Lý thuyết Tập hợp
4
Lý thuyết tập hợp
Tập hợp
Các phần tử trong tập hợp không có thứ tự
Không có phần tử trùng nhau
Các phần tử có cùng kiểu dữ liệu

Xác định tập hợp dạng tường minh
Ví dụ: {1, 3, 5} {1, 5, 3}
{3, 5, 1} {3, 1, 5}
{5, 3, 1} {5, 1, 3}
Ví dụ: {6, …,10} tương đương với {6, 7, 8, 9, 10}
5
Lý thuyết tập hợp
Xác định tập hợp dạng tường minh
{1, 3, 5} = {1, 5, 3} = {3, 5, 1} = {3, 1, 5} = {5, 3, 1} = ={5, 1, 3}
{a} ≠ a

Ví dụ: {6, …,10} tương đương với {6, 7, 8, 9, 10}
{iZ| 1 ≤ z ≤ 3} = {1,2,3}
{2,…,2} = {2}

6
Lý thuyết tập hợp
Thuộc tập hợp: 
Ví dụ: 3  {1, 3, 5}
Không thuộc tập hợp: 
Ví dụ: 2  {1, 3, 5}
Tập rỗng, ký hiệu {}
Lưu ý: j
{f(i) | p(i)}, ở đó f xác định đầy đủ trên D, khi đó nó có nghĩa
x{f(i) | p(i)}  iD  p(i)  x= f(i)
7
Lý thuyết tập hợp
Giả sử S1 = {a,b,c}, S2 = {c,d}
Phép hội: S1  S2 = {a,b,c,d}. Nó có thể định nghĩa
e1e2 = {x| xe1  xe2}
Phép hội nhiều tập
Uss = {x | ess  xe}
Ví dụ:
U{S1,{e},S2,{}}= {a,b,c,d,e}

Phép giao: S1  S2 = {c}. Nó có thể định nghĩa
e1e2 = {x| xe1  xe2}
8
Lý thuyết tập hợp
Phép hiệu: S1 – S2 = {a,b}. Nó có thể định nghĩa
e1 – e2 = {x| xe1  xe2}
Đôi khi: S1 – S2  S1 S2 = S2 (phần bù của S2)
Tập con
Ví dụ: {c} S1
S1  S1
S1  (S1S2)
{}  S1
Nó có thể định nghĩa:
e1  e2 = {xe1  xe2}
9
Lý thuyết tập hợp
Tập con nghiêm ngặt
Ví dụ: {} S1
{a,b}  S1
(S1  S2)

Nó có thể định nghĩa:
e1  e2  e1  e2  (e2  e1)
Suy luận
e1 = e2  e1  e2  e2  e1
10
Lý thuyết tập hợp
Giả sử PT, QT, và RT
 là phản xạ: P  P
 là bắc cầu: (P  Q  Q  R) P  R
 là phản đối xứng: (P  Q  Q  P)  P = Q
[T] là nhỏ nhất của T: [T]  P
11
Lý thuyết tập hợp
 là giá trị lớn nhất của cận dưới của 
R  P  R  Q  R  (P  Q)
(P  Q) cũng là tập con lớn nhất của cả hai P và Q
 là không thay đổi: P  P = P
 là đối xứng: P  Q = Q  P
 là giao hoán: (P  Q)  R = P  (Q  R)
 là tính tăng: P  Q  (R  P)  (R  Q)
12
Lý thuyết tập hợp
Cardinality (Card) của một tập là số phần tử trong một tập
Ví dụ
Card S1 = 3
Card S2 = 2
Card {} = 0
13
Lý thuyết tập hợp
Tích Descartes
P x Q = {p : P; q : Q  (p,q)}
Tổng quát
T1 x T2 x T3 x…x Tn = {x1:T1,x2:T2,x3:,…,xn:Tn  (x1,x2,x3,…,xn)}
Lưu ý:
A x B ≠ B x A và
(A x B) x C ≠ A x (B x C)
14
Lý thuyết tập hợp
Sơ đồ của các phép toán trên tập
15
Các hàm và thao tác trên tập hợp
16
Các hàm và thao tác trên tập hợp
17
Các tập hợp được định nghĩa sẵn
Tập số nguyên ℤ = {…, -2, -1, 0, 1, 2, …}
Tập số tự nhiên ℕ = {0, 1, 2, 3, …}
Tập số nguyên dương ℕ1 = {1, 2, 3, …}
Tập số thực ℝ
Tập số hữu tỉ ℚ
Tập boolean B = {true, false}
Tập ký tự (gồm chữ cái hoa/thường, số, phép toán, dấu câu)
Char = {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’, ‘j’, ‘k’, ‘l’, ‘m’,
‘n’, ‘o’, ‘p’, ‘q’, ‘r’, ‘s’, ‘t’, ‘u’, ‘v’, ‘w’, ‘x’, ‘y’, ‘z’,
‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’, ‘I’, ‘J’, ‘K’, ‘L’, ‘M’,
‘N’, ‘O’, ‘P’, ‘Q’, ‘R’, ‘S’, ‘T’, ‘U’, ‘V’, ‘W’, ‘X’, ‘Y’, ‘Z’,
‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘+’, ‘-’, ‘=‘, ‘<‘, ‘>’,
‘*’, ‘/’, ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’, ‘.’, ‘,’, ‘?’, ‘!’, …}
18
Xác định tập hợp thông qua tính chất
Xác định tập hợp một cách không tường minh dựa vào tính chất của các phần tử trong tập hợp
Hình thức tổng quát của định nghĩa tập có thể lấy theo hình thức sau:
{x: kiểu dữ liệu (type) | Vịtừ (x) (predicate(x))}
hoặc tổng quát:
{ ký hiệu (signature)| Vị từ (predicate)}, ở đó ký hiệu có thể bao gồm nhiều biến
Vậy cách biểu diễn là
{ x  P(x) } hay { x : S P(x) }
19
Xác định tập hợp thông qua tính chất
Công thức tổng quát
{x: kiểu dữ liệu (type) | Vịtừ (x) (predicate(x))  Biểu thức (expresion)}
Vậy cách biễu diễn là
{x1:T1;…; xn:Tn| Vị từ  (x1,…xn)}
20
Xác định tập hợp thông qua tính chất
Ví dụ:
{ x : Z (0 < x < 10)  La_So_Chan(x) }
tương đương với {2, 4, 6, 8}
{ x : Z La_So_Chan(x)  La_So_Le(x) }
tương đương với { }
{ x: N | x is_prime}
tương đương với {2,3,5,7,11,13,…}
{ x: N | x is_prime  x≠2}  {x:N| x is_odd}
Tập các số nguyên tố là tập con của số lẻ.
{ x: N | x is_prime  xx}
21
Mối quan hệ giữa tập và vị từ
Ví dụ:
{x : T| p } {x : T| q} = {x : T| pq }
{x : T| p } {x : T| q} = {x : T| pq }
{x : T| p}- = {x : T| p} (T là dạng cơ bản)
{x : T| p}  {x : T| q} nếu và chỉ nếu p  q
{x : T| p} = {x : T| q} nếu và chỉ nếu p  q
[T] = {x : T| false}
T = {x : T| true}
22
Logic mệnh đề
và Phép tính mệnh đề
23
Logic mệnh đề
Mệnh đề (proposition):
Khẳng định có giá trị chân lý xác định (hoặc Đúng hoặc Sai, không thể vừa Đúng vừa Sai)
Ví dụ:
Trong hệ cơ số 10, 2+2 = 4 => Giá trị chân lý: Đúng
Năm 2000 là năm nhuận => Giá trị chân lý: Đúng
4 là số nguyên tố => Giá trị chân lý: Sai
Các khẳng định dưới dạng tán thán, hoặc mệnh lệnh không phải là mệnh đề vì nó không có chân trị nhất định
Ký hiệu thông thường
Mệnh đề: P, Q, R,…
Chân trị: 1 (đúng), 0 (sai), T (đúng), F (sai)
24
Mệnh đề và Liên từ
Có thể chia mệnh đề thành 2 loại:
Mệnh đề phức hợp: được xây dựng từ các mệnh đề khác nhờ liên kết chúng lại bằng các liên từ (và, hay, nếu… thì…) hoặc trạng từ “không”
Ví dụ: “4 không phải là số nguyên tố” là mệnh đề phức hợp
Mệnh đề nguyên thủy/mệnh đề sơ cấp: không thể xây dựng từ các mệnh đề khác nhờ các liên từ hay trạng từ “không”
Ví dụ: “3 là số nguyên dương”
Mục đích của Phép tính mệnh đề:
Nghiên cứu chân trị của một mệnh đề phức hợp từ chân trị của các mệnh đề đơn giản hơn và các phép nối những mệnh đề này thể hiện qua liên từ hoặc trạng từ “không”
25
Mệnh đề vs Vị từ
Khẳng định “n là số nguyên tố” không phải là mệnh đề.
Nếu thay n bởi một số nguyên cố định nào đó thì ta sẽ được một mệnh đề.
Ví dụ: với n=3, ta được một mệnh đề đúng
Ví dụ: với n=4, ta được một mệnh đề sai
Khẳng định “n là số nguyên tố” là một Vị từ (predicate)
26
Các phép nối
Phép Phủ định (not)
Phép nối liền / Phép hội (and)
Phép nối rời / Phép tuyển (or)
Phép kéo theo
Phép kéo theo 2 chiều
27
Bảng chân trị
t
f
t
t
t
t
t
f
t
f
f
t
28
Độ ưu tiên
Cao nhất



Thấp nhất
29
Dạng mệnh đề
Trong Đại số, ta có các biểu thức đại số được xây dựng từ:
Các số nguyên, hữu tỉ, thực …  gọi là hằng số
Các biến x, y… có thể lấy giá trị là các hằng số
Các phép toán thao tác trên hằng số và các biến theo một thứ tự nhất định
Khi thay thế các biến trong 1 biểu thức đại số bởi các hằng số thì kết quả thực hiện phép toán trong biểu thức sẽ là một hằng số nào đó.
30
Dạng mệnh đề
Trong phép tính mệnh đề, “biểu thức logic” hay Dạng mệnh đề được xây dựng từ:
Các mệnh đề (hằng mệnh đề)
Các biến mệnh đề (p, q…) có thể lấy giá trị là các mệnh đề nào đó
Các phép nối thao tác trên các hằng mệnh đề và biến mệnh đề theo một thứ tự nhất định
Ví dụ: E(p, q, r) = (p  q)  (( r)  P )

Giả sử E, F là 2 dạng mệnh đề, khi ấy, E, E  F, E  F, E  F, E  F là các dạng mệnh đề
31
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 bảng chân trị.
Khi đó, ta viết E  F

Lưu ý: Nếu E và F tương đương logic thì Dạng mệnh đề E  F luôn lấy giá trị 1 dù các biến có lấy giá trị nào đi nữa

Một dạng mệnh đề được gọi là hằng đúng nếu nó luôn lấy chân trị 1
Một dạng mệnh đề được gọi là một hằng sai hay mâu thuẫn nếu nó luôn lấy chân trị 0
32
Ví dụ
Mệnh đề

tương đương với
33
Quy luật logic
Với p, q, r là các biến mệnh đề, 1 là hằng đúng, 0 là hằng sai, ta có các tương đương logic:
Phủ định của phủ định:  p  p
Quy tắc De Morgan:  (p  q )   p   q
 (p  q )   p   q
Luật giao hoán: p  q  q  p
p  q  q  p
Luật kết hợp: p  (q  r)  (p  q)  r
p  (q  r)  (p  q)  r
Luật phân bố: p  (q  r)  (p  q)  (p  r)
p  (q  r)  (p  q)  (p  r)
34
Quy luật logic
Luật lũy đẳng: p  p  p
p  p  p
Luật trung hòa: p  1  p
p  0  p
Luật về phần tử bù: p  p  0
p  p  1
Luật thống trị: p  0  0
p  1  1
Luật hấp thụ: p  (p  q)  p
p  (p  q)  p
35
Lượng từ
Lượng từ 
 biến  Kiểu  Vị từ phát biểu với biến đã khai báo
Lượng từ 
 biến  Kiểu  Vị từ phát biểu với biến đã khai báo

Ghi chú:
Trong trường hợp có phát biểu
 biến1  Kiểu   biến2  Kiểu  Vị từ P
ta có thể viết lại như sau:
 biến1, biến2  Kiểu  Vị từ P
Tương tự đối với lượng từ 
36
Luật suy diễn
Quan sát được p đúng và q đúng
Suy diễn ra được p  q đúng
p q
p  q
37
Luật suy diễn
E1
E2
E1=
38
Luật suy diễn
E1=
E1
(p  q )  (p  r)
39
Luật suy diễn





Luật suy diễn cơ sở (tiên đề)
Luật introduction
Luật elimination
Tiền đề
Kết luận
[quy tắc]
40
Liên từ 
and-introduction:



and-elimination:
41
Ví dụ 1
Quan sát được p ^ q là đúng, suy diễn ra là q ^ p cũng đúng




Chứng minh:



?
42
Liên từ 
or-introduction:




or-elimination:
43
Ví dụ 2
Nếu quan sát được p  q là đúng thì suy diễn ra được q  p cũng đúng:
44
Liên từ 
-introduction:




-elimination:


45
Ví dụ 3
?
46
Ví dụ 3
47
Ví dụ 3
48
Ví dụ 3
49
Ví dụ 3
50
Ví dụ 3
51
Ví dụ 3
52
Ví dụ 3
53
Tính bắc cầu của 
54
Liên từ 
-introduction:




-elimination:
55
Ví dụ 4
?
56
Ví dụ 4
p  q
p  q  p
57
Ví dụ 4
58
Ví dụ 4
59
Ví dụ 4
60
Ví dụ 4
61
Ví dụ 4
62
Ví dụ 4
63
Ví dụ 4
64
False và trạng từ 
false-elimination:




false-introduction:
65
Ví dụ 5
?
66
Ví dụ 5
67
Ví dụ 5
68
Ví dụ 5
69
Ví dụ 5
70
Ví dụ 5
71
Ví dụ 5
72
Ví dụ 5
73
Ví dụ 5
74
Ví dụ 5
75
Ví dụ 5