A set $\sum$ of formulas in propositional logic is complete if for each propositional formula $\phi$ either $\sum \vdash \phi$ or $\sum \vdash \neg \phi$. Clearly every inconsistent set of formulas is complete because of the following lemma



> 
> Lemma: Let $\sum$ be an inconsistent set, then for every propositional formula $\phi$ , $\sum \vdash \phi$
> 
> 
> 


So the important thing is determining whether a consistent set of formulas is complete or not. I would like to know is there any method to find out whether a consistent set of formulas is complete or not? and Is this method decidable or not?


As an example the following sets are complete ($\downarrow$ means **NOR**)


$\{p\_1,p\_1 \leftrightarrow p\_2,p\_2 \leftrightarrow p\_3,p\_3 \leftrightarrow p\_4,... \}$


$\{p\_1 \downarrow p\_2,p\_2 \downarrow p\_3,p\_3 \downarrow p\_4,p\_4 \downarrow p\_5,...\}$ 


But this one is not 


$\{\neg p\_1 , p\_1 \vee p\_2,p\_1 \vee p\_2 \vee p\_3,p\_1 \vee p\_2 \vee p\_3 \vee p\_4 , ... \}$



Completeness of a set of propositional formulas
Given a finite propositional theory, one can decide completeness by checking the truth table. As Emil mentions, in general completeness for a finite theory will be NP-complete.


But your examples are infinite. In this case, one needs to take more care with the precise formulation of the question. For the decidability question, how are we to give the theory as input? If the theory is given by means of a program that will enumerate the sentences of the theory, then the problem of determining whether or not it is complete will not be computable, basically because of Rice's theorem. If there were an algorithm that decided completeness, we could start enumerating a complete theory until the algorithm output the answer, and then switch to an incomplete theory to get a contradiction, using the recursion theorem.


