Ktl-icon-tai-lieu

BÀI 1 MỘT SỐ KHÁI NIỆM MỞ ĐẦU

Được đăng lên bởi phandaobn
Số trang: 16 trang   |   Lượt xem: 1370 lần   |   Lượt tải: 0 lần
Page 1 of 16

1

BÀI 1
MỘT SỐ KHÁI NIỆM MỞ ĐẦU
1.1. Đồ thị
Đồ thị bao gồm tập V các đỉnh và E là một tập các cạnh, mỗi
cạnh là một cặp không có thứ tự của các đỉnh.
Đồ thị đầy đủ đỉnh n là một đồ thị với | V | = n, còn E chứa tất cả các cặp đỉnh.
Nghĩa là với bất kỳ hai đỉnh bất kỳ của V đều có một cạnh nối duy nhất.
Câu hỏi đặt ra là:: Có bao nhiêu cạnh?
1.2. Logic hình thức
Logic hình thức được định nghĩa bởi cú pháp và ngữ nghĩa
Cú pháp
Cú pháp của logic hình thức là việc sử dụng các đối tượng và gắn kết các đối
tượng để tạo ra một biểu thức logic chuẩn. Trong biểu thức logic bao gồm:
1. Tập các ký tự làm kí hiệu: a, b, c,…, A, B, C,…
2. Tập các phép toán logic: NOT, AND, OR, XOR (¬ , ∧, ∨, ⊕)
3. Một dày hữu hạn các ký hiệu và các phép toán để tạo ra một biểu thức logic
4. Một tập các quy tắc cho trước nhằm xác định biểu thức logic chuẩn (đúng quy
tắc).
Ngữ nghĩa
Ngữ nghĩa của biểu thức logic là ý nghĩa của biểu thức logic đó. Có thể dung các
phương pháp: quy nạp, đệ quy, suy luận để chứng minh biểu thức logic đã cho là
chuẩn hay không và cho giá trị đúng hoặc sai.
1.3. Mệnh đề logic (Propositional Logic)
1. Mệnh đề logic tuy đơn giản nhưng rất quan trọng trong khoa học máy tính.
Là cơ sở lập luận hàng ngày và trong lập trình
2. Là lý thuyết liên quan đến mạch số
3. Nhiều vấn đề có thể chuyển sang mệnh đề logic
4. Là một bộ phận rất quan trọng của các loại logic phức tạp hơn
Mệnh đề logic – Cú pháp
(

Mở ngoặc đơn, được đặt đầu nhóm, đầu biểu thức logic

)

Đóng ngoặc đơn, được đặt cuối nhóm, cuối biểu thức logic

Lê Huy Thập

1

11/10/2013

Page 2 of 16

2

¬ Phủ định - Not
∧ Hội (Conjunction) - And
∨ Tuyển (Disjunction) - Or
→ Ký hiệu điều kiện (Kéo theo - If…then…)
↔ Kéo theo hai chiều (if and only if)
A1, A2, ….. An … Ký hiệu mệnh đề 1, mệnh đề 2, …. mệnh đề thứ n
Chúng ta gỉa thiết rằng tập các ký tự trong biểu thức logic là đếm được, nhưng hầu
hết các kết luận vẫn đúng cho trường hợp không đếm được.
Các ký tự và ký hiệu
¬ Phủ định
∧ Hội
∨ Tuyển
→ Kéo theo (if…then…)
↔

Kéo theo hai chiều (if and only if)

Các ký hiệu: ¬, ∧, ∨, →, ↔ được dùng để nối các mệnh đề
Các ký hiệu: ¬, ∧, ∨, →, ↔ , ( , ) là các ký hiệu logic
Các ký hiệu: A1, A2, ….. An là các tham số, phi logic
Các ký hiệu logic có ý nghĩa không đổi, còn các tham số có nội dung phụ thuộc và
ngữ cảnh.
Biểu thức logic
Biểu thức logic là một dãy các ký hiệu. Một dãy được biểu thị bởi một danh
sách phân cách bởi dấu phẩy và được để trong dấu ngoặcc nhọn. Chẳng hạn : <a1,
a2, …,an>
Ví dụ
< (, A...
Page 1 of 16
BÀI 1
MỘT SỐ KHÁI NIỆM MỞ ĐẦU
1.1. Đồ thị
Đồ thị bao gồm tập V các đỉnh và E là một tập các cạnh, mỗi
cạnh là một cặp không có thứ tự của các đỉnh.
Đồ thị đầy đủ đỉnh n là một đồ thị với | V | = n, còn E chứa tất cả các cặp đỉnh.
Nghĩa là với bất kỳ hai đỉnh bất kỳ của V đều có một cạnh nối duy nhất.
Câu hỏi đặt ra là:: Có bao nhiêu cạnh?
1.2. Logic hình thức
Logic hình thức được định nghĩa bởi cú pháp và ngữ nghĩa
Cú pháp
Cú pháp của logic hình thức là việc sử dụng các đối tượng và gắn kết các đối
tượng để tạo ra một biểu thức logic chuẩn. Trong biểu thức logic bao gồm:
1. Tập các ký tự làm kí hiệu: a, b, c,…, A, B, C,…
2. Tập các phép toán logic: NOT, AND, OR, XOR (¬ , , , )
3. Một dày hữu hạn các ký hiệu và các phép toán để tạo ra một biểu thức logic
4. Một tập các quy tắc cho trước nhằm xác định biểu thức logic chuẩn (đúng quy
tắc).
Ngữ nghĩa
Ngữ nghĩa của biểu thức logic là ý nghĩa của biểu thức logic đó. Có thể dung các
phương pháp: quy nạp, đệ quy, suy luận để chứng minh biểu thức logic đã cho là
chuẩn hay không và cho giá trị đúng hoặc sai.
1.3. Mệnh đề logic (Propositional Logic)
1. Mệnh đề logic tuy đơn giản nhưng rất quan trọng trong khoa học máy tính.
Là cơ sở lập luận hàng ngày và trong lập trình
2. Là lý thuyết liên quan đến mạch số
3. Nhiều vấn đề có thể chuyển sang mệnh đề logic
4. Là một bộ phận rất quan trọng của các loại logic phức tạp hơn
Mệnh đề logic – Cú pháp
( Mở ngoặc đơn, được đặt đầu nhóm, đầu biểu thức logic
) Đóng ngoặc đơn, được đặt cuối nhóm, cuối biểu thức logic
Lê Huy Thập 11/10/2013
1
1
BÀI 1 MỘT SỐ KHÁI NIỆM MỞ ĐẦU - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
BÀI 1 MỘT SỐ KHÁI NIỆM MỞ ĐẦU - Người đăng: phandaobn
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
16 Vietnamese
BÀI 1 MỘT SỐ KHÁI NIỆM MỞ ĐẦU 9 10 267