# Deciding Consistency

Decide if the following subsets of Form are consistent: $$\{P_{1} \lor P_{2}, P_{2} \lor \neg P_{3},\neg P_{3} \lor \neg P_{4}, P_{3} \lor \neg P_{1}, \neg P_{2} \lor P_{4}\}$$

$$\{ P_{1} \to P_{2},P_{2} \to P_{3}, P_{3} \to \neg P_{1}, P_{4} \to P_{2}, P_{3} \to \neg P_{4}, \neg P_{4} \to P_{1}\}$$

How exactly does one go about? Do you show that a subset of Form is consistent if you show that is a tautology?

## 1 Answer

Do you mean semantic consistency or syntactic consistency?

The propositional formulae $\varphi_1, \varphi_2, \ldots \varphi_n$ are semantically consistent if and only if there is a valuation of all the atoms which appear in (one or more of) the formulae which makes them all true together.

The brute force method for seeing whether this is so is to do a simultaneous truth-table evaluating all those formulae (for every valuation of the atoms in the $\varphi_j$) and check whether there is a line of the truth-table where the $\varphi_j$ all come out true together.

The propositional formulae $\varphi_1, \varphi_2, \ldots \varphi_n$ are syntactically consistent [in your favourite proof-system $L$] if there is no $L$-proof from premisses $\varphi_1, \varphi_2, \ldots \varphi_n$ to a contradiction.

But since the soundness and completeness proofs for $L$ tell you that $\varphi_1, \varphi_2, \ldots \varphi_n$ are syntactically consistent if and only if they are semantically consistent, you can use the same truth-table test for semantic consistency to check whether they are syntactically consistent too.

See also the answer to Proving and Modeling Logical Consistence