Exercise 126 (Hilbert-styles vs. Natural Deduction). Read Exercise 125, without necessarily solving it, before you attempt this one. The preceding exercise proposes a strictly proof-theoretic approach to showing that a Hilbert-style

proof system and a natural-deduction proof system have equal deductive power. In this exercise we consider an alternative semantic approach, which invokes Soundness and Completeness for both proof systems. Specifically, each of the two sys- tems as here presented is sound and complete relative to the standard (classical) semantics of propositional logic based on Boolean algebras. There are three parts in this exercise, the first two of which are just plans in outline to prove the equivalence of the two systems: 1. If I, then I by Soundness of the Hilbert system. By Completeness of the natural deduction system, it follows that I END 4. 2. If I END 4, then I by Soundness of the natural deduction system. By Completeness of the Hilbert system, it follows that I ₁9. Provide the details of the two preceding parts, given only in outline here, pointing out missing prerequisites (e.g., we do not prove Soundness and Completeness for the Hilbert system in these notes) and propose ways of filling the gaps and how to prove them. (We do not add subscripts "H" and "ND" to "", because the two systems are sound and complete relative to the same semantics.) 3. Compare and discuss the pros and the cons of the proof-theoretic approach in Exercise 125 and the approach in this Exercise 126 which makes a detour through semantics. 0