# Assignment A

Students are expected to use Principle of Induction on the Construction of a Wff. You must explicitly state the three conditions in the principle and reason why these three conditions hold. Creativities are required since you need to decide the properties which hold for all wffs but the formulas in the exercises.

Common Mistakes:

• Students who failed to acquire the technique when justifying their answers will get at most 1 point for each question even if their conclusions are correct.
• Several students used ‘paired brackets’ in their proofs. However, this notion is undefined though it looks quite intuitive. In fact, paired brackets are defined inductively on formulas. Only one student succeeded to define the notion by developing the concepts of ‘matched brackets’ and ‘matchable formulas’.
• Note that the formation rules for wffs only use propositional variables, \sim and \vee. Strictly speaking, other symbols such as \wedge, \supset are just shorthands. Thus, in these exercises, you are not supposed to consider the appearance of symbols other than the ones in the formation rules.
• In X1004(b), some students planned to prove that every wff doesn’t contain empty brackets []. But this doesn’t suffice to meet the third condition in the principle. You can think about how to make that up by adding more properties.
• Same things happen to X1004(c) when students were trying to prove \vee] doesn’t show up in wffs. And it is more complicated to modify it.