Bài giảng Toán rời rạc: Chương 1 - ThS. Trần Quang Khải

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

Thêm vào BST

Báo xấu

24
lượt xem 2
download

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

Bài giảng Toán rời rạc: Chương 1 Logic, cung cấp cho người học những kiến thức như: Propositional Logic; Predicate Logic. 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 Toán rời rạc: Chương 1 - ThS. Trần Quang Khải

TOÁN RỜI RẠC Chương 01 Logic Giảng viên: ThS. Trần Quang Khải
Nội dung 1. Propositional Logic. 2. Predicate Logic. Toán rời rạc Chương 1: Logic 2
What is LOGIC? Logic is the study of arguments. Toán rời rạc Chương 1: Logic 3
What is LOGIC? Logic is the study of arguments. In philosophy Logic (from the Greek) is the formal systematic study (sự nghiên cứu có tính hệ thống) of the principles (quy tắc) of valid inference and correct reasoning (lập luận có căn cứ và suy luận đúng). Toán rời rạc Chương 1: Logic 4
What is LOGIC? Trong toán học: các quy luật Logic giúp xác định ý nghĩa chính xác của các phát biểu toán học.  Logic toán học là một nhánh của toán học có quan hệ chặt chẽ với khoa học máy tính và logic triết học.  Phân biệt các suy luận đúng (valid) và không đúng (invalid) Toán rời rạc Chương 1: Logic 5
TOPIC 1 PROPOSITIONAL LOGIC (Logic mệnh đề) Giảng viên: ThS. Trần Quang Khải Toán rời rạc Chương 1: Logic 6
Propositions Mệnh đề (Proposition) là 1 câu (hoặc 1 phát biểu) tường thuật chỉ có giá trị “đúng” hoặc “sai”  Mệnh đề không thể vừa đúng vừa sai  Giá trị đúng hoặc sai của mệnh đề: chân trị. TRUTH VALUE Toán rời rạc Chương 1: Logic 7
Propositions - Examples 1. “Pigs can fly.” 2. “1 + 1 = 2.“ 3. “2 + 2 = 3.” 4. “Your teacher is Superman.” 5. “Hanoi is the capital of Vietnam.” 6. “Paris is the capital of London.” Toán rời rạc Chương 1: Logic 8
Sentences not to be propositions 1. What time is it? 2. Do your homework. 3. x + 1 = 3. 4. x + y = z. 5. What a pretty girl! Toán rời rạc Chương 1: Logic 9
Biểu diễn mệnh đề Biểu diễn 1 mệnh đề bằng 1 kí tự (letter).  VD: p, q, r, s, t, …  Gọi là biến mệnh đề (propositional variables or statement variables).  Phủ định một mệnh đề: ký hiệu ¬p Quy ước: Truth table  TRUE: T or 1.  FALSE: F or 0. p ¬p p ¬p T F 1 0 F T 0 1 Toán rời rạc Chương 1: Logic 10
Xác định chân trị Xác định 1 mệnh đề là true/false: không phải là nhiệm vụ của Logic Ex: Today is Friday. true or false depends on what is today. Toán rời rạc Chương 1: Logic 11
Negation (phủ định) Phủ định của một mệnh đề: “Today is Friday.”  “It is not the case that today is Friday.”  “Today is not Friday.”  “It is not Friday today.” Toán rời rạc Chương 1: Logic 12
Compound propositions Mệnh đề kết hợp (Mệnh đề phức hợp)  Các phát biểu thường gồm 1 hay nhiều mệnh đề.  Các mệnh đề kết hợp bằng toán tử logic (logical operators). Toán rời rạc Chương 1: Logic 13
Compound propositions George Boole (1854) – English mathematician  “The Mathematical Analysis of Logic” (1848).  “The Law of Thought” (1854)  Boolean Algebra. Toán rời rạc Chương 1: Logic 14
Toán tử Logic Gọi p, q là các mệnh đề:  ¬p: negation (phủ định).  p  q: conjunction (hội).  p  q: disjunction (tuyển).  p  q: exclusive-OR (tuyển loại – phép XOR).  p  q: implication (kéo theo). Kết quả của việc kết hợp các mệnh đề bằng các toán tử cũng là một mệnh đề. Toán rời rạc Chương 1: Logic 15
Toán tử Logic – Bảng chân trị p q ¬p pq pq pq pq pq T T F T T F T T T F F T T F F F T T F T T T F F F F F F T T Toán rời rạc Chương 1: Logic 16
Phép hội: p  q Mệnh đề “p và q” là:  TRUE khi cả p và q đều TRUE.  FALSE trong các trường hợp còn lại. Trong lập trình:  Kết hợp các điều kiện AND. if (a > 1 AND a < 4) then … p q pq T T T T F F F T F T F F Toán rời rạc Chương 1: Logic 17
Phép tuyển: p  q Mệnh đề “p hoặc q” là:  FALSE khi cả p và q đều FALSE.  TRUE trong các trường hợp còn lại. Trong lập trình:  Kết hợp các điều kiện OR. if (a > 1 OR a < 4) then … p q pq T T T T F T F T T F F F Toán rời rạc Chương 1: Logic 18
Phép tuyển loại: p  q Mệnh đề “p  q” là:  FALSE khi p và q đều là TRUE hoặc FALSE.  Nhận xét: p và q giống nhau.  TRUE trong các trường hợp còn lại.  Nhận xét: p và q khác nhau. Trong lập trình: p q pq  Phép XOR. T T F T F T F T T F F F Toán rời rạc Chương 1: Logic 19
Toán tử “kéo theo”: p  q Toán tử p → q có vai trò đặc biệt quan trọng trong toán học:  p: giả thiết (hypothesis).  q: kết luận (conclusion).  “Nếu p, thì q”  “p chỉ nếu q”  “p suy ra q”  “p là đủ cho q”  “Điều kiện cần cho p là q” Toán rời rạc Chương 1: Logic 20