2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

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