• Jan 31st 2013, 04:15 PM
Manueldodo
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.

InductionStep: f∈F¬f∈F
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 fare 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.
• Jan 31st 2013, 05:19 PM
emakarov
Do you know what structural induction and complete induction are? Have you read example proofs using these methods? Do you understand the recursive definition of formulas? (By the way, what do "sorted lists of integers" have to do with formulas?) In other words, please describe precisely your difficulty.
• Jan 31st 2013, 05:31 PM
Manueldodo
"3. We can define sorted lists of integers as follows. " <- sorry I added it accidentally. I know how to get –∀f∈F¬f∈F
– ∀f1,f2 ∈F f1 ∧f2 ∈F
– ∀f1,f2 ∈F f1 ∨f2 ∈F.
By that I mean that I have a base case, Induction Hypothesis. I know how to get to "1 ∧f2 ∈F, f1 ∨f2 ∈F etc". But then I dont know what to do to get the goal that he only negation symbols (“¬”) in f′ are applied to individual propositional variables ;(
• Jan 31st 2013, 06:18 PM
emakarov
Quote:

Originally Posted by Manueldodo
"3. We can define sorted lists of integers as follows. " <- sorry I added it accidentally. I know how to get –∀f∈F¬f∈F
– ∀f1,f2 ∈F f1 ∧f2 ∈F
– ∀f1,f2 ∈F f1 ∨f2 ∈F.
By that I mean that I have a base case, Induction Hypothesis. I know how to get to "1 ∧f2 ∈F, f1 ∨f2 ∈F etc".

What you wrote is a definition, not a proof. As such, it does not have an induction hypothesis. I'll assume that you understand the recursive definition of formulas, but you still have not answered the other questions in post #2. At the moment, I can't find an easy tutorial on structural induction on the Internet. You should check your textbook or lecture notes for example proofs.

If f is a propositional formula, let N(f) mean that negations in f are applied to propositional variables only. Also, let E(f) mean that there exists a formula f' such that f is equivalent to f' and N(f'). You need to prove E(f) for all formulas f.

Structural induction works as follows. First you need to show E(p) for any propositional variable p. Then show that if E(f) and E(g) for some formulas f and g, then E(f \/ g), E(f /\ g) and E(~f).
• Jan 31st 2013, 06:27 PM
Manueldodo
thank u! I got it. One more question: how deal with this condition: Prove the goal using complete induction on the number of logical operators (∧, ∨, and ¬) that is used in formula f TO THE SAME PROBLEM?
• Jan 31st 2013, 06:35 PM
emakarov
Quote:

Originally Posted by Manueldodo
One more question: how deal with this condition: Prove the goal using complete induction on the number of logical operators (∧, ∨, and ¬) that is used in formula f TO THE SAME PROBLEM?

This proof uses induction on natural numbers, but where in the induction step you assume not just P(n), but all of P(0), P(1), ..., P(n) to prove P(n + 1). This is often called strong induction.

In this case, P(n) means that for all formulas f, if f has n logical operators, then E(f). For the induction step, assume P(0), ..., P(n) and let some formula f have n + 1 operators. Then f has to have the form f1 /\ f2, f1 \/ f2 or ~f1 for some f1, f2. What can be said about the number of operators in f1 and f2? Do you see why assuming just P(n) is not enough?
• Jan 31st 2013, 06:51 PM
Manueldodo
I see why P(n) is not enough. So assuming that P(0)....P(n) is true, then number of operators in f1 and f2 is going to be n+1 operators.....even number of operators((
• Jan 31st 2013, 06:56 PM
emakarov
Quote:

Originally Posted by Manueldodo
I see why P(n) is not enough.

Then why?

Quote:

Originally Posted by Manueldodo
So assuming that P(0)....P(n) is true, then number of operators in f1 and f2 is going to be n+1 operators

By the "number of operators in f1 and f2," do you mean the number of operators in f1plus the number of operators in f2? Even so, this number is one less than the number of operators in f1 /\ f2.

Quote:

Originally Posted by Manueldodo
even number of operators((

Why do you think it is even?
• Jan 31st 2013, 07:00 PM
Manueldodo