Bài giảng Toán rời rạc - Chương 1: Logic

Giảng viên: ThS. Trần Quang Khải TOÁN RỜI RẠC Chương 01 Logic Toán rời rạc Nội dung 1. Propositional Logic. 2. Predicate Logic. 2Chương 1: Logic Toán rời rạc What is LOGIC? Chương 1: Logic 3 Logic is the study of arguments. Toán rời rạc What is LOGIC? Chương 1: Logic 4 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 What is LOGIC? Chương 1: Logic 5 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 Giảng viên: ThS. Trần Quang Khải PROPOSITIONAL LOGIC (Logic mệnh đề) Chương 1: Logic 6 TOPIC 1 Toán rời rạc Propositions Chương 1: Logic 7 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 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.” Chương 1: Logic 8 Toán rời rạc 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! Chương 1: Logic 9 Toán rời rạc 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:  TRUE: T or 1.  FALSE: F or 0. Chương 1: Logic 10 p ¬p 1 0 0 1 Truth table p ¬p T F F T Toán rời rạc Xác định chân trị Chương 1: Logic 11 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 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.” Chương 1: Logic 12 Toán rời rạc Compound propositions Chương 1: Logic 13 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 Compound propositions George Boole (1854) – English mathematician  “The Mathematical Analysis of Logic” (1848).  “The Law of Thought” (1854)  Boolean Algebra. Chương 1: Logic 14 Toán rời rạc 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 đề. Chương 1: Logic 15 Toán rời rạc 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 F T F T F F T T F F F T T T F F T T F T F T T T F F T Chương 1: Logic 16 Toán rời rạc 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 Chương 1: Logic 17 p q p  q T T F T T F T F T F F F Toán rời rạc 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 Chương 1: Logic 18 p q p  q T T F F T F T F T T T F Toán rời rạc 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: Phép XOR. Chương 1: Logic 19 p q p  q T T F F T F T F F T T F Toán rời rạc Toán tử “kéo theo”: p  q Chương 1: Logic 20 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 Toán tử “kéo theo”: p  q Toán tử p → q là:  FALSE khi p = TRUE và q = FALSE.  TRUE trong các trường hợp còn lại. Chương 1: Logic 21 p q p  q T T F F T F T F T F T F Toán rời rạc Toán tử “kéo theo”: p  q Ví dụ: 1. “Messi đá hay thì đội Việt Nam bị loại” (đúng  đúng) 2. “Con lợn biết bay thì iPhone 5 có giá rẻ” (sai  sai) 3. “If today is Friday, then 2 + 3 = 5” (true/false  true) 4. “If today is Friday, then 2 + 3 = 6” (true/false  false) 5. “If you study discrete maths well, you will earn much money” Chương 1: Logic 22 Toán rời rạc Vì sao TRUE→ FALSE là sai? Chỉ sai khi giả thiết (hypothesis) p là đúng nhưng kết luận (conclusion) q là sai sai vì không tuân theo luật. Chương 1: Logic 23 Toán rời rạc Quan hệ “nguyên nhân – hệ quả” Cause (hypothesis, antecedent, premise) – effect (conclusion, consequence):  Ex: “Nếu bạn chém gió quá nhiều người yêu của bạn sẽ không còn tin bạn” Phép kéo theo trong logic:  Ex: “Nếu môn toán rời rạc dở, thì Bill Gates là siêu cầu thủ” Phép kéo theo trong logic tổng quát hơn quan hệ “nhân-quả” trong ngôn ngữ tự nhiên. Chương 1: Logic 24 Toán rời rạc Toán tử “kéo theo”: p  q q  p: mệnh đề đảo (converse). ¬q  ¬p: mệnh đề phản đảo (contrapositive) ¬p  ¬q: mệnh đề nghịch đảo (inverse) Chương 1: Logic 25 Toán rời rạc Toán tử “kéo theo”: p  q Ví dụ: Xây dựng bảng chân trị cho mệnh đề (p  ¬q) → (p  q) Chương 1: Logic 26 p q ¬q p  ¬q p  q (p  ¬q) → (p  q) T T F F T F T F F T F T T T F T T F F F T F T F Toán rời rạc Toán tử “tương đương”: p  q Toán tử p  q là:  TRUE khi p và q có cùng chân trị.  FALSE trong các trường hợp còn lại. Chỉ đúng khi cả p  q và q  p đều đúng. Nhận xét: ngược lại toán tử XOR. Thực chất: Không thực sự gọi là “tương đương”. Phát biểu “điều kiện đôi” (biconditional statements). Phép “kéo theo hai chiều” (bi-implications). Chương 1: Logic 27 Toán rời rạc Toán tử “tương đương”: p  q Diễn giải:  “p nếu và chỉ nếu q”.  “p là cần và đủ để/đối-với q”.  “nếu p thì q và ngược lại”. Ví dụ:  “Con bò biết lập trình nếu và chỉ nếu hạt mưa rơi”.  “Cái nồi nhảy hip-hop là cần và đủ để con trai yêu con gái”. Chương 1: Logic 28 Toán rời rạc Mệnh đề tương đương Chương 1: Logic 29 Logical Equivalence Hai mệnh đề kết hợp được gọi là “tương đương logic” nếu chúng có bảng chân trị giống nhau. Hai mệnh đề kết hợp p, q là tương đương nếu p  q là đúng trong mọi trường hợp (tautology) Ký hiệu: p  q Có thể chứng minh 2 mệnh đề tương đương bằng cách so sánh bảng chân trị của chúng Toán rời rạc Mệnh đề tương đương Chương 1: Logic 30  Tautology (hằng đúng): mệnh đề luôn luôn đúng.  Contradiction (mâu thuẫn): mệnh đề luôn luôn sai.  Ví dụ: p ¬p p  ¬p p  ¬p T F F T F F T T Mâu thuẫn Hằng đúng Toán rời rạc Mệnh đề tương đương Ví dụ 1: Chứng minh ¬(pq)  ¬p¬q Chương 1: Logic 31 p q ¬p ¬q ¬(p  q) ¬p¬q T T F F T F T F F F T T F T F T F F F T F F F T Toán rời rạc Mệnh đề tương đương Ví dụ 2: Chứng minh ¬(p  q)  ¬p  ¬q Chương 1: Logic 32 p q ¬p ¬q ¬(p  q) ¬p¬q Toán rời rạc Mệnh đề tương đương Ví dụ 3: Chứng minh ¬p  q  p → q Chương 1: Logic 33 p q ¬p ¬q ¬p  q p → q Toán rời rạc Một số luật quan trọng (1) Chương 1: Logic 34 Toán rời rạc Một số luật quan trọng (2) Chương 1: Logic 35 Toán rời rạc Chứng minh mệnh đề tương đương Chương 1: Logic 36 Toán rời rạc Bài tập 1. Viết 10 câu mệnh đề và cho biết chân trị của chúng. 2. Lập bảng chân trị cho các mệnh đề: a) (p  ¬q)  q b) (p  q)  (p  q) c) (p  q)  (q  p) d) p  ¬q e) (p  q) (p  ¬q) 3. Chứng minh: (p  q)  (¬q  ¬p). 4. Chứng minh (p  q)  (p  q) là hằng đúng. Chương 1: Logic 37 Toán rời rạc Bài tập 5. Chuyển các câu sau sang dạng mệnh đề: a) Nếu người đi bộ băng qua đường thì hoặc là đèn điều khiển đang xanh hoặc là sức khỏe người đi bộ không tốt. b) Người đi xe máy không thể vượt đèn đỏ nếu anh ta thấy công an trừ khi anh ta quá liều. Chương 1: Logic 38 Toán rời rạc Giảng viên: ThS. Trần Quang Khải PREDICATE LOGIC (Logic vị từ) Chương 1: Logic 39 TOPIC 2 Toán rời rạc Điểm yếu của Logic mệnh đề Không thể biểu diễn các phát biểu có chứa biến (variables). Ex:  x = y + 4.  x > 3 Các biến KHÔNG có giá trị cụ thể. Xuất hiện nhiều trong thực tế. Chương 1: Logic 40 Toán rời rạc Điểm yếu của Logic mệnh đề Một số phát biểu tương đương: “Not all birds fly.” AND “Some bird don’t fly.” “Không phải tất cả bánh đều ăn được.” “Chỉ một số bánh ăn được.” “Không phải mọi số nguyên đều là số lẻ.” AND “Một số số nguyên là số lẻ.” Cách duy nhất để suy luận là liệt kê tất cả các mệnh đề một cách phân biệt. Chương 1: Logic 41 Toán rời rạc Điểm yếu của Logic mệnh đề Giả sử ta biết: “Mọi sinh viên IT phải học toán rời rạc.” Không có luật nào của Logic mệnh đề cho phép kết luận chân trị của phát biểu: “Ronaldo phải học toán rời rạc.” Trong đó Ronaldo là một sinh viên IT. Không có luật để tìm chân trị của phát biểu: “Có một sinh viên IT không học toán rời rạc.” Chương 1: Logic 42 Toán rời rạc Vị từ (Vị ngữ) Ví dụ: “x > 3” (x lớn hơn 3) “x”: chủ ngữ “lớn hơn 3”: vị ngữ P(x): x > 3 (P kí hiệu vĩ ngữ “lớn hơn 3”) Xét P(x): x > 3  Mệnh đề P(4) có chân trị là TRUE (4 > 3).  Mệnh đề P(2) có chân trị là FALSE (2 > 3). P(x) là giá trị hàm mệnh đề P tại x. Chương 1: Logic 43 Toán rời rạc Vị từ (Vị ngữ) Thực tế: câu thường có nhiều biến hơn. Ví dụ: xét câu “x = y + 3”. Q(x,y): x = y +3 Xét chân trị của các mệnh đề Q(1,2) và Q(3,0)? Chương 1: Logic 44 Toán rời rạc Predicate Chương 1: Logic 45 Vị từ Predicate (vị từ) là một hàm mệnh đề mô tả thuộc tính của các đối tượng và mối quan hệ giữa chúng. Ký hiệu Một phát biểu có n biến x1, x2, , xn, biểu diễn là P(x1, x2, , xn), được gọi là hàm mệnh đề. Ví dụ: P(x,y,z): x + y = z. Toán rời rạc Predicate IS NOT Proposition Statement “x > 1” is not a proposition. How to make it to be a proposition? Cách 1: gán 1 giá trị cho biến x (Ex: 0 > 1). Cách 2: biến đổi câu trên thành hoặc Nhận xét: liên quan đến “số lượng” Chương 1: Logic 46 Có một số tự nhiên x sao cho x > 1 Với mọi số tự nhiên x thì x > 1 Toán rời rạc Lượng từ (quantifier) Để biến vị từ thành mệnh đề “Sự lượng hóa” : for-all (với mọi) ∀xP(x) = “P(x) is T for all x” “với mọi x, P(x)” : exists (tồn tại) ∃xP(x) = “There exists x such that P(x) is T” “tồn tại x sao cho P(x)” Các khái niệm “few, many,” có thể được diễn đạt với , . Chương 1: Logic 47 Toán rời rạc Miền giá trị của biến Trong phát biểu toán học: Một tính chất có thể đúng với mọi giá trị của biến trong một miền đặc biệt nào đó (Miền xác định – Toán phổ thông). Domain (universe) of discourse: hoặc Chương 1: Logic 48 Miền không gian Vũ trụ biện luận Toán rời rạc Ví dụ - Lượng từ  Chương 1: Logic 49 Ví dụ 1: “All IT students must study discrete maths” P(x) = “x must study discrete maths” Proposition: xP(x) Lưu ý: x ngụ ý là một sinh viên IT (domain). Ví dụ 1: Diễn giải một cách cụ thể hơn  S(x) = “x is an IT student”  P(x) = “x must study discrete maths”  Proposition: x(S(x)  P(x)) Toán rời rạc Ví dụ - Lượng từ  Chương 1: Logic 50 Ví dụ 1: Diễn giải một cách cụ thể hơn  S(x) = “x is an IT student”  P(x) = “x must study discrete maths”  Proposition: x(S(x)  P(x)) Today’s Big question: Why not x(S(x)  P(x))? Toán rời rạc Ví dụ - Lượng từ  Chương 1: Logic 51 Ví dụ 2: P(x) = “x > 3” Domain: x    Proposition:  xP(x)  TRUE or FALSE? Ví dụ 3: Q(x) = “x=x+ 1” Domain: x    Proposition: ∃xQ(x)  TRUE or FALSE? Toán rời rạc Làm sao để xác định chân trị?  ∀xP(x) =P(x1) ∧ P(x2) ∧ . . . ∧ P(xn)  ∃xP(x) =P(x1) ∨ P(x2) ∨ . . . ∨ P(xn) Trong đó x1, x2 xn là mọi giá trị có thể có của x. Kiểm tra mọi xi đối với  để xác định TRUE. Tìm một giá trị xi đối với  để xác định TRUE. Chương 1: Logic 52 Toán rời rạc Thứ tự ưu tiên của lượng từ Thứ tự giữa các ký hiệu lượng từ là quan trọng. Trừ các trường hợp sau:  Mọi ký hiệu lượng từ là “for-all”.  Mọi ký hiệu lượng từ là “exists”. Thứ tự:  từ trái sang phải,  từ trong ra ngoài Chương 1: Logic 53 Toán rời rạc Thứ tự ưu tiên của lượng từ Chương 1: Logic 54 Ví dụ 1: ∀x∀y (x + y = y + x) ∀y∀x (x + y = y + x) TRUE for all x, y ∈  Ví dụ 2: ∀x∃y (x + y = 0) is T, when ∃y∀x (x + y = 0) is F Toán rời rạc Dịch sang ngôn ngữ tự nhiên Translate the following proposition: ∀x(C(x)∨ ∃y(C(y)∧F(x, y)))) In which: •C(x): “x có máy tính” •F(x, y): “x, y là bạn” •x, y ∈ all students in the university  Chương 1: Logic 55 Với mọi sinh viên x trong trường, hoặc x có máy tính, hoặc tồn tại sinh viên y có máy tính và sinh viên x, y là bạn. Toán rời rạc Dịch sang ngôn ngữ tự nhiên Ví dụ 1: xét mệnh đề sau ∀x(C(x)∨ ∃y(C(y)∧F(x, y)))) Trong đó: •C(x): “x có máy tính” •F(x, y): “x, y là bạn” •x, y ∈ all students in the university  Chương 1: Logic 56 Với mọi sinh viên x trong trường, hoặc x có máy tính, hoặc tồn tại sinh viên y có máy tính và sinh viên x, y là bạn. Toán rời rạc Dịch sang ngôn ngữ tự nhiên Ví dụ 2: xét mệnh đề sau ∃x∀y∀z(((F(x, y)∧F(x, z)∧(yz)) → ¬F(y, z))) Trong đó: •F(x, y): “x, y là bạn” •x, y ∈ all students in the university  Chương 1: Logic 57 There exists a student x, such that for all student y, for all student z different from y, if x is friend of y and x is friend of z then y, z are not friend to each other. (Có một sinh viên có 2 người bạn mà 2 người đó không biết nhau) Toán rời rạc Công thức hóa ngôn ngữ tự nhiên (1) “There are some students in our class who have visited Hanoi.” (2) “All students in our class have visited Nha Trang or Vung Tau.”  Chương 1: Logic 58 If we have following predicates: C(x): “x has visited Hà Nội” D(x): “x has visited Nha Trang” E(x): “x has visited Vũng Tàu” Then: (1): ∃xC(x) (2): ∀x(D(x)∨E(x)) Toán rời rạc Công thức hóa ngôn ngữ tự nhiên “All people have at least one best friend.” (“Mọi người đều có ít nhất một người bạn tốt nhất.”)  Chương 1: Logic 59 If we have following predicates: B(x, y): “y is best friend of x” Then: ∀x∃y∀z(B(x, y)∧((yz)→ ¬B(x, z))) Toán rời rạc Công thức hóa ngôn ngữ tự nhiên “If one is woman and parental, then she is the mother of some one.” (“Nếu một người là phụ nữ và là cha mẹ, thì người đó là mẹ của một người nào đó.”)  Chương 1: Logic 60 If we have following predicates: C(x): “x là phụ nữ” D(x): “x là cha mẹ” E(x, y): “x là mẹ của y” Then: ∀x((C(x)∧D(x)) → ∃yE(x, y)) Toán rời rạc Tóm tắt Chương 1: Logic 61 Toán rời rạc Phủ định của lượng từ “Tất cả sinh viên IT phải học Toán Rời Rạc” ∀x P(x) Phủ định (negation) của câu trên: “Không phải tất cả SV IT phải học TRR” ∃x ¬P(x) Chương 1: Logic 62 Phủ định Tương đương với ¬ (∃xP(x)) ¬ (∀xP(x)) ∀x ¬P(x) ∃x ¬P(x) Toán rời rạc Đọc thêm textbook Sự tương đương của các vị từ được lượng hóa: page 39-41. Chương 1: Logic 63 Toán rời rạc Bài tập Biểu diễn các câu sau ở dạng vị từ: a) “Tất cả sư tử đều hung dữ.” b) “Một số sư tử không uống cà phê.” c) “Có một phụ nữ đã bay tất cả các tuyến bay trên thế giới.” (Mỗi tuyến bay có nhiều chuyến bay) Chương 1: Logic 64 Toán rời rạc Bài tập Cho các mệnh đề sau: R(x) = “x là một con lợn” H(x) = “x thik uống bia Ken” Trong đó x xét trên tập tất cả các con vật. Dịch sang ngôn ngữ tự nhiên các mệnh đề sau: 1. ∀x (R(x)  H(x)) 2. ∀x (R(x) ∧ H(x)) 3. ∃x (R(x)  H(x)) 4. ∃x (R(x) ∧ H(x)) Chương 1: Logic 65