4. Binary connectives: 10 of 16 are real binary functions Definition 6(Adequate connectives). A set S of truth functional connectives is adequate if, given any truth function connective o, we can find a proposition built up from the connectives is S with the same abbreviated truth table as g In general, we have the following Adequacy theorem Theorem 7(Adequacy).,v, A is adequate( complete) It means that a few connectives is enough. Before formal proof. We first consider whether we can use{→,v,} to represent→. As our expectation,(a→B)≡(a)VB). It can be observed from the abbreviated truth table of - as shown in Figure 3a We first just consider a very special case, all Ai are true and o(Al, .. Ak) is also true. Consider the conjunction A1∧A2∧…∧Ak, you would find that the configuration of other row would make it false Generally, we have the following proof. Proof. Construct the truth table of any connective o(Al, .. Ak). Consider the row with function value 1. For details, please refer to our textbook Furthermore, we can remove connective A such that the remainders are still adequate Corollary 8.-,v is adequate We may wonder whether there is a adequate set with only one connective. The answer is positive. You can refer to exercise 4. The propositional logic with only one connective elegant. However, it first serve people. In practice, we also hope that the system is friend tradeoff, most of text book will adopt the set (,A, V., and + are two one which chara cd. wvty human's thinking style. So they are also kept in the symbol set In class, we have not mentioned the following to definition. Any truth function is represented as a proposition with form of disjunction of conjunction. It is called as followin Definition 9(DNF). a is called disjunctive normal form(abbreviated DNF). If a is a disjunction Q =1 where each ri is a conjunction n=B1∧……∧B and each Bij is a proposition letter or the negation of a proposition letter. Example5.a=(A1∧A2AA3)V(-B1∧B2)V(-C1∧=C2A-C3) is a dne For symmetry, we can also exchange the position of conjunction and disjunction in DNF and get the following: Definition 10(CNF). a is called conjunctive normal form(abbreviated CNF). If a is a conjunction where each i is a disjunction and each Bii is a proposition letter or the negation of a proposition letter 54. Binary connectives: 10 of 16 are real binary functions. Definition 6 (Adequate connectives). A set S of truth functional connectives is adequate if, given any truth function connective σ, we can find a proposition built up from the connectives is S with the same abbreviated truth table as σ. In general, we have the following Adequacy theorem. Theorem 7 (Adequacy). {¬, ∨, ∧} is adequate(complete). It means that a few connectives is enough. Before formal proof. We first consider whether we can use {¬, ∨, ∧} to represent →. As our expectation, (α → β) ≡ ((¬α) ∨ β). It can be observed from the abbreviated truth table of → as shown in Figure 3a. We first just consider a very special case, all Ai are true and σ(A1, . . . , Ak) is also true. Consider the conjunction A1 ∧ A2 ∧ · · · ∧ Ak, you would find that the configuration of other row would make it false. Generally, we have the following proof. Proof. Construct the truth table of any connective σ(A1, . . . , Ak). Consider the row with function value 1. For details, please refer to our textbook. Furthermore, we can remove connective ∧ such that the remainders are still adequate. Corollary 8. {¬, ∨} is adequate. We may wonder whether there is a adequate set with only one connective. The answer is positive. You can refer to exercise 4. The propositional logic with only one connective is very elegant. However, it first serve people. In practice, we also hope that the system is friend. With tradeoff, most of text book will adopt the set {¬, ∧, ∨}. → and ↔ are two one which characterize human’s thinking style. So they are also kept in the symbol set. In class, we have not mentioned the following to definition. Any truth function is represented as a proposition with form of disjunction of conjunction. It is called as following: Definition 9 (DNF). α is called disjunctive normal form (abbreviated DNF). If α is a disjunction α = γ1 ∨ · · · ∨ γk, where each γi is a conjunction γi = βi1 ∧ · · · ∧ βini and each βij is a proposition letter or the negation of a proposition letter. Example 5. α = (A1 ∧ A2 ∧ A3) ∨ (¬B1 ∧ B2) ∨ (¬C1 ∧ ¬C2 ∧ ¬C3) is a DNF. For symmetry, we can also exchange the position of conjunction and disjunction in DNF and get the following: Definition 10 (CNF). α is called conjunctive normal form (abbreviated CNF). If α is a conjunction α = γ1 ∧ · · · ∧ γk, where each γi is a disjunction γi = βi1 ∨ · · · ∨ βini and each βij is a proposition letter or the negation of a proposition letter. 5