I am requested to build a proof for the following I am requested to prove the following statement, however I have no idea on how to begin... Does any of you know how can I do such induction on the structure? Maybe you could give me a link with some similar approach, or give me a text book on this theme...

A predicate logic formula $\phi$ belongs to the negative fragment if $\phi$ can be constructed from the following grammar, where $t_1, t_2,..., t_n (n>0)$ are terms:

$\phi::= \hspace{2 mm}\neg p(t_1, t_2,..., t_n)\hspace{2 mm} ||\hspace{2 mm}\bot\hspace{2 mm}||\hspace{2 mm}(\neg\phi) \hspace{2 mm} ||\hspace{2 mm}(\phi\land\phi)\hspace{2 mm}||\hspace{2 mm}(\phi\rightarrow\phi)\hspace{2 mm}||\hspace{2 mm}(\forall_x \phi)$

Prove in minimal logic that $\neg\neg\theta \vdash_m \theta$ for any formula $\theta$ belonging to the negative fragment. Use induction on the structure of $\theta$.



Browse other questions tagged or ask your own question.