Consider the following recursive definition of the set of all propositional formulas F
Base Case: ∀i ∈ N pi ∈ F (pi is a propositional variable) 1
3. We can define sorted lists of integers as follows.
– ∀f1,f2 ∈F f1 ∧f2 ∈F
– ∀f1,f2 ∈F f1 ∨f2 ∈F
And, F contains no other elements than defined above.
Recall that propositional formulas f1 and f2 are logically equivalent if and only if f1 and f2 evaluate to the same value, no matter how their variables are set.
The goal is to prove that for all propositional formulas f ∈ F, there is an equivalent propositional formula f′ ∈ F such that the only negation symbols (“¬”) in f′ are applied to individual propositional variables.
For example, the formal ¬(p1 ∧ p2) ∨ p3 is in F and its equivalent formula (¬p1 ∨ ¬p2) ∨ p3 has the negation symbols only applied to the individual propositional variables. You are allowed to use propositional logic equalities such as ¬(p ∧ q) = ¬p ∨ ¬q in your proof.
(a) Prove the goal using structural induction.
(b) Prove the goal using complete induction on the number of logical operators (∧, ∨, and ¬) that is used in formula f.