2013年期末试卷.pdf

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 T T F F A⊖B T T F T B T F T F 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 F A⊖B T A⊖B FA TA FB TB Figure 1: Atomic tableau of ⊖ F (A ⊖ B) → (A ∨ ¬B) T (A ⊖ B) F (A ∨ ¬B) FA F ¬B TB T (A ⊖ B) TA FB ⊗ ⊗ 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 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) TA T A → (B ∨ C) FA T (B ∨ C) ⊗ TB TC .. . T C → ¬D FC T¬D ⊗ FD 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 ∀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 ∃zφ(c0 , c1 , z) T ψ(c0 ) .. . 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 F ¬A TA T ¬C FC TB→C FB TC TA→B ⊗ FA TB ⊗ ⊗ 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 a set of sentences S = {ϕi |i ≥ 1}. (1 mark) ∧ 1≤i̸=j≤n ¬(xi = xj ). Then we can form (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 F ∃x(ϕ(x) → ψ(x)) → (∃xϕ(x) → ∃xψ(x)) T ∃x(ϕ(x) → ψ(x)) F ∃xϕ(x) → ∃xψ(x) T ∃xϕ(x) F ∃xψ(x) T ∃xϕ(x) T ϕ(c0 ), new constant c0 T ∃x(ϕ(x) → ψ(x)) T ϕ(c1 ) → ψ(c1 ), new constant c1 F ϕ(c1 ) T ψ(c1 ) F ∃xψ(x) F ∃xψ(x) F ψ(c1 ) F ψ(c1 ) .. . ⊗ Figure 6: Tableau of 4.(b) 7. Given a language L, T is the theory and ϕ is a sentence of L. T is finitely satisfiable if every finite subset of T is satisfiable. Answer the following question: (6 marks) (a) If T is finitely satisfiable, prove that either T ∪ {ϕ} or T ∪ {¬ϕ} is finite satisfiable. (4 marks) (b) If T is general, prove or disprove the result in (a). (2 marks) Solution. (a) Suppose that T ∪ {ϕ} is not finitely satisfiable.(1 mark) Then, there is a finite ∆ ⊂ T such that ∆ |= T . (1 mark) We claim that T ∪{¬ϕ} is finitely satisfiable. Let Σ be a finite subset of T . Because ∆ ∪ Σ is satisfiable and ∆ ∪ Σ |= ¬ϕ, Σ ∪ {ϕ} is satisfiable.(2 mark) Thus T ∪ {¬ϕ} is finitely satisfiable. (b) Given a general T , if T is satisfiable, then its every finite subset is also satisfiable.(1 mark) Then it also holds.(1 mark) 8. In 1977 it was proved that every planar map can be colored with four colors(Of course there are only finite countries on map). If two countries are adjacent, they must be colored with two different colors. 6 Generally, a planar map can be modeled as a planar graph. Every country is a member of vertices {v1 , v2 , . . .}, if two countries vi and vj are adjacent, then there is a edge (vi , vj ) between them. Answer the following questions. (9 marks) (a) Formalize 4-clolorable problem with predicate logic sentences. (5 marks) (b) Prove that an infinite map can be still colored with four colors. (4 marks) Solution. This is only a reference solution. There are many describing approaches. A grap can be represented as G =< V, E >. (a) Let c0 , c1 , c2 , c3 be constant to represent 4 colors. ϕ(x, c) means x is colored with c. (1 mark) E(x, y) means vertices x and y has a edge. E is a set of sentences like E(vi , vj ), vi , vj ∈ V . (1 mark) We can formulate a graph which is 4-colorable with the following sentences: i. ψ1 = ∀x(P (x, c0 ) ∨ P (x, c1 ) ∨ P (x, c2 ) ∨ P (x, c3 )). It means that every vertex can be colored with one of 4 colors. (1 mark) ∧ ii. ψ2 = ∀x( 0≤i̸=j≤3 ¬(P (x, ci ) ∧ P (x, cj )). A vertex can only be colored with one color.(1 mark) ∧ iii. ψ3 = ∀x∀y(E(x, y) → ¬( 0≤i≤3 ¬(P (x, ci ) ∧ P (y, ci )))). It means if two vertex are adjacent, they cannot be colored with the same color.(1 mark) (b) Σ = E ∪ {ψ1 , ψ2 , ψ3 } is an infinite set. (1 mark) Consider any finite subset Σ0 . We can extract vertices V0 from it and construct a set S which describe the graph G0 generated by V0 .(1 mark) For every finite subgraph is 4-colorable, S is satisfiable. Σ0 must be satisfiable. (1 mark) According to compactness theorem, Σ is satisfiable which means the graph is 4-colorable. (1 mark) 7 F ∀z(∃x∀y∀w(ϕ(x, y, w) ∨ ψ(x, y, z)) → ∃x∀y(∀zϕ(x, y, z) ∨ ψ(x, y, z))) F ∃x∀y∀w(ϕ(x, y, w) ∨ ψ(x, y, c0 )) → ∃x∀y(∀zϕ(x, y, z) ∨ ψ(x, y, c0 )), new constant c0 T ∃x∀y∀w(ϕ(x, y, w) ∨ ψ(x, y, c0 )) F ∃x∀y(∀zϕ(x, y, z) ∨ ψ(x, y, c0 )) T ∃x∀y∀w(ϕ(x, y, w) ∨ ψ(x, y, c0 )) T ∀y∀w(ϕ(c1 , y, w) ∨ ψ(c1 , y, c0 )), new constant c1 F ∃x∀y(∀zϕ(x, y, z) ∨ ψ(x, y, c0 )) F ∀y(∀zϕ(c1 , y, z) ∨ ψ(c1 , y, c0 )) F ∀zϕ(c1 , c2 , z) ∨ ψ(c1 , c2 , c0 ), new constant c2 F ∀zϕ(c1 , c2 , z) F ψ(c1 , c2 , c0 ) F ∀zϕ(c1 , c2 , z) F ϕ(c1 , c2 , c3 ), new constant c3 T ∀y∀w(ϕ(c1 , y, w) ∨ ψ(c1 , y, c0 )) T ∀w(ϕ(c1 , c2 , w) ∨ ψ(c1 , c2 , c0 )) T ϕ(c1 , c2 , c3 ) ∨ ψ(c1 , c2 , c0 ) T ϕ(c1 , c2 , c3 ) T ψ(c1 , c2 , c0 ) ⊗ ⊗ Figure 7: Tableau of 4.(c) 8 F ∃x(P (x) → Q) T ∀xP (x) → Q F ∀xP (x) TQ F P (c), new constant c F ∃x(P (x) → Q) F ∃x(P (x) → Q) F P (t) → Q, for a ground term t F P (c) → Q T P (t) T P (c) FQ FQ ⊗ ⊗ Figure 8: Tableau proof of 5.(b) F ∀x(∀xP (x) → Q(x)) F ∀xP (x) → Q(c0 ), new constant c0 T ∀xP (x) F Q(c0 ) T ∃x(P (x) → Q(x)) T P (c1 ) → Q(c1 ), new constant c1 F P (c1 ) T Q(c1 ) T ∀xP (x) T ∀xP (x) T P (c1 ) T P (c0 ) ⊗ .. . Figure 9: Tableau proof of 5.(c) 9