Proving that the number of atoms in a formula is equal to the number of the symbols $\land,\lor,\rightarrow$ plus 1

75 Views Asked by At

This is only correct for a formula only having the symbols $\land,\lor,\rightarrow$ .The proof behind this shouldn't be complicated but i'm having difficulty writing the induction step since I'm a novice with proofs by inductions.

I have started the proof like this: let $C(\varphi)$ be the number of occurences of the symbols $\land,\lor,\rightarrow$,and let $S(\varphi)$ be the number of atoms for a well formed formula $\varphi$.

Base step:$\varphi$ is an atom ,then $C(\varphi)=0,S(\varphi)=C(\varphi)+1=1.$

Induction step:Here i'm thinking of taking some $S(\varphi_1),S(\varphi_2)$ for a well formed formulas and then checking the 3 cases where i do $S(\varphi_3)=S(\varphi_1\lor\varphi_2) \implies S(\varphi_3)=S(\varphi_1)+S(\varphi_2)+1.$ similiary for $\land,\rightarrow...$

Is my induction step correct? if so i need a little help in writing it correctly to be considered a proper proof because i'm thinking that i'm failing to do that.

1

There are 1 best solutions below

9
On BEST ANSWER

The idea is correct. You only need to notice that

$$ S(\varphi_3) = S(\varphi_1 \land \varphi_2) = S(\varphi_1) + S(\varphi_2) = C(\varphi_1) + 1 + C(\varphi_2) + 1 = C(\varphi_1)+ C(\varphi_2) + 2$$

and

$$ C(\varphi_3) = C(\varphi_1 \land \varphi_2) = C(\varphi_1) + C(\varphi_2) + 1$$

You don't really need to distinguish the $3$ cases as we are not really using the properties of the connectives.