1

I am preparing for exams and am struggling to understand the theory in my textbook. Can someone please confirm if I understand this correctly.

Propositional logic is decidable and you can prove it because you can construct a truth table got any propositional logic formula

Predicate logic is undecidable because the truth table method does not work since there are infinitely many models that can be applied.

To me it makes perfect sense, but is it a valid explanation?

  • The explanation is not completely valid. It depends on what sort of predicate logic you use and what sort of objects you apply it to. – reinierpost Nov 16 '15 at 10:00
3

The first statement is right.

For the second one, while it is right your explanation why truth table method does not give us an algorithm for predicate logic, from this fact does not follow that some other algorithm cannot exist.

The existence of an algorithm for predicate logic is ruled out by a theorem of Alonzo Church.

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.