Toán rời rạc - Bài 1 - Logic

Tham khảo tài liệu 'toán rời rạc - bài 1 - logic', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Toán rời rạc - Bài 1 - Logic Module #1 - Logic University of Florida Dept. of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr. Michael P. Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) (5 by Kenneth H. Rosen 10/21/11 (c)2001-2004, Michael P. Frank 1 Module #1 - Logic Bài #1: Cơ sở Logic Rosen 5th ed., §§1.1-1.4 ~81 slides, ~4 lectures 10/21/11 (c)2001-2004, Michael P. Frank 2 Module #1 - Logic 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. 10/21/11 (c)2001-2004, Michael P. Frank 3 Module #1 - Logic 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. 10/21/11 (c)2001-2004, Michael P. Frank 4 Module #1 - Logic Topic #1 – Propositional Logic 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: George Boole (1815-1864) • 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. Chrysippus of Soli (ca. 281 B.C. – 205 B.C.) 10/21/11 (c)2001-2004, Michael P. Frank 5 Module #1 - Logic Topic #1 – Propositional Logic Đị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!) 10/21/11 (c)2001-2004, Michael P. Frank 6 Module #1 - Logic 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) .” (T • “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) Ai đó?” (c • “La la la la la.” (không có ý nghĩa) La (kh • “Hãy làm đi!” (mệnh lệnh) !” (m • “Vâng, có lẽ tôi sẽ...” (mơ hồ) ...” (m • “1 + 2” (biểu thức không có giá trị đúng/sai ) 2” (bi 10/21/11 (c)2001-2004, Michael P. Frank 7 Module #1 - Logic Topic #1.0 – Propositional Logic: Operators Phép toán / Kết nối • 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); 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 ác mệnh đề (hoặc với giá trị chân lý của chúng) thay vì trên các số. 10/21/11 (c)2001-2004, Michael P. Frank 8 Module #1 - Logic Topic #1.0 – Propositional Logic: Operators Một số phép toán Bool thông dụng Tên chính thức Viết tắt Ký hiệu Ngôi Phép phủ định NOT Unary ¬ ∧ Phép hội AND Binary ∨ Phép tuyển OR Binary ⊕ Phép tuyển loại trừ XOR Binary → Phép kéo theo IMPLIES Binary Phép điều kiện hai IFF Binary ↔ chiều 10/21/11 (c)2001-2004, Michael P. Frank 9 Module #1 - Logic 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.” th p ¬p Bảng chân lý của NOT: TF T :≡ True; F :≡ False FT “:≡” nghĩa là “được định nghĩa là” Operand Result column column 10/21/11 (c)2001-2004, Michael P. Frank 1 ...