Fudan University 复旦大学 2012-2013学年第二学期考试试卷 课程名称:离散数学(I) 课程代码:SOFT130040 开课院系:软件学院 考试形式:开卷 姓名 学号 专业 题 89—10总分 得分‖ DIRECTION: There are totally two pages of examination paper. You must write all your answers, include your name and student number clearly, on a specific answersheet. You have 2 hours to solve all the questi REMARK: All solutions are only for reference. Because there may be more than one method to solve a problem 1. Define a binary connective A e B whose truth table is given in Table 1. Answer the ABAb TTF Table 1: Truth table of e following questions (7 marks) (a)Prove or disprove that (,e) is adequate (2 marks (b)Add the atomic tableau of e into atomic tableaux (2 marks) ()Discuss the validity of (Ae B)+(Av-B by using tableau proof. 3 marks) Solution.(a) First A V B can be represented as A e-B.(1 mark) Hence (V, is adequate. , e) is also adequate. (1 mark (b)The tableau is shown in Figure 1. F and T each has 1 mark (c)The tableau is shown in Figure 2 It is a tableau proof. So the sentence/proposition valid 2. Give the following statements
Fudan University 复旦大学 2012-2013 学年第二学期考试试卷 课程名称: 离散数学 (II) 课程代码: SOFT130040.01 开课院系: 软件学院 考试形式: 开卷 姓名: 学号: 专业: 题目 1 2 3 4 5 6 7 8 9 10 总分 得分 Direction: There are totally two pages of examination paper. You must write all your answers, include your name and student number clearly, on a specific answersheet. You have 2 hours to solve all the questions. Remark: All solutions are only for reference. Because there may be more than one method to solve a problem. 1. Define a binary connective A ⊖ B whose truth table is given in Table 1. Answer the A B A ⊖ B T T T T F T F T F F F T Table 1: Truth table of ⊖ following questions. (7 marks) (a) Prove or disprove that {¬, ⊖} is adequate. (2 marks) (b) Add the atomic tableau of ⊖ into atomic tableaux. (2 marks) (c) Discuss the validity of (A ⊖ B) → (A ∨ ¬B) by using tableau proof. (3 marks) Solution. (a) First A ∨ B can be represented as A ⊖ ¬B. (1 mark) Hence {∨, ¬} is adequate. {¬, ⊖} is also adequate. (1 mark) (b) The tableau is shown in Figure 1. F and T each has 1 mark. (c) The tableau is shown in Figure 2 It is a tableau proof. So the sentence/proposition is valid. 2. Give the following statements: 1
FAeB T AeB FA TA FB T B Figure 1: Atomic tableau of e F(AeB)→(AV=B) T(AeB F(AV-B FA F-B T B T (AeB TA F B Figure 2: Tableau proof (a) The attack will succeed only if the enemy is taken by surprise or the position is weakly defended (b)The enemy will not be taken by surprise unless he is overconfident (c) The enemy will not be overconfident if the position is weakly defended (d)Therefore, the attack will not succeed Answer the following questions (7 marks (a) Translate the argument into propositions (4 marks) b) Use tableau proof to determine whether the argument is logically valid. 3 marks) Solution.(a)The proposition letters and its corresponding represented statement are as fo i. A: The attack will succeed B: The enemy is taken by surprise iii. C: The position is weakly defended iv. D: He is overconfident Then the statements can be represented as following: (each 0.5 mark) i.A→(BVC)
F A ⊖ B F A T B T A ⊖ B T A F B Figure 1: Atomic tableau of ⊖ F (A ⊖ B) → (A ∨ ¬B) T (A ⊖ B) F (A ∨ ¬B) F A F ¬B T B T (A ⊖ B) T A F B ⊗ ⊗ Figure 2: Tableau proof (a) The attack will succeed only if the enemy is taken by surprise or the position is weakly defended. (b) The enemy will not be taken by surprise unless he is overconfident. (c) The enemy will not be overconfident if the position is weakly defended. (d) Therefore, the attack will not succeed. Answer the following questions: (7 marks) (a) Translate the argument into propositions. (4 marks) (b) Use tableau proof to determine whether the argument is logically valid. (3 marks) Solution. (a) The proposition letters and its corresponding represented statement are as following:(each 0.5 mark) i. A: The attack will succeed. ii. B: The enemy is taken by surprise. iii. C: The position is weakly defended. iv. D: He is overconfident. Then the statements can be represented as following:(each 0.5 mark) i. A → (B ∨ C). 2
i.→D→-B. i.C→ iv, - A (b) The result is -A. The tableau proof is shown in Figure 3.(2 marks) F(=A) T A TA→(BVC) FA T(BVC) 6 TB TC TC→-D FC T-D Figure 3: Tableau proof As Figure 3 shown, there is at least a noncontradictory path. So the argument is not logically valid. (1 marks 3. Given a formula (, y, a)=(v)()va(a, y, a)),p(a, y, a), where a, 3, z are free variables. Answer the following questions (8m (a) Show which occurrence of every variable is free. If it is bound, show which quantifier bounds it (b)Given a function f(t, a) and t does not occurs in Is y/f(t, a) substitutable in p(a, y, a)? Show your reason. (2 marks (c) Discuss its truth of (a, y, 2). If it is not valid, give a model made it false. (3 marks) Solution.(a)The third occurrence of the second occurrence of z and both occurrences of y are free. (1 mark) The first two a is bounded by(Vr).(1 mark)The first z is bounded by 3z. (1 mark (b) The second substitution of y is substitutable for z, t in f is still free. However the first one is not for z is bounded by 3x(1 mark) Then it is not substitutable. (1 mark) (c) It is not a sentence. We first represent it as the V-closure form. It is valid. It could be proved by a tableau proof shown in Figure 4. Obviously, the tableau noncontradictory. (2 marks)So it is not valid. The counterexample is very simple Let A=co, C1, c21,v=(co1, p =0.(1 mark
ii. ¬D → ¬B. iii. C → ¬D. iv. ¬A. (b) The result is ¬A. The tableau proof is shown in Figure 3.(2 marks) F (¬A) T A T A → (B ∨ C) F A T (B ∨ C) ⊗ T B T C . . . T C → ¬D F C T¬D ⊗ F D Figure 3: Tableau proof As Figure 3 shown, there is at least a noncontradictory path. So the argument is not logically valid.(1 marks) 3. Given a formula Φ(x, y, z) = (∀x)(ψ(x)∨(∃z)φ(x, y, z)) → φ(x, y, z), where x, y, z are free variables. 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(t, z) and t does not occurs in Φ. Is y/f(t, z) substitutable in Φ(x, y, z)? Show your reason. (2 marks) (c) Discuss its truth of Φ(x, y, z).If it is not valid, give a model made it false. (3 marks) Solution. (a) The third occurrence of x, the second occurrence of z and both occurrences of y are free.(1 mark) The first two x is bounded by (∀x). (1 mark) The first z is bounded by ∃z.(1 mark) (b) The second substitution of y is substitutable for z, t in f is still free. However the first one is not for z is bounded by ∃z.(1 mark) Then it is not substitutable. (1 mark) (c) It is not a sentence. We first represent it as the ∀-closure form. It is valid. It could be proved by a tableau proof shown in Figure 4. Obviously, the tableau is noncontradictory.(2 marks) So it is not valid. The counterexample is very simple. Let A = {c0, c1, c2}, ψ = {c0}, φ = ∅. (1 mark) 3
Fⅵ arayA(x)(v(x)∨(彐zy(x,y,z)→φ(x,孙,z) F VyVz((va)((r)vxp(a, y, z))-+P(c0, 9, a)), new co F Vz(Va)((a)v a(a, c1, 2))->p(c0, C1, a)), new cl F(a)(v(a)v(xp(a, c1, a))->p(c0, C1, C2), new C2 T (V(v(a)Vz(a, c1, z)) Fpc T(Vr)(v(r)vxo(a, c1, z)) T v(co)V zy(co, c1, z)) T al(co) T 3xp(co, C1, z) Figure 4: Tableau proof 4. Prove or disprove the following statements. If it is false, a counterexample should be described (9 marks) a){A→B,B→C,=C} (3 marks (b)彐x(o(x)→v(x)→(xo(x)→彐(x) (c)3.cVyVw(o(a/)Vv),3rVy(Vzv v). where o and ol are any formulas with free variables a, yand z. w is a variable not appearing in and y (3 marks Solution. (a) The tableau is show in Figure 5.(2 ks)As it is contradictory, so ac- e assertion Is d (1 mark (b) The tableau is show in Figure 6. As it is noncontradictory, so the sentence is not valid. (2 marks) Along the left path, we can construct a counterexample. Let A=co, c1,o {co},=0 (c) There are free variables. It should be transformed into its -closure form as Vz rvyVw(o(e, y, w)v v(a, y, a))-3rvy(Vap(a, y, a)Vv (a, y, a)).(1 mark) The tableau is shown in Figure 7. It is contradictory. So it is valid.(2 marks) 5. Give two sentences a= 3x(P(a)>Q)and B=(VrP(a)Q) (a) Prove that B a in semantics approach (b) Prove it by using tableau proof (2 marks (c) If a is free in Q, discuss the truth of the following assertion 3r(P(a),Q(r))H (Va P()+Q(a)). If is wrong, you should give a counterexample (3 marks
F ∀x∀y∀z((∀x)(ψ(x) ∨ (∃zφ(x, y, z)) → φ(x, y, z)) F ∀y∀z((∀x)(ψ(x) ∨ (∃zφ(x, y, z)) → φ(c0, y, z)), new c0 F ∀z((∀x)(ψ(x) ∨ (∃zφ(x, c1, z)) → φ(c0, c1, z)), new c1 F (∀x)(ψ(x) ∨ (∃zφ(x, c1, z)) → φ(c0, c1, c2), new c2 T (∀x)(ψ(x) ∨ (∃zφ(x, c1, z)) F φ(c0, c1, c2) T (∀x)(ψ(x) ∨ (∃zφ(x, c1, z)) T ψ(c0) ∨ (∃zφ(c0, c1, z)) T ψ(c0) T ∃zφ(c0, c1, z) . . . Figure 4: Tableau proof 4. Prove or disprove the following statements. If it is false, a counterexample should be described: (9 marks) (a) {A → B, B → C, ¬C} |= ¬A. (3 marks) (b) ∃x(ϕ(x) → ψ(x)) → (∃xϕ(x) → ∃xψ(x)). (3 marks) (c) ∃x∀y∀w(ϕ(z/w) ∨ ψ) → ∃x∀y(∀zϕ ∨ ψ). where ϕ and ψ are any formulas with free variables x, yand z. w is a variable not appearing in ϕ and ψ. (3 marks) Solution. (a) The tableau is show in Figure 5.(2 marks) As it is contradictory, so according to soundness theorem, the assertion is valid.(1 mark) (b) The tableau is show in Figure 6.As it is noncontradictory, so the sentence is not valid.(2 marks) Along the left path, we can construct a counterexample. Let A = {c0, c1}, ϕ = {c0}, ψ = ∅. (c) There are free variables. It should be transformed into its ∀-closure form as ∀z(∃x∀y∀w(ϕ(x, y, w)∨ ψ(x, y, z)) → ∃x∀y(∀zϕ(x, y, z)∨ψ(x, y, z))).(1 mark) The tableau is shown in Figure 7. It is contradictory. So it is valid. (2 marks) 5. Give two sentences α = ∃x(P(x) → Q) and β = (∀xP(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 ∃x(P(x) → Q(x)) ⊢ (∀xP(x) → Q(x)). If is wrong, you should give a counterexample. (3 marks) 4
T A T-C F C TB→C FB TC TA→B⑧ FAT B 5: Tableau of 4.( a) Solution.(a) If Va P(r) Q is true, then Var P() is false or Q is true. (1 mark) If Va P(r)is false, there is at least a ground term t make P(t) false. We have -P(t)or Q(1 mark)So there is a ground term t make P(t),Q(1 mark) Finally we have r(P(x)→Q)(1mark (b) We first give the tableau proof as Figure8. The tableau is contradictory. It means BHa. By soundness theorem, we have BEa (c There is a formula. It is to prove 3 r(P()Q())H Vr(va P(a)>Q(a).(I mark Its tableau proof is given in Figure 9.(1 mark) The right branch is noncontradictory. We can construct a model A with A=co, C1, P=co, C1, Q=c1 such that A make the assertion wrong. (1 mark 6. Construct a set of sentences S subject to the following properties (5 marks (a) Every finite subset of S has only finite model (b)It has only infinite model (3 marks You should prove why the property holds.(Hints: there is no size limit on S) Solution. Define a sentence as n=3c1..in A1<iti<n -(ai=aj). Then we can form a set of sentences S=oili>1.(1 m (a)Consider any finite subset Si=oil, .. oin], where i1 <.. ik. To satisfy S,we need only ik distinct elements, which means the model is finite.(1 mark) (b) Because every finite subset of s is satisfiable, S is also satisfiable according to Com pactness theorem (1 mark) Suppose the model is still finite, say N. Consider i with i>N, which can't be satisfied. So the model can only be infinite.(2 marks)
F ¬A T A T ¬C F C T B → C F B T C T A → B ⊗ F A T B ⊗ ⊗ Figure 5: Tableau of 4.(a) Solution. (a) If ∀xP(x) → Q is true, then ∀xP(x) is false or Q is true.(1 mark) If ∀xP(x) is false, there is at least a ground term t make P(t) false. We have ¬P(t) or Q.(1 mark) So there is a ground term t make P(t) → Q.(1 mark) Finally we have ∃x(P(x) → Q).(1 mark) (b) We first give the tableau proof as Figure 8. The tableau is contradictory. It means β ⊢ α. By soundness theorem, we have β |= α. (c) There is a formula. It is to prove ∃x(P(x) → Q(x)) ⊢ ∀x(∀xP(x) → Q(x)). (1 mark) Its tableau proof is given in Figure 9. (1 mark) The right branch is noncontradictory. We can construct a model A with A = {c0, c1}, P = {c0, c1}, Q = {c1} such that A make the assertion wrong. (1 mark) 6. Construct a set of sentences S subject to the following properties: (5 marks) (a) Every finite subset of S has only finite model. (2 marks) (b) It has only infinite model. (3 marks) You should prove why the property holds. (Hints: there is no size limit on S.) Solution. Define a sentence as ϕn = ∃x1 . . . ∃xn ∧ 1≤i̸=j≤n ¬(xi = xj ). Then we can form a set of sentences S = {ϕi |i ≥ 1}. (1 mark) (a) Consider any finite subset Si = {ϕi1 , . . . , ϕik }, where i1 < · · · < ik. To satisfy S ′ , we need only ik distinct elements, which means the model is finite. (1 mark) (b) Because every finite subset of S is satisfiable, S is also satisfiable according to Compactness theorem.(1 mark) Suppose the model is still finite, say N. Consider ϕi with i > N, which can’t be satisfied. So the model can only be infinite. (2 marks) 5