Expressive completeness and decidability (Q2277437)

This short paper first addresses the question of under what conditions of a finite set of (2-valued) truth functional connectives, it is decidable whether that set is expressively complete. The authors first prove a theorem, due to Post, setting truth-table conditions on connectives in the set. They also prove a theorem on the degree of formulae generated by these connectives. Finally, after a short discussion on the Turing representation of truth-functional connectives, they show that ``there is no effective procedure that, given a recursive specification of a finite set of connectives, decides whether the set is expressivley complete''.