I have a homework assignment that I am a little stumped on, the questions is:
Describe a sound and complete proof system (axioms and proof rules) for proposition logic. Explain in detail why you believe your proof system is sound and complete. Is your proof system terminating? If yes, explain why. If no, explain why not?
I am stumped for two reasons:
1) I can't seem to find an example of a "sound and complete proof system" my thinking here is that for a proof system to be useful it needs to be both sound and complete, so proof systems dont seem to bother to "state" that they are such.
2) When I asked the lecturer about the assignment, he said that we had discussed two proof systems in class that could be used. The only topics discussed seem to be proof by contradiction and proof by induction, however - I can't seem to find any reference as to what the axioms of these two are. For example, is the only axiom of proof by contradiction that: if $\bot \lnot A$ then $\top A$?
I'd appreciate any help/direction in this.
It sounds as if your attention flickered at some point in class -- if your lecturer said that at some point he had discussed two proof systems, he probably did -- e.g. an axiomatic system, and/or a natural deduction alternative, or a proof system which goes via converting to disjunctive or conjunctive normal forms, or ....
Proof by contradiction would be a rule (one among a number of rules) in an ND system. (Induction though wouldn't be a rule in proof system for propositional logic; you may have encountered it being used in metatheorical proofs about propositional logic, but not in proofs in propositional logic.)
OK: have you been to the library? Chased up the lecturer's references/suggested course reading? Looked at some other elementary logic texts? Every single one will give you a sound and complete proof system for propositional logic, in one style of another. Look at a few such books, then.
Elementary areas of mathematics in general, and logic in particular, are wonderfully supplied with excellent textbooks. Consult them! That is what they are there for ...