0

For a formula α ∈ WFF we let (α) denote the number of symbols in α that are left brackets ‘(’, let v(α) the number of variable symbols, and c(α) the number of symbols that are the NOT symbol ‘¬’. For example in ((p1 → p2) ∧ ((¬p1) → p2)) we have (α) = 4, v(α) = 4 and c(α) = 1.

Prove by induction that he following property holds for all well formed formulas:

    l(α)= v(α) + c(α) −1

For the Base case I did let l(α)= 1, v(α) = 1 and c(α) = 1 which would hold true for the above formula but I am confused as to what would the Hypothesis and induction step would be.

Jazib Khan
  • 1

1 Answers1

1

Your base case will be showing that all literals (like $p_1$) satisfy the condition. Then your induction step is showing that if $A$ and $B$ are wffs that satisfy the condition, then $(\neg A$), $(A\wedge B)$, $(A\to B)$, and whatever other propositional connectives you have defined in your system also satisfy the condition.