TAILIEUCHUNG - Bài giảng Cấu trúc rời rạc cho Khoa học máy tính: Chapter 2 – ĐH Bách Khoa

Bài giảng Cấu trúc rời rạc cho Khoa học máy tính, chapter 1B - Predicate Logic. Chương này bao gồm các bài tập về Predicate Logic, . | ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA KHOA HỌC - KỸ THUẬT MÁY TÍNH CẤU TRÚC RỜI RẠC CHO KHMT (CO1007) Nhóm:18-TDTT —- Homework CHAPTER 1B Predicate Logic GVHD: SV thực hiện: Nguyễn An Khương Đinh Minh Tân – 1613074 Trương Minh Tiến – 1613544 Vũ Đào Anh Tuấn – 1613938 Nguyễn Thị Trà My – 51305086 Tp. Hồ Chí Minh, Tháng 11/2016 1 Exercise 1 1 arity: Một con số thuộc toán học Ex: Arity in technology variable:biến số Ex:x is a variable argument:đối số, lí lẽ Ex: argument of the vector We agreed without much further argument ! constant:hằng số Ex:h is Plang ’s constant 2 term:số hạng Formula: công thức Ex: Mathemetical formula is difficult to learn by heart expression: biểu thức Ex: This is a simple expression x2 + 2x + 1 = 0 3 free: tự do, độc lập Ex: In free liqid surface, water is under oil bound: giới hạn Ex: compulation bound captured: đạt được Ex: This lim captured =3 2 Exercise 2 1 ∃x(P (x) ∧ Q(x)) 6= ∃xP (x) ∧ ∃xQ(x) We need proof ∃xP (x) ∧ ∃xQ(x) 0 ∃x(P (x) ∧ Q(x)) Let P(x) denotes ”x ≥ 0” and Q(x) denotes ”x < 0” It is easy to see that the left hand is always true and the right hand is false So we have the proof. 2 ∃x(P (x) ∧ Q(x)) → ∃xP (x) ∧ ∃xQ(x) 1. ∃x(P (x) ∧ Q(x)) premise 2. x0 P (x0 ) ∧ Q(x0 ) assumption 3. P (x0 ) ∧e1 2 4. ∃xP (x) ∃x i 3 5. Q(x0 ) ∧e2 2 6. ∃xQ(x) ∃x i 5 7. ∃xP (x) ∧ ∃xQ(x) ∧i4, 6 8. ∃xP (x) ∧ ∃xQ(x) ∃i1, 2 − 7 1 3 a) ∃x(S(x) ∨ R(x)) ≡ ∃xS(x) ∨ ∃xR(x) Proof ∃x(S(x) ∨ R(x)) ` ∃xS(x) ∨ ∃xR(x) 1. ∃x(S(x) ∨ R(x)) 2. x0 S(x0 ) ∨ R(x0 ) assumption 3. S(x0 ) assumption 4. ∃xS(x) ∃x i 3 5. ∃xS(x) ∨ ∃xR(x) ∨i1 4 6. R(x0 ) assumption 7. ∃xR(x) ∃x i 6 8. ∃xS(x) ∨ ∃xR(x) ∨i2 7 9. ∃xS(x) ∨ ∃xR(x) ∨ e 2, 3–5, 6–8 10. ∃xS(x) ∨ ∃xR(x) ∃x e 1, 2–9 premise Proof ∃x(S(x) ∨ R(x)) a ∃xS(x) ∨ ∃xR(x) 1. ∃xS(x) ∨ ∃xR(x) premise 2. ∃xS(x) assumption 3. x0 S(x0 ) assumption 4. S(x0 ) ∨ R(x0 ) ∨i1 3 5. ∃x(S(x) ∨ R(x)) ∃x i .

• Cơ sở dữ liệu
• Cấu trúc rời rạc
• Khoa học máy tính
• Bài giảng Cấu trúc rời rạc
• Phép toán logic
• Cấu trúc dữ liệu
• Predicate logic
• Logic vị từ
• Đề thi học kỳ
• Đề thi Cấu trúc rời rạc
• Bài tập Cấu trúc rời rạc
• Ôn tập Cấu trúc rời rạc
• Đáp án đề thi Cấu trúc rời rạc
• Đáp án đề thi cuối học kỳ II
• Toán rời rạc
• bài giảng Toán rời rạc
• giáo trình Toán rời rạc
• bài tập Toán rời rạc
• đề cương Toán rời rạc
• Toán học rời rạc
• Biểu diễn đồ thị
• Đẳng cấu đồ thị
• Đại cương về đồ thị
• Bài giảng Toán học rời rạc
• Phương pháp đếm dùng hàm sinh
• Hệ số hàm sinh
• Hàm sinh mũ
• Sơ đồ Ven
• Nguyên lý bù trừ
• Kỹ thuật đếm
• Cây khung ngắn nhất
• Cây có gốc
• Phép duyệt cây
• Tìm đường đi ngắn nhất
• Đồ thị Euler
• Đồ thị Hamilton
• Set partitioning
• Đề thi học kì 1
• Đề thi học kì 1 môn Cấu trúc rời rạc
• Đề thi môn Cấu trúc rời rạc
• Chu trình Euler
• Đường đi Hamilton
• Đồ thị phân đôi
• Đối tượng rời rạc
• Biểu diễn quan hệ
• Quan hệ tương đương
• Bài toán đếm
• tài liệu học đại học
• tài liệu toán rời rạc
• toán cao cấp
• học toán rời rạc
• Phép đếm
• Ebook Toán rời rạc
• Nguyên lý cơ bản của phép đếm
• Hệ số nhị thức
• Tổ hợp căn bản
• Tổ hợp lặp
• Khai triển lũy thừa
• Khai triển đa thức
• Propositional logic
• Bài giảng Toán học tổ hợp và cấu trúc rời rạc
• Toán học tổ hợp
• Lý thuyết rời rạc
• Lý thuyết đồ thị
• Hàm đại số lôgic
• Kỹ thuật máy tính
• Hàm và thuật toán
• Độ phức tạp của thuật toán
• Độ tăng của hàm
• Đường đi Euler
• Thuật ngữ về đồ thị
• Hàm đơn ánh
• Thuật toán
• Thuật toán tìm kiếm
• Thuật toán sắp xếp nổi bọt
• Lý thuyết tập hợp
• Phép toán tập hợp
• Tích Descartes
• Một số kỹ thuật đếm
• Sử dụng sơ đồ Ven