Bài giảng Toán rời rạc: Cơ sở Logic

University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete Mathematics & Its Applications (5th Edition)by Kenneth H. Rosen Bài #1:Cơ sở Logic Rosen 5th ed., §§1.1-1.4 ~81 slides, ~4 lectures Module #1: Foundations of Logic(§§1.1-1.3, ~3 lectures) Logic toán là công cụ để làm việc với các lệnh phức hợp. Nó bao gồm: Ngôn ngữ hình thức biểu diễn chúng. Ký hiệu chính xác để viết chúng. Phương pháp luận để suy luận về tính đúng đắn. Là cơ sở biểu diễn chứng minh hình thức như mọi nhánh toán học khác. Cơ sở Logic: Tổng quan Logic mệnh đề (§1.1-1.2): Các định nghĩa cơ sở. (§1.1) Luật suy diễn và qui tắc tương đương. (§1.2) Logic tân từ (§1.3-1.4) Tân từ. Biểu diễn tân từ lượng tử. Suy diễn và tương đương. Logic mệnh đề (§1.1) Logic mệnh đề là logic về các khẳng định phức tạp được xây dựng từ các mệnh đề đơn giản sử dụng các kết nối Bool. Một số ứng dụng trong khoa học máy tính: Thiết kế các mạch điện tử số. Biểu diễn các điều kiện trong chương trình. Cơ chế tìm kiếm và truy vấn cơ sở dữ liệu. Topic #1 – Propositional Logic George Boole(1815-1864) Chrysippus of Soli(ca. 281 B.C. – 205 B.C.) Định nghĩa Mệnh đề Định nghĩa: Mệnh đề (ký hiệu p, q, r, …) đơn giản là: Một khẳng định (tức là, một câu tuyên bố) Với một ngữ nghĩa xác định (không nhập nhằng) Có giá trị chân lý là đúng true (T) hoặc sai false (F) Không khi nào hoặc cả hai hoặc nửa chừng!” Tuy nhiên bạn có thể chưa biết giá trị chân lý của nó, Và giá trị chân lý có thể phụ thuộc vào tình huống của ngữ cảnh. Sau này ta học xác suất, ở đó có thể có mức độ đúng sai của mệnh đề (“giữa” T và F). Nhưng bây giờ: chỉ nghĩ về đúng hoặc sai (True/False only!) Topic #1 – Propositional Logic Các ví dụ về mệnh đề “Trời đang mưa.” (Tại tình huống cho trước) “Hà nội là thủ đô của Việt nam” • “1 + 2 = 4” Nhưng đây KHÔNG là mệnh đề: “Ai đó?” (câu hỏi) “La la la la la.” (không có ý nghĩa) “Hãy làm đi!” (mệnh lệnh) “Vâng, có lẽ tôi sẽ...” (mơ hồ) “1 + 2” (biểu thức không có giá trị đúng/sai ) Topic #1 – Propositional Logic Phép toán và kết nối liên kết một hoặc nhiều biểu thức toán hạng thành các biểu thức lớn hơn. (như, “+” trong biểu thức số) Phép toán một ngôi dùng một toán hạng (như −3); Phép toán hai ngôi dùng hai toán hạng (như 34). Toán tử mệnh đề hoặc Bool thao tác trên các mệnh đề (hoặc với giá trị chân lý của chúng) thay vì trên các số. Phép toán / Kết nối Topic #1.0 – Propositional Logic: Operators Một số phép toán Bool thông dụng Topic #1.0 – Propositional Logic: Operators Phép Phủ định (negation) Phép phủ định một ngôi “¬” (NOT) chuyển mệnh đề thành phủ định logic của nó. Ví dụ. Nếu p = “Tôi có tóc đen.” thì ¬p = “Tôi không có tóc đen.” Bảng chân lý của NOT: T :≡ True; F :≡ False “:≡” nghĩa là “được định nghĩa là” Operandcolumn Resultcolumn Topic #1.0 – Propositional Logic: Operators Phép Hội (conjunction) Phép hội hai ngôi “” (AND) kết nối hai mệnh đề thành giao hội chung logic của chúng. Ví dụ. Nếu p=“Tôi có nộm rau cho bữa trưa.” và q=“Tôi có món bít tết cho bữa tối.”, thì pq=“Tôi có nộm rau cho bữa trưa và bít tết cho bữa tối.” Remember: “” points up like an “A”, and it means “ND” ND Topic #1.0 – Propositional Logic: Operators Lưu ý hội có tính kết hợp và hội p1  p2  …  pncủa n mệnh đề có 2n hàng trong bảng chân lý. Cũng như: phép ¬ và  cùng nhau đủ để biểu diễn mọi bảng chân lý bất kỳ! Bảng chân lý của phép Hội Operand columns Topic #1.0 – Propositional Logic: Operators Phép Tuyển (disjunction - tách) Phép tuyển hai ngôi “” (OR) kết hợp hai mệnh đề thành sự lựa chọn logic của chúng. p=“Ôtô của tôi có máy không tốt.” q=“Ôtô của tôi có bộ chế hoà khí không tốt.” pq=“Hoặc ôtô của tôi có máy không tốt, hoặc ôtô của tôi có bộ chế hoà khí không tốt.” After the downward-pointing “axe” of “”splits the wood, youcan take 1 piece OR the other, or both. Topic #1.0 – Propositional Logic: Operators Meaning is like “and/or” in English. Nhận xét rằng pq có nghĩa là p đúng, hoặc q đúng, hoặc cả hai đều đúng! Phép tuyển còn được gọi làtuyển bao trùm, vì nó bao gồm cả khả năng cả hai p và q đều đúng. “¬” và “” cùng nhau cũng là đầy đủ. Bảng chân lý phép Tuyển Notedifferencefrom AND Topic #1.0 – Propositional Logic: Operators Biểu thức mệnh đề lồng Sử dụng ngoặc để nhóm các biểu thức con:“Tôi đã nhìn thấy bạn cũ của mình, và hoặc anh ta đã lớn hoặc tôi đã e ngại gặp” = f  (g  s) (f  g)  s có ý nghĩa khác f  g  s có thể còn mơ hồ Qui ước, “¬” có độ ưu tiên hơn cả hai “” và “”. ¬s  f means (¬s)  f , not ¬ (s  f) “” có độ ưu tiên cao hơn “”. f  g  s có nghĩa là (f  g)  s, not f  (g  s) Topic #1.0 – Propositional Logic: Operators Bài tập đơn giản G/s p=“Tối hôm qua trời mưa”, q=“Các xe phun nước đã tưới tối qua,” r=“Bãi cỏ vẫn còn ướt sáng nay.” Hãy dùng lời mô tả các mệnh đề sau: ¬p = r  ¬p = ¬ r  p  q = “It didn’t rain last night.” “The lawn was wet this morning, andit didn’t rain last night.” “Either the lawn wasn’t wet this morning, or it rained last night, or the sprinklers came on last night.” Topic #1.0 – Propositional Logic: Operators Phép tuyển loại trừ Phép hai ngôi tuyển loại trừ “” (XOR) kết hợp hai mệnh đề tạo thành lựa chọn loại trừ của chúng. p = “Tôi sẽ đạt điểm 10 môn này,” q = “Tôi sẽ bỏ môn này,” p  q = “Tôi sẽ hoặc đạt điểm 10 môn này hoặc bỏ nó (nhưng không thể cả hai)” Topic #1.0 – Propositional Logic: Operators Nhận thấy pq có nghĩa là p đúng, hoặc q đúng,nhưng không cả hai! Phép toán này được gọi là tuyển loại trừ, vìnó loại trừ khả năng cả hai p và q đều đúng. “¬” và “” cùng nhau không là đầy đủ. Bảng chân lý của tuyển loại trừ Notedifferencefrom OR. Topic #1.0 – Propositional Logic: Operators Note that English “or” can be ambiguous regarding the “both” case! “Pat is a singer orPat is a writer.” - “Pat is a man orPat is a woman.” - Need context to disambiguate the meaning! For this class, assume “or” means inclusive. Ngôn ngữ tự nhiên không rõ ràng   Topic #1.0 – Propositional Logic: Operators Phép Kéo theo (Implication) Phép kéo theo p  q khẳng định rằng p kéo theo q. Tức là, nếu p đúng, thì q đúng; nhưng nếu p không đúng, thì q có thể đúng hoặc sai. Ví dụ, G/s p = “Bạn học cần cù.” q = “Bạn sẽ nhận được điểm tốt.” p  q = “Nếu bạn học cần cù, thì bạn sẽ nhận được điểm tốt.” (ngược lại, không biết điều gì sẽ xảy ra) Topic #1.0 – Propositional Logic: Operators antecedent consequent Bảng chân lý phép kéo theo p  q là sai chỉ khi p đúng nhưng q không đúng. p  q không nói rằngp gây ra q! p  q không đòi hỏi rằngp hoặc q cần phải là đúng! VD. “(1=0)  pigs can fly” is TRUE! The onlyFalsecase! Topic #1.0 – Propositional Logic: Operators Các ví dụ phép kéo theo “If this lecture ever ends, then the sun will rise tomorrow.” True or False? “If Tuesday is a day of the week, then I am a penguin” True or False? (chim cánh cụt). “If 1+1=6, then Bush is president.” True or False? “If the moon is made of green cheese, then I am richer than Bill Gates.” True or False? Topic #1.0 – Propositional Logic: Operators Tại sao trông có vẻ sai? Xét câu kiểu như sau, “Nếu tôi mặc áo phông đỏ ngày mai, thì Osama bin Laden se bị bắt!” Trong logic, chúng ta coi câu trên còn là đúng khi tôi không mặc áo đỏ, hoặc Osama bị bắt. Nhưng, trong đối thoại thông thường, nếu tôi tuyên bố như vậy, bạn có thể nghĩ là tôi nói dối. Tại sao có sự không nhất quán giữa logic & ngôn ngữ? Giải quyết sự không nhất quán Nói chung câu “nếu p thì q” thường được hiểu ẩn dụ như là, “Trong mọi tình huống, nếu p thì q.” Như là, “Để p đúng và q sai là điều không thể có.” Hoặc, “Tôi đảm bảo rằng không có gì thay đổi, nếu p, thì q.” Điều đó có thể biểu diễn trong logic tân từ như sau: “Trong mọi tình huống s, nếu p là đúng trong tình huống s, thì q cũng đúng trong tình huống s” Một cách hình thức, ta có thể viết: s, P(s) → Q(s) Như vậy câu nói trong ví dụ của chúng ta là sai về mặt logic, vì tôi mặc áo đỏ và Osama vẫn không bị bắt là tình huống có thể có. Ngôn ngữ tự nhiên và logic khi đó thống nhất với nhau. English Phrases Meaning p  q “p implies q” “if p, then q” “if p, q” “when p, q” “whenever p, q” “q if p” “q when p” “q whenever p” “p only if q” “p is sufficient for q” “q is necessary for p” “q follows from p” “q is implied by p” We will see some equivalent logic expressions later. Topic #1.0 – Propositional Logic: Operators Converse, Inverse, Contrapositive Some terminology, for an implication p  q: Its converse is: q  p. Its inverse is: ¬p  ¬q. Its contrapositive: ¬q  ¬ p. Có một câu trong 3 câu trên cùng nghĩa (cùng bảng chân lý) với p  q. Bạn cho biết câu nào? Topic #1.0 – Propositional Logic: Operators Tại sao chúng ta lại biết chắc như vậy? Chứng minh sự tương đương giữa p  q và mệnh đề phản đảo của nó sử dụng bảng chân lý: Topic #1.0 – Propositional Logic: Operators Phép toán điều kiện hai phía Điều kiện hai phía p  q khẳng định rằng p là đúng khi và chỉ khi (IFF) q là đúng. p = “Bush wins the 2004 election.” q = “Bush will be president for all of 2005.” p  q = “If, and only if, Bush wins the 2004 election, Bush will be president for all of 2005.” Topic #1.0 – Propositional Logic: Operators 2004 I’m stillhere! 2005 Biconditional Truth Table p  q có nghĩa là p và qcó cùng giá trị chân lý. Nhận thấy bảng chân lý này hoàn toàn ngược lại với của ! Vậy, p  q nghĩa là ¬(p  q) p  q không suy ra rằng p và q là đúng. Topic #1.0 – Propositional Logic: Operators Tổng kết các phép toán Bool Ta đã nhìn thấy 1 phép toán 1 ngôi (trong số 4 cái có thể) và 5 phép toán 2 ngôi (trong số 16 cái có thể). Bảng chân lý của chúng như sau. Topic #1.0 – Propositional Logic: Operators Một số ký hiệu khác tương đương Topic #1.0 – Propositional Logic: Operators Bits và các phép toán trên Bit A bit is a binary (base 2) digit: 0 or 1. Bits có thể dùng để biểu diễn giá trị chân lý. Qui ước:  0 biểu diễn “false”; 1 biểu diễn “true”. Đại số Bool giống đại số thường ngoại trừ biến dùng thay bit, + là tuyển “or”, và nhân là hội “and”. See module 23 (chapter 10) for more details. Topic #2 – Bits John Tukey(1915-2000) Xâu Bit Xâu Bit có độ dài n là dãy có thứ tự (series, tuple) của n0 bits. More on sequences in §3.2. Qui ước, các xâu bit strings được viết từ trái qua phải: Tức là. bit “đầu tiên” của xâu bit “1001101010” là 1. Hãy quan sát! Cách qui ước khác, bit đầu là bit phải nhất bit #0, bit thứ hai là bit phải thứ hai bit #1, cứ như vậy Khi xâu bit biểu diễn số cơ số 2, theo qui ước, bit đầu (trái nhất) là bit có ý nghĩa nhất. Tức là: 11012=8+4+1=13. Topic #2 – Bits Đếm trong cơ số nhị phân Bạn có biết đếm đến 1,023 mà sử dụng hai bàn tay không? Như thế nào? Đếm trong nhị phân! Mỗi ngón tay (trên xuống) biểu diễn 1 bit. Khi đếm: tăng bit phải nhất (bậc nhỏ low-order). Nếu thay đối 1→0, thì tăng bit tiếp theo bên trái, Nếu bit đó thay đổi 1→0, thì tăng bit tiếp theo, v.v. 0000000000, 0000000001, 0000000010, ……, 1111111101, 1111111110, 1111111111 Topic #2 – Bits Các phép toán trên Bit Các phép toán Bool có thể được mở rộng cho các xâu bit như cho từng bit. VD.:01 1011 011011 0001 110111 1011 1111 Bit-wise OR01 0001 0100 Bit-wise AND10 1010 1011 Bit-wise XOR Topic #2 – Bits Kết thúc §1.1 Bạn đã học về: Mệnh đề là gì. Các phép toán của logic mệnh đề Định nghĩa Ký hiệu Tương đương trong tiếng Anh. Nghĩa Logic. Bảng chân lý. Mệnh đề nguyên thuỷ và mệnh đề phức hợp. Các ký hiệu khác nhau. Bits và xâu bit. Bài sau: §1.2 Tương đương mệnh đề. Chứng minh như thế nào. Các mệnh đề tương đương (§1.2) Hai mệnh đề phức tạp khác nhau về cú pháp có thể đồng nhất về ngữ nghĩa (tức là có cùng ý nghĩa). Ta gọi chúng là tương đương. Ta sẽ học: Các qui tắc và luật tương đương khác nhau. Cách chứng minh tương đương sử dụng các suy diễn hình thức. Topic #1.1 – Propositional Logic: Equivalences Hằng đúng (HĐ) và hằng sai(HS) Hằng đúng là mệnh đề phức mà luôn là đúng không phụ thuộc vào giá trị chân lý của các mệnh đề nguyên tố thành phần! VD. p  p [Bảng chân lý của nó như thế nào?] Hằng sai là mệnh đề phức mà luôn là sai mà không phụ thuộc giá trị chân lý của các mệnh đề nguyên tố thành phần! VD. p  p [Bảng chân lý?] Các mệnh đề phức khác là ngẫu nhiên. Topic #1.1 – Propositional Logic: Equivalences Tương đương Logic Mệnh đề phức p là tương đương logic với mệnh đề phức q, viết dạng pq, khi và chỉ khi (IFF) mệnh đề phức pq là hằng đúng. Các mệnh đề phức p và q là tương đương logic với nhau khi và chỉ khi (IFF) p và q chứa các giá trị chân lý như nhau trên mọi hàng của bảng chân lý của chúng. Topic #1.1 – Propositional Logic: Equivalences Thỏa được và kiểm tra tính HĐ, HS Mệnh đề thỏa được (tiếp liên) là mệnh đề phức mà tồn tại bộ giá trị chân lý của các mệnh đề nguyên tố thành phần làm cho nó đúng. VD: (p→q)→ p Một số phương pháp kiểm tra tính HĐ, HS, và thỏa được. Ex. Prove that pq  (p  q). Chứng minh tương đương qua bảng chân lý F T T T T T T T T T F F F F F F F F T T Topic #1.1 – Propositional Logic: Equivalences Các luật tương đương Chúng tương tự các luật số học mà chúng ta học trong đại số, nhưng ở đây dùng cho sự tương đương mệnh đều. Chúng cung cấp mẫu hoặc khuôn để sánh tất cả hoặc một phần của các mệnh đề phức tạp hơn và tìm ra sự tương đương cho nó. Topic #1.1 – Propositional Logic: Equivalences Equivalence Laws - Examples Đồng nhất: pT  p pF  p Trội : pT  T pF  F Luỹ đẳng : pp  p pp  p Phủ định kép: p  p Giao hoán : pq  qp pq  qp Kết hợp : (pq)r  p(qr) (pq)r  p(qr) Topic #1.1 – Propositional Logic: Equivalences More Equivalence Laws Phân phối: p(qr)  (pq)(pr) p(qr)  (pq)(pr) De Morgan’s: (pq)  p  q (pq)  p  q Hằng đúng/hằng sai hiển nhiên: p  p  T p  p  F Topic #1.1 – Propositional Logic: Equivalences AugustusDe Morgan(1806-1871) Định nghĩa thông qua tương đương Sử dụng tương đương, chúng ta định nghĩa các phép toán thông các phép toán khác. Phép loại trừ: pq  (pq)(pq) pq  (pq)(qp) Kéo theo: pq  p  q Điều kiện hai chiều: pq  (pq)  (qp) pq  (pq) Topic #1.1 – Propositional Logic: Equivalences Bài tập ví dụ Kiểm tra sử dụng suy diễn hình thức (p  q)  (p  r)  p  q  r. (p  q)  (p  r) [Dùng ĐN của ]  (p  q)  (p  r) [Dùng ĐN của ]  (p  q)  ((p  r)  (p  r)) [DeMorgan’s Law]  (p  q)  ((p  r)  (p  r)) cont. Topic #1.1 – Propositional Logic: Equivalences Tiếp tục ... (p  q)  ((p  r)  (p  r))  [ giao hoán]  (q  p)  ((p  r)  (p  r)) [ kết hợp]  q  (p  ((p  r)  (p  r))) [phân phối  trên ]  q  (((p  (p  r))  (p  (p  r))) [Kết hợp.]  q  (((p  p)  r)  (p  (p  r))) [Hằng đúng.]  q  ((T  r)  (p  (p  r))) [Trội]  q  (T  (p  (p  r))) [Đồng nhất]  q  (p  (p  r))  cont. Topic #1.1 – Propositional Logic: Equivalences Kết thúc ví dụ q  (p  (p  r)) [DeMorgan’s]  q  (p  (p  r)) [Kết hợp]  q  ((p  p)  r) [Đồng nhất]  q  (p  r) [Kết hợp]  (q  p)  r [Giao hoán]  p  q  r Q.E.D. (quod erat demonstrandum) – Điều cần phải chứng minh Topic #1.1 – Propositional Logic: Equivalences Dạng chuẩn tắc tuyển và dạng chuẩn tắc hội Dạng chuẩn tắc tuyển (CTT): Hội sơ cấp: là hội của các mệnh đề nguyên tố và các phủ định của chúng. vd: pqr Dạng CTT : tuyển của các hội sơ cấp. Dạng chuẩn tắc hội (CTH): Tuyển sơ cấp:tuyển của các mệnh đề nguyên tố và các phủ định của chúng. vd: p  q  r Dạng CTH : hội của các tuyển sơ cấp. Ôn lại: Logic mệnh đề(§§1.1-1.2) Mệnh đề nguyên tố: p, q, r, … Các phép toán Bool:       Các mệnh đề phức: s : (p  q)  r Tương đương: pq  (p  q) Chứng minh tương đương dùng: Bảng chân lý. Suy diễn hình thức. p  q  r … Topic #1 – Propositional Logic Logic vị từ - Predicate Logic (§1.3) Logic vị từ là mở rộng logic mệnh đề mà cho phép suy luận chính xác về cả lớp các thực thể. Logic mệnh đề coi các mệnh đề đơn giản (câu) như các thực thể nguyên tố (atomic entities) Ngược lại, logic vị từ phân biệt chủ ngữ (subject) của câu khỏi vị ngữ (predicate) của nó. Topic #3 – Predicate Logic Các ứng dụng của Logic vị từ Đó là ký hiệu hình thức để viết hoàn toàn rõ ràng, chính xác các định nghĩa, tiên đề, định lý toán học không nhập nhăng cho mọi nhánh của toán học (sẽ học nhiều hơn trong bài 2). Logic vị từ với ký hiệu hàm, phép toán “=”, và một số qui tắc xây dựng chứng minh là đủ để định nghĩa các hệ toán học hiện thực và để chứng minh bất cứ điều gì mà có thể chứng minh trong hệ đó! Topic #3 – Predicate Logic Các ứng dụng khác Logic vị từ là cơ sở của ngành toán học logic mà đạt đỉnh điểm trong định lý không hoàn chỉnh Gödel, mà được tin là giới hạn đỉnh điểm của suy nghĩ toán học: Với mọi thủ tục chứng minh thích hợp, mô tả, hữu hạn được, ở đây luôn còn có những khẳng định đúng đắn nào đó mà không bao giờ được chứng minh bởi thủ tục đó. Tức là, chúng ta không thể khám phá được tất cả các chân lý toán học, trừ khi chúng ta có phương sách để đoán chúng. Topic #3 – Predicate Logic Kurt Gödel1906-1978 Áp dụng thực tiễn của Logic vị từ Đây là cơ sở để biểu diễn một cách rõ ràng các đặc tả hình thức cho các hệ phức tạp bất kỳ. Đây là cơ sở cho việc chứng minh định lý tự động và nhiều hệ thống trí tuệ nhân tạo khác. VD. Hệ thống kiểm chứng chương trình tự động (automatic program verification systems). Logic vị từ giống như các khẳng định được hỗ trợ bởi các cơ chế truy vấn cơ sở dữ liệu tốt và các thư viện chứa lớp. Có nhiều kiểu của công cụ lập trình. Topic #3 – Predicate Logic Chủ ngữ và vị ngữ Subjects and Predicates Trong câu “Con chó đang ngủ”: Cụm “Con chó” là chủ ngữ - là đối tượng hay chủ thể mà câu đang muốn nói về nó. Cụm “đang ngủ” là vị ngữ - nêu tính chất mà đúng đối với chủ ngữ. Trong Logic vị từ, vị ngữ được mô hình là hàm P(·) từ đối tượng vào mệnh đề. P(x) = “x đang ngủ” (trong đó x là đối tượng bất kỳ). Topic #3 – Predicate Logic More About Predicates Qui ước: Các biến chữ thường x, y, z... Ký hiệu các đối tượng/thực thể; Các biến chữ hoa P, Q, R… ký hiệu các hàm mệnh đề (vị ngữ). Nhớ rằng kết quả việc áp dụng vị ngữ (predicate) P cho đối tượng c là mệnh đề P(c). Nhưng bản thân vị ngữ P (VD. P=“đang ngủ”) không là mệnh đề (câu không hoàn chỉnh). VD. Nếu P(x) = “x là số nguyên tố”, P(3) là mệnh đề “3 là số nguyên tố.” Topic #3 – Predicate Logic Các hàm mệnh đề Propositional Functions Logic vị từ khái quát hoá các định nghĩa ngữ pháp của vị ngữ thành các hàm có một số đối số tuỳ ý, mỗi một biến đóng vai trò ngữ pháp mà danh từ có thể có. VD. G/s P(x,y,z) = “x cho y điểm z”, thì nếu x=“Mike”, y=“Mary”, z=“A”, thì P(x,y,z) = “Mike cho Mary điểm A.” Topic #3 – Predicate Logic Vũ trụ khẳng định Universes of Discourse (U.D.s) Lực lượng các đối tượng khác nhau từ vị ngữ là cái giành cho bạn khẳng định đồng thời cho rất nhiều đối tượng. VD, G/s P(x)=“x+1> x”. Chúng ta có thể nói,“Với mọi số x, P(x) là đúng” thay vì phải viết(0+1>0)  (1+1>1)  (2+1>2)  ... Họ các giá trị mà biến x lấy được gọi là vũ trụ khẳng định của x Topic #3 – Predicate Logic Biểu thức lượng tử Lượng tử là các ký hiệu để ta ước lượng có bao nhiêu đối tượng trong vũ trụ khẳng định thoả mãn vị ngữ đã cho. . “” là với mọi (FORLL) hoặc lượng tử với mọi.x P(x) nghĩa là với mọi x trong u.d., P thoả mãn. “” là tồn tại (XISTS) hay lượng tử tồn tại.x P(x) nghĩa là tồn tại x trong u.d. (có một hoặc nhiều hơn sao cho P(x) là đúng. Topic #3 – Predicate Logic Lượng tử với mọi  Ví dụ: G/s Vũ trụ khẳng định (u.d.) của x là các chỗ đỗ xe trong trường GT.G/s P(x) là vị ngữ “x đã đầy.”Khi đó lượng tử với mọi của P(x), x P(x), là mệnh đề: “Mọi chỗ đỗ xe trong GT đã đầy.” Tức là, “Chỗ đỗ xe bất kỳ trong GT đã đầy.” Hay , “Với mỗi chỗ đỗ xe trong GT, chỗ đó đã đầyl.” Topic #3 – Predicate Logic Lượng tử tồn tạiThe Existential Quantifier  Ví dụ: G/s vũ trụ khẳng định (u.d.) của x là các chỗ đỗ oto trong trường GT.G/s P(x) là vị ngữ “x là đầy.”Khi đó lượng tử tồn tại của P(x), x P(x), là mệnh đề: “Tồn tại một chỗ đỗ nào đó trong GT là đầy.” “Có một chỗ đỗ oto nào đó trong GT mà nó đầy.” “Có ít nhất một chỗ đỗ trong GT là đầy.” Topic #3 – Predicate Logic Biến bị trói buộc và tự do Biểu thức như P(x) được gọi là có biến tự do x (theo nghĩa, x không xác định). Lượng tử (hoặc  hoặc ) tác động lên biểu thức có một hay nhiều biến tự do, và trói buộc một hay nhiều biến khác, tạo thành biểu thức có một hay nhiều biến trói buộc. Topic #3 – Predicate Logic Ví du về trói buộc P(x,y) có hai biến tự do, x và y. x P(x,y) có 1 biến tự do, và 1 biến trói buộc. [Biến nào là gì?] “P(x), trong đó x=3” là một cách trói buộc x. Biểu thức với không biến tự do làmệnh đề thực sự. Biểu thức với một hay nhiều hơn biến tự do vẫn còn là vị ngữ (predicate): VD G/s Q(y) = x P(x,y) Topic #3 – Predicate Logic Lồng lượng tử với nhau VD:G/s vũ trụ (u.d.) của x & y là mọi người. G/s L(x,y)=“x thích y” (vị ngữ với 2 b tự do) Khi đó y L(x,y) = “Có ai đó mà x thích” (Vị ngữ với 1 biến tự do x) Và x (y L(x,y)) = “Mỗi người đều thích ai đó.”(Vị ngữ có mấy biến tự do?) Topic #3 – Predicate Logic Ôn tập: Predicate Logic (§1.3) Các đối tượng x, y, z, … Vị ngữ P, Q, R, … là các hàm ánh xạ các đối tượng x vào các mệnh đề P(x). Vị ngữ đa đối số P(x, y). Lượng tử: [x P(x)] :≡ “Với mọi x’s, P(x).” [x P(x)] :≡ “Có x sao cho thỏa P(x).” Vũ trụ khẳng định, biến trói buộc và tự do. Bài tập lượng tử Nếu R(x,y)=“x tin cậy vào y,” biểu diễn các điều sau: x(y R(x,y))= y(x R(x,y))= x(y R(x,y))= y(x R(x,y))= x(y R(x,y))= Everyone has someone to rely on. There’s a poor overburdened soul whom everyone relies upon (including himself)! There’s some needy person who relies upon everybody (including himself). Everyone has someone who relies upon them. Everyone relies upon everybody, (including themselves)! Topic #3 – Predicate Logic Ngôn ngữ tự nhiên nhập nhằng Natural language is ambiguous! “Mỗi người thích người nào đó.” Đối với mỗi người, có người nào đó mà họ thích. x y Likes(x,y) Hoặc, có người nào đó (người nổi tiếng) mà mọi người đều thích? y x Likes(x,y) “Người nào đó thích mỗi người.” Vấn đề tương tự: phụ thuộc ngữ cảnh, cách nhấn. [Probably more likely.] Topic #3 – Predicate Logic Ngữ nghĩa lý thuyết của trò chơi Nghĩ theo cách trò chơi đối kháng có thể giúp bạn nói mệnh đề với luợng tử lồng nhau có đúng không. Trò chơi có 2 người, cả hai có kiến thức như nhau: Kiểm chứng - Verifier: muốn chứng tỏ rằng mệnh đề đúng. Phủ quyết: muốn chứng tỏ mệnh đề sai. Các qui tắc chơi “kiểm chứng hay phủ quyết”: Đọc lượng tử từ trái qua phải, chọn giá trị của biến. Khi bạn thấy “”, phủ quyết chọn giá trị. Khi bạn thấy “”, kiểm định chọn giá trị. Nếu kiểm chứng luôn thắng, thì mệnh đề đúng. Nếu phủ quyết luôn thắng thì mệnh đề sai. Topic #3 – Predicate Logic Nào chơi, “Kiểm chứngVerify or Falsify!” G/s B(x,y) :≡ “ngày sinh của x tiếp theo ngày sinh của y trong vòng 7 days.” G/s tôi tuyên bố với các bạn:  x y B(x,y) Lượt của bạn, phủ quyết:  Bạn chọn bất kỳ x → (so-and-so) y B(so-and-so,y) Lượt tôi, như người kiểm chứng:  Tôi chọn bất kỳ y → (such-and-such) B(so-and-so,such-and-such) Hãy chơi trong lớp. Ai thắng trò chơi này? Điều gì xảy ra nếu tôi đảo lượng tử y x B(x,y)? Ai sẽ thắng trong  trường hợp này? Topic #3 – Predicate Logic Nói thêm về qui ước Đôi khi vũ trụ khẳng định được hạn chế ngay trong lượng tử, như x>0 P(x) là viết tắt của“Với mọi x mà lớn hơn không thoả P(x).”=x (x>0  P(x)) x>0 P(x) viết tắt của“Có x lớn hơn không mà thoả P(x).”=x (x>0  P(x)) Topic #3 – Predicate Logic Nói thêm về luật tương đương x y P(x,y)  y x P(x,y)x y P(x,y)  y x P(x,y) x (P(x)  Q(x))  (x P(x))  (x Q(x))x (P(x)  Q(x))  (x P(x))  (x Q(x))  x P(x)  x  P(x)  x P(x)  x  P(x) Bài tập:  Sẽ thấy nếu bạn có thể tự chứng minh. Sự tương đương mệnh đề nào bạn đã sử dụng? Topic #3 – Predicate Logic Thêm qui ước ký hiệu Lượng tử trói buộc lỏng lẻo, cần mở đóng ngoặc: x P(x)  Q(x) Lượng tử liên tiếp cùng kiểu có thể kết hợp: x y z P(x,y,z) x,y,z P(x,y,z) hoặc có thể viết xyz P(x,y,z) Mọi biểu thức lượng tử có thể đưa về dạng chính tắc luôn phiên sau x1x2x3x4… P(x1, x2, x3, x4, …) ( ) Topic #3 – Predicate Logic Định nghĩa lượng tử mới Như tên của nó, lượng tử có thể dùng để biểu diễn rằng vị ngữ là đúng cho đúng số lượng đối tượng cho trước. Định nghĩa !x P(x) có nghĩa “P(x) là đúng với đúng một x trong vũ trụ khẳng định.” !x P(x)  x (P(x)  y (P(y)  y x))“Có x thoả P(x), và không có y cũng thỏa P(y) và y khác x.” Topic #3 – Predicate Logic Một số ví dụ về lý thuyết số G/s vũ trụ u.d. = các số tự nhiên 0, 1, 2, … “Số x là chẵn, E(x), khi và chỉ khi nó bằng hai lần số khác.”x (E(x)  (y x=2y)) “Số x là nguyên tố, P(x), khi và chỉ khi nó lớn hơn 1 và không là tích của hai số khác 1.”x (P(x)  (x>1  yz x=yz  y1  z1)) Topic #3 – Predicate Logic Giả thuyết Goldbach (chưa CM) Sử dụng E(x) và P(x) từ trang trước, E(x>2): P(p),P(q): p+q = x Hoặc, với ký hiệu tường minh hơn: x [x>2  E(x)] → p q P(p)  P(q)  p+q = x. “Mỗi số chẵn