5
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – No one Mar 9 '15 at 19:56
  • $\begingroup$ 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? $\endgroup$ – No one Mar 9 '15 at 21:10
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.