Example 6. C=(A1 V A2 VA3)A(B1VB2)AGCIV-C2V-C3) is a CNF. According to proof of Adequacy theorem, we have the following theorem Theorem 11. Any proposition can be reformed as a DNF and a CNF. oof. According to adequacy theorem Exercies 1. Which of the following expressions are well-formed? (a)(=(AVB)∧C) (b)(A∧B)C (c)(CVB)AA)分D) 2. Prove that set of propositions generated according to definition is countable 3. Prove that - is an adequate set of connectives. 4. Prove that the binary connective(aB)("not both. . and")called the Sheffer stroke whose truth table is given in the following table is adequat FF T 5. Prove that (A, V is not adequate 6. Let + be the ternary connective such that +aBy is equivalent to a+B+y (a) Show that (F, T,A,+) is complete (b) Show that no proper subset is complete Remark: +o is the ternary parity connective; +a10203 is true if and only if odd number of 01, 02, a is T 7. Prove that any proposition(Boolean function) can be represented as a CNF 6Example 6. α = (A1 ∨ A2 ∨ A3) ∧ (¬B1 ∨ B2) ∧ (¬C1 ∨ ¬C2 ∨ ¬C3) is a CNF. According to proof of Adequacy theorem, we have the following theorem. Theorem 11. Any proposition can be reformed as a DNF and a CNF. Proof. According to adequacy theorem. Exercies 1. Which of the following expressions are well-formed? (a) ((¬(A ∨ B)) ∧ C) (b) (A ∧ B) ∨ C (c) (((C ∨ B) ∧ A) ↔ D) 2. Prove that set of propositions generated according to definition is countable. 3. Prove that {¬, →} is an adequate set of connectives. 4. Prove that the binary connective (α|β) (“not both . . . and”) called the Sheffer stroke whose truth table is given in the following table is adequate. α β α|β T T F T F T F T T F F T 5. Prove that {∧, ∨} is not adequate. 6. Let +3 be the ternary connective such that +3αβγ is equivalent to α + β + γ. (a) Show that {F, T, ∧, +3} is complete. (b) Show that no proper subset is complete. Remark: +3 is the ternary parity connective; +α1α2α3 is true if and only if odd number of α1, α2, α3 is T. 7. Prove that any proposition(Boolean function) can be represented as a CNF. 6