This set of exercises develops a formal system for propositional logic with a single binary logical connective, , known as the Sheffer stroke or NAND operation. The rules are slightly more complicated, but it is remarkable that a fully expressive propositional logic can be developed from the single symbol.
We start with a set of letters and the terms built from with the symbol only. So each is in and if then so is .
The following are rules of the system. (We will see shortly that a much smaller set of rules suffices, but it is convenient when learning the system to have a larger set handy.)
Given rule: if then .
|-Elimination rules: (|-EL) if and then ; (|-ER) if and then .
||-Elimination rules: (||-EL) if and then ; (||-ER) if and then .
|-Introduction rules: (|-IL) if then ; and (|-IR) if then .
||-Introduction rules: (||-IL) if then ; and (||-IR) if then .
Weakening rules: (WL) if then ; and (WR) if then .
Cut rules: (|-CutL) if and then ; (|-CutR) if and then . (Similar rules may be invented/discovered for Cut on the other side, or cut where the hypotheses has and the conclusion is , etc. But the ones listed already suffice.)
Double negation rule: if then .
In the following, the Given rule should be assumed as available implicitly at all times.
Show that from ||-IL one can prove for all .
Show that using only WL, ||-EL and |-IL one can show for all .
Use |-EL and |-IL (or |-ER and |-IR) to derive the following metarule: if then . Deduce that given |-EL and |-IL (or |-ER and |-IR) the left version of each rule is equivalent to the right version, in the sense that if one is given the other is available as a metarule.
Show that the |-CutL rule is a metarule of the system with ||-ER, |-EL and |-IL.
We now show completeness and soundness theorems for the system with these rules. From now on we assume refers to provability using any of the rules, or equivalently using rules |-EL, ||-EL, |-IL, ||-IL, WL and the double negation rule.
A valuation is a map . Valuations are extended to arbitrary terms of by .
means that for all valuations , if for all then .
Prove the Soundness Theorem, that implies . (Using induction on the length of proofs.)
A set is consistent if for no is it the case that and .
Use |-IL, ||-IL and a cut rule to show that if is inconsistent then . Deduce that if is consistent and is any term in then at least one of or is consistent.
Prove that if then is consistent. (Use introduction rules, cut and the double negation rule.)
Show that if is consistent then there is a maximally consisten . For this show that:
(a) the valuation if and if is well-defined;
(b) if then at least one of or ;
(c) if then both and ;
(d) hence (by induction on terms in ) iff .
(a) Deduce from the previous exercise that is consistent implies that there is a valuation making each true.
(b) Now assume that and use (a) to show that there is a valuation making each true and false, i.e. that .