(a)Let a be a well-defined proposition. a has arbitrary length when length k > 4.3 mark (b)B is satisfiable if and only if (B)is not valid. (3 marks) (c)(B)is not satisfiable if and only if B is valid. (3 marks) (d)The number of tautologies is the same as the number of unsatisfiable propositions (3 marks) (e) Given two sets of propositions∑1and∑2,∑1∑2→M(2)sM(∑1) 4. Let F be the constant false and M be the ternary minority connectives(M(A, B, C)is true if and only if at most one of A, B, C is true). Show that (F, M is complete.(4 marks 5. Prove that every proposition can be represented in CNF(Conjunctive Normal Form).(6 marks 6. Prove or disprove the following statements. If it is false, a counterexample is needed: (10 mari (a){(-(→)→-a),B}=(a→7).(4 marks) (b)IR+P,SVR, S)HnP. 3 marks) (c)(P→(Q→R)→(P→Q)→(P→B).(3 marks 7. Given the following deduction If the equatorial rain forests produce oxygen used by Americans, then eithe Americans ought to pay for the oxygen, or they ought to stop complaining about the destruction of the rain forests. But either it is false that americans ought to pay for the oxygen, or it is false that Americans ought to stop complaining about the destruction of the rain forests. Therefore, it is false that the equatorial rain forests produce oxygen used by Americans Answer the following questions:(9 marks) (a) Formalize the deduction with propositional logic. (5 marks) (b)Prove or disprove the conclusion formally.(4 marks 8. Given a set 2=a1,..., an of finite propositions, prove that 2F a if and only if (a1A…A∧an)→ a is valid.8 marks) 9. In 1977 it was proved that every planar map can be colored with four colors(Of course there are only finite countries on map) Suppose we have an infinite(but countable) planar map with countries C1, C2, C3 0 marks (a) Formalize this problem with propositional logic.(5 marks) (b)Prove that an infinite map can be still colored with four colors. (5 marks)(a) Let α be a well-defined proposition. α has arbitrary length when length k ≥ 4. (3 marks) (b) B is satisfiable if and only if (¬B) is not valid. (3 marks) (c) (¬B) is not satisfiable if and only if B is valid. (3 marks) (d) The number of tautologies is the same as the number of unsatisfiable propositions. (3 marks) (e) Given two sets of propositions Σ1 and Σ2, Σ1 ⊆ Σ2 ⇒ M(Σ2) ⊆ M(Σ1). 4. Let F be the constant false and M be the ternary minority connectives(M(A, B, C) is true if and only if at most one of A, B, C is true). Show that {F, M} is complete. (4 marks) 5. Prove that every proposition can be represented in CNF(Conjunctive Normal Form).(6 marks) 6. Prove or disprove the following statements. If it is false, a counterexample is needed:(10 marks) (a) {(¬(β → γ) → ¬α), β} |= (α → γ).(4 marks) (b) {R → P, ¬S ∨ R, S} ` ¬P.(3 marks) (c) ((P → (Q → R)) → ((P → Q) → (P → R))). (3 marks) 7. Given the following deduction: If the equatorial rain forests produce oxygen used by Americans, then either Americans ought to pay for the oxygen, or they ought to stop complaining about the destruction of the rain forests. But either it is false that Americans ought to pay for the oxygen, or it is false that Americans ought to stop complaining about the destruction of the rain forests. Therefore, it is false that the equatorial rain forests produce oxygen used by Americans. Answer the following questions: (9 marks) (a) Formalize the deduction with propositional logic. (5 marks) (b) Prove or disprove the conclusion formally. (4 marks) 8. Given a set Σ = {α1, . . . , αn} of finite propositions, prove that Σ |= α if and only if (α1 ∧ · · · ∧ αn) → α is valid.(8 marks) 9. In 1977 it was proved that every planar map can be colored with four colors(Of course there are only finite countries on map). Suppose we have an infinite(but countable) planar map with countries C1, C2, C3, . . .. (10 marks) (a) Formalize this problem with propositional logic. (5 marks) (b) Prove that an infinite map can be still colored with four colors. (5 marks) 2