1

Here's my attempt to prove that all positive formulae are satisfiable (where positive formula is defined as a propositional formula that does not contain a negation, and the operators are "^" (and), "V" (or), "->" (implies), and "<->" (if and only if)):

Proof by induction:

Base Cases:

p ^ q: Satisfiable - True for p = T and q = T
p V q: Satisfiable - True for p = T and q = T
p -> q: Satisfiable - True for p = T and q = T
p <-> q: Satisfiable - True for p = T and q = T

Inductive Hypothesis: 

All positive formulae are satisfiable, and are true by the valuation
of all propositional symbols being True.

Inductive Step:

A positive formula can be either an atomic proposition, or constructed from other formulae, which must not contain negations by definition of positive formula, therefore a compound positive formula must be built from positive formulae. Denote these positive formulae by f1, f2...There are only 4 ways to construct a compound positive formula:

f1 ^ f2: Satisfiable - True for f1 = T and f2 = T
f1 V f2: Satisfiable - True for f1 = T and f2 = T
f1 -> f2: Satisfiable - True for f1 = T and f2 = T
f1 <-> f2: Satisfiable - True for f1 = T and f2 = T

We know that f1 and f2 can be true at the same time because we can just set all the propositional symbols included in either or both of the formulae to be True, and then by the Inductive Hypothesis this valuation would set both formulae to be True as well.

What I'm not sure about this proof is if the inductive hypothesis I used is reasonable or not, and if I used it in the right way.

Is my attempt at a proof correct?

user2108462
  • 387

1 Answers1

2

Your inductive hypothesis needs to be "$f_1$ and $f_2$ are satisfied by the valuation assigning $\top$ to every variable," rather than "every positive formula is satisfied by the valuation assigning $\top$ to every variable," which is your desired conclusion.

Note that (as I think you already see) the inductive hypothesis needs to be "$f_1$ and $f_2$ are satisfied by the valuation assigning $\top$ to every variable," not just "$f_1$ and $f_2$ are satisfiable." Otherwise there is no guarantee that the valuation satisfying $f_1$ and the valuation satisfying $f_2$ can be chosen to be compatible.

This exercise is a good example of proving a stronger statement (every positive formula is satisfied by the valuation assigning $\top$ to every variable) by induction, and then observing at the end that a weaker statement (every positive formula is satisfiable) follows immediately, which is a common proof technique.

In your base case, you should consider a formula consisting of a single propositional variable (e.g. $p$,) assuming that this meets your definition of "formula" (which it really should.) In addition to covering this trivial case, such a modification will make the proof in the base case simpler because you won't have to duplicate any work from the inductive step.

Trevor Wilson
  • 16,989
  • You mean I can replace my current base case with base cases consisting of the single propositional variable? – user2108462 May 22 '14 at 21:37
  • 1
    That's right; in fact, you need to because otherwise you don't prove anything about the case where the formula is a single propositional variable (which should count as a positive formula.) The induction should follow the recursive definition of "positive formula." – Trevor Wilson May 22 '14 at 21:38