Bài giảng Đặc tả hình thức: Chương 2 - PGS.TS. Vũ Thanh Nguyên

Bài giảng Đặc tả hình thức: Chương 2 Cơ sở toán học trong đặc tả hình thức, cung cấp cho người đọc những kiến thức như: Lý thuyết tập hợp; Phép toán vị từ; Lượng từ; Luật suy diễn. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Đặc tả hình thức: Chương 2 - 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 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 1 Nội dung  Lý thuyết tập hợp  Phép toán vị từ  Lượng từ  Luật suy diễn 2 Lý thuyết Tập hợp 3 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} 4 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} 5 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 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} 7 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} 8 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 9 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 10 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) 11 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 12 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) 13 Lý thuyết tập hợp  Sơ đồ của các phép toán trên tập 14 Các hàm và thao tác trên tập hợp Phần tử t thuộc tập S 13  {0, 5, 11, 13, 19} tS Kết quả: true Phần tử t không thuộc tập S 13  {0, 5, 11, 19} tS Kết quả: true S1 là tập con (nghiêm ngặt) của S2 {‘r’, ‘e’}  {‘d’, ‘e’, ‘r’} S1  S2 Kết quả: true {‘r’, ‘e’}  {‘e’, ‘r’} Kết quả: false S1 là tập con của S2 {‘r’, ‘e’}  {‘d’, ‘e’, ‘r’} S1  S2 Kết quả: true {‘r’, ‘e’}  {‘e’, ‘r’} Kết quả: true Số lượng phần tử (cardinality) của card {1, 2, 8, 9} = 4 card S tập S 15 Các hàm và thao tác trên tập hợp Phép hội 2 tập hợp {‘r’, ‘e’}  {‘d’} S1  S2 Kết quả: {‘d’, ‘e’, ‘r’} Phép hội nhiều tập hợp U {{‘r’, ‘e’},{‘d’},{}, {‘d’, ‘s’}} U{S1, Kết quả: {‘d’, ‘e’, ‘r’, ‘s’} S2,…} Phép giao {1, 2, 3, 5, 7}  {2, 4, 6, 8} S1  S2 Kết quả: {2} Phép trừ {1.5, 3.6, 7.4} – {3.6} S1 – S2 Kết quả: {1.5, 7.4} Tích Descartes {1, 2, 3}  {6, 8} S1  S2 Kết quả: { (1, 6), (1, 8), (2, 6), (2, 8), (3, 6), (3, 8) } 16 Các tập hợp được định nghĩa sẵn Tập số n ...