Fudan University 复旦大学 2011-2012学年第2学期考试试卷 课程名称:离散数学(I 课程代码:SOFT130040.01 开课院系:软件学院 考试形式:开卷 姓名 学号 专业 叶° 「总分 DIRECTION: There are totally two pages and 60 marks of examination paper. You must write all your answers, include your name and student number clearly, on a given answersheet. You have 2 hours to solve all the questions. Please mark your name and id on each answer sheet 1. Give the following statements (a)If i graduate this semester, then i will have passed the physics course (b) If I do not study physics for 10 hours a week, then I would not pass physics (c)If I study physics for 10 hours a week, then I can not play volley ball Answer the following questions:(9 marks) (a) Formalize them in logic approach (5 marks) (b)Prove or disprove the assertion: if I play volleyball, I will not graduate this semester mar」 2. Define a binary connective A e B whose truth table is given in Table ??.Answer A|B|A⊕B 00 Table 1: Truth table of D the following questions. (7 marks) (a) Is e adequate? 2 marks)
Fudan University ❊➀➷ 2011-2012➷❝✶2➷Ï⑧➪➪ò ➅➜➯→: ❧Ñê➷(II) ➅➜➇è: SOFT130040.01 ♠➅✓❳: ❫❻➷✓ ⑧➪✴➟: ♠ò ✻ ➯: ➷ Ò: ❀ ➆: ❑✽ 1 2 3 4 5 6 7 8 9 10 ♦➞ ✚➞ Direction: There are totally two pages and 60 marks of examination paper. You must write all your answers, include your name and student number clearly, on a given answersheet. You have 2 hours to solve all the questions. Please mark your name and id on each answer sheet. 1. Give the following statements: (a) If I graduate this semester, then I will have passed the physics course. (b) If I do not study physics for 10 hours a week, then I would not pass physics. (c) If I study physics for 10 hours a week, then I can not play volleyball. Answer the following questions: (9 marks) (a) Formalize them in logic approach. (5 marks) (b) Prove or disprove the assertion: if I play volleyball, I will not graduate this semester. (4 marks) 2. Define a binary connective A ⊕ B whose truth table is given in Table ??. Answer A B A ⊕ B 0 0 0 0 1 1 1 0 1 1 1 0 Table 1: Truth table of ⊕ the following questions.(7 marks) (a) Is {⊕} adequate? (2 marks) 1
(b) Add the atomic tableau of into atomic tableaux. (2 marks) (c) Discuss the validity of(A⊕B)→((A∧=B)V(=A∧B)) by using tableau 3. Given a formula (a, y)=(p(a, y)+(va)(ab()v.r)(a, y))), answer the follow ing questions. (8 marks) (a)Show which occurrence of every variable is free. If it is bound, show which quantifier bounds it 3 marks (b)Given a function f(a, r), is y/f(a, )in (a, y) substitutable? Show your reason 2 marks (c) Discuss its truth of (a, y) (3 marks) 4. Prove or disprove the following statements using tableau proof system. If it is false, a counterexample is needed:( 9 marks) (a)(AVB, BVC, CVD)HA+D (3 marks) (b)Var(o(a)vv(a))+vaco()vara(a)) nar (c) Vary(p V3x)V=yw(p Vv(z/w)), where p and w are any formulas with free variables T, y and z. w is a variable not appearing in p and al.3 marks) 5. Give two sentence a=(Var P(a))->Q and B= Va(P(r)Q).(9 marks) (a)Prove that B h a in semantics approach (4 marks) (b) Prove it by using tableau proof (2 marks) (c) If a is free in Q, discuss the truth of the following assertion (wxP(x)→Q(x)hwr(P(x)→Q(x) (3 marks 6. Construct a set of sentences S and prove that it has only infinite models marks 7. Let S=oi(al,., Ini s n for some n be a set of open formulas on top of a language L. If S is unsatisfiable, there are only finitely many ground instance of elements of S whose conjunction is unsatisfiable 5 marks) 8. A graph G=(V, E is 2-colorable if and only if G has no odd cycle. Given a binary predicate E(, y), which means that there is a edge between vertex and vertex y (9 marks) (a) Construct a sentence n to represent there is no cycle with n-length.(Hints Construct it recursively . (3 marks) (b) Use a set of sentences E to describe that G is 2-colorable 2 marks) (c)Prove that a graph is 2-colorable cannot be described by a sentence v(Hints Consider -a/ and sentence set 2, then apply Compactness Theorem. ) (4
(b) Add the atomic tableau of ⊕ into atomic tableaux. (2 marks) (c) Discuss the validity of (A ⊕ B) → ((A ∧ ¬B) ∨ (¬A ∧ B)) by using tableau proof. (3 marks) 3. Given a formula Φ(x, y) = (ϕ(x, y) → (∀x)(ψ(x)∨(∃x)ϕ(x, y))), answer the following questions.(8 marks) (a) Show which occurrence of every variable is free. If it is bound, show which quantifier bounds it. (3 marks) (b) Given a function f(z, x), is y/f(z, x) in Φ(x, y) substitutable? Show your reason. (2 marks) (c) Discuss its truth of Φ(x, y). (3 marks) 4. Prove or disprove the following statements using tableau proof system. If it is false, a counterexample is needed: (9 marks) (a) {A ∨ ¬B, B ∨ ¬C, C ∨ ¬D} ` A → D. (3 marks) (b) ∀x(φ(x) ∨ ψ(x)) ↔ (∀xφ(x) ∨ ∀xψ(x)). (3 marks) (c) ∀x∃y(ϕ∨ ∃zψ) → ∀x∃y∃w(ϕ∨ψ(z/w)), where ϕ and ψ are any formulas with free variables x, y and z. w is a variable not appearing in ϕ and ψ. (3 marks) 5. Give two sentence α = (∀xP(x)) → Q and β = ∀x(P(x) → Q). (9 marks) (a) Prove that β |= α in semantics approach. (4 marks) (b) Prove it by using tableau proof. (2 marks) (c) If x is free in Q, discuss the truth of the following assertion ((∀xP(x)) → Q(x)) ` ∀x((P(x) → Q(x)). (3 marks) 6. Construct a set of sentences S and prove that it has only infinite models. (4 marks) 7. Let S = {φi(x1, . . . , xni )|i ≤ n for some n} be a set of open formulas on top of a language L. If S is unsatisfiable, there are only finitely many ground instance of elements of S whose conjunction is unsatisfiable. (5 marks) 8. A graph G = hV, Ei is 2-colorable if and only if G has no odd cycle. Given a binary predicate E(x, y), which means that there is a edge between vertex x and vertex y. (9 marks) (a) Construct a sentence φn to represent there is no cycle with n-length. (Hints: Construct it recursively.) (3 marks) (b) Use a set of sentences Σ to describe that G is 2-colorable. (2 marks) (c) Prove that a graph is 2-colorable cannot be described by a sentence ψ. (Hints: Consider ¬ψ and sentence set Σ, then apply Compactness Theorem.) (4 marks) 2