0
$\begingroup$

A set of propositional formulas $P_1, \cdots, P_k$ is consistent iff there is an environment in which they are all true.

Write a formula, $S$, so that the set $P_1, \cdots, P_k$ is not consistent iff $S$ is valid.

Sorry for asking this homework question. I really don't know how to solve it.

$\endgroup$
1
$\begingroup$

Let $S := \lnot (P_1 \land \ldots \land P_k)$.

If $\{ P_1, \ldots, P_k \}$ is inconsistent (i.e. unsatisfiable), then $(P_1 \land \ldots \land P_k)$ is always false, and thus its negation is a tautology (i.e. valid).

If $S$ is valid, then $(P_1 \land \ldots \land P_k)$ is always false (a contradiction) and thus there is no truth assignment that can simultaneously satisfy all the $P_i$'s, i.e. $\{ P_1, \ldots, P_k \}$ is unsatisfiable (i.e. inconsistent).


According to your post

a set $F$ of formulas is consistent iff there is a truth-assignment such that all the formulas of $F$ are true.

Thus, inconsistent (the negation of consistent) means that there is no truth-assignment for which the formulas are all true.

This in turn means that there is no truth-assignment that simultaneously satisfies all formulas, and this amounts to saying that the set of formulas is unsatisfiable.

$\endgroup$
  • $\begingroup$ The proof is pretty good and clear. But I don't understand what the '(i.e. unsatisfiable)' means? $\{P_1, \cdots, P_k\}$ is a set. A set does not poess the property of satisfiability which is the quality of a proposition formula. $\endgroup$ – 王文军 or Wenjun Wang Mar 14 at 6:41

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.