# How to find out if a set of Propositional formulas is complete?

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?

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 , ... \}$

UPDATE:

From what I tried, I got this

$$\{\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 , ... \} \nvdash p_1$$

Because when we write $$\{\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 , ... \} \vdash p_1$$

it means every model for the left side (satisfies every element of the set) must be a model for the right side, But there is no way to find a model to satisfy $$\{\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 , ... \} \vdash p_1$$

because every element of the left side must be $T$ so $\neg p_1$ must be $T$ so it means $p_1 = F$ it concludes that the right side is $F$, the same reasoning holds for $$\{\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 , ... \} \vdash \neg p_1$$ so I found the propositional formula $p_1$ such that $$\{\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 , ... \} \nvdash p_1$$ and $$\{\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 , ... \} \nvdash \neg p_1$$ so as a result $$\{\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 , ... \}$$ is not complete.But I was looking for a more algorithmic (even a semi-decidable one) to solve the problem.

• What do those downarrows mean? I haven't seen them used in logic before. – Fizz Feb 7 '15 at 9:08
• Is it "nor" maybe? – Fizz Feb 7 '15 at 10:12
• @RespawnedFluff yes it is NOR – No one Feb 19 '15 at 4:43

So, to state what is probably obvious, a set of propositions is consistent if there is at least one assignment of truth values to literals that makes all the propositions true; and a set of propositions is complete if there is at most one such assignment. For the set of propositions to be both consistent and complete, then, there must be a unique satisfying assignment of truth values. To show it is not complete, then, you just need to exhibit two satisfying assignments. In your example, for instance, the assignments $$\{F, T, T, T, T, \ldots \}$$ and $$\{F, T, F, F, F, \ldots\}$$ both make all the propositions true.

• I couldn't understand this statement: and a set of propositions is complete if there is at most one such assignment why is it true? – No one Mar 9 '15 at 19:56
• I couldn't understand this statement: and a set of propositions is complete if there is at most one such assignment why is it true? – No one Mar 9 '15 at 21:10

I suspect the terminology (complete set of formulas) is in the context of the completeness theorem for propositional calculus. In this context it means this:

Let Σ be a set of formulas in a language L. Σ is complete for L if it is consistent and for each formula [literal] φ in L, exactly one of φ and ¬φ belongs to Σ.

So, unless you spell out what the language (''L'') is, you cannot say if a set of propositional formulas is complete or not.

Basically the same def appears in another book.

Also, your example $\{ p_1, p_2 , p_3,\neg (p_1 \vee p_2 \vee p_3)\}$ is not consistent (so not complete according to the above) because it implies both $p_1$ and $\neg p_1$.