Assignment P

In this 55-minute test, besides remembering some key concepts covered in the class, students had the opportunity to develop a new logistic system \mathcal{R}, rebuild the notions, such as well formed formula, sytax, semantic, etc., as what we’ve done to \mathcal{P}, and discuss its decision problem, completeness and soundness, which turns out to be very interesting. In the last problem, students need to mimic the proof of consistency of \mathcal{F}.

Common Mistakes:

  • In problem I, some students switched Completeness and Soundness in their answers. Roughly speaking, completeness means nothing needs to be added to it, while soundness means axioms are all valid and rules having the property of preserving truth.
  • In problem II. A, strong induction over the construction of a proof is the key to the answer. Some students forgot to prove the easier direction that a t-wff is a theorem. In problem II. E, a counterexample should be stated explicitly.
  • In problem III, few students stated consistent with respect to negation instead of absolutely consistent.
  • In problem IV. A, many students made mistakes. One of the golden rules while translating statements is to leave the free variables alone and kill the bounded. In problem IV. D, the key idea is to notice that the result of erasing all quantifiers of the new axiom is a tautology, the rest is just mimicking the consistency proof of \mathcal{F}.

Leave a Reply

Your email address will not be published. Required fields are marked *