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 .
