zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:75

Báo xấu

9
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ố 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’, ‘+’, ‘-’, ‘=‘, ‘’, ‘*’, ‘/’, ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’, ‘.’, ‘,’, ‘?’, ‘!’, …} 17
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) } 18
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)} 19
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} 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.